metrale_grammar/fsm/
compact_with_start_end.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// CompactFsmWithStartEnd — the compact-FSM counterpart of
4// FsmWithStartEnd. Split out of `with_start_end.rs` to keep each
5// file under the 250-line cap. Port of `CompactFSMWithStartEnd`
6// from `cpp/fsm.{h,cc}`.
7
8use ahash::AHashSet;
9
10use super::compact::CompactFsm;
11use super::edge::edge_type;
12use super::with_start_end::FsmWithStartEnd;
13
14/// A compact FSM paired with start/accepting states.
15///
16/// `node_num` / `edge_num` record the size of the *logical* FSM this
17/// value represents. For a standalone FSM that equals the backing
18/// `fsm`'s own counts; for a per-rule view spliced into a shared
19/// `complete_fsm`, they record the sub-FSM's size — not the whole
20/// completed FSM. Distinguishing the two is the upstream #600 fix
21/// (`CompactFSMWithStartEndWithSize`, commit 58494db).
22#[derive(Debug, Clone, Default, PartialEq, Eq)]
23pub struct CompactFsmWithStartEnd {
24    pub(crate) fsm: CompactFsm,
25    pub(crate) start: usize,
26    pub(crate) ends: Vec<bool>,
27    pub(crate) is_dfa: bool,
28    node_num: usize,
29    edge_num: usize,
30}
31
32impl CompactFsmWithStartEnd {
33    /// Build a standalone compact FSM; `node_num`/`edge_num` are the
34    /// FSM's own counts.
35    pub fn new(fsm: CompactFsm, start: usize, ends: Vec<bool>) -> Self {
36        let node_num = fsm.num_states();
37        let edge_num = fsm.num_edges();
38        Self {
39            fsm,
40            start,
41            ends,
42            is_dfa: false,
43            node_num,
44            edge_num,
45        }
46    }
47
48    /// Build a per-rule view onto a shared `complete_fsm`. `node_num`
49    /// and `edge_num` are the spliced-in sub-FSM's counts, *not* the
50    /// backing FSM's totals (upstream commit 58494db, #600).
51    pub fn new_view(
52        fsm: CompactFsm,
53        start: usize,
54        ends: Vec<bool>,
55        node_num: usize,
56        edge_num: usize,
57    ) -> Self {
58        Self {
59            fsm,
60            start,
61            ends,
62            is_dfa: false,
63            node_num,
64            edge_num,
65        }
66    }
67
68    /// The underlying compact FSM.
69    pub fn fsm(&self) -> &CompactFsm {
70        &self.fsm
71    }
72
73    /// Start state id.
74    pub fn start(&self) -> usize {
75        self.start
76    }
77
78    /// Accepting-state bitmap.
79    pub fn ends(&self) -> &[bool] {
80        &self.ends
81    }
82
83    /// True if `state` is accepting.
84    pub fn is_end_state(&self, state: usize) -> bool {
85        self.ends[state]
86    }
87
88    /// Number of states in the logical (sub-)FSM. For a per-rule view
89    /// this is the spliced-in sub-FSM's count, not the backing
90    /// `complete_fsm`'s total (upstream commit 58494db, #600).
91    pub fn num_states(&self) -> usize {
92        self.node_num
93    }
94
95    /// Number of edges in the logical (sub-)FSM. For a per-rule view
96    /// this is the spliced-in sub-FSM's count, not the backing
97    /// `complete_fsm`'s total (upstream commit 58494db, #600).
98    pub fn num_edges(&self) -> usize {
99        self.edge_num
100    }
101
102    /// Number of states in the backing FSM storage — for a per-rule
103    /// view this is the whole shared `complete_fsm`. Use this (not
104    /// `num_states`) when indexing into the backing edge table.
105    pub fn backing_num_states(&self) -> usize {
106        self.fsm.num_states()
107    }
108
109    /// True if the FSM accepts the byte string.
110    pub fn accept_string(&self, bytes: &[u8]) -> bool {
111        let mut start_states: AHashSet<i32> = AHashSet::from_iter([self.start as i32]);
112        self.fsm.epsilon_closure(&mut start_states);
113        let mut result_states = AHashSet::new();
114        for &byte in bytes {
115            result_states.clear();
116            self.fsm.advance(
117                &start_states,
118                byte as i32,
119                &mut result_states,
120                edge_type::CHAR_RANGE,
121                false,
122            );
123            if result_states.is_empty() {
124                return false;
125            }
126            std::mem::swap(&mut start_states, &mut result_states);
127        }
128        start_states.iter().any(|&s| self.ends[s as usize])
129    }
130
131    /// All states reachable from the start state.
132    pub fn reachable_states(&self, result: &mut AHashSet<i32>) {
133        self.fsm.reachable_states(&[self.start as i32], result);
134    }
135
136    /// Expand into the mutable form.
137    pub fn to_fsm(&self) -> FsmWithStartEnd {
138        FsmWithStartEnd::new(
139            self.fsm.to_fsm(),
140            self.start,
141            self.ends.clone(),
142            self.is_dfa,
143        )
144    }
145
146    /// Approximate heap footprint.
147    pub fn memory_size(&self) -> usize {
148        self.fsm.memory_size() + self.ends.len()
149    }
150}
metrale_grammar/fsm/compact_with_start_end.rs

metrale_grammar/fsm/
compact_with_start_end.rs
