cure_engine/
walk.rs

1//! 迭代式遍历（显式栈，避免深树递归爆栈），并收集父指针表。
2
3use std::collections::HashMap;
4use std::hash::{BuildHasherDefault, Hasher};
5
6use crate::lang::Lang;
7
8/// 稠密整数句柄的快速定长 hasher（FxHash 风格）：`L::Id` 的 Hash 实现
9/// 通常只写一个 u32/u64，Sip13 的全量安全哈希在这里纯属浪费。
10/// 冲突安全性由 HashMap 的探测保证，这里只提供廉价混合。
11#[derive(Default)]
12pub struct IdHasher(u64);
13
14impl IdHasher {
15    #[inline]
16    fn mix(&mut self, v: u64) {
17        self.0 = (self.0.rotate_left(5) ^ v).wrapping_mul(0x517c_c1b7_2722_0a95);
18    }
19}
20
21impl Hasher for IdHasher {
22    #[inline]
23    fn finish(&self) -> u64 {
24        self.0
25    }
26    #[inline]
27    fn write(&mut self, bytes: &[u8]) {
28        for &b in bytes {
29            self.mix(b as u64);
30        }
31    }
32    #[inline]
33    fn write_u32(&mut self, i: u32) {
34        self.mix(i as u64);
35    }
36    #[inline]
37    fn write_u64(&mut self, i: u64) {
38        self.mix(i);
39    }
40    #[inline]
41    fn write_usize(&mut self, i: usize) {
42        self.mix(i as u64);
43    }
44}
45
46pub type IdBuild = BuildHasherDefault<IdHasher>;
47pub(crate) type IdMap<K, V> = HashMap<K, V, IdBuild>;
48/// 字符串集合（规则热路径）：同一快速 hasher。
49/// 借用字符串集合（规则热路径）：键借自 AST，零分配。
50pub type StrSet<'a> = std::collections::HashSet<&'a str, IdBuild>;
51
52/// 先序遍历的快照：id 列表 + 每个非根节点的 (parent, child_index)。
53///
54/// 快照在遍历时一次性取出；之后 apply 编辑不影响本次快照的正确性
55/// （arena 追加式，Id 永不失效；被改动节点的旧信息由“命中即重启扫描”策略规避）。
56pub struct Walk<L: Lang> {
57    pub ids: Vec<L::Id>,
58    pub(crate) parents: IdMap<L::Id, (L::Id, usize)>,
59    pub root: L::Id,
60}
61
62impl<L: Lang> Walk<L> {
63    pub fn parent(&self, id: L::Id) -> Option<L::Id> {
64        self.parents.get(&id).map(|p| p.0)
65    }
66    pub fn index(&self, id: L::Id) -> Option<usize> {
67        self.parents.get(&id).map(|p| p.1)
68    }
69}
70
71pub fn walk<L: Lang>(lang: &L, root: L::Id) -> Walk<L> {
72    let mut ids = Vec::new();
73    let mut parents: IdMap<L::Id, (L::Id, usize)> = HashMap::default();
74    // 栈元素: (节点, 父, 序号)
75    let mut stack: Vec<(L::Id, Option<(L::Id, usize)>)> = vec![(root, None)];
76    while let Some((id, par)) = stack.pop() {
77        if let Some((p, i)) = par {
78            parents.insert(id, (p, i));
79        }
80        ids.push(id);
81        let children = lang.children(id);
82        // 逆序入栈保证先序
83        for (i, &c) in children.iter().enumerate().rev() {
84            stack.push((c, Some((id, i))));
85        }
86    }
87    Walk {
88        ids,
89        parents,
90        root,
91    }
92}
cure_engine/walk.rs

cure_engine/
walk.rs
