mpl 0.3.0

//! Static-codegen runtime for high-performance parsers.
//!
//! This module is the runtime that the [`FastParse`](../../mpl_macro/derive.FastParse.html)
//! derive in `mpl-macro` targets. It is also a small, public API — you
//! can write a parser by hand against the same primitives if you want
//! more control than the derive offers, or if your input is not a byte
//! slice.
//!
//! # Generated parser shape
//!
//! Each grammar variable becomes one Rust function with a uniform
//! signature:
//!
//! ```ignore
//! fn parse_<rule><S: ParseState, const EMIT: bool>(
//!     state: &mut S, pos: u32,
//! ) -> Result<u32, ()>;
//! ```
//!
//! On success it returns `Ok(end_position)`; on failure `Err(())`. When
//! `EMIT == true` it pushes [`Token::Start`] before its body and
//! [`Token::End`] on success, rewinding the buffer via
//! [`ParseState::truncate`] on failure. When `EMIT == false` (recognition
//! mode) every token write is elided at compile time.
//!
//! # State types
//!
//! - [`CheckState`] — input + furthest position only (two machine words).
//!   Used by the recognition path. Matches peg's `(__input, __pos) ->
//!   end_pos` calling convention.
//! - [`ParserState`] — full state with token buffer, bump arena slot,
//!   and seed-growing memo. Used by `fast_parse` and `fast_recognize`.
//!
//! Both implement [`ParseState`] so generated rule fns can be
//! instantiated over either.
//!
//! # AST output
//!
//! The flat token buffer is Sampson-style — no nested `Box`es, just a
//! single `Vec<Token>` whose entries reference each other by index.
//! Walk it via [`ParseTree`], which exposes `Pair` / `Leaf` /
//! `NodeView` / `Children` iterators with span ranges and parent /
//! child traversal — directly comparable to pest's `Pairs` API.
//!
//! # Left recursion
//!
//! Direct left recursion (`R = R X / Y`) is handled by Squirrel-style
//! position-only seed-growing through the [`LrMemoEntry`] memo carried
//! on every `ParseState`. The memo is populated lazily and only by
//! rules `mpl-macro` flagged as left-recursive at compile time, so
//! parsers without LR rules pay zero cost.
//!
//! See the project [README] and [CHANGELOG] for end-to-end examples
//! and benchmark numbers.
//!
//! [README]: https://github.com/kurotakazuki/mpl/blob/main/README.md
//! [CHANGELOG]: https://github.com/kurotakazuki/mpl/blob/main/CHANGELOG.md

pub use bumpalo;
use bumpalo::Bump;

/// One parse-tree token. Internal nodes are bracketed by a matching
/// `Start`/`End` pair; terminal/metasymbol matches are stored as `Leaf`.
///
/// `kind` is grammar-specific: each parser assigns its own integer ids to
/// variables and terminal categories.
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum Token {
    /// Opening marker of a successful rule match.
    ///
    /// `pos` is the input position where matching started. The matching
    /// `End`'s index is not stored on the `Start` — readers walk forward
    /// and use the `start_idx` back-pointer on `End` to associate the pair.
    Start { kind: u32, pos: u32 },
    /// Closing marker of a successful rule match.
    ///
    /// `pos` is the end input position (exclusive). `start_idx` is the
    /// index of the matching `Start` in [`ParserState::tokens`].
    End { kind: u32, pos: u32, start_idx: u32 },
    /// A terminal or metasymbol match.
    Leaf { kind: u32, start: u32, end: u32 },
}

/// Mutable parser state shuttled between the generated `parse_<rule>` fns.
///
/// `'a` is the lifetime of the input slice. The optional bump arena (when
/// constructed via [`new_in`](Self::new_in)) shares the same lifetime.
pub struct ParserState<'a> {
    pub input: &'a [u8],
    pub tokens: Vec<Token>,
    /// Optional bump arena for memoising backends to allocate per-rule
    /// tables in. Held by reference so the caller controls its lifetime.
    pub arena: Option<&'a Bump>,
    /// The furthest input position any rule reached. Used for error reporting.
    pub furthest: u32,
    /// Per-rule seed-growing memo for left-recursive rules. Empty unless
    /// the generated parser actually contains LR rules.
    pub lr_memo: std::collections::HashMap<(u32, u32), LrMemoEntry>,
}

