Merge pull request #46 from typst/parser-ng

Next Generation Parser

1 files changed, 436 insertions, 527 deletions

diff --git a/src/parse/mod.rs b/src/parse/mod.rs
index 30787423..f9c0049f 100644
--- a/src/parse/mod.rs
+++ b/src/parse/mod.rs
@@ -12,216 +12,162 @@ pub use tokens::*;
 
 use std::rc::Rc;
 
-use crate::diag::TypResult;
-use crate::source::SourceFile;
-use crate::syntax::*;
-use crate::util::EcoString;
+use crate::syntax::ast::{Associativity, BinOp, UnOp};
+use crate::syntax::{ErrorPos, Green, GreenNode, NodeKind};
 
 /// Parse a source file.
-pub fn parse(source: &SourceFile) -> TypResult<Markup> {
-    let mut p = Parser::new(source);
-    let markup = markup(&mut p);
-    let errors = p.finish();
-    if errors.is_empty() {
-        Ok(markup)
-    } else {
-        Err(Box::new(errors))
+pub fn parse(src: &str) -> Rc<GreenNode> {
+    let mut p = Parser::new(src);
+    markup(&mut p);
+    match p.finish().into_iter().next() {
+        Some(Green::Node(node)) => node,
+        _ => unreachable!(),
     }
 }
 
 /// Parse markup.
-fn markup(p: &mut Parser) -> Markup {
+fn markup(p: &mut Parser) {
     markup_while(p, true, &mut |_| true)
 }
 
-/// Parse markup that stays equal or right of the given column.
-fn markup_indented(p: &mut Parser, column: usize) -> Markup {
+/// Parse markup that stays right of the given column.
+fn markup_indented(p: &mut Parser, column: usize) {
     p.eat_while(|t| match t {
-        Token::Space(n) => n == 0,
-        Token::LineComment(_) | Token::BlockComment(_) => true,
+        NodeKind::Space(n) => *n == 0,
+        NodeKind::LineComment | NodeKind::BlockComment => true,
         _ => false,
     });
 
     markup_while(p, false, &mut |p| match p.peek() {
-        Some(Token::Space(n)) if n >= 1 => p.column(p.next_end()) >= column,
+        Some(NodeKind::Space(n)) if *n >= 1 => p.column(p.current_end()) >= column,
         _ => true,
     })
 }
 
-/// Parse a syntax tree while the peeked token satisifies a condition.
+/// Parse a syntax tree while the peeked NodeKind satisifies a condition.
 ///
 /// If `at_start` is true, things like headings that may only appear at the
 /// beginning of a line or template are allowed.
-fn markup_while<F>(p: &mut Parser, mut at_start: bool, f: &mut F) -> Markup
+fn markup_while<F>(p: &mut Parser, mut at_start: bool, f: &mut F)
 where
     F: FnMut(&mut Parser) -> bool,
 {
-    let mut tree = vec![];
-    while !p.eof() && f(p) {
-        if let Some(node) = markup_node(p, &mut at_start) {
-            at_start &= matches!(node, MarkupNode::Space | MarkupNode::Parbreak(_));
-            tree.push(node);
+    p.perform(NodeKind::Markup, |p| {
+        while !p.eof() && f(p) {
+            markup_node(p, &mut at_start);
         }
-    }
-
-    tree
+    });
 }
 
 /// Parse a markup node.
-fn markup_node(p: &mut Parser, at_start: &mut bool) -> Option<MarkupNode> {
-    let token = p.peek()?;
-    let span = p.peek_span();
-    let node = match token {
+fn markup_node(p: &mut Parser, at_start: &mut bool) {
+    let token = match p.peek() {
+        Some(t) => t,
+        None => return,
+    };
+
+    match token {
         // Whitespace.
-        Token::Space(newlines) => {
-            *at_start |= newlines > 0;
-            if newlines < 2 {
-                MarkupNode::Space
+        NodeKind::Space(newlines) => {
+            *at_start |= *newlines > 0;
+            if *newlines < 2 {
+                p.eat();
             } else {
-                MarkupNode::Parbreak(span)
+                p.convert(NodeKind::Parbreak);
             }
+            return;
         }
 
-        // Text.
-        Token::Text(text) => MarkupNode::Text(text.into()),
-        Token::Tilde => MarkupNode::Text("\u{00A0}".into()),
-        Token::HyphHyph => MarkupNode::Text("\u{2013}".into()),
-        Token::HyphHyphHyph => MarkupNode::Text("\u{2014}".into()),
-        Token::UnicodeEscape(t) => MarkupNode::Text(unicode_escape(p, t)),
+        // Comments.
+        NodeKind::LineComment | NodeKind::BlockComment => {
+            p.eat();
+            return;
+        }
+
+        // Text and markup.
+        NodeKind::Text(_)
+        | NodeKind::EnDash
+        | NodeKind::EmDash
+        | NodeKind::NonBreakingSpace
+        | NodeKind::Emph
+        | NodeKind::Strong
+        | NodeKind::Linebreak
+        | NodeKind::Raw(_)
+        | NodeKind::Math(_)
+        | NodeKind::UnicodeEscape(_) => {
+            p.eat();
+        }
 
-        // Markup.
-        Token::Backslash => MarkupNode::Linebreak(span),
-        Token::Star => MarkupNode::Strong(span),
-        Token::Underscore => MarkupNode::Emph(span),
-        Token::Raw(t) => raw(p, t),
-        Token::Eq if *at_start => return Some(heading(p)),
-        Token::Hyph if *at_start => return Some(list_node(p)),
-        Token::Numbering(number) if *at_start => return Some(enum_node(p, number)),
+        NodeKind::Eq if *at_start => heading(p),
+        NodeKind::Minus if *at_start => list_node(p),
+        NodeKind::EnumNumbering(_) if *at_start => enum_node(p),
 
         // Line-based markup that is not currently at the start of the line.
-        Token::Eq | Token::Hyph | Token::Numbering(_) => {
-            MarkupNode::Text(p.peek_src().into())
+        NodeKind::Eq | NodeKind::Minus | NodeKind::EnumNumbering(_) => {
+            p.convert(NodeKind::Text(p.peek_src().into()));
         }
 
         // Hashtag + keyword / identifier.
-        Token::Ident(_)
-        | Token::Let
-        | Token::If
-        | Token::While
-        | Token::For
-        | Token::Import
-        | Token::Include => {
-            let stmt = matches!(token, Token::Let | Token::Import);
+        NodeKind::Ident(_)
+        | NodeKind::Let
+        | NodeKind::If
+        | NodeKind::While
+        | NodeKind::For
+        | NodeKind::Import
+        | NodeKind::Include => {
+            let stmt = matches!(token, NodeKind::Let | NodeKind::Import);
             let group = if stmt { Group::Stmt } else { Group::Expr };
 
-            p.start_group(group, TokenMode::Code);
-            let expr = expr_with(p, true, 0);
-            if stmt && expr.is_some() && !p.eof() {
-                p.expected_at(p.prev_end(), "semicolon or line break");
+            p.start_group(group);
+            let res = expr_prec(p, true, 0);
+            if stmt && res.is_ok() && !p.eof() {
+                p.expected_at("semicolon or line break");
             }
             p.end_group();
-
-            return expr.map(MarkupNode::Expr);
         }
 
         // Block and template.
-        Token::LeftBrace => return Some(MarkupNode::Expr(block(p))),
-        Token::LeftBracket => return Some(MarkupNode::Expr(template(p))),
-
-        // Comments.
-        Token::LineComment(_) | Token::BlockComment(_) => {
-            p.eat();
-            return None;
-        }
+        NodeKind::LeftBrace => block(p),
+        NodeKind::LeftBracket => template(p),
 
-        _ => {
-            *at_start = false;
-            p.unexpected();
-            return None;
-        }
+        NodeKind::Error(_, _) => p.eat(),
+        _ => p.unexpected(),
     };
-    p.eat();
-    Some(node)
-}
 
-/// Handle a unicode escape sequence.
-fn unicode_escape(p: &mut Parser, token: UnicodeEscapeToken) -> EcoString {
-    let span = p.peek_span();
-    let text = if let Some(c) = resolve::resolve_hex(token.sequence) {
-        c.into()
-    } else {
-        // Print out the escape sequence verbatim if it is invalid.
-        p.error(span, "invalid unicode escape sequence");
-        p.peek_src().into()
-    };
-
-    if !token.terminated {
-        p.error(span.end, "expected closing brace");
-    }
-
-    text
-}
-
-/// Handle a raw block.
-fn raw(p: &mut Parser, token: RawToken) -> MarkupNode {
-    let column = p.column(p.next_start());
-    let span = p.peek_span();
-    let raw = resolve::resolve_raw(span, column, token.backticks, token.text);
-    if !token.terminated {
-        p.error(span.end, "expected backtick(s)");
-    }
-    MarkupNode::Raw(Box::new(raw))
+    *at_start = false;
 }
 
 /// Parse a heading.
-fn heading(p: &mut Parser) -> MarkupNode {
-    let start = p.next_start();
-    p.eat_assert(Token::Eq);
-
-    // Count depth.
-    let mut level: usize = 1;
-    while p.eat_if(Token::Eq) {
-        level += 1;
-    }
-
-    if level > 6 {
-        return MarkupNode::Text(p.get(start .. p.prev_end()).into());
-    }
-
-    let column = p.column(p.prev_end());
-    let body = markup_indented(p, column);
-    MarkupNode::Heading(Box::new(HeadingNode {
-        span: p.span_from(start),
-        level,
-        body,
-    }))
+fn heading(p: &mut Parser) {
+    p.perform(NodeKind::Heading, |p| {
+        p.eat_assert(&NodeKind::Eq);
+        while p.eat_if(&NodeKind::Eq) {}
+        let column = p.column(p.prev_end());
+        markup_indented(p, column);
+    });
 }
 
 /// Parse a single list item.
-fn list_node(p: &mut Parser) -> MarkupNode {
-    let start = p.next_start();
-    p.eat_assert(Token::Hyph);
-    let column = p.column(p.prev_end());
-    let body = markup_indented(p, column);
-    MarkupNode::List(Box::new(ListNode { span: p.span_from(start), body }))
+fn list_node(p: &mut Parser) {
+    p.perform(NodeKind::List, |p| {
+        p.eat_assert(&NodeKind::Minus);
+        let column = p.column(p.prev_end());
+        markup_indented(p, column);
+    });
 }
 
 /// Parse a single enum item.
-fn enum_node(p: &mut Parser, number: Option<usize>) -> MarkupNode {
-    let start = p.next_start();
-    p.eat_assert(Token::Numbering(number));
-    let column = p.column(p.prev_end());
-    let body = markup_indented(p, column);
-    MarkupNode::Enum(Box::new(EnumNode {
-        span: p.span_from(start),
-        number,
-        body,
-    }))
+fn enum_node(p: &mut Parser) {
+    p.perform(NodeKind::Enum, |p| {
+        p.eat();
+        let column = p.column(p.prev_end());
+        markup_indented(p, column);
+    });
 }
 
 /// Parse an expression.
-fn expr(p: &mut Parser) -> Option<Expr> {
-    expr_with(p, false, 0)
+fn expr(p: &mut Parser) -> ParseResult {
+    expr_prec(p, false, 0)
 }
 
 /// Parse an expression with operators having at least the minimum precedence.
@@ -231,13 +177,16 @@ fn expr(p: &mut Parser) -> Option<Expr> {
 /// in markup.
 ///
 /// Stops parsing at operations with lower precedence than `min_prec`,
-fn expr_with(p: &mut Parser, atomic: bool, min_prec: usize) -> Option<Expr> {
-    let start = p.next_start();
-    let mut lhs = match p.eat_map(UnOp::from_token) {
+fn expr_prec(p: &mut Parser, atomic: bool, min_prec: usize) -> ParseResult {
+    let marker = p.marker();
+
+    // Start the unary expression.
+    match p.peek().and_then(UnOp::from_token) {
         Some(op) => {
+            p.eat();
             let prec = op.precedence();
-            let expr = expr_with(p, atomic, prec)?;
-            Expr::Unary(Box::new(UnaryExpr { span: p.span_from(start), op, expr }))
+            expr_prec(p, atomic, prec)?;
+            marker.end(p, NodeKind::Unary);
         }
         None => primary(p, atomic)?,
     };
@@ -245,19 +194,19 @@ fn expr_with(p: &mut Parser, atomic: bool, min_prec: usize) -> Option<Expr> {
     loop {
         // Exclamation mark, parenthesis or bracket means this is a function
         // call.
-        if matches!(p.peek_direct(), Some(Token::LeftParen | Token::LeftBracket)) {
-            lhs = call(p, lhs)?;
+        if let Some(NodeKind::LeftParen | NodeKind::LeftBracket) = p.peek_direct() {
+            call(p, marker)?;
             continue;
         }
 
-        if p.eat_if(Token::With) {
-            lhs = with_expr(p, lhs)?;
-        }
-
         if atomic {
             break;
         }
 
+        if p.at(&NodeKind::With) {
+            with_expr(p, marker)?;
+        }
+
         let op = match p.peek().and_then(BinOp::from_token) {
             Some(binop) => binop,
             None => break,
@@ -269,96 +218,94 @@ fn expr_with(p: &mut Parser, atomic: bool, min_prec: usize) -> Option<Expr> {
         }
 
         p.eat();
+
         match op.associativity() {
             Associativity::Left => prec += 1,
             Associativity::Right => {}
         }
 
-        let rhs = match expr_with(p, atomic, prec) {
-            Some(rhs) => rhs,
-            None => break,
-        };
-
-        let span = lhs.span().join(rhs.span());
-        lhs = Expr::Binary(Box::new(BinaryExpr { span, lhs, op, rhs }));
+        marker.perform(p, NodeKind::Binary, |p| expr_prec(p, atomic, prec))?;
     }
 
-    Some(lhs)
+    Ok(())
 }
 
 /// Parse a primary expression.
-fn primary(p: &mut Parser, atomic: bool) -> Option<Expr> {
-    if let Some(expr) = literal(p) {
-        return Some(expr);
+fn primary(p: &mut Parser, atomic: bool) -> ParseResult {
+    if literal(p) {
+        return Ok(());
     }
 
     match p.peek() {
         // Things that start with an identifier.
-        Some(Token::Ident(string)) => {
-            let ident = Ident {
-                span: p.eat_span(),
-                string: string.into(),
-            };
+        Some(NodeKind::Ident(_)) => {
+            let marker = p.marker();
+            p.eat();
 
             // Arrow means this is a closure's lone parameter.
-            Some(if !atomic && p.eat_if(Token::Arrow) {
-                let body = expr(p)?;
-                Expr::Closure(Box::new(ClosureExpr {
-                    span: ident.span.join(body.span()),
-                    name: None,
-                    params: vec![ClosureParam::Pos(ident)],
-                    body: Rc::new(body),
-                }))
+            if !atomic && p.at(&NodeKind::Arrow) {
+                marker.end(p, NodeKind::ClosureParams);
+                p.eat_assert(&NodeKind::Arrow);
+                marker.perform(p, NodeKind::Closure, expr)
             } else {
-                Expr::Ident(Box::new(ident))
-            })
+                Ok(())
+            }
         }
 
         // Structures.
-        Some(Token::LeftParen) => parenthesized(p),
-        Some(Token::LeftBracket) => Some(template(p)),
-        Some(Token::LeftBrace) => Some(block(p)),
+        Some(NodeKind::LeftParen) => parenthesized(p),
+        Some(NodeKind::LeftBracket) => {
+            template(p);
+            Ok(())
+        }
+        Some(NodeKind::LeftBrace) => {
+            block(p);
+            Ok(())
+        }
 
         // Keywords.
-        Some(Token::Let) => let_expr(p),
-        Some(Token::If) => if_expr(p),
-        Some(Token::While) => while_expr(p),
-        Some(Token::For) => for_expr(p),
-        Some(Token::Import) => import_expr(p),
-        Some(Token::Include) => include_expr(p),
+        Some(NodeKind::Let) => let_expr(p),
+        Some(NodeKind::If) => if_expr(p),
+        Some(NodeKind::While) => while_expr(p),
+        Some(NodeKind::For) => for_expr(p),
+        Some(NodeKind::Import) => import_expr(p),
+        Some(NodeKind::Include) => include_expr(p),
+
+        Some(NodeKind::Error(_, _)) => {
+            p.eat();
+            Err(())
+        }
 
         // Nothing.
         _ => {
             p.expected("expression");
-            None
+            Err(())
         }
     }
 }
 
 /// Parse a literal.
-fn literal(p: &mut Parser) -> Option<Expr> {
-    let span = p.peek_span();
-    let lit = match p.peek()? {
+fn literal(p: &mut Parser) -> bool {
+    match p.peek() {
         // Basic values.
-        Token::None => Lit::None(span),
-        Token::Auto => Lit::Auto(span),
-        Token::Bool(b) => Lit::Bool(span, b),
-        Token::Int(i) => Lit::Int(span, i),
-        Token::Float(f) => Lit::Float(span, f),
-        Token::Length(val, unit) => Lit::Length(span, val, unit),
-        Token::Angle(val, unit) => Lit::Angle(span, val, unit),
-        Token::Percent(p) => Lit::Percent(span, p),
-        Token::Fraction(p) => Lit::Fractional(span, p),
-        Token::Str(token) => Lit::Str(span, {
-            if !token.terminated {
-                p.expected_at(span.end, "quote");
-            }
-            resolve::resolve_string(token.string)
-        }),
-        _ => return None,
-    };
-    p.eat();
-    Some(Expr::Lit(Box::new(lit)))
+        Some(
+            NodeKind::None
+            | NodeKind::Auto
+            | NodeKind::Int(_)
+            | NodeKind::Float(_)
+            | NodeKind::Bool(_)
+            | NodeKind::Fraction(_)
+            | NodeKind::Length(_, _)
+            | NodeKind::Angle(_, _)
+            | NodeKind::Percentage(_)
+            | NodeKind::Str(_),
+        ) => {
+            p.eat();
+            true
+        }
+
+        _ => false,
+    }
 }
 
 /// Parse something that starts with a parenthesis, which can be either of:
@@ -366,433 +313,395 @@ fn literal(p: &mut Parser) -> Option<Expr> {
 /// - Dictionary literal
 /// - Parenthesized expression
 /// - Parameter list of closure expression
-fn parenthesized(p: &mut Parser) -> Option<Expr> {
-    p.start_group(Group::Paren, TokenMode::Code);
-    let colon = p.eat_if(Token::Colon);
-    let (items, has_comma) = collection(p);
-    let span = p.end_group();
+fn parenthesized(p: &mut Parser) -> ParseResult {
+    let marker = p.marker();
 
-    // Leading colon makes this a dictionary.
+    p.start_group(Group::Paren);
+    let colon = p.eat_if(&NodeKind::Colon);
+    let kind = collection(p).0;
+    p.end_group();
+
+    // Leading colon makes this a (empty) dictionary.
     if colon {
-        return Some(dict(p, items, span));
+        dict(p, marker);
+        return Ok(());
     }
 
     // Arrow means this is a closure's parameter list.
-    if p.eat_if(Token::Arrow) {
-        let params = params(p, items);
-        let body = expr(p)?;
-        return Some(Expr::Closure(Box::new(ClosureExpr {
-            span: span.join(body.span()),
-            name: None,
-            params,
-            body: Rc::new(body),
-        })));
+    if p.at(&NodeKind::Arrow) {
+        params(p, marker);
+        p.eat_assert(&NodeKind::Arrow);
+        return marker.perform(p, NodeKind::Closure, expr);
     }
 
-    // Find out which kind of collection this is.
-    Some(match items.as_slice() {
-        [] => array(p, items, span),
-        [CallArg::Pos(_)] if !has_comma => match items.into_iter().next() {
-            Some(CallArg::Pos(expr)) => Expr::Group(Box::new(GroupExpr { span, expr })),
-            _ => unreachable!(),
-        },
-        [CallArg::Pos(_), ..] => array(p, items, span),
-        [CallArg::Named(_), ..] => dict(p, items, span),
-        [CallArg::Spread(expr), ..] => {
-            p.error(expr.span(), "spreading is not allowed here");
-            return None;
-        }
-    })
+    // Transform into the identified collection.
+    match kind {
+        CollectionKind::Group => marker.end(p, NodeKind::Group),
+        CollectionKind::Positional => array(p, marker),
+        CollectionKind::Named => dict(p, marker),
+    }
+
+    Ok(())
+}
+
+/// The type of a collection.
+#[derive(Debug, Copy, Clone, Eq, PartialEq)]
+enum CollectionKind {
+    /// The collection is only one item and has no comma.
+    Group,
+    /// The collection starts with a positional and has more items or a trailing
+    /// comma.
+    Positional,
+    /// The collection starts with a named item.
+    Named,
 }
 
 /// Parse a collection.
 ///
-/// Returns whether the literal contained any commas.
-fn collection(p: &mut Parser) -> (Vec<CallArg>, bool) {
-    let mut items = vec![];
-    let mut has_comma = false;
-    let mut missing_coma = None;
+/// Returns the length of the collection and whether the literal contained any
+/// commas.
+fn collection(p: &mut Parser) -> (CollectionKind, usize) {
+    let mut kind = CollectionKind::Positional;
+    let mut items = 0;
+    let mut can_group = true;
+    let mut error = false;
+    let mut missing_coma: Option<Marker> = None;
 
     while !p.eof() {
-        if let Some(arg) = item(p) {
-            items.push(arg);
+        if let Ok(item_kind) = item(p) {
+            if items == 0 && item_kind == NodeKind::Named {
+                kind = CollectionKind::Named;
+                can_group = false;
+            }
 
-            if let Some(pos) = missing_coma.take() {
-                p.expected_at(pos, "comma");
+            if item_kind == NodeKind::Spread {
+                can_group = false;
+            }
+
+            items += 1;
+
+            if let Some(marker) = missing_coma.take() {
+                marker.expected(p, "comma");
             }
 
             if p.eof() {
                 break;
             }
 
-            let behind = p.prev_end();
-            if p.eat_if(Token::Comma) {
-                has_comma = true;
+            if p.eat_if(&NodeKind::Comma) {
+                can_group = false;
             } else {
-                missing_coma = Some(behind);
+                missing_coma = Some(p.trivia_start());
             }
+        } else {
+            error = true;
         }
     }
 
-    (items, has_comma)
+    if error || (can_group && items == 1) {
+        kind = CollectionKind::Group;
+    }
+
+    (kind, items)
 }
 
-/// Parse an expression or a named pair.
-fn item(p: &mut Parser) -> Option<CallArg> {
-    if p.eat_if(Token::Dots) {
-        return expr(p).map(CallArg::Spread);
+/// Parse an expression or a named pair, returning whether it's a spread or a
+/// named pair.
+fn item(p: &mut Parser) -> ParseResult<NodeKind> {
+    let marker = p.marker();
+    if p.eat_if(&NodeKind::Dots) {
+        marker.perform(p, NodeKind::Spread, expr)?;
+        return Ok(NodeKind::Spread);
     }
 
-    let first = expr(p)?;
-    if p.eat_if(Token::Colon) {
-        if let Expr::Ident(name) = first {
-            Some(CallArg::Named(Named { name: *name, expr: expr(p)? }))
-        } else {
-            p.error(first.span(), "expected identifier");
-            expr(p);
-            None
-        }
+    expr(p)?;
+
+    if p.at(&NodeKind::Colon) {
+        marker.perform(p, NodeKind::Named, |p| {
+            if let Some(NodeKind::Ident(_)) = marker.peek(p).map(|c| c.kind()) {
+                p.eat();
+                expr(p)
+            } else {
+                let error = NodeKind::Error(ErrorPos::Full, "expected identifier".into());
+                marker.end(p, error);
+                p.eat();
+                expr(p).ok();
+                Err(())
+            }
+        })?;
+
+        Ok(NodeKind::Named)
     } else {
-        Some(CallArg::Pos(first))
+        Ok(NodeKind::None)
     }
 }
 
 /// Convert a collection into an array, producing errors for anything other than
 /// expressions.
-fn array(p: &mut Parser, items: Vec<CallArg>, span: Span) -> Expr {
-    let iter = items.into_iter().filter_map(|item| match item {
-        CallArg::Pos(expr) => Some(expr),
-        CallArg::Named(_) => {
-            p.error(item.span(), "expected expression, found named pair");
-            None
-        }
-        CallArg::Spread(_) => {
-            p.error(item.span(), "spreading is not allowed here");
-            None
-        }
+fn array(p: &mut Parser, marker: Marker) {
+    marker.filter_children(p, |x| match x.kind() {
+        NodeKind::Named => Err("expected expression, found named pair"),
+        NodeKind::Spread => Err("spreading is not allowed here"),
+        _ => Ok(()),
     });
-    Expr::Array(Box::new(ArrayExpr { span, items: iter.collect() }))
+    marker.end(p, NodeKind::Array);
 }
 
 /// Convert a collection into a dictionary, producing errors for anything other
 /// than named pairs.
-fn dict(p: &mut Parser, items: Vec<CallArg>, span: Span) -> Expr {
-    let iter = items.into_iter().filter_map(|item| match item {
-        CallArg::Named(named) => Some(named),
-        CallArg::Pos(_) => {
-            p.error(item.span(), "expected named pair, found expression");
-            None
-        }
-        CallArg::Spread(_) => {
-            p.error(item.span(), "spreading is not allowed here");
-            None
-        }
+fn dict(p: &mut Parser, marker: Marker) {
+    marker.filter_children(p, |x| match x.kind() {
+        kind if kind.is_paren() => Ok(()),
+        NodeKind::Named | NodeKind::Comma | NodeKind::Colon => Ok(()),
+        NodeKind::Spread => Err("spreading is not allowed here"),
+        _ => Err("expected named pair, found expression"),
     });
-    Expr::Dict(Box::new(DictExpr { span, items: iter.collect() }))
+    marker.end(p, NodeKind::Dict);
 }
 
 /// Convert a collection into a list of parameters, producing errors for
 /// anything other than identifiers, spread operations and named pairs.
-fn params(p: &mut Parser, items: Vec<CallArg>) -> Vec<ClosureParam> {
-    let iter = items.into_iter().filter_map(|item| match item {
-        CallArg::Pos(Expr::Ident(ident)) => Some(ClosureParam::Pos(*ident)),
-        CallArg::Named(named) => Some(ClosureParam::Named(named)),
-        CallArg::Spread(Expr::Ident(ident)) => Some(ClosureParam::Sink(*ident)),
-        _ => {
-            p.error(item.span(), "expected identifier");
-            None
-        }
+fn params(p: &mut Parser, marker: Marker) {
+    marker.filter_children(p, |x| match x.kind() {
+        kind if kind.is_paren() => Ok(()),
+        NodeKind::Named | NodeKind::Comma | NodeKind::Ident(_) => Ok(()),
+        NodeKind::Spread
+            if matches!(
+                x.children().last().map(|child| child.kind()),
+                Some(&NodeKind::Ident(_))
+            ) =>
+        {
+            Ok(())
+        }
+        _ => Err("expected identifier"),
     });
-    iter.collect()
-}
-
-/// Convert a collection into a list of identifiers, producing errors for
-/// anything other than identifiers.
-fn idents(p: &mut Parser, items: Vec<CallArg>) -> Vec<Ident> {
-    let iter = items.into_iter().filter_map(|item| match item {
-        CallArg::Pos(Expr::Ident(ident)) => Some(*ident),
-        _ => {
-            p.error(item.span(), "expected identifier");
-            None
-        }
-    });
-    iter.collect()
+    marker.end(p, NodeKind::ClosureParams);
 }
 
 // Parse a template block: `[...]`.
-fn template(p: &mut Parser) -> Expr {
-    p.start_group(Group::Bracket, TokenMode::Markup);
-    let tree = markup(p);
-    let span = p.end_group();
-    Expr::Template(Box::new(TemplateExpr { span, body: tree }))
+fn template(p: &mut Parser) {
+    p.perform(NodeKind::Template, |p| {
+        p.start_group(Group::Bracket);
+        markup(p);
+        p.end_group();
+    });
 }
 
 /// Parse a code block: `{...}`.
-fn block(p: &mut Parser) -> Expr {
-    p.start_group(Group::Brace, TokenMode::Code);
-    let mut exprs = vec![];
-    while !p.eof() {
-        p.start_group(Group::Stmt, TokenMode::Code);
-        if let Some(expr) = expr(p) {
-            exprs.push(expr);
-            if !p.eof() {
-                p.expected_at(p.prev_end(), "semicolon or line break");
+fn block(p: &mut Parser) {
+    p.perform(NodeKind::Block, |p| {
+        p.start_group(Group::Brace);
+        while !p.eof() {
+            p.start_group(Group::Stmt);
+            if expr(p).is_ok() && !p.eof() {
+                p.expected_at("semicolon or line break");
             }
+            p.end_group();
+
+            // Forcefully skip over newlines since the group's contents can't.
+            p.eat_while(|t| matches!(t, NodeKind::Space(_)));
         }
         p.end_group();
-
-        // Forcefully skip over newlines since the group's contents can't.
-        p.eat_while(|t| matches!(t, Token::Space(_)));
-    }
-    let span = p.end_group();
-    Expr::Block(Box::new(BlockExpr { span, exprs }))
+    });
 }
 
 /// Parse a function call.
-fn call(p: &mut Parser, callee: Expr) -> Option<Expr> {
-    let mut args = match p.peek_direct() {
-        Some(Token::LeftParen) => args(p),
-        Some(Token::LeftBracket) => CallArgs {
-            span: Span::at(p.id(), callee.span().end),
-            items: vec![],
-        },
+fn call(p: &mut Parser, callee: Marker) -> ParseResult {
+    callee.perform(p, NodeKind::Call, |p| match p.peek_direct() {
+        Some(NodeKind::LeftParen | NodeKind::LeftBracket) => {
+            args(p, true);
+            Ok(())
+        }
         _ => {
-            p.expected_at(p.prev_end(), "argument list");
-            return None;
+            p.expected_at("argument list");
+            Err(())
         }
-    };
-
-    while p.peek_direct() == Some(Token::LeftBracket) {
-        let body = template(p);
-        args.items.push(CallArg::Pos(body));
-    }
-
-    Some(Expr::Call(Box::new(CallExpr {
-        span: p.span_from(callee.span().start),
-        callee,
-        args,
-    })))
+    })
 }
 
 /// Parse the arguments to a function call.
-fn args(p: &mut Parser) -> CallArgs {
-    p.start_group(Group::Paren, TokenMode::Code);
-    let items = collection(p).0;
-    let span = p.end_group();
-    CallArgs { span, items }
+fn args(p: &mut Parser, allow_template: bool) {
+    p.perform(NodeKind::CallArgs, |p| {
+        if !allow_template || p.peek_direct() == Some(&NodeKind::LeftParen) {
+            p.start_group(Group::Paren);
+            collection(p);
+            p.end_group();
+        }
+
+        while allow_template && p.peek_direct() == Some(&NodeKind::LeftBracket) {
+            template(p);
+        }
+    })
 }
 
 /// Parse a with expression.
-fn with_expr(p: &mut Parser, callee: Expr) -> Option<Expr> {
-    if p.peek() == Some(Token::LeftParen) {
-        Some(Expr::With(Box::new(WithExpr {
-            span: p.span_from(callee.span().start),
-            callee,
-            args: args(p),
-        })))
-    } else {
-        p.expected("argument list");
-        None
-    }
+fn with_expr(p: &mut Parser, marker: Marker) -> ParseResult {
+    marker.perform(p, NodeKind::WithExpr, |p| {
+        p.eat_assert(&NodeKind::With);
+
+        if p.at(&NodeKind::LeftParen) {
+            args(p, false);
+            Ok(())
+        } else {
+            p.expected("argument list");
+            Err(())
+        }
+    })
 }
 
 /// Parse a let expression.
-fn let_expr(p: &mut Parser) -> Option<Expr> {
-    let start = p.next_start();
-    p.eat_assert(Token::Let);
+fn let_expr(p: &mut Parser) -> ParseResult {
+    p.perform(NodeKind::LetExpr, |p| {
+        p.eat_assert(&NodeKind::Let);
 
-    let mut output = None;
-    if let Some(binding) = ident(p) {
-        let mut init = None;
+        let marker = p.marker();
+        ident(p)?;
 
-        if p.eat_if(Token::With) {
-            init = with_expr(p, Expr::Ident(Box::new(binding.clone())));
+        if p.at(&NodeKind::With) {
+            with_expr(p, marker)?;
         } else {
             // If a parenthesis follows, this is a function definition.
-            let mut maybe_params = None;
-            if p.peek_direct() == Some(Token::LeftParen) {
-                p.start_group(Group::Paren, TokenMode::Code);
-                let items = collection(p).0;
-                maybe_params = Some(params(p, items));
+            let has_params = p.peek_direct() == Some(&NodeKind::LeftParen);
+            if has_params {
+                let marker = p.marker();
+                p.start_group(Group::Paren);
+                collection(p);
                 p.end_group();
+                params(p, marker);
             }
 
-            if p.eat_if(Token::Eq) {
-                init = expr(p);
-            } else if maybe_params.is_some() {
+            if p.eat_if(&NodeKind::Eq) {
+                expr(p)?;
+            } else if has_params {
                 // Function definitions must have a body.
-                p.expected_at(p.prev_end(), "body");
+                p.expected_at("body");
             }
 
             // Rewrite into a closure expression if it's a function definition.
-            if let Some(params) = maybe_params {
-                let body = init?;
-                init = Some(Expr::Closure(Box::new(ClosureExpr {
-                    span: binding.span.join(body.span()),
-                    name: Some(binding.clone()),
-                    params,
-                    body: Rc::new(body),
-                })));
+            if has_params {
+                marker.end(p, NodeKind::Closure);
             }
         }
 
-        output = Some(Expr::Let(Box::new(LetExpr {
-            span: p.span_from(start),
-            binding,
-            init,
-        })));
-    }
-
-    output
+        Ok(())
+    })
 }
 
 /// Parse an if expresion.
-fn if_expr(p: &mut Parser) -> Option<Expr> {
-    let start = p.next_start();
-    p.eat_assert(Token::If);
-
-    let mut output = None;
-    if let Some(condition) = expr(p) {
-        if let Some(if_body) = body(p) {
-            let mut else_body = None;
-            if p.eat_if(Token::Else) {
-                if p.peek() == Some(Token::If) {
-                    else_body = if_expr(p);
-                } else {
-                    else_body = body(p);
-                }
-            }
+fn if_expr(p: &mut Parser) -> ParseResult {
+    p.perform(NodeKind::IfExpr, |p| {
+        p.eat_assert(&NodeKind::If);
+
+        expr(p)?;
+        body(p)?;
 
-            output = Some(Expr::If(Box::new(IfExpr {
-                span: p.span_from(start),
-                condition,
-                if_body,
-                else_body,
-            })));
+        if p.eat_if(&NodeKind::Else) {
+            if p.at(&NodeKind::If) {
+                if_expr(p)?;
+            } else {
+                body(p)?;
+            }
         }
-    }
 
-    output
+        Ok(())
+    })
 }
 
 /// Parse a while expresion.
-fn while_expr(p: &mut Parser) -> Option<Expr> {
-    let start = p.next_start();
-    p.eat_assert(Token::While);
-
-    let mut output = None;
-    if let Some(condition) = expr(p) {
-        if let Some(body) = body(p) {
-            output = Some(Expr::While(Box::new(WhileExpr {
-                span: p.span_from(start),
-                condition,
-                body,
-            })));
-        }
-    }
-
-    output
+fn while_expr(p: &mut Parser) -> ParseResult {
+    p.perform(NodeKind::WhileExpr, |p| {
+        p.eat_assert(&NodeKind::While);
+        expr(p)?;
+        body(p)?;
+        Ok(())
+    })
 }
 
 /// Parse a for expression.
-fn for_expr(p: &mut Parser) -> Option<Expr> {
-    let start = p.next_start();
-    p.eat_assert(Token::For);
-
-    let mut output = None;
-    if let Some(pattern) = for_pattern(p) {
-        if p.eat_expect(Token::In) {
-            if let Some(iter) = expr(p) {
-                if let Some(body) = body(p) {
-                    output = Some(Expr::For(Box::new(ForExpr {
-                        span: p.span_from(start),
-                        pattern,
-                        iter,
-                        body,
-                    })));
-                }
-            }
-        }
-    }
-
-    output
+fn for_expr(p: &mut Parser) -> ParseResult {
+    p.perform(NodeKind::ForExpr, |p| {
+        p.eat_assert(&NodeKind::For);
+        for_pattern(p)?;
+        p.eat_expect(&NodeKind::In)?;
+        expr(p)?;
+        body(p)?;
+        Ok(())
+    })
 }
 
 /// Parse a for loop pattern.
-fn for_pattern(p: &mut Parser) -> Option<ForPattern> {
-    let first = ident(p)?;
-    if p.eat_if(Token::Comma) {
-        if let Some(second) = ident(p) {
-            return Some(ForPattern::KeyValue(first, second));
+fn for_pattern(p: &mut Parser) -> ParseResult {
+    p.perform(NodeKind::ForPattern, |p| {
+        ident(p)?;
+        if p.eat_if(&NodeKind::Comma) {
+            ident(p)?;
         }
-    }
-    Some(ForPattern::Value(first))
+        Ok(())
+    })
 }
 
 /// Parse an import expression.
-fn import_expr(p: &mut Parser) -> Option<Expr> {
-    let start = p.next_start();
-    p.eat_assert(Token::Import);
+fn import_expr(p: &mut Parser) -> ParseResult {
+    p.perform(NodeKind::ImportExpr, |p| {
+        p.eat_assert(&NodeKind::Import);
+
+        if !p.eat_if(&NodeKind::Star) {
+            // This is the list of identifiers scenario.
+            p.perform(NodeKind::ImportItems, |p| {
+                p.start_group(Group::Imports);
+                let marker = p.marker();
+                let items = collection(p).1;
+                if items == 0 {
+                    p.expected_at("import items");
+                }
+                p.end_group();
 
-    let imports = if p.eat_if(Token::Star) {
-        // This is the wildcard scenario.
-        Imports::Wildcard
-    } else {
-        // This is the list of identifiers scenario.
-        p.start_group(Group::Imports, TokenMode::Code);
-        let items = collection(p).0;
-        if items.is_empty() {
-            p.expected_at(p.prev_end(), "import items");
-        }
-        p.end_group();
-        Imports::Idents(idents(p, items))
-    };
+                marker.filter_children(p, |n| match n.kind() {
+                    NodeKind::Ident(_) | NodeKind::Comma => Ok(()),
+                    _ => Err("expected identifier"),
+                });
+            });
+        };
 
-    let mut output = None;
-    if p.eat_expect(Token::From) {
-        if let Some(path) = expr(p) {
-            output = Some(Expr::Import(Box::new(ImportExpr {
-                span: p.span_from(start),
-                imports,
-                path,
-            })));
-        }
-    }
+        p.eat_expect(&NodeKind::From)?;
+        expr(p)?;
 
-    output
+        Ok(())
+    })
 }
 
 /// Parse an include expression.
-fn include_expr(p: &mut Parser) -> Option<Expr> {
-    let start = p.next_start();
-    p.eat_assert(Token::Include);
-
-    expr(p).map(|path| {
-        Expr::Include(Box::new(IncludeExpr { span: p.span_from(start), path }))
+fn include_expr(p: &mut Parser) -> ParseResult {
+    p.perform(NodeKind::IncludeExpr, |p| {
+        p.eat_assert(&NodeKind::Include);
+        expr(p)?;
+        Ok(())
     })
 }
 
 /// Parse an identifier.
-fn ident(p: &mut Parser) -> Option<Ident> {
-    if let Some(Token::Ident(string)) = p.peek() {
-        Some(Ident {
-            span: p.eat_span(),
-            string: string.into(),
-        })
-    } else {
-        p.expected("identifier");
-        None
+fn ident(p: &mut Parser) -> ParseResult {
+    match p.peek() {
+        Some(NodeKind::Ident(_)) => {
+            p.eat();
+            Ok(())
+        }
+        _ => {
+            p.expected("identifier");
+            Err(())
+        }
     }
 }
 
 /// Parse a control flow body.
-fn body(p: &mut Parser) -> Option<Expr> {
+fn body(p: &mut Parser) -> ParseResult {
     match p.peek() {
-        Some(Token::LeftBracket) => Some(template(p)),
-        Some(Token::LeftBrace) => Some(block(p)),
+        Some(NodeKind::LeftBracket) => template(p),
+        Some(NodeKind::LeftBrace) => block(p),
         _ => {
-            p.expected_at(p.prev_end(), "body");
-            None
+            p.expected_at("body");
+            return Err(());
         }
     }
+    Ok(())
 }