metrale_grammar/fsm/
algorithms.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// FSM language algorithms — `IsDFA`, `ToDFA`, `MinimizeDFA`, `Not`,
4// `Intersect`. Port of the corresponding `FSMWithStartEnd` methods from
5// `cpp/fsm.cc`.
6
7use ahash::AHashSet;
8
9use super::edge::edge_type;
10use super::fsm::Fsm;
11use super::with_start_end::FsmWithStartEnd;
12
13/// Default cap on result-state count for DFA / minimize / not.
14pub const DEFAULT_MAX_STATES: usize = 1_000_000;
15
16impl FsmWithStartEnd {
17    /// True if the FSM is a DFA: no epsilon edges and no two char-range
18    /// (or rule-ref) edges from one state overlap. Caches the result.
19    pub fn is_dfa(&mut self) -> bool {
20        if self.is_dfa {
21            return true;
22        }
23        for edges in self.fsm.all_edges() {
24            let mut char_seen = [false; 256];
25            let mut rule_seen: AHashSet<i32> = AHashSet::new();
26            for edge in edges {
27                if edge.is_epsilon() {
28                    return false;
29                }
30                if edge.is_char_range() {
31                    for c in edge.min..=edge.max {
32                        if char_seen[c as usize] {
33                            return false;
34                        }
35                        char_seen[c as usize] = true;
36                    }
37                    continue;
38                }
39                if edge.is_rule_ref() && !rule_seen.insert(edge.ref_rule_id()) {
40                    return false;
41                }
42            }
43        }
44        self.is_dfa = true;
45        true
46    }
47
48    /// Subset-construction NFA -> DFA. Returns `Err` if the result would
49    /// exceed `max_num_states`.
50    pub fn to_dfa(&self, max_num_states: usize) -> Result<FsmWithStartEnd, String> {
51        if self.num_states() > max_num_states {
52            return Err("The number of states exceeds the limit.".to_string());
53        }
54        let mut dfa = FsmWithStartEnd::new(Fsm::with_states(0), 0, Vec::new(), true);
55        let mut closures: Vec<AHashSet<i32>> = Vec::new();
56
57        let mut closure: AHashSet<i32> = AHashSet::from_iter([self.start as i32]);
58        self.fsm.epsilon_closure(&mut closure);
59        closures.push(closure);
60
61        let mut now_process = 0;
62        while now_process < closures.len() {
63            let mut rules: AHashSet<i32> = AHashSet::new();
64            let mut repeat_aux: AHashSet<i16> = AHashSet::new();
65            let mut interval_ends: std::collections::BTreeSet<i32> =
66                std::collections::BTreeSet::new();
67            let mut allowed = [false; 256];
68            dfa.add_state();
69
70            for &state in &closures[now_process] {
71                if self.is_end_state(state as usize) {
72                    dfa.add_end_state(now_process);
73                }
74                for edge in self.fsm.edges(state as usize) {
75                    if edge.is_char_range() {
76                        interval_ends.insert(edge.min as i32);
77                        interval_ends.insert(edge.max as i32 + 1);
78                        for c in edge.min..=edge.max {
79                            allowed[c as usize] = true;
80                        }
81                    } else if edge.is_rule_ref() {
82                        rules.insert(edge.ref_rule_id());
83                    } else if edge.is_repeat_ref() {
84                        repeat_aux.insert(edge.aux_index());
85                    }
86                }
87            }
88
89            // Partition the char axis into maximal fully-allowed intervals.
90            let mut intervals: Vec<(i32, i32)> = Vec::new();
91            let mut last: i32 = -1;
92            for &end in &interval_ends {
93                if last == -1 {
94                    last = end;
95                    continue;
96                }
97                let ok = (last..end).all(|i| allowed[i as usize]);
98                if ok {
99                    intervals.push((last, end - 1));
100                }
101                last = end;
102            }
103
104            for (lo, hi) in intervals {
105                let mut next_closure: AHashSet<i32> = AHashSet::new();
106                for &state in &closures[now_process] {
107                    for edge in self.fsm.edges(state as usize) {
108                        if edge.is_char_range()
109                            && lo >= edge.min as i32
110                            && hi <= edge.max as i32
111                            && !next_closure.contains(&edge.target)
112                        {
113                            let mut ec: AHashSet<i32> = AHashSet::from_iter([edge.target]);
114                            self.fsm.epsilon_closure(&mut ec);
115                            next_closure.extend(ec);
116                        }
117                    }
118                }
119                let idx = closures.iter().position(|c| *c == next_closure);
120                match idx {
121                    Some(j) => dfa.fsm_mut().add_edge(now_process, j, lo as i16, hi as i16),
122                    None => {
123                        dfa.fsm_mut()
124                            .add_edge(now_process, closures.len(), lo as i16, hi as i16);
125                        closures.push(next_closure);
126                    }
127                }
128            }
129
130            for rule in &rules {
131                let next_closure = self.rule_target_closure(&closures[now_process], *rule);
132                let idx = closures.iter().position(|c| *c == next_closure);
133                match idx {
134                    Some(j) => dfa.fsm_mut().add_rule_edge(now_process, j, *rule as i16),
135                    None => {
136                        dfa.fsm_mut()
137                            .add_rule_edge(now_process, closures.len(), *rule as i16);
138                        closures.push(next_closure);
139                    }
140                }
141            }
142
143            for aux_idx in &repeat_aux {
144                let next_closure = self.repeat_target_closure(&closures[now_process], *aux_idx);
145                let idx = closures.iter().position(|c| *c == next_closure);
146                match idx {
147                    Some(j) => dfa.fsm_mut().add_typed_edge(
148                        now_process,
149                        j,
150                        edge_type::REPEAT_REF,
151                        *aux_idx,
152                    ),
153                    None => {
154                        dfa.fsm_mut().add_typed_edge(
155                            now_process,
156                            closures.len(),
157                            edge_type::REPEAT_REF,
158                            *aux_idx,
159                        );
160                        closures.push(next_closure);
161                    }
162                }
163            }
164            now_process += 1;
165        }
166        dfa.fsm_mut()
167            .set_edge_aux_data(self.fsm.edge_aux_data().to_vec());
168        dfa.is_dfa = true;
169        Ok(dfa)
170    }
171
172    /// Epsilon closure of all rule-ref targets matching `rule`.
173    fn rule_target_closure(&self, from: &AHashSet<i32>, rule: i32) -> AHashSet<i32> {
174        let mut next: AHashSet<i32> = AHashSet::new();
175        for &state in from {
176            for edge in self.fsm.edges(state as usize) {
177                if edge.is_rule_ref() && edge.ref_rule_id() == rule && !next.contains(&edge.target)
178                {
179                    let mut ec: AHashSet<i32> = AHashSet::from_iter([edge.target]);
180                    self.fsm.epsilon_closure(&mut ec);
181                    next.extend(ec);
182                }
183            }
184        }
185        next
186    }
187
188    /// Epsilon closure of all repeat-ref targets at `aux_idx`.
189    fn repeat_target_closure(&self, from: &AHashSet<i32>, aux_idx: i16) -> AHashSet<i32> {
190        let mut next: AHashSet<i32> = AHashSet::new();
191        for &state in from {
192            for edge in self.fsm.edges(state as usize) {
193                if edge.is_repeat_ref()
194                    && edge.aux_index() == aux_idx
195                    && !next.contains(&edge.target)
196                {
197                    let mut ec: AHashSet<i32> = AHashSet::from_iter([edge.target]);
198                    self.fsm.epsilon_closure(&mut ec);
199                    next.extend(ec);
200                }
201            }
202        }
203        next
204    }
205}
206
207#[cfg(test)]
208#[path = "algorithms_tests.rs"]
209mod tests;
metrale_grammar/fsm/algorithms.rs

metrale_grammar/fsm/
algorithms.rs
