反对基于查询的编译器

# 反对基于查询的编译器 来源：https://matklad.github.io/2026/02/25/against-query-based-compilers.html 2026年2月25日 近期，基于查询的编译器风头正劲（https://thunderseethe.dev/posts/compiler-education-deserves-a-revoluation/），因此，在此指出其中暗藏的险滩暗礁，也算恰逢其时。 基于查询的编译器，本质上就是将增量计算的思想直接应用于编译——没错，你想对了。编译器不过是一个简单的文本转换程序，由大量函数实现。你可以将编译器在特定输入源代码上的*一次运行*，可视化为一个函数调用图： 这里，示意性地，方块代表输入（如文件文本或编译器的命令行参数），`g` 是一个中间函数（例如类型检查），它被调用了两次（参数不同），而 `f` 和 `h` 是顶层函数（编译可执行文件，或为 LSP 计算补全）。 看到这张图，如何让编译器变得“增量”就显而易见了——如果某个输入发生了变化，只需重新计算从变更输入到根“查询”路径上的结果即可： 再稍微思考一下，你就能推导出“提前剪枝”优化： 如果函数的输入发生了变化，但其结果没有变化（例如，函数类型不受空白符改变的影响），就可以提前停止变更传播。 然后……基本上就是这样了。这个方案的美妙之处在于它那银弹般的光环——可以不加思考地应用于任何计算，而且借助一点元编程，你甚至不需要显著更改编译器的代码。 *《Build Systems à la Carte》*（https://simon.peytonjones.org/assets/pdfs/build-systems-jfp.pdf）是这里必读的经典论文。在构建系统中，一个查询是一个不透明的进程，其输入和输出是文件。而在基于查询的编译器中，查询只是函数而已。 --- 我们最初想要这个，是为了增量编译——尤其是在 IDE 环境下，编译器需要对一连串微小的编辑做出反应，其时间预算大约在 100 毫秒左右。此时大 O 分析法很有用：对变更的反应时间应与变更的规模成正比，而不是与代码库的整体规模成正比。O(1) 的变更应导致 O(N) 代码库的 O(1) 更新。 同样的大 O 分析也揭示了该方案的主要局限性——更新的工作量不可能小于结果的变化量。 举个例子。假设我们的“编译器”将短语转换为大写： `` compile("hello world") == "HELLO WORLD" `` 这很容易实现增量，因为改变输入中的几个字母，输出中也只改变几个字母： `` compile("hallo world") == "HALLO WORLD" `` 但现在假设我们的“编译器”是一个哈希或加密函数： `` compile("hello world") == "a948904f2f0" compile("hallo world") == "a7336983eca" `` 这已经被证明不可能实现有用的增量。加密*可以*实现为函数调用图，你*可以*将通用的增量方案应用于它，只是它不会很快。 原因是雪崩效应——对于好的加密算法，输入中任何一位的变化，都应该导致输出中大约一半的位翻转。因此，仅仅更改输出所需的工作量（完全忽略计算需要更改什么的工作量）就是 O(N)，而不是 O(1)。 > 基于查询的编译器的有效性受限于源语言的依赖结构。 这里特别麻烦的一个效果是，即使只存在*潜在的*雪崩效应（即某种类型的变更*可能*影响输出的很大一部分，即便通常不会），你的增量引擎很可能仍会花费一些 CPU 时间或内存来确认依赖关系的不存在。 --- 在我的文章《*三种面向响应式 IDE 的架构*》（https://rust-analyzer.github.io/blog/2020/07/20/three-architectures-for-responsive-ide.html）中，基于查询的编译被列为第三种、也是兜底的选择。我仍然认为这基本上是对的：作为语言设计者，我认为值得倾听你内心的 Grug（https://grugbrain.dev/），尽可能将查询的需求推至编译管线的下游，坚持使用更直接的方法。*不*使用查询更简单、更快，并且更容易优化（分析基于查询的编译器是一种特殊的障碍赛跑）。 Zig 和 Rust 提供了一个很好的对比。在 Zig 中，每个文件都可以完全独立地解析，因此编译从独立且并行地解析所有文件开始。由于在 Zig 中每个名称都需要显式声明（没有 `use *`），名称解析也可以在每个文件的基础上进行，无需查询。Zig 甚至更进一步，直接将无类型 AST 转换为 IR，在此过程中产生大量错误（例如，“`var` 不需要可变”）。详情请参见 *Zig AstGen: AST => ZIR*（https://mitchellh.com/zig/astgen）。等到编译器到达跟踪查询的阶段时，它需要处理的数据已经与原始源代码相去甚远，但这只是因为 Zig *语言*经过精心设计才允许如此。 相反，在 Rust 中你无法真正解析一个文件。Rust 的宏会生成新的源代码，因此直到所有宏展开完毕，解析才能完成。展开宏需要名称解析，而在 Rust 中，名称解析是一个 crate 级别的操作，而非文件级别。语言的一个基本属性是：在 `a.rs` 中输入内容可能会改变 `b.rs` 的解析结果，这迫使精细的依赖追踪和失效从前端的最开始就进行。 类似地，trait 系统的性质决定了，与特定方法调用相关的 `impl` 块几乎可以出现在任何地方。对于每个 trait 方法调用，你都会对提供实现的 `impl` 块产生依赖，但你*同时*也会对其他每个文件中不存在的冲突 `impl` 产生依赖！ 再次，请参考《*三种架构*》（https://rust-analyzer.github.io/blog/2020/07/20/three-architectures-for-responsive-ide.html）以获得正面思路，但总体技巧是利用语言语义，手动将编译任务切割成定义上（由源语言决定）就相互独立的、稍微粗粒度的块。Grug 为其语言构建了一个增量的 map-reduce 编译器： - 递归遍历目录以查找所有需要编译的文件。 - 并行地、独立地解析、名称解析并降低（lower）每个文件。尽可能多地将语言特性（及错误）处理成由语法驱动而非由类型驱动，并在该阶段处理。 - 并行地从每个文件中提取一个“摘要”，本质上只是一个类型和签名的列表，函数体为空。 - 顺序地对这组摘要运行“签名求值”阶段，将签名中的类型引用转换为实际类型，处理文件之间的相互依赖。每当某个文件的摘要发生变化时，就重新运行此阶段。反过来，任何函数体内部的变更都不会使已解析的签名失效。 - 并行地，对每个函数的函数体进行类型检查，并降低为类型和布局都确定的 IR，应用函数局部优化。 - 顺序地对已编译的函数运行一套细粒度 LTO 风格的分析，做出内联决策，并计算受调用图影响的属性（如函数纯度）。 - 并行地，将每个函数生成为机器码，其中对其他函数的引用尚未解析（重定位）。 - 顺序地将函数拼接成可执行文件，分配地址。 - 并行地将所有重定位解析为现在已知的地址。 上述方案仅在语言具有以下属性时才有效：更改函数 `foo` 的函数体（不触及它的签名）不会在不相关的函数 `bar` 中引入类型错误。 --- 另一个如果你盲目应用查询就会变得不那么可用的技巧是原地更新。考虑一种具有包声明和完全限定名称的语言，例如 Kotlin： `` package org.example fun printMessage() { /*...*/ } class Message { /*...*/ } `` 这种语言的编译器可能希望维护一个所有公开声明的映射，其中键是完全限定的名称，值是声明本身。如果你用查询的眼光来考虑计算这个映射的问题，你可能会有一个基于每个文件的基础查询，返回该文件声明的映射，然后是一个递归的基于每个目录的查询。并且你可能还会采用某种结构共享的映射，这样更改单个文件只会更新“脊柱”，而不会实际复制大多数其他条目。 但有一种更直接的方法可以使这类结构对变更做出响应。你只需要两个“查询”——每个文件一个，以及一个全局查询。当文件发生变化时，你查看该文件映射的*先前*版本，计算添加或删除的声明的差异，然后将此差异应用到全局映射上。 Zig 计划使用类似的方法来增量链接——不是生成一个将基本未改变的机器码块粘合起来的新二进制文件，而是原地修补之前的二进制文件。 --- 如果你喜欢这篇文章，你可能对我多年来写的一些其他相关文章感兴趣，大致按重要性排序： - Three Architectures for a Responsive IDE (https://rust-analyzer.github.io/blog/2020/07/20/three-architectures-for-responsive-ide.html) - Durable Incrementality (https://rust-analyzer.github.io/blog/2023/07/24/durable-incrementality.html) - Zig Language Server And Cancellation (https://matklad.github.io/2023/05/06/zig-language-server-and-cancellation.html) - Resilient LL Parsing Tutorial (https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html) - Find Usages (https://rust-analyzer.github.io/blog/2019/11/13/find-usages.html) - The Heart of a Language Server (https://rust-analyzer.github.io/blog/2023/12/26/the-heart-of-a-language-server.html) - How to Make a 💡? (https://rust-analyzer.github.io/blog/2020/09/28/how-to-make-a-light-bulb.html) - LSP could have been better (https://matklad.github.io/2023/10/12/lsp-could-have-been-better.html) - On Modularity of Lexical Analysis (https://matklad.github.io/2023/08/01/on-modularity-of-lexical-analysis.html) - Why an IDE? (https://matklad.github.io/2020/11/11/yde.html)