合并 (版本控制)

  关于与“合并 (版本控制)”标题相近或相同的条目页，请见“合并”。

例子：一个项目的版本控制的历史。合并为红色箭头

在版本控制中，合并（英语：merging），也称为整合（integration），是指当一个文件在多个独立分支中被修改后如何合并这些修改成为一个文件的操作。

合并可以是版本控制软件自动执行，但如果有冲突，就需要考虑手工合并。

合并算法

合并算法是一个热点研究领域，有多种不同的算法。

三路合并

C是最初, A与B是从C派生, D是最新输出版本

三路合并（three-way merge），首先考虑对文件A、文件B以及它们的共同祖先文件C做差异分析。对于文件中的每节(sector)，如果上述三个文件中有两个文件该节的内容一致，那么抛弃文件C中该节的内容，保留与文件C中不同的内容放到结果文件中。如果该节在三个文件中都不同，那么这个冲突需要手工合并。

三路合并被程序diff3实现，是基于文件锁的版本控制系统到基于合并的版本控制系统转变的核心。被CVS广泛使用.

递归三路合并

三路合并算法的基础技术是找到被合并文件的共同祖先文件。在遇到十字交叉合并（criss-cross merge）时，不存在独一无二最小共同祖先。

"Criss-cross-merge“问题。在左半边，2个区域被修改, $X$与$Y$. $X'$与$X''$是两个连续修改版本。右半边是解决办法：一个虚拟祖先(选线圆圈)被创建.

Git采取了递归三路合并(Recursive three-way merge)，对没有共同祖先的一对文件递归创建虚拟祖先。这一方法还可以用于有向无环图。

模糊修补包算法

修补包是一个文件，包含另一个文件的改变的描述。Unix传统使用修补包传播一个文本文件的改变，这个修补包可用命令"diff -u"生成，然后用命令patch把修补包应用到一个文本文件。

但patch程序也可以把一个修补包用于与最初产生该包的文件不是完全相同的文件。这称作模糊修补包应用(fuzzy patch application)。 GNU arch采用了这种方法。但模糊修补包应用是一种不太可信的办法，在上下文太少情况下可能会误用。

编织合并

编织合并(Weave merge)算法跟踪每行是被增加或是删除，产生结果信息。如果在一个版本中该行被删除，则结果文件就不包含该行。BitKeeper、GNU Bazaar、Codeville采用了此方法，对三路合并出错的情形能产生正确结果。

修补包交换

修补包交换(Patch commutation)改变修补包的应用顺序，形成一线性历史。效果上，当两个修补包产生于同一个环境，合并时，一个修补包被重写以便它可以在另一个修补包执行完毕后才使用。例如，修补包A在文件F的行7之后增加了行"X"，修补包B在文件F的行310之后增加了行"Y"，B需要重写为对文件F的行311之后增加行"Y"，以便能在修补包A使用后再使用修补包B。

Darcs、Git (称作"rebasing")采用了这一方法。

"patchutils" package中的Unix程序flipdiff实现了修补包交换.

外部链接

• Nair, Sarat. Versioning Systems and 3 Way merge process. Reflections of my thoughts blog. 2010-09-21 [2017-05-22]. （原始内容存档于2012-03-13）.  Simple way to understand 3-Way merge process
• Cohen, Bram. The new Codeville merge algorithm. Revctrl (邮件列表). 2005-05-05 [2017-05-22]. Message-ID <[email protected]>. （原始内容存档于2011-07-19）. 
• 3 way merging. Misuse blog. 2007-02-24 [2014-11-28]. （原始内容存档于2014-12-09）.  Review of several popular Merge tools from various manufacturers