git merge 的（伪）形式化定义

2025-11-05

文件

每个文件是一个以行为单位的序列，例如下面的文件：

a
bc
d

就是序列 ，我们认为序列是 base-1 的，即从 开始编号

文件 的规模 是序列的大小，在这个例子中为

hunk

定义对文件的原子操作（hunk） 为三元组 ，其中 是一个以行为单位的序列（所以，你乐意的话，当然也可以视为一个文件）， 表示从原文件的第 行开始，删除 行，然后插入

的规模 是 ，领域 是区间

脚本

每个脚本是 互不相同的 hunk 的集合

表示将脚本 中的 hunk 按 降序（为了保证位置稳定）依次应用到 产生的新文件，举个例子：

文件 如下：

a
bc
d

脚本 如下：

那么 就得到如下文件：

e
a
f
gh
d

脚本 的规模 是其中所有 hunk 规模的总和，在这个例子中为

脚本 的领域 是其中所有 领域的并集

diff

对文件 ,，定义 ，结果是一个脚本，满足

这不构成一个定义，只是一个约束条件，实际结果通过 Myers diff algorithm 计算得到

merge

对文件 ,，定义 ，结果是一个文件

如果 ，那么没有合并冲突，可以按下式自动合并：

否则，需要先解决合并冲突，然后合并

注意，如果你在两个分支分别修改了一个文件的相邻两行，这会产生合并冲突！因为此时，如果把前一行的行号记作 ，那么 ，，，，这可以看作是 git 的一个小特性