metrale_grammar/grammar/functor/
fsm_builder.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// GrammarFsmBuilder — builds per-rule FSMs for an (optimized) grammar.
4// Port of `GrammarFSMBuilderImpl` from `cpp/grammar_functor.cc`.
5//
6// The W2 FSM agent explicitly deferred grammar-aware FSM construction to
7// the functor wave: this is it. Each rule body (a choices-of-sequences
8// or a TagDispatch) is converted to an `FsmWithStartEnd`, then spliced
9// into one shared `complete_fsm`. `GrammarData::per_rule_fsms[i]` holds
10// a compact view into that shared FSM for rule `i`.
11
12use crate::fsm::{CompactFsmWithStartEnd, Fsm, FsmWithStartEnd};
13use crate::grammar::data::GrammarData;
14use crate::grammar::expr::{GrammarExpr, GrammarExprType};
15
16use super::char_range::{add_character_range, codepoint_to_packed_utf8};
17use super::tag_dispatch_fsm::build_tag_dispatch_fsm;
18
19/// Per-rule FSM construction pass.
20pub struct GrammarFsmBuilder;
21
22impl GrammarFsmBuilder {
23    /// Build `complete_fsm` + `per_rule_fsms` for `grammar` in place.
24    pub fn apply(grammar: &mut GrammarData) {
25        let num_rules = grammar.num_rules();
26        let mut complete = Fsm::with_states(0);
27        // Each entry: the spliced view plus the *sub-FSM's* node/edge
28        // counts captured before splicing — needed so the per-rule
29        // `CompactFsmWithStartEnd` reports the sub-FSM size rather than
30        // the whole `complete_fsm` (upstream commit 58494db, #600).
31        let mut per_rule: Vec<Option<(FsmWithStartEnd, usize, usize)>> =
32            Vec::with_capacity(num_rules as usize);
33
34        for i in 0..num_rules {
35            let body_id = grammar.rule(i).body_expr_id;
36            let body = grammar.expr(body_id);
37            let rule_fsm: Option<FsmWithStartEnd> = if body.kind == GrammarExprType::TagDispatch {
38                build_tag_dispatch_fsm(&grammar.tag_dispatch(body_id))
39            } else {
40                debug_assert_eq!(body.kind, GrammarExprType::Choices);
41                build_choices(&body, grammar)
42            };
43            per_rule.push(rule_fsm.map(|f| {
44                let node_num = f.num_states();
45                let edge_num = f.fsm().num_edges();
46                (splice_into(&mut complete, &f), node_num, edge_num)
47            }));
48        }
49
50        let compact_complete = complete.to_compact();
51        let final_per_rule: Vec<Option<CompactFsmWithStartEnd>> = per_rule
52            .into_iter()
53            .map(|opt| {
54                opt.map(|(view, node_num, edge_num)| {
55                    CompactFsmWithStartEnd::new_view(
56                        compact_complete.clone(),
57                        view.start(),
58                        view.ends().to_vec(),
59                        node_num,
60                        edge_num,
61                    )
62                })
63            })
64            .collect();
65
66        grammar.complete_fsm = compact_complete;
67        grammar.per_rule_fsms = final_per_rule;
68    }
69}
70
71/// Splice `sub` into `complete`, returning a view whose start/ends point
72/// at the spliced-in states.
73fn splice_into(complete: &mut Fsm, sub: &FsmWithStartEnd) -> FsmWithStartEnd {
74    let mapping = complete.add_fsm(sub.fsm());
75    let new_start = mapping[sub.start()];
76    let mut new_ends = vec![false; complete.num_states()];
77    for s in 0..sub.num_states() {
78        if sub.is_end_state(s) {
79            new_ends[mapping[s]] = true;
80        }
81    }
82    FsmWithStartEnd::new(complete.clone(), new_start, new_ends, false)
83}
84
85/// FSM for a `RuleRef` element: a single rule-ref edge.
86pub fn build_rule_ref(expr: &GrammarExpr<'_>) -> FsmWithStartEnd {
87    let mut fsm = FsmWithStartEnd::default();
88    fsm.add_state();
89    fsm.add_state();
90    fsm.set_start_state(0);
91    fsm.add_end_state(1);
92    fsm.fsm_mut().add_rule_edge(0, 1, expr.data[0] as i16);
93    fsm
94}
95
96/// FSM for a `Repeat` element: a single repeat-ref edge.
97pub fn build_repeat(expr: &GrammarExpr<'_>) -> FsmWithStartEnd {
98    let mut fsm = FsmWithStartEnd::default();
99    fsm.add_state();
100    fsm.add_state();
101    fsm.set_start_state(0);
102    fsm.add_end_state(1);
103    fsm.fsm_mut()
104        .add_repeat_edge(0, 1, expr.data[0], expr.data[1], expr.data[2]);
105    fsm
106}
107
108/// FSM for a `ByteString` element: a linear chain of byte edges.
109pub fn build_byte_string(expr: &GrammarExpr<'_>) -> FsmWithStartEnd {
110    let mut fsm = FsmWithStartEnd::default();
111    let mut cur = fsm.add_state();
112    fsm.set_start_state(cur);
113    for &byte in expr.data {
114        let next = fsm.add_state();
115        fsm.fsm_mut().add_edge(cur, next, byte as i16, byte as i16);
116        cur = next;
117    }
118    fsm.add_end_state(cur);
119    fsm
120}
121
122/// FSM for a `CharacterClass` / `CharacterClassStar` element.
123pub fn build_character_class(expr: &GrammarExpr<'_>) -> FsmWithStartEnd {
124    let is_negative = expr.data[0] != 0;
125    if is_negative {
126        return build_negative_character_class(expr);
127    }
128    let mut fsm = FsmWithStartEnd::default();
129    let start = fsm.add_state();
130    fsm.set_start_state(start);
131    let is_star = expr.kind == GrammarExprType::CharacterClassStar;
132    let end = if is_star { start } else { fsm.add_state() };
133    fsm.add_end_state(end);
134    let mut i = 1;
135    while i < expr.data.len() {
136        let lo = codepoint_to_packed_utf8(expr.data[i] as u32);
137        let hi = codepoint_to_packed_utf8(expr.data[i + 1] as u32);
138        add_character_range(&mut fsm, start, end, lo, hi);
139        i += 2;
140    }
141    fsm
142}
143
144/// FSM for a negated character class — the complement of the ASCII set
145/// the class names, plus all multi-byte unicode.
146fn build_negative_character_class(expr: &GrammarExpr<'_>) -> FsmWithStartEnd {
147    let mut char_set = [false; 128];
148    let mut i = 1;
149    while i < expr.data.len() {
150        let lo = expr.data[i];
151        let mut hi = expr.data[i + 1];
152        if hi > 128 {
153            hi = 127;
154        }
155        for j in lo..=hi {
156            if (0..128).contains(&j) {
157                char_set[j as usize] = true;
158            }
159        }
160        i += 2;
161    }
162    let mut fsm = FsmWithStartEnd::default();
163    let start = fsm.add_state();
164    fsm.set_start_state(start);
165    let is_star = expr.kind == GrammarExprType::CharacterClassStar;
166    let end = if is_star { start } else { fsm.add_state() };
167    fsm.add_end_state(end);
168    let mut i = 0;
169    while i < 128 {
170        if !char_set[i] {
171            let mut right = i + 1;
172            while right < 128 && !char_set[right] {
173                right += 1;
174            }
175            fsm.fsm_mut()
176                .add_edge(start, end, i as i16, (right - 1) as i16);
177            i = right;
178        } else {
179            i += 1;
180        }
181    }
182    use super::char_range::{MAX_4B, MIN_2B};
183    add_character_range(&mut fsm, start, end, MIN_2B, MAX_4B);
184    fsm
185}
186
187/// FSM for a normalized `Sequence` (a list of element exprs).
188/// Returns `None` if any element is not FSM-expressible.
189pub fn build_sequence(expr: &GrammarExpr<'_>, grammar: &GrammarData) -> Option<FsmWithStartEnd> {
190    let mut parts: Vec<FsmWithStartEnd> = Vec::new();
191    for &id in expr.data {
192        let e = grammar.expr(id);
193        let part = match e.kind {
194            GrammarExprType::ByteString => build_byte_string(&e),
195            GrammarExprType::RuleRef => build_rule_ref(&e),
196            GrammarExprType::CharacterClass | GrammarExprType::CharacterClassStar => {
197                build_character_class(&e)
198            }
199            GrammarExprType::Repeat => build_repeat(&e),
200            _ => return None,
201        };
202        parts.push(part);
203    }
204    if parts.is_empty() {
205        return Some(empty_fsm());
206    }
207    Some(FsmWithStartEnd::concat(&parts))
208}
209
210/// FSM for a normalized rule body — a `Choices` of `Sequence`s (with an
211/// optional leading `EmptyStr`). Returns `None` if not FSM-expressible.
212pub fn build_choices(expr: &GrammarExpr<'_>, grammar: &GrammarData) -> Option<FsmWithStartEnd> {
213    debug_assert_eq!(expr.kind, GrammarExprType::Choices);
214    let mut fsm_list: Vec<FsmWithStartEnd> = Vec::new();
215    let mut nullable = false;
216    for &id in expr.data {
217        let e = grammar.expr(id);
218        if e.kind == GrammarExprType::EmptyStr {
219            nullable = true;
220            continue;
221        }
222        debug_assert_eq!(e.kind, GrammarExprType::Sequence);
223        fsm_list.push(build_sequence(&e, grammar)?);
224    }
225    if fsm_list.is_empty() {
226        return Some(empty_fsm());
227    }
228    if nullable {
229        fsm_list.push(empty_fsm());
230    }
231    let mut result = FsmWithStartEnd::union(&fsm_list);
232    result = result.simplify_epsilon();
233    result = result.merge_equivalent_successors();
234    // Upstream commit 96ae88b (#616) dropped the `MinimizeDFA` call here:
235    // Hopcroft minimization does not reduce states on these grammars and
236    // scales super-linearly in state count, so it was pure wasted work.
237    Some(result)
238}
239
240/// A one-state FSM accepting only the empty string.
241pub fn empty_fsm() -> FsmWithStartEnd {
242    let mut fsm = FsmWithStartEnd::default();
243    fsm.add_state();
244    fsm.set_start_state(0);
245    fsm.add_end_state(0);
246    fsm
247}
248
249#[cfg(test)]
250#[path = "fsm_builder_tests.rs"]
251mod tests;
metrale_grammar/grammar/functor/fsm_builder.rs

metrale_grammar/grammar/functor/
fsm_builder.rs
