Amber Tree：在 Rowan 的 Red Tree 与 Green Tree 之间寻找平衡点

背景

在构建语言工具（Language Tools）时，语法树（Syntax Tree）的选择至关重要。Rowan 是一个广泛使用的 Rust 库，用于构建高效、不可变的语法树。它提供了两种核心数据结构：Red Tree 和 Green Tree，二者各有优劣，但也存在明显的局限性。

Red Tree 功能丰富且 API 友好。它允许开发者不仅遍历子节点和 Token，还能通过父节点引用向上遍历至父节点和兄弟节点。然而，这种双向引用导致了循环引用（Cyclic References），使得节点必须堆分配（Heap-allocated）并使用 Rc（引用计数智能指针）进行包装，以减少克隆开销。这种设计虽然灵活，但带来了内存管理的复杂性和一定的性能损耗。

Green Tree 则提供了卓越的性能，但做出了诸多妥协。它仅支持向下访问子节点，API 不直接区分节点（Node）和 Token，而是返回一个 NodeOrToken 枚举，这在日常开发中显得颇为笨拙。此外，Green 节点不存储文本范围（Text Range），导致无法直接得知节点在源代码中的具体位置。

值得注意的是，在 Rowan 的实现中，Red Tree 和 Green Tree 并非两个独立的数据结构，而是同一底层数据的不同视图：Red Tree 本质上是对 Green Tree 的封装。

对于许多应用场景（如作者的项目 wasm-language-tools），并不需要向上遍历父节点或兄弟节点。开发者通常使用 Red Tree 主要是为了其便捷的 API 和文本范围支持。因此，作者提出了一种新的设计思路：能否设计一种语法树，在不需要父/兄弟节点遍历的前提下，既拥有友好的 API 和文本范围支持，又能接近 Green Tree 的性能？

核心内容

为了解决上述痛点，作者提出了 Amber Tree（琥珀树），一种介于 Red Tree 和 Green Tree 之间的折中方案。

1. Amber Tree 的设计与实现

Amber Tree 的核心定义非常简洁，旨在通过轻量级的设计实现高性能与易用性的平衡。其节点结构定义如下：

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct AmberNode<'a> {
    green: &'a GreenNode,
    range: TextRange,
}

该结构包含两个关键字段：

• green: 持有对 GreenNode 的引用。这使得 Amber 节点极其轻量。得益于 Rust 的借用检查器，AmberNode 的生命周期与其持有的 GreenNode 紧密绑定，从而在无需运行时开销的情况下确保了内存安全。
• range: 存储节点的源代码位置（Text Range）。这一设计解决了 Green 节点缺乏文本范围信息的缺陷，使得开发者可以直接获取节点在源码中的起始和结束位置。

由于这两个字段都是 Copy 类型（GreenNode 本身不是 Copy，但其引用是），AmberNode 也天然具备 Copy 特性，进一步降低了复制成本。

从实现角度看，由于持有对 Green Tree 的引用，向子节点或更深层次后代节点的遍历依然保持廉价和高效。作者将项目中原本使用 Red Tree 的部分逻辑替换为 Amber Tree，并进行了基准测试。需要注意的是，这里的基准测试对比的是作者自己优化过的 Red Tree 实现（而非原始的 Rowan 实现），因此基线性能已经相当高。

2. 性能优化案例：WAT 格式化器

为了验证 Amber Tree 的实际效果，作者将其应用于 wat_formatter，这是一个用于 WebAssembly 文本格式（WAT）的代码格式化器，类似于 Rust 的 rustfmt。

wat_formatter 极少需要访问父节点或兄弟节点，因此是 Amber Tree 的理想应用场景。这次替换不仅实现了直接的性能提升，还解锁了重要的次要优化。

Red Tree 的性能瓶颈： 在 Red Tree 中，SyntaxToken 的文本内容存储在堆上，且其生命周期与 Token 本身解耦。这意味着当调用格式化库 tiny_pretty 时，无法直接传递 &str，必须调用 .text().to_string()。这一操作引入了不必要的堆分配和字符串拷贝，严重降低了性能。

Amber Tree 的优化方案： 在 Amber Tree 中，Token 文本的生命周期直接绑定于节点所持有的 Green Tree 引用。这使得我们可以直接将 &str 传递给 tiny_pretty，实现了零分配（Zero Allocations）。

由于 Red Tree 中 SyntaxToken 的设计限制，其文本（&str）的生命周期与 SyntaxToken 本身无关，导致无法直接传递。而 Amber Token 持有对 GreenToken 的引用，其文本生命周期与 Token 本身一致，从而允许直接使用 Amber Token 返回的 &str。

3. 量化成果

这一优化带来了显著的性能提升：格式化器的执行时间从约 85.191 µs 降低至约 34.808 µs。这意味着执行时间减少了约 59%，速度提升了约 2.4 倍。

关键要点

• 定位明确：Amber Tree 旨在填补 Red Tree（功能全但重）与 Green Tree（快但难用）之间的空白，适用于不需要向上遍历（父/兄弟节点）的场景。
• 轻量级结构：通过持有 GreenNode 引用和存储 TextRange，Amber 节点实现了 Copy 语义，兼具内存安全性和低开销。
• 解决生命周期痛点：Amber Tree 解决了 Red Tree 中 Token 文本生命周期与节点解耦的问题，允许直接传递 &str，避免了不必要的堆分配和字符串拷贝。
• 显著的性能收益：在 wat_formatter 的实际应用中，Amber Tree 带来了约 2.4 倍的速度提升（执行时间减少 59%）。
• 实现简单：Amber Tree 的实现逻辑比预期简单得多，证明了在特定约束下简化数据结构的有效性。

意义与影响

Amber Tree 的提出展示了在系统级编程中，通过精确分析业务需求来优化数据结构的重要性。对于大多数语言服务（Language Service）而言，向上遍历父节点的需求并不高频，强行使用 Red Tree 往往是一种性能浪费。

这一设计为 Rust 生态中的语言工具开发者提供了一个新的选择：在不需要复杂导航功能时，可以采用类似 Amber Tree 的轻量级封装，在保持 API 易用性的同时，获得接近底层 Green Tree 的性能。这不仅提升了代码格式化器等工具的效率，也为构建更高效的编译器前端和静态分析工具提供了新的思路。

更多详细的实现细节和代码讨论，可参考作者提交的相关 Pull Request：#36 Rewrite rowan with our own implementation in wasm-language-tools。