cure_tree/
child.rs

1//! 子节点容器（内联优化）。
2
3/// 子节点容器：≤3 个孩子零堆分配（AST 绝大多数节点——
4/// Binary/Assign=2、Member/MethodRef=1、VarDecl≤1、Literal=0……
5/// 大语料 malloc 采样的剩余大头是每节点一次 Vec 堆分配）；
6/// ≥4 溢出到堆。Block/Call 大参数列表溢出属预期路径。
7///
8/// `Id` 需 `Copy + Default`（`Default` 作为空槽哨兵值；语言侧通常用
9/// `u32::MAX` 之类的非法下标 newtype）。
10#[derive(Clone, Debug)]
11pub struct ChildList<Id: Copy + Default> {
12    inline_len: u8,
13    inline: [Id; 3],
14    heap: Vec<Id>,
15}
16
17impl<Id: Copy + Default> Default for ChildList<Id> {
18    fn default() -> Self {
19        Self::new()
20    }
21}
22
23impl<Id: Copy + Default + PartialEq> PartialEq for ChildList<Id> {
24    fn eq(&self, other: &Self) -> bool {
25        self.as_slice() == other.as_slice()
26    }
27}
28
29impl<Id: Copy + Default> ChildList<Id> {
30    pub fn new() -> Self {
31        Self { inline_len: 0, inline: [Id::default(); 3], heap: Vec::new() }
32    }
33    pub fn from_vec(v: Vec<Id>) -> Self {
34        let n = v.len();
35        if n <= 3 {
36            let mut cl = Self::new();
37            for (i, id) in v.into_iter().enumerate() {
38                cl.inline[i] = id;
39            }
40            cl.inline_len = n as u8;
41            cl
42        } else {
43            Self { inline_len: 0, inline: [Id::default(); 3], heap: v }
44        }
45    }
46    pub fn as_slice(&self) -> &[Id] {
47        if self.heap.is_empty() {
48            &self.inline[..self.inline_len as usize]
49        } else {
50            &self.heap
51        }
52    }
53    pub fn len(&self) -> usize {
54        if self.heap.is_empty() {
55            self.inline_len as usize
56        } else {
57            self.heap.len()
58        }
59    }
60    pub fn is_empty(&self) -> bool {
61        self.len() == 0
62    }
63    /// 按索引替换（保持同一形态）。
64    pub fn set(&mut self, index: usize, new: Id) {
65        if self.heap.is_empty() {
66            self.inline[index] = new;
67        } else {
68            self.heap[index] = new;
69        }
70    }
71    /// 移除一个孩子（内联区左移；堆走 Vec::remove）。
72    pub fn remove(&mut self, index: usize) {
73        if self.heap.is_empty() {
74            for i in index..self.inline_len as usize - 1 {
75                self.inline[i] = self.inline[i + 1];
76            }
77            self.inline_len -= 1;
78        } else {
79            self.heap.remove(index);
80            // 缩回 ≤3：搬回内联
81            if self.heap.len() <= 3 {
82                let v = std::mem::take(&mut self.heap);
83                *self = Self::from_vec(v);
84            }
85        }
86    }
87    /// 区间替换（Splice 语义：删 [index, index+remove) 插 insert）。
88    pub fn splice(&mut self, index: usize, remove: usize, insert: Vec<Id>) {
89        let new_len = self.len() - remove + insert.len();
90        if new_len <= 3 && self.heap.is_empty() {
91            // 纯内联区间的手工搬移
92            let mut result: Vec<Id> = self.as_slice().to_vec();
93            let end = (index + remove).min(result.len());
94            result.splice(index..end, insert);
95            *self = Self::from_vec(result);
96        } else {
97            // 堆路径：先物化成 Vec，操作，再回填
98            let mut v = std::mem::take(&mut self.heap);
99            if v.is_empty() {
100                v = self.as_slice().to_vec();
101                self.inline_len = 0;
102            }
103            let end = (index + remove).min(v.len());
104            v.splice(index..end, insert);
105            *self = Self::from_vec(v);
106        }
107    }
108}
cure_tree/child.rs

cure_tree/
child.rs
