git merge 不为人知的秘密

丹尼尔：Hi，蛋兄，周杰伦都出新专辑了，你咋还不更新啊，真的打算半年一更啊？

蛋先生：好像确实是这样，今天刚好也是 InfoQ 签约作者第三季，择日不如撞日，今天聊聊？

丹尼尔：好啊，那聊些啥呢？

蛋先生：最近搞的事情需要实现两个应用项目的代码合并，逻辑就完全参照 git merge 的基本原则，那就聊聊 git merge 吧

丹尼尔：git merge 我倒是经常用，不过却从未关心过它内部是怎么实现的。那你就跟我讲一下它的工作原理呗

合并的基本原则: three-way

蛋先生：git merge 的基本原则是 three-way

丹尼尔：3 条路？啥东东？

蛋先生：简单讲就是有 3 个分支。假设就叫 a, o, b，其中 a 和 b 都来自于 o，如下所示：

丹尼尔：嗯，然后呢？

蛋先生：现在 a 和 b 要进行合并。假设你当前在 a 分支，然后运行 git merge b，那么合并结果是根据 a, o, b 之间的内容比较结果分析得出的

丹尼尔：哦，嗯，比较逻辑是什么呢？

蛋先生：Very 简单。只要 a, o, b 任意两个的内容一致，就放弃 o 的内容；如果都不一样，就冲突。如下图所示

丹尼尔：只要... (＠_＠;)

蛋先生：我还是列举下所有的场景吧，然后你就会明白了

1) o == a, o != b

假设内容如下：

o: daniel

a: daniel

b: dx-b

a merge b 的结果: dx-b

2) o == b, o != a

假设内容如下：

o: daniel

a: dx-a

b: daniel

a merge b 的结果: dx-a

3) a == b, o != a

假设内容如下：

o: daniel

a: dx-ab

b: dx-ab

a merge b 的结果: dx-ab

4) o != a, o != b, a != b

假设内容如下：

o: dx-o

a: dx-a

b: dx-b

a merge b 的结果: 冲突

<<<<<<< a  dx-a  =======  dx-b  >>>>>>> b

丹尼尔：哦，懂了，就是以 o 为基准来判断该保留哪个分支的内容，如果判断不了，就提示冲突，自行解决

蛋先生：没错！

丹尼尔：上面是假设 3 个分支要对比的文件都存在，那如果某个分支的文件被删除或有新文件，该怎么处理呢？

蛋先生：你可以把缺少的文件当作空内容文件来处理。嗯，这样说好像也不太准确。我还是再列举下场景吧。以下假设要比较各分支的 dx.txt 文件

1) o 有, a 有, b 没

• 假设 1: o == a

合并结果：删除文件

因为 o == a，所以取 b 的结果

• 假设 2: o != a

合并结果：保留文件，内容为 a 的内容

因为 o, a, b 互不相同，结果为冲突，但 b 没有文件，所以冲突结果直接取 a 的内容

2) o 有, a 没, b 有

与（1）类似，相当于把 a 换成 b

3) o 有, a 没, b 没

合并结果：删除文件

a == b，所以取 a 或 b 的结果，即删除

4) o 没, a 有, b 没

合并结果：取 a 的内容

o == b，所以取 a 的内容

5) o 没, a 没, b 有

与 (4) 类似，相当于把 a 换成 b

6) o 没, a 有, b 有

• 假设 1: a == b

合并结果：取 a（或 b）的内容

• 假设 2: a != b

合并结果：冲突

丹尼尔：漂亮，这下我完全搞懂了合并逻辑了

Diff 的实现算法：最长公共子序列

丹尼尔：但我还有一个疑问，对比文件内容的时候，是一行一行内容对比的吧

蛋先生：那是当然了

丹尼尔：那如果我加多一行，故意错开，岂不是都对不上了

蛋先生：当然...是不会犯这样低级的错误的啦。在实现 diff 的时候，是利用了 LCS（Longest Common Sequence，即最长公共子序列）的算法。用下图来简单了解一下

假设有两个字符串 S1 和 S2，那它们的最长公共子序列就是 abcd

S1: "abcde"  S2: " a1bc2d"

丹尼尔：哦。但这是字符串，该怎么应用到文件内容的 diff 上呢？

蛋先生：把图转一转，每个方块代表文件的一行内容，是不是就一样了

丹尼尔：是哦。通过 LCS 的算法，就算我故意错开了行，也不影响比较，因为相同内容的行总是能对得上

蛋先生：恩，不过这里只是两个文件的比较，而 three-way 是三个文件内容的比较，要稍微多做点事

丹尼尔：能讲得具体一点吗？

蛋先生：上个图吧。假设我们要合并 a 和 b 分支的 dx.txt 文件，先使用 LCS 来计算三个分支该文件内容的最长公共子序列（下图就是连线的内容，分别为 a,c,e 的行），然后以这些子序列对各个文件的内容行进行分割，分割的块（下图中杂乱曲线的部分）就是差异的部分，对这些块的内容进行 three-way 分析，即可得出这些内容块合并后的结果

丹尼尔：恩，终究还是一图胜千言啊，一看就明白了。讲了这么多，要不直接 show 下代码吧

蛋先生：一样的思路，可以有各种各样的实现。我自个实现了一个简单的版本，请移步到 codepen.io 查看。也可以去瞧瞧 node-diff3 的代码实现，它比较严谨，毕竟是一个可上生产的模块

丹尼尔：好咧，等会就去观摩观摩

小插曲

丹尼尔：我刚刚特意上网查了一下，git merge <branch> 的默认策略是 recursive，为啥叫递归呢？

蛋先生：还记得 git merge 的基本原则是 three-way 吗？a 和 b 的共同祖先是 o，但有些情况下，a 和 b 的共同祖先可能不止一个，这时就需要将这些共同祖先通过 three-way 进行合并，这个动作会一直往上递归到根祖先分支，所以这也是策略叫 recursive 的原因。

丹尼尔：除了 recursive，git merge 还有哪些合并策略呢？

蛋先生：这个就要看你安装的 git 的版本了。git merge 可以指定合并策略。这里有个小技巧，你可以故意给个不存在的策略名称，git 就会显示出所有可用的策略名称，如下所示：

$ git merge -s dxCould not find merge strategy 'dx'.Available strategies are: octopus ours recursive resolve subtree.

最后

丹尼尔：要不是我买了周杰伦的专辑，才想起你也好久没更新了，也就不会有今天这一出了

蛋先生：感谢提醒，合作愉快

丹尼尔：真快，又到了说再见的时候了

蛋先生：See you next time!