use std::fmt::Debug;

use crate::{
    ast::{Atom, Error, Expr, LetVar, Parser, parser::MAX_DEPTH, tests::E::*},
    lex::Token::{self, *},
    span::{Pos, Span, Spanned},
};

#[derive(Debug, PartialEq)]
enum E {
    Int(i64),
    Str(&'static str),
    Sym(&'static str),
    Bool(bool),
    Nil,
    Fn(&'static str, Vec<&'static str>, Vec<E>),
    Const(Vec<(&'static str, E)>),
    Let(Vec<(&'static str, E)>, Vec<E>),
    If(Box<E>, Box<E>, Option<Box<E>>),
    For(&'static str, Box<E>, Box<E>, Vec<E>),
    Set(&'static str, Box<E>),
    Do(Vec<E>),
    Call(&'static str, Vec<E>),
}

fn leak(s: &str) -> &'static str {
    Box::leak(s.to_string().into_boxed_str())
}

fn convert_var(var: LetVar) -> (&'static str, E) {
    (leak(&var.name.inner), var.expr.inner.into())
}

impl From<Expr> for E {
    fn from(expr: Expr) -> Self {
        match expr {
            Expr::Atom(atom) => match atom {
                Atom::Int(i) => Int(i),
                Atom::Str(s) => Str(leak(&s)),
                Atom::Sym(s) => Sym(leak(&s)),
                Atom::Bool(b) => Bool(b),
                Atom::Nil => Nil,
            },
            Expr::Fn { name, args, body } => Fn(
                leak(&name.inner),
                args.into_iter().map(|a| leak(&a.inner)).collect(),
                body.into_iter().map(|e| e.inner.into()).collect(),
            ),
            Expr::Const { vars } => Const(vars.into_iter().map(|v| convert_var(v.inner)).collect()),
            Expr::Let { vars, body } => Let(
                vars.into_iter().map(|v| convert_var(v.inner)).collect(),
                body.into_iter().map(|e| e.inner.into()).collect(),
            ),
            Expr::If {
                condition,
                then_expr,
                else_expr,
            } => If(
                Box::new(E::from(*condition.inner)),
                Box::new(E::from(*then_expr.inner)),
                else_expr.map(|e| Box::new(E::from(*e.inner))),
            ),
            Expr::For {
                loop_var,
                from,
                to,
                body,
            } => For(
                leak(&loop_var.inner),
                Box::new(E::from(*from.inner)),
                Box::new(E::from(*to.inner)),
                body.into_iter().map(|e| e.inner.into()).collect(),
            ),
            Expr::Set { target_var, expr } => {
                Set(leak(&target_var.inner), Box::new(E::from(*expr.inner)))
            }
            Expr::Do { body } => Do(body.into_iter().map(|e| e.inner.into()).collect()),
            Expr::Call { fn_name, args } => Call(
                leak(&fn_name.inner),
                args.into_iter().map(|e| e.inner.into()).collect(),
            ),
        }
    }
}

fn dummy_tokens(tokens: Vec<Token<'static>>) -> impl Iterator<Item = Spanned<Token<'static>>> {
    let span = Span::new(Pos::new(0, 0, 0), Pos::new(0, 0, 0));
    tokens.into_iter().map(move |t| Spanned::new(t, span))
}

fn parse(tokens: Vec<Token<'static>>) -> Vec<E> {
    Parser::new(dummy_tokens(tokens))
        .parse()
        .unwrap()
        .into_inner()
        .into_iter()
        .map(|e| e.inner.into())
        .collect()
}

#[test]
fn test_empty() {
    assert_eq!(parse(vec![]), vec![], "input: empty");
}

#[test]
fn test_integers() {
    let cases = vec![
        (vec![Number("0")], vec![Int(0)]),
        (vec![Number("42")], vec![Int(42)]),
        (vec![Number("-7")], vec![Int(-7)]),
        (vec![Number("+5")], vec![Int(5)]),
        (vec![Number("9223372036854775807")], vec![Int(i64::MAX)]),
        (vec![Number("-9223372036854775808")], vec![Int(i64::MIN)]),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_keywords() {
    let cases = vec![
        (vec![Symbol("true")], vec![Bool(true)]),
        (vec![Symbol("false")], vec![Bool(false)]),
        (vec![Symbol("nil")], vec![Nil]),
        (vec![LeftPar, RightPar], vec![Nil]),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_keywords_case_sensitive() {
    let cases = vec![
        (vec![Symbol("True")], vec![Sym("True")]),
        (vec![Symbol("FALSE")], vec![Sym("FALSE")]),
        (vec![Symbol("NIL")], vec![Sym("NIL")]),
        (vec![Symbol("Nil")], vec![Sym("Nil")]),
        (vec![Symbol("Inf")], vec![Sym("Inf")]),
        (vec![Symbol("INF")], vec![Sym("INF")]),
        (vec![Symbol("NaN")], vec![Sym("NaN")]),
        (vec![Symbol("NAN")], vec![Sym("NAN")]),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_symbols() {
    let cases = vec![
        (vec![Symbol("foo")], vec![Sym("foo")]),
        (vec![Symbol("foo-bar")], vec![Sym("foo-bar")]),
        (vec![Symbol("set!")], vec![Sym("set!")]),
        (vec![Symbol("empty?")], vec![Sym("empty?")]),
        (vec![Symbol("+")], vec![Sym("+")]),
        (vec![Symbol("-")], vec![Sym("-")]),
        (vec![Symbol("<=")], vec![Sym("<=")]),
        (vec![Symbol(",")], vec![Sym(",")]),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_strings() {
    let cases = vec![
        (vec![String("")], vec![Str("")]),
        (vec![String("hello")], vec![Str("hello")]),
        (vec![String("(not a list)")], vec![Str("(not a list)")]),
        (
            vec![String("; not a comment")],
            vec![Str("; not a comment")],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_string_escapes() {
    let cases = vec![
        (vec![String(r"a\nb")], vec![Str("a\nb")]),
        (vec![String(r#"a\"b"#)], vec![Str("a\"b")]),
        (vec![String("a\\\nb")], vec![Str("ab")]),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_call() {
    let cases = vec![
        // (foo 1)
        (
            vec![LeftPar, Symbol("foo"), Number("1"), RightPar],
            vec![Call("foo", vec![Int(1)])],
        ),
        // (+ 1 2 3)
        (
            vec![
                LeftPar,
                Symbol("+"),
                Number("1"),
                Number("2"),
                Number("3"),
                RightPar,
            ],
            vec![Call("+", vec![Int(1), Int(2), Int(3)])],
        ),
        // (foo (bar 1) baz)
        (
            vec![
                LeftPar,
                Symbol("foo"),
                LeftPar,
                Symbol("bar"),
                Number("1"),
                RightPar,
                Symbol("baz"),
                RightPar,
            ],
            vec![Call("foo", vec![Call("bar", vec![Int(1)]), Sym("baz")])],
        ),
        // (f "s" foo true nil)
        (
            vec![
                LeftPar,
                Symbol("f"),
                String("s"),
                Symbol("foo"),
                Symbol("true"),
                Symbol("nil"),
                RightPar,
            ],
            vec![Call("f", vec![Str("s"), Sym("foo"), Bool(true), Nil])],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_fn() {
    let cases = vec![
        // (fn foo () 1)
        (
            vec![
                LeftPar,
                Symbol("fn"),
                Symbol("foo"),
                LeftPar,
                RightPar,
                Number("1"),
                RightPar,
            ],
            vec![Fn("foo", vec![], vec![Int(1)])],
        ),
        // (fn add (x y) (+ x y))
        (
            vec![
                LeftPar,
                Symbol("fn"),
                Symbol("add"),
                LeftPar,
                Symbol("x"),
                Symbol("y"),
                RightPar,
                LeftPar,
                Symbol("+"),
                Symbol("x"),
                Symbol("y"),
                RightPar,
                RightPar,
            ],
            vec![Fn(
                "add",
                vec!["x", "y"],
                vec![Call("+", vec![Sym("x"), Sym("y")])],
            )],
        ),
        // (fn id (x) x x)
        (
            vec![
                LeftPar,
                Symbol("fn"),
                Symbol("id"),
                LeftPar,
                Symbol("x"),
                RightPar,
                Symbol("x"),
                Symbol("x"),
                RightPar,
            ],
            vec![Fn("id", vec!["x"], vec![Sym("x"), Sym("x")])],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_const() {
    let cases = vec![
        // (const (x 1))
        (
            vec![
                LeftPar,
                Symbol("const"),
                LeftPar,
                Symbol("x"),
                Number("1"),
                RightPar,
                RightPar,
            ],
            vec![Const(vec![("x", Int(1))])],
        ),
        // (const (x 1) (y 2))
        (
            vec![
                LeftPar,
                Symbol("const"),
                LeftPar,
                Symbol("x"),
                Number("1"),
                RightPar,
                LeftPar,
                Symbol("y"),
                Number("2"),
                RightPar,
                RightPar,
            ],
            vec![Const(vec![("x", Int(1)), ("y", Int(2))])],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_let() {
    let cases = vec![
        // (let ((x 1)) x)
        (
            vec![
                LeftPar,
                Symbol("let"),
                LeftPar,
                LeftPar,
                Symbol("x"),
                Number("1"),
                RightPar,
                RightPar,
                Symbol("x"),
                RightPar,
            ],
            vec![Let(vec![("x", Int(1))], vec![Sym("x")])],
        ),
        // (let ((x 1) (y 2)) (+ x y))
        (
            vec![
                LeftPar,
                Symbol("let"),
                LeftPar,
                LeftPar,
                Symbol("x"),
                Number("1"),
                RightPar,
                LeftPar,
                Symbol("y"),
                Number("2"),
                RightPar,
                RightPar,
                LeftPar,
                Symbol("+"),
                Symbol("x"),
                Symbol("y"),
                RightPar,
                RightPar,
            ],
            vec![Let(
                vec![("x", Int(1)), ("y", Int(2))],
                vec![Call("+", vec![Sym("x"), Sym("y")])],
            )],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_if() {
    let cases = vec![
        // (if true 1 2)
        (
            vec![
                LeftPar,
                Symbol("if"),
                Symbol("true"),
                Number("1"),
                Number("2"),
                RightPar,
            ],
            vec![If(
                Box::new(Bool(true)),
                Box::new(Int(1)),
                Some(Box::new(Int(2))),
            )],
        ),
        // (if true 1)
        (
            vec![LeftPar, Symbol("if"), Symbol("true"), Number("1"), RightPar],
            vec![If(Box::new(Bool(true)), Box::new(Int(1)), None)],
        ),
        // (if (= x 0) a b)
        (
            vec![
                LeftPar,
                Symbol("if"),
                LeftPar,
                Symbol("="),
                Symbol("x"),
                Number("0"),
                RightPar,
                Symbol("a"),
                Symbol("b"),
                RightPar,
            ],
            vec![If(
                Box::new(Call("=", vec![Sym("x"), Int(0)])),
                Box::new(Sym("a")),
                Some(Box::new(Sym("b"))),
            )],
        ),
        // (if true (do 1 2) (do 3 4))
        (
            vec![
                LeftPar,
                Symbol("if"),
                Symbol("true"),
                LeftPar,
                Symbol("do"),
                Number("1"),
                Number("2"),
                RightPar,
                LeftPar,
                Symbol("do"),
                Number("3"),
                Number("4"),
                RightPar,
                RightPar,
            ],
            vec![If(
                Box::new(Bool(true)),
                Box::new(Do(vec![Int(1), Int(2)])),
                Some(Box::new(Do(vec![Int(3), Int(4)]))),
            )],
        ),
        // (if nil nil)
        (
            vec![
                LeftPar,
                Symbol("if"),
                Symbol("nil"),
                Symbol("nil"),
                RightPar,
            ],
            vec![If(Box::new(Nil), Box::new(Nil), None)],
        ),
        // (if true (if false 1 2) 3)
        (
            vec![
                LeftPar,
                Symbol("if"),
                Symbol("true"),
                LeftPar,
                Symbol("if"),
                Symbol("false"),
                Number("1"),
                Number("2"),
                RightPar,
                Number("3"),
                RightPar,
            ],
            vec![If(
                Box::new(Bool(true)),
                Box::new(If(
                    Box::new(Bool(false)),
                    Box::new(Int(1)),
                    Some(Box::new(Int(2))),
                )),
                Some(Box::new(Int(3))),
            )],
        ),
        // (if true 1 (if false 2 3))
        (
            vec![
                LeftPar,
                Symbol("if"),
                Symbol("true"),
                Number("1"),
                LeftPar,
                Symbol("if"),
                Symbol("false"),
                Number("2"),
                Number("3"),
                RightPar,
                RightPar,
            ],
            vec![If(
                Box::new(Bool(true)),
                Box::new(Int(1)),
                Some(Box::new(If(
                    Box::new(Bool(false)),
                    Box::new(Int(2)),
                    Some(Box::new(Int(3))),
                ))),
            )],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_for() {
    let cases = vec![
        // (for i from 0 to 10 i)
        (
            vec![
                LeftPar,
                Symbol("for"),
                Symbol("i"),
                Symbol("from"),
                Number("0"),
                Symbol("to"),
                Number("10"),
                Symbol("i"),
                RightPar,
            ],
            vec![For(
                "i",
                Box::new(Int(0)),
                Box::new(Int(10)),
                vec![Sym("i")],
            )],
        ),
        // (for i from 0 to 10 i (+ i 1))
        (
            vec![
                LeftPar,
                Symbol("for"),
                Symbol("i"),
                Symbol("from"),
                Number("0"),
                Symbol("to"),
                Number("10"),
                Symbol("i"),
                LeftPar,
                Symbol("+"),
                Symbol("i"),
                Number("1"),
                RightPar,
                RightPar,
            ],
            vec![For(
                "i",
                Box::new(Int(0)),
                Box::new(Int(10)),
                vec![Sym("i"), Call("+", vec![Sym("i"), Int(1)])],
            )],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_set() {
    let cases = vec![
        // (set x 5)
        (
            vec![LeftPar, Symbol("set"), Symbol("x"), Number("5"), RightPar],
            vec![Set("x", Box::new(Int(5)))],
        ),
        // (set x (+ x 1))
        (
            vec![
                LeftPar,
                Symbol("set"),
                Symbol("x"),
                LeftPar,
                Symbol("+"),
                Symbol("x"),
                Number("1"),
                RightPar,
                RightPar,
            ],
            vec![Set("x", Box::new(Call("+", vec![Sym("x"), Int(1)])))],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_do() {
    let cases = vec![
        // (do 1)
        (
            vec![LeftPar, Symbol("do"), Number("1"), RightPar],
            vec![Do(vec![Int(1)])],
        ),
        // (do 1 2 3)
        (
            vec![
                LeftPar,
                Symbol("do"),
                Number("1"),
                Number("2"),
                Number("3"),
                RightPar,
            ],
            vec![Do(vec![Int(1), Int(2), Int(3)])],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_top_level() {
    let cases = vec![
        (
            vec![Number("1"), Number("2"), Number("3")],
            vec![Int(1), Int(2), Int(3)],
        ),
        (
            vec![
                LeftPar,
                Symbol("a"),
                Number("1"),
                RightPar,
                LeftPar,
                Symbol("b"),
                Number("2"),
                RightPar,
            ],
            vec![Call("a", vec![Int(1)]), Call("b", vec![Int(2)])],
        ),
    ];
    for (tokens, expected) in cases {
        assert_eq!(parse(tokens.clone()), expected, "input: {tokens:?}");
    }
}

fn parse_err(tokens: Vec<Token<'static>>) -> Error {
    Parser::new(dummy_tokens(tokens)).parse().unwrap_err().inner
}

#[test]
fn test_unexpected_close_par() {
    let cases = vec![
        // )
        vec![RightPar],
        // 1 )
        vec![Number("1"), RightPar],
        // (a) )
        vec![LeftPar, Symbol("a"), RightPar, RightPar],
        // (do)
        vec![LeftPar, Symbol("do"), RightPar],
        // (set x)
        vec![LeftPar, Symbol("set"), Symbol("x"), RightPar],
        // (let ((x 1)))
        vec![
            LeftPar,
            Symbol("let"),
            LeftPar,
            LeftPar,
            Symbol("x"),
            Number("1"),
            RightPar,
            RightPar,
            RightPar,
        ],
    ];
    for tokens in cases {
        assert_eq!(
            parse_err(tokens.clone()),
            Error::UnexpectedClosePar,
            "input: {tokens:?}"
        );
    }
}

#[test]
fn test_unclosed_par() {
    let cases = vec![
        // (foo
        vec![LeftPar, Symbol("foo")],
        // (foo 1
        vec![LeftPar, Symbol("foo"), Number("1")],
        // (foo 1 2
        vec![LeftPar, Symbol("foo"), Number("1"), Number("2")],
        // (foo (bar 1)
        vec![
            LeftPar,
            Symbol("foo"),
            LeftPar,
            Symbol("bar"),
            Number("1"),
            RightPar,
        ],
    ];
    for tokens in cases {
        assert_eq!(
            parse_err(tokens.clone()),
            Error::UnclosedPar,
            "input: {tokens:?}"
        );
    }
}

#[test]
fn test_unexpected_eof() {
    let cases = vec![
        // (
        vec![LeftPar],
        // (fn foo ()
        vec![LeftPar, Symbol("fn"), Symbol("foo"), LeftPar, RightPar],
    ];
    for tokens in cases {
        assert_eq!(
            parse_err(tokens.clone()),
            Error::UnexpectedEof,
            "input: {tokens:?}"
        );
    }
}

#[test]
fn test_unexpected_token() {
    let cases = vec![
        // (1 2 3)
        vec![LeftPar, Number("1"), Number("2"), Number("3"), RightPar],
        // (())
        vec![LeftPar, LeftPar, RightPar, RightPar],
        // ("hello")
        vec![LeftPar, String("hello"), RightPar],
        // (for)
        vec![LeftPar, Symbol("for"), RightPar],
        // (fn)
        vec![LeftPar, Symbol("fn"), RightPar],
    ];
    for tokens in cases {
        assert_eq!(
            parse_err(tokens.clone()),
            Error::UnexpectedToken,
            "input: {tokens:?}"
        );
    }
}

#[test]
fn test_invalid_integer() {
    let cases = vec![
        "99999999999999999999",
        "-99999999999999999999",
        "+",
        "-",
        "",
        "1_000",
        "0x10",
        "1 2",
        "++1",
        "--1",
        "1,5",
        "10,40",
    ];
    for number in cases {
        let tokens = vec![Number(number)];
        let error = number.parse::<i64>().unwrap_err();
        assert_eq!(
            parse_err(tokens.clone()),
            Error::InvalidIntegerLiteral(number.into(), error),
            "input: {tokens:?}",
        );
    }
}

#[test]
fn test_unclosed_string() {
    let cases = vec![
        (
            vec![UnclosedString("oops")],
            Error::UnclosedString("oops".into()),
        ),
        (
            vec![String("oops\\")],
            Error::UnclosedString("oops\\".into()),
        ),
    ];
    for (tokens, error) in cases {
        assert_eq!(parse_err(tokens.clone()), error, "input: {tokens:?}");
    }
}

#[test]
fn test_unexpected_escape_char_propagates() {
    let tokens = vec![String(r"a\q")];
    assert_eq!(
        parse_err(tokens.clone()),
        Error::UnexpectedEscapeChar('q'),
        "input: {tokens:?}"
    );
}

fn run_with_large_stack(f: impl FnOnce() + Send + 'static) {
    std::thread::Builder::new()
        .stack_size(8 * 1024 * 1024)
        .spawn(f)
        .unwrap()
        .join()
        .unwrap();
}

#[test]
fn test_recursion_limit() {
    run_with_large_stack(|| {
        let n = MAX_DEPTH + 1;
        let mut tokens = Vec::with_capacity(n * 2 + 1 + n);
        for _ in 0..n {
            tokens.push(LeftPar);
            tokens.push(Symbol("foo"));
        }
        tokens.push(Number("1"));
        for _ in 0..n {
            tokens.push(RightPar);
        }
        assert_eq!(
            parse_err(tokens),
            Error::RecursionLimit,
            "input: {n} nested calls",
        );
    });
}

fn p(line: usize, column: usize, offset: usize) -> Pos {
    Pos::new(line, column, offset)
}

fn sp(s: (usize, usize, usize), e: (usize, usize, usize)) -> Span {
    Span::new(p(s.0, s.1, s.2), p(e.0, e.1, e.2))
}

fn tsp(t: Token<'static>, span: Span) -> Spanned<Token<'static>> {
    Spanned::new(t, span)
}

fn parse_sp(tokens: Vec<Spanned<Token<'static>>>) -> Vec<Spanned<Expr>> {
    Parser::new(tokens.into_iter())
        .parse()
        .unwrap()
        .into_inner()
}

fn parse_sp_err(tokens: Vec<Spanned<Token<'static>>>) -> Spanned<Error> {
    Parser::new(tokens.into_iter()).parse().unwrap_err()
}

#[test]
fn test_span_atom() {
    let s = sp((1, 0, 0), (1, 2, 2));
    let tokens = vec![tsp(Number("42"), s)];
    let prog = parse_sp(tokens.clone());

    assert_eq!(prog[0].span, s, "input: {tokens:?}");
}

#[test]
fn test_span_call_covers_parens() {
    // (foo 1)
    let lp = sp((1, 0, 0), (1, 1, 1));
    let foo = sp((1, 1, 1), (1, 4, 4));
    let one = sp((1, 5, 5), (1, 6, 6));
    let rp = sp((1, 6, 6), (1, 7, 7));
    let tokens = vec![
        tsp(LeftPar, lp),
        tsp(Symbol("foo"), foo),
        tsp(Number("1"), one),
        tsp(RightPar, rp),
    ];
    let prog = parse_sp(tokens.clone());

    assert_eq!(prog[0].span, sp((1, 0, 0), (1, 7, 7)), "input: {tokens:?}");

    if let Expr::Call { fn_name, args } = &prog[0].inner {
        assert_eq!(fn_name.span, foo, "input: {tokens:?}");
        assert_eq!(args[0].span, one, "input: {tokens:?}");
    } else {
        panic!("expected call, input: {tokens:?}");
    }
}

#[test]
fn test_span_empty_list_covers_parens() {
    // ()
    let lp = sp((1, 0, 0), (1, 1, 1));
    let rp = sp((1, 1, 1), (1, 2, 2));
    let tokens = vec![tsp(LeftPar, lp), tsp(RightPar, rp)];
    let prog = parse_sp(tokens.clone());

    assert_eq!(prog[0].inner, Expr::Atom(Atom::Nil), "input: {tokens:?}");
    assert_eq!(prog[0].span, sp((1, 0, 0), (1, 2, 2)), "input: {tokens:?}");
}

#[test]
fn test_error_span_unexpected_close_par() {
    // )
    let s = sp((1, 5, 5), (1, 6, 6));
    let tokens = vec![tsp(RightPar, s)];
    let err = parse_sp_err(tokens.clone());

    assert_eq!(err.inner, Error::UnexpectedClosePar, "input: {tokens:?}");
    assert_eq!(err.span, s, "input: {tokens:?}");
}

#[test]
fn test_error_span_invalid_integer() {
    let s = sp((1, 0, 0), (1, 20, 20));
    let tokens = vec![tsp(Number("99999999999999999999"), s)];
    let err = parse_sp_err(tokens.clone());

    assert_eq!(err.span, s, "input: {tokens:?}");
}

#[test]
fn test_error_span_unclosed_par() {
    // (foo 1
    let lp = sp((1, 0, 0), (1, 1, 1));
    let foo = sp((1, 1, 1), (1, 4, 4));
    let one = sp((1, 5, 5), (1, 6, 6));
    let tokens = vec![
        tsp(LeftPar, lp),
        tsp(Symbol("foo"), foo),
        tsp(Number("1"), one),
    ];
    let err = parse_sp_err(tokens.clone());

    assert_eq!(err.inner, Error::UnclosedPar, "input: {tokens:?}");
    assert_eq!(err.span, lp, "input: {tokens:?}");
}

#[test]
fn test_error_span_unclosed_par_nested() {
    // (foo (bar 1
    let outer = sp((1, 0, 0), (1, 1, 1));
    let foo = sp((1, 1, 1), (1, 4, 4));
    let inner = sp((1, 5, 5), (1, 6, 6));
    let bar = sp((1, 6, 6), (1, 9, 9));
    let one = sp((1, 10, 10), (1, 11, 11));
    let tokens = vec![
        tsp(LeftPar, outer),
        tsp(Symbol("foo"), foo),
        tsp(LeftPar, inner),
        tsp(Symbol("bar"), bar),
        tsp(Number("1"), one),
    ];
    let err = parse_sp_err(tokens.clone());

    assert_eq!(err.inner, Error::UnclosedPar, "input: {tokens:?}");
    assert_eq!(err.span, inner, "input: {tokens:?}");
}

#[test]
fn test_error_span_unexpected_eof() {
    // (
    let lp = sp((1, 0, 0), (1, 1, 1));
    let tokens = vec![tsp(LeftPar, lp)];
    let err = parse_sp_err(tokens.clone());

    assert_eq!(err.inner, Error::UnexpectedEof, "input: {tokens:?}");
    assert_eq!(err.span, lp, "input: {tokens:?}");
}

#[test]
fn test_error_span_unexpected_token() {
    // (1)
    let lp = sp((1, 0, 0), (1, 1, 1));
    let one = sp((1, 1, 1), (1, 2, 2));
    let rp = sp((1, 2, 2), (1, 3, 3));
    let tokens = vec![tsp(LeftPar, lp), tsp(Number("1"), one), tsp(RightPar, rp)];
    let err = parse_sp_err(tokens.clone());

    assert_eq!(err.inner, Error::UnexpectedToken, "input: {tokens:?}");
    assert_eq!(err.span, one, "input: {tokens:?}");
}

#[test]
fn test_error_span_unclosed_string() {
    let s = sp((1, 0, 0), (1, 7, 7));
    let tokens = vec![tsp(UnclosedString("oops"), s)];
    let err = parse_sp_err(tokens.clone());

    assert_eq!(
        err.inner,
        Error::UnclosedString("oops".into()),
        "input: {tokens:?}",
    );
    assert_eq!(err.span, s, "input: {tokens:?}");
}

#[test]
fn test_error_span_unexpected_escape_char() {
    let s = sp((1, 0, 0), (1, 5, 5));
    let tokens = vec![tsp(String(r"a\q"), s)];
    let err = parse_sp_err(tokens.clone());

    assert_eq!(
        err.inner,
        Error::UnexpectedEscapeChar('q'),
        "input: {tokens:?}"
    );
    assert_eq!(err.span, s, "input: {tokens:?}");
}

#[test]
fn test_error_span_deep_nested() {
    // (foo (bar (baz 99999999999999999999)))
    let bad_span = sp((1, 9, 9), (1, 29, 29));
    let any = sp((1, 0, 0), (1, 1, 1));
    let tokens = vec![
        tsp(LeftPar, any),
        tsp(Symbol("foo"), any),
        tsp(LeftPar, any),
        tsp(Symbol("bar"), any),
        tsp(LeftPar, any),
        tsp(Symbol("baz"), any),
        tsp(Number("99999999999999999999"), bad_span),
        tsp(RightPar, any),
        tsp(RightPar, any),
        tsp(RightPar, any),
    ];
    let err = parse_sp_err(tokens.clone());

    assert!(
        matches!(err.inner, Error::InvalidIntegerLiteral(..)),
        "input: {tokens:?}, got: {:?}",
        err.inner,
    );
    assert_eq!(err.span, bad_span, "input: {tokens:?}");
}

#[test]
fn test_error_span_recursion_limit() {
    run_with_large_stack(|| {
        let any = sp((0, 0, 0), (0, 0, 0));
        let mut tokens = Vec::with_capacity((MAX_DEPTH + 1) * 2);
        for i in 0..=MAX_DEPTH {
            let s = sp((1, i, i), (1, i + 1, i + 1));
            tokens.push(tsp(LeftPar, s));
            tokens.push(tsp(Symbol("foo"), any));
        }
        let trigger = sp((1, MAX_DEPTH, MAX_DEPTH), (1, MAX_DEPTH + 1, MAX_DEPTH + 1));
        let err = parse_sp_err(tokens);

        assert_eq!(err.inner, Error::RecursionLimit, "MAX_DEPTH={MAX_DEPTH}");
        assert_eq!(err.span, trigger, "MAX_DEPTH={MAX_DEPTH}");
    });
}

#[test]
fn test_keyword_prefixed_symbols() {
    let cases = vec![
        (vec![Symbol("fn-foo")], vec![Sym("fn-foo")]),
        (vec![Symbol("let1")], vec![Sym("let1")]),
        (vec![Symbol("from-here")], vec![Sym("from-here")]),
        (vec![Symbol("do!")], vec![Sym("do!")]),
        (vec![Symbol("set?")], vec![Sym("set?")]),
        (vec![Symbol("for-each")], vec![Sym("for-each")]),
        (vec![Symbol("const-x")], vec![Sym("const-x")]),
        (vec![Symbol("if-then")], vec![Sym("if-then")]),
        (vec![Symbol("iffy")], vec![Sym("iffy")]),
        (vec![Symbol("if?")], vec![Sym("if?")]),
        // (fn-foo 1)
        (
            vec![LeftPar, Symbol("fn-foo"), Number("1"), RightPar],
            vec![Call("fn-foo", vec![Int(1)])],
        ),
        // (set! x 1)
        (
            vec![LeftPar, Symbol("set!"), Symbol("x"), Number("1"), RightPar],
            vec![Call("set!", vec![Sym("x"), Int(1)])],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_long_symbol() {
    let long: &'static str = leak(&"a".repeat(10_000));
    let tokens = vec![Symbol(long)];
    assert_eq!(parse(tokens), vec![Sym(long)]);
}

#[test]
fn test_signed_zero() {
    let cases = vec![
        (vec![Number("+0")], vec![Int(0)]),
        (vec![Number("-0")], vec![Int(0)]),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_double_backslash_in_string() {
    let cases = vec![
        (vec![String(r"\\")], vec![Str("\\")]),
        (vec![String(r"a\\b")], vec![Str("a\\b")]),
        (vec![String(r"\\\\")], vec![Str("\\\\")]),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_nil_as_value() {
    let cases = vec![
        // (foo () bar)
        (
            vec![
                LeftPar,
                Symbol("foo"),
                LeftPar,
                RightPar,
                Symbol("bar"),
                RightPar,
            ],
            vec![Call("foo", vec![Nil, Sym("bar")])],
        ),
        // (do () nil ())
        (
            vec![
                LeftPar,
                Symbol("do"),
                LeftPar,
                RightPar,
                Symbol("nil"),
                LeftPar,
                RightPar,
                RightPar,
            ],
            vec![Do(vec![Nil, Nil, Nil])],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_special_form_errors() {
    let cases = vec![
        // (fn foo)
        (
            vec![LeftPar, Symbol("fn"), Symbol("foo"), RightPar],
            Error::UnexpectedToken,
        ),
        // (fn foo bar)
        (
            vec![
                LeftPar,
                Symbol("fn"),
                Symbol("foo"),
                Symbol("bar"),
                RightPar,
            ],
            Error::UnexpectedToken,
        ),
        // (fn 1 2)
        (
            vec![LeftPar, Symbol("fn"), Number("1"), Number("2"), RightPar],
            Error::UnexpectedToken,
        ),
        // (fn foo (1) body)
        (
            vec![
                LeftPar,
                Symbol("fn"),
                Symbol("foo"),
                LeftPar,
                Number("1"),
                RightPar,
                Symbol("body"),
                RightPar,
            ],
            Error::UnexpectedToken,
        ),
        // (let)
        (
            vec![LeftPar, Symbol("let"), RightPar],
            Error::UnexpectedToken,
        ),
        // (let () body)
        (
            vec![
                LeftPar,
                Symbol("let"),
                LeftPar,
                RightPar,
                Symbol("body"),
                RightPar,
            ],
            Error::UnexpectedToken,
        ),
        // (for i)
        (
            vec![LeftPar, Symbol("for"), Symbol("i"), RightPar],
            Error::UnexpectedToken,
        ),
        // (for i from 0)
        (
            vec![
                LeftPar,
                Symbol("for"),
                Symbol("i"),
                Symbol("from"),
                Number("0"),
                RightPar,
            ],
            Error::UnexpectedToken,
        ),
        // (for i from 0 to)
        (
            vec![
                LeftPar,
                Symbol("for"),
                Symbol("i"),
                Symbol("from"),
                Number("0"),
                Symbol("to"),
                RightPar,
            ],
            Error::UnexpectedClosePar,
        ),
        // (for i wrong 0 to 10 body)
        (
            vec![
                LeftPar,
                Symbol("for"),
                Symbol("i"),
                Symbol("wrong"),
                Number("0"),
                Symbol("to"),
                Number("10"),
                Symbol("body"),
                RightPar,
            ],
            Error::UnexpectedToken,
        ),
        // (set x y z)
        (
            vec![
                LeftPar,
                Symbol("set"),
                Symbol("x"),
                Symbol("y"),
                Symbol("z"),
                RightPar,
            ],
            Error::UnexpectedToken,
        ),
        // (const)
        (
            vec![LeftPar, Symbol("const"), RightPar],
            Error::UnexpectedToken,
        ),
        // (const ())
        (
            vec![LeftPar, Symbol("const"), LeftPar, RightPar, RightPar],
            Error::UnexpectedToken,
        ),
        // (if)
        (
            vec![LeftPar, Symbol("if"), RightPar],
            Error::UnexpectedClosePar,
        ),
        // (if true)
        (
            vec![LeftPar, Symbol("if"), Symbol("true"), RightPar],
            Error::UnexpectedClosePar,
        ),
    ];
    for (tokens, expected) in cases {
        assert_eq!(parse_err(tokens.clone()), expected, "input: {tokens:?}");
    }
}

#[test]
fn test_stops_at_first_error() {
    let cases = vec![
        // ) ) )
        (
            vec![RightPar, RightPar, RightPar],
            Error::UnexpectedClosePar,
        ),
        // 1 ) 2
        (
            vec![Number("1"), RightPar, Number("2")],
            Error::UnexpectedClosePar,
        ),
    ];
    for (tokens, expected) in cases {
        assert_eq!(parse_err(tokens.clone()), expected, "input: {tokens:?}");
    }
    // 99999999999999999999 )
    let tokens = vec![Number("99999999999999999999"), RightPar];
    let err = parse_err(tokens.clone());
    assert!(
        matches!(err, Error::InvalidIntegerLiteral(..)),
        "input: {tokens:?}, got: {err:?}",
    );
}

#[test]
fn test_nested_special_forms() {
    let cases = vec![
        // (do (do 1))
        (
            vec![
                LeftPar,
                Symbol("do"),
                LeftPar,
                Symbol("do"),
                Number("1"),
                RightPar,
                RightPar,
            ],
            vec![Do(vec![Do(vec![Int(1)])])],
        ),
        // (fn outer () (fn inner () 1))
        (
            vec![
                LeftPar,
                Symbol("fn"),
                Symbol("outer"),
                LeftPar,
                RightPar,
                LeftPar,
                Symbol("fn"),
                Symbol("inner"),
                LeftPar,
                RightPar,
                Number("1"),
                RightPar,
                RightPar,
            ],
            vec![Fn("outer", vec![], vec![Fn("inner", vec![], vec![Int(1)])])],
        ),
        // (let ((x (let ((y 1)) y))) x)
        (
            vec![
                LeftPar,
                Symbol("let"),
                LeftPar,
                LeftPar,
                Symbol("x"),
                LeftPar,
                Symbol("let"),
                LeftPar,
                LeftPar,
                Symbol("y"),
                Number("1"),
                RightPar,
                RightPar,
                Symbol("y"),
                RightPar,
                RightPar,
                RightPar,
                Symbol("x"),
                RightPar,
            ],
            vec![Let(
                vec![("x", Let(vec![("y", Int(1))], vec![Sym("y")]))],
                vec![Sym("x")],
            )],
        ),
        // (for i from 0 to (+ 1 2) (set sum (+ sum i)))
        (
            vec![
                LeftPar,
                Symbol("for"),
                Symbol("i"),
                Symbol("from"),
                Number("0"),
                Symbol("to"),
                LeftPar,
                Symbol("+"),
                Number("1"),
                Number("2"),
                RightPar,
                LeftPar,
                Symbol("set"),
                Symbol("sum"),
                LeftPar,
                Symbol("+"),
                Symbol("sum"),
                Symbol("i"),
                RightPar,
                RightPar,
                RightPar,
            ],
            vec![For(
                "i",
                Box::new(Int(0)),
                Box::new(Call("+", vec![Int(1), Int(2)])),
                vec![Set("sum", Box::new(Call("+", vec![Sym("sum"), Sym("i")])))],
            )],
        ),
        // (let ((x 1)) x (+ x 1))
        (
            vec![
                LeftPar,
                Symbol("let"),
                LeftPar,
                LeftPar,
                Symbol("x"),
                Number("1"),
                RightPar,
                RightPar,
                Symbol("x"),
                LeftPar,
                Symbol("+"),
                Symbol("x"),
                Number("1"),
                RightPar,
                RightPar,
            ],
            vec![Let(
                vec![("x", Int(1))],
                vec![Sym("x"), Call("+", vec![Sym("x"), Int(1)])],
            )],
        ),
        // (if (if a b c) (if d e) (if f g h))
        (
            vec![
                LeftPar,
                Symbol("if"),
                LeftPar,
                Symbol("if"),
                Symbol("a"),
                Symbol("b"),
                Symbol("c"),
                RightPar,
                LeftPar,
                Symbol("if"),
                Symbol("d"),
                Symbol("e"),
                RightPar,
                LeftPar,
                Symbol("if"),
                Symbol("f"),
                Symbol("g"),
                Symbol("h"),
                RightPar,
                RightPar,
            ],
            vec![If(
                Box::new(If(
                    Box::new(Sym("a")),
                    Box::new(Sym("b")),
                    Some(Box::new(Sym("c"))),
                )),
                Box::new(If(Box::new(Sym("d")), Box::new(Sym("e")), None)),
                Some(Box::new(If(
                    Box::new(Sym("f")),
                    Box::new(Sym("g")),
                    Some(Box::new(Sym("h"))),
                ))),
            )],
        ),
        // (fn abs (x) (if (< x 0) (- 0 x) x))
        (
            vec![
                LeftPar,
                Symbol("fn"),
                Symbol("abs"),
                LeftPar,
                Symbol("x"),
                RightPar,
                LeftPar,
                Symbol("if"),
                LeftPar,
                Symbol("<"),
                Symbol("x"),
                Number("0"),
                RightPar,
                LeftPar,
                Symbol("-"),
                Number("0"),
                Symbol("x"),
                RightPar,
                Symbol("x"),
                RightPar,
                RightPar,
            ],
            vec![Fn(
                "abs",
                vec!["x"],
                vec![If(
                    Box::new(Call("<", vec![Sym("x"), Int(0)])),
                    Box::new(Call("-", vec![Int(0), Sym("x")])),
                    Some(Box::new(Sym("x"))),
                )],
            )],
        ),
    ];
    for (tokens, ast) in cases {
        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
    }
}

#[test]
fn test_smoke_program() {
    // (const (x 1))
    // (fn add (a b) (+ a b))
    // (let ((y 2)) (add x y))
    let tokens = vec![
        LeftPar,
        Symbol("const"),
        LeftPar,
        Symbol("x"),
        Number("1"),
        RightPar,
        RightPar,
        LeftPar,
        Symbol("fn"),
        Symbol("add"),
        LeftPar,
        Symbol("a"),
        Symbol("b"),
        RightPar,
        LeftPar,
        Symbol("+"),
        Symbol("a"),
        Symbol("b"),
        RightPar,
        RightPar,
        LeftPar,
        Symbol("let"),
        LeftPar,
        LeftPar,
        Symbol("y"),
        Number("2"),
        RightPar,
        RightPar,
        LeftPar,
        Symbol("add"),
        Symbol("x"),
        Symbol("y"),
        RightPar,
        RightPar,
    ];
    let expected = vec![
        Const(vec![("x", Int(1))]),
        Fn(
            "add",
            vec!["a", "b"],
            vec![Call("+", vec![Sym("a"), Sym("b")])],
        ),
        Let(
            vec![("y", Int(2))],
            vec![Call("add", vec![Sym("x"), Sym("y")])],
        ),
    ];
    assert_eq!(parse(tokens), expected);
}

#[test]
fn test_recursion_limit_via_do() {
    run_with_large_stack(|| {
        let n = MAX_DEPTH + 1;
        let mut tokens = Vec::with_capacity(n * 2 + 1 + n);
        for _ in 0..n {
            tokens.push(LeftPar);
            tokens.push(Symbol("do"));
        }
        tokens.push(Number("1"));
        for _ in 0..n {
            tokens.push(RightPar);
        }
        assert_eq!(parse_err(tokens), Error::RecursionLimit);
    });
}

#[test]
fn test_span_fn() {
    // (fn id (x) x)
    let lp = sp((1, 0, 0), (1, 1, 1));
    let kw = sp((1, 1, 1), (1, 3, 3));
    let name = sp((1, 4, 4), (1, 6, 6));
    let lp_args = sp((1, 7, 7), (1, 8, 8));
    let arg = sp((1, 8, 8), (1, 9, 9));
    let rp_args = sp((1, 9, 9), (1, 10, 10));
    let body_x = sp((1, 11, 11), (1, 12, 12));
    let rp = sp((1, 12, 12), (1, 13, 13));

    let tokens = vec![
        tsp(LeftPar, lp),
        tsp(Symbol("fn"), kw),
        tsp(Symbol("id"), name),
        tsp(LeftPar, lp_args),
        tsp(Symbol("x"), arg),
        tsp(RightPar, rp_args),
        tsp(Symbol("x"), body_x),
        tsp(RightPar, rp),
    ];
    let prog = parse_sp(tokens.clone());

    assert_eq!(
        prog[0].span,
        sp((1, 0, 0), (1, 13, 13)),
        "input: {tokens:?}"
    );
    if let Expr::Fn {
        name: n,
        args,
        body,
    } = &prog[0].inner
    {
        assert_eq!(n.span, name, "input: {tokens:?}");
        assert_eq!(args[0].span, arg, "input: {tokens:?}");
        assert_eq!(body[0].span, body_x, "input: {tokens:?}");
    } else {
        panic!("expected Fn, input: {tokens:?}");
    }
}

#[test]
fn test_span_let() {
    // (let ((x 1)) x)
    let lp = sp((1, 0, 0), (1, 1, 1));
    let kw = sp((1, 1, 1), (1, 4, 4));
    let lp_vars = sp((1, 5, 5), (1, 6, 6));
    let lp_var = sp((1, 6, 6), (1, 7, 7));
    let x_name = sp((1, 7, 7), (1, 8, 8));
    let one = sp((1, 9, 9), (1, 10, 10));
    let rp_var = sp((1, 10, 10), (1, 11, 11));
    let rp_vars = sp((1, 11, 11), (1, 12, 12));
    let body_x = sp((1, 13, 13), (1, 14, 14));
    let rp = sp((1, 14, 14), (1, 15, 15));

    let tokens = vec![
        tsp(LeftPar, lp),
        tsp(Symbol("let"), kw),
        tsp(LeftPar, lp_vars),
        tsp(LeftPar, lp_var),
        tsp(Symbol("x"), x_name),
        tsp(Number("1"), one),
        tsp(RightPar, rp_var),
        tsp(RightPar, rp_vars),
        tsp(Symbol("x"), body_x),
        tsp(RightPar, rp),
    ];
    let prog = parse_sp(tokens.clone());

    assert_eq!(
        prog[0].span,
        sp((1, 0, 0), (1, 15, 15)),
        "input: {tokens:?}"
    );
    if let Expr::Let { vars, body } = &prog[0].inner {
        assert_eq!(
            vars[0].span,
            sp((1, 6, 6), (1, 11, 11)),
            "input: {tokens:?}"
        );
        assert_eq!(vars[0].inner.name.span, x_name, "input: {tokens:?}");
        assert_eq!(vars[0].inner.expr.span, one, "input: {tokens:?}");
        assert_eq!(body[0].span, body_x, "input: {tokens:?}");
    } else {
        panic!("expected Let, input: {tokens:?}");
    }
}

#[test]
fn test_span_if() {
    // (if true 1 2)
    let lp = sp((1, 0, 0), (1, 1, 1));
    let kw = sp((1, 1, 1), (1, 3, 3));
    let cond = sp((1, 4, 4), (1, 8, 8));
    let then_t = sp((1, 9, 9), (1, 10, 10));
    let else_t = sp((1, 11, 11), (1, 12, 12));
    let rp = sp((1, 12, 12), (1, 13, 13));

    let tokens = vec![
        tsp(LeftPar, lp),
        tsp(Symbol("if"), kw),
        tsp(Symbol("true"), cond),
        tsp(Number("1"), then_t),
        tsp(Number("2"), else_t),
        tsp(RightPar, rp),
    ];
    let prog = parse_sp(tokens.clone());

    assert_eq!(
        prog[0].span,
        sp((1, 0, 0), (1, 13, 13)),
        "input: {tokens:?}"
    );
    if let Expr::If {
        condition,
        then_expr,
        else_expr,
    } = &prog[0].inner
    {
        assert_eq!(condition.span, cond, "input: {tokens:?}");
        assert_eq!(then_expr.span, then_t, "input: {tokens:?}");
        assert_eq!(
            else_expr.as_ref().unwrap().span,
            else_t,
            "input: {tokens:?}"
        );
    } else {
        panic!("expected If, input: {tokens:?}");
    }
}

#[test]
fn test_span_if_no_else() {
    // (if true 1)
    let lp = sp((1, 0, 0), (1, 1, 1));
    let kw = sp((1, 1, 1), (1, 3, 3));
    let cond = sp((1, 4, 4), (1, 8, 8));
    let then_t = sp((1, 9, 9), (1, 10, 10));
    let rp = sp((1, 10, 10), (1, 11, 11));

    let tokens = vec![
        tsp(LeftPar, lp),
        tsp(Symbol("if"), kw),
        tsp(Symbol("true"), cond),
        tsp(Number("1"), then_t),
        tsp(RightPar, rp),
    ];
    let prog = parse_sp(tokens.clone());

    assert_eq!(
        prog[0].span,
        sp((1, 0, 0), (1, 11, 11)),
        "input: {tokens:?}"
    );
    if let Expr::If {
        condition,
        then_expr,
        else_expr,
    } = &prog[0].inner
    {
        assert_eq!(condition.span, cond, "input: {tokens:?}");
        assert_eq!(then_expr.span, then_t, "input: {tokens:?}");
        assert!(else_expr.is_none(), "input: {tokens:?}");
    } else {
        panic!("expected If, input: {tokens:?}");
    }
}

#[test]
fn test_span_for() {
    // (for i from 0 to 10 i)
    let lp = sp((1, 0, 0), (1, 1, 1));
    let kw = sp((1, 1, 1), (1, 4, 4));
    let i = sp((1, 5, 5), (1, 6, 6));
    let from = sp((1, 7, 7), (1, 11, 11));
    let zero = sp((1, 12, 12), (1, 13, 13));
    let to = sp((1, 14, 14), (1, 16, 16));
    let ten = sp((1, 17, 17), (1, 19, 19));
    let body_i = sp((1, 20, 20), (1, 21, 21));
    let rp = sp((1, 21, 21), (1, 22, 22));

    let tokens = vec![
        tsp(LeftPar, lp),
        tsp(Symbol("for"), kw),
        tsp(Symbol("i"), i),
        tsp(Symbol("from"), from),
        tsp(Number("0"), zero),
        tsp(Symbol("to"), to),
        tsp(Number("10"), ten),
        tsp(Symbol("i"), body_i),
        tsp(RightPar, rp),
    ];
    let prog = parse_sp(tokens.clone());

    assert_eq!(
        prog[0].span,
        sp((1, 0, 0), (1, 22, 22)),
        "input: {tokens:?}"
    );
    if let Expr::For {
        loop_var,
        from: f,
        to: t,
        body,
    } = &prog[0].inner
    {
        assert_eq!(loop_var.span, i, "input: {tokens:?}");
        assert_eq!(f.span, zero, "input: {tokens:?}");
        assert_eq!(t.span, ten, "input: {tokens:?}");
        assert_eq!(body[0].span, body_i, "input: {tokens:?}");
    } else {
        panic!("expected For, input: {tokens:?}");
    }
}

#[test]
fn test_span_set() {
    // (set x 5)
    let lp = sp((1, 0, 0), (1, 1, 1));
    let kw = sp((1, 1, 1), (1, 4, 4));
    let x = sp((1, 5, 5), (1, 6, 6));
    let five = sp((1, 7, 7), (1, 8, 8));
    let rp = sp((1, 8, 8), (1, 9, 9));

    let tokens = vec![
        tsp(LeftPar, lp),
        tsp(Symbol("set"), kw),
        tsp(Symbol("x"), x),
        tsp(Number("5"), five),
        tsp(RightPar, rp),
    ];
    let prog = parse_sp(tokens.clone());

    assert_eq!(prog[0].span, sp((1, 0, 0), (1, 9, 9)), "input: {tokens:?}");
    if let Expr::Set { target_var, expr } = &prog[0].inner {
        assert_eq!(target_var.span, x, "input: {tokens:?}");
        assert_eq!(expr.span, five, "input: {tokens:?}");
    } else {
        panic!("expected Set, input: {tokens:?}");
    }
}

#[test]
fn test_span_do() {
    // (do 1 2)
    let lp = sp((1, 0, 0), (1, 1, 1));
    let kw = sp((1, 1, 1), (1, 3, 3));
    let one = sp((1, 4, 4), (1, 5, 5));
    let two = sp((1, 6, 6), (1, 7, 7));
    let rp = sp((1, 7, 7), (1, 8, 8));

    let tokens = vec![
        tsp(LeftPar, lp),
        tsp(Symbol("do"), kw),
        tsp(Number("1"), one),
        tsp(Number("2"), two),
        tsp(RightPar, rp),
    ];
    let prog = parse_sp(tokens.clone());

    assert_eq!(prog[0].span, sp((1, 0, 0), (1, 8, 8)), "input: {tokens:?}");
    if let Expr::Do { body } = &prog[0].inner {
        assert_eq!(body[0].span, one, "input: {tokens:?}");
        assert_eq!(body[1].span, two, "input: {tokens:?}");
    } else {
        panic!("expected Do, input: {tokens:?}");
    }
}

#[test]
fn test_span_const() {
    // (const (x 1) (y 2))
    let lp = sp((1, 0, 0), (1, 1, 1));
    let kw = sp((1, 1, 1), (1, 6, 6));
    let lp_x = sp((1, 7, 7), (1, 8, 8));
    let x_name = sp((1, 8, 8), (1, 9, 9));
    let one = sp((1, 10, 10), (1, 11, 11));
    let rp_x = sp((1, 11, 11), (1, 12, 12));
    let lp_y = sp((1, 13, 13), (1, 14, 14));
    let y_name = sp((1, 14, 14), (1, 15, 15));
    let two = sp((1, 16, 16), (1, 17, 17));
    let rp_y = sp((1, 17, 17), (1, 18, 18));
    let rp = sp((1, 18, 18), (1, 19, 19));

    let tokens = vec![
        tsp(LeftPar, lp),
        tsp(Symbol("const"), kw),
        tsp(LeftPar, lp_x),
        tsp(Symbol("x"), x_name),
        tsp(Number("1"), one),
        tsp(RightPar, rp_x),
        tsp(LeftPar, lp_y),
        tsp(Symbol("y"), y_name),
        tsp(Number("2"), two),
        tsp(RightPar, rp_y),
        tsp(RightPar, rp),
    ];
    let prog = parse_sp(tokens.clone());

    assert_eq!(
        prog[0].span,
        sp((1, 0, 0), (1, 19, 19)),
        "input: {tokens:?}"
    );
    if let Expr::Const { vars } = &prog[0].inner {
        assert_eq!(
            vars[0].span,
            sp((1, 7, 7), (1, 12, 12)),
            "input: {tokens:?}"
        );
        assert_eq!(vars[0].inner.name.span, x_name, "input: {tokens:?}");
        assert_eq!(vars[0].inner.expr.span, one, "input: {tokens:?}");
        assert_eq!(
            vars[1].span,
            sp((1, 13, 13), (1, 18, 18)),
            "input: {tokens:?}"
        );
        assert_eq!(vars[1].inner.name.span, y_name, "input: {tokens:?}");
        assert_eq!(vars[1].inner.expr.span, two, "input: {tokens:?}");
    } else {
        panic!("expected Const, input: {tokens:?}");
    }
}