brink_syntax_native/parser/

mod.rs

mod annotation;
mod binding;
mod block;
mod choice;
mod content;
mod control_flow;
mod decl;
mod divert;
mod doc_comment;
mod element;
mod expr;
mod family;
mod markup;
mod source_file;
mod stmt;
#[cfg(test)]
mod tests;
mod types;

use crate::SyntaxKind::{self, ERROR};
use crate::lexer;
use rowan::GreenNode;

/// Result of parsing a `.brink` source file.
///
/// `PartialEq` compares the green tree structurally (rowan `GreenNode`
/// equality is content-based) plus the error list.
#[derive(Clone, PartialEq, Eq)]
pub struct Parse {
    green: GreenNode,
    errors: Vec<ParseError>,
}

impl Parse {
    /// The root green node of the lossless CST.
    #[must_use]
    pub fn green(&self) -> &GreenNode {
        &self.green
    }

    /// The root syntax node (typed wrapper around the green tree).
    #[must_use]
    pub fn syntax(&self) -> crate::SyntaxNode {
        crate::SyntaxNode::new_root(self.green.clone())
    }

    /// Parse errors encountered.
    #[must_use]
    pub fn errors(&self) -> &[ParseError] {
        &self.errors
    }
}

/// A parse diagnostic's severity — whether it blocks compilation.
///
/// This crate has no `brink-ir` dependency (peer-crate rule, `lib.rs`'s
/// doc comment), so this stays a small local enum rather than reusing
/// `brink_ir::Severity` — consumers (`brink-db`'s `lower_native_file`) map
/// it onto the appropriate `DiagnosticCode` (`E037` for `Error`, a
/// dedicated Warning-severity code for `Warning`) at the seam where the two
/// diagnostic vocabularies meet.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ParseSeverity {
    /// Malformed source — blocks compilation.
    Error,
    /// Advisory only — surfaced to the user but never blocks compilation
    /// (issue #1263: `<-` outside a choice point *can* be literal dialogue,
    /// so a hard error would be wrong).
    Warning,
}

/// A parse error with a message and the source range it points at.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ParseError {
    pub message: String,
    /// Byte range in the source that the error points at.
    pub range: rowan::TextRange,
    /// Whether this diagnostic blocks compilation. Defaults to `Error` for
    /// every existing diagnostic (`Parser::error`); only `Parser::warning`
    /// produces `Warning`.
    pub severity: ParseSeverity,
}

/// Parse a `.brink` source string into a lossless CST.
#[must_use]
pub fn parse(source: &str) -> Parse {
    let raw_tokens = lexer::lex(source);
    let mut p = Parser::new(&raw_tokens);
    source_file::source_file(&mut p);
    let green = p.builder.finish();
    Parse {
        green,
        errors: p.errors,
    }
}

/// Parse with a shared [`rowan::NodeCache`] for green-node interning.
pub fn parse_with_cache(source: &str, cache: &mut rowan::NodeCache) -> Parse {
    let raw_tokens = lexer::lex(source);
    let mut p = Parser::with_cache(&raw_tokens, cache);
    source_file::source_file(&mut p);
    let green = p.builder.finish();
    Parse {
        green,
        errors: p.errors,
    }
}

// ── Parser internals ────────────────────────────────────────────────

/// Maximum nesting depth for recursive grammar rules (blocks, expressions,
/// parenthesized groups). Prevents stack overflow and superlinear parse
/// time on pathological/adversarial input. 256 matches Rust's default
/// `recursion_limit`.
const MAX_DEPTH: u32 = 256;

