metrale_grammar/grammar/functor/
hash_walk.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Per-FSM BFS hashing — the `HashFsm` / `IsPartialHashable` helpers of
4// `GrammarFSMHasherImpl` (`cpp/grammar_functor.cc`).
5//
6// Each rule's FSM is walked breadth-first; states are renumbered in
7// discovery order and every edge (char range / rule ref / repeat ref)
8// is folded into a structural hash.
9
10use std::collections::{BTreeMap, BTreeSet, VecDeque};
11
12use crate::grammar::data::GrammarData;
13use crate::support::hash::hash_combine_binary;
14
15/// Sentinel flag values mixed into structural hashes.
16pub mod flag {
17    /// State is not accepting.
18    pub const NOT_END: u64 = (-0x100_i64) as u64;
19    /// State is accepting.
20    pub const END: u64 = (-0x200_i64) as u64;
21    /// A self-recursion rule-ref edge.
22    pub const SELF_RECURSION: u64 = (-0x300_i64) as u64;
23    /// Placeholder hash for a rule on a simple cycle.
24    pub const SIMPLE_CYCLE: u64 = (-0x400_i64) as u64;
25    /// An as-yet-unhashed referenced rule (only valid at the start).
26    pub const UNKNOWN: u64 = (-0x500_i64) as u64;
27}
28
29/// Mix several values into `seed` (incremental `HashCombine`).
30fn mix(seed: u64, values: &[u64]) -> u64 {
31    let mut s = seed;
32    for &v in values {
33        hash_combine_binary(&mut s, v);
34    }
35    s
36}
37
38/// Sorted edges of complete-FSM state `s` (rule/repeat/char all together).
39fn sorted_edges(grammar: &GrammarData, s: usize) -> Vec<crate::fsm::FsmEdge> {
40    let mut e: Vec<_> = grammar.complete_fsm.edges(s).to_vec();
41    e.sort_unstable();
42    e
43}
44
45/// Hash a fully-hashable FSM (all referenced rules already hashed, or
46/// self-recursive). Returns `(hash, new_state_id_mapping)`.
47pub fn hash_fsm(grammar: &GrammarData, fsm_index: i32) -> (u64, Vec<(i32, i32)>) {
48    let fsm = grammar.per_rule_fsms[fsm_index as usize]
49        .as_ref()
50        .expect("fsm present");
51    let mut old_to_new: BTreeMap<i32, i32> = BTreeMap::new();
52    old_to_new.insert(fsm.start() as i32, 0);
53    let mut queue: VecDeque<i32> = VecDeque::new();
54    queue.push_back(fsm.start() as i32);
55    let mut hash = 0u64;
56
57    while let Some(old) = queue.pop_front() {
58        let new_id = old_to_new[&old];
59        hash = if fsm.is_end_state(old as usize) {
60            mix(hash, &[new_id as u64, flag::END, flag::END, new_id as u64])
61        } else {
62            mix(
63                hash,
64                &[new_id as u64, flag::NOT_END, flag::NOT_END, new_id as u64],
65            )
66        };
67
68        let edges = sorted_edges(grammar, old as usize);
69        // First: rule/repeat-ref edges, ordered by (ref-hash, target).
70        let mut hash_and_target: BTreeSet<(i64, i32)> = BTreeSet::new();
71        for edge in &edges {
72            if edge.is_rule_ref() {
73                let rid = edge.ref_rule_id();
74                let h = ref_hash(grammar, fsm_index, rid);
75                hash_and_target.insert((h as i64, edge.target));
76            } else if edge.is_repeat_ref() {
77                let info = grammar.complete_fsm.repeat_edge_info(edge.aux_index());
78                let rid = info.rule_id as i32;
79                let base = ref_hash(grammar, fsm_index, rid);
80                let rh = mix(base, &[info.lower as i64 as u64, info.upper as i64 as u64]);
81                hash_and_target.insert((rh as i64, edge.target));
82            }
83        }
84        for (h, target) in hash_and_target {
85            assign(&mut old_to_new, &mut queue, target);
86            let tnew = old_to_new[&target];
87            hash = mix(hash, &[new_id as u64, h as u64, tnew as u64]);
88        }
89        // Then: char-range edges.
90        for edge in &edges {
91            assign(&mut old_to_new, &mut queue, edge.target);
92            let tnew = old_to_new[&edge.target];
93            if edge.is_rule_ref() || edge.is_repeat_ref() {
94                continue;
95            }
96            hash = mix(
97                hash,
98                &[
99                    new_id as u64,
100                    edge.min as i64 as u64,
101                    edge.max as i64 as u64,
102                    tnew as u64,
103                ],
104            );
105        }
106    }
107    (hash, old_to_new.into_iter().collect())
108}
109
110/// The hash of a referenced rule (or the self-recursion flag).
111fn ref_hash(grammar: &GrammarData, fsm_index: i32, ref_rule_id: i32) -> u64 {
112    if ref_rule_id == fsm_index {
113        flag::SELF_RECURSION
114    } else {
115        grammar.per_rule_fsm_hashes[ref_rule_id as usize]
116            .expect("referenced rule must already be hashed")
117    }
118}
119
120/// Renumber `target` in discovery order if not yet seen.
121fn assign(map: &mut BTreeMap<i32, i32>, queue: &mut VecDeque<i32>, target: i32) {
122    if !map.contains_key(&target) {
123        let new_id = map.len() as i32;
124        map.insert(target, new_id);
125        queue.push_back(target);
126    }
127}
128
129/// Partially hash an FSM: tolerated when up to one referenced rule is
130/// unhashed *and* that edge starts at the start state. `None` otherwise.
131pub fn partial_hash_fsm(grammar: &GrammarData, fsm_index: i32) -> Option<(u64, Vec<(i32, i32)>)> {
132    let fsm = grammar.per_rule_fsms[fsm_index as usize].as_ref()?;
133    let start = fsm.start() as i32;
134    let mut old_to_new: BTreeMap<i32, i32> = BTreeMap::new();
135    old_to_new.insert(start, 0);
136    let mut queue: VecDeque<i32> = VecDeque::new();
137    queue.push_back(start);
138    let mut hash = 0u64;
139
140    while let Some(old) = queue.pop_front() {
141        let is_start = old == start;
142        let new_id = old_to_new[&old];
143        hash = if fsm.is_end_state(old as usize) {
144            mix(hash, &[new_id as u64, flag::END, flag::END, new_id as u64])
145        } else {
146            mix(
147                hash,
148                &[new_id as u64, flag::NOT_END, flag::NOT_END, new_id as u64],
149            )
150        };
151
152        let edges = sorted_edges(grammar, old as usize);
153        let mut hash_and_target: BTreeSet<(i64, i32)> = BTreeSet::new();
154        let mut unhashed = 0;
155        for edge in &edges {
156            let rid = if edge.is_rule_ref() {
157                edge.ref_rule_id()
158            } else if edge.is_repeat_ref() {
159                grammar
160                    .complete_fsm
161                    .repeat_edge_info(edge.aux_index())
162                    .rule_id as i32
163            } else {
164                continue;
165            };
166            if rid == fsm_index {
167                hash_and_target.insert((flag::SELF_RECURSION as i64, edge.target));
168                continue;
169            }
170            match grammar.per_rule_fsm_hashes[rid as usize] {
171                Some(h) => {
172                    hash_and_target.insert((h as i64, edge.target));
173                }
174                None => {
175                    if !is_start {
176                        return None;
177                    }
178                    unhashed += 1;
179                    if unhashed > 1 {
180                        return None;
181                    }
182                    hash_and_target.insert((flag::UNKNOWN as i64, edge.target));
183                }
184            }
185        }
186        for (h, target) in hash_and_target {
187            assign(&mut old_to_new, &mut queue, target);
188            let tnew = old_to_new[&target];
189            hash = mix(hash, &[new_id as u64, h as u64, tnew as u64]);
190        }
191        for edge in &edges {
192            assign(&mut old_to_new, &mut queue, edge.target);
193            let tnew = old_to_new[&edge.target];
194            if edge.is_rule_ref() || edge.is_repeat_ref() {
195                continue;
196            }
197            hash = mix(
198                hash,
199                &[
200                    new_id as u64,
201                    edge.min as i64 as u64,
202                    edge.max as i64 as u64,
203                    tnew as u64,
204                ],
205            );
206        }
207    }
208    Some((hash, old_to_new.into_iter().collect()))
209}
metrale_grammar/grammar/functor/hash_walk.rs

metrale_grammar/grammar/functor/
hash_walk.rs
