metrale_grammar/fsm/
fsm_traversal.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Traversal methods on the mutable `Fsm` — transition, epsilon
4// closure, set-advance, reachability. Split out of `fsm.rs` to keep
5// each file under the 250-line cap. The heavy lifting lives in the
6// shared `traversal` module; these are thin typed wrappers.
7
8use ahash::AHashSet;
9use std::collections::VecDeque;
10
11use super::fsm::Fsm;
12use super::traversal;
13
14impl Fsm {
15    /// Single-character / typed transition. Returns the first matching
16    /// target, or `NO_NEXT_STATE`. `edge_type` must not be epsilon.
17    pub fn next_state(&self, from: usize, value: i32, edge_type: i16) -> i32 {
18        traversal::next_state(&self.edges, from, value, edge_type)
19    }
20
21    /// Epsilon closure (in place); `state_set` is *not* cleared first.
22    pub fn epsilon_closure(&self, state_set: &mut AHashSet<i32>) {
23        traversal::epsilon_closure(&self.edges, state_set);
24    }
25
26    /// Advance a set of states by `value` along `edge_type` edges.
27    /// `result` is cleared first; the epsilon closure of the result is
28    /// included. Set `from_is_closure` if `from` is already closed.
29    pub fn advance(
30        &self,
31        from: &AHashSet<i32>,
32        value: i32,
33        result: &mut AHashSet<i32>,
34        edge_type: i16,
35        from_is_closure: bool,
36    ) {
37        traversal::advance(&self.edges, from, value, result, edge_type, from_is_closure);
38    }
39
40    /// All rule ids referenced by `state`'s outgoing edges.
41    pub fn possible_rules(&self, state: usize, rules: &mut AHashSet<i32>) {
42        rules.clear();
43        for edge in &self.edges[state] {
44            if edge.is_rule_ref() {
45                rules.insert(edge.ref_rule_id());
46            }
47        }
48    }
49
50    /// All states reachable from `from` (including `from`). `result` is
51    /// cleared first.
52    pub fn reachable_states(&self, from: &[i32], result: &mut AHashSet<i32>) {
53        result.clear();
54        let mut queue: VecDeque<i32> = VecDeque::new();
55        for &s in from {
56            if result.insert(s) {
57                queue.push_back(s);
58            }
59        }
60        while let Some(cur) = queue.pop_front() {
61            for edge in &self.edges[cur as usize] {
62                if result.insert(edge.target) {
63                    queue.push_back(edge.target);
64                }
65            }
66        }
67    }
68}
metrale_grammar/fsm/fsm_traversal.rs

metrale_grammar/fsm/
fsm_traversal.rs