impl<'a> ParserState<'a> {
    /// Plain constructor, no arena. Recommended default for parsers
    /// without memoisation.
    ///
    /// The initial capacity is sized for ~16 tokens per input byte —
    /// roughly what a deeply-nested expression grammar like BubFns
    /// emits. Going higher pre-allocates more than we need and slows
    /// the per-call malloc; sub-16 multipliers force a single growth
    /// re-alloc on bub-style inputs. 16 hits the sweet spot in practice.
    #[inline]
    pub fn new(input: &'a [u8]) -> Self {
        let cap = input.len().saturating_mul(16).max(64);
        Self {
            input,
            tokens: Vec::with_capacity(cap),
            arena: None,
            furthest: 0,
            lr_memo: std::collections::HashMap::new(),
        }
    }

    /// Constructor for recognition-only / "check mode" parses where the
    /// generated rule fns are instantiated with `EMIT = false`. The token
    /// buffer is never written to, so we skip the up-front allocation —
    /// useful for benchmarks that compare against `peg`-style parsers
    /// that return only `bool` / `()`.
    #[inline]
    pub fn new_check(input: &'a [u8]) -> Self {
        Self {
            input,
            tokens: Vec::new(),
            arena: None,
            furthest: 0,
            lr_memo: std::collections::HashMap::new(),
        }
    }

    /// Construct a parser state with access to a bump arena. Memoising
    /// backends can allocate per-rule cache tables in the arena and reset
    /// it between parses for amortised allocation.
    #[inline]
    pub fn new_in(input: &'a [u8], arena: &'a Bump) -> Self {
        let cap = input.len().saturating_mul(16).max(64);
        Self {
            input,
            tokens: Vec::with_capacity(cap),
            arena: Some(arena),
            furthest: 0,
            lr_memo: std::collections::HashMap::new(),
        }
    }

    #[inline(always)]
    pub fn checkpoint(&self) -> usize {
        self.tokens.len()
    }

    /// Drop tokens beyond `checkpoint`. Cheap for `Copy` element types
    /// (just resets the length).
    #[inline(always)]
    pub fn truncate(&mut self, checkpoint: usize) {
        self.tokens.truncate(checkpoint);
    }

    /// Append a token without re-checking capacity. The caller has
    /// already ensured `tokens.len() < tokens.capacity()`. We rely on
    /// [`new`](Self::new) and [`new_in`](Self::new_in) sizing the buffer
    /// for ~16 tokens per input byte; deeply-nested inputs that exceed
    /// that fall back to [`Vec::push`] via the safe wrappers below.
    ///
    /// # Safety
    /// `self.tokens.len() < self.tokens.capacity()` must hold.
    #[inline(always)]
    unsafe fn push_unchecked(&mut self, t: Token) {
        let len = self.tokens.len();
        debug_assert!(len < self.tokens.capacity());
        let ptr = self.tokens.as_mut_ptr().add(len);
        core::ptr::write(ptr, t);
        self.tokens.set_len(len + 1);
    }

    /// Append a token, growing the buffer if needed. The fast wrappers
    /// (`push_start`/`push_end`/`push_leaf`) call this; `unsafe` paths
    /// can use [`push_unchecked`](Self::push_unchecked) directly.
    #[inline(always)]
    fn push_safe(&mut self, t: Token) {
        if self.tokens.len() < self.tokens.capacity() {
            // SAFETY: capacity check above.
            unsafe { self.push_unchecked(t) }
        } else {
            self.tokens.push(t);
        }
    }

    #[inline(always)]
    pub fn push_start(&mut self, kind: u32, pos: u32) -> u32 {
        let idx = self.tokens.len() as u32;
        self.push_safe(Token::Start { kind, pos });
        idx
    }

    #[inline(always)]
    pub fn push_end(&mut self, kind: u32, pos: u32, start_idx: u32) {
        self.push_safe(Token::End { kind, pos, start_idx });
    }

