最近在调研 Rspack 的 incremental 实现，很多其他编译器实现增量构建的资料中都有提到一篇论文： Build Systems à la Carte: Theory and Practice ^[1] ，所以抽空学习了下发现挺有意思的，和 bundler 也有一些相关性。本文会简单介绍这篇论文的内容，并尝试从 build system 的角度来概括 bundlers。

à la carte：菜单的法语。

本文为了方便描述，省略很多细节；论文中有专门一章的内容描述了 real world build system 会遇到的问题，本文为了方便描述省略了这部分内容，real world build system 会有很多实际工程上的问题，所以本文仅作介绍，提供一个新的角度来看待问题。

Build system

Build system 指的是自动化执行一系列可重复任务的软件系统，常见的有 Make ^[2] 、 Shake ^[3] 、 Bazel ^[4] ，他们以源文件作为输入，根据任务描述文件（比如：makefile）执行任务，构建出可执行文件。

还有一些并不常见的， Excel ^[5] 以单元格作为输入，根据指定单元格的公式作为任务并执行任务，构建出这个单元格的结果；UI frameworks 以 props 作为输入，根据 Components 作为任务并执行，构建出新的 UI。

由此我们可以看出一些通用的概念：

• Task：任务，实际的逻辑由任务的描述（task descriptor）所定义，比如 makefile、Excel 的公式。
• Input：任务输入。
• Output：任务输出，任务的输出可能是下一个任务的输入。
• Info：构建信息，跨构建的信息，供下次构建使用，比如 Make 中文件的修改时间就是它的 Info，可以理解为 bundler 中的缓存。
• Store：存储，存储 Task 的 Input 和 Output 以及 Info 的地方，比如在 Make 中文件系统就是它的 Store。
• Build：构建，依据上述的概念我们可以将一次构建看作：根据定义的 Tasks 和原有的 Store，输入新的 Inputs，获得新的 Store。

这些概念是很通用的，在各个 build system 中的实现也比较相似，并不是造成不同 build systems 的主要原因，各个 build systems 不同的主要原因其实是对于以下两点所选取的策略不同导致的：

• Task 是否重新执行。
• Tasks 的执行顺序。

这两点分别对应两个比较重要的概念：Rebuilder 和 Scheduler，不同 build systems 可以看做使用了不同 Rebuilder 和不同 Scheduler 的组合。

Scheduler

持有 Rebuilder，进行一次新的 Build，决定了以怎样的顺序执行 Tasks。

• Topological：根据任务的依赖关系进行拓扑排序，以拓扑排序的结果执行任务。
• Restarting：选取一个任务执行，如果任务的依赖没被执行完毕，则重新选取一个任务，直到所有任务执行完毕。
• Suspending：选取一个任务执行，如果任务的依赖没被执行完毕，则执行其依赖，依赖执行完毕后再继续执行该任务，这种能通过 async/await 轻松实现。

Rebuilder

持有 Task，对 Task 进行重新执行，决定了 Task 是否需要重新执行，是使用缓存还是重新执行的结果。

• Dirty bit：每个任务会记录自己是 clean 还是 dirty，构建结束后所有任务都为 clean，下次构建时发生改变的输入会标记为 dirty 重新执行任务，如果输入以及它的依赖都是 clean 的，那这个输入对应的任务就不用重新执行。
• Verifying traces：会记录任务依赖的信息，包括 hashes 或 timestamps 等，下次执行任务时用来验证任务依赖是否改变，如果改变则重新执行任务，否则复用上次任务结果；可以理解为 cache，记录的 hashes 或 timestamps 就是 cache key。
• Constructive traces：由 Verifying traces 衍生而来，用来支持云缓存。Consturctive traces 相比 Verifying traces 的不同在于，除了记录 hashes 或 timestamps 这些轻量的信息，也会把实际内容记录下来，这样 traces 通过网络传输时就能传输实际内容，从而实现云缓存和远程执行任务。

Build systems

build systems 可以看做使用了不同 Rebuilder 和不同 Scheduler 的组合 ^[6] 。