/// The parser. Holds a token stream and a `GreenNodeBuilder`.
pub(crate) struct Parser<'t, 'c> {
    tokens: &'t [(SyntaxKind, &'t str)],
    pos: usize,
    depth: u32,
    /// Pre-computed non-trivia token indices. `non_trivia[k]` is the raw
    /// token index of the k-th non-trivia token. Enables O(1) `nth(n)`
    /// instead of an O(n) rescan per lookahead — this parser calls `nth`
    /// in hot loops (block/content dispatch), so an un-indexed scan would
    /// make parsing a large file superlinear.
    non_trivia: Vec<usize>,
    builder: rowan::GreenNodeBuilder<'c>,
    errors: Vec<ParseError>,
    /// When `true`, a `PATH` followed by `{` is **not** read as a
    /// `TypeName { … }` construction literal (B5, issue #1464) — the brace
    /// belongs to the enclosing construct's body instead.
    ///
    /// Set only in the four head positions where an expression is directly
    /// followed by a block opener and the two readings are genuinely
    /// ambiguous: `if`/`while`/`for … in` heads (`parser::control_flow`)
    /// and the content-ground `{if …}`/`{match …}` heads
    /// (`parser::family::conditional_body`). Rust's own
    /// `no-struct-literal` restriction is the precedent; `(…)`, an
    /// argument list and a construction literal's own entry list all clear
    /// it again, so `if (Point { x: 1 }) == p { … }` still parses.
    no_construct_literal: bool,
    /// Whether a **cue chain** is currently live at body-item position —
    /// the prose dialect's chain rule (`docs/prose-dialect-spec.md` §3.1:
    /// "chain rules (dialogue is the line after a cue/parenthetical)", the
    /// shipped `brink_ir::dialect` classifier's mechanism promoted to the
    /// grammar). Set by a cue, carried across that cue's parentheticals
    /// and dialogue lines, and cleared by a blank line or any other item
    /// (`dialect.rs`: "blank lines always break a chain").
    ///
    /// Only [`element::at_parenthetical`] consults it, and only to decide
    /// whether a whole-line `( … )` is a parenthetical or an ordinary
    /// content line — so outside a cue chain the G-1 `(label)` spelling
    /// (`content::at_content_label`) is reached exactly as before.
    cue_chain: bool,
}

impl<'t> Parser<'t, 'static> {
    fn new(tokens: &'t [(SyntaxKind, &'t str)]) -> Self {
        let non_trivia = Self::build_non_trivia(tokens);
        Self {
            tokens,
            pos: 0,
            depth: 0,
            non_trivia,
            builder: rowan::GreenNodeBuilder::new(),
            errors: Vec::new(),
            no_construct_literal: false,
            cue_chain: false,
        }
    }
}

