Sapling Mononoke 变更集路径规模防护：O(changeset_paths) 复杂度风险、代码审查规则与流式处理实践

• 开发工具
• CLI
• 后端

本文解读 Sapling（Meta 开源的源码控制系统）中 Mononoke 服务端仓库内 changeset_path_scaling.md 这一条Severity: CRITICAL的 AI 代码审查规则：它专门针对“随变更集路径数量线性增长（O(changeset_paths)）”的代码模式。读完本文，你将掌握如何识别先收集全部路径再处理、逐路径发 RPC/查库等危险写法，并学会用有界并发流式处理、批量查询与显式大小检查等模式，在大型 codemod 提交和百万级目录下避免 OOM、超时与下游服务饱和。

规则定位：Mononoke 的 AI 代码审查规则体系

Sapling 仓库在 eden/mononoke/.llms/rules/ 目录下维护了一套供 LLM/AI Agent 在编写与审查 Mononoke Rust 代码时遵循的规则文件，入口 AGENTS.md 声明了整体上下文。这些规则以带 frontmatter 元数据的 Markdown 形式存在，例如strict标记是否严格适用、oncalls标记归属团队等。

本文涉及的changeset_path_scaling.md属于其中一条严格规则，其元数据定义如下：

name: changeset-path-scaling metadata: oncalls: ['source_control'] strict: true apply_to_path: 'eden/mononoke/.*\.rs$' apply_to_content: 'changed_files|file_changes|path|paths|manifest|diff|list_all'

可以推断其适用范围为：仅检查eden/mononoke/下的 Rust 源文件，且当代码内容命中changed_files、file_changes、path、paths、manifest、diff、list_all等关键词时才触发。这意味着任何涉及“遍历变更集路径、处理文件变更、操作 manifest、计算 diff、全量罗列”的代码都是本条规则的审查对象。

问题的本质：什么是 O(changeset_paths)

Mononoke 的核心提交对象是BonsaiChangeset。在 eden/mononoke/mononoke_types/src/bonsai_changeset.rs 中，它对外暴露了三个查看文件变更的入口：

• file_changes()：返回impl ExactSizeIterator<Item = (&NonRootMPath, &FileChange)>，源码注释明确保证迭代顺序为深度优先遍历序——“一旦某个树的全部变更都应用完毕，就不会再被引用”；
• file_changes_map()：直接返回底层的&SortedVectorMap<NonRootMPath, FileChange>，可按路径有序访问；
• simplified_file_changes()：将 tracked 与 untracked 变更合并成(&NonRootMPath, Option<&BasicFileChange>)，便于统一处理。

关键在于：这些 API 本身都是惰性迭代器，遍历单条路径的开销很小。真正的风险来自调用方如何消费这个迭代器。规则给出的定义是：

Operations that scale with O(changeset_paths) — iterating, collecting, or processing all paths in a changeset.

即任何“迭代、收集或处理变更集中全部路径”的操作，其复杂度都随路径数线性增长。单个变更集可触及的路径数是无上限的（unbounded），这是整套规则的出发点。

何时标记（When to Flag）

规则列举了四种应当标记为问题的模式：

而任何对变更集路径的循环，若没有大小限制（size limit）、分页（pagination）或流式处理（streaming），都应被标记。这一条覆盖了最容易漏网的情形：即使循环体本身很轻，O(n) 的全量扫描在 n 巨大时同样是风险。

何时不标记（Do NOT Flag）

规则同时划定了豁免边界，避免审查过度：

• 已经是流式/分页 API，按有界块处理路径的代码；
• 操作本身已被限定范围（例如先按已知的小集合过滤再处理）；
• 只操作单条路径或固定的少量路径的代码；
• 测试代码（test code）。

这说明该规则的审查目标是“无界全量扫描 + 无界下游调用”，而不是一刀切禁止任何对file_changes()的遍历。

反模式一：把所有路径收集进内存

规则给出了第一个典型反例：

let all_paths: Vec<_> = changeset.file_changes().collect(); for path in &all_paths { check_hook(path).await?; }

问题有两层：collect()先把全部路径物化到Vec，对数十万甚至百万路径的提交而言，这会一次性占据大量堆内存；随后逐路径check_hook(path).await又是串行的、无并发度的下游调用，总耗时随路径数线性放大。两者叠加，正是“OOM 或 timeout”的典型成因。

反模式二：逐路径数据库查询

第二个反例展示的是更隐蔽的“无界下游调用”：

