前阵子在看 rust-analyzer 的语法树实现，顺手把 rowan 源码翻了一遍。

rowan 是它背后的通用语法树库。它处理的正是 IDE 语法树里最麻烦的那几个要求：

• 如果节点保存父指针和绝对偏移，编辑后大量节点的位置都会失效
• 如果树要完全不可变，增量修改时又必须尽量复用旧结构
• 如果你还想保留空白、注释、错误节点，树会比传统编译器里的 AST 大得多
• 如果 IDE 每次敲键都要重建整棵“带父指针的树”，内存和分配成本都会很难看

红绿树就是为了解这组矛盾出现的。rowan 则是一个相当干净的实现。

红绿树到底在解决什么

红绿树这个名字来自 Roslyn。Eric Lippert 在介绍 Roslyn 时提到，团队最初需要同时满足几件事：不可变、可复用、能拿父节点、能拿绝对位置、还能支撑编辑器每次输入后的快速更新。把这些需求硬塞进一棵树里，会立刻撞上两个问题：

1. 子节点如果保存父指针，就很难在新树里复用到另一个父节点下面
2. 节点如果保存绝对位置，那么一次插入字符可能让后面大半棵树的位置都变化

Roslyn 的办法是把“语法事实”和“访问视图”拆开：

• green tree 只保存结构本身，不保存父指针和绝对位置
• red tree 在 green tree 之上按需构造，补上父指针、偏移和遍历能力

这样一来，编辑时真正可持久复用的是 green tree；用户和分析器平时操作的是 red tree。

到了 rust-analyzer 这里，这个思路又被拆成了三层：

1. GreenNode / GreenToken
2. SyntaxNode / SyntaxToken
3. AST 包装层

rust-analyzer 的文档里对这三层写得很清楚：green tree 只存结构；SyntaxNode 是带父子关系和偏移的访问视图；AST 再往上包一层类型。

rowan 的总体结构

如果只看 src/lib.rs，rowan 的主干其实很明确：

pub use crate::{
    api::{
        Language, SyntaxElement, SyntaxElementChildren, SyntaxNode, SyntaxNodeChildren, SyntaxToken,
    },
    green::{
        Checkpoint, Children, GreenNode, GreenNodeBuilder, GreenNodeData, GreenToken,
        GreenTokenData, NodeCache, SyntaxKind,
    },
    syntax_text::SyntaxText,
    utility_types::{Direction, NodeOrToken, TokenAtOffset, WalkEvent},
};

可以直接把它理解成三层 API：