impl<'t, 'c> Parser<'t, 'c> {
    fn with_cache(tokens: &'t [(SyntaxKind, &'t str)], cache: &'c mut rowan::NodeCache) -> Self {
        let non_trivia = Self::build_non_trivia(tokens);
        Self {
            tokens,
            pos: 0,
            depth: 0,
            non_trivia,
            builder: rowan::GreenNodeBuilder::with_cache(cache),
            errors: Vec::new(),
            no_construct_literal: false,
            cue_chain: false,
        }
    }

    /// O(n) pre-pass: collect the raw indices of all non-trivia tokens.
    fn build_non_trivia(tokens: &[(SyntaxKind, &str)]) -> Vec<usize> {
        tokens
            .iter()
            .enumerate()
            .filter(|(_, (k, _))| !k.is_trivia())
            .map(|(i, _)| i)
            .collect()
    }

    /// Enter one level of recursive-grammar nesting. Returns `false` (and
    /// records an error) if `MAX_DEPTH` would be exceeded — callers must
    /// bail out without recursing further, still consuming forward
    /// progress via `error_recover`. Every mutually-recursive entry point
    /// (blocks, the annotated-brace family, expressions) pairs this with
    /// `exit_depth` so pathological/adversarial nesting can never blow the
    /// stack (CLAUDE.md: "guard against unbounded growth").
    fn enter_depth(&mut self) -> bool {
        if self.depth >= MAX_DEPTH {
            self.error("maximum nesting depth exceeded".into());
            false
        } else {
            self.depth += 1;
            true
        }
    }

    /// Leave one level entered by `enter_depth`.
    fn exit_depth(&mut self) {
        self.depth -= 1;
    }

    /// Set the [`Self::no_construct_literal`] restriction, returning the
    /// previous value so the caller can restore it — a save/restore pair
    /// rather than a plain `= false` reset, so nested heads (`if a { if b
    /// { … } }`, `{if x: {match y { … }}}`) each unwind to whatever their
    /// own enclosing context was.
    fn set_no_construct_literal(&mut self, value: bool) -> bool {
        std::mem::replace(&mut self.no_construct_literal, value)
    }

    /// Whether a `PATH` at the current position may be followed by a
    /// `TypeName { … }` construction literal (see
    /// [`Self::no_construct_literal`]).
    fn construct_literals_allowed(&self) -> bool {
        !self.no_construct_literal
    }

    /// Set the [`Self::cue_chain`] flag, returning the previous value — a
    /// save/restore pair like [`Self::set_no_construct_literal`], so a
    /// nested body can start a fresh chain and unwind to whatever its
    /// enclosing body was in the middle of.
    fn set_cue_chain(&mut self, value: bool) -> bool {
        std::mem::replace(&mut self.cue_chain, value)
    }

    /// Whether a cue chain is live at the current body-item position (see
    /// [`Self::cue_chain`]).
    fn in_cue_chain(&self) -> bool {
        self.cue_chain
    }

    // ── Lookahead ───────────────────────────────────────────────

    /// The kind of the current token (or `EOF` if past the end).
    fn current(&self) -> SyntaxKind {
        self.nth(0)
    }

    /// Lookahead by `n` tokens, skipping trivia (WHITESPACE, comments).
    /// `nth(0)` returns the current non-trivia token.
    fn nth(&self, n: usize) -> SyntaxKind {
        let start = self.non_trivia.partition_point(|&idx| idx < self.pos);
        let target = start + n;
        if target < self.non_trivia.len() {
            self.tokens[self.non_trivia[target]].0
        } else {
            SyntaxKind::EOF
        }
    }

    /// The source text of the `n`-th non-trivia token ahead (`""` past the
    /// end). The text counterpart of [`Self::nth`], for the handful of
    /// guards that recognize a *specific word* rather than a token kind —
    /// today only the prose dialect's `INT.`/`EXT.` scene-heading prefix
    /// (`parser::element::at_scene_heading`), which is a declared
    /// line-shape pattern, not a reserved keyword.
    fn nth_text(&self, n: usize) -> &'t str {
        let start = self.non_trivia.partition_point(|&idx| idx < self.pos);
        self.non_trivia
            .get(start + n)
            .map_or("", |&idx| self.tokens[idx].1)
    }

    /// True when the `n`-th and `n+1`-th non-trivia tokens ahead are
    /// *directly adjacent* in the source — no whitespace or comment
    /// between them. Used by sigil guards whose spelling is tight by
    /// construction (`@NAME` — a lone `@` followed by a space stays plain
    /// prose, per `SyntaxKind::AT`'s doc comment).
    fn nth_adjacent(&self, n: usize) -> bool {
        let start = self.non_trivia.partition_point(|&idx| idx < self.pos);
        match (
            self.non_trivia.get(start + n),
            self.non_trivia.get(start + n + 1),
        ) {
            (Some(&a), Some(&b)) => b == a + 1,
            _ => false,
        }
    }

    /// Lookahead by `n` tokens WITHOUT skipping trivia.
    fn nth_raw(&self, n: usize) -> SyntaxKind {
        self.tokens
            .get(self.pos + n)
            .map_or(SyntaxKind::EOF, |&(k, _)| k)
    }

    /// Returns `true` if the current non-trivia token matches `kind`.
    fn at(&self, kind: SyntaxKind) -> bool {
        self.current() == kind
    }

    /// Returns `true` if we're at end-of-file.
    fn at_eof(&self) -> bool {
        self.current() == SyntaxKind::EOF
    }

    /// Current position in the raw token stream (for loop-progress checks).
    fn pos(&self) -> usize {
        self.pos
    }

    // ── Consumption ─────────────────────────────────────────────

    /// Emit the current token to the builder and advance.
    fn bump(&mut self) {
        if self.pos < self.tokens.len() {
            let (kind, text) = self.tokens[self.pos];
            self.builder.token(rowan::SyntaxKind(kind as u16), text);
            self.pos += 1;
        }
    }

    /// If the current non-trivia token matches `kind`, eat trivia then bump it.
    /// Returns `true` if consumed.
    fn eat(&mut self, kind: SyntaxKind) -> bool {
        // Flush leading trivia *unconditionally*, before the check — not
        // only on a match. Two correctness properties depend on this:
        // (1) trailing trivia with nothing meaningful after it (a final
        // comment, trailing whitespace at EOF) would otherwise never get
        // flushed into the tree at all, since every loop-continuation
        // check (`at_eof`, `at(R_BRACE)`, …) trivia-skips to decide
        // "nothing left to do" without ever having called `bump` on the
        // trivia itself — found by `proptest_native`'s
        // `arbitrary_garbage_never_panics` (`"#//"` lost its trailing
        // `//`) and `truncated_input_never_panics_and_roundtrips` (a
        // truncated `flow a_a_() ` lost its trailing space). (2) it makes
        // every `eat`/`expect` call site safe to follow with a raw
        // `bump()` for a *different* token regardless of whether pending
        // trivia sat between them — the class of bug this crate's parser
        // tests caught repeatedly during development (e.g. `annotation_arg`
        // bumping a stray space instead of the next `IDENT`).
        self.skip_ws();
        if self.current() == kind {
            self.bump();
            true
        } else {
            false
        }
    }

    /// Expect the current non-trivia token to be `kind`. If it is, eat
    /// trivia and bump. Otherwise, emit an error (no token consumed —
    /// callers that need forward progress on mismatch should follow up
    /// with `error_recover`).
    fn expect(&mut self, kind: SyntaxKind) {
        if !self.eat(kind) {
            self.error(format!("expected {kind:?}, found {:?}", self.current()));
        }
    }

    /// Consume all trivia (`WHITESPACE`, `LINE_COMMENT`, `BLOCK_COMMENT`).
    fn skip_ws(&mut self) {
        while self.pos < self.tokens.len() && self.tokens[self.pos].0.is_trivia() {
            self.bump();
        }
    }

    /// Consume all trivia **and** `NEWLINE` tokens.
    ///
    /// `NEWLINE` is deliberately not trivia (it terminates content
    /// lines/diverts/etc. at body-item position) — but inside an
    /// explicitly bracket/brace-delimited list (param lists, struct
    /// fields, annotation args, `use`-tree lists, match arms, …), a line
    /// break is pure formatting, exactly the case the charter's "whitespace
    /// never load-bearing" ground rule (§2) describes. Every such list
    /// loop calls this instead of `skip_ws` so multi-line lists parse.
    fn skip_ws_and_newlines(&mut self) {
        while self.pos < self.tokens.len()
            && (self.tokens[self.pos].0.is_trivia()
                || self.tokens[self.pos].0 == SyntaxKind::NEWLINE)
        {
            self.bump();
        }
    }

    /// Look at the next significant token, skipping trivia **and**
    /// `NEWLINE` (read-only — does not move `pos`). The lookahead half of
    /// [`Self::skip_ws_and_newlines`]'s policy, for list loops that need to
    /// check a closing delimiter before deciding whether to recurse.
    fn peek_skip_nl(&self) -> SyntaxKind {
        let mut i = self.pos;
        while i < self.tokens.len()
            && (self.tokens[i].0.is_trivia() || self.tokens[i].0 == SyntaxKind::NEWLINE)
        {
            i += 1;
        }
        self.tokens.get(i).map_or(SyntaxKind::EOF, |&(k, _)| k)
    }

    // ── Nodes ───────────────────────────────────────────────────

    /// Start a new CST node.
    fn start_node(&mut self, kind: SyntaxKind) {
        self.builder.start_node(rowan::SyntaxKind(kind as u16));
    }

    /// Start a new CST node at a previously saved checkpoint.
    fn start_node_at(&mut self, checkpoint: rowan::Checkpoint, kind: SyntaxKind) {
        self.builder
            .start_node_at(checkpoint, rowan::SyntaxKind(kind as u16));
    }

    /// Finish the current CST node.
    fn finish_node(&mut self) {
        self.builder.finish_node();
    }

    /// Save the current position as a checkpoint for `start_node_at`.
    fn checkpoint(&self) -> rowan::Checkpoint {
        self.builder.checkpoint()
    }

    // ── Errors ──────────────────────────────────────────────────

    /// Record a parse diagnostic at the current position with the given
    /// severity. Shared implementation for [`Self::error`]/[`Self::warning`].
    fn push_diagnostic(&mut self, message: String, severity: ParseSeverity) {
        let upto = self.pos.min(self.tokens.len());
        let start: usize = self.tokens[..upto].iter().map(|(_, t)| t.len()).sum();
        let len: usize = self.tokens.get(self.pos).map_or(0, |(_, t)| t.len());
        let start = rowan::TextSize::from(u32::try_from(start).unwrap_or(u32::MAX));
        let len = rowan::TextSize::from(u32::try_from(len).unwrap_or(u32::MAX));
        self.errors.push(ParseError {
            message,
            range: rowan::TextRange::at(start, len),
            severity,
        });
    }

    /// Record a parse error at the current position. Blocks compilation
    /// (`ParseSeverity::Error`).
    fn error(&mut self, message: String) {
        self.push_diagnostic(message, ParseSeverity::Error);
    }

    /// Record a warning-severity diagnostic at the current position.
    /// Advisory only — never blocks compilation (`ParseSeverity::Warning`).
    fn warning(&mut self, message: String) {
        self.push_diagnostic(message, ParseSeverity::Warning);
    }

    /// Wrap the current token in an `ERROR` node and advance.
    ///
    /// Used by grammar rules that need to recover from unexpected tokens
    /// without losing the rest of the input. Guarantees forward progress
    /// even at EOF-adjacent malformed input, as long as at least one raw
    /// token remains — callers at the very top (`source_file`) additionally
    /// guard against a zero-progress spin when even that isn't true.
    fn error_recover(&mut self, message: &str) {
        self.error(message.to_owned());
        self.start_node(ERROR);
        if self.pos < self.tokens.len() {
            self.bump();
        }
        self.finish_node();
    }
}