From abda8d00117072f7c03f57eaeca9cf44427078dc Mon Sep 17 00:00:00 2001 From: Tolmachev Igor Date: Mon, 11 May 2026 08:34:22 +0300 Subject: Replace generic list AST with typed expression tree Each form (fn, let, for, set, do, call) now has its own variant with named fields instead of being a plain list. --- compiler/src/ast/tests.rs | 1298 +++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 1204 insertions(+), 94 deletions(-) (limited to 'compiler/src/ast/tests.rs') diff --git a/compiler/src/ast/tests.rs b/compiler/src/ast/tests.rs index 44789cb..5b2399f 100644 --- a/compiler/src/ast/tests.rs +++ b/compiler/src/ast/tests.rs @@ -1,7 +1,7 @@ -use std::{fmt::Debug, iter::repeat_n}; +use std::fmt::Debug; use crate::{ - ast::{Atom, Error, Expr, Parser, parser::MAX_DEPTH, tests::E::*}, + ast::{Atom, Error, Expr, LetVar, Parser, parser::MAX_DEPTH, tests::E::*}, lex::Token::{self, *}, span::{Pos, Span, Spanned}, }; @@ -13,20 +13,62 @@ enum E { Sym(&'static str), Bool(bool), Nil, - List(Vec), + Fn(&'static str, Vec<&'static str>, Vec), + Const(Vec<(&'static str, E)>), + Let(Vec<(&'static str, E)>, Vec), + For(&'static str, Box, Box, Vec), + Set(&'static str, Box), + Do(Vec), + Call(&'static str, Vec), +} + +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 for E { fn from(expr: Expr) -> Self { match expr { Expr::Atom(atom) => match atom { - Atom::Integer(i) => Int(i), - Atom::String(s) => Str(Box::leak(s.into())), - Atom::Symbol(s) => Sym(Box::leak(s.into())), + 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::List(l) => List(l.into_iter().map(|e| e.inner.into()).collect()), + 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::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(), + ), } } } @@ -142,72 +184,311 @@ fn test_string_escapes() { } #[test] -fn test_lists() { +fn test_call() { let cases = vec![ - // (1) + // (foo 1) ( - vec![LeftPar, Number("1"), RightPar], - vec![List(vec![Int(1)])], + vec![LeftPar, Symbol("foo"), Number("1"), RightPar], + vec![Call("foo", vec![Int(1)])], ), - // (1 2 3) + // (+ 1 2 3) ( - vec![LeftPar, Number("1"), Number("2"), Number("3"), RightPar], - vec![List(vec![Int(1), Int(2), Int(3)])], + vec![ + LeftPar, + Symbol("+"), + Number("1"), + Number("2"), + Number("3"), + RightPar, + ], + vec![Call("+", vec![Int(1), Int(2), Int(3)])], ), - // (()) -> (nil) + // (foo (bar 1) baz) ( - vec![LeftPar, LeftPar, RightPar, RightPar], - vec![List(vec![Nil])], + vec![ + LeftPar, + Symbol("foo"), + LeftPar, + Symbol("bar"), + Number("1"), + RightPar, + Symbol("baz"), + RightPar, + ], + vec![Call("foo", vec![Call("bar", vec![Int(1)]), Sym("baz")])], ), - // (a (b c) d) + // (f "s" foo true nil) ( vec![ LeftPar, - Symbol("a"), + 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("b"), - Symbol("c"), + 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, - Symbol("d"), RightPar, ], - vec![List(vec![ - Sym("a"), - List(vec![Sym("b"), Sym("c")]), - Sym("d"), - ])], + vec![Const(vec![("x", Int(1)), ("y", Int(2))])], ), - // (define x 42) + ]; + 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("define"), + Symbol("let"), + LeftPar, + LeftPar, + Symbol("x"), + Number("1"), + RightPar, + RightPar, Symbol("x"), - Number("42"), RightPar, ], - vec![List(vec![Sym("define"), Sym("x"), Int(42)])], + vec![Let(vec![("x", Int(1))], vec![Sym("x")])], ), - // (1 2.5 "s" foo true nil) + // (let ((x 1) (y 2)) (+ x y)) ( vec![ LeftPar, + Symbol("let"), + LeftPar, + LeftPar, + Symbol("x"), Number("1"), - Number("-1"), - String("s"), - Symbol("foo"), - Symbol("true"), - Symbol("nil"), + 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_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![List(vec![ - Int(1), - Int(-1), - Str("s"), - Sym("foo"), - Bool(true), - Nil, - ])], + vec![Do(vec![Int(1), Int(2), Int(3)])], ), ]; for (tokens, ast) in cases { @@ -226,12 +507,14 @@ fn test_top_level() { vec![ LeftPar, Symbol("a"), + Number("1"), RightPar, LeftPar, Symbol("b"), + Number("2"), RightPar, ], - vec![List(vec![Sym("a")]), List(vec![Sym("b")])], + vec![Call("a", vec![Int(1)]), Call("b", vec![Int(2)])], ), ]; for (tokens, expected) in cases { @@ -244,32 +527,103 @@ fn parse_err(tokens: Vec>) -> Error { } #[test] -fn test_unexpected_right_par() { +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::UnexpectedRightPar, + Error::UnclosedPar, "input: {tokens:?}" ); } } #[test] -fn test_unclosed_left_par() { +fn test_unexpected_eof() { let cases = vec![ + // ( vec![LeftPar], - vec![LeftPar, Number("1")], - vec![LeftPar, LeftPar, Symbol("a"), RightPar], + // (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::UnclosedLeftPar, + Error::UnexpectedToken, "input: {tokens:?}" ); } @@ -329,18 +683,34 @@ fn test_unexpected_escape_char_propagates() { ); } +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() { - let mut tokens = Vec::with_capacity(MAX_DEPTH * 2); - tokens.extend(repeat_n(LeftPar, MAX_DEPTH)); - tokens.extend(repeat_n(RightPar, MAX_DEPTH)); - assert_eq!( - parse_err(tokens), - Error::RecursionLimit, - "input: {} LeftPar then {} RightPar", - MAX_DEPTH, - MAX_DEPTH, - ); + 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 { @@ -360,8 +730,6 @@ fn parse_sp(tokens: Vec>>) -> Vec> { .parse() .unwrap() .into_inner() - .into_iter() - .collect() } fn parse_sp_err(tokens: Vec>>) -> Spanned { @@ -378,26 +746,33 @@ fn test_span_atom() { } #[test] -fn test_span_list_covers_parens() { - // (foo) +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 rp = sp((1, 4, 4), (1, 5, 5)); - let tokens = vec![tsp(LeftPar, lp), tsp(Symbol("foo"), foo), tsp(RightPar, rp)]; + 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, 5, 5)), "input: {tokens:?}"); + assert_eq!(prog[0].span, sp((1, 0, 0), (1, 7, 7)), "input: {tokens:?}"); - if let Expr::List(items) = &prog[0].inner { - assert_eq!(items[0].span, foo, "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 list, input: {tokens:?}"); + panic!("expected call, input: {tokens:?}"); } } #[test] fn test_span_empty_list_covers_parens() { - // () -> Atom::Nil, span [0..2] + // () 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)]; @@ -408,12 +783,13 @@ fn test_span_empty_list_covers_parens() { } #[test] -fn test_error_span_unexpected_right_par() { +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::UnexpectedRightPar, "input: {tokens:?}"); + assert_eq!(err.inner, Error::UnexpectedClosePar, "input: {tokens:?}"); assert_eq!(err.span, s, "input: {tokens:?}"); } @@ -427,26 +803,67 @@ fn test_error_span_invalid_integer() { } #[test] -fn test_error_span_unclosed_left_par() { +fn test_error_span_unclosed_par() { + // (foo 1 let lp = sp((1, 0, 0), (1, 1, 1)); - let tokens = vec![tsp(LeftPar, lp)]; + 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::UnclosedLeftPar, "input: {tokens:?}"); + assert_eq!(err.inner, Error::UnclosedPar, "input: {tokens:?}"); assert_eq!(err.span, lp, "input: {tokens:?}"); } #[test] -fn test_error_span_unclosed_left_par_nested() { +fn test_error_span_unclosed_par_nested() { + // (foo (bar 1 let outer = sp((1, 0, 0), (1, 1, 1)); - let inner = sp((1, 2, 2), (1, 3, 3)); - let tokens = vec![tsp(LeftPar, outer), tsp(LeftPar, inner)]; + 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::UnclosedLeftPar, "input: {tokens:?}"); + 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)); @@ -477,16 +894,16 @@ fn test_error_span_unexpected_escape_char() { #[test] fn test_error_span_deep_nested() { - // (a (b (c BAD))) + // (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("a"), any), + tsp(Symbol("foo"), any), tsp(LeftPar, any), - tsp(Symbol("b"), any), + tsp(Symbol("bar"), any), tsp(LeftPar, any), - tsp(Symbol("c"), any), + tsp(Symbol("baz"), any), tsp(Number("99999999999999999999"), bad_span), tsp(RightPar, any), tsp(RightPar, any), @@ -504,14 +921,707 @@ fn test_error_span_deep_nested() { #[test] fn test_error_span_recursion_limit() { - let mut tokens = Vec::with_capacity(MAX_DEPTH); - for i in 0..MAX_DEPTH { - let s = sp((1, i, i), (1, i + 1, i + 1)); - tokens.push(tsp(LeftPar, s)); + 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")]), + // (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:?}"); } - let trigger = sp((1, MAX_DEPTH - 1, MAX_DEPTH - 1), (1, MAX_DEPTH, MAX_DEPTH)); - 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_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, + ), + ]; + 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)])], + )], + ), + ]; + 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_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:?}"); + } } -- cgit v1.3