rantlr_core/

parser.rs

//! Recursive-descent parser: Token stream → [`Grammar`] AST.

use crate::ast::{
    ExampleDecl, Expr, Grammar, GrammarItem, ImportDecl, RuleDecl, TokenBody, TokenDecl,
};
use crate::diagnostic::{Diagnostic, DiagnosticKind};
use crate::error::RantlrError;
use crate::lexer::{lex, LexerError};
use crate::span::Span;
use crate::token::{Keyword, Token, TokenKind};

/// Parse a `.gr` source string into a [`Grammar`] AST.
pub fn parse(source: &str) -> Result<Grammar, RantlrError> {
    let tokens = lex(source).map_err(|e| match e {
        LexerError::Diagnostic(diag) => RantlrError::from_diagnostic(source, diag),
    })?;
    Parser::new(source, tokens).parse_grammar()
}

struct Parser<'src> {
    source: &'src str,
    tokens: Vec<Token>,
    pos: usize,
}

impl<'src> Parser<'src> {
    fn new(source: &'src str, tokens: Vec<Token>) -> Self {
        Self {
            source,
            tokens,
            pos: 0,
        }
    }

    fn parse_grammar(mut self) -> Result<Grammar, RantlrError> {
        let start = self.peek().span;
        self.expect_keyword(Keyword::Grammar)?;
        let (name, name_span) = self.expect_ident("grammar name")?;
        self.expect_semi()?;

        let mut items = Vec::new();
        while !self.at_eof() {
            items.push(self.parse_item()?);
        }

        let end = self.prev_span();
        Ok(Grammar {
            name,
            name_span,
            items,
            span: start.merge(end),
        })
    }

    fn parse_item(&mut self) -> Result<GrammarItem, RantlrError> {
        match &self.peek().kind {
            TokenKind::Keyword(Keyword::Token) => Ok(GrammarItem::Token(self.parse_token_decl()?)),
            TokenKind::Keyword(Keyword::Rule) => Ok(GrammarItem::Rule(self.parse_rule_decl()?)),
            TokenKind::Keyword(Keyword::Example) => {
                Ok(GrammarItem::Example(self.parse_example_decl()?))
            }
            TokenKind::Keyword(Keyword::Import) => {
                Ok(GrammarItem::Import(self.parse_import_decl()?))
            }
            _ => Err(self.unexpected(
                "expected `token`, `rule`, `example`, or `import`",
            )),
        }
    }

    fn parse_token_decl(&mut self) -> Result<TokenDecl, RantlrError> {
        let start = self.peek().span;
        self.expect_keyword(Keyword::Token)?;
        let (name, name_span) = self.expect_ident("token name")?;
        self.expect_kind(TokenKind::Eq, "`=`")?;

        let body = match &self.peek().kind {
            TokenKind::Builtin(b) => {
                let b = *b;
                self.bump();
                TokenBody::Builtin(b)
            }
            TokenKind::String(s) => {
                let s = s.clone();
                self.bump();
                TokenBody::Literal(s)
            }
            TokenKind::Ident(name) => {
                // Allow lowercase mistake? Only builtins are PascalCase tokens.
                // If someone writes an ident, suggest builtins.
                let span = self.peek().span;
                let name = name.clone();
                return Err(self.err_at(
                    span,
                    format!("expected a built-in type or string literal, found `{name}`"),
                    Some("built-ins: Number, QuotedString, Email, Url, DateTime"),
                ));
            }
            _ => {
                return Err(self.unexpected(
                    "expected a built-in type (e.g. Number) or a string literal",
                ));
            }
        };

        let skip = if self.eat_kind(&TokenKind::Arrow) {
            self.expect_keyword(Keyword::Skip)?;
            true
        } else {
            false
        };

        self.expect_semi()?;
        let end = self.prev_span();
        Ok(TokenDecl {
            name,
            name_span,
            body,
            skip,
            span: start.merge(end),
        })
    }

    fn parse_rule_decl(&mut self) -> Result<RuleDecl, RantlrError> {
        let start = self.peek().span;
        self.expect_keyword(Keyword::Rule)?;
        let (name, name_span) = self.expect_ident("rule name")?;
        self.expect_kind(TokenKind::LBrace, "`{`")?;
        let body = self.parse_expr()?;
        self.expect_kind(TokenKind::RBrace, "`}`")?;
        let end = self.prev_span();
        Ok(RuleDecl {
            name,
            name_span,
            body,
            span: start.merge(end),
        })
    }

