三段拼接 · 引用相等 · 复用率

增量解析：只重解析脏区

一份三千行的文件，敲下一个字符后有多少语法结构发生了变化？通常是一条语句。全文重解析要重做另外两千九百九十九行的工作。

增量解析的目标就是把这部分省掉。它是 tree-sitter 的看家本领，也是 rust-analyzer、Roslyn、以及任何要在按键之间完成响应的语言服务器的必需品。

1 · 编辑点两侧的切分

一次编辑由三个数描述：替换区间 $[\text{start}, \text{end})$ 与插入文本。它把旧文档切成三段：

旧：│ prefix（编辑前） │ middle（相交） │ suffix（编辑后） │
        ↓ 复用             ↓ 仅此段重解析   ↓ 复用（位移由红树吸收）

关键在 suffix：它的内容没变，但位置整体位移了。若树的节点存绝对位置，这段就必须全部重建。而绿节点只存相对宽度（见无损语法树一页定理 2.1），位移对它们于是不构成任何改动：同一批绿对象直接挂到新树上，绝对位置由红树遍历时累加得出。

图 1-1 · 一次编辑的复用情况，全部来自 @vega/parsing/incremental 的真实 reparse。上表给出顶层元素的去向，下方进度条是节点级复用率。读数条同时核对两条硬保证：与整篇重解析引用相等，以及 round-trip 仍然无损。可切换五种编辑位置观察复用率变化。

2 · 复用边界的对齐条件

脏区的两端不能随便取。本仓库的实现要求边界同时满足三个条件，否则向外扩展直到满足（单调外扩必然收敛，最坏退化为整篇重解析，仍然正确）：

token 边界：新坐标必须落在新文本的某个 token 起始处。原因是插入的字符可能与邻接 token 合并：紧贴 zz 插入 xy 得到 xyzz，是一个标识符而非两个，新的 token 边界于此落进了旧元素内部。

元素边界：旧坐标必须落在旧顶层元素的边界上，否则左右两侧无法整块复用。

parse-state 对齐：复用边界之前的最后一个实义 token 必须是 ;，即处在「语句起始」这个状态。这一条最容易被忽略：即便文本边界对齐，若 parser 在该处的内部状态与上次不同，复用出来的子树就可能挂错位置。

警示 · 第三条是增量解析最常见的正确性陷阱。tree-sitter 的做法是把 lexer 与 parser 的状态一并记入节点，复用时比对状态是否相同；简化实现则像本仓库这样，只在一个明确的同步状态（语句边界）上允许复用。跳过这一检查的实现会在特定编辑序列下产出与全量重解析不同的树，而这类缺陷极难复现，它依赖编辑历史，而非当前文本。

3 · 可断言的保证

增量解析的正确性不适合靠例子验收，因为它依赖编辑历史。两条不变量把它变成可自动检查的性质：

正确性：同一个 interner 下，增量重解析的结果与「对新文本整篇重解析」引用相等。这条断言之所以能写成一次 === 比较，靠的正是无损语法树一页的结构共享：结构相同则对象相同。

有效性：节点复用率大于零，且局部编辑下应接近 1。这条排除了「实现虽然正确但每次都全量重建」这种退化，那样的实现会通过全部正确性测试。

图 1-1 的读数条把两条并列显示。五种编辑实测的节点复用率：改一个字面量 95%，改整行 90%，末尾追加一句 96%，开头插入一句 91%，跨两条语句的编辑 82%。规律很清楚：脏区越大复用率越低，而位移本身不影响复用（开头插入让后续四条语句全部位移，复用率仍有 91%）。五种编辑下引用相等与 round-trip 两项断言全部通过。

4 · 粒度的取舍

本仓库的实现是顶层元素粒度：脏区按语句对齐，一条语句要么整体复用要么整体重解析。这是最小可用的版本，也是最容易保证正确的版本。

更细的粒度可以复用语句内部的子树，例如改动 aa + bb 里的 bb 时保留 aa 那棵子树。收益是重解析范围更小，代价是要在树上做自顶向下的下潜，且每层都要重新检查前述三处对齐。tree-sitter 走的是这条路，它的节点自带足够状态信息支持任意层级的复用判断。

另一个维度是批量编辑。真实编辑器一次可能提交多处改动（多光标、查找替换、格式化）。逐个应用是正确的但浪费，每次都要重新算对齐。工业实现通常把多个编辑合并成一组，一次算出所有脏区再统一重解析。

注 · 增量的收益依赖「编辑是局部的」这个前提。若一次改动确实触及全文（改缩进风格、批量重命名），增量解析的开销比全量重解析更大，它要为每处改动做对齐检查。成熟实现于是都有一条退化路径：脏区超过某个比例就直接全量重解析。

5 · 与容错的关系

增量与容错是编辑器 parser 的两条腿，且互相依赖。

编辑过程中的文档大部分时间不合法（见容错解析一页），增量重解析的输入常常是有错的文本。这要求两件事：出错的那段仍要产出节点（否则树上会出现空洞，后续编辑无法在此对齐），且错误节点的边界要稳定（否则每次按键都会让脏区扩散）。

反过来，容错的质量也依赖增量：一处错误若导致整棵树重建，编辑器就会在每次按键时丢失全部缓存的语义信息。两者共同的设计目标是局部性：一处改动、一处错误，影响面都要限制在最小范围内。

6 · 参考文献

Wagner, T. A., & Graham, S. L. (1998). Efficient and flexible incremental parsing. ACM Transactions on Programming Languages and Systems, 20(5), 980–1013.
Brunsfeld, M. (2018). Tree-sitter: A new parsing system for programming tools. Strange Loop conference presentation.
Ghezzi, C., & Mandrioli, D. (1979). Incremental parsing. ACM Transactions on Programming Languages and Systems, 1(1), 58–70.