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/error.rs | 11 +- compiler/src/ast/mod.rs | 2 +- compiler/src/ast/models.rs | 48 +- compiler/src/ast/parser.rs | 303 +++++++++-- compiler/src/ast/tests.rs | 1298 ++++++++++++++++++++++++++++++++++++++++---- compiler/src/span.rs | 4 + 6 files changed, 1510 insertions(+), 156 deletions(-) (limited to 'compiler') diff --git a/compiler/src/ast/error.rs b/compiler/src/ast/error.rs index 38b3916..5598376 100644 --- a/compiler/src/ast/error.rs +++ b/compiler/src/ast/error.rs @@ -10,8 +10,10 @@ pub enum Error { UnexpectedEscapeChar(char), // Par - UnexpectedRightPar, - UnclosedLeftPar, + UnexpectedClosePar, + UnclosedPar, + + UnexpectedToken, UnexpectedEof, @@ -26,8 +28,9 @@ impl fmt::Display for Error { } Error::UnclosedString(string) => write!(f, "unclosed string {string:?}"), Error::UnexpectedEscapeChar(ch) => write!(f, "unexpected escape char {ch:?}"), - Error::UnexpectedRightPar => write!(f, "unexpected right par"), - Error::UnclosedLeftPar => write!(f, "unclosed left par"), + Error::UnexpectedClosePar => write!(f, "unexpected `)`"), + Error::UnclosedPar => write!(f, "unclosed `(`"), + Error::UnexpectedToken => write!(f, "unexpected token"), Error::UnexpectedEof => write!(f, "unexpected eof"), Error::RecursionLimit => write!(f, "recursion limit"), } diff --git a/compiler/src/ast/mod.rs b/compiler/src/ast/mod.rs index 2a0be03..afd459e 100644 --- a/compiler/src/ast/mod.rs +++ b/compiler/src/ast/mod.rs @@ -3,7 +3,7 @@ mod models; mod parser; pub use error::Error; -pub use models::{Ast, Atom, Expr}; +pub use models::{Ast, Atom, Expr, LetVar}; pub use parser::Parser; #[cfg(test)] diff --git a/compiler/src/ast/models.rs b/compiler/src/ast/models.rs index 2a8c5ae..64fec19 100644 --- a/compiler/src/ast/models.rs +++ b/compiler/src/ast/models.rs @@ -2,22 +2,56 @@ use std::rc::Rc; use crate::span::Spanned; -#[derive(Clone, Debug, PartialEq)] +#[derive(Clone, Debug, PartialEq, Eq)] +pub struct LetVar { + pub name: Spanned>, + pub expr: Spanned, +} + +#[derive(Clone, Debug, PartialEq, Eq)] pub enum Atom { - Integer(i64), - String(Rc), - Symbol(Rc), + Int(i64), + Str(Rc), + Sym(Rc), Bool(bool), Nil, } -#[derive(Clone, Debug, PartialEq)] +#[derive(Clone, Debug, PartialEq, Eq)] pub enum Expr { + Fn { + name: Spanned>, + args: Vec>>, + body: Vec>, + }, + Const { + vars: Vec>, + }, + Let { + vars: Vec>, + body: Vec>, + }, + For { + loop_var: Spanned>, + from: Spanned>, + to: Spanned>, + body: Vec>, + }, + Set { + target_var: Spanned>, + expr: Spanned>, + }, + Do { + body: Vec>, + }, + Call { + fn_name: Spanned>, + args: Vec>, + }, Atom(Atom), - List(Vec>), } -#[derive(Clone, Debug, PartialEq)] +#[derive(Clone, Debug, PartialEq, Eq)] pub struct Ast(Vec>); impl Ast { diff --git a/compiler/src/ast/parser.rs b/compiler/src/ast/parser.rs index 4b4f949..12a6f0d 100644 --- a/compiler/src/ast/parser.rs +++ b/compiler/src/ast/parser.rs @@ -1,7 +1,7 @@ -use std::iter::Peekable; +use std::{iter::Peekable, rc::Rc}; use crate::{ - ast::{Ast, Atom, Error, Expr}, + ast::{Ast, Atom, Error, Expr, models::LetVar}, lex::Token, span::{Pos, Span, Spanned}, }; @@ -10,7 +10,7 @@ pub(super) const MAX_DEPTH: usize = 256; // TODO: make it a compile flag fn parse_number(number: &str) -> Result { match number.parse() { - Ok(ok) => Ok(Atom::Integer(ok)), + Ok(ok) => Ok(Atom::Int(ok)), Err(err) => Err(Error::InvalidIntegerLiteral(number.into(), err)), } } @@ -41,7 +41,7 @@ fn parse_string(string: &str) -> Result { return Err(Error::UnclosedString(string.into())); } - Ok(Atom::String(result.into())) + Ok(Atom::Str(result.into())) } fn parse_symbol(symbol: &str) -> Atom { @@ -49,7 +49,7 @@ fn parse_symbol(symbol: &str) -> Atom { "true" => Atom::Bool(true), "false" => Atom::Bool(false), "nil" => Atom::Nil, - _ => Atom::Symbol(symbol.into()), + _ => Atom::Sym(symbol.into()), } } @@ -78,50 +78,275 @@ where self.tokens.peek().copied() } - fn consume(&mut self) -> Option>> { - self.tokens - .next() - .inspect(|s| self.last_token_span = s.span) + fn peek_token(&mut self) -> Result>, Spanned> { + match self.peek() { + Some(token) => Ok(token), + None => Err(Spanned::new(Error::UnexpectedEof, self.last_token_span)), + } } - fn parse_expr(&mut self) -> Result, Spanned> { - let Spanned { inner: token, span } = match self.peek() { - Some(token) => token, - None => return Err(Spanned::new(Error::UnexpectedEof, self.last_token_span)), + fn consume(&mut self) -> Result<(), Spanned> { + match self.tokens.next() { + Some(token) => { + let (token, span) = token.into_parts(); + + if let Token::LeftPar = token { + self.depth = self.depth.saturating_add(1); + if self.depth > MAX_DEPTH { + return Err(Spanned::new(Error::RecursionLimit, span)); + } + } else if let Token::RightPar = token { + self.depth = self.depth.saturating_sub(1); + } + + self.last_token_span = span; + Ok(()) + } + None => panic!("no tokens to consume"), + } + } + + fn require_sym(&mut self, symbol: &str) -> Result> { + let (token, span) = self.peek_token()?.into_parts(); + self.consume()?; + match token { + Token::Symbol(s) if s == symbol => Ok(span), + _ => Err(Spanned::new(Error::UnexpectedToken, span)), + } + } + + fn require_left_par(&mut self) -> Result> { + let (token, span) = self.peek_token()?.into_parts(); + self.consume()?; + match token { + Token::LeftPar => Ok(span), + _ => Err(Spanned::new(Error::UnexpectedToken, span)), + } + } + + fn require_right_par(&mut self) -> Result> { + let (token, span) = self.peek_token()?.into_parts(); + self.consume()?; + match token { + Token::RightPar => Ok(span), + _ => Err(Spanned::new(Error::UnexpectedToken, span)), + } + } + + fn parse_sym(&mut self) -> Result, Spanned> { + let (token, span) = self.peek_token()?.into_parts(); + self.consume()?; + match token { + Token::Symbol(symbol) => Ok(Spanned::new(symbol, span)), + _ => Err(Spanned::new(Error::UnexpectedToken, span)), + } + } + + fn parse_args(&mut self, open_span: Span) -> Result>>, Spanned> { + let mut args = Vec::new(); + while let Some(token) = self.peek() { + let (token, span) = token.into_parts(); + + self.consume()?; + match token { + Token::Symbol(symbol) => args.push(Spanned::new(symbol.into(), span)), + Token::RightPar => return Ok(args), + _ => return Err(Spanned::new(Error::UnexpectedToken, span)), + } + } + + Err(Spanned::new(Error::UnclosedPar, open_span)) + } + + fn parse_body( + &mut self, + open_span: Span, + non_empty: bool, + ) -> Result>, Spanned> { + let mut body = Vec::new(); + if non_empty { + body.push(self.parse_expr()?); + } + while let Some(token) = self.peek() { + match token.inner { + Token::RightPar => { + self.consume()?; + return Ok(body); + } + _ => body.push(self.parse_expr()?), + } + } + + Err(Spanned::new(Error::UnclosedPar, open_span)) + } + + fn parse_var(&mut self) -> Result, Spanned> { + let open_span = self.require_left_par()?; + let name = self.parse_sym()?.map(Into::into); + let expr = self.parse_expr()?; + let close_span = self.require_right_par()?; + + let let_var = LetVar { name, expr }; + let span = Span::new(open_span.start, close_span.end); + Ok(Spanned::new(let_var, span)) + } + + fn parse_vars(&mut self, open_span: Span) -> Result>, Spanned> { + let mut vars = Vec::new(); + vars.push(self.parse_var()?); + + while let Some(token) = self.peek() { + let (token, span) = token.into_parts(); + match token { + Token::LeftPar => vars.push(self.parse_var()?), + Token::RightPar => { + self.consume()?; + return Ok(vars); + } + _ => return Err(Spanned::new(Error::UnexpectedToken, span)), + } + } + + Err(Spanned::new(Error::UnclosedPar, open_span)) + } + + fn parse_fn(&mut self, open_span: Span) -> Result, Spanned> { + self.consume()?; + + let name = self.parse_sym()?.map(Into::into); + let args_open_span = self.require_left_par()?; + let args = self.parse_args(args_open_span)?; + + let body = self.parse_body(open_span, true)?; + let function = Expr::Fn { name, args, body }; + let span = Span::new(open_span.start, self.last_token_span.end); + + Ok(Spanned::new(function, span)) + } + + fn parse_const(&mut self, open_span: Span) -> Result, Spanned> { + self.consume()?; + + let vars = self.parse_vars(open_span)?; + let constant = Expr::Const { vars }; + let span = Span::new(open_span.start, self.last_token_span.end); + Ok(Spanned::new(constant, span)) + } + + fn parse_let(&mut self, open_span: Span) -> Result, Spanned> { + self.consume()?; + + let vars_span = self.require_left_par()?; + let vars = self.parse_vars(vars_span)?; + let body = self.parse_body(open_span, true)?; + let let_vars = Expr::Let { vars, body }; + let span = Span::new(open_span.start, self.last_token_span.end); + Ok(Spanned::new(let_vars, span)) + } + + fn parse_for(&mut self, open_span: Span) -> Result, Spanned> { + self.consume()?; + + let loop_var = self.parse_sym()?.map(Into::into); + self.require_sym("from")?; + let from = self.parse_expr()?.map(Box::new); + self.require_sym("to")?; + let to = self.parse_expr()?.map(Box::new); + let body = self.parse_body(open_span, true)?; + + let for_loop = Expr::For { + loop_var, + from, + to, + body, }; + let span = Span::new(open_span.start, self.last_token_span.end); + Ok(Spanned::new(for_loop, span)) + } + + fn parse_set(&mut self, open_span: Span) -> Result, Spanned> { + self.consume()?; + + let target_var = self.parse_sym()?.map(Into::into); + let expr = self.parse_expr()?.map(Box::new); + self.require_right_par()?; + + let set = Expr::Set { target_var, expr }; + let span = Span::new(open_span.start, self.last_token_span.end); + Ok(Spanned::new(set, span)) + } + + fn parse_do(&mut self, open_span: Span) -> Result, Spanned> { + self.consume()?; + + let body = self.parse_body(open_span, true)?; + + let do_body = Expr::Do { body }; + let span = Span::new(open_span.start, self.last_token_span.end); + Ok(Spanned::new(do_body, span)) + } + + fn parse_call(&mut self, open_span: Span) -> Result, Spanned> { + let fn_name = self.parse_sym()?.map(Into::into); + let args = self.parse_body(open_span, false)?; + + let call = Expr::Call { fn_name, args }; + let span = Span::new(open_span.start, self.last_token_span.end); + Ok(Spanned::new(call, span)) + } + + fn parse_special_form(&mut self, open_span: Span) -> Result, Spanned> { + let (token, span) = self.peek_token()?.into_parts(); + + let symbol = match token { + Token::Symbol(symbol) => symbol, + Token::RightPar => { + self.consume()?; + let span = Span::new(open_span.start, span.end); + return Ok(Spanned::new(Expr::Atom(Atom::Nil), span)); + } + _ => return Err(Spanned::new(Error::UnexpectedToken, span)), + }; + + match symbol { + "fn" => self.parse_fn(open_span), + "const" => self.parse_const(open_span), + "let" => self.parse_let(open_span), + "for" => self.parse_for(open_span), + "set" => self.parse_set(open_span), + "do" => self.parse_do(open_span), + _ => self.parse_call(open_span), + } + } + + fn parse_expr(&mut self) -> Result, Spanned> { + let (token, span) = self.peek_token()?.into_parts(); let expr = match token { Token::LeftPar => { - self.consume(); - let list = self.parse_list(span)?; - let expr = if !list.is_empty() { - Expr::List(list) - } else { - Expr::Atom(Atom::Nil) - }; - - Spanned::new(expr, Span::new(span.start, self.last_token_span.end)) + self.consume()?; + self.parse_special_form(span)? } Token::RightPar => { - self.consume(); - return Err(Spanned::new(Error::UnexpectedRightPar, span)); + self.consume()?; + return Err(Spanned::new(Error::UnexpectedClosePar, span)); } Token::Number(number) => { - self.consume(); + self.consume()?; let atom = parse_number(number).map_err(|e| Spanned::new(e, span))?; Spanned::new(Expr::Atom(atom), span) } Token::String(string) => { - self.consume(); + self.consume()?; let atom = parse_string(string).map_err(|e| Spanned::new(e, span))?; Spanned::new(Expr::Atom(atom), span) } Token::UnclosedString(string) => { - self.consume(); + self.consume()?; return Err(Spanned::new(Error::UnclosedString(string.into()), span)); } Token::Symbol(symbol) => { - self.consume(); + self.consume()?; let atom = parse_symbol(symbol); Spanned::new(Expr::Atom(atom), span) } @@ -130,28 +355,6 @@ where Ok(expr) } - fn parse_list(&mut self, left_par_span: Span) -> Result>, Spanned> { - let mut list = Vec::new(); - - self.depth += 1; - if self.depth >= MAX_DEPTH { - return Err(Spanned::new(Error::RecursionLimit, self.last_token_span)); - } - - while let Some(Spanned { inner: token, .. }) = self.peek() { - match token { - Token::RightPar => { - self.consume(); - return Ok(list); - } - _ => list.push(self.parse_expr()?), - } - } - self.depth -= 1; - - Err(Spanned::new(Error::UnclosedLeftPar, left_par_span)) - } - pub fn parse(mut self) -> Result> { let mut ast = Vec::new(); 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:?}"); + } } diff --git a/compiler/src/span.rs b/compiler/src/span.rs index 8686f4f..8b46b31 100644 --- a/compiler/src/span.rs +++ b/compiler/src/span.rs @@ -38,6 +38,10 @@ impl Spanned { Self { inner, span } } + pub fn into_parts(self) -> (T, Span) { + (self.inner, self.span) + } + pub fn map(self, f: impl FnOnce(T) -> U) -> Spanned { let Self { inner, span } = self; Spanned { -- cgit v1.3