先介绍几个常见的特性：

• Dynamic dependencies：Task 依赖的 Tasks 是静态声明的还是动态计算出的，比如 makefile 就静态声明了各个 Task 间的依赖关系，Excel 的 IF(RANDBETWEEN(0, 1) > 0.5, A1, A2) 就需要动态计算出 B2 的依赖。
• Minimality：仅执行最少的任务完成构建，当然最小是很难达到的，所以这个特性往往是相对的。
• Early cutoff：Task 重新执行时 Output 没发生改变时，依赖该 Task 的 Tasks 能否停止执行，提前完成构建。

Make

make = topological modTimeRebuilder

Make 使用 makefile 来描述任务，这些任务间的依赖关系明确，属于静态依赖，也不支持循环依赖，所以 Make 使用了 topological scheduler 以拓扑顺序执行任务。

Make 的 Info 构建信息其实就是文件系统本身，文件系统会有文件修改时间，Make 通过文件修改时间来判断任务是否需要重新执行，如果文件的修改时间早于其依赖文件的修改时间，则说明该任务需要重新执行，Make 将文件修改时间当做 dirty bit，属于 dirty bit rebuilder 的一种。

当然很多情况下文件修改时间是不可信的，比如有些程序会更新文件修改时间，但文件实际内容并不会修改，这就导致任务没必要的重新执行。

Make 通过 modTimeRebuilder 实现 Minimality，跳过不需要执行的任务，但也因为 modTimeRebuilder 导致它没有实现 Early cutoff，因为任务重新执行后输出的新的文件，尽管内容没变，文件修改时间也是改变的，导致不能提前中断，从这里也可以看出，没有实现 Early cutoff 的执行的任务一定不是最少的，所以 Minimality 往往是相对的。

Excel

excel = restarting dirtyBitRebuilder

Excel 通过单元格中的公式来描述任务，有些公式会有静态的依赖关系，但有些是动态的，所以使用了 restarting scheduler 来执行任务。值得注意的是，Excel 会记录最终的执行顺序供下次构建参考，以减少 restarting 的开销。

Excel 使用 dirty bit rebuilder，对于用户修改的单元格标记为 dirty，并重新执行依赖该单元格的任务，对于导致动态依赖的公式，Excel 会在每次构建时都标记为 dirty，确保每次都对其进行更新，来保证正确性，通过损耗一些性能来保证其正确性。

Excel 对于静态依赖是 Minimality 的，但对于动态依赖并没有实现 Minimality。

Bazel

bazel = restarting ctRebuilder

Bazel 也使用了 restarting scheduler 来执行任务，Bazel 也有一套优化机制来避免 restarting 的开销。

Bazel 使用 ctRebuilder 支持了云缓存和远程执行任务。

Shake

shake = suspending vtRebuilder

Shake 使用 vtRebuilder，在任务执行时追踪任务的依赖，并记录下来，在下次执行时，如果依赖没发生改变，则跳过执行，并且如果当前任务没被执行，则依赖当前任务的任务由于依赖没发生改变，也不需要执行，以此实现 Minimality 和 Early cutoff。

Shake 由于是任务执行时追踪依赖，并不需要提前静态定义，所以也支持 Dynamic dependencies。

Cloud Shake

cloudShake = suspending ctRebuilder

cloud shake 在 shake 的基础上支持了云缓存，区别在于将 Rebuilder 从 vtRebuilder 换成了 ctRebuilder。

Buck2

buck2 = suspending ctRebuilder

buck2 的核心开发者之一是 shake 的作者 ^[7] ，也是 Build Systems à la Carte: Theory and Practice 这篇论文的作者之一。

Buck2 与 cloud shake 类似 ^[8] ，buck2 支持 dynamic dependencies，实现了 minimality 和 early cutoff，除此之外还支持云缓存，并且一等公民的支持了 远程执行任务 ^[9] 。

buck2 也实现了自己的 incremental computation engine： DICE ^[10]

Bundlers

