metrale_grammar/fsm/
dfa_ops.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// DFA-level operations — MinimizeDFA, Not, Intersect. Split out of
4// `algorithms.rs` to keep each file under the 250-line cap; together
5// they port the corresponding `FSMWithStartEnd` methods from
6// `cpp/fsm.cc`.
7
8use ahash::{AHashMap, AHashSet};
9use std::collections::VecDeque;
10
11use super::algorithms::DEFAULT_MAX_STATES;
12use super::fsm::Fsm;
13use super::with_start_end::FsmWithStartEnd;
14
15impl FsmWithStartEnd {
16    /// Hopcroft DFA minimization. Returns `Err` over the state cap.
17    pub fn minimize_dfa(&self, max_num_states: usize) -> Result<FsmWithStartEnd, String> {
18        if self.num_states() > max_num_states {
19            return Err("The number of states exceeds the limit.".to_string());
20        }
21        let now_fsm = if self.is_dfa {
22            self.copy()
23        } else {
24            self.to_dfa(max_num_states)?
25        };
26        let n = now_fsm.num_states();
27
28        // precursors[t] = list of ((min,max), source)
29        let mut precursors: Vec<Vec<((i16, i16), usize)>> = vec![Vec::new(); n];
30        for i in 0..n {
31            for edge in now_fsm.fsm().edges(i) {
32                precursors[edge.target as usize].push(((edge.min, edge.max), i));
33            }
34        }
35
36        let mut final_states: AHashSet<i32> = AHashSet::new();
37        let mut non_final: AHashSet<i32> = AHashSet::new();
38        for i in 0..n {
39            if now_fsm.is_end_state(i) {
40                final_states.insert(i as i32);
41            } else {
42                non_final.insert(i as i32);
43            }
44        }
45        let mut partitions: Vec<AHashSet<i32>> = vec![final_states.clone(), non_final.clone()];
46        let mut working: Vec<AHashSet<i32>> = vec![final_states, non_final];
47
48        while let Some(current) = working.pop() {
49            // possible_transitions[(min,max)] = set of precursor states
50            let mut possible: AHashMap<(i16, i16), AHashSet<i32>> = AHashMap::new();
51            for &state in &current {
52                for &(label, src) in &precursors[state as usize] {
53                    possible.entry(label).or_default().insert(src as i32);
54                }
55            }
56            for (_label, precs) in possible {
57                let mut i = 0;
58                while i < partitions.len() {
59                    let intersection: Vec<i32> = partitions[i]
60                        .iter()
61                        .copied()
62                        .filter(|s| precs.contains(s))
63                        .collect();
64                    let difference: Vec<i32> = partitions[i]
65                        .iter()
66                        .copied()
67                        .filter(|s| !precs.contains(s))
68                        .collect();
69                    if !intersection.is_empty() && !difference.is_empty() {
70                        let part = partitions[i].clone();
71                        let in_working = working.iter().position(|w| *w == part);
72                        match in_working {
73                            Some(wi) => {
74                                working[wi] = intersection.iter().copied().collect();
75                                working.push(difference.iter().copied().collect());
76                            }
77                            None => {
78                                let smaller = if difference.len() < intersection.len() {
79                                    &difference
80                                } else {
81                                    &intersection
82                                };
83                                working.push(smaller.iter().copied().collect());
84                            }
85                        }
86                        partitions[i] = intersection.iter().copied().collect();
87                        partitions.push(difference.iter().copied().collect());
88                    }
89                    i += 1;
90                }
91            }
92        }
93
94        let mut state_mapping = vec![0usize; n];
95        for (i, part) in partitions.iter().enumerate() {
96            for &state in part {
97                state_mapping[state as usize] = i;
98            }
99        }
100        Ok(now_fsm.rebuild_with_mapping(&state_mapping, partitions.len()))
101    }
102
103    /// The complement of the FSM's language. Only valid for leaf FSMs
104    /// (no rule references).
105    pub fn not(&self, max_result_num_states: usize) -> Result<FsmWithStartEnd, String> {
106        if !self.is_leaf() {
107            return Err("Not operation is not supported for FSM with rule references.".to_string());
108        }
109        let mut result = if self.is_dfa {
110            self.copy()
111        } else {
112            self.to_dfa(max_result_num_states)?
113        };
114
115        let mut new_final = vec![false; result.num_states() + 1];
116        for i in 0..result.num_states() {
117            if !result.is_end_state(i) {
118                new_final[i] = true;
119            }
120        }
121        let accept_all = result.add_state();
122        new_final[accept_all] = true;
123
124        for i in 0..result.num_states() {
125            if i == accept_all {
126                continue;
127            }
128            let mut char_set = [false; 256];
129            for edge in result.fsm().edges(i) {
130                if edge.is_char_range() {
131                    for c in edge.min..=edge.max {
132                        char_set[c as usize] = true;
133                    }
134                }
135            }
136            let mut left = 0usize;
137            while left < 256 {
138                if char_set[left] {
139                    left += 1;
140                    continue;
141                }
142                let mut right = left + 1;
143                while right < 256 && !char_set[right] {
144                    right += 1;
145                }
146                result
147                    .fsm_mut()
148                    .add_edge(i, accept_all, left as i16, (right - 1) as i16);
149                left = right;
150            }
151        }
152        result.set_end_states(new_final);
153        Ok(result)
154    }
155
156    /// Intersection of two leaf FSMs (product construction over DFAs).
157    pub fn intersect(
158        lhs: &FsmWithStartEnd,
159        rhs: &FsmWithStartEnd,
160        _max_result_num_states: usize,
161    ) -> Result<FsmWithStartEnd, String> {
162        if !lhs.is_leaf() || !rhs.is_leaf() {
163            return Err("Intersect only support leaf fsm!".to_string());
164        }
165        let lhs_dfa = lhs.to_dfa(DEFAULT_MAX_STATES)?;
166        let rhs_dfa = rhs.to_dfa(DEFAULT_MAX_STATES)?;
167
168        let mut result = FsmWithStartEnd::new(Fsm::with_states(0), 0, Vec::new(), true);
169        let mut state_map: AHashMap<(usize, usize), usize> = AHashMap::new();
170        let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
171
172        queue.push_back((lhs_dfa.start(), rhs_dfa.start()));
173        result.add_state();
174        state_map.insert((lhs_dfa.start(), rhs_dfa.start()), 0);
175
176        while let Some((ls, rs)) = queue.pop_front() {
177            if lhs_dfa.is_end_state(ls) && rhs_dfa.is_end_state(rs) {
178                let id = state_map[&(ls, rs)];
179                result.add_end_state(id);
180            }
181            for le in lhs_dfa.fsm().edges(ls) {
182                for re in rhs_dfa.fsm().edges(rs) {
183                    if !le.is_char_range() || !re.is_char_range() {
184                        continue;
185                    }
186                    if le.min > re.max || re.min > le.max {
187                        continue;
188                    }
189                    let min_v = le.min.max(re.min);
190                    let max_v = le.max.min(re.max);
191                    let key = (le.target as usize, re.target as usize);
192                    let target = match state_map.get(&key) {
193                        Some(&t) => t,
194                        None => {
195                            let t = result.add_state();
196                            state_map.insert(key, t);
197                            queue.push_back(key);
198                            t
199                        }
200                    };
201                    let src = state_map[&(ls, rs)];
202                    result.fsm_mut().add_edge(src, target, min_v, max_v);
203                }
204            }
205        }
206        Ok(result)
207    }
208}
metrale_grammar/fsm/dfa_ops.rs

metrale_grammar/fsm/
dfa_ops.rs