    fn parse_example_decl(&mut self) -> Result<ExampleDecl, RantlrError> {
        let start = self.peek().span;
        self.expect_keyword(Keyword::Example)?;

        let label = if let TokenKind::String(s) = &self.peek().kind {
            let s = s.clone();
            self.bump();
            Some(s)
        } else {
            None
        };

        self.expect_kind(TokenKind::LBrace, "`{`")?;
        self.expect_keyword(Keyword::Input)?;
        self.expect_kind(TokenKind::Colon, "`:`")?;

        let input = match &self.peek().kind {
            TokenKind::RawString(s) | TokenKind::String(s) => {
                let s = s.clone();
                self.bump();
                s
            }
            _ => {
                return Err(self.unexpected(
                    "expected example input as a string or raw string (`...`)",
                ));
            }
        };

        let expect = if self.eat_keyword(Keyword::Expect) {
            self.expect_kind(TokenKind::Colon, "`:`")?;
            let (name, _) = self.expect_ident("expected rule name")?;
            Some(name)
        } else {
            None
        };

        self.expect_kind(TokenKind::RBrace, "`}`")?;
        let end = self.prev_span();
        Ok(ExampleDecl {
            label,
            input,
            expect,
            span: start.merge(end),
        })
    }

    fn parse_import_decl(&mut self) -> Result<ImportDecl, RantlrError> {
        let start = self.peek().span;
        self.expect_keyword(Keyword::Import)?;
        let path = match &self.peek().kind {
            TokenKind::String(s) => {
                let s = s.clone();
                self.bump();
                s
            }
            _ => return Err(self.unexpected("expected a string path after `import`")),
        };
        self.expect_semi()?;
        let end = self.prev_span();
        Ok(ImportDecl {
            path,
            span: start.merge(end),
        })
    }

    // ── Expressions ──────────────────────────────────────────────
    // expr  = alt
    // alt   = seq ("|" seq)*
    // seq   = atom+
    // atom  = match | repeat | optional | primary
    // primary = Ident | Builtin | String | "(" expr ")"

    fn parse_expr(&mut self) -> Result<Expr, RantlrError> {
        self.parse_alt()
    }

    fn parse_alt(&mut self) -> Result<Expr, RantlrError> {
        let mut alts = vec![self.parse_seq()?];
        while self.eat_kind(&TokenKind::Pipe) {
            alts.push(self.parse_seq()?);
        }
        Ok(Expr::alt(alts))
    }

    fn parse_seq(&mut self) -> Result<Expr, RantlrError> {
        let mut items = Vec::new();
        while self.at_atom_start() {
            items.push(self.parse_atom()?);
        }
        if items.is_empty() {
            return Err(self.unexpected(
                "expected an expression (match, repeat, optional, name, string, or group)",
            ));
        }
        Ok(Expr::seq(items))
    }

    fn parse_atom(&mut self) -> Result<Expr, RantlrError> {
        match &self.peek().kind {
            TokenKind::Keyword(Keyword::Match) => self.parse_match(),
            TokenKind::Keyword(Keyword::Repeat) => self.parse_repeat(),
            TokenKind::Keyword(Keyword::Optional) => self.parse_optional(),
            _ => self.parse_primary(),
        }
    }

    fn parse_match(&mut self) -> Result<Expr, RantlrError> {
        self.expect_keyword(Keyword::Match)?;
        // Each arm is a single primary so `match "+" | "-" term` parses as
        // Match(["+","-"]) followed by Ref(term), not one giant match arm.
        // Use a group for compound arms: `match Num | ("(" expr ")")`.
        let mut arms = vec![self.parse_primary()?];
        while self.eat_kind(&TokenKind::Pipe) {
            if !self.at_primary_start() {
                return Err(self.unexpected("expected a match arm after `|`"));
            }
            arms.push(self.parse_primary()?);
        }
        Ok(Expr::Match { arms })
    }

    fn parse_repeat(&mut self) -> Result<Expr, RantlrError> {
        self.expect_keyword(Keyword::Repeat)?;

        let (min, max) = if self.eat_kind(&TokenKind::LParen) {
            let min = match &self.peek().kind {
                TokenKind::Integer(n) => {
                    let n = *n;
                    self.bump();
                    Some(n)
                }
                TokenKind::DotDot => None,
                _ => {
                    return Err(self.unexpected(
                        "expected a lower bound integer or `..` in repeat(...)",
                    ));
                }
            };
            self.expect_kind(TokenKind::DotDot, "`..`")?;
            let max = if let TokenKind::Integer(n) = &self.peek().kind {
                let n = *n;
                self.bump();
                Some(n)
            } else {
                None
            };
            self.expect_kind(TokenKind::RParen, "`)`")?;
            (min.or(Some(0)), max)
        } else {
            (None, None)
        };

        self.expect_kind(TokenKind::LBrace, "`{`")?;
        let body = self.parse_expr()?;
        self.expect_kind(TokenKind::RBrace, "`}`")?;

        Ok(Expr::Repeat {
            min,
            max,
            body: Box::new(body),
        })
    }

