metrale_grammar/earley/
parser_api.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// EarleyParser — history, rollback, push/reset API.
4// Split out of `parser.rs` to keep each file under the 250-line cap.
5// Port of `PopLastStates`, `PushStateAndExpand`, `PushOneStateToCheck`,
6// `Reset` and `ExpandAndEnqueueUnexpandedState` from
7// `cpp/earley_parser.{h,cc}`.
8
9use super::parser::EarleyParser;
10use super::state::{NO_PREV_INPUT_POS, ParserState};
11
12impl EarleyParser {
13    /// Remove the last `count` input positions — the rollback used by
14    /// the matcher to undo speculatively-consumed tokens. Advancing
15    /// `count` bytes then `pop_last_states(count)` restores the exact
16    /// prior state.
17    ///
18    /// Panics if `count` would empty the history (the first step is the
19    /// initial state and must remain — matches the C++ `FATAL` check).
20    pub fn pop_last_states(&mut self, count: usize) {
21        self.stop_token_is_accepted = false;
22        assert!(
23            (count as i32) < self.completable.len(),
24            "cannot pop {count} states: only {} recorded",
25            self.completable.len()
26        );
27        // CSR rollback: dropping the last `count` rows is an O(count)
28        // offset truncation — `indptr` shrinks and `data` is cut at the
29        // new last offset. Restores the exact prior state.
30        self.completable.pop_rows(count as i32);
31        self.is_completed.truncate(self.is_completed.len() - count);
32        self.scanable_history.pop_rows(count as i32);
33    }
34
35    /// Push `state` into the parser and run predict/complete on it,
36    /// recording the resulting scanable states as a new input position.
37    pub fn push_state_and_expand(&mut self, state: ParserState) {
38        self.queue.clear_visited();
39        self.accept_stop_token = false;
40        self.to_be_added.clear();
41
42        if !self.expand_and_enqueue_unexpanded(state) {
43            self.queue.enqueue(state);
44        }
45        self.completable.push_row(&[]);
46        while let Some(state) = self.queue.pop() {
47            let (scanable, completable) = self.predict(state);
48            if completable {
49                self.complete(state);
50            }
51            if scanable {
52                self.to_be_added.push(state);
53            }
54        }
55        self.is_completed.push(self.accept_stop_token);
56        // ZapFormat dead-state pruning — see `advance` / `prune.rs`.
57        self.productivity.prune(&mut self.to_be_added);
58        let added = std::mem::take(&mut self.to_be_added);
59        self.scanable_history.push_row_owned(added);
60    }
61
62    /// Push one state as an extra history step that only checks whether
63    /// it can accept a token — used by the matcher to probe a candidate
64    /// without running prediction/completion. Pop it with
65    /// `pop_last_states(1)`.
66    pub fn push_one_state_to_check(&mut self, state: ParserState) {
67        self.completable.push_row(&[]);
68        self.is_completed
69            .push(*self.is_completed.last().unwrap_or(&false));
70        self.scanable_history.push_row(&[state]);
71    }
72
73    /// Reset the parser to a fresh parse of the grammar's root rule.
74    pub fn reset(&mut self) {
75        self.completable = Default::default();
76        self.scanable_history = Default::default();
77        self.is_completed.clear();
78        self.stop_token_is_accepted = false;
79        debug_assert!(self.queue.is_empty());
80        let root = Self::root_initial_state(&self.grammar);
81        self.push_state_and_expand(root);
82    }
83
84    /// Handle an unexpanded initial state: enqueue the rule-body FSM
85    /// start node. Returns true when `state` was unexpanded.
86    /// Port of `ExpandAndEnqueueUnexpandedState`.
87    pub(crate) fn expand_and_enqueue_unexpanded(&mut self, state: ParserState) -> bool {
88        if !state.is_unexpanded() {
89            return false;
90        }
91        let body_id = self.grammar.rule(state.rule_id).body_expr_id;
92        let fsm = self.grammar.per_rule_fsms[state.rule_id as usize]
93            .as_ref()
94            .expect("unexpanded rule must have a per-rule FSM");
95        self.queue.enqueue(ParserState::new(
96            state.rule_id,
97            body_id,
98            fsm.start() as i32,
99            NO_PREV_INPUT_POS,
100            0,
101        ));
102        true
103    }
104}
metrale_grammar/earley/parser_api.rs

metrale_grammar/earley/
parser_api.rs
