Add RecursionLimit parser error

Returns error after 256 levels of nesting to avoid stack overflow. The limit is hardcoded now, but
will become a compiler flag later.

2 files changed, 12 insertions, 0 deletions

diff --git a/compiler/src/ast/error.rs b/compiler/src/ast/error.rs
index ced2231..21102ea 100644
--- a/compiler/src/ast/error.rs
+++ b/compiler/src/ast/error.rs
@@ -19,6 +19,8 @@ pub enum Error {
     UnclosedLeftPar,
 
     UnexpectedEof,
+
+    RecursionLimit,
 }
 
 impl From<ParseFloatError> for Error {
diff --git a/compiler/src/ast/parser.rs b/compiler/src/ast/parser.rs
index 6b11cc6..8e476ad 100644
--- a/compiler/src/ast/parser.rs
+++ b/compiler/src/ast/parser.rs
@@ -6,6 +6,8 @@ use crate::{
     span::{Pos, Span, Spanned},
 };
 
+const MAX_DEPTH: usize = 256; // TODO: make it a compile flag
+
 fn parse_number(number: &str) -> Result<Atom, Error> {
     let is_float = number.bytes().any(|b| matches!(b, b'.' | b'e' | b'E'))
         || matches!(number, "inf" | "+inf" | "-inf" | "nan");
@@ -66,6 +68,7 @@ where
 {
     tokens: Peekable<I>,
     last_token_span: Span,
+    depth: usize,
 }
 
 impl<'a, I> Parser<'a, I>
@@ -76,6 +79,7 @@ where
         Self {
             tokens: tokens.peekable(),
             last_token_span: Span::new(Pos::new(1, 0, 0), Pos::new(1, 0, 0)),
+            depth: 0,
         }
     }
 
@@ -147,6 +151,11 @@ where
     fn parse_list(&mut self, left_par_span: Span) -> Result<Vec<Spanned<Expr>>, Spanned<Error>> {
         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 => {
@@ -156,6 +165,7 @@ where
                 _ => list.push(self.parse_expr()?),
             }
         }
+        self.depth -= 1;
 
         Err(Spanned::new(Error::UnclosedLeftPar, left_par_span))
     }