metrale_grammar/fsm/
compact.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// CompactFsm — the immutable CSR form of `Fsm`.
4// Port of `class CompactFSM` (+ `CompactFSM::Impl`) from `cpp/fsm.{h,cc}`.
5//
6// A `CompactFsm` stores its edges in a `Compact2DArray<FsmEdge>` so every
7// state's edge list is contiguous in memory; outgoing edges are sorted by
8// `(min, max, target)`. It is immutable — mutate by converting to `Fsm`,
9// editing, and converting back.
10
11use ahash::AHashSet;
12
13use super::compact_array::Compact2DArray;
14use super::edge::{FsmEdge, RepeatEdgeRef};
15use super::fsm::{Fsm, NO_NEXT_STATE};
16use super::traversal;
17
18/// An immutable, CSR-packed finite-state machine.
19#[derive(Debug, Clone, Default, PartialEq, Eq)]
20pub struct CompactFsm {
21    edges: Compact2DArray<FsmEdge>,
22    edge_aux_data: Vec<i32>,
23}
24
25impl CompactFsm {
26    /// Build directly from a CSR edge array and aux data.
27    pub fn new(edges: Compact2DArray<FsmEdge>, edge_aux_data: Vec<i32>) -> Self {
28        Self {
29            edges,
30            edge_aux_data,
31        }
32    }
33
34    /* ----------------------- visitors ----------------------- */
35
36    /// Number of states.
37    pub fn num_states(&self) -> usize {
38        self.edges.len()
39    }
40
41    /// The CSR edge array.
42    pub fn all_edges(&self) -> &Compact2DArray<FsmEdge> {
43        &self.edges
44    }
45
46    /// Outgoing edges of `state` as a contiguous slice.
47    pub fn edges(&self, state: usize) -> &[FsmEdge] {
48        self.edges.row(state)
49    }
50
51    /// The repeat-edge auxiliary data buffer.
52    pub fn edge_aux_data(&self) -> &[i32] {
53        &self.edge_aux_data
54    }
55
56    /// Replace the repeat-edge auxiliary data buffer.
57    pub fn set_edge_aux_data(&mut self, data: Vec<i32>) {
58        self.edge_aux_data = data;
59    }
60
61    /// Decode the repeat-edge info stored at aux index `idx`.
62    pub fn repeat_edge_info(&self, idx: i16) -> RepeatEdgeRef {
63        RepeatEdgeRef::from_aux(&self.edge_aux_data, idx as usize)
64    }
65
66    /// Total edges across all states.
67    pub fn num_edges(&self) -> usize {
68        self.edges.total_elems()
69    }
70
71    /// Approximate heap footprint in bytes.
72    pub fn memory_size(&self) -> usize {
73        self.edges.memory_size() + self.edge_aux_data.len() * std::mem::size_of::<i32>()
74    }
75
76    /* ----------------------- traversal ----------------------- */
77
78    /// Materialize the adjacency rows as `Vec<Vec<FsmEdge>>` so the
79    /// shared traversal helpers can run. Edges are already sorted.
80    fn adjacency(&self) -> Vec<Vec<FsmEdge>> {
81        self.edges.iter_rows().map(|r| r.to_vec()).collect()
82    }
83
84    /// Collect every transition target from `from` for `value` along
85    /// `edge_type` into `targets` (cleared first). Because the compact
86    /// rows are sorted, this could early-break, but for simplicity it
87    /// scans the (small) row fully — behavior is identical.
88    pub fn next_states(&self, from: usize, value: i32, edge_type: i16, targets: &mut Vec<i32>) {
89        targets.clear();
90        for edge in self.edges(from) {
91            if traversal::edge_matches(edge, value, edge_type) {
92                targets.push(edge.target);
93            }
94        }
95    }
96
97    /// First transition target, or [`NO_NEXT_STATE`].
98    pub fn next_state(&self, from: usize, value: i32, edge_type: i16) -> i32 {
99        let mut t = Vec::new();
100        self.next_states(from, value, edge_type, &mut t);
101        t.first().copied().unwrap_or(NO_NEXT_STATE)
102    }
103
104    /// Epsilon closure (in place); `state_set` is *not* cleared.
105    pub fn epsilon_closure(&self, state_set: &mut AHashSet<i32>) {
106        traversal::epsilon_closure(&self.adjacency(), state_set);
107    }
108
109    /// Advance a set of states — see [`Fsm::advance`].
110    pub fn advance(
111        &self,
112        from: &AHashSet<i32>,
113        value: i32,
114        result: &mut AHashSet<i32>,
115        edge_type: i16,
116        from_is_closure: bool,
117    ) {
118        traversal::advance(
119            &self.adjacency(),
120            from,
121            value,
122            result,
123            edge_type,
124            from_is_closure,
125        );
126    }
127
128    /// All rule ids referenced by `state`'s outgoing edges.
129    pub fn possible_rules(&self, state: usize, rules: &mut AHashSet<i32>) {
130        rules.clear();
131        for edge in self.edges(state) {
132            if edge.is_rule_ref() {
133                rules.insert(edge.ref_rule_id());
134            }
135        }
136    }
137
138    /// All states reachable from `from`. `result` is cleared first.
139    pub fn reachable_states(&self, from: &[i32], result: &mut AHashSet<i32>) {
140        self.to_fsm().reachable_states(from, result);
141    }
142
143    /* --------------------- construction ---------------------- */
144
145    /// Expand back into a mutable [`Fsm`].
146    pub fn to_fsm(&self) -> Fsm {
147        let edges: Vec<Vec<FsmEdge>> = self.edges.iter_rows().map(|r| r.to_vec()).collect();
148        Fsm::from_edges(edges, self.edge_aux_data.clone())
149    }
150}
151
152impl Fsm {
153    /// Sort edges and pack into the CSR [`CompactFsm`] form.
154    pub fn to_compact(&self) -> CompactFsm {
155        let mut sorted = self.clone();
156        sorted.sort_edges();
157        let mut arr: Compact2DArray<FsmEdge> = Compact2DArray::new();
158        for row in &sorted.edges {
159            arr.push_row(row);
160        }
161        CompactFsm::new(arr, sorted.edge_aux_data)
162    }
163}
164
165#[cfg(test)]
166#[path = "compact_tests.rs"]
167mod tests;
metrale_grammar/fsm/compact.rs

metrale_grammar/fsm/
compact.rs
