无损语法树：红绿两层
解析流水线 一页给 AST 的定义里有一句：不记源码里的空白、注释与多余的分组括号。这对编译器是优点，语义相同的写法产出相同的树。但对另一类工具是致命的。
formatter 要在改动一处的同时保持其余排版；重构工具要把 aa 改名为 width 而不动对齐与注释；语言服务器要根据光标偏移找到对应节点。这些都要求树能逐字节还原源码。
1 · trivia 进树
定义 1.1（无损语法树） 无损语法树（concrete syntax tree，CST）把空白与注释（统称 trivia）作为普通 token 保留在树里。「全树 token 文本顺次拼接」由此恒等于原始源码，这条性质称为 round-trip。
round-trip 是这类树的硬验收条件：它可以对任意输入自动检查，不需要人工写期望值。图 1-1 的读数条把它作为一项常驻断言。
@vega/parsing/cst 的真实模块。树上角标是该节点覆盖的字符宽度；可切换是否显示 trivia，对照同一棵树在「无损」与「AST 视角」下的差别。末表验证结构共享与 GreenBuilder 的三个动作。2 · 红层与绿层的分工
设计对标 rust-analyzer 的 rowan，也是 Roslyn 与 tree-sitter 的共同地基。核心是把两类信息分开。
绿树不可变，只存相对信息：节点种类、子元素、覆盖宽度。它不知道自己的绝对位置。这一点是刻意的：不知道位置，同一棵子树才能出现在多处而无须复制。
红树是绿树加上绝对 offset 与父指针的惰性视图。求 span、定位、上溯父节点都在红层完成。一棵绿树可以派生多个红视图，各自带不同 offset 互不干扰。
定理 2.1 绿节点不含绝对位置，是「同一棵子树可在多处共享」的充要前提。
必要性：若绿节点存绝对 offset，则位置不同的两处即便结构相同也不能共用同一对象。充分性：宽度信息足以在遍历时累加出任意节点的绝对位置，红层可以按需算出位置而不必存。
这条性质的直接后果就是下一页的增量解析：编辑点之后的语句整体位移时，它们的绿子树零改动，位移由红树遍历吸收。
3 · 结构共享与 O(1) 判同
绿树的构造走一张 interner 表（hash-consing）：造节点前先按「种类加各子元素身份」查表，命中就复用。结构相同的子树在内存里因此只有一份。
两个收益。一是省内存，大文件里海量重复的空白与标点不再各存一份。二是引用相等即结构相等：a === b 就能
判定两棵子树完全一样，无须深比较。
图 1-1 末表用 a = 1;a = 1; 直接演示：同一个 interner 下解析，两条相同语句的绿子树引用相等。增量解析就是靠这个判据决定「这棵子树没变，直接复用」。
4 · 绿树构造 API
绿树的构造 API 是游标式的：startNode(kind) 开一个节点，token(kind, text) 往当前节点塞叶子，finishNode() 收口并挂到父节点。增量解析另需一个 addExisting(el)，用来直接复用一棵已有绿子树。
这套 API 的形状值得注意：它不要求调用方持有树的引用，只要求按正确顺序发出事件。parser 因此可以是纯流式的：一边扫 token 一边发 token() 与 startNode()，无须回头修改已建好的部分。tree-sitter 与 Roslyn 的增量重解析都建立在这个形状上。
5 · rename 与 formatter
图 1-1 的 rename 演示了无损树的实际价值：把 aa 改成 width 之后，空白、注释与对齐一字未动。这在 AST 上做不到：AST 上重命名之后要重新生成文本，而生成器不知道原来的排版。
同一性质支撑 formatter 的「最小改动」策略：只重排被改动的那部分，其余原样输出。prettier 一族的做法相反（全文重排），它需要一份完整的排版规则，而无损树加最小改动的路线只需要「改了什么」的规则。
注 · trivia 的归属是这类实现里最琐碎也最容易出错的部分。一段注释该挂在它前面那条语句上，还是后面那条？rowan 与 Roslyn 的约定不同（前者倾向后随、后者区分 leading 与 trailing trivia），而这个选择直接决定「把一条语句连同它的注释一起删掉」这类重构的行为是否符合直觉。本仓库的实现把 trivia 一律作为普通 token 留在它出现的位置上，不做归属判断：这足以保证 round-trip，但把归属问题留给了调用方。
6 · 参考文献
- Matklad (Aleksey Kladov). (2020). Rust analyzer syntax trees & rowan crate documentation.
- Neal, D., & the Roslyn team. (2014). Roslyn overview: Syntax trees and trivia. Microsoft.
- Brunsfeld, M. (2018). Tree-sitter: A new parsing system for programming tools. Strange Loop conference presentation.