diff3 与三路合并 ​

参考：Merging with diff3（James Coglan）
算法形式化可参考 Sanjeev Khanna、Keshav Kunal、Benjamin C. Pierce 的论文；Unix 上的 diff3 工具最早可追溯到 1988 年（Randy Smith）。

为什么合并不只是「两个快照拼起来」 ​

两个分支各自改同一文件时，直觉上会想到「Alice 改了第 3 行、Bob 删了第 5 行」这类描述。但行号会随编辑漂移：先插入再删除时，「第 5 行」指的早已不是同一段内容，甚至可能误删对方新增的行。
根本原因是：并发分支上的提交在时间上只有偏序，没有唯一「谁先谁后」——这和实时协作里的操作变换（OT）面对的是同一类困难，只是 VCS 里通常用三路合并而不是在线 OT 协议。

Git 为何仍能「算出差量再合并」 ​

不少系统以 patch/diff 为主存储提交；Git 存的是完整快照，并不持久化「版本之间的差异」。合并时仍可这样做：

1. 取要合并的两个版本 A、B；
2. 再取它们的共同祖先（merge base）上的版本 O；
3. 分别算 O → A、O → B 的差异，相当于从文本反推各自相对祖先改了什么；
4. 再把这些变更相对祖先对齐、综合，得到合并结果。

完成第 3、4 步的常见工具就是 diff3 合并算法。

输入输出：什么是「三路」 ​

算法输入是三个文本（通常按行处理）：

输出是一个合并文本；若某段 A、B 相对 O 都有修改且内容不一致，算法无法语义裁决，就标成冲突，交给人工处理。因为始终用到三个文件，所以叫三路合并（three-way merge）。

算法在做什么（直观流程） ​

1. 算两遍 diff：diff(O, A) 与 diff(O, B)。底层用 Myers 或别的 diff 实现都可以（见前文 Myers、线性空间 Myers）。
2. 找「在两边 diff 里都未改动的行」：这些行在三份文件里语义上对齐，用来把全文切成一段段 chunk。
3. 按 chunk 决策：
   • 三份相同：直接输出（无人修改）。
   • 仅 A 与 O 不同：采纳 A 的改法；仅 B 与 O 不同：采纳 B。
   • A、B 都与 O 不同：冲突——输出双方（以及可选的祖先片段）供用户解决。

文中「食材列表」例子（celery / garlic / onions / salmon / tomatoes / wine）说明：Alice 重排、Bob 重排后，中间一段在两边 diff 里都对不上祖先的同一段落，会被判为冲突；只有单侧相对祖先变化时则自动合并。

Git 里的冲突标记 ​

默认冲突块大致为：

<<<<<<< A 侧名称
……
=======
……
>>>>>>> B 侧名称

若设置 merge.conflictStyle = diff3（或使用独立 diff3 程序），冲突块中还会插入祖先 O 的内容，便于对照：

<<<<<<< A
……
||||||| Original（或 base）
……
=======
……
>>>>>>> B

实现上的一点提示（match set） ​

工程实现里常先对 O 与 A、O 与 B 做 diff，为「等于关系」建行号映射（match set），再在扫描时用映射判断「当前位置在三份文件中是否仍对齐到同一条祖先行」，从而交替找出匹配块与不匹配块，最后按规则发出 Clean / Conflict 等 chunk。Coglan 文中给出了与上述文字对应的循环与 write_chunk 逻辑。

局限：严重依赖底层 diff ​

diff3 本身规则并不复杂，但合并结果（尤其是冲突边界与是否误报冲突）对底层 diff 很敏感：同一次三路合并，换一种 diff 或不同「最短路」选择，无冲突时的最终结果应一致，但冲突块的范围与内容可能变，甚至出现看起来很怪的冲突。更细的失败模式与缓解思路，博文后续篇目有展开。

小结 ​

相关：Myers 差分 · 线性空间 Myers