写点什么

git merge 不为人知的秘密

作者:蛋先生DX
  • 2022 年 7 月 25 日
  • 本文字数:2195 字

    阅读完需:约 7 分钟

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 的原因。


丹尼尔:除了 recursivegit 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!

发布于: 4 小时前阅读数: 22
用户头像

蛋先生DX

关注

一源一世界 2019.03.03 加入

ncform / ncgen / nice-hooks 开源项目作者

评论

发布
暂无评论
git merge 不为人知的秘密_git merge_蛋先生DX_InfoQ写作社区