Home 分类 About
Git三路合并算法(Three Way Merge)

最近工作上需要用到git cherry-pick来生成一个特殊的软件版本，具体要求如下

commit和branch如下图：

G <-- master
|
F2
|
E
|     F2  <-- my-goal
F1   /
|   F1
D  /
| C <-- v3.0.1
|/
B
|
A

具体的做法是：

  1. git checkout -b my-goal v3.0.1
  2. git cherry-pick F1
  3. git cherry-pick F2

其中遇到很多问题，例如：

  1. cherry-pick F1后无法编译，因为F1依赖D中的一些变更
  2. 通过git命令进行cherry-pick F2出现大量冲突，后来通过人工肉眼进行对比修改，可以成功cherry-pick

对于第1个问题：要么就把D也cherry-pick过来，要么手动把D的部分必要修改（F1依赖的部分）也加过来。

对于第2个问题：既然人可以成功解决冲突，为啥git不能自动帮我解决呢？这就涉及到git的merge算法。

git merge文件是以行为单位进行一行一行进行合并的，但是有些时候并不是两行内容不一样git就会报冲突，因为git会帮我们自动进行取舍，分析出哪个结果才是我们所期望的，如果git都无法进行取舍的时候才会报冲突，这个时候才需要我们进行人工干预。那git是如何帮我们进行merge操作的呢?

在介绍git merge算法前，先来看一个比较简单的算法：Two-way merge。

Two-way merge

Two-way merge解决的问题是：如何把两个文件进行合并。

举个例子，假设你和另外一个人同时修改了一个文件，这时merging算法看到了这两个文件，如下图：

merging算法发现两个文件大部分都一样，只有30行不一样，

但是merging算法怎么知道是你修改了30行还是另外一个人修改了？可能会有以下几种情况：

  1. Mine版本没有修改，Yours版本修改了内容（从Print("bye") 修改 Print("hello"))
  2. Yours版本没有修改，Mine版本修改了内容（从Print("hello") 修改 Print("bye")）
  3. Yours和Mine都修改了内容，（Yours从???修改成Print("hello")；Mine从???修改成Print("bye")
  4. Yours和Mine都增加了一行

对于一个merge算法来说，该怎么处理上述4中情况呢？

  1. Mine版本没有修改，Yours版本修改了内容 => 应该选Yours版本
  2. Yours版本没有修改，Mine版本修改了内容 => 应该选Mine版本
  3. Yours和Mine都修改了内容 => 需要手动解决冲突
  4. Yours和Mine都增加了一行 => 需要手动解决冲突

由于缺乏必要的信息，Two-way merge根本无法帮助我们解决冲突，TA只能帮助我们发现冲突，需要手动解决冲突。

如果让merging算法知道更多一些信息，merging算法是否可以帮助我们自动解决一些简单的冲突呢？下面来看一下Three-way merge算法。

Three-way merge

Three-way merge是在Two-way merge的基础上又增加了一个信息，即两个需要合并的文件修改前的版本。如下图所示，merge算法现在知道三个信息：

  1. Mine：需要合并的一个文件
  2. Yours：另一个需要合并的文件
  3. Base：两个文件修改前的版本

这时merging算法发现：

说明Yours对这一行做了修改，而Mine对这行没有做修改，因此对Yours和Mine进行merge后的结果应该采用Yours的修改，于是就变成Print("hello")。

这就是Three-way merge的大致原理。

Three-way merge的一个复杂案例

我们来看一个更加复杂的案例，如下图：

按行对比两个文件后，merging算法发现有3个地方不一样，分别是：

  1. 30行：上文描述的冲突案例
  2. 51行：有一个for循环被同时修改
  3. 70行：Mine的版本里面新增了一行

我们来看一下这三种冲突改怎么解决：

  1. 30行：只有Yours修改了，因此使用Yours的版本
  2. 51行：Yours和Mine都修改了，需要手工解决冲突
  3. 70行：Mine新增了一行，因此使用Mine的版本

使用Three-way merge进行merge

我们来看下git是如何使用Three-way merge来进行git merge操作的。

先来看下git merge在官网的定义：

git-merge - Join two or more development histories together

即把两个或两个以上的开发历史进行合并。

这样讲比较抽象，来看一个简单的例子，假设我们有2个branch：

第一次Merge：main -> task001

我们在task001上开发了一段时间，需要把main上的修改合并到task001，这时可以运行

$ git checkout task001
$ git merge main

merge后结果如下

merge的过程其实就是使用Three-way merge，其中

  1. Base = commit 1
  2. Mine = commit 4
  3. Yours = commit 3

merge后会生成一个新的merge节点commit 5，并且commit 5会同时依赖commit 3和commit 4。

第二次Merge：task001 -> maim

我们继续在task001上开发了几个commit后，终于完成了任务，需要把task001合并会main，这时可以运行

$ git checkout main
$ git merge task001

这次merge的过程也是一次Three-way merge，其中：

  1. Base = commit 3
  2. Mine = commit 7
  3. Yours = commit 6

Recursive three-way merge

一般情况下Base会选择Yours和Mine节点的最近的公共祖先。

但是有的时候最近的公共祖先不是唯一的，例如出现如下图所示的情况：

merge X'' Y'和X' Y''的时候发现有两个节点都符合最近的公共祖先，即：

我们称这种情况为：Criss-cross-merge，这时就需要用到Recursive three-way merge算法，具体步骤如下：

  1. 先把候选的两个最近的公共祖先递归调用merge，生成成一个虚拟的节点
  2. 然后让这个虚拟节点作为Base

git软件中使用的就是Recursive three-way merge算法。

使用Three-way merge进行cherry-pick

cherry-pick在官网的定义如下：

git-cherry-pick - Apply the changes introduced by some existing commits

即把已经有的commit apply到其他分支，git cherry-pick其实也是使用Three-way merge，其中：

  1. Mine = 执行cherry-pick时所在的branch的HEAD
  2. Yours = 被cherry-pick的那个commit
  3. Base = 被cherry-pick的那个commit的前一个commit

这样讲比较抽象，举个例子：

E <-- master
|
D
| C <-- foo_feature(*)
|/
B
|
A

假设我们目前在foo_feature分支，运行git cherry-pick D，这时Three-way merge的参数：

假设我们目前在foo_feature分支，运行git cherry-pick E，这时Three-way merge的参数：

使用Three-way merge进行rebase

rebase官方定义如下：

git-rebase - Reapply commits on top of another base tip

即使用其他分支作为基础，重新apply当前分支所有的commit，git rebase的过程可以看做是不断的做git cherry-pick，举个例子：

E <-- master
|
|   F <-- foo_feature(*)
D  /
| C
|/
B
|
A

在foo_feature branch运行下面运行git rebase master命令，就会变成下面的样子：

E <-- master
|
|       F <-- foo_feature(*)
|      /
|     C
D    /
|   E
|  /
| D
|/
B
|
A

相当于运行了下面几个命令：

git checkout master
git checkout -b foo_feature_rebased
git cherry-pick C
git cherry-pick F

参考

Written on July 24, 2019