Dune 规则引擎：依赖图构建、增量计算与并行调度机制解析

Dune 作为 OCaml 生态的主流构建系统，其核心竞争力不仅在于简洁的声明式配置语法，更在于底层规则引擎对增量计算与并行调度的深度优化。传统构建工具往往将 "构建脚本生成" 与 "执行" 分离（如 Ninja 模式），而 Dune 选择将两者统一在同一可执行文件内，通过反馈驱动的动态规则生成实现更灵活的构建策略。这种架构选择对底层计算模型提出了严苛要求：必须支持动态依赖发现、细粒度增量更新以及高并发并行执行，同时保持数百万节点规模下的性能可扩展性。

依赖图构建：从声明式规则到 DAG

Dune 的规则引擎以 ** 有向无环图（DAG）** 为核心数据结构。图中的节点代表派生值（编译产物、中间结果、配置计算值），边代表构建顺序约束。当用户定义 (library ...) 或 (executable ...) 等 stanza 时，Dune 并非立即生成完整的构建脚本，而是构建一个惰性求值的依赖图。

依赖图的构建遵循以下关键原则：

节点标识稳定性：每个规则被分配稳定的标识符（R0, R1, ...），按源码顺序排列。这种稳定性确保增量构建时节点身份可复用，避免因文件重排导致缓存失效。

动态边发现：与传统构建系统要求预先声明所有输入不同，Dune 允许规则在执行过程中动态发现依赖。例如，一个 PPX 预处理器可能根据源文件内容决定引入哪些额外依赖，这些依赖在规则首次执行时才被记录到图中。

反向图维护：系统同时维护正向依赖图（输入→输出）和反向依赖图（输出→输入）。反向图的作用是失效传播—— 当某个源文件变更时，通过反向边快速定位所有受影响的下游节点，触发重新计算。

Memo 增量计算：观察 - 验证 - 复用模型

Dune 3.0 引入的 Memo 库是支撑其增量能力的核心组件。Memo 的设计目标是在构建系统领域实现通用计算模型的统一：无论是运行外部命令（如 OCaml 编译器）还是执行内部 OCaml 函数，都通过同一套 memoization 机制管理。

Memo 的核心 API 可简化为：

val memoize
  :  name:string
  -> doc:string
  -> 'a input_ops
  -> 'b output_ops
  -> ('a -> 'b Fiber.t)
  -> ('a -> 'b Fiber.t)

其中 input_ops 和 output_ops 提供哈希与相等性判断操作，Fiber.t 是 Dune 内部使用的并发 monad。

观察记录机制是 Memo 的关键创新。当 memoized 函数首次执行时，系统会自动记录该函数的所有观察：读取了哪些文件、调用了哪些其他 memoized 函数、访问了哪些环境变量。这些观察构成该函数结果的 "依赖指纹"。

在后续构建中，若函数被再次调用且输入参数相同，系统首先验证观察是否仍然有效（文件未变更、依赖函数结果未变）。若验证通过，直接返回缓存结果；否则重新执行函数并更新观察记录。

这种设计带来了几个工程优势：

• 零配置依赖追踪：开发者无需手动声明函数依赖，系统通过运行时拦截自动捕获
• 跨构建缓存：有效结果可在不同构建会话间复用，不仅限于单次构建内
• 精确失效定位：仅重新计算真正受变更影响的节点，而非整个依赖子树

并行调度：Fiber 并发与任务窃取

Dune 的并行调度建立在 Fiber 并发模型之上。Fiber 是一种轻量级协作式线程，可在单个 OCaml 线程内多路复用，也可利用 OCaml 5 的多域（Domain）能力实现真正的并行执行。

依赖图的并行执行遵循以下策略：

拓扑序与并发性平衡：系统尝试在尊重依赖顺序的前提下最大化并行度。当多个节点的前置依赖均已满足时，这些节点可并发执行。Fiber 模型允许在单个构建规则内发起多个并发子任务（如同时编译多个独立的模块）。

任务窃取调度：对于大规模项目，Dune 采用工作窃取（work-stealing）策略分配任务。空闲的执行单元可从繁忙单元的任务队列中 "窃取" 待处理的独立节点，实现负载均衡。

动态依赖的并发挑战：动态依赖的存在使静态调度变得困难。Memo 采用投机执行策略：在依赖关系尚未完全确定时，系统可基于当前已知信息启动推测性计算；若后续发现新依赖导致之前的计算无效，则取消或重做相关任务。

工程实现要点

在实际项目中利用 Dune 规则引擎的增量与并行能力，需关注以下工程细节：

规则粒度控制：过细的规则粒度会增加依赖图规模，带来内存与调度开销；过粗的粒度则降低增量精度。建议将逻辑上独立的编译单元拆分为独立规则，但避免为每个文件创建单独的自定义规则。

输入稳定性：Memo 的缓存键基于输入参数的哈希值。若参数包含不稳定数据（如时间戳、绝对路径），会导致不必要的缓存失效。应使用相对路径和确定性数据作为规则输入。

调试与可观测性：Dune 提供 dune compute <function> <arg> CLI 命令用于调试 memoized 函数。结合 --trace 选项可输出依赖图遍历轨迹，帮助定位意外的全量重建问题。

循环依赖处理：尽管依赖图理论上是 DAG，但动态依赖可能导致运行时循环。Dune 通过 DFS 检测循环并在发现时生成用户友好的错误报告，指出涉及的规则链。

局限与权衡

Memo 模型并非没有代价。动态依赖的运行时追踪引入了额外开销，对于简单项目可能不如静态声明式系统高效。此外，观察验证机制需要维护完整的依赖历史状态，在数千万节点规模下内存占用成为挑战。Dune 通过分层缓存和持久化存储缓解这一问题，但在极端规模场景下仍需权衡精度与资源消耗。

参考来源

• Dune Blog: "A new general computation model for Dune" (https://dune.build/blog/new-computation-model/)
• Mokhov A., Alekseyev A. "Memo: an incremental computation library that powers Dune", OCaml Workshop 2022 (https://icfp22.sigplan.org/details/ocaml-2022-papers/4/Memo-an-incremental-computation-library-that-powers-Dune)

compilers