    #[inline(always)]
    pub fn push_leaf(&mut self, kind: u32, start: u32, end: u32) {
        self.push_safe(Token::Leaf { kind, start, end });
    }

    /// Update the furthest-reached position, used for error reporting on
    /// failed terminal matches. Marked `#[cold]` so the no-update fast
    /// path stays in the inlined caller.
    #[inline(always)]
    pub fn note_failure_at(&mut self, pos: u32) {
        if pos > self.furthest {
            self.furthest = pos;
        }
    }
}

// =========================================================================
// AST view: typed navigation over the flat token buffer
// =========================================================================

/// Borrowing view of a successful parse: token buffer plus the input slice.
///
/// Construct via [`ParseTree::new`]; navigate via [`root`](Self::root).
pub struct ParseTree<'a> {
    tokens: &'a [Token],
    input: &'a [u8],
}

impl<'a> ParseTree<'a> {
    #[inline]
    pub fn new(tokens: &'a [Token], input: &'a [u8]) -> Self {
        Self { tokens, input }
    }

    pub fn tokens(&self) -> &'a [Token] {
        self.tokens
    }

    pub fn input(&self) -> &'a [u8] {
        self.input
    }

    /// First node in the buffer. For grammars whose start rule succeeds
    /// via the first choice this is a [`Pair`] wrapping the whole match.
    /// For start rules whose second choice is a bare terminal (mpl
    /// returns the terminal directly without wrapping), this is a [`Leaf`].
    pub fn root(&self) -> Option<NodeView<'_>> {
        node_view_at(self.tokens, self.input, 0)
    }
}

/// One node in the parse tree — either a non-terminal `Pair` or a
/// terminal/metasymbol `Leaf`.
#[derive(Clone, Copy)]
pub enum NodeView<'a> {
    Pair(Pair<'a>),
    Leaf(Leaf<'a>),
}

impl<'a> NodeView<'a> {
    pub fn kind(&self) -> u32 {
        match self {
            NodeView::Pair(p) => p.kind(),
            NodeView::Leaf(l) => l.kind(),
        }
    }

    pub fn span(&self) -> (u32, u32) {
        match self {
            NodeView::Pair(p) => p.span(),
            NodeView::Leaf(l) => l.span(),
        }
    }

    pub fn text(&self) -> &'a [u8] {
        match self {
            NodeView::Pair(p) => p.text(),
            NodeView::Leaf(l) => l.text(),
        }
    }
}

/// View of a non-terminal subtree, bounded by a matching `Start`/`End` pair.
#[derive(Clone, Copy)]
pub struct Pair<'a> {
    tokens: &'a [Token],
    input: &'a [u8],
    start_idx: usize,
    end_idx: usize,
}

impl<'a> Pair<'a> {
    pub fn kind(&self) -> u32 {
        match self.tokens[self.start_idx] {
            Token::Start { kind, .. } => kind,
            _ => unreachable!("Pair start_idx must point at a Start token"),
        }
    }

    pub fn span(&self) -> (u32, u32) {
        let start = match self.tokens[self.start_idx] {
            Token::Start { pos, .. } => pos,
            _ => unreachable!(),
        };
        let end = match self.tokens[self.end_idx] {
            Token::End { pos, .. } => pos,
            _ => unreachable!(),
        };
        (start, end)
    }

    pub fn text(&self) -> &'a [u8] {
        let (s, e) = self.span();
        &self.input[s as usize..e as usize]
    }

    pub fn children(&self) -> Children<'a> {
        Children {
            tokens: self.tokens,
            input: self.input,
            cursor: self.start_idx + 1,
            end: self.end_idx,
        }
    }
}

/// View of a leaf (terminal / metasymbol) match.
#[derive(Clone, Copy)]
pub struct Leaf<'a> {
    tokens: &'a [Token],
    input: &'a [u8],
    idx: usize,
}

impl<'a> Leaf<'a> {
    pub fn kind(&self) -> u32 {
        match self.tokens[self.idx] {
            Token::Leaf { kind, .. } => kind,
            _ => unreachable!(),
        }
    }

    pub fn span(&self) -> (u32, u32) {
        match self.tokens[self.idx] {
            Token::Leaf { start, end, .. } => (start, end),
            _ => unreachable!(),
        }
    }

