metrale_grammar/fsm/
with_start_end.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// FsmWithStartEnd / CompactFsmWithStartEnd — an FSM paired with a start
4// state and a set of accepting states. Port of `FSMWithStartEndBase`,
5// `FSMWithStartEnd` and `CompactFSMWithStartEnd` from `cpp/fsm.{h,cc}`.
6//
7// The C++ uses a CRTP base template parameterized over `FSM`/`CompactFSM`.
8// Rust has no CRTP; instead this file holds the mutable `FsmWithStartEnd`
9// with its rich construction API, and a lighter `CompactFsmWithStartEnd`.
10// Shared accepting-state logic is provided by free helpers.
11
12use ahash::AHashSet;
13
14use super::edge::edge_type;
15use super::fsm::Fsm;
16
17/// A mutable FSM together with a start state and accepting states.
18#[derive(Debug, Clone, Default, PartialEq, Eq)]
19pub struct FsmWithStartEnd {
20    pub(crate) fsm: Fsm,
21    pub(crate) start: usize,
22    /// `ends[s]` is true when state `s` is accepting.
23    pub(crate) ends: Vec<bool>,
24    /// Cached DFA flag — true once the FSM is known deterministic.
25    pub(crate) is_dfa: bool,
26}
27
28impl FsmWithStartEnd {
29    /// Build from parts.
30    pub fn new(fsm: Fsm, start: usize, ends: Vec<bool>, is_dfa: bool) -> Self {
31        Self {
32            fsm,
33            start,
34            ends,
35            is_dfa,
36        }
37    }
38
39    /* --------------------- accessors --------------------- */
40
41    /// The underlying FSM.
42    pub fn fsm(&self) -> &Fsm {
43        &self.fsm
44    }
45
46    /// Mutable underlying FSM.
47    pub fn fsm_mut(&mut self) -> &mut Fsm {
48        &mut self.fsm
49    }
50
51    /// The start state id.
52    pub fn start(&self) -> usize {
53        self.start
54    }
55
56    /// The accepting-state bitmap.
57    pub fn ends(&self) -> &[bool] {
58        &self.ends
59    }
60
61    /// True if `state` is accepting.
62    pub fn is_end_state(&self, state: usize) -> bool {
63        self.ends[state]
64    }
65
66    /// Total number of states.
67    pub fn num_states(&self) -> usize {
68        self.fsm.num_states()
69    }
70
71    /// Set the start state.
72    pub fn set_start_state(&mut self, state: usize) {
73        debug_assert!(state < self.num_states());
74        self.start = state;
75    }
76
77    /// Mark `state` accepting.
78    pub fn add_end_state(&mut self, state: usize) {
79        debug_assert!(state < self.num_states());
80        self.ends[state] = true;
81    }
82
83    /// Replace the accepting-state bitmap.
84    pub fn set_end_states(&mut self, ends: Vec<bool>) {
85        self.ends = ends;
86    }
87
88    /// Append a new (non-accepting) state; returns its id.
89    pub fn add_state(&mut self) -> usize {
90        self.ends.push(false);
91        self.fsm.add_state()
92    }
93
94    /// True if `state` has at least one outgoing char-range edge.
95    pub fn is_scanable_state(&self, state: usize) -> bool {
96        self.fsm.edges(state).iter().any(|e| e.is_char_range())
97    }
98
99    /// True if `state` has a rule-ref / epsilon / repeat-ref edge.
100    pub fn is_non_terminal_state(&self, state: usize) -> bool {
101        self.fsm
102            .edges(state)
103            .iter()
104            .any(|e| e.is_rule_ref() || e.is_epsilon() || e.is_repeat_ref())
105    }
106
107    /* --------------------- traversal --------------------- */
108
109    /// True if the FSM accepts the byte string `str`.
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    /// True if no reachable state has a rule-ref or repeat-ref edge.
137    pub fn is_leaf(&self) -> bool {
138        let mut reachable = AHashSet::new();
139        self.reachable_states(&mut reachable);
140        for &s in &reachable {
141            for edge in self.fsm.edges(s as usize) {
142                if edge.is_rule_ref() || edge.is_repeat_ref() {
143                    return false;
144                }
145            }
146        }
147        true
148    }
149
150    /* --------------------- construction --------------------- */
151
152    /// A deep copy.
153    pub fn copy(&self) -> FsmWithStartEnd {
154        self.clone()
155    }
156
157    /// Rebuild with remapped state ids.
158    pub fn rebuild_with_mapping(
159        &self,
160        state_mapping: &[usize],
161        new_num_states: usize,
162    ) -> FsmWithStartEnd {
163        let new_fsm = self.fsm.rebuild_with_mapping(state_mapping, new_num_states);
164        let new_start = state_mapping[self.start];
165        let mut new_ends = vec![false; new_num_states];
166        for end in 0..self.num_states() {
167            if self.is_end_state(end) {
168                new_ends[state_mapping[end]] = true;
169            }
170        }
171        FsmWithStartEnd::new(new_fsm, new_start, new_ends, false)
172    }
173
174    /// Splice this FSM into `complete_fsm`, returning a view onto it.
175    pub fn add_to_complete_fsm(&self, complete_fsm: &mut Fsm) -> FsmWithStartEnd {
176        let state_mapping = complete_fsm.add_fsm(&self.fsm);
177        let new_start = state_mapping[self.start];
178        let mut new_ends = vec![false; complete_fsm.num_states()];
179        for end in 0..self.num_states() {
180            if self.is_end_state(end) {
181                new_ends[state_mapping[end]] = true;
182            }
183        }
184        FsmWithStartEnd::new(complete_fsm.clone(), new_start, new_ends, self.is_dfa)
185    }
186
187    /// Pack into the compact form.
188    pub fn to_compact(&self) -> CompactFsmWithStartEnd {
189        CompactFsmWithStartEnd::new(self.fsm.to_compact(), self.start, self.ends.clone())
190    }
191}
192
193// Star / Plus / Optional / Union / Concat live in `fsm_ops.rs`;
194// CompactFsmWithStartEnd lives in `compact_with_start_end.rs`.
195pub use super::compact_with_start_end::CompactFsmWithStartEnd;
196
197#[cfg(test)]
198#[path = "with_start_end_tests.rs"]
199mod tests;
metrale_grammar/fsm/with_start_end.rs

metrale_grammar/fsm/
with_start_end.rs
