将两个补丁合并成一个补丁的算法？

Question

我试图实现的事情本来应该很简单，但却变成了一条兔子洞，我认为肯定有更好的方法。

假设你有两个连续的补丁文件（表示顺序更改），但你没有源文件本身。

如何将这两个补丁组合成一个单独的补丁，以表示组合后的更改集。将组合后的补丁应用于源文件的结果应与按顺序应用两个补丁的结果相同。所有上下文都应被保留。

是否有已知的算法可以解决这个问题？

例如，取这两个补丁：

@@ -1,1 +1,2 @@
+ add this first line
this line is just context

@@ -1,2 +1,2 @@
- add this first line
+ change the first line
this line is just context
@@ -7,2 +7,2 @@
context
- change this line
+ to this one
more context

结果将会是：

@@ -1,1 +1,2 @@
+ change the first line
this line is just context
@@ -7,2 +7,2 @@
context
- change this line
+ to this one
more context

我找到了唯一一个适用于这种情况的工具/库，但在测试中发现它存在不少缺陷，并且代码过于密集，以至于我无法弄清楚底层算法是什么：

https://github.com/twaugh/patchutils

- Samuel Stern

---

就合并补丁的程序而言：您可以生成一个文件，该文件具有与补丁中期望的行号和上下文行匹配的行，并将补丁应用于该文件，然后获得最终差异。 - LeGEC

为了实现无缝衔接，您需要拥有完全兼容的补丁：在所有受到第 1 .. n 个补丁影响的行上，第 n+1 个补丁应该具有与这些行完全匹配的上下文（行号和行内容）。 - LeGEC

要创建初始文件，您应该扫描所有补丁，以查看起始文件应具有哪些行。例如：以您的简单示例为例，您必须读取两个补丁才能发现起始文件至少需要有9行--或者是10行？--以便应用第二个补丁。 - LeGEC

@LeGEC 感谢您的建议！我尝试过类似的方法，但问题在于当获取最终差异时，空行的数量会导致问题，至少在我的测试中是这样。因此，我正在寻找一种直接合并补丁而无需重新进行差异处理的方法。 - Sam Stern

为什么不直接使用你现在从Git上拥有的内容呢？先应用两个补丁，然后再从这两个补丁中制作一个新的补丁，如何？ - A-_-S

Answer 1

首先，我修复了您的补丁文件中的语法错误：

• 补丁文件必须有文件头，因此我添加了---和+++行。
• 上下文行以单个空格开头，因此我在它们前面添加了 。
• @@ hunks中的数字必须与后续的行匹配，因此我将2更改为3，以包括more context行。

p1现在如下：

--- old
+++ new
@@ -1,1 +1,2 @@
+ add this first line
 this line is just context

p2现在是：

--- old
+++ new
@@ -1,2 +1,2 @@
- add this first line
+ change the first line
 this line is just context
@@ -7,3 +7,3 @@
 context
- change this line
+ to this one
 more context

运行combinediff p1 p2 的结果如下：

combinediff: hunk-splitting is required in this case, but is not yet implemented
combinediff: use the -U option to work around this

运行 combinediff -U1 p1 p2 的结果如下:

diff -U1 new new
--- new
+++ new
@@ -1 +1,2 @@
+ change the first line
 this line is just context
@@ -6,3 +7,3 @@
 context
- change this line
+ to this one
 more context

以下是您期望结果的两个不同之处：

• 生成的补丁中有@@ -1而不是@@ -1,1。这是允许的缩写。
• 生成的补丁中有@@ -6,3而不是@@ -7,3，这正确地考虑了第一个补丁添加的1行。

除了未实现的功能外，这对我来说看起来完全符合预期。

- Roland Illig

---

是的，combinediff 大部分情况下都能正常工作，尽管我已经发现了其中两个错误，并且 C 代码相当难以理解，因此我正在寻找一种指向通用算法方法的指针。 - Sam Stern