    fn parse_optional(&mut self) -> Result<Expr, RantlrError> {
        self.expect_keyword(Keyword::Optional)?;
        self.expect_kind(TokenKind::LBrace, "`{`")?;
        let body = self.parse_expr()?;
        self.expect_kind(TokenKind::RBrace, "`}`")?;
        Ok(Expr::Optional {
            body: Box::new(body),
        })
    }

    fn parse_primary(&mut self) -> Result<Expr, RantlrError> {
        let tok = self.peek().clone();
        match tok.kind {
            TokenKind::Ident(name) => {
                self.bump();
                Ok(Expr::Ref {
                    name,
                    span: tok.span,
                })
            }
            TokenKind::Builtin(b) => {
                // Builtins may appear as bare refs only in token decls;
                // in rules, treat as a named ref to the built-in type.
                self.bump();
                Ok(Expr::Ref {
                    name: b.as_str().to_string(),
                    span: tok.span,
                })
            }
            TokenKind::String(value) => {
                self.bump();
                Ok(Expr::Literal {
                    value,
                    span: tok.span,
                })
            }
            TokenKind::LParen => {
                self.bump();
                let body = self.parse_expr()?;
                self.expect_kind(TokenKind::RParen, "`)`")?;
                Ok(Expr::Group {
                    body: Box::new(body),
                })
            }
            _ => Err(self.unexpected("expected a name, string, or `(...)` group")),
        }
    }

    // ── Token helpers ────────────────────────────────────────────

    fn at_atom_start(&self) -> bool {
        matches!(
            &self.peek().kind,
            TokenKind::Keyword(Keyword::Match)
                | TokenKind::Keyword(Keyword::Repeat)
                | TokenKind::Keyword(Keyword::Optional)
                | TokenKind::Ident(_)
                | TokenKind::Builtin(_)
                | TokenKind::String(_)
                | TokenKind::LParen
        )
    }

    fn at_primary_start(&self) -> bool {
        matches!(
            &self.peek().kind,
            TokenKind::Ident(_)
                | TokenKind::Builtin(_)
                | TokenKind::String(_)
                | TokenKind::LParen
        )
    }

    fn at_eof(&self) -> bool {
        self.peek().kind.is_eof()
    }

    fn peek(&self) -> &Token {
        &self.tokens[self.pos.min(self.tokens.len().saturating_sub(1))]
    }

    fn prev_span(&self) -> Span {
        if self.pos == 0 {
            Span::default()
        } else {
            self.tokens[self.pos - 1].span
        }
    }

    fn bump(&mut self) {
        if !self.peek().kind.is_eof() {
            self.pos += 1;
        }
    }

    fn eat_kind(&mut self, kind: &TokenKind) -> bool {
        let matched = match (kind, &self.peek().kind) {
            (TokenKind::LBrace, TokenKind::LBrace)
            | (TokenKind::RBrace, TokenKind::RBrace)
            | (TokenKind::LParen, TokenKind::LParen)
            | (TokenKind::RParen, TokenKind::RParen)
            | (TokenKind::LBracket, TokenKind::LBracket)
            | (TokenKind::RBracket, TokenKind::RBracket)
            | (TokenKind::Pipe, TokenKind::Pipe)
            | (TokenKind::Comma, TokenKind::Comma)
            | (TokenKind::Semi, TokenKind::Semi)
            | (TokenKind::Colon, TokenKind::Colon)
            | (TokenKind::Eq, TokenKind::Eq)
            | (TokenKind::DotDot, TokenKind::DotDot)
            | (TokenKind::Arrow, TokenKind::Arrow)
            | (TokenKind::Eof, TokenKind::Eof) => true,
            _ => false,
        };
        if matched {
            self.bump();
        }
        matched
    }

    fn eat_keyword(&mut self, kw: Keyword) -> bool {
        if matches!(&self.peek().kind, TokenKind::Keyword(k) if *k == kw) {
            self.bump();
            true
        } else {
            false
        }
    }

    fn expect_keyword(&mut self, kw: Keyword) -> Result<(), RantlrError> {
        if self.eat_keyword(kw) {
            Ok(())
        } else {
            Err(self.unexpected(&format!("expected keyword `{}`", kw.as_str())))
        }
    }

    fn expect_kind(&mut self, kind: TokenKind, label: &str) -> Result<(), RantlrError> {
        if self.eat_kind(&kind) {
            Ok(())
        } else {
            Err(self.unexpected(&format!("expected {label}")))
        }
    }

    fn expect_semi(&mut self) -> Result<(), RantlrError> {
        self.expect_kind(TokenKind::Semi, "`;`")
    }