Bundler 其实可以理解为 build system + 一部分 task descriptor，build system 其实对任务具体做什么并不关心，任务具体做什么由用户通过任务描述文件提供，build system 只管执行任务。早期 gulp ^[11] 、 grunt ^[12] 这种 task runner 其实更接近 build system，开发者使用这些 task runner 来手动编排文件的处理逻辑，以 task runner 作为 build system；同样的 turborepo 不关心任务逻辑，只执行任务，也声称自己是 build system。

Bundler 本身描述了一部分的任务逻辑，比如怎样构建模块、怎样拆分 chunk、怎样进行优化等，然后由用户的配置和插件提供剩余部分，组合成完整的 task descriptor。

Bundler 和 Build system 的任务也是有些不同的：

• 首先 Bundler 任务的依赖是非常动态的（dynamic dependencies），任务逻辑本身是动态的，比如模块代码生成可能依赖于其他模块的生成结果、模块的优化可能依赖于其他模块的优化结果，而且用户的配置和插件也会影响任务逻辑，而早期 build system 对 dynamic dependencies 的支持并不好，基本都是静态依赖，比如 Make，到后来的 build system 才有了比较好的支持，比如 Shake、Buck2 等。
• 其次是对环的处理，Bundler 由于模块之间关系经常出现循环依赖关系，导致任务之间出现循环依赖，这时需要对环进行处理，而 build system 大部分都不支持环，当然也有少数 build system 对环进行了处理。

另外以 build system 中定义的 Build 为准的话，Bundler 的 Build 其实分为两种：

• 不中断 Compiler 的 Build，即 watch 下的 rebuild。
• 中断 Compiler 的 Build，即 build 完成后再次 build。

这两种 Build 也导致了两种不同的 Info，即 memory cache 和 persistent cache，这两种 Info 不仅能分开使用，也能针对场景进行混合使用。

Webpack/Parcel/Rollup/esbuild

passBasedBundler = foreach ctRebuilder

在传统的 pass-based bundler 中，每个 pass 的任务执行顺序（Scheduler）和是否执行（Rebuilder）都是不同的，每个 pass 依据这个阶段的任务逻辑，使用适合这个阶段的任务执行顺序和是否执行策略，比如在 webpack 中：

• module graph 和 chunk graph 并不是一个无环图，所以 topological scheduler 在大部分阶段都不适用。
• SideEffectsFlagPlugin：在优化一个模块的 incoming connections 时，需要确保这个模块的父模块的 incoming connections 已经被优化过了，以达到最佳的优化效果，属于 suspending scheduler；但由于只是更新模块的 connection 关系，没有太大计算开销，所以没有任何逻辑来跳过任务的执行，属于 “always true” rebuilder。
• FlagProvidedExportsPlugin：由于 re-export 会影响模块的导出内容，所以会将含有 re-export 模块和 re-export 引入模块记录为依赖关系，当 re-export 引入模块的导出内容改变时，会将含有 re-export 模块的导出内容重新进行计算，直到不再有模块的导出内容发生改变为止，属于 restarting scheduler；由于计算导出内容是有一定计算量的，所以引入了 cache 来跳过一些任务，属于 vtRebuilder。
• 其他大部分阶段的任务逻辑并不关心任务的先后顺序，比如 module build、module codegen 等，而且支持持久缓存，所以其他大部分 pass 都使用了 “foreach” scheduler + ctRebuilder 的组合。

在 pass-based bundler 中，cache 为 bundler 实现了 Minimality，但由于各个 pass 之间的任务互不感知，pass 之间的任务不能实现 early cutoff，导致仍然存在过量任务需要进行 cache 验证。这往往也是 pass-based bundler 慢的原因：没有实现 Early cutoff 导致不够 Minimality。

Turbopack

turbopack = suspending ctRebuilder

不同于传统的 pass-based bundler，turbopack 并没有强调从头到尾的一个个编译阶段（pass），而是更接近于 query-based，定义任务，通过 query 获取任务结果，尤其是在 Dev 环境下，比如编译一个以 html 为入口的 web 页面，turbopack 的逻辑是：

