metrale_grammar/earley/
state.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// ParserState — the Earley item.
4// Port of `struct ParserState` from xgrammar `cpp/earley_parser.h`.
5
6/// A `sequence_id` of this value means the rule has not been expanded
7/// yet (used for the initial state pushed into the parser).
8pub const UNEXPANDED_RULE_START_SEQUENCE_ID: i32 = 128_000;
9
10/// A `rule_start_pos` of this value marks an item as a root of the
11/// parsing stack (no preceding input position).
12pub const NO_PREV_INPUT_POS: i32 = -1;
13
14/// An Earley item: a position inside a rule's body, paired with the
15/// input position the rule was predicted at.
16///
17/// In the grammar a rule is always either a `Choices` of `Sequence`s
18/// (or `EmptyStr`), or a `TagDispatch`. After FSM acceleration the body
19/// is walked as an FSM, so `element_id` doubles as the FSM node id.
20///
21/// Faithful port of the C++ fields:
22/// - `rule_id`        — which rule, or `-1` for the non-FSM body view.
23/// - `sequence_id`    — which choice/sequence (a `GrammarExpr` id).
24/// - `element_id`     — element index in the sequence, or FSM node id.
25/// - `rule_start_pos` — input position the rule was predicted at.
26/// - `sub_element_id` — sub-position inside the current element
27///   (byte index in a `ByteString`, or remaining UTF-8 bytes).
28/// - `repeat_count`   — times a `Repeat` element has matched.
29/// - `partial_codepoint` — UTF-8 codepoint accumulated mid-character.
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
31pub struct ParserState {
32    pub rule_id: i32,
33    pub sequence_id: i32,
34    pub element_id: i32,
35    pub rule_start_pos: i32,
36    pub sub_element_id: i32,
37    pub repeat_count: i32,
38    pub partial_codepoint: i32,
39}
40
41impl ParserState {
42    /// Construct an item. `repeat_count` and `partial_codepoint`
43    /// default to 0 — matching the C++ constructor defaults.
44    pub fn new(
45        rule_id: i32,
46        sequence_id: i32,
47        element_id: i32,
48        rule_start_pos: i32,
49        sub_element_id: i32,
50    ) -> Self {
51        Self {
52            rule_id,
53            sequence_id,
54            element_id,
55            rule_start_pos,
56            sub_element_id,
57            repeat_count: 0,
58            partial_codepoint: 0,
59        }
60    }
61
62    /// Construct an item with an explicit `repeat_count`.
63    pub fn with_repeat(
64        rule_id: i32,
65        sequence_id: i32,
66        element_id: i32,
67        rule_start_pos: i32,
68        sub_element_id: i32,
69        repeat_count: i32,
70    ) -> Self {
71        Self {
72            rule_id,
73            sequence_id,
74            element_id,
75            rule_start_pos,
76            sub_element_id,
77            repeat_count,
78            partial_codepoint: 0,
79        }
80    }
81
82    /// The invalid sentinel item (`sequence_id == -1`).
83    pub fn invalid() -> Self {
84        Self::new(-1, -1, -1, -1, -1)
85    }
86
87    /// True if this is the invalid sentinel.
88    pub fn is_invalid(&self) -> bool {
89        self.sequence_id == -1
90    }
91
92    /// True if this item is the root of its parsing stack.
93    pub fn is_root(&self) -> bool {
94        self.rule_start_pos == NO_PREV_INPUT_POS
95    }
96
97    /// True if the rule still needs expansion before parsing.
98    pub fn is_unexpanded(&self) -> bool {
99        self.sequence_id == UNEXPANDED_RULE_START_SEQUENCE_ID
100    }
101}
102
103/// The C++ uses two equality notions; we model the parsing one as
104/// `PartialEq` (all fields). The cache notion ignores `rule_start_pos`
105/// and `repeat_count` — see [`cache_key`].
106///
107/// `cache_key` returns the tuple the C++ `StateHashForCache` /
108/// `StateEqualForParsing`-minus-position uses to deduplicate states
109/// when computing the acceptable-token mask. Consumed by the W6
110/// `GrammarMatcher` token-mask cache.
111#[allow(dead_code)]
112pub fn cache_key(s: &ParserState) -> (i32, i32, i32, i32) {
113    (s.rule_id, s.sequence_id, s.element_id, s.sub_element_id)
114}
115
116#[cfg(test)]
117mod tests {
118    use super::*;
119
120    #[test]
121    fn invalid_sentinel() {
122        let s = ParserState::invalid();
123        assert!(s.is_invalid());
124        assert!(!ParserState::new(0, 0, 0, 0, 0).is_invalid());
125    }
126
127    #[test]
128    fn root_detection() {
129        assert!(ParserState::new(0, 0, 0, NO_PREV_INPUT_POS, 0).is_root());
130        assert!(!ParserState::new(0, 0, 0, 3, 0).is_root());
131    }
132
133    #[test]
134    fn unexpanded_detection() {
135        let s = ParserState::new(
136            0,
137            UNEXPANDED_RULE_START_SEQUENCE_ID,
138            0,
139            NO_PREV_INPUT_POS,
140            0,
141        );
142        assert!(s.is_unexpanded());
143        assert!(!ParserState::new(0, 5, 0, 0, 0).is_unexpanded());
144    }
145
146    #[test]
147    fn cache_key_ignores_position_and_repeat() {
148        let a = ParserState::with_repeat(1, 2, 3, 10, 4, 5);
149        let b = ParserState::with_repeat(1, 2, 3, 99, 4, 7);
150        assert_eq!(cache_key(&a), cache_key(&b));
151        assert_ne!(a, b);
152    }
153}
metrale_grammar/earley/state.rs

metrale_grammar/earley/
state.rs
