修改开源软件以后仍保持更新同步

git merge ―― 为什么比diff + patch好

2013.2.16, 北京

本文地址: http://www.jiangyouxin.net/2013/02/16/git_merge.html

基于开源软件做二次开发是很常见的。这类开发常常遇到的问题是，当我们已经针对开源软件做了很多修改，与上游主干版本之间已经渐行渐远；此时上游主干有了更新，此时如何把上游的更新与我们自己的修改合并起来？假定上游主干版本为A，我们在A的基础上开发了A'；此时上游主干更新到B，现在我们要做的事情就是相应更新到B'。

一个做法是用diff工具生成A'与A的差异（patch），然后在B上面应用这个patch，期望得到B'。用数学的公式表示就是：

B' = B + (A' - A) ・・・・ (i, using diff & patch)

如果使用git做版本控制，以上的做法是可行的，但不是最优的。更好的做法是以A为基础，生成A'和B两条分支，然后执行 git checkout B; git merge A'。有一种误解认为这个merge操作执行的就是上面的公式(i)，其实不然，git merge的算法叫做3-way merge（准确的说叫recusive 3-way merge，当两个分支有多个共同父亲时它比普通3-way merge表现得更好），用公式表示如下：

B' = merge(A, A', B) ・・・・ (ii, using 3-way merge)

(ii) 比 (i) 好在哪里？

用diff工具生成patch时，我们所做的每一处修改，会连同它的“定位信息”（行号，以及修改处前三行与后三行的原始文本）一并保存到patch中。patch被应用时，会在原文件中寻找“定位信息”，然后将修改应用。那么，当我们把 patch(A' - A) 在 B 上应用的时候，很有可能定位信息本身被修改了，这样patch会失败，此时需要手工修改patch文件。

3-way-merge能在很大程度上解决这个问题。对于diff & patch会失败的情况，很多时候merge能够成功；其余则会产生冲突，但修改冲突也比手工改patch更为人性化。

算法本身就不描述了，单举一个例子来说明吧：

1. 版本A

   mkdir test
   cd test
   git init 
   vi test.txt
   
   1111
   2222
   3333
   4444
   5555
   6666
   
   git add test.txt
   git commit -m "init"
   

2. 版本A'，位于分支b1

   git checkout -b b1
   vi test.txt  # 插入一行abcdefg，尾部增加一行bottom
   
   1111
   2222
   3333
   abcdefg
   4444
   5555
   6666
   bottom
   
   git add test.txt
   git commit -m "modified on b1"
   

3. 版本B，位于分支b2

   git checkout master -b b2
   vi test.txt  # 顶部增加一行add top line，“2222”做了修改，尾部增加一行bottom
   
   add top line
   1111
   22222222
   3333
   4444
   5555
   6666
   bottom
   
   git add test.txt
   git commit -m "modified on b2"
   

4. 版本B'，使用git merge成功合并

   git checkout -b testmerge
   git merge b1
   cat test.txt # 两条分支的修改成功合并，注意尾部的bottom也只增加了一行
                # 如果用 patch & diff 方法，
                #   因为patch的两个定位信息（行号、上下文）都遭到了破坏
                #   是一定不会成功的
   
   add top line
   1111
   22222222
   3333
   abcdefg
   4444
   5555
   6666
   bottom
   

从上面这个例子也可以基本看出3-way merge的算法：

• 两个分支中如果一个分支对某处做了修改，另一个分支未修改，则保留修改

• 两个分支如果都对某处做了修改，且修改内容相同，则保留修改（不是做两遍）

3-way merge在下面的情况下会产生冲突：

• 两个分支如果都对某处做了修改，且修改内容不同，则产生冲突

至于什么叫“某处”，是基于文件三个版本的LCS（最长公共子序列）确定的，就不赘述了。

参考：http://www.jiangyouxin.net/2013/02/16/git_merge.html