传统 pass-based bundler 的逻辑是：

相比于 pass-based bundler，turbopack 只会关注获取 query 结果所需要执行的这一部分任务，其他无关任务不会执行，尤其 Dev 环境下不会有完整的 ModuleGraph 和 ChunkGraph。在 Production 环境下还是会通过一些方式来聚合成完整的图，以对完整 ModuleGraph / ChunkGraph 进行全局优化。

Turbopack 底层的 incremental computation engine：turbo tasks 就是驱动 turbopack 的 build system，task、scheduler、rebuilder 等 build system 的概念都有在 turbo tasks 中实现，上层 turbopack 相当于在 turbo tasks 的基础上对 bundler 的具体任务进行描述。这样看其实 incremental computation engine 本身就是一种 build system，同样基于 incremental computation engine：DICE 的 buck2 也类似，DICE 已经覆盖了 build system 中的核心功能， buck2 在其基础上实现将用户描述的任务作为 DICE 的任务进行执行 ^[13] 。

Turbopack 整体统一基于 turbo tasks，使用 suspending + ctRebuilder 的组合，实现整体的 Minimality 和 Early cutoff。

Vite

vite = suspending vtRebuilder

虽然 Vite 本身并不会 Bundle，但 Vite 在 dev 时还是会对任务不断进行执行，符合 build system 的定义，Vite 并不会对多个模块进行打包，而是对单个模块进行编译，所以 Vite 的任务逻辑其实很简单，就是编译模块。Vite 是在浏览器对模块进行请求时才去编译模块，浏览器没命中缓存才会发起请求，发起请求的顺序就是模块 import 的顺序，也是由浏览器决定的，所以可以看出 Vite 利用浏览器 ESM 模块系统作为自己的一部分 build system，属于 suspending + vtRebuilder 的组合。

利用浏览器 ESM 模块系统虽然会让本身的实现简单很多，但浏览器 ESM 模块系统本身并不是以 build system 为目标来实现的，相比真正的 build system 会带来很多限制，比如：

• 请求并发数量被浏览器限制 ➡️ 任务并发数量除了任务的依赖关系、机器资源以外，额外被浏览器限制。
• 浏览器缓存不能共享 ➡️ 构建信息或任务缓存不能共享，浏览器限制 vtRebuilder 不能修改为 ctRebuilder。

Rspack

incrementalRspack = foreach dirtyBitAndCtRebuilder

Rspack 本身也属于 pass-based bundler，但为了将 HMR 的性能从 O(project) 优化到 O(change)，Rspack 引入了 affected-based incremental ^[14] 。简单来说 affected-based incremental 会收集各个阶段的变更，后续阶段会根据收集到的变更计算出可能被影响的任务，从而只重新执行这些被影响的任务，减少任务的执行数量。

从 build system 的角度来讲，affected-based incremental 其实就是在 pass-based bundler 原有的 build system 基础上，引入新的 Rebuilder，让各个阶段之间的任务能够通过收集到的变更相互感知，以此能够对后续阶段的任务做 Early cutoff，通过添加 Early cutoff 这一特性来让 Rspack 更加 Minimality。这种方式更接近 self-adjusting computation：

The fundamental idea is to track the control and data dependencies in a computation in such a way that changes to data can be propagated through the computation by identifying the affected pieces that depend on the changes and re-doing the affected pieces. —— Self-Adjusting Computation ^[15]

根据变更找到被影响的输入，作为 dirty 的输入重新执行对应任务，这种实现相比于 incremental computation 不那么智能，但却是一种相对简单且有效的方式。

总结

• Minimality：对于重构建性能有很大影响。
• Early cutoff：影响 Minimality，实现 Early cutoff 的 bundler 往往比未实现的更加 Minimality。
• Parallelism：明确任务之间的依赖关系后，可以尽可能的对任务进行并发，suspending 往往使用 async/await 的 runtime 开多个 worker 进行并发。