    pub fn text(&self) -> &'a [u8] {
        let (s, e) = self.span();
        &self.input[s as usize..e as usize]
    }
}

/// Iterator over the immediate children of a [`Pair`].
pub struct Children<'a> {
    tokens: &'a [Token],
    input: &'a [u8],
    cursor: usize,
    end: usize, // index of the matching End token (exclusive boundary)
}

impl<'a> Iterator for Children<'a> {
    type Item = NodeView<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.cursor >= self.end {
            return None;
        }
        match self.tokens[self.cursor] {
            Token::Leaf { .. } => {
                let n = NodeView::Leaf(Leaf {
                    tokens: self.tokens,
                    input: self.input,
                    idx: self.cursor,
                });
                self.cursor += 1;
                Some(n)
            }
            Token::Start { .. } => {
                let s = self.cursor;
                let e = find_matching_end(self.tokens, s);
                let n = NodeView::Pair(Pair {
                    tokens: self.tokens,
                    input: self.input,
                    start_idx: s,
                    end_idx: e,
                });
                self.cursor = e + 1;
                Some(n)
            }
            Token::End { .. } => None,
        }
    }
}

fn find_matching_end(tokens: &[Token], start_idx: usize) -> usize {
    let mut depth: u32 = 1;
    let mut i = start_idx + 1;
    while i < tokens.len() {
        match tokens[i] {
            Token::Start { .. } => depth += 1,
            Token::End { .. } => {
                depth -= 1;
                if depth == 0 {
                    return i;
                }
            }
            Token::Leaf { .. } => {}
        }
        i += 1;
    }
    panic!("token buffer unbalanced: no matching End for Start at {start_idx}");
}

fn node_view_at<'a>(tokens: &'a [Token], input: &'a [u8], idx: usize) -> Option<NodeView<'a>> {
    if idx >= tokens.len() {
        return None;
    }
    match tokens[idx] {
        Token::Start { .. } => {
            let e = find_matching_end(tokens, idx);
            Some(NodeView::Pair(Pair {
                tokens,
                input,
                start_idx: idx,
                end_idx: e,
            }))
        }
        Token::Leaf { .. } => Some(NodeView::Leaf(Leaf {
            tokens,
            input,
            idx,
        })),
        Token::End { .. } => None,
    }
}

// =========================================================================
// State abstraction: ParseState trait + thin CheckState for EMIT=false.
// =========================================================================

/// Position-only seed-growing memo entry for left-recursive rules in
/// FastParse-generated code. Mirrors [`SquirrelRecEntry`](crate::parser::SquirrelRecEntry)
/// but for the static-codegen path: end positions only, no AST.
#[derive(Copy, Clone, Debug)]
pub enum LrMemoEntry {
    InProgress { seed: Option<u32> },
    Done { result: Option<u32> },
}

/// Error returned when a `FastParse`-generated parser fails. Holds the
/// furthest input position any rule reached during recognition — by
/// PEG/TDPL convention this is also the most informative position to
/// point at in error messages.
///
/// Use [`row_col`](Self::row_col) to convert the byte offset into a
/// 1-based `(line, column)` for human-friendly diagnostics.
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct ParseError {
    /// Byte offset into the input where parsing got stuck.
    pub pos: u32,
}

impl ParseError {
    #[inline]
    pub fn at(pos: u32) -> Self {
        Self { pos }
    }

    /// Convert `self.pos` into a 1-based `(line, column)` against the
    /// original input. Lines split on `\n`; column counts bytes since
    /// the previous newline (so wide UTF-8 codepoints contribute their
    /// byte length, not their visual width).
    pub fn row_col(&self, input: &[u8]) -> (u32, u32) {
        let cap = self.pos as usize;
        let stop = cap.min(input.len());
        let mut line: u32 = 1;
        let mut col: u32 = 1;
        for &b in &input[..stop] {
            if b == b'\n' {
                line += 1;
                col = 1;
            } else {
                col += 1;
            }
        }
        (line, col)
    }
}

impl core::fmt::Display for ParseError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        write!(f, "parse error at byte offset {}", self.pos)
    }
}

