# 持久化数据结构
Deft 的列表、映射、集合与带标签映射在 Clojure 意义上是持久化的：一次操作返回一个新值，旧值保持有效且不变，两个版本共享大部分内存。共享由两种结构完成——列表和集合使用 32 路向量 trie，映射使用 CHAMP 树——而一个运算符 `<<` 会走出纯模型，就地累加到一个绑定中。本篇介绍表示形式、写时复制规则，以及 `<<` 究竟有何不同。面向用户的 API 见 集合；分配与 GC 机制见 内存管理。
## 值语义与结构共享
每个集合值都是指向不可变堆对象的指针。像 `append`、`assoc` 或 `dissoc` 这样的操作会构建一个新对象，并共享改动未触及的每个节点：
def xs @{ 1 2 3 } def ys $xs set zs [append $xs 4] # zs is @{ 1 2 3 4 }, shares $xs's trie $xs # => @{ 1 2 3 } — unchanged $ys # => @{ 1 2 3 } — the same value, still valid
这一设计加上 内存管理 中描述的不移动 GC，带来三个性质：
- 旧版本始终可用。 任何持有先前版本的值都继续读取它；没有失效、没有读时复制、没有锁。
- 内存与增量成正比。 一个版本的代价是变更路径上的节点，而不是整个集合的一份副本。
- 无需写屏障。 回收器从不移动对象，因此共享节点可以被任何持有它的方读取——包括另一个运行时的线程读取被根引用的值（值仍只能通过复制跨堆传递；见 执行模型）。
可变数组（`[array ...]`）是有意留出的逃生通道：扁平、O(1) 的 `aset`、无共享。下文一切都关于持久化集合。
相等性按种类而定：列表和集合逐元素比较，而映射（以及带标签映射）按身份比较——两个分别构建、结构相等的映射并不 `==`，而同一个值读取两次则相等。
## 列表：32 路向量 trie
`@{ ... }` 构建一个 `ObjVector`。文档称其为列表；其形态是 Clojure 的持久化向量：
- count —— 元素数量（u32）。
- shift —— 以位为单位的 trie 深度；32 个或更少元素的向量为 0，之后是 5、10……每个 trie 层级消耗 5 个索引位，因此节点是 32 槽数组（`VEC_BITS = 5`）。
- root —— trie 根，当所有元素都能放进尾部时为 null。
- tail / tail_len —— 最后 1–32 个元素，扁平存放在 trie 之外，以便快速追加。
### 查找
对于 `idx`，一旦 count 达到 32，尾部起点为 `(count - 1) & ~31`；位于或超过该偏移的索引会直接读取尾部。否则，索引会一次五位地沿 trie 向下走到叶子——`(idx >> level) & 31`。即 O(log32 n)，对于 32 位 count 最多读取七个节点。
### 追加
`[append $xs v]` 是唯一只复制一条路径的向量操作，它分两种情况：
1. 尾部有空间（`tail_len < 32`）。分配一个新的向量外壳和一个包含 `tail_len + 1` 个元素的新尾部数组，最多复制 31 个值。trie 根原样共享。
2. 尾部已满。 将旧尾部复制进一个新的叶节点，只复制插入路径上的节点把它接进 trie（`vecPushTail`），再开始一个新的单元素尾部。兄弟子树与旧向量共享。如果 trie 在当前深度下已经达到容量，则增加一个新的根层级（`shift += 5`）。
因此单次追加的代价是一次路径复制——O(log32 n)——而重复追加均摊到每次 O(1)，因为每 32 次追加只有一次需要为 trie 付出代价。
### 并非每个操作都共享
只有 `append` 会做路径复制。`set-nth`、`insert-nth`、`remove-nth`、`slice`、`reverse`、`sort`、`flatten` 及其余操作都会生成扁平缓冲区并从头重建 trie（`makeVector` → `ObjVector.create`），代价为 O(n) 且没有共享。对于一次性重写这没问题，但循环调用 `set-nth` 是 O(n²)——应改用 `<<` 或转换器（transducer）来累加。
### 节点与 GC
每个 trie 节点都是一个固定大小的对象：一个 `VecTrieNodeHeader`，带有 32 个原始 u64 槽、一个代数戳（generation stamp）、一个每周期更新的 `valid_gen` 守卫，以及一个侵入式链表链接。叶槽存放 NaN 装箱的 `Value` 字。
所有节点都链接进 `heap.vec_trie_nodes`。清扫阶段通过遍历这一个链表来释放死亡节点，而不是递归遍历每个向量（否则共享节点可能有重复释放的风险）；标记阶段则遍历每个存活根，并用当前周期的代数给访问过的节点打戳。`valid_gen` 戳会在周期开始时刷新到每个头部，使查找和复制能够检测到过期的叶指针并返回 nil，而不是解引用已释放的内存——这道防线把上游的释放后使用变成泄漏，而不是崩溃。
## 映射：CHAMP
`%{ ... }` 构建一个由 CHAMP 树（Compressed Hash-Array Mapped Prefix-tree）支撑的 `ObjMap`，它是 HAMT 的演进。键被哈希为 64 位，每层消耗五位，因此一次查找最多向下 13 次。
### 结构形态
每个节点携带两个 32 位位图——`datamap` 用于内联键/值对，`nodemap` 用于子指针——后面跟着一个紧凑的内容数组：先是数据对，然后是子指针。这种布局正是 CHAMP 在查找上胜过普通 HAMT 的原因：常见情况（键内联存放）永远不会离开节点的缓存行。节点容量向上取整到下一个 2 的幂（最小为 2），使增长保持在一个分配器大小类别内。两个哈希在最后移位之前都相同的键会一起存放在碰撞节点（`is_collision`）中，线性扫描。
### 查找与更新
- `get` —— 测试 `datamap` 中的槽位，比较内联键，或经由 `nodemap` 向下；槽位缺失 → nil。O(log32 n)。
- `assoc` —— 覆盖一个内联对，或者（当哈希前缀与另一个键冲突时）把两个键一起下推进子节点，必要时创建子节点。只复制路径上的节点；每个未触及的子节点都与旧映射共享。总是会分配一个新的映射外壳，因此旧映射不受影响。
- `dissoc` —— 移除该对（内部调用 `ObjMap.without`）；收缩到只剩单个条目的子节点会被内联回父节点，没有条目的子节点则被丢弃。如果键不存在，则返回同一个映射值。
数据/子节点的转换保持形态规范：对于给定的键集，布局由哈希决定，因此对已存在的键重新 `assoc` 只会改写其值槽，而 `dissoc` 会及时折叠子节点，不会留下稀疏节点。
### 键与哈希
`Value.hash()` 按种类分派：
| 键种类 | 哈希 |
|---|---|
| 数字、布尔值、nil | 对 NaN 装箱后的位做 splitmix64 混合 |
| 字符串 | 对字节做 Wyhash，结果备忘在字符串对象上 |
| 关键字 | Wyhash，加盐，使 `:ok` 与 `"ok"` 落在不同槽位 |
| 其他对象 | 身份（指针） |
键按内容比较（`Value.eql`），因此任何不可变值都可以作键。在 `get`/`assoc`/`dissoc` 边界处，字符串键会经过一个有界的 128 项备忘表规范化为未驻留的动态关键字——关于为什么不把它们加入永久驻留表，见 内存管理。
### 迭代顺序
`keys`、`values`、`entries` 以及直接的 `for`/`each` 迭代都会遍历 trie：按哈希顺序，对给定的键集稳定，但不是插入顺序。在输出稳定性重要的地方，规范化的写入方会显式排序——`theme/save` 会对每个映射内的键排序——因此不要指望 trie 顺序能跨越文件边界。
### 分配与瞬态
节点分配先检查按桶划分的空闲链表，然后从 64 KB bump slab 中切分，最后回退到分配器。所有节点都链接进 `heap.champ_nodes`；清扫会把死亡节点回收进桶空闲链表，而不是归还给分配器，从而让复用保持在所属堆内（见 内存管理）。映射外壳来自一个专用池。
`TransientMap` 是可变的构建器（瞬态，transient）：
- 它首先分配一个编辑令牌（edit token）并共享持久化根。
- 第一次通过属于不同令牌的节点写入时，会复制该路径并打上该令牌的戳——写时复制。之后通过令牌拥有的节点写入则就地修改，内容只要还在节点的桶内就就地增长。
- `persistent()` 分配一个外壳、移交根并释放令牌——O(1) 冻结，无需重建。
映射字面量就是这样构建的（`ObjMap.create` 循环使用一个瞬态），语句位置的 `[assoc $m k v]`（融合为 `assoc_local`）、`<<` 的映射分支，以及 `reduce`/`into` 中的映射累加器也是如此（瞬态安装在 `g_reduce_transient` 中，并由 `nativeAssoc` 拦截）。
## 集合、带标签映射与元数据
集合复用向量布局：`makeSet` 构建一个 `ObjVector` 并把外壳的种类翻转为 `.set`。集合字面量在构建时去重，`in?`、`union`、`intersection`、`difference` 以及子集谓词都线性扫描底层向量。这带来两个实现上的后果：集合相等性是位置性的（相同成员但顺序不同则不相等）；而且由于 `.set` 标志位于外壳上，而追加/瞬态路径构建的是普通向量外壳，对集合使用 `<<` 和 `append` 会返回列表。当结果必须保持为集合时，请使用 `into ^{}` 或 `union`。
带标签映射（`%Tag{ ... }`）是一个薄包装：`ObjTaggedMap` 持有一个 `ObjMap` 外加一个最多 48 字节的名称缓冲区。操作会解包、修改映射、再重新包装（`rewrapTagged`），因此标签不增加 trie 方面的工作。
元数据（`with-meta` / `meta`）是一条旁路：映射、带标签映射、向量、集合、字符串和关键字都可以携带一个可选的 `meta` 指针。附加元数据只复制外壳并共享载荷，且载荷的相等性语义不变——携带元数据的关键字或字符串仍然能命中普通查找。
## `<<` 运算符
以上一切都描述纯值。`<<` 是例外：它就地追加到一个绑定，并在可能时绕过持久化复制。`[append $xs v]` 仍是它的纯函数兄弟：
def build {|| def out @{} for x in @{ 1 2 3 } { $out << ($x * 2) } # one transient for the loop $out } [build] # => @{ 2 4 6 } [append [build] 8] # pure: a new value, receiver unchanged
### 修改发生在哪里
编译器按接收者的位置（而非运行时类型）来降级 `<<`：
| 接收者 | 降级为 | 修改目标 |
|---|---|---|
| 函数局部 `$xs` | `append_local`（捕获的局部变量：`append_boxed`） | 该槽上的每帧瞬态 |
| 顶层 / 全局 `$xs` | `[append $xs v]` + 存回命名空间 | 绑定（别名保留旧值） |
| 字面量、字段访问、调用结果 | 普通的 `append` 调用 | 无——返回新值 |
对于局部变量，VM 维护一个与帧的局部变量平行的、惰性创建的 `transients` 数组。对某个槽的第一次追加会包装当前值：
- 列表得到 `TransientVector`——一份具有几何增长的扁平副本；
- 映射得到 `TransientMap`——共享根、写时复制。
后续追加会修改包装器，因此循环累加时不会触碰 trie。当局部变量被读取、函数返回或协程挂起时，包装器会被冻结回该局部变量（`flushFrameTransients`——这就是为什么 `$xs << 1; [await`
...]; $xs << 2` 不会丢失第一次追加）。`
常见形态会在编译期融合：`set x ($x << y)` 仍走追加快速路径，语句位置的 `$buf << [str ...]` 变成单条 `append_format_str` 操作码，语句位置的 `[assoc $m k v]` 变成 `assoc_local`。链式 `$xs << a << b << c` 会折叠为对底层局部变量的一系列顺序追加，整条链只冻结一次。
别名是安全的。瞬态从副本开始（向量），或对它触及的任何节点做写时复制（映射），因此别处持有的持久化值永远不会被修改——只有绑定移动到新值。捕获的局部变量会被装箱，因此通过闭包进行的追加对兄弟闭包可见，冻结时会写入箱子的值。
### 求值结果
由于 `<<` 是作用于绑定的运算符，它的值取决于形式。编译器对此有明确规定：
| 形式 | 求值为 |
|---|---|
| `$xs << v` 作为被丢弃的语句 | 无（栈上不留值） |
| 表达式位置的 `($xs << v)`，一次追加 | `v`——被追加的值 |
| 表达式位置的 `($xs << a << b)` 链 | 修改后的集合 |
| `set xs ($xs << v)` | `v`（并且 `$xs` 被修改） |
| `set xs ($xs << a << b)` | 修改后的集合 |
| `(@{} << v)`——非局部接收者 | 新列表 `@{ v }` |
两点注意：顶层/全局的存回只覆盖最内层的追加，因此对全局绑定的链式追加应拆成独立语句；另外，由于单次追加求值为被追加的值，想要集合的代码应读取绑定或使用 `[append ...]`。
### 开销
- 同帧累加（`for`/`while`，内联进帧中）：向量瞬态每次追加均摊 O(1)，然后在瞬态冻结时进行一次 O(n) 重建。这正是 `<<` 为之存在的形态。
- 闭包累加（`each`/`map` 主体）：每次调用都是一个独立的帧，因此捕获的累加器在每次返回时都会被冻结并重新复制——n 次追加实际上为 O(n²)。大规模累加应优先使用 `for`/`while` 循环、`reduce` 或 `transduce`。
- 向大列表追加一次：瞬态会预先复制整个列表，而 `[append ...]` 只会做 O(log32 n) 的路径复制。`<<` 只有在反复追加时才划算，追加一次并不划算。
## 快速参考
| 问题 | 答案 |
|---|---|
| `@{}`/`%{}`/`^{}` 可变吗？ | 不可变——操作返回新值；旧值不变 |
| `[append $xs v]` 会改变 `$xs` 吗？ | 不会——请用 `$xs << v` 更新绑定 |
| `$xs << v` 会改变指向旧值的其他引用吗？ | 不会——瞬态会复制/写时复制；只有绑定移动 |
| `<<` 与 `append` 有何不同？ | 对局部变量会融合为瞬态操作码并修改绑定；其表达式值因形式而异（见表格） |
| `[append $list v]` 是 O(1) 吗？ | O(log32 n)——路径复制；32 次追加均摊 O(1) |
| `$list << v` 更快吗？ | 累加时更快；读取/返回时的冻结对列表是 O(n)，对映射是 O(1) |
| `assoc` 会共享结构吗？ | 会——仅路径复制；未触及的节点是共享的 |
| `set-nth` 会共享结构吗？ | 不会——完整的扁平重建，O(n) |
| 映射键按插入顺序吗？ | 不是——trie/哈希顺序，确定但非插入顺序 |
| `<<` 会让集合保持为集合吗？ | 不会——它返回列表；请使用 `into ^{}` / `union` |
| 为什么我的 `each` 累加无法随规模扩展？ | 每次闭包调用都会冻结瞬态；请使用 `for`/`while` 或 `transduce` |