metrale_grammar/grammar/functor/
fsm_hasher.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// GrammarFsmHasher — port of `GrammarFSMHasherImpl` from
4// `cpp/grammar_functor.cc`.
5//
6// Computes a structural hash for each rule's FSM (used by the matcher's
7// rule-level token-mask cache) plus a canonical state renumbering.
8// Hashing proceeds from terminal FSMs inward, breaking simple cycles.
9
10use crate::grammar::data::GrammarData;
11use crate::grammar::expr::GrammarExprType;
12use crate::support::hash::hash_combine_binary;
13
14use super::analyzer::RuleRefGraphFinder;
15use super::hash_walk::{flag, hash_fsm};
16
17/// Per-rule FSM structural hashing pass.
18pub struct GrammarFsmHasher {
19    visited: Vec<bool>,
20    /// `referrer_to_referee[r]` lists the rules that rule `r` references.
21    referrer_to_referee: Vec<Vec<i32>>,
22    /// `referee_to_referrer[r]` lists the rules that reference rule `r`.
23    referee_to_referrer: Vec<Vec<i32>>,
24}
25
26impl GrammarFsmHasher {
27    /// Build `per_rule_fsm_hashes` and `per_rule_fsm_new_state_ids`.
28    pub fn apply(grammar: &mut GrammarData) {
29        let num_rules = grammar.num_rules() as usize;
30        grammar.per_rule_fsm_hashes = vec![None; num_rules];
31        grammar.per_rule_fsm_new_state_ids = vec![Vec::new(); num_rules];
32
33        let referee_to_referrer = RuleRefGraphFinder::apply(grammar);
34        let mut referrer_to_referee: Vec<Vec<i32>> = vec![Vec::new(); num_rules];
35        for (referee, referrers) in referee_to_referrer.iter().enumerate() {
36            for &referrer in referrers {
37                referrer_to_referee[referrer as usize].push(referee as i32);
38            }
39        }
40
41        let mut visited = vec![false; num_rules];
42        for (i, fsm) in grammar.per_rule_fsms.iter().enumerate() {
43            if fsm.is_none() {
44                visited[i] = true;
45            }
46        }
47
48        let mut hasher = Self {
49            visited,
50            referrer_to_referee,
51            referee_to_referrer,
52        };
53
54        // Hash terminal / self-recursive FSMs first, breaking cycles.
55        loop {
56            let idx = hasher.find_terminal();
57            if idx != -1 {
58                hasher.visited[idx as usize] = true;
59                let (h, mapping) = hash_fsm(grammar, idx);
60                grammar.per_rule_fsm_hashes[idx as usize] = Some(h);
61                grammar.per_rule_fsm_new_state_ids[idx as usize] = mapping;
62                hasher.detach(idx);
63                continue;
64            }
65            if !hasher.break_one_cycle(grammar) {
66                break;
67            }
68        }
69
70        // Remaining FSMs: partial-hash those whose start has no inward
71        // edge and whose unhashed rule refs are all at the start state.
72        let mut partial: Vec<(i32, u64)> = Vec::new();
73        for i in 0..num_rules as i32 {
74            if grammar.per_rule_fsm_hashes[i as usize].is_some() {
75                continue;
76            }
77            let Some(fsm) = &grammar.per_rule_fsms[i as usize] else {
78                continue;
79            };
80            if has_inward_edge(grammar, fsm.start()) {
81                continue;
82            }
83            if let Some((h, mapping)) = super::hash_walk::partial_hash_fsm(grammar, i) {
84                grammar.per_rule_fsm_new_state_ids[i as usize] = mapping;
85                partial.push((i, h));
86            }
87        }
88        for (rule_id, h) in partial {
89            grammar.per_rule_fsm_hashes[rule_id as usize] = Some(h);
90        }
91    }
92
93    /// Find a terminal (no outgoing refs) or self-recursive FSM that can
94    /// be hashed now. `-1` if none.
95    fn find_terminal(&self) -> i32 {
96        for i in 0..self.referrer_to_referee.len() {
97            if self.visited[i] {
98                continue;
99            }
100            if self.referrer_to_referee[i].is_empty() {
101                return i as i32;
102            }
103            if self.referrer_to_referee[i].len() == 1 && self.referrer_to_referee[i][0] == i as i32
104            {
105                return i as i32;
106            }
107        }
108        -1
109    }
110
111    /// Detach `idx` from the reference graph.
112    fn detach(&mut self, idx: i32) {
113        for referer in self.referee_to_referrer[idx as usize].clone() {
114            self.referrer_to_referee[referer as usize].retain(|&r| r != idx);
115        }
116    }
117
118    /// Find one simple cycle, hash its members, detach it. Returns
119    /// `false` when no cycle remains.
120    fn break_one_cycle(&mut self, grammar: &mut GrammarData) -> bool {
121        let n = self.referee_to_referrer.len();
122        let mut not_simple = self.visited.clone();
123        for i in 0..n {
124            if not_simple[i] {
125                continue;
126            }
127            let mut dfs_stack: Vec<i32> = vec![i as i32];
128            let mut in_stack = vec![false; n];
129            in_stack[i] = true;
130            let mut cur = i as i32;
131            let mut cycle: Vec<i32> = Vec::new();
132            while self.referrer_to_referee[cur as usize].len() == 1 && !not_simple[cur as usize] {
133                assert_ne!(
134                    cur, self.referrer_to_referee[cur as usize][0],
135                    "self-recursion cycle not allowed"
136                );
137                not_simple[cur as usize] = true;
138                cur = self.referrer_to_referee[cur as usize][0];
139                if in_stack[cur as usize] {
140                    cycle.push(cur);
141                    while *dfs_stack.last().unwrap() != cur {
142                        cycle.push(dfs_stack.pop().unwrap());
143                    }
144                    break;
145                }
146                dfs_stack.push(cur);
147                in_stack[cur as usize] = true;
148            }
149            if !cycle.is_empty() {
150                self.hash_cycle(grammar, &cycle);
151                return true;
152            }
153        }
154        false
155    }
156
157    /// Hash a simple cycle: hash each member, rotation-combine, detach.
158    fn hash_cycle(&mut self, grammar: &mut GrammarData, cycle: &[i32]) {
159        for &id in cycle {
160            self.visited[id as usize] = true;
161            grammar.per_rule_fsm_hashes[id as usize] = Some(flag::SIMPLE_CYCLE);
162        }
163        let mut local: Vec<u64> = Vec::with_capacity(cycle.len());
164        for &id in cycle {
165            let (h, mapping) = hash_fsm(grammar, id);
166            grammar.per_rule_fsm_new_state_ids[id as usize] = mapping;
167            local.push(h);
168        }
169        let len = local.len();
170        for (i, &id) in cycle.iter().enumerate() {
171            let mut seed = 0u64;
172            for j in 0..len {
173                hash_combine_binary(&mut seed, local[(i + j) % len]);
174            }
175            grammar.per_rule_fsm_hashes[id as usize] = Some(seed);
176        }
177        for &id in cycle {
178            self.detach(id);
179        }
180    }
181}
182
183/// True if any state in the complete FSM has an edge into `state`.
184fn has_inward_edge(grammar: &GrammarData, state: usize) -> bool {
185    let fsm = &grammar.complete_fsm;
186    for s in 0..fsm.num_states() {
187        for edge in fsm.edges(s) {
188            if edge.target as usize == state {
189                return true;
190            }
191        }
192    }
193    false
194}
195
196/// Hash a normalized `Sequence` expr — used by the matcher to key its
197/// per-sequence cache. `None` when the sequence is not hashable.
198pub fn hash_sequence(grammar: &GrammarData, sequence_id: i32) -> Option<u64> {
199    if sequence_id == -1 {
200        return None;
201    }
202    let seq = grammar.expr(sequence_id);
203    debug_assert_eq!(seq.kind, GrammarExprType::Sequence);
204    let mut seed = 0u64;
205    for &eid in seq.data {
206        let e = grammar.expr(eid);
207        hash_combine_binary(&mut seed, e.kind as i32 as u64);
208        match e.kind {
209            GrammarExprType::ByteString
210            | GrammarExprType::CharacterClass
211            | GrammarExprType::CharacterClassStar
212            | GrammarExprType::EmptyStr => {
213                for &x in e.data {
214                    hash_combine_binary(&mut seed, x as i64 as u64);
215                }
216            }
217            GrammarExprType::RuleRef => {
218                let h = grammar.per_rule_fsm_hashes[e.data[0] as usize]?;
219                hash_combine_binary(&mut seed, h);
220            }
221            GrammarExprType::Repeat => {
222                let h = grammar.per_rule_fsm_hashes[e.data[0] as usize]?;
223                hash_combine_binary(&mut seed, h);
224                hash_combine_binary(&mut seed, e.data[1] as i64 as u64);
225                hash_combine_binary(&mut seed, e.data[2] as i64 as u64);
226            }
227            GrammarExprType::Sequence | GrammarExprType::Choices => return None,
228            GrammarExprType::TagDispatch => return None,
229        }
230    }
231    Some(seed)
232}
233
234#[cfg(test)]
235#[path = "fsm_hasher_tests.rs"]
236mod tests;
metrale_grammar/grammar/functor/fsm_hasher.rs

metrale_grammar/grammar/functor/
fsm_hasher.rs
