metrale_grammar/fsm/
traversal.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Shared FSM traversal algorithms — epsilon closure, single-step
4// transition, and set-advance. Port of the traversal methods in
5// `FSMImplBase` / `FSM::Impl` / `CompactFSM::Impl` from `cpp/fsm.cc`.
6//
7// These work on any `&[Vec<FsmEdge>]`-shaped adjacency view, so the same
8// code backs both the mutable `Fsm` and the immutable `CompactFsm` (the
9// latter materializes rows as slices via `CompactFsm::advance`).
10
11use ahash::AHashSet;
12use std::collections::VecDeque;
13
14use super::edge::{FsmEdge, edge_type};
15use super::fsm::NO_NEXT_STATE;
16
17/// Compute the epsilon closure of `state_set` in place over `edges`.
18///
19/// The set is *not* cleared — every state already present plus every
20/// state reachable from it by epsilon edges ends up in the set.
21pub fn epsilon_closure(edges: &[Vec<FsmEdge>], state_set: &mut AHashSet<i32>) {
22    let mut queue: VecDeque<i32> = state_set.iter().copied().collect();
23    while let Some(cur) = queue.pop_front() {
24        for edge in &edges[cur as usize] {
25            if !edge.is_epsilon() {
26                continue;
27            }
28            if state_set.insert(edge.target) {
29                queue.push_back(edge.target);
30            }
31        }
32    }
33}
34
35/// First transition target from `from` for `value` along `edge_type`,
36/// or [`NO_NEXT_STATE`]. Panics if `edge_type` is epsilon.
37pub fn next_state(edges: &[Vec<FsmEdge>], from: usize, value: i32, edge_type: i16) -> i32 {
38    debug_assert_ne!(
39        edge_type,
40        super::edge::edge_type::EPSILON,
41        "Should not call next_state with edge type epsilon."
42    );
43    for edge in &edges[from] {
44        if edge_matches(edge, value, edge_type) {
45            return edge.target;
46        }
47    }
48    NO_NEXT_STATE
49}
50
51/// True if `edge` accepts `value` under `edge_type`.
52pub fn edge_matches(edge: &FsmEdge, value: i32, etype: i16) -> bool {
53    match etype {
54        edge_type::CHAR_RANGE => {
55            edge.is_char_range() && (edge.min as i32) <= value && (edge.max as i32) >= value
56        }
57        edge_type::RULE_REF => edge.is_rule_ref() && edge.max as i32 == value,
58        edge_type::EOS => edge.is_eos(),
59        edge_type::REPEAT_REF => edge.is_repeat_ref(),
60        _ => false,
61    }
62}
63
64/// Advance the set `from` by `value` along `edge_type` edges.
65///
66/// `result` is cleared first, then filled with the epsilon closure of
67/// every reachable target. If `from_is_closure` is false, the epsilon
68/// closure of `from` is taken first.
69pub fn advance(
70    edges: &[Vec<FsmEdge>],
71    from: &AHashSet<i32>,
72    value: i32,
73    result: &mut AHashSet<i32>,
74    edge_type: i16,
75    from_is_closure: bool,
76) {
77    debug_assert_ne!(
78        edge_type,
79        super::edge::edge_type::EPSILON,
80        "Should not call advance with edge type epsilon."
81    );
82
83    let mut closure_tmp;
84    let start_closure: &AHashSet<i32> = if from_is_closure {
85        from
86    } else {
87        closure_tmp = from.clone();
88        epsilon_closure(edges, &mut closure_tmp);
89        &closure_tmp
90    };
91
92    result.clear();
93    for &state in start_closure {
94        for edge in &edges[state as usize] {
95            if edge_matches(edge, value, edge_type) {
96                result.insert(edge.target);
97            }
98        }
99    }
100    epsilon_closure(edges, result);
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    fn sorted(set: &AHashSet<i32>) -> Vec<i32> {
108        let mut v: Vec<i32> = set.iter().copied().collect();
109        v.sort_unstable();
110        v
111    }
112
113    #[test]
114    fn closure_of_disconnected_set_is_identity() {
115        let edges: Vec<Vec<FsmEdge>> = vec![Vec::new(), Vec::new()];
116        let mut set: AHashSet<i32> = AHashSet::from_iter([0, 1]);
117        epsilon_closure(&edges, &mut set);
118        assert_eq!(sorted(&set), vec![0, 1]);
119    }
120
121    #[test]
122    fn closure_handles_epsilon_cycle() {
123        let edges = vec![
124            vec![FsmEdge::new(edge_type::EPSILON, 0, 1)],
125            vec![FsmEdge::new(edge_type::EPSILON, 0, 0)],
126        ];
127        let mut set: AHashSet<i32> = AHashSet::from_iter([0]);
128        epsilon_closure(&edges, &mut set);
129        assert_eq!(sorted(&set), vec![0, 1]);
130    }
131
132    #[test]
133    fn next_state_char_range() {
134        let edges = vec![vec![FsmEdge::new(b'a' as i16, b'c' as i16, 1)]];
135        assert_eq!(next_state(&edges, 0, b'b' as i32, edge_type::CHAR_RANGE), 1);
136        assert_eq!(
137            next_state(&edges, 0, b'd' as i32, edge_type::CHAR_RANGE),
138            NO_NEXT_STATE
139        );
140    }
141
142    #[test]
143    fn advance_with_precomputed_closure() {
144        let edges = vec![vec![FsmEdge::new(b'a' as i16, b'a' as i16, 1)], vec![]];
145        let from: AHashSet<i32> = AHashSet::from_iter([0]);
146        let mut result = AHashSet::new();
147        advance(
148            &edges,
149            &from,
150            b'a' as i32,
151            &mut result,
152            edge_type::CHAR_RANGE,
153            true,
154        );
155        assert_eq!(sorted(&result), vec![1]);
156    }
157
158    #[test]
159    fn advance_empty_when_no_match() {
160        let edges = vec![vec![FsmEdge::new(b'a' as i16, b'a' as i16, 1)], vec![]];
161        let from: AHashSet<i32> = AHashSet::from_iter([0]);
162        let mut result = AHashSet::new();
163        advance(
164            &edges,
165            &from,
166            b'z' as i32,
167            &mut result,
168            edge_type::CHAR_RANGE,
169            true,
170        );
171        assert!(result.is_empty());
172    }
173}
metrale_grammar/fsm/traversal.rs

metrale_grammar/fsm/
traversal.rs