impl std::error::Error for ParseError {}

/// Operations the generated `parse_<rule>` fns invoke on whatever state
/// they're driving. Implemented by both [`ParserState`] (full token
/// emission) and [`CheckState`] (recognition-only, no token buffer).
///
/// All push/checkpoint/truncate methods return zero or are no-ops on
/// [`CheckState`]; the EMIT=false instantiation of generated code
/// eliminates the calls at compile time anyway, but using a thin state
/// shrinks the parser-state pointer's referent from ~7 to 2 machine
/// words and improves register allocation across the recursive call
/// chain (matches `peg`'s `(__input, __pos) → end_pos` calling convention).
///
/// `lr_memo_*` methods support left-recursive rule codegen
/// (Squirrel-style seed growing). Both [`ParserState`] and
/// [`CheckState`] carry a lazily-populated `HashMap<(rule_kind, pos), LrMemoEntry>`.
pub trait ParseState {
    fn input(&self) -> &[u8];
    fn checkpoint(&self) -> usize;
    fn truncate(&mut self, cp: usize);
    fn push_start(&mut self, kind: u32, pos: u32) -> u32;
    fn push_end(&mut self, kind: u32, pos: u32, start_idx: u32);
    fn push_leaf(&mut self, kind: u32, start: u32, end: u32);
    fn note_failure_at(&mut self, pos: u32);
    /// The furthest input position any rule reached. Used by the
    /// generated entry points to populate [`ParseError::pos`] on failure.
    fn furthest(&self) -> u32;

    fn lr_memo_get(&self, kind: u32, pos: u32) -> Option<LrMemoEntry>;
    fn lr_memo_set(&mut self, kind: u32, pos: u32, entry: LrMemoEntry);
}

impl<'a> ParseState for ParserState<'a> {
    #[inline(always)]
    fn input(&self) -> &[u8] { self.input }
    #[inline(always)]
    fn checkpoint(&self) -> usize { ParserState::checkpoint(self) }
    #[inline(always)]
    fn truncate(&mut self, cp: usize) { ParserState::truncate(self, cp) }
    #[inline(always)]
    fn push_start(&mut self, kind: u32, pos: u32) -> u32 {
        ParserState::push_start(self, kind, pos)
    }
    #[inline(always)]
    fn push_end(&mut self, kind: u32, pos: u32, start_idx: u32) {
        ParserState::push_end(self, kind, pos, start_idx)
    }
    #[inline(always)]
    fn push_leaf(&mut self, kind: u32, start: u32, end: u32) {
        ParserState::push_leaf(self, kind, start, end)
    }
    #[inline(always)]
    fn note_failure_at(&mut self, pos: u32) {
        ParserState::note_failure_at(self, pos)
    }
    #[inline(always)]
    fn furthest(&self) -> u32 {
        self.furthest
    }
    #[inline(always)]
    fn lr_memo_get(&self, kind: u32, pos: u32) -> Option<LrMemoEntry> {
        self.lr_memo.get(&(kind, pos)).copied()
    }
    #[inline(always)]
    fn lr_memo_set(&mut self, kind: u32, pos: u32, entry: LrMemoEntry) {
        self.lr_memo.insert((kind, pos), entry);
    }
}

/// Thin state for recognition-only parsing. Holds the input slice, a
/// u32 furthest-failure tracker, and a lazily-populated seed-growing
/// memo for left-recursive rules. The `lr_memo` HashMap is empty (and
/// therefore essentially free) on parsers without LR rules.
pub struct CheckState<'a> {
    pub input: &'a [u8],
    pub furthest: u32,
    pub lr_memo: std::collections::HashMap<(u32, u32), LrMemoEntry>,
}

impl<'a> CheckState<'a> {
    #[inline]
    pub fn new(input: &'a [u8]) -> Self {
        Self {
            input,
            furthest: 0,
            lr_memo: std::collections::HashMap::new(),
        }
    }
}

