AST-grep 如何使用 Rust 重写 Tree-sitter 并使其速度提升 30%

# 用 Rust 重写 Tree-sitter 并使其提速 30% 的方法 来源: https://astgrep.com/blog/tree-sitter-rust-rewrite *系列第 1 部分，共 4 部分——完整冒险* ast-grep 用 Rust 重写了 Tree-sitter 的 C 核心，并由 AI 编写代码。新核心在解析、读取完整语法树以及 ast-grep 自身运行上都更快。（标题中的“30%”仅针对解析器；端到端来看，ast-grep 大约快了 22%。） 源代码仓库：HerringtonDarkholme/tree-sitter (https://github.com/HerringtonDarkholme/tree-sitter)。 在展示数据之前先做两个快速介绍。ast-grep——本博客所属的结构化代码搜索工具——通过语法而非文本来搜索代码，因此它处理的每个文件都必须首先被解析成语法树。Tree-sitter (https://tree-sitter.github.io/) 是构建该树的解析框架：你提供语法定义，它就能为这种语言生成一个快速的解析器。Tree-sitter 诞生于编辑器领域，如今驱动着庞大的语法解析器和工具生态系统。 Rust 核心运行时与 C 的性能对比 **性能与峰值 RSS。** 吞吐量经过归一化处理，使得未修改的 C 构建（“C / normal”）得分为 100；数值越高越好。RSS 是峰值常驻内存，原始解析行显示为范围值，因为它在基准测试的不同语言文件上有所变化。大纲行是 ast-grep 的实际工作负载：解析仓库中的每个文件，然后遍历每个完整的语法树以提取结构大纲。 基准测试 | C / normal | Rust | 差异 --- | --- | --- | --- 原始解析 | 吞吐量: 100<br>RSS: 8.48–21.41 MiB | 吞吐量: 129.74<br>RSS: 8.42–25.70 MiB | +29.74% 吞吐量<br>+20.0% RSS 上限 树遍历 | 吞吐量: 100<br>RSS: 20.38 MiB | 吞吐量: 110.16<br>RSS: 22.20 MiB | +10.16% 吞吐量<br>+8.9% RSS 完整的 ast-grep 大纲 | 用户 CPU: 1.233 s<br>RSS: 26.52 MiB | 用户 CPU: 0.960 s<br>RSS: 34.43 MiB | −22.2% 用户 CPU<br>+29.8% RSS Rust 在每一个解析器和遍历测试中都胜出，并且 ast-grep 生成了完全相同的大纲。内存是权衡的代价：在 ast-grep 运行时，Rust 构建多用了约 8 MiB。在更大的 TypeScript 压力测试用例——TypeScript 编译器仓库的测试基线树，也是本项目的内存压力测试——上，其峰值达到 **91.2 MiB**。这个数字是成果而非妥协：项目早期，同样的用例峰值曾超过 1 GiB。 这个结果并非上游 Tree-sitter 的 1:1 替代。它是一个更狭义的运行时，专为分析完整文件快照的 AI 编码代理而构建： - 已有的生成式语言和解析器仍然兼容。 - 移除了对 WebAssembly 编译语言的原生加载以及增量旧树复用。 - 兼容性仍然需要大量裸指针和 `unsafe` 代码块。 这样的边界在保持语法解析器生态系统对代理式编程有用的同时，移除了目标工作负载不需要的编辑器特定机制。 这就是结局。达到这一目标的过程则是另一回事。 ## 为什么要重写 Tree-sitter？ (https://astgrep.com/blog/tree-sitter-rust-rewrite#why-rewrite-tree-sitter) 每一次严肃的 ast-grep 性能调查最终都指向同一个地方：**Tree-sitter**。 ast-grep 可以让它的规则更快。它可以剪枝工作、缓存配置，并避免访问无关的语法。但每个文件仍然必须先成为语法树，而 Tree-sitter 负责构建这棵树。解析器既是基础，也日益成为天花板。 多年来我一直梦想着重写或深度优化它。但这个梦想通常在我打开运行时的那一刻就破灭了。那里有一套成熟的 C 实现、二进制兼容性、外部扫描器、错误恢复、增量解析、歧义语法、多种语言绑定，以及一个微不足道的小问题——不能破坏建立在其上的庞大语法解析器生态系统。 对于一个人来说，这可不是一个周末项目。这是一个披着头文件的赫拉克勒斯式任务。 *所以什么也没发生。* 然后，AI 辅助的重写尝试开始出现在各处——Bun (https://bun.com/blog/bun-in-rust)、pgrust (https://github.com/malisper/pgrust) 和 Roc (https://rtfeldman.com/rust-to-zig) 等。它们并没有证明重写 Tree-sitter 是明智的，也没有让运行时变得更小，更没有让解析器理论不再陌生。它们表明，这个实验的成本已经低到足以让一个人去尝试，从而给了我足够的杠杆，去问那个看似不合理的问题，并在十年结束前得到答案。 于是，我指示 ChatGPT 用 Rust 重写 Tree-sitter 的 C 核心。这个项目从优先兼容性的翻译开始，经历了一个快速但不可读的优化尝试，最终走向更简单的运行时和真正的解析器性能提升——结果却发现，更快的解析器仍然可能让 ast-grep 变慢。 本文的其余部分将沿着这条旅程展开：什么有效、什么必须回退，以及将解析器基准测试的胜利转化为应用胜利需要付出什么。 ## Tree-sitter 的解析架构 (https://astgrep.com/blog/tree-sitter-rust-rewrite#tree-sitter-s-parsing-architecture) Tree-sitter 接收源代码并生成语法树。每个支持的语言都始于一个语法定义，Tree-sitter 将其编译成生成的解析表和词法分析器代码；当本系列提到“生成的语言”、“生成的语法”或“生成的表”时，指的就是这些产物。在运行时，词法分析器将字符转换为诸如 `identifier`、`+` 和 `number` 这样的标记。然后解析器使用生成的表和一个栈来决定每个标记的含义。 大多数情况下，表会请求以下两种操作之一： - **移进 (shift)**：消费一个标记并将其压入解析栈； - **规约 (reduce)**：识别出几个语法片段构成了一个更大的语法规则，用它们的父节点替换它们，然后继续。 如果每个表项只有一个有效答案，解析器可以用一个栈跟随一个历史路径。这就是普通的 **LR** 情况。编程语言的语法偶尔会有真正的冲突：可能有多个动作仍然有效，直到更多的输入揭示哪个解释成立。 因此，Tree-sitter 使用 **广义 LR (GLR)**。它可以同时跟随多个历史路径，同时在一个图结构栈中共享它们共同的过去。想象一条可以短暂分叉、然后合并的道路。当语法存在歧义时，图结构是必要的。但当解析器为一条始终笔直的道路构建图结构时，就显得不那么迷人了。 另一个核心对象是 **子树 (subtree)**。一个移进的标记变成一个叶子节点；规约将子节点组合成一个内部语法节点。这些值在解析过程中创建，在栈历史路径之间共享，作为最终树发布，由 ast-grep 遍历，并最终释放。如果只优化它们的创建而忽略其后的生命周期，后来会得到一个相当昂贵的教训。 以上是概述所需的全部解析器理论。 ## 第一步：在 Rust 中保持 C 的行为 (https://astgrep.com/blog/tree-sitter-rust-rewrite#first-step-preserve-c-behavior-in-rust) 第一个目标不是优雅，而是一致性。 重写合同刻意保守： - **将现有测试作为行为基准。** 一个看似合理的 Rust 实现是不够的；它必须产生相同的树、恢复行为、导航结果和公共 API 效果。 - **测试生态系统，而不仅仅是手写示例。** 已有的生成式语法和外部扫描器必须无需重新生成或修改源代码即可继续工作。 - **保持二进制接口 (ABI)。** 生成的语法表、公共 C 函数、布局、符号和调用约定保持兼容，而它们背后的实现则切换了语言。 - **先翻译再重新设计。** 第一个 Rust 版本有意模仿 C 的控制流，以便一致性失败时有有限的可搜索范围。 用一句话概括：保留生态系统能够观察到的所有东西，然后让内部变得可替换。 我指示 ChatGPT 逐部分翻译运行时：基本工具、树存储、词法分析、解析栈、树导航，最后是解析循环。代理读取 C 和 Rust 代码，编写补丁，修复编译错误，运行测试，并调查不一致之处。我提供目标、约束、反对意见和决策。现有的实现和测试套件则提供答案密钥。 这个区别很重要。我本人并没有打字完成一个英勇的 Rust 移植，然后让 AI 润色注释。实现、性能分析、工具检测以及大部分实验代码都是在我的指导下由代理生成的。没有 AI，这个项目现在还会是一个我偶尔提起、然后明智地转移话题的想法。 C 核心变成了 Rust。它编译通过了。它通过了测试。现有的语法可以使用它。当项目被搁置时，这看起来还是一件不可能的事情。 自然，我立刻要求更多。 ## 为什么第一次优化尝试失败了 (https://astgrep.com/blog/tree-sitter-rust-rewrite#why-the-first-optimization-attempt-failed) 这个请求纯粹是“氛围编码”——在 `/goal` 命令中键入一行。其背后的过程更加谨慎：我指示 ChatGPT 使用适当的性能分析工具，理解运行时的数据布局和所有权，并寻找算法上的改变，而不仅仅是打磨单个指令。基准测试确实达到了要求的线。然后我打开代码，发现自己无法跟上。层层叠叠的 AI 生成优化位于机械的 C 到 Rust 翻译之上，很快解析器开始出现段错误：没有友好的 Rust 恐慌，没有断言失败，进程直接消失了。一个快 20% 但偶尔消失的解析器不是优化。它是一场带了惊吓的基准测试。 我完全回退了优化工作。那 20% 的提升也随之而去，项目最终达到的性能来自后面描述的干净、分层的工作。第二部分 (https://astgrep.com/blog/tree-sitter-rust-migration) 会完整讲述这个故事。这里重要的是，它如何逆转了项目的方向：我不再要求 ChatGPT 让这堆代码变快，而是开始要求它让系统变得可解释。 ## 第二步：缩小范围并提高可读性 (https://astgrep.com/blog/tree-sitter-rust-rewrite#second-step-reduce-scope-and-improve-readability) 清理工作包含两部分： 1. 删除目标产品范围之外的功能和表示形式； 2. 将保留的 C 风格 Rust 转化为所有权和控制流可以在本地推敲的代码。 这两个步骤都没有承诺英雄般的基准测试结果。但它们是信任下一步的前提条件。 ### 从目标运行时中移除增量解析 (https://astgrep.com/blog/tree-sitter-rust-rewrite#remove-incremental-parsing-from-the-target-runtime) 一开始，“重写 Tree-sitter”意味着保留所有功能。然后目标工作负载迫使一个更好的问题：为谁保留？ 上游 Tree-sitter 在编辑器内部非常有用。用户插入一个字符，再删除两个，并期望高亮在下一帧之前更新。增量解析让运行时可以重用旧树，只重建受影响的区域。在这个世界里，每次击键后重新解析整个文件是不必要的工作。 但这并不是这个分支所处的世界。ast-grep 和我关心的 AI 编码代理工具都在完整的文件快照上操作：代理读取一个文件，分析或重写它，然后要求工具处理新的快照。没有编辑器拥有的语法树在每次击键时前进。从头解析并不是降级的备选方案；它是正常的操作。 所以我决定移除增量旧树复用，并指示 ChatGPT 这样做。公共参数为了兼容性而保留，但此运行时总是从头解析。查找和重用旧树片段的机制——它深入到许多核心结构中——从热路径实现中消失了；第二部分 (https://astgrep.com/blog/tree-sitter-rust-migration) 会详细列出具体删除了什么。 第二个范围缩减随之而来：移除了对 Wasm 编译语法的原生加载。Tree-sitter 可以将语法编译为 WebAssembly 并在运行时加载——这个能力与浏览器端的 Wasm 构建是不同的，后者保留了下来。原生工具设定了本项目的性能目标，而运行时 Wasm 语法加载并不属于那个工作负载。 这不是建议上游 Tree-sitter 应该放弃增量解析。这是一个针对逐文件分析和代理工具的更狭义运行时所做的产品决策。如果这个分支要回到交互式编辑器使用场景，这个决策必须重新评估。规则是：只在声明好的边界后删除，绝不能因为某个功能恰好不方便就删除。 删除结果成了第一个真正的优化技术：移除其用例已经离开的代码。 ### 为了可维护性重构保留的运行时 (https://astgrep.com/blog/tree-sitter-rust-rewrite#refactor-the-retained-runtime-for-maintainability) 逐行翻译只有在读者已经逐行了解原始代码时才是可读的。我指示 ChatGPT 将庞大、指针密集的移植代码分解为更符合 Rust 习惯用法的内部代码——同时避免以破坏现有语法的方式让 ABI 相关的类型变得“符合习惯”。 这次清理与其说是重新设计，不如说是一系列小的提升。内部裸指针参数在生命周期局部且可证明的情况下变成了引用或切片；表示“这里没有节点”的哨兵指针变成了诚实的 `Option`。在 C ABI 不需要的情况下，输出参数变成了返回值。大型模块按职责拆分，使得修改紧邻其改变的状态。必须保留的密集技巧——例如树中的紧凑索引、指针运算——被隐藏在狭窄的、有名字的操作后面。在需要保持兼容性的地方，代码故意保持丑陋：生成的语言布局和导出的函数仍然保持 C 的形状，因为另一个二进制已经承诺了那种形状。 那次清理让问题变得可以回答：谁拥有树的这一部分？当存储增长时，这个引用还能存活吗？为什么一次规约会创建一个临时解析器状态，然后立即删除它？ 重要的输出不是更漂亮的语法。而是一个组织得足够好的运行时，使得段错误、不变量失败或可疑的分配都有其在架构中的位置。 ## GLR 与内存布局优化 (https://astgrep.com/blog/tree-sitter-rust-rewrite#glr-and-memory-layout-optimizations) 一旦我能够理解运行时，我便指示 ChatGPT 重新关注 **规约**——即架构部分提到的“reduce”，也是解析器不断执行的操作。 那个小操作触及两个主要数据结构。它将子节点从解析器的工作栈中移除，然后将它们以新的父节点存储在语法树中。性能分析显示 Tree-sitter 在为这些子节点做的工作远多于普通情况所需。 成功的改动最终归结为四个简单的原则： - **避免为不常见的情况工作。** 约 99% 的解析器栈是单一笔直路径，因此解析器现在只在输入实际分叉时才构建图。主要在编辑中需要的工作也尽可能地从新解析中排除。 - **让分配变便宜，索引变小。** 为每个内部语法节点向通用分配器请求内存是昂贵的。区域分配器 (arena) 获取一个增长的块，并从中提供许多节点。另外，紧凑索引减少了在解析器栈和树之间移动的字节数。 - **重复的工作只做一次。** 解析器提前准备常见的语法查找，而树读取器避免查找超