ast-grep 与 Tree-sitter 简介
ast-grep 借助 AI 编写代码，用 Rust 重写了 Tree-sitter 的 C 核心。新核心在解析速度、读取完整语法树的速度，以及 ast-grep 自身的运行速度上都有所提升。标题中的 "30%" 仅指解析器的提速；从端到端来看，ast-grep 的运行速度大约提升了 22%。源代码仓库为 [HerringtonDarkholme/tree-sitter](https://github.com/HerringtonDarkholme/tree-sitter)。ast-grep 是一款结构化代码搜索工具，通过语法而非文本进行代码搜索，处理的每个文件都必须先转换为语法树。[Tree-sitter](https://tree-sitter.github.io/) 是一个用于构建语法树的解析器框架，只需提供语法定义，它就能为该语言生成一个快速解析器，诞生于编辑器领域，如今已支撑起庞大的语法和工具生态系统。
性能和内存峰值对比
吞吐量经过归一化处理，未修改的 C 版本构建（"C / normal"）评分为 100，数值越高越好。RSS 是驻留内存峰值，原始解析行将其显示为范围，因为它在基准测试的语言样本中有所不同。大纲行是 ast-grep 的实际工作负载：解析仓库中的每个文件，然后遍历每个完成的语法树以提取结构化大纲。
| 基准测试 | C / normal | Rust | 差异 |
|---|---|---|---|
| 原始解析 | 吞吐量：100 RSS：8.48 - 21.41 MiB | 吞吐量：129.74 RSS：8.42 - 25.70 MiB | 吞吐量 +29.74% RSS 上限 +20.0% |
| 树遍历 | 吞吐量：100 RSS：20.38 MiB | 吞吐量：110.16 RSS：22.20 MiB | 吞吐量 +10.16% RSS +8.9% |
| 完整 ast-grep 大纲 | 用户 CPU：1.233 s RSS：26.52 MiB | 用户 CPU：0.960 s RSS：34.43 MiB | 用户 CPU -22.2% RSS +29.8% |
在每个解析和遍历测试中，Rust 版本都表现更优，并且 ast-grep 生成的大纲完全相同。不过，代价是内存使用增加：在 ast-grep 运行时，Rust 版本大约多使用 8 MiB 内存。在更大的 TypeScript 压力测试集（即 TypeScript 编译器仓库的测试基线树，这也是该项目的内存压力测试）中，内存峰值达到了 91.2 MiB。这一结果值得肯定，而非需要担忧：在项目早期，同样的测试集内存峰值超过了 1 GiB。这个成果并非是对上游 Tree-sitter 的直接替代，而是为分析完整文件快照的 AI 编码代理构建的一个更精简的运行时：现有的生成语言和解析器仍然兼容；移除了 WebAssembly 编译语言的原生加载和旧语法树的增量复用功能；为了保持兼容性，仍然需要使用许多原始指针和 `unsafe` 块。这样的边界设定在去除了目标工作负载不需要的编辑器特定机制的同时，让语法生态系统对代理式编码仍然有用。
为何重写 Tree-sitter？
每次对 ast-grep 进行深入的性能调查，最终都会指向同一个问题：Tree-sitter。ast-grep 可以优化规则以提高速度，它可以减少工作量、缓存配置并避免处理无关语法。但每个文件仍需先转换为语法树，而这正是 Tree-sitter 的工作。解析器既是基础，也逐渐成为性能瓶颈。多年来，一直梦想着重写或深度优化它，但这个梦想往往在打开运行时代码后就破灭了。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 的解析架构
Tree-sitter 接收源代码并生成语法树。每种受支持的语言都始于一个语法定义，Tree-sitter 将其编译为生成的解析表和词法分析器代码。在本系列文章中，"生成语言""生成语法"或"生成表"指的就是这些产物。在运行时，词法分析器将字符转换为 `identifier`、`+` 和 `number` 等标记。然后，解析器使用生成的表和栈来确定每个标记的含义。大多数情况下，解析表会请求执行以下两种操作之一：移位（shift）：消耗一个标记并将其压入解析器栈；归约（reduce）：识别出几个语法片段构成一个更大的语法规则，用一个父节点替换它们，然后继续处理。如果每个解析表项都只有一个有效答案，解析器就可以使用一个栈遵循一条路径进行解析，这就是普通的 **LR** 情况。但编程语言的语法偶尔会出现真正的冲突：在获得更多输入以确定哪种解释有效之前，可能有多个操作都是有效的。因此，Tree-sitter 使用 **广义 LR (GLR)** 算法，它可以同时遵循多条路径，同时在图结构栈中共享它们的共同历史。可以想象成一条路偶尔会分叉，然后再合并。当语法存在歧义时，这种图结构是必要的，但当解析器为一条直路构建图结构时，就显得有些多余了。另一个核心对象是 **子树**。移位操作得到的标记成为叶子节点，归约操作将子节点合并为一个内部语法节点。这些值在解析过程中创建，在栈历史中共享，最终作为完整的语法树输出，供 ast-grep 遍历，最后被释放。如果只优化它们的创建过程，而忽略其整个生命周期的其他部分，后来会为此付出昂贵的代价。以上就是解析器理论的简要概述。
第一步：在 Rust 中保留 C 语言的行为
首要目标并非追求代码优雅，而是实现功能对等。重写的目标设定得很保守：以现有测试作为行为参考，仅仅有一个看似合理的 Rust 实现是不够的，它必须生成相同的语法树、具备相同的错误恢复行为、导航结果和公共 API 效果；测试整个生态系统，而非仅依赖手写示例，现有的生成语法和外部扫描器必须无需重新生成或修改源代码就能继续工作；保留二进制接口 (ABI)，在实现语言变更的同时，生成的语言表、公共 C 函数、布局、符号和调用约定必须保持兼容；先翻译，再重新设计，第一个 Rust 版本有意模仿 C 语言的控制流程，这样在出现功能不对等的问题时，排查范围会比较有限。简而言之，就是保留生态系统可观察到的所有内容，然后让内部实现变得可替换。让 ChatGPT 逐步翻译运行时代码，包括基础工具、树存储、词法分析、解析器栈、树导航，最后是解析器循环。AI 读取 C 语言和 Rust 代码，编写补丁，修复编译器错误，运行测试，并调查不匹配的问题。提出目标、约束条件、异议并做出决策，现有的实现和测试套件则提供了验证标准。这一点很重要。并非亲自编写了一个出色的 Rust 移植版本，然后让 AI 来优化注释。实际上，实现、性能分析、调试以及大部分实验代码都是在指导下由 AI 完成的。没有 AI，这个项目可能至今仍只是偶尔提及但又明智放弃的想法。C 语言核心代码成功转换为 Rust 代码，代码能够编译，测试通过，现有的语法也能正常使用。这在项目最初搁置时，看起来几乎是不可能实现的结果。自然地，马上有了更高的要求。
首次优化尝试为何失败
只是在 `/goal` 命令中输入了一行简单的要求，但背后的过程其实更为严谨：指导 ChatGPT 使用合适的性能分析工具，理解运行时的数据布局和所有权关系，并寻找算法层面的改进，而非仅仅优化个别指令。基准测试结果确实达到了预期，但当查看代码时，却发现难以理解。在机械的 C 到 Rust 翻译基础上，叠加了多层 AI 生成的优化代码，不久后解析器开始出现段错误：没有友好的 Rust 错误提示，也没有断言失败信息，进程直接崩溃。一个速度提升了 20% 但偶尔会崩溃的解析器并非优化成果，而是一个会带来惊吓的基准测试。完全回退了优化工作，20% 的性能提升也随之消失。项目最终实现的性能提升，来自于后续干净、分层的工作，这将在 [第二部分](./tree-sitter-rust-migration) 详细介绍。这里关键的是这次尝试如何改变了项目方向：不再让 ChatGPT 单纯地提升代码速度，而是要求它让系统变得更易于理解。
第二步：缩小范围并提高代码可读性
清理工作分为两部分：删除目标产品不需要的功能和表示；将保留的类 C 风格的 Rust 代码转换为可以局部推理其所有权和控制流的代码。这两步都不能保证在基准测试中取得显著成果，但它们是后续工作值得信赖的前提。
从目标运行时中移除增量解析功能
最初，"重写 Tree-sitter" 意味着保留所有功能。但目标工作负载让重新思考：保留这些功能是为了谁？上游的 Tree-sitter 在编辑器领域非常有用。用户插入一个字符、删除另外两个字符后，期望在下一帧之前就能看到代码高亮更新。增量解析允许运行时复用旧的语法树，只重建受影响的区域。在这种场景下，每次按键后重新解析整个文件是不必要的。但这并非本分支的应用场景。ast-grep 和关注的 AI 编码代理工具处理的是完整的文件快照：代理读取文件，进行分析或重写，然后让工具处理新的快照。这里没有编辑器维护的逐键更新的语法树，全新解析并非降级方案，而是正常操作。因此，决定移除旧语法树的增量复用功能，并让 ChatGPT 完成这项工作。为了保持兼容性，公共参数仍然保留，但这个运行时会进行全新解析。用于查找和复用旧语法树部分的机制，这些机制涉及到许多核心结构，从关键实现中移除了；[第二部分](./tree-sitter-rust-migration) 会详细列出具体移除的内容。与此同时，还进行了另一项范围缩减：移除了 WebAssembly 编译语法的原生加载功能。Tree-sitter 可以将语法编译为 WebAssembly 并在运行时加载，这一功能与浏览器的 Wasm 构建不同，后者得以保留。本地工具设定了本项目的性能目标，而运行时的 Wasm 语法加载并非该工作负载的一部分。这并非建议上游的 Tree-sitter 放弃增量解析功能，而是针对按文件进行分析和代理工具的更精简运行时做出的产品决策。如果这个分支要重新用于交互式编辑器，就需要重新考虑这个决定。原则是：只在明确界定的范围内进行删除，而不是因为某个功能不方便就删除。事实证明，删除是第一种真正有效的优化方法：去除那些已经不再适用的功能。
为了可维护性重构保留的运行时
逐行翻译的代码只有在读者熟悉原始代码的情况下才易于理解。让 ChatGPT 将这个庞大、指针密集的移植版本重构为更符合 Rust 习惯的内部代码，同时避免让面向 ABI 的类型以可能破坏现有语法的方式 "变得符合习惯"。这次清理工作更像是一系列小的改进，而非彻底的重新设计。只要内部原始指针参数的生命周期是局部且可证明的，就将其转换为引用或切片；表示 "此处无节点" 的哨兵指针被替换为 `Option` 类型。在 C ABI 没有强制要求的情况下，将输出参数改为返回值；大型模块按职责拆分，使修改操作与受影响的状态相邻；必须保留的复杂技巧，如树中的紧凑索引、指针运算等，被封装在简洁、命名清晰的操作背后。在需要保持兼容性的地方，代码故意保持不美观：生成语言的布局和导出函数仍然保持 C 语言的风格，因为其他二进制文件已经依赖于这种格式。这次清理让问题变得可解答：谁拥有树的这一部分？当存储增长时，这个引用能否继续存在？为什么一次归约操作会创建一个临时解析器状态，然后又立即删除它？重要的成果不是更漂亮的语法，而是一个组织良好的运行时，使得段错误、不变性失败或可疑的内存分配问题都能在架构中有迹可循。
GLR 和内存布局优化
在能够理解运行时之后，让 ChatGPT 再次聚焦于 **归约（reduce）** 操作，也就是前面架构部分提到的操作，这也是解析器经常执行的操作。这个小操作涉及到两个主要的数据结构。它从解析器的工作栈中移除子节点，然后将它们存储在语法树的新父节点下。性能分析显示，Tree-sitter 在处理这些子节点时做了很多超出常规情况所需的工作。最终成功的改进遵循了四个简单的原则：避免为罕见情况做不必要的工作，观察发现，大约 99% 的解析器栈是单一路径，因此在输入实际分叉之前，解析器不再构建图结构。同时，尽可能避免在全新解析时进行主要用于编辑的操作；降低内存分配成本，减小索引大小，每次为内部语法节点向通用内存分配器请求内存是很昂贵的。使用内存池（arena）可以预先分配一个不断增长的内存块，为多个节点提供内存。此外，紧凑的索引可以减少解析器栈和语法树之间的数据移动量；一次性完成重复工作，解析器提前准备好常见的语法查找，语法树读取器避免重复查找相同的子节点；为简单情况提供捷径，直接处理一种解析器操作，普通 ASCII 输入避免完整的字符解码过程。当简单路径不适用时，仍然可以使用完整的回退机制。
普通解析：保持单一路径
真正的歧义：切换到完整的图结构
99% 这个数据描述了问题，但没有给出解决方案。让 ChatGPT（这次处于研究模式而非编码模式）回顾关于广义解析器的学术研究，结果让想起一个古老的经验：在输入真正需要之前，不要构建通用结构。内存池是一个独立的想法，需要进行自己的实验。线性栈避免了图结构的管理开销，内存池减少了对通用内存分配器的调用。减小索引大小也是一种布局选择，但并非自动就能提高速度，经过多次尝试才取得了效果。重要的结果是：普通解析不再为罕见的歧义情况和每个内部语法节点的单独内存分配付出全部代价。有一段时间，解析器的基准测试结果看起来非常出色。然后，让 ChatGPT 基于这个版本构建 ast-grep。
端到端性能发现
AI 在一个真实的 TypeScript 仓库 opencode 上运行了这个二进制文件。此时，仅解析器的基准测试显示，这个 Rust 实现比 C 语言运行时快了大约 30%。但应用程序的运行速度却变慢了。解析器速度提高了 30%，应用程序怎么会变慢呢？解析器基准测试只复用了一个解析器，而 ast-grep 为数千个文件创建了解析器，然后遍历每个完成的语法树以提取大纲。基准测试只衡量了这个过程的一部分。最初，每次创建解析器时，内存池都会预留一个巨大的虚拟内存区域。虽然它不会立即占用所有物理内存，这让这个设计看起来无害，但在处理整个仓库时，这种预留操作会进行数千次，每次都需要付出实际的代价：一轮新的预留和释放系统调用，以及背后的页面错误和页表更新，每个文件都要重复这些操作。在 opencode 测试集中，正是这些开销（而非解析操作）导致了 CPU 性能下降。让 ChatGPT 将预留操作改为普通的小内存分配，只有在需要时才进行扩展。解决了这个问题后，又暴露出了另一个问题：内存。在单独的 TypeScript 压力测试集中，始终使用一个 ast-grep 工作进程进行测量，内存池早期的增长策略导致旧的内存块一直被保留，使得内存峰值达到了 1.04 GiB。要将内存峰值降低到最终的 91.2 MiB，需要对内存池进行多次调整，其中还包括一个意外情况：一直让 ChatGPT 回收的内存并非实际浪费的内存。[第四部分](./tree-sitter-end-to-end) 会给出详细的跟踪信息和问题根源，这里就不剧透了。完成的语法树还有一个意外情况。紧凑索引在构建语法树时很有用，但 ast-grep 在读取时需要查找这些索引，这导致部分解析时间转移到了树遍历阶段。ChatGPT 修改了语法树读取器，让它一次性查找每组子节点，而不是重复查找，从而挽回了这部分开销。这些改进措施，即使用普通内存分配代替每个解析器的虚拟内存预留操作，以及让语法树读取器一次性解析每组子节点，解决了性能下降的问题。再结合后续对解析器的进一步调优，就得到了本文开头的数据：与 C 语言版本相比，大纲生成操作的用户 CPU 时间减少了 22.2%。端到端性能测试的失败并没有否定解析器的改进工作，而是让重新定义了 "成功" 的含义。从那以后，性能结果需要涵盖解析、内存使用、语法树读取以及应用程序的整个生命周期。这些成果并非依赖于某个神奇的补丁。有些改进节省了解析时间，有些避免了内存灾难，还有些在读取完成的语法树时挽回了时间。本文概述了连接各个实验的原则，后续的详细文章将对它们进行拆解分析。
AI 辅助重写的经验教训
一开始，AI 让一条指令就能推动大量代码的编写工作，这使得重写成为可能，但远远不足以保证重写的质量。早期的工作流程是这样的：
/goal 提高 20% 的性能
-> 生成大量看似合理的代码
-> 得到令人困惑的基准测试结果
-> 再生成一个看似合理的补丁
后来变成了这样：
找出开销大的操作
-> 解释其原因
-> 修改一个机制
-> 与之前的 Rust 版本进行比较
-> 测试整个应用程序
-> 保留、修改或放弃该改进
ChatGPT 并没有逐渐变得完美无缺，而是逐渐深入了解了运行时，能够给它提出更具体的问题，挑战一些默认假设，并在合适的层面要求提供证据。早期速度提升但出现段错误、内存池的内存爆炸以及应用程序变慢等问题，背后都是看似合理的代码和有希望的局部结果。性能分析和测试必须发现双方都忽略的问题。到最后，这种协作找到了合理的分工。ChatGPT 能够以手工无法企及的速度探索实现方案，而工作是不断细化问题，直到性能分析、不变量检查和端到端测试能够给出答案。速度让这次探索成为可能，而证据则决定了哪些改进值得保留。这就是整个故事。后续文章将详细展开：1. [用 Rust 重写 Tree-sitter 的 C 核心：迁移与兼容性](./tree-sitter-rust-migration) 介绍了迁移过程、`/goal` 操作及其回退、本分支删除的内容，以及兼容性边界是如何得以保留的。2. [改进 Tree-sitter 的 GLR 算法和内存布局](./tree-sitter-glr-arena) 解释了为什么解析器要为几乎总是线性的工作负载构建图结构，以及 "使用内存池" 背后的诸多决策。3. [为端到端 ast-grep 性能优化 Tree-sitter](./tree-sitter-end-to-end) 包含内存跟踪信息、树遍历调查、基准测试规则，以及根据应用程序性能分析进行的进一步解析器优化（查找索引、单动作调度）。简而言之，AI 让有机会移动了一堵承重墙，而项目的后续工作就是通过一次次基准测试，发现这堵墙原本支撑着的其他一切。