for path in changeset.file_changes() { let metadata = db.get_file_metadata(path).await?; // ... }

虽然这里没有收集全部路径，但每一条路径都触发一次独立 DB 查询。一次包含几十万文件变更的提交，就意味着几十万次 RPC/查询往返。在高并发生产环境下，这会迅速打满数据库连接池或下游服务配额，造成“saturate downstream services”的连锁故障。规则对这类模式的核心判据是：是否存在批处理（batching）或分页（pagination）。

正确姿势一：有界并发流式处理

规则的第一个 GOOD 示例展示了 Rust 生态中处理异步迭代器的标准解法——try_for_each_concurrent：

changeset .file_changes() .try_for_each_concurrent(100, |path| async move { check_hook(path).await }) .await?;

要点解析：

• 不物化：从file_changes()迭代器直接消费，逐条处理，内存占用与路径总数无关；
• 有界并发：100是并发上限，既充分利用异步 I/O 的并行能力，又防止瞬间向服务端发起无界请求；
• 错误传播：try_前缀保证任一路径失败即中止并向上返回Err。

这是对“需要检查每个路径、且路径数可能极大”场景的最优解之一。

正确姿势二：批量数据库查询

针对逐路径 DB 查询的反例，规则给出的 GOOD 写法是分块批处理：

for chunk in changeset.file_changes().chunks(1000) { let metadata = db.get_file_metadata_batch(&chunk).await?; // ... }

核心思想是把每 1000 条路径打包成一次get_file_metadata_batch调用，将 O(n) 次往返压缩为 O(n/1000) 次。配合上游file_changes()的深度优先有序迭代，批处理还能保证按稳定顺序消费，便于实现续传与断点恢复。

为什么这是生产风险：规模现实

规则用“Why This Matters”一节解释了这条规则的现实依据：

Some repositories contain commits that touch hundreds of thousands of paths (codemod commits, large directory moves). ... Large directories (e.g., fbcode/third-party) compound the problem since a single directory listing can return millions of entries.

即两大数据事实：

1. 大提交客观存在：codemod（大规模机械改写）提交、大型目录移动（directory move）可以一次触碰数十万条路径；
2. 目录本身可以极大：像fbcode/third-party这类巨型目录，单次目录列举就可能返回百万级条目。

当这两种情况叠加时，任何 O(changeset_paths) 且无流式/批处理/分页的代码都会产生三种后果之一：进程OOM、请求timeout、或打爆下游服务（数据库、hook 检查、RPC 端点）。

仓库源码印证：Mononoke 内部如何安全消费变更集路径

这条规则并非纸上谈兵，Mononoke 自身实现可以佐证其正确模式。以 eden/mononoke/features/hooks/src/implementations/limit_commit_size.rs 中的LimitCommitSizeHook为例：

let mut commit_size = 0; let mut changed_files = 0; for (path, file_change) in changeset.file_changes() { let path = path.to_string(); // 1. 检查 path_overrides 是否提高该路径的限额 // 2. 命中 ignore_path_regexes 的路径直接 continue changed_files += 1; commit_size += file_change.size().unwrap_or(0); }

这是一个必须全量扫描但绝不物化的合法模式：

• 它没有collect出Vec，只维护两个标量计数器，内存为 O(1)；
• 它不发起任何逐路径下游调用，所有计算都在本地进行；
• 它用path_overrides、ignore_path_regexes做路径级正则过滤，相当于“先过滤再计数”，符合规则中“operations that are already bounded”的豁免精神；
• 同文件mod test中的test_limit_commit_size_removed_files、test_limit_commit_size_override等测试（见 limit_commit_size.rs）通过CreateCommitContext构造多个文件变更的提交，验证了计数与大小统计逻辑——这些测试场景本身就说明“提交可包含任意数量路径”是常态。

从源码结构看，Mononoke 中许多派生数据（derived data）管线（如 eden/mononoke/derived_data 下的 blame、fsnodes、manifest 相关模块）同样频繁调用file_changes，它们必须时刻遵循本文规则，否则在大型提交上会拖垮整个派生链路。

推荐实践与自查清单

规则给出的最终 Recommendation 可以概括为四句话：

1. 永远假设一个变更集可以触及无上限数量的路径；
2. 优先使用流式处理或分页，而不是先收集；
3. 对下游调用做批处理；
4. 处理需要并发时使用有界并发（bounded concurrency）。

最后还有一条兜底建议：如果确实必须收集全部路径，一定要加大小检查并尽早失败（fail early），抛出清晰错误，而不是默默走到 OOM。可以把上面的规则浓缩成提交前自查清单：

延伸阅读

本条规则与 .llms/rules/ 目录下的其他规则共同构成 Mononoke 的代码质量防线：例如mononoke_structure.md约束模块划分、derive_manifest_usage.md规范 manifest 派生 API 的使用、derived_data_merge_correctness.md与rederivation_safety.md保障派生数据正确性。它们大多遵循相似的 frontmatter 结构（strict、apply_to_path、apply_to_content），供 AI 审查与人类评审共用——而changeset_path_scaling.md因其CRITICAL严重级别，是所有涉及路径遍历的改动都必须最先对照的一条。

• 开发工具
• CLI
• 后端