MarsTalk | Git三路合并算法

導言

最近工作上需要用到git cherry-pick來生成一個特殊的軟件版本,具體要求如下:- 基于v3.0.1的穩定版本- 加入2個只在master branch的Patch: F1和F2- 能編譯并通過ci測試相關的commit和branch關系如下圖:

G <-- master|F2|E|     F2  <-- my-goalF1   /|   F1D  /| C <-- v3.0.1|/B|A

具體的做法是:

1. git checkout -b my-goal v3.0.12. git cherry-pick F13. 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行不一樣,- 在`Yours`的版本里內容是:`Print("hello")`- 在`Mine`的版本里內容是:`Print("bye")`但是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算法`發現:- 修改前的`Base`版本里的內容是:`Print("bye")`- 在`Yours`的版本里內容是:`Print("hello")`- 在`Mine`的版本里內容是:`Print("bye")`說明`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:- main:master branch- task001:我們正在開發的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''`的時候發現有兩個節點都符合`最近的公共祖先`,即:

- `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的HEAD2. `Yours` = 被`cherry-pick`的那個commit3. `Base` = 被`cherry-pick`的那個commit的前一個commit這樣講比較抽象,舉個例子:

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

假設我們目前在foo_feature分支,運行git cherry-pick D,這時Three-way merge的參數:

- `Mine` = `C`- `Yours` = `D`- `Base` = `B`

假設我們目前在foo_feature分支,運行git cherry-pick E,這時Three-way merge的參數:

- `Mine` = `C`- `Yours` = `E`- `Base` = `D`

使用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(*)|      /|     CD    /|   E|  /| D|/B|A

相當于運行了下面幾個命令:

git checkout mastergit checkout -b foo_feature_rebasedgit cherry-pick Cgit cherry-pick F

以上就是今天的內容!不知道有沒有讓你更懂git一點點呢~Sch?nes Wochenende!我的2019周更計劃已完成:30/52[********............]