impl<'a> ParseState for CheckState<'a> {
    #[inline(always)]
    fn input(&self) -> &[u8] { self.input }
    #[inline(always)]
    fn checkpoint(&self) -> usize { 0 }
    #[inline(always)]
    fn truncate(&mut self, _cp: usize) {}
    #[inline(always)]
    fn push_start(&mut self, _kind: u32, _pos: u32) -> u32 { 0 }
    #[inline(always)]
    fn push_end(&mut self, _kind: u32, _pos: u32, _start_idx: u32) {}
    #[inline(always)]
    fn push_leaf(&mut self, _kind: u32, _start: u32, _end: u32) {}
    #[inline(always)]
    fn note_failure_at(&mut self, pos: u32) {
        if pos > self.furthest {
            self.furthest = pos;
        }
    }
    #[inline(always)]
    fn furthest(&self) -> u32 {
        self.furthest
    }
    #[inline(always)]
    fn lr_memo_get(&self, kind: u32, pos: u32) -> Option<LrMemoEntry> {
        self.lr_memo.get(&(kind, pos)).copied()
    }
    #[inline(always)]
    fn lr_memo_set(&mut self, kind: u32, pos: u32, entry: LrMemoEntry) {
        self.lr_memo.insert((kind, pos), entry);
    }
}

/// Reserved `kind` ids for built-in metasymbols so generated parsers do
/// not collide. User grammars assign their own ids starting from
/// [`USER_BASE`](kind::USER_BASE).
pub mod kind {
    pub const TERMINAL: u32 = 0xFFFF_FF00;
    pub const EMPTY: u32 = 0xFFFF_FF01;
    pub const FAILURE: u32 = 0xFFFF_FF02;
    pub const ANY: u32 = 0xFFFF_FF03;
    pub const ALL: u32 = 0xFFFF_FF04;

    /// First id available to user grammars.
    pub const USER_BASE: u32 = 0;
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn checkpoint_and_truncate_round_trip() {
        let mut state = ParserState::new(b"hello");
        let cp = state.checkpoint();
        state.push_leaf(kind::TERMINAL, 0, 1);
        state.push_leaf(kind::TERMINAL, 1, 2);
        assert_eq!(state.tokens.len(), 2);
        state.truncate(cp);
        assert_eq!(state.tokens.len(), 0);
    }

    #[test]
    fn start_end_pair_links_back() {
        let mut state = ParserState::new(b"x");
        let s = state.push_start(7, 0);
        state.push_leaf(kind::TERMINAL, 0, 1);
        state.push_end(7, 1, s);

        match state.tokens[2] {
            Token::End { start_idx, .. } => assert_eq!(start_idx, 0),
            _ => panic!("expected End token"),
        }
    }

    #[test]
    fn state_with_arena_holds_reference() {
        let arena = Bump::new();
        let state = ParserState::new_in(b"x", &arena);
        assert!(state.arena.is_some());
    }

    #[test]
    fn ast_view_walks_a_simple_tree() {
        // Hand-build a buffer for: `Root [Leaf 'x', Pair Inner [Leaf 'y']]`.
        let tokens = vec![
            Token::Start { kind: 1, pos: 0 },         // Root
            Token::Leaf { kind: 100, start: 0, end: 1 }, // 'x'
            Token::Start { kind: 2, pos: 1 },         // Inner
            Token::Leaf { kind: 100, start: 1, end: 2 }, // 'y'
            Token::End { kind: 2, pos: 2, start_idx: 2 },
            Token::End { kind: 1, pos: 2, start_idx: 0 },
        ];
        let input = b"xy";
        let tree = ParseTree::new(&tokens, input);
        let root = tree.root().expect("root");

        let pair = match root {
            NodeView::Pair(p) => p,
            _ => panic!("expected Pair"),
        };
        assert_eq!(pair.kind(), 1);
        assert_eq!(pair.span(), (0, 2));
        assert_eq!(pair.text(), b"xy");

        let mut children = pair.children();
        let first = children.next().expect("first child");
        assert_eq!(first.kind(), 100);
        assert_eq!(first.text(), b"x");

        let second = match children.next().expect("second child") {
            NodeView::Pair(p) => p,
            _ => panic!("expected nested Pair"),
        };
        assert_eq!(second.kind(), 2);
        assert_eq!(second.text(), b"y");
        assert_eq!(second.children().count(), 1);

        assert!(children.next().is_none());
    }
}