# 开发报告:将 petgraph 迁移重构为 MoonBit > 项目:`I3eg1nner/petgraph` —— Rust 图算法库 **petgraph** 的 MoonBit 移植 > 仓库:(本地工作目录 `/data/my/moonbit-petgraph`) > 配套文档:[设计文档 `DESIGN.md`](./DESIGN.md) · [测试文档 `测试文档.md`](./测试文档.md) · > [第三方来源 `THIRD_PARTY.md`](./THIRD_PARTY.md) · [进度跟踪 `TODO.md`](./TODO.md) > **修订记录** > > - **初始交付**:聚焦核心子集,75 → 133 个测试。 > - **2026-06-03**:接口地道化重构(惰性 `Iter` 访问器、不透明 `Graph`、`toposort` / > `bellman_ford` 改 `raise`),并为公开入口补充 doc-test 示例 —— 145 个测试。 > - **2026-08-15(本轮,即本报告当前描述的状态)**:工具链升级到 > `moon 0.1.20260807` / `moonc v0.10.7`,命名空间统一为 `I3eg1nner/petgraph`, > 并用**六路并行 worktree** 完成一次大规模扩展 —— 实现代码 7118 行、测试代码 8218 行、 > **331 个测试在 wasm / wasm-gc / js / native 四后端全绿**,`@algo` 对外暴露 35 个顶层入口。 > 本轮还发现并修复了**两个真实缺陷**(详见 §5.1、§5.2)。 --- ## 1. 项目目标与成果 将 Rust 的 petgraph(约 2.8 万行,含 4 种图结构 + 约 30 个算法)以**地道的 MoonBit** 重新 实现,交付一个结构清晰、充分测试、可复现、有持续集成与完整文档的图算法库。首轮交付的是 "聚焦核心"子集;本轮把算法面从 10 个扩展到 35 个,并补齐了 `@graph` 的边引用/变换 API 与 `@visit` 的视图适配器。 **当前成果一览(除标注为"CI 强制"的两项外,均经本次实测):** | 维度 | 成果 | |------|------| | 源码规模 | 55 个实现 `.mbt`(7118 行)+ 25 个测试 `.mbt`(8218 行),共 80 个 `.mbt` 文件 | | 包结构 | 5 个内聚库包 + 1 个根门面 + 1 个演示程序,依赖关系无环 | | 核心数据结构 | 邻接表 `Graph[N, E]`(有向/无向)、并查集、`EdgeRef` 边引用 | | 遍历 | `Dfs` / `Bfs` / `DfsPostOrder` / `Topo` + `depth_first_search`;`Reversed` / `NodeFiltered` / `EdgeFiltered` / `UndirectedAdaptor` 视图适配器;`Walker` 抽象 | | 算法 | `@algo` 对外 **35 个顶层入口**(见 §2) | | 测试 | **331 个用例**,`wasm` / `wasm-gc` / `js` / `native` 四后端全部通过 | | 覆盖率 | 行覆盖 **2311 / 2471 ≈ 93.5%**(`moon test --enable-coverage` + `moon coverage report -f summary` 实测) | | 质量门禁 | `moon check --target all --deny-warn` 零告警;CI 另以 `moon fmt` / `moon info` + `git diff --exit-code` 强制格式规范与 `.mbti` 公开接口不漂移 | | 文档 | README(文档即测试)、设计/测试/开发报告、第三方来源说明、进度跟踪 | | CI | GitHub Actions:check / fmt / info / test 四道验收门禁 + 四后端构建与测试 | 各包实现/测试行数: | 包 | 实现行 | 测试行 | 测试用例数 | |----|------:|------:|------:| | `graph` | 1261 | 1637 | 50 | | `unionfind` | 223 | 564 | 27 | | `visit` | 932 | 745 | 43 | | `dot` | 130 | 284 | 13 | | `algo` | 4502 | 4988 | 192 | | 根包(`README.mbt.md` + `petgraph.mbt`)| 23 | — | 3 | | 演示 `cmd/main` | 47 | — | 0 | | **合计** | **7118** | **8218** | **331** | --- ## 2. 范围界定 首轮采用"聚焦核心(focused core)"方案,本轮在同一套 `Graph[N, E]` 之上把算法面扩展到与 上游 petgraph 常用算法基本对齐。**注意:上一版报告中列为"排除范围"的最大流、Floyd-Warshall / Johnson、一般匹配、支配树、关节点/桥、凝聚图等,现已实现,不再排除。** ### 2.1 纳入范围(现状) - **`graph`** —— 邻接表 `Graph[N, E]`(有向 + 无向)、`NodeId` / `EdgeId` / `Direction`、 增删查改、邻居与边遍历、`from_edges` / `from_edges_undirected`、`reverse`、`clear`; 本轮新增 `EdgeRef[E]` 边引用类型与 `edge_references`、`edges`、`edges_connecting`、 `map`、`filter_map`、`retain_nodes`、`retain_edges`、`node_weights`、`edge_weights`、 `extend_with_edges`、`first_edge`、`next_edge`、`into_nodes_edges`;`NeighborSource` trait。 - **`unionfind`** —— 按秩合并 + 路径压缩的并查集。 - **`visit`** —— `Dfs` / `Bfs` / `DfsPostOrder` / `Topo`、事件驱动的 `depth_first_search`; 本轮新增 `Reversed`、`NodeFiltered`、`EdgeFiltered`、`UndirectedAdaptor` 四个视图适配器, 以及 `Walker` 抽象(四种遍历器都有 `iter()` / `walker()`)。 - **`algo`** —— 35 个顶层入口: - *加权最短路*:`dijkstra`、`astar`、`bellman_ford`、`spfa`、`k_shortest_path`、 `bidirectional_dijkstra`、`find_negative_cycle` - *全源最短路*:`floyd_warshall`、`johnson` - *结构与连通性*:`toposort`、`is_cyclic_directed`、`is_cyclic_undirected`、 `connected_components`、`kosaraju_scc`、`tarjan_scc`、`condensation`、 `has_path_connecting`、`is_bipartite_undirected`、`articulation_points`、`bridges`、 `simple_fast`(+ `Dominators` 类型) - *生成树与 Steiner*:`min_spanning_tree`(Kruskal)、`min_spanning_tree_prim`、 `steiner_tree` - *最大流*:`ford_fulkerson`、`dinics` - *组合优化*:`maximal_cliques`、`greedy_matching` / `maximum_matching`(+ `Matching` 类型)、 `dsatur_coloring`、`greedy_feedback_arc_set` - *路径枚举*:`all_simple_paths`、`all_simple_paths_multi` - *DAG 传递闭包/归约*:`dag_to_toposorted_adjacency_list`、`dag_transitive_reduction_closure` - *数值 trait*:`Measure`、`BoundedMeasure` - **`dot`** —— Graphviz DOT 导出。 ### 2.2 仍然排除的范围 - **替代图表示**:`StableGraph`、`GraphMap`、`Csr`、`MatrixGraph`、`adj::List`,以及 `Acyclic` / `Frozen` 包装。全部功能都建立在唯一的邻接表 `Graph[N, E]` 上。 - **解析**:petgraph 的 DOT 解析器与 graph6 编解码。本项目只**输出** DOT,不读取。 - **序列化(serde)**、**quickcheck 集成**、**`Ix` 内存宽度泛型**。 - **同构判定(VF2)**、**page_rank**、**`parallel_johnson`**(本移植无线程)。 排除项与理由的完整论证见 [`DESIGN.md` §1](./DESIGN.md)。 --- ## 3. 关键设计决策(Rust → MoonBit) petgraph 的 `Graph` 携带两个 MoonBit 难以优雅表达的类型参数, 本项目将二者都去除: 1. **去掉 `Ix` 索引宽度参数 → 固定为 `Int`。** `Ix` 在 Rust 中只为节省内存(u8/u16/u32); MoonBit 的 `Int` 为 32 位,恰好对应 petgraph 默认的 u32,足以覆盖一切现实图。 2. **去掉 `Ty` 有向性类型参数 → 改为运行时枚举字段。** petgraph 用零大小标记类型做静态分发, MoonBit 无此机制,且 petgraph 本身也在运行时读取 `is_directed()`。故定义 `enum Directedness { Directed; Undirected }` 作为图的字段。 3. **`NodeId` / `EdgeId` 用包装结构体而非类型别名。** 裸 `Int` 别名会让结点/边索引悄悄混用 (图代码的常见 bug 源),包装类型几乎零成本,且能派生独立的 `Hash` / `Debug`。 4. **保留侵入式邻接链表。** 每个结点存出/入两条边链表的头,每条边存两个方向的 next 指针及 两个端点;Rust 的 `[_;2]` 数组改为命名可变字段 + `next(dir)/set_next(dir,..)` 辅助方法, 使 `change_edge_links` 几乎逐行对译。 5. **轻量 trait 层,不复刻上游的 trait 体系。** **坚决不复刻** petgraph 庞大的 `GraphBase` / `Visitable` / `IntoNeighbors` / `IntoEdges` 家族,只保留两条主线: - `NeighborSource`(在 `graph` 包):"能给出结点数、结点 id 与某方向邻居"的最小接口, 供遍历与结构性算法泛型化使用。 - `Measure` / `BoundedMeasure`(在 `algo` 包):权重运算,见下条。 其余算法直接在具体 `Graph[N, E]` 上操作,辅以 `edge_cost` 闭包(对应 petgraph 的 `edge_cost: FnMut`),不把权重泛型塞进图类型。 6. **新增 `BoundedMeasure : Measure`,把上游两个数值 trait 合并为一个。**(本轮) `Measure` 只有 `zero` / `add` / `compare`,不足以支撑需要"无穷大哨兵"、"加法溢出检测" 和"减法"的算法。`src/algo/measure.mbt` 因此增加 ``` pub trait BoundedMeasure: Measure { fn max_value() -> Self fn checked_add(Self, Self) -> Self? fn sub(Self, Self) -> Self } ``` 为 `Int`(`max_value` = `2147483647`,`checked_add` 用符号法判溢出)与 `Double` (`max_value` = `+inf`,`checked_add` 永不报溢出、直接饱和)提供实例。它把上游的 `BoundedMeasure`(`max` / `overflowing_add`)与 `PositiveMeasure` / `Sub` 的减法部分 **合并成一个约束**,于是 `floyd_warshall`、`johnson`、`ford_fulkerson` / `dinics` 与 `steiner_tree` 共用同一条数值边界,不必各带一套 bound。 7. **`NeighborSource` 由 `pub` 改为 `pub(open)`。**(本轮)MoonBit 会**密封 `pub trait`**: 定义包之外的类型无法为它写 `impl`。而 `@visit` 的 `Reversed` / `NodeFiltered` / `EdgeFiltered` / `UndirectedAdaptor` 恰恰必须实现 `NeighborSource`,才能不加修改地接到 既有的 `Dfs` / `Bfs` / `DfsPostOrder` / `Topo` / `depth_first_search` 上。 改为 `pub(open)` **只放宽"谁可以实现"**,方法签名一个没动;代价是这条 trait 从此对外 开放实现,属于公开 API 承诺的一部分。备选方案(把适配器塞进 `@graph` 包)会让 `graph` 包承担遍历视图的职责,依赖方向也更难看,故未采用。 详尽论证见 [`DESIGN.md`](./DESIGN.md)。 --- ## 4. 开发流程与方法 ### 4.1 首轮:分阶段、依赖驱动的实施 按依赖关系把工作拆成可独立编译、独立测试的阶段: ``` P0 脚手架 → P1(graph ∥ unionfind) → P2(visit ∥ dot) → P3(algo) → P4(集成) ``` `graph` 与 `unionfind` 为叶子包,可并行;`visit`、`dot` 仅依赖 `graph`,可并行;`algo` 依赖三者;最后 P4 做集成(演示、README、文档、CI)。 ### 4.2 本轮:六路并行 worktree 扩展 本轮扩展是**六个 subagent 在各自独立的 git worktree 中并行推进**,每个 worktree 一条 `worktree-agent-*` 分支、一份独立的工作副本(`.claude/worktrees/agent-*`),再合并回 `main`。 拆分原则是**文件不相交**:每个工作包只新增自己的 `src/algo/*.mbt` / `src/visit/*.mbt` 与配套测试文件,尽量不碰他人文件。每个 agent 的输入都是**上游 Rust 源码 + 上游对应测试**, 要求在移植算法的同时把上游测试一并译过来(保留原 Rust 测试函数名)。 六个工作包与落地提交: | # | 分支 | 落地提交 | 内容 | |---|------|----------|------| | 1 | `worktree-agent-a55e62b9…` | `d0d64cb` | `articulation_points`、`bridges`、`simple_fast` / `Dominators`、`condensation`、`has_path_connecting` / `is_bipartite_undirected` | | 2 | `worktree-agent-a7ec30e5…` | `2696111` | `ford_fulkerson`、`dinics`、`min_spanning_tree_prim`、`steiner_tree`、`dag_to_toposorted_adjacency_list` / `dag_transitive_reduction_closure` | | 3 | `worktree-agent-a8a19ecb…` | `a589cfb` | `@graph` 扩展:`EdgeRef`、`edge_references` / `edges` / `edges_connecting`、`map` / `filter_map`、`retain_*`、权重迭代器等 | | 4 | `worktree-agent-a8e0900d…` | `592aff5` | `floyd_warshall`、`johnson`、`spfa`、`k_shortest_path`、`bidirectional_dijkstra`、`find_negative_cycle` | | 5 | `worktree-agent-ada5e36b…` | `3b6ebe3` | `maximal_cliques`、`greedy_matching` / `maximum_matching`、`dsatur_coloring`、`all_simple_paths(_multi)`、`greedy_feedback_arc_set` | | 6 | `worktree-agent-aa33293b…` | `1eb9922` | `@visit` 视图适配器 `Reversed` / `NodeFiltered` / `EdgeFiltered` / `UndirectedAdaptor` 与 `Walker` | 集成方式:第 1 个工作包以 fast-forward 落到 `main`,其余五个各产生一个合并提交 (`0be1757`、`fbce92d`、`e23e6f5`、`49c7e09`、`d7096c8`)。合并后在 `main` 上再做两件事: `84fdc30` 修复合并后跨包联测暴露的两个缺陷(§5.1、§5.2),`a5a0940` 统一重新生成六路合并后的 `.mbti` 接口文件。 这套流程有两处**必须如实记录的摩擦**: 1. **一个工作包不得不修改共享 trait。** 第 6 个工作包(视图适配器)必须把 `src/graph/traits.mbt` 里的 `NeighborSource` 从 `pub` 改成 `pub(open)`,否则 `@visit` 里的适配器类型根本无法实现它(§3.7)。这是本轮**唯一一次**跨越"只改自己文件" 边界的改动:改动本身只有 6 行、不动任何方法签名,合并时无冲突,但它说明"文件不相交" 的拆分原则对**类型系统层面的耦合**是失效的 —— 可见性、trait 约束这类东西天然是全局的。 2. **六个 worktree 都从陈旧基线开叉。** 六条分支全部 `Created from origin/main`,即 `9aa1d9c`;而当时本地 `main` 已经领先两个提交(`6a4ec0a` 加了 `BoundedMeasure` 与 命名空间统一,`811b828` 加了第三方来源说明与 CI 门禁)。也就是说,几个需要 `BoundedMeasure` 的工作包一开始拿到的是**没有这个 trait 的代码**。每个 worktree 随后都 执行了一次 `merge main` 补齐:五条快进到 `811b828`,第 4 个工作包只快进到 `6a4ec0a`, 差的那一个提交由最终的合并提交补上。教训是:**派发并行工作前先把基线推到远端(或显式 从本地 `main` 开叉)**,否则每个 worktree 都要付一次重新同步的成本,而且同步时机不同会 让分支基线参差不齐。 ### 4.3 测试保真:移植 petgraph 自身的测试 自首轮起就把"移植上游真实测试"作为保真手段:首轮移植了 58 条(保留原 Rust 测试名,置于各包 `*_ported_test.mbt`),**全部一次性通过、未触发实现修改**。 本轮把这条原则贯彻到每个新工作包:新算法的测试文件(`combinatorial_test.mbt`、 `flow_tree_test.mbt`、`paths_extended_test.mbt`、`connectivity_test.mbt`、 `graph/extended_test.mbt`)都在文件头注明上游来源文件,并保留上游 Rust 测试函数名 (部分以 `port:` 前缀标注)。按"沿用上游测试函数名"这一口径统计,当前 **331 个用例中约 161 个可追溯到上游的具体测试**,其余为本项目自研的交叉验证、边界与回归用例。逐包对照清单见 [`测试文档.md` §9](./测试文档.md)。 与首轮不同的是:**本轮确实抓出了缺陷**——`dinics` 的退化输入不终止,以及 `dijkstra` / `astar` / `bellman_ford` 在无向图上的遍历错误(§5.1、§5.2)。两者都是在六路 合并回 `main`、跑全量联测时暴露的,单独看任何一条分支都是绿的。 ### 4.4 TODO 与上下文管理 - 用任务系统跟踪阶段状态(pending → in_progress → completed)。 - 用 [`docs/TODO.md`](./TODO.md) 作为活文档,记录范围、设计决策、依赖图、风险与验证命令。 - 关键的、可复用的工具链经验沉淀为长期记忆(见 §5 与附录)。 --- ## 5. 遇到的主要问题与解决 ### 5.1 无向图上 `dijkstra` / `astar` / `bellman_ford` 的遍历缺陷(本轮最严重的实现缺陷) **现象。** 在无向图上,这三个加权最短路算法会把**可达结点报成不可达**;从图的另一端搜索 时结果还不对称。 **原因。** 一条无向边在存储上**只存一次**,带一个固定的 `(src, dst)`,但它会出现在 **两个端点**的关联边链表里。三个算法当时都是"遍历 `edges_directed(node, Outgoing)`,再 无条件取这条边存储的 `dst` 当邻居": ``` for edge in g.edges_directed(node, Outgoing) { guard g.edge_endpoints(edge) is Some((_, next)) else { continue } ... } ``` 于是任何被存成 `(other, node)` 的无向边,读出来的 `dst` 就是 `node` 自己 —— 搜索直接 **走回起点**。结果是算法只探索"碰巧存对方向"的那些边,其余邻居被静默丢弃。 **修复。** 三处统一改为遍历 `Graph::edges(node)`。这个访问器会对每条关联边做端点规范化, 保证 `target` 是**背离 `node`** 的那一端,正是 petgraph `Edges` / `EdgeRef::target` 的语义: ``` for eref in g.edges(node) { let next = eref.target ... let next_score = node_score.add(edge_cost(eref.id)) } ``` 有向图行为不变:对有向图 `edges(a)` 恰好就是 `a` 的出边。修复与回归套件在提交 `84fdc30`, 回归用例见 `src/algo/undirected_regression_test.mbt`(所有夹具都故意把边"反着存",即以较大 索引作 source,使有缺陷的代码路径只能报出源点自己)。 **为什么之前没暴露。** 首轮 `algo` 中 `dijkstra` / `astar` / `bellman_ford` 的用例 (`src/algo/path_test.mbt`)**全部是有向图**;唯一一个无向夹具是 `bellman_ford` 的负环 doctest(`dijkstra_ported_test.mbt`),而它的每条边都恰好"正着存"(source 索引小于 target), 有缺陷的代码路径照样能走通。缺陷因此完整地落在首轮的测试盲区里,直到本轮六路合并后的全量 联测才暴露(修复提交 `84fdc30` 位于全部六个工作包合并之后)。 ### 5.2 `dinics` 在 `source == destination` 时不终止 **现象。** 一次 `dinics(g, source=a, destination=a, ...)` 的调用**超过 2 分钟仍未返回** (本地实测超时),而同一输入下 `ford_fulkerson` 正常返回。 **原因。** 层次图始终把 destination 放在一个正的层级上,外层循环因此永远看不到"层级为 0" 的终止条件;而每一轮找到的增广路都是空的,流量一点不增 —— 于是死循环。**上游 petgraph 有 同样的缺陷**,并非本移植引入。 **修复。** 在 `dinics` 入口显式挡掉这一退化输入,报告零流量,与本来就能正常终止的 `ford_fulkerson` 保持一致: ``` if source == destination { return (max_flow, flows) } ``` 理由记录在代码注释里:**不终止比与上游行为有出入更糟**。回归用例见 `src/algo/flow_degenerate_test.mbt`,同时覆盖"汇点不可达"这一相邻的退化情形,并要求 `dinics` 与 `ford_fulkerson` 给出相同答案。 ### 5.3 工具链升级到 `moon 0.1.20260807` / `moonc v0.10.7` 带来的迁移 升级后 `moon check --deny-warn` / `moon test --deny-warn` 出现两类新告警,均已迁移完成 (提交 `6a4ec0a`): - **空 Map 字面量 `{}` 被弃用 → 改写为 `Map([])`。** 迁移提交改了 6 处,例如 `let scores : Map[@graph.NodeId, K] = {}` 改为 `= Map([])`。 - **非穷尽的 `guard ... is Some(x)` 需改用 `guard!`。** 新工具链要求把"故意在不匹配时 panic"的守卫显式标注为 `guard!`,否则报非穷尽告警;迁移提交改了 7 处,集中在测试夹具里。 本轮新增的代码一律沿用新写法,目前全仓共有 26 处 `Map([])` 与 13 处 `guard!` (后者也出现在 `matching.mbt` 的内部不变量断言中)。 此外,升级前还处理过一次 `try?` 的弃用(提交 `88e5312`,改为 `try … catch … noraise`)。 ### 5.4 早期问题(保留记录) 1. **`Show` → `Debug` 迁移。** 早期工具链弃用 `Show` 作为调试输出:`derive(Show)` 与对组合值 调用 `inspect` 都会告警。本想用 `warn-list` 抑制,但 `moon fmt` 会强制把 `moon.mod.json` 迁移到新版 `moon.mod` 格式,而后者不支持带连字符的 `warn-list` 键(词法错误)。 **最终方案:全面改用 `derive(Debug)` + `debug_inspect`**,并据此调整所有快照,实现零告警。 注意:`Debug` 下字符串插值 `"\{自定义值}"` 无法编译,需改用原始访问器(如 `\{dir.index()}`)。 2. **swap-remove 索引失效(最高风险点)。** `remove_node` / `remove_edge` 采用"末元素填洞 + `change_edge_links` 修补链接"。MoonBit 的 `Array` 没有 `Vec::swap_remove`,需手写 `arr[i]=arr[last]; arr.pop()` 复刻语义,并用末尾哨兵 `END` 替代 petgraph 的 `IndexType::max()`。该部分以白盒不变量测试严防死守(删中间/末尾结点、自环、多种删边顺序); 本轮新增的 `retain_nodes` / `retain_edges` 复用同一套删除路径,并补了对应的不变量用例。 3. **优先队列方向。** 核心库 `@priority_queue` 是按 `Compare` 的**大顶堆**;Dijkstra/A*/Kruskal 需要小顶。复刻 petgraph 的 `scored::MinScored`,令其 `Compare` 对权重**取反**,使最小代价 先弹出。 4. **降序 range 不迭代(被交叉验证抓出的真 bug)。** 见测试文档 §7:`(len-1)..=0` 在 MoonBit 中不会迭代,导致 `kosaraju_scc` 返回空,由"tarjan ≡ kosaraju"交叉用例发现并修复。 5. **新版配置格式与构建目录。** 本工具链启用 `rr_moon_mod`/`rr_moon_pkg`,`moon fmt` 会把 `moon.mod.json`/`moon.pkg.json` 迁移为新版 `moon.mod`/`moon.pkg`,构建目录是 `_build/` (非 `target/`)。`.gitignore` 已相应更新。 --- ## 6. 复现与验证 从干净状态完整复现(标 ✔ 的命令在本轮由本机实测,其余由 CI 每次 push / PR 执行): ```bash export PATH="$HOME/.moon/bin:$PATH" cd moonbit-petgraph moon version --all # ✔ moon 0.1.20260807 / moonc v0.10.7 moon clean moon check --target all --deny-warn # ✔ 全后端静态检查,零告警 moon fmt && git diff --exit-code # 格式必须已规范化 moon info && git diff --exit-code # .mbti 公开接口必须已提交且最新 moon test --target all # ✔ 331 个测试 × 4 后端,全部通过 moon test --enable-coverage && moon coverage report -f summary # ✔ 2311/2471 moon run src/cmd/main # 运行演示 ``` 前四条正是 CI(`.github/workflows/ci.yml`)强制执行的验收门禁;第二个 job 再在 `wasm` / `wasm-gc` / `js` / `native` 四个后端上分别构建与测试。 演示程序(`src/cmd/main/main.mbt`)复刻 petgraph README 的例子:构造 4 元环无向图,打印 从结点 0 出发的 Dijkstra 距离、Kruskal MST 保留的边数,以及该图的 DOT 文本。 --- ## 7. 目录结构 ``` moonbit-petgraph/ ├── moon.mod # 模块元数据(I3eg1nner/petgraph,新版格式) ├── README.md -> src/README.mbt.md # 文档即测试(软链)· README.zh.md 中文版 ├── LICENSE-MIT / LICENSE-APACHE # 双许可,与上游一致 ├── .github/workflows/ci.yml # 四道验收门禁 + 四后端构建测试 ├── docs/ │ ├── DESIGN.md / TESTING.md / TODO.md / THIRD_PARTY.md │ ├── demo-graph.svg # 由本库 @dot 输出经 Graphviz 渲染 │ └── 测试文档.md / 开发报告.md # 中文文档 └── src/ ├── graph/ # 邻接表核心:graph / access / mutate / neighbors / index / │ # builder / iters / edge_refs / transform / retain / traits ├── unionfind/ # 并查集 ├── visit/ # 遍历:dfs / bfs / dfs_post_order / topo / dfs_visit / visit_map │ # 适配器:reversed / filter / undirected_adaptor / walker ├── dot/ # DOT 导出 ├── algo/ # 35 个算法入口 + measure(Measure / BoundedMeasure)+ scored ├── petgraph.mbt # 根门面(模块文档 + version) ├── README.mbt.md # 受测使用示例 └── cmd/main/ # 可运行演示 ``` 每个包内还有 `pkg.generated.mbti` —— 由 `moon info` 生成并提交的公开接口快照,CI 会用 `git diff --exit-code` 保证它不会悄悄漂移。 --- ## 8. 后续可迭代方向 - **补充图结构**:`StableGraph`(稳定索引)、`GraphMap`、`Csr`、`MatrixGraph`、`adj::List`。 其中 `StableGraph` 价值最高:上游有相当一批测试(尤其是 `steiner_tree`、`retain_*` 的 删除场景)只在 `StableGraph` 上跑,目前只能跳过。 - **补充算法**:同构判定(VF2)、`page_rank`、图生成器(`generate` feature)。 - **输入侧**:DOT 解析、graph6 编解码。 - **工程**:发布到 mooncakes 包仓库;补充基准测试;把 `Measure` / `BoundedMeasure` 扩展到 更多数值类型。 - **上游回馈**:§5.2 的 `dinics` 不终止是上游 petgraph 同样存在的缺陷,值得向上游报告。 --- ## 附录:开发过程中遇到的错误与误区(踩坑全记录) 本附录如实汇总移植全过程(首轮 + 本轮扩展)中遇到的工具链问题、语言特性陷阱、配置迁移坑和 实现缺陷,供后续 MoonBit 项目参考。按类别归纳,每条给出**现象 → 原因 → 解决**。 ### A. 工具链 / 构建系统 | # | 现象 | 原因 | 解决 | |---|------|------|------| | A1 | `moon new petgraph_mbt --lib` 报错 `tip: to pass '--lib' as a value...` | 该版本 `moon new` 的 CLI 用法已变 | 改为手工搭建目录与配置文件 | | A2 | 构建产物 `_build/` 差点被 git 跟踪(初版 `.gitignore` 只忽略了 `target/`) | 新工具链的构建目录是 **`_build/`**,不是旧的 `target/` | `.gitignore` 同时忽略 `_build/`、`target/`、`.mooncakes/`,并 `git rm -r --cached _build` | | A3 | 多个并行 subagent 跑 `moon` 时偶发 "another instance" 锁错误 | `moon` 对整个 workspace(`_build/`)加构建锁,并发调用相互阻塞 | 首轮:约定每个 agent 只改本包目录、遇锁重试。**本轮改用独立 git worktree**,每个 agent 有自己的工作副本与 `_build/`,构建锁天然不再冲突 | | A4 | `moon check` 默认只测一个后端 | 默认 `wasm-gc` | 用 `moon check --target all` 覆盖 wasm / wasm-gc / js / native | | A5 | 升级到 `moonc v0.10.7` 后 `--deny-warn` 报新告警 | 空 Map 字面量 `{}` 与非穷尽 `guard` 被弃用/收紧 | `{}` → `Map([])`(迁移 6 处);故意 panic 的守卫 → `guard!`(迁移 7 处);见 §5.3 | | A6 | 早先 `try?` 报弃用 | 错误处理语法迁移 | 改写为 `try … catch … noraise`(提交 `88e5312`) | ### B. `Show` → `Debug` 调试输出迁移(首轮最耗时的一类) | # | 现象 | 原因 | 解决 | |---|------|------|------| | B1 | `derive(Show)` 报弃用告警 `[0027] deprecated_syntax` | 工具链正把调试输出从 `Show` 迁到 `Debug` | 自定义类型一律 `derive(Debug)` | | B2 | 对 `Option`/`Array`/元组等组合值调用 `inspect` 报 `[0020] deprecated` | `inspect` 走的是 `Show`-用于调试的旧路径 | 测试改用 `debug_inspect(v, content=...)`(prelude 自带,无需 import) | | B3 | 仅 `derive(Debug)` + `inspect` 直接编译错误 `[4018]` | `inspect` 需要 `Show`,`debug_inspect` 需要 `Debug`,二者不可混 | 统一 `derive(Debug)` + `debug_inspect` | | B4 | 改 `Debug` 后字符串插值 `"\{nodeId}"` 编译失败 | 插值需要 `Show`,而类型只派生了 `Debug` | 插值改用原始访问器,如 `"\{dir.index()}"` | | B5 | 切到 `debug_inspect` 后快照对不上:`Some(b)` 变 `Some("b")` | `Debug` 会给字符串加引号,旧 `Show` 不加 | 重新生成并人工核验快照 | | B6 | `Int?` 用 `assert_eq` 仍触发 `Show` 弃用告警 | `Int?` 只派生了 `Show` 而非 `Debug` | 改用 `json_inspect` 或布尔 `is Some(..) && ..` 断言 | | B7 | 多行字符串(DOT 输出)用 `debug_inspect` 被转义成单行,无法比对 | `debug_inspect` 会转义整串 | 用 `assert_eq` 对照 `#|` 多行字面量,并补一行空 `#|` 以匹配结尾换行 | ### C. 配置格式迁移(新版 `moon.mod` / `moon.pkg`) | # | 现象 | 原因 | 解决 | |---|------|------|------| | C1 | 想用 `warn-list` 屏蔽 B 类告警,写进配置后 `Lexing error` | 启用了 `rr_moon_mod`/`rr_moon_pkg` 特性,新版 `moon.mod` 不接受带连字符的键,且**不支持 `warn-list`** | 放弃屏蔽,改为从源头采用 `Debug` 约定(B 类) | | C2 | 保留 `moon.mod.json` 想绕开新格式,但 `moon fmt` 把它强制迁移成 `moon.mod` 并丢弃 `warn-list` | `moon fmt` 会**强制**把 `*.json` 配置迁到新格式 | 接受新格式;凡需 `moon fmt` 的项目都要按新格式组织 | | C3 | `pub typealias`、`fnalias`、`using @pkg {x as y}` 做"门面"再导出全部报弃用告警 | 这些再导出语法都处于迁移中 | 放弃 prelude 再导出层,改为让使用者直接 import 子包(`@graph`/`@algo`/...) | | C4 | 模块名先后改了三次(`petgraph_mbt` → `wuyaxin/petgraph` → `I3eg1nner/petgraph` → `I3eg1nner/petgraph`) | 需与 GitHub 远端和 mooncakes.io 发布账号一致 | 改名要同步 `moon.mod`、每个 `moon.pkg`、全部 `.mbti`、README 与文档;`moon info` 重新生成 `.mbti` 后必须一并提交 | ### D. MoonBit 语言特性陷阱 | # | 现象 | 原因 | 解决 | |---|------|------|------| | D1 | **降序区间不迭代** —— `for i in (len-1)..=0` 整个循环空转,致 `kosaraju_scc` 返回空 | MoonBit 的区间 `a..=b`/`a.. continue`) | 实现选择 | 每次从分数表取最优 `g`,个别结点可能被重复展开,但**结果仍最优** | | E4 | SCC 用例顺序对不上 | Kosaraju/Tarjan 均为**逆拓扑序**,且 SCC 内部顺序任意 | 比较前规范化(内部与外层都排序),对应 petgraph 自己的 `assert_sccs_eq` | | E5 | 邻居顺序看似"反了" | petgraph 与本实现都用**逆插入序**(侵入式链表头插) | 这是正确行为;测试要么期望该精确序,要么先排序 | | E6 | **无向边"只存一次、两端可见"** —— 按 `edges_directed(n, Outgoing)` + 边的存储 `dst` 取邻居,会走回 `n` 自己 | 无向边有固定的 `(src, dst)`,却同时挂在两个端点的链表上 | 一律走 `Graph::edges(n)`,它把 `target` 规范化为**背离 `n`** 的一端(petgraph `EdgeRef::target` 语义)。见 §5.1 | | E7 | `floyd_warshall` / `johnson` / 最大流 / `steiner_tree` 各自需要"无穷大"、"加法溢出检测"、"减法",而 `Measure` 只有 `zero`/`add`/`compare` | 上游把这些能力拆在 `BoundedMeasure` 与 `PositiveMeasure` 两个 trait 里 | 合并成一个 `BoundedMeasure : Measure`(`max_value` / `checked_add` / `sub`),四类算法共用。见 §3.6 | | E8 | `dinics(g, s, s)` 永不返回(实测超 2 分钟) | 层次图始终把 destination 放在正层级,终止条件永不成立;**上游同缺陷** | 入口显式挡掉 `source == destination`,报零流量,与 `ford_fulkerson` 对齐。见 §5.2 | ### F. 测试移植中的适配(范围/保真) | # | 误区/现象 | 处理 | |---|-----------|------| | F1 | 以为"petgraph 没有测试" | 实际有 200+ 测试函数(集成测试文件 + 内联 `#[test]` + quickcheck);本项目移植了其中**范围内的约 161 条**,见 [`测试文档.md` §9](./测试文档.md) | | F2 | petgraph 的 `Ix`(u8/u16/u32)宽度变体 | 本项目索引固定 `Int`,`_u8`/`_u16`/`_u32` 变体**合并为单个用例**(注明) | | F3 | petgraph 用 `g[idx]` 索引、`try_*` 返回 `Result`、`neighbors().count()`、MST 返回新图 | 分别适配为 `node_weight(..).unwrap()`、返回 `Option`、`.length()`、返回 `Array[EdgeId]` 后校验边数与总权重 | | F4 | `uf_rand` 等依赖 Rust 随机数 | 用确定性 LCG(固定种子)替代,保留"大量随机操作后校验一致性"的意图 | | F5 | 文档即测试(`README.mbt.md`)放在根包,导入未配置导致示例编译不过 | 把示例所需子包放进根包的 **test-import**;代码块用 ```` ```mbt check ```` 围栏 | | F6 | 上游若干测试只在 `StableGraph` 上跑(`steiner_tree`、`retain_*` 的删除场景) | 本项目无稳定索引图,这些用例登记跳过;等价语义改用 `Graph` 的删除路径 + 白盒不变量测试覆盖 | | F7 | 上游 `f32` 权重夹具 | `Measure` 只有 `Int` / `Double` 实例:整数夹具用 `Int`,`f32` 夹具改用 `Double` 再跑一遍 | ### G. 并行 worktree 工作流(本轮新增) | # | 现象 | 原因 | 解决 | |---|------|------|------| | G1 | 六条 agent 分支全部从 `origin/main`(`9aa1d9c`)开叉,而本地 `main` 已领先两个提交 | 派发时基线只推到了本地,没推到远端 | 每个 worktree 补跑 `merge main`(五条快进到 `811b828`,一条只到 `6a4ec0a`,余下差异由合并提交补齐)。**下次应先把基线推远端再派发** | | G2 | "每个 agent 只改自己的文件"这一拆分原则被破 | 视图适配器必须修改 `@graph` 的 `NeighborSource` 可见性,可见性/trait 约束是**全局耦合**,无法按文件切分 | 允许该工作包做这一处最小改动(6 行、不动签名),并在合并后单独提交 `.mbti` 重新生成(`a5a0940`) | | G3 | 各分支单独测都绿,合并后才暴露缺陷 | 缺陷是**跨工作包**的:新算法带来的无向夹具照出了老算法的遍历错误 | 合并后必须在 `main` 上跑一次全量四后端测试;本轮由此产出修复提交 `84fdc30` | | G4 | 合并后 `.mbti` 冲突/漂移 | 六个包都改了公开接口,各自生成的 `.mbti` 互不知情 | 合并完成后统一跑一次 `moon info` 重新生成全部 `.mbti` 并提交;CI 用 `moon info && git diff --exit-code` 兜底 | ### 总体经验 - **首轮最大的时间消耗来自工具链处于迁移期**(B/C 两类):`Show`→`Debug`、JSON 配置→新格式、 再导出语法弃用。应对原则是**顺应新方向**,而非与之对抗(如试图用 `warn-list` 屏蔽)。 - **交叉验证与"扩大夹具面"是缺陷的主要来源。** D1(降序区间)由"tarjan ≡ kosaraju"这条 交叉用例抓出;E6(无向遍历)在首轮完全落在盲区(见 §5.1),是本轮把无向夹具铺开、并在 合并后做全量联测才暴露的;E8(`dinics` 不终止)的回归用例则直接写成"`dinics` 必须与 `ford_fulkerson` 给出相同答案"。**没有一个缺陷是单点快照发现的。** - **移植上游真实测试的收益是分阶段显现的。** 首轮 58 条零修改通过,印证了核心的行为保真; 本轮把移植面扩大到约 161 条,才把无向语义和退化输入这两个盲区照出来。**"一次通过"不代表 没有缺陷,只代表测试面还不够宽。** - **白盒不变量测试**为 swap-remove 这类"高危但外部不可见"的操作提供了安全网,本轮 `retain_*` 直接复用了这套网。 - **并行 worktree 的正确姿势**:先把基线推到远端,再按"文件不相交"拆分;但要预先承认 **类型系统层面的耦合(可见性、trait、公共 trait 约束)无法按文件切分**,应提前指定由哪个 工作包负责、其余包只消费。合并后的**全量联测**是不可省的一步。