    fn expect_ident(&mut self, what: &str) -> Result<(String, Span), RantlrError> {
        match &self.peek().kind {
            TokenKind::Ident(name) => {
                let name = name.clone();
                let span = self.peek().span;
                self.bump();
                Ok((name, span))
            }
            // Allow builtins as names? No — grammar/rule/token names are Idents.
            TokenKind::Builtin(b) => {
                // Token names like `Number` as rule names are rare; reject clearly.
                let span = self.peek().span;
                Err(self.err_at(
                    span,
                    format!(
                        "expected {what}, found built-in type `{}`",
                        b.as_str()
                    ),
                    Some("built-in types are used on the right-hand side of `token Name = ...`"),
                ))
            }
            _ => Err(self.unexpected(&format!("expected {what}"))),
        }
    }

    fn unexpected(&self, message: &str) -> RantlrError {
        let tok = self.peek();
        let found = describe_token(&tok.kind);
        self.err_at(
            tok.span,
            format!("{message}, found {found}"),
            None,
        )
    }

    fn err_at(
        &self,
        span: Span,
        message: impl Into<String>,
        help: Option<&str>,
    ) -> RantlrError {
        let mut diag = Diagnostic::error(DiagnosticKind::ParseError, message, span);
        if let Some(help) = help {
            diag = diag.with_help(help);
        }
        RantlrError::from_diagnostic(self.source, diag)
    }
}

fn describe_token(kind: &TokenKind) -> String {
    match kind {
        TokenKind::Eof => "end of file".into(),
        TokenKind::Keyword(k) => format!("`{}`", k.as_str()),
        TokenKind::Builtin(b) => format!("built-in `{}`", b.as_str()),
        TokenKind::Ident(s) => format!("identifier `{s}`"),
        TokenKind::String(s) => format!("string {s:?}"),
        TokenKind::RawString(s) => format!("raw string {s:?}"),
        TokenKind::Integer(n) => format!("integer `{n}`"),
        TokenKind::LBrace => "`{`".into(),
        TokenKind::RBrace => "`}`".into(),
        TokenKind::LParen => "`(`".into(),
        TokenKind::RParen => "`)`".into(),
        TokenKind::LBracket => "`[`".into(),
        TokenKind::RBracket => "`]`".into(),
        TokenKind::Pipe => "`|`".into(),
        TokenKind::Comma => "`,`".into(),
        TokenKind::Semi => "`;`".into(),
        TokenKind::Colon => "`:`".into(),
        TokenKind::Eq => "`=`".into(),
        TokenKind::DotDot => "`..`".into(),
        TokenKind::Arrow => "`->`".into(),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::ast::{GrammarItem, TokenBody};
    use crate::token::BuiltinType;

    #[test]
    fn parses_calculator_example() {
        let src = include_str!("../testdata/calculator.gr");
        let g = parse(src).expect("parse calculator.gr");
        assert_eq!(g.name, "Calculator");

        let rules: Vec<_> = g
            .items
            .iter()
            .filter_map(|i| match i {
                GrammarItem::Rule(r) => Some(r.name.as_str()),
                _ => None,
            })
            .collect();
        assert_eq!(rules, ["prog", "expr", "term", "factor"]);

        let tokens: Vec<_> = g
            .items
            .iter()
            .filter_map(|i| match i {
                GrammarItem::Token(t) => Some((t.name.as_str(), t.skip, &t.body)),
                _ => None,
            })
            .collect();
        assert!(matches!(
            tokens[0],
            ("Num", false, TokenBody::Builtin(BuiltinType::Number))
        ));
        assert!(tokens.iter().any(|(n, skip, _)| *n == "Ws" && *skip));

        let examples = g
            .items
            .iter()
            .filter(|i| matches!(i, GrammarItem::Example(_)))
            .count();
        assert_eq!(examples, 2);
    }

    #[test]
    fn parses_match_repeat_optional() {
        let src = r#"
            grammar Mini;
            token N = Number;
            rule items {
                optional { item }
                repeat(0..) { "," item }
            }
            rule item {
                match N | "x" | ("(" N ")")
            }
        "#;
        let g = parse(src).expect("parse");
        let rule = g
            .items
            .iter()
            .find_map(|i| match i {
                GrammarItem::Rule(r) if r.name == "items" => Some(r),
                _ => None,
            })
            .unwrap();

        match &rule.body {
            Expr::Seq { items } => {
                assert!(matches!(items[0], Expr::Optional { .. }));
                assert!(matches!(
                    items[1],
                    Expr::Repeat {
                        min: Some(0),
                        max: None,
                        ..
                    }
                ));
            }
            other => panic!("expected Seq, got {other:?}"),
        }
    }

    #[test]
    fn parse_error_includes_snippet() {
        let src = "grammar X;\nrule bad {\n";
        let err = parse(src).unwrap_err();
        assert_eq!(err.kind, crate::error::ErrorKind::Parse);
        assert!(err.snippet.contains("|"));
        assert!(err.snippet.contains("^"));
        assert!(err.line >= 2);
    }
}