理解 Darcs/补丁理论和冲突



冲突

到目前为止，我们只处理了合并彼此不冲突的补丁。下一个感兴趣的问题是 darcs 在它们确实发生冲突时应该如何表现。

考虑之前的 darcs 黑客马拉松示例，与往常一样，Arjan 决定购物清单需要一些啤酒。在这种情况下，Ganesh 决定你不能只靠苹果和饼干生活，并记录了一个将“意大利面”添加到 s_list 文件的补丁。现在他想知道 Arjan 在做什么，因此将啤酒补丁拉到他的仓库中，但糟糕！Arjan 和 Ganesh 的补丁冲突了！darcs 在这里应该如何表现？

Arjan 和 Ganesh 的补丁冲突

darcs 的答案是，两个补丁都互相抵消，因此它们都没有任何效果。最终的购物清单既没有啤酒，也没有意大利面。这听起来可能令人震惊，但并不像你想象的那么糟糕。Darcs 不会静默地删除你的代码。在取消两个补丁后，它会在你的工作目录中添加第三个补丁，该补丁指示冲突的双方，以便你可以选择你想要的那个。因此，你应用的任何解决方案都是一个依赖于两个冲突补丁的第三个补丁。如果你在此时对 Ganesh 的仓库执行了 darcs whatsnew，你将得到类似以下内容

v v v v v v 
beer
-----------
pasta
^ ^ ^ ^ ^ ^ 

我们如何知道我们有冲突？

直观地显而易见的是，Arjan 的补丁与 Ganesh 的冲突，但如果直觉不能转化为实际的 Haskell 代码，那么直觉就毫无用处。因此，第一个问题是首先知道我们是否发生了冲突。

所有这些都归结为交换。如果两个补丁的交换未定义，我们就会有冲突。让我们简要回顾一下上一章中描述的合并过程。上一章。当 Ganesh 试图拉取 Arjan 的补丁时，他试图通过执行以下顺序来使补丁适应他的环境：反转他自己的补丁，应用 Arjan 的补丁 $A$，将反转的补丁与 Arjan 的补丁交换，并丢弃他反转的补丁的邪恶继姐妹。正如我们所知，反转补丁很容易。Ganesh 的补丁被反转为一些从 s_list 文件的第 3 行删除“意大利面”的内容。另一方面，当我们尝试将其与 Arjan 的补丁交换时，我们遇到了故障。

为什么？仅仅因为这就是我们定义两种类型的补丁之间的交换方式。例如，Ganesh 和 Arjan 的补丁都是块补丁。两个相同文件块补丁的交换在 darcs 中使用类似于以下内容的 Haskell 代码定义（从 PatchCommute.lhs 简化而来）

commuteHunk :: FileName -> (FilePatchType, FilePatchType) -> Maybe (Patch, Patch)
commuteHunk f (p1@(Hunk line2 old2 new2), p2@(Hunk line1 old1 new1))
  | line1 + lengthnew1 < line2 = Just ...
  | line1 + lengthnew1 == line2 && nonZero = Just ...
  | line2 + lengthold2 < line1 = Just ...
  | line2 + lengthold2 == line1 && nonZero = Just ...
  | otherwise = Nothing
  where nonZero = lengthold2 /= 0 && lengthold1 /= 0 && lengthnew2 /= 0 && lengthnew1 /= 0 
        lengthnew1 = length new1
        lengthnew2 = length new2
        lengthold1 = length old1
        lengthold2 = length old2

只定义了四种情况。前两种情况涵盖了 p1 发生在 p2 之前文件部分的情况（即使像第二种情况那样撞到它）。后两种情况涵盖了相反的情况（p2 位于文件中的 p1 之前的部分）。但是，p1 和 p2 重叠的情况根本没有落入其中一种可能性。因此，我们遇到了冲突。

强制交换

现在我们知道我们遇到了冲突，我们现在需要以一种明智的方式处理这种冲突。我们不仅要处理手头的冲突，还要以一种允许冲突干净地传播到整个补丁序列的方式来处理它。好吧，darcs 基于交换，因此为了使一切顺利运行，我们需要确保事物继续交换。因此，我们将定义一个辅助的强制交换操作，我们只在发生冲突时使用它。

回想一下上一章中交换的定义

强制换向将执行类似的操作，但会带有一些奇怪的转折。与补丁$Y_{1}$和$X_{1}$执行与它们各自的祖先$Y$和$X$相同的更改不同，强制换向将为我们提供补丁，每个补丁都执行其他补丁执行的更改。也就是说，普通换向希望$Y_{1}$执行与$Y$大致相同的事情，但强制换向使其执行与$X$相同的事情。

操作	$Y_{1}$的效果	$X_{1}$的效果
正常换向	$Y$	$X$
强制换向	$X$	$Y$

效果

顺便说一句，我们需要一些术语来避免我们口误。总是谈论一个补丁与另一个补丁执行相同的更改并不是很方便，而这正是我们将会经常提到的东西。所以让我们简化一些内容。与其说补丁$Y_{1}$执行与$X$相同的更改，我们简单地说$Y_{1}$的**效果**是$X$。它是同一个想法，只是术语稍微平滑一些。

合并中的强制换向

让我们看看这对 Ganesh 和 Arjan 的影响。我们想对 Ganesh 的补丁进行反向运算（$B^{-1}$）与 Arjan 的补丁进行运算。由于这两个补丁冲突，我们必须诉诸强制运算，这将产生两个补丁 ${A_{1}}$ 和 ${B_{1}}^{-1}$，它们具有以下奇怪的特性

• $A_{1}$ 的作用是 $B^{-1}$；它从购物清单中删除了 Ganesh 的“意大利面”。
• 同样，${B_{1}}^{-1}$ 的作用是 $A$；它将 Arjan 的“啤酒”添加到购物清单中。

通过强制运算合并冲突

这非常方便，因为我要提醒你，我们真正想要的是取消补丁。如果我们使用标准的合并技术简单地删除 ${B_{1}}^{-1}$（这样我们就不会再添加啤酒了），我们就能成功地撤销 Ganesh 的意大利面补丁。合并完成！

解决 Arjan 和 Ganesh 的冲突

标记冲突

等等！我们不能就这样把事情放下。如果 darcs 通过撤销操作来处理冲突，可怜的开发者怎么知道是否有冲突？答案是我们不会止步于此。撤销冲突是一个非常重要的第一步，正如我们将在下面更详细地看到的那样。这样想吧。我们知道存在冲突，因为运算的定义方式，我们也知道哪些补丁参与了冲突。所以，每当这种情况发生时，我们先撤销所有操作，然后检查冲突补丁的内容，并利用它来创建一个新的冲突标记补丁。

FIXME: 在这里插入显示冲突标记补丁的图像

Darcs 2

:TODO: introduce this section

指数级合并问题

不幸的是，darcs 1 的合并算法具有以下属性：某些合并——人们在现实生活中经历过的合并——对于冲突的大小（以冲突补丁的数量来衡量）而言是指数级的。这导致一些用户遇到了这样的问题：用户会执行darcs pull令人费解的是，darcs 只是在那里挂起...

那么新的 darcs 2 如何解决这个问题？幕后发生了什么？

冲突者

冲突者的概念本质上是，我们会特殊处理包含其冲突补丁列表的补丁

使用广义代数数据类型来提高代码安全性

• 另请参阅Haskell/GADT 和 http://wiki.darcs.net/Ideas/GADTPlan