丹尼爾：Hi，蛋兄，周傑倫都出新專輯了，你咋還不更新啊，真的打算半年一更啊？

蛋先生：好像确實是這樣，要不，擇日不如撞日，今天聊聊？

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

蛋先生：最近搞的事情需要實現兩個應用項目的代碼合并，邏輯就完全參照 git merge 的基本原則，那就聊聊 git merge 吧

丹尼爾：git merge 我倒是經常用，不過卻從未關心過它内部是怎麼實現的。那你跟我講一下它的工作原理呗。

蛋先生：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: daniela: danielb: dx-b

a merge b 的結果: dx-b

2). o == b, o != a

假設内容如下：o: daniela: dx-ab: daniel

a merge b 的結果: dx-a

3). a == b, o != a

假設内容如下：o: daniela: dx-abb: dx-ab

a merge b 的結果: dx-ab

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

假設内容如下：o: dx-oa: dx-ab: 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 dx Could not find merge strategy 'dx'. Available strategies are: octopus ours recursive resolve subtree.

最後

丹尼爾：要不是我買了周傑倫的專輯，才想起你也好久沒更新了，也就不會有今天這一出了

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

丹尼爾：真快，又到了說再見的時候了

蛋先生：See you next time!

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部