Amber Tree: 介于Rowan红树和绿树之间的中间方案

# Amber Tree：介于红树与绿树之间的中间方案 来源：https://blog.gplane.win/posts/introducing-amber-tree.html ## ¶ (https://blog.gplane.win/posts/introducing-amber-tree.html#Problems-of-rowan-red-tree-and-green-tree)红树与绿树的问题 Rowan 提供了两种语法树： - **红树**：功能丰富，API 友好。它不仅能遍历子节点和词素，还能通过父引用遍历父节点和兄弟节点。然而，这些父引用会产生循环引用，因此节点必须堆分配并用 `Rc` 包装，以减少克隆开销。 - **绿树**：性能更好，但有所取舍。你只能访问子节点，且 API 不直接区分节点和词素——它返回 `NodeOrToken` 枚举，使用起来不太方便。绿节点也不存储文本范围，因此无法知道节点在源码中的位置。 值得注意的是，在 rowan 中，红树和绿树并非两个独立结构。它们是同一底层数据的不同视图：红树本质上是绿树的一个包装。 在我的项目 `wasm-language-tools` (https://github.com/g-plane/wasm-language-tools) 中，大多数用例不需要向上遍历到父节点或兄弟节点。我使用红树主要是因为它的 API 更方便，并且提供了文本范围。那么，能否设计一种语法树，提供足够友好的 API 和文本范围支持，同时不考虑父/兄弟遍历，并接近绿树的性能？ 当然可以。事实证明这比你想象的要简单得多。由于它的能力介于红树和绿树之间，我称之为“琥珀树”。 ## ¶ (https://blog.gplane.win/posts/introducing-amber-tree.html#Implementation)实现 下面是琥珀节点的定义： ```rust #[derive(Clone, Copy, PartialEq, Eq, Hash)] pub struct AmberNode<'a> { green: &'a GreenNode, range: TextRange, } ``` - `green`：持有对绿节点的引用，使琥珀节点轻量级。借助 Rust 的借用检查器，`AmberNode` 的生命周期与其 `GreenNode` 绑定，确保内存安全且没有运行时开销。 - `range`：存储节点的源码位置，解决了绿节点缺少文本范围信息的问题。 两个字段都是 `Copy` 的（`GreenNode` 本身不是 `Copy`，但引用是），因此 `AmberNode` (https://docs.rs/wat_syntax/latest/wat_syntax/struct.AmberNode.html) 也能自然地实现 `Copy`。 从这里开始，我们可以实现一些需要的 API。由于持有对绿树的引用，遍历到子节点或更深的后代节点仍然高效且廉价。 我用琥珀树替换了语言服务中之前使用红树的部分。请注意，这些基准测试对比的是我自己优化过的红树实现（不是原始的 rowan 实现），因此基线已经相当调优。 | 基准测试 | 之前 | 之后 | 变化 | | --- | --- | --- | --- | | **未改变文本** | 15.469 μs | 7.609 μs | ↓ 50.8% | | **已改变文本** | 224.73 μs | 172.39 μs | ↓ 23.3% | ## ¶ (https://blog.gplane.win/posts/introducing-amber-tree.html#Improving-formatter)改进格式化器 `wat_formatter` (https://crates.io/crates/wat_formatter) 是一个用于 WebAssembly 文本格式（WAT）的代码格式化器——类似于 Rust 的 `rustfmt`，但用于 `.wat` 文件。`wat_formatter` (https://github.com/g-plane/wasm-language-tools/tree/main/crates/formatter) 很少需要访问父节点或兄弟节点，因此它是琥珀树的完美候选。这次切换开启了一个重要的二次优化。 在红树中，`SyntaxToken` 的文本存储在堆上，其生命周期与 token 本身解耦。这意味着我无法直接将 `&str` 传递给 `tiny_pretty` (https://docs.rs/tiny_pretty)；我必须调用 `.text().to_string()`，导致不必要的堆分配和字符串拷贝。 在琥珀树中，token 文本的生命周期直接与节点持有的绿树引用绑定。这样我就可以直接将 `&str` 传递给 `tiny_pretty` (https://docs.rs/tiny_pretty)，零分配。 由于红树中 `SyntaxToken` 的设计，token 文本（即 `&str`）的生命周期与 `SyntaxToken` 本身的生命周期无关，因此我们无法直接将那个 `&str` 传递给 `tiny_pretty` (https://docs.rs/tiny_pretty)。为了解决这个问题，我们不得不调用 `.text().to_string()`，但这引入了堆分配和字符串拷贝，降低了性能。现在使用琥珀树，token 文本的生命周期与 token 本身的生命周期一致，因为琥珀 token 持有对 `GreenToken` 的引用，我们可以直接使用琥珀 token 返回的 `&str`。 结果呢？格式化器的执行时间从大约 **85.191 μs** 下降到 **~34.808 μs**——时间减少了约 **59%**，或者说大约 **2.4 倍加速**。 ## ¶ (https://blog.gplane.win/posts/introducing-amber-tree.html#Conclusion)结论 通过牺牲向上遍历的能力，琥珀树提供了一个甜区：红树的人机工程学，以及接近绿树的性能。 更多细节和实现可以在 `wasm-language-tools` (https://github.com/g-plane/wasm-language-tools) 中的 pull request #36 Rewrite rowan with our own implementation (https://github.com/g-plane/wasm-language-tools/pull/36) 中找到。