CVS合并算法

我记得不久前读到的一篇文章,CVS merge实际上使用diff3算法来执行合并。

这篇PDF文章 A Formal Investigation of Diff3, by Sanjeev Khanna, Keshav Kunal, and Benjamin C. Pierce 宾夕法尼亚大学的diff3算法详细介绍。

If主要关注合并算法本身的属性,而不是它如何与CVS集成。

标签,日期意识

从CVS手册页:

-j标记[:日期]合并标记指定修订的更改,或 指定了日期,标记是一个分支 标记,分支标记的版本 因为它存在于日期

2或3路和文本/二进制意识

从diff3手册页:

如果'diff3'认为 它正在比较的文件是二进制文件(a 错误,因为这样的比较是错误的 通常没有用。与“diff”一样, 你可以强迫'diff3 '考虑所有 将文件转换为文本文件并进行比较 通过使用“-a”或

比较期间的基本版本

根据链接的文章,基本版本是最后一个 常见的 文件的两个当前版本(A和B)之间的版本(O)。它首先使用双向diff算法来寻找O和A,以及O和B之间的最长公共子序列。

然后(引自文章)它:

... 取O所在的区域 合并重叠的部分, 导致交替顺序的 稳定(所有副本相等)和 不稳定(一个或两个副本) 图1(c)所示的块 最后,它检查了发生了什么变化 可以传播,如图所示 1(d)这里,第二个块被更改 仅在A中(通过插入4,5),因此 第四个区块在A和B中都有变化 B、 所以什么都不能传播。

您可以使用两种不同形式的“merge”命令,它们做的事情略有不同:

1. cvs up -j TAG
2. cvs up -j TAG1 -j TAG2

变量之间的区别在于如何选择“基本”版本,但任一变量的基本算法是,对于每个文件,CVS选择的两个版本之间的差异将应用于当前工作副本的顶部。

在第一种形式中,合并基是给定标记和工作副本修订的共同祖先。因此,假设您的本地版本为1.38(正面版本为38),您正在合并1.34.4.2(正面版本为34的分支4的第2版)-共同祖先将为1.34。我相信这个变体使用两个diff 1.34..1.38和1.34..1.34.4.2进行了三向合并,在不匹配的地方产生冲突。

在第二种形式中,您自己指定基础修订,因此最终结果与 cvs diff -r TAG1 -r TAG2 | patch 除了从CVS获取冲突标记。

这个 CVS 使用文件的三个修订版,将两者之间的差异合并到第三个版本中。实际合并不会使用签出的三个文件之外的任何信息。您可以在中查看详细信息 并行版本系统 RCS_merge 在里面 src/rcscmds.c ,它使用 call_diff3 从…起 diff/diff3.c (或类似的事情)。当然,你可以通过抬起头来满足你的好奇心 并行版本系统 你自己。