• green/*：不可变、可共享的底层树
• cursor.rs + api.rs：给 green tree 加上父节点、偏移、兄弟节点、遍历等“编辑器友好”的访问接口
• ast.rs：在通用语法树之上再套一层强类型 AST

所以 rowan 本身更接近一套 CST 基础设施，但上面又能继续长出 AST。

第一层：green tree 只保存不可变语法事实

rowan 里的 green tree 是一棵无父指针、无绝对偏移、完全不可变的 n 叉树。

它的核心类型是：

• GreenNode
• GreenToken
• SyntaxKind

其中 SyntaxKind 只是一个轻量的 u16 标签：

pub struct SyntaxKind(pub u16);

也就是说，底层并不关心“这是 if 还是函数定义”，它只认一个轻量标签。具体语义交给上层语言。

GreenToken：叶子节点直接存文本

GreenTokenData 很简单，核心就是两件事：

• token 的 kind
• token 的原始文本

也就是说，rowan 是无损语法树。空白、注释、错误恢复出来的 token，都可以原样留在树里。只要把所有 token 文本按顺序拼起来，就能恢复源码。

这也是它和很多只关心语义的 AST 的区别：rowan 先把源码无损保留下来。

GreenNode：内部节点存 kind、总长度和孩子列表

GreenNodeHead 的字段也很少：

• kind
• text_len
• children

其中比较关键的是 text_len 和每个孩子的 rel_offset。rowan 没给节点存绝对位置，但它会在 green 节点里记录：

• 这个子树总共覆盖多少文本
• 每个孩子相对父节点起点的偏移

这样后面的红层只要知道父节点的绝对起点，就能沿着路径把位置算出来，不需要把绝对偏移硬塞进每个 green 节点。

green tree 为什么适合增量编辑

因为它不可变，所以“修改”这件事会表现为创建一棵带结构共享的新树，不会直接原地改旧树。

GreenNodeData::replace_child、insert_child、remove_child、splice_children 都体现了这个思路：它们返回的是一个新的 GreenNode。旧节点不动，新节点尽量复用未变化的子树。

对语法树这种通常比较浅的结构来说，更新成本基本落在受影响路径上，通常可以近似看成 O(depth)。

第二层：builder 和 cache 决定了 green tree 怎么被建出来

如果写过 parser，GreenNodeBuilder 会很好理解。它基本就是一个按深度优先顺序吐事件的构造器：

• start_node(kind)
• token(kind, text)
• finish_node()
• finish()

examples/s_expressions.rs 就是最直接的例子。parser 在识别到列表、原子、错误节点时，边解析边往 builder 里发事件，最后得到一棵 GreenNode。

Checkpoint / start_node_at

rowan 的一个很好用的小设计是 checkpoint() 和 start_node_at()。

它适合处理“我先解析出一段内容，之后才发现需要把它包一层节点”的情况。比如表达式解析里，先读到了左操作数，后面才发现遇到 +，这时可以回到 checkpoint，把已经产生的那部分 children 包进一个新的父节点。

这样 parser 不用提前造一堆临时节点，只是先记一个位置，后面再决定要不要包。

NodeCache：共享不只是理论上的

这里比较实在的一点是，rowan 不只是“理论上可以共享”，它真的做了节点驻留和复用。

NodeCache 里维护了两个表：

• tokens
• nodes

构建 token 时，如果 (kind, text) 一样，就直接复用已有 GreenToken。构建 node 时，如果节点 kind 和孩子序列一致，也复用已有 GreenNode。

原因也简单，语法树里重复东西太多：

• 重复的关键字
• 重复的标点
• 大量形状完全一致的小节点

源码里直接举了例子：这个文件里的所有 #[inline] 都可以共享同一个 green node。

有意思的是，NodeCache 没有“无脑缓存所有节点”。在 node_cache.rs 里可以看到，它只对孩子数不超过 3 的节点走哈希去重；更大的节点直接构造。这个取舍非常实际：

• 小节点重复率高，值得去重
• 大节点哈希和比较成本更高，未必划算

这很符合 rowan 的整体风格：它更关心 IDE 场景里是否划算，对概念上的完美感没那么执着。

第三层：访问层才是 rowan 真正“好用”的地方

如果只有 green tree，rowan 还只是个不错的不可变树实现。真正让它适合编辑器的是 cursor.rs 这层访问接口。

这个文件开头就把设计意图说得很直白：它实现的是一个建立在纯函数式 green tree 之上的游标式访问层。

这一层主要补了三样东西：

• 给节点补上父指针
• 给节点补上绝对偏移和 text_range
• 提供方便的遍历、兄弟节点、祖先节点、按偏移定位 token 等 API

SyntaxNode 并不拥有完整树

rowan 的 SyntaxNode 更接近游标，和那种把整棵红树缓存下来的做法不一样。注释里专门强调，NodeData 是短暂存在的：遍历过程中按需创建，不再被引用时就释放。

这样做的好处也很直接：

• 你平时只会持有少量当前关注的节点
• 常见遍历只会让“当前节点到根的路径”常驻
• 不需要像 Roslyn 那样把完整外观层节点大量缓存下来

rust-analyzer 文档也专门提到过这一点：它曾经用过带缓存的红层节点，后来换成 cursor，主要就是为了降低完整访问树的额外内存开销。

父指针和绝对偏移是按路径算出来的

创建 root 时，SyntaxNode::new_root 只拿到一个 GreenNode。之后访问孩子节点时，这层访问接口才会用：

• 当前父节点
• child 的 rel_offset
• child 在父里的 index

创建新的 SyntaxNode / SyntaxToken 视图。

所以绝对位置不属于 green tree 自带的信息，它来自红层沿着访问路径的逐步计算。

这其实就是红绿树最核心的拆法：

• green tree 负责“这段文本长什么样”
• red tree 负责“我站在这里怎么看它”

token_at_offset、covering_element 这类 API 非常像 IDE 需求

只看 api.rs 的方法名，也能看出它明显是朝 IDE 需求去的：

• token_at_offset
• covering_element
• next_token
• prev_token
• ancestors
• siblings_with_tokens
• preorder_with_tokens

这些 API 组合起来，正好覆盖编辑器里最常见的几种查询：

• 光标在某个字节位置时对应哪个 token
• 某个 range 落在哪个最深的节点或 token 上
• 我能不能从当前 token 往前后找语法邻居
• 我能不能快速往上找 enclosing node

做语法高亮、跳转、补全、重构时，这些接口基本都用得上。

rowan 里的“红”和传统的红树对象缓存有很大区别

第一次接触红绿树时，很容易脑补成“两棵完整树”。

rowan 这里走的是另一套形态。

它的红层更准确地说是一套按需物化的访问视图。cursor.rs 里的实现甚至明确把自己描述成一种游标式结构。相比 Roslyn 那种会缓存红层子节点的外观层，rowan 更偏向：

• green tree 长期存在
• red node 临时创建
• 只保留当前路径和少量活跃节点

这也解释了为什么它很适合 rust-analyzer 这种场景。

可变树支持：clone_for_update 不会打破 green tree 的不可变性

还有个挺实用的点：它支持从不可变语法树克隆出一个可更新视图。

对应 API 是：

• SyntaxNode::new_root_mut
• clone_for_update
• detach
• splice_children

不过能变化的是访问层的那套关系，green tree 本身保持不变。底层真正发生的事情，仍然是函数式地创建新 green node，再把受影响的路径重新接起来。

所以它可以理解成下面这个过程：

1. 先克隆出一套可更新的访问层关系
2. 在访问层做 detach / attach / splice
3. 底层用新的 green node 重建受影响路径

这也是为什么 SyntaxNode::replace_with 最终返回的是 GreenNode，并且复杂度与树深度相关。

AST 层：rowan 不替你定义语言，但给了你一套零成本包装方式

光有 untyped syntax tree 还不够。做语义分析时，我们通常希望看到的是：

• FnDef
• Expr
• NameRef
• IfExpr

你更希望看到的是带语义名字的节点，不会想直接面对一堆裸 SyntaxKind。

rowan 没有自己发明一套 AST，ast.rs 里给的是一个 AstNode trait，让上层自己包。

这样做有两个直接好处。

1. 通用树层和语言层彻底分离

rowan 只关心：

• 你有一个 Language
• 这个语言能把自己的 kind 和底层 SyntaxKind(u16) 互转

于是 api.rs 里的 SyntaxNode<L>、SyntaxToken<L> 就能对任意语言工作。

2. 强类型 AST 包装几乎没有额外成本

ast.rs 里写得很明确：AST node 和 SyntaxNode 具有相同表示，本质上就是透明包一层。因此从 syntax node cast 到 AST node，不需要复制子树。

这一层我觉得做得挺舒服：底层继续保持通用和无损，上层又能拿到强类型接口。

examples/s_expressions.rs 里那几个 Atom、List、Root 的包装，就是最小可运行版本。

SyntaxNodePtr 很像一种“稳定但不永久绑定对象身份”的引用

ast.rs 里另一个值得注意的类型是 SyntaxNodePtr。

它保存的是下面这两样，不直接抓节点对象本身：

• 节点 kind
• 节点 TextRange

之后需要时，再在 root 上重新解析出对应节点。

这对 rowan 很重要，因为它的 syntax node 本来就不适合长期持有。更自然的用法是记住位置，需要时再从 root 恢复。

当然，这也意味着它不能用于 mutable tree。源码里直接有断言，因为一旦发生编辑，原先的 range 就可能失效。

rowan 更接近 CST 基础设施，也能继续长出 AST

这点在 rust-analyzer 文档里也很明显：

• syntax tree 要保留空白和注释
• 错误输入也要尽量形成树
• parser error 不直接塞进树里，但错误片段会用 ERROR 节点表示
• 语法树和 parser 要彼此隔离，方便独立演化

所以 rowan 不能简单理解成“编译原理课 AST 的 Rust 版”。把它看成编辑器基础设施会更贴切。

几个读下来印象比较深的点

1. 它把“可持久性”和“易遍历性”拆到了两层

green tree 负责共享和稳定，访问层负责父指针和偏移。拆开之后，很多冲突自然就没那么尖锐了。

2. 它真的在为 IDE 场景做优化

NodeCache 的去重策略、显式 token 文本、token_at_offset、短暂存在的访问节点、可更新副本，这些都很像真实 IDE 需求倒逼出来的实现。

3. 它刻意不把语言知识塞进库里

rowan 只提供通用机制，语言特定 AST 留给上层，这样复用边界比较清楚。

4. 它接受复杂性，但把复杂性收束在边界里

最典型的例子就是 cursor.rs 开头那句“utterly and horribly unsafe”。读完代码以后会觉得，这种复杂度确实很难完全省掉，区别只是把它摊得到处都是，还是集中封装在一层边界里。

结语

我读完 rowan 之后最大的感受是，现代编辑器里的语法树和课本里的 AST 已经差很多了。它不只是 parser 的输出，还是一个要长期支撑跳转、补全、重构、错误恢复和增量分析的数据结构。

红绿树这套办法的价值也在这里：它确实把几件互相冲突的事情拆开了。rowan 则把这套拆法落成了一个很实用的库，读起来也能看出不少 rust-analyzer 的工程取向。

参考资料

• Rowan README
• Syntax in rust-analyzer
• Persistence, façades and Roslyn’s red-green trees
• Use the .NET Compiler Platform SDK syntax model