了解 Darcs/补丁理论

只针对数学和计算机科学极客

(偶尔会容忍物理学家)

警告，休闲用户，您将要阅读的内容不适合胆小者！如果您是日常的 Darcs 用户，您可能不需要阅读此页面上的任何内容。但是，如果您有兴趣了解 Darcs 的实际工作原理，我们邀请您卷起袖子，并跟随我们一起进行这次对不断发展的补丁理论的导览。请注意，我自己才刚刚开始学习补丁理论和冲突，所以前面可能存在错误。

补丁理论是什么？

Darcs 补丁形式主义是帮助我们了解 Darcs 在存储库之间交换补丁时应如何表现的底层“数学”。它在 Darcs 引擎中作为用于表示补丁序列的数据结构和等效于形式主义中操作的 Haskell 函数来实现。本节针对两个受众：好奇的旁观者和想要参与 Darcs 核心开发的人员。我的目标是帮助您理解所有这些数学背后的直觉，这样您就可以尽快了解当前的冲突者研究并开始做出贡献。请注意，我自己才刚刚开始学习补丁理论和冲突者，所以前面可能存在错误。

为什么要用这么多数学？

集中式和分布式版本控制系统之间的一个区别是，“合并”是我们几乎一直都在做的事情，因此我们必须确保正确合并。将版本控制问题变成一个数学问题有两个影响：它让我们可以将所有无关的实现细节抽象出来，并且它迫使我们确保我们想出的任何技术都是基础可靠的，即它们在事情变得越来越复杂时不会崩溃。不幸的是，对于那些不经常使用数学的人来说，数学可能很难，因此我们在本手册中试图做的是通过使用具体的、图解的例子让您逐渐适应数学。

不过要提醒您的是，“正确合并”并不一定意味着在冲突方面有巧妙的行为。我们将首先关注成功的、无冲突的合并，然后继续讨论 Darcs 处理冲突的方法。

上下文、补丁和变更

让我们从购物开始。Arjan 正在为即将到来的 Darcs 黑客马拉松制作购物清单。就在我们说话的时候，他的存储库包含一个名为s_list的文件，其内容为

1 apples
2 bananas
3 cookies
4 rice

注意：您看到的数字只是行号，不是文件内容的一部分

正如我们将在本书的这个和其他的例子中看到的那样，我们通常需要给存储库的状态分配一个名称。我们称这个名称为上下文。例如，我们可以说 Arjan 的存储库是一个上下文 $o$ ，由存在一个名为 s_list 的文件且内容如上所述来定义。

Arjan 做了一个修改，该修改是在s_list中添加一行。他的新文件如下所示

1 apples
2 bananas
3 beer
4 cookies
5 rice

当 Arjan 记录这个变更（添加啤酒）时，我们生成了一个补丁，它不仅告诉我们 Arjan 添加了哪些内容（“啤酒”），还告诉我们他在哪里添加了它们，即在s_list的第 3 行。我们可以说，在他的存储库中，我们已经从上下文 $o$ 转移到上下文 $a$ ，通过一个补丁 A。我们可以使用紧凑的符号 ${}^{o}A^{a}$ 或使用下面的图形表示来表示

顺序补丁

从这个上下文开始，Arjan 可能会决定进行进一步的更改。他的新更改将是应用于先前补丁上下文的补丁。因此，如果 Arjan 在此基础上创建了一个新的补丁 $B$ ，它将把我们从上下文 $a$ 转移到一个新的上下文 $b$ 。下一个补丁将把我们从这个上下文转移到另一个新的上下文 $c$ ，等等。像这样彼此应用的补丁称为顺序补丁。我们像下表中那样以从左到右的顺序书写它们，要么显式地表示上下文，要么为了简洁而省略它们

带上下文	无上下文（简写）
${}^{o}A^{a}$	$A$
${}^{o}A^{a}B^{b}$	$AB$
${}^{o}A^{a}B^{b}C^{c}$	$ABC$

所有 darcs 仓库都是简单的补丁序列，如上所示；但是，当执行像撤销或与其他用户交换补丁这样的复杂操作时，我们必须拥有一种机制来重新排列补丁并将它们放到不同的顺序中。Darcs 补丁理论本质上是关于对补丁和补丁树可以被操作和转换的方式给出精确的定义，同时保持仓库的一致性。

逆

让我们回到本模块开头的那一个例子。Arjan 刚刚在我们的黑客马拉松购物清单中添加了啤酒，但是他突然间变得犹豫不决，想撤销他的修改。在这个例子中，这可能包括启动他的文本编辑器，从购物清单中删除那行内容。但是如果他的修改很复杂，难以跟踪呢？更好的做法是让 darcs 自己解决。Darcs 通过计算一个逆补丁来做到这一点，也就是说，一个补丁，它执行的修改与另一个补丁完全相反

定义（补丁的逆）:

补丁 $P$ 的逆是 $P^{-1}$ ，它是唯一的一个补丁，它与补丁 $P$ 的组合 $PP^{-1}$ 对上下文不做任何修改，并且逆的逆是原始补丁。

所以上面，我们说 Arjan 创建了一个补丁 $A$ ，它将啤酒添加到购物清单中，从上下文 $o$ 转变到上下文 $a$ ，或者更简洁地说， ${}^{o}A^{a}$ 。现在我们要创建逆补丁 $A^{-1}$ ，它删除购物清单中的啤酒，并将我们带回到上下文 $o$ 。在简洁的上下文-补丁表示法中，我们将它写成 ${}^{o}A^{a}{A^{-1}}^{o}$ 。在图形上，我们将这种情况表示如下

An inverse patch makes the opposite change of another patch — 逆补丁执行另一个补丁的相反修改

补丁逆可能看起来微不足道，但正如我们将在本模块后面看到的那样，它们是一个基本操作，对使一些更高级的功能（如合并）正常工作至关重要。我们对 darcs 强加的规则之一是每个补丁都必须有一个逆。这些规则就是我们所说的补丁属性。补丁属性告诉我们关于补丁的哪些事情必须为真，才能让 darcs 正常工作。人们通常喜欢梦想着设计出新的补丁类型来扩展 darcs 的功能，而定义这些补丁属性就是我们如何知道他们的新补丁类型在 darcs 下会表现得正常。这些属性中的第一个非常简单

交换

阿詹很幸运能尽快意识到他想撤销他的更改。但如果他意识到自己的错误慢一点会发生什么？如果他在意识到自己想撤销第一个更改之前进行了其他更改怎么办？是否可以在不撤销所有后续更改的情况下撤销他的第一个更改？有时可以，但要做到这一点，我们需要定义一个称为 **交换** 的操作。

考虑上面示例的一个变体。像往常一样，阿詹将啤酒添加到购物清单中。接下来，他决定在文件的第 5 行添加一些意大利面

问题是，如果阿詹现在决定他毕竟不想在购物清单中添加啤酒，darcs 应该如何表现？阿詹只想删除添加啤酒的补丁，而无需触碰添加意大利面的补丁。问题是 darcs 存储库是简单、愚蠢的补丁序列。我们不能只是删除啤酒补丁，因为那样就没有意大利面补丁的上下文了！阿詹的第一个补丁 $A$ 将我们带到上下文 $a$ ，如下所示： ${}^{o}A^{a}$ ，他的第二个补丁将我们带到上下文 $b$ ，值得注意的是从初始上下文 $a$ 开始： ${}^{a}B^{b}$ 。删除补丁 $A$ 将会从补丁 $B$ 下撤掉地毯。这里的诀窍是，以某种方式 **改变** 补丁 $A$ 和 $B$ 的 **顺序** 。这正是交换的作用。

为什么不保留我们旧的补丁呢？

要理解交换，你应该理解为什么我们不能保留我们最初的补丁，而是被迫依赖邪恶的继女。使用上面啤酒和意大利面的具体示例会有所帮助。虽然我们可以写出序列 $AB$ 来表示先添加啤酒，然后添加意大利面，简单地写下 $BA$ 来表示先添加意大利面，然后添加啤酒，这将是一件非常愚蠢的事情。

这么说吧：如果我们把 $B$ 应用在 $A$ 之前会发生什么？我们在文件的第 5 行添加了面条

1 apples
2 bananas
3 cookies
4 rice
5 pasta

你有没有觉得哪里不对劲？我们接着在第 3 行添加了啤酒。如果你注意最终结果的内容，你可能会注意到我们列表的顺序稍微错了。比较这两个列表看看原因

$BA$ （错误！）	$AB$ （正确）
1 apples 2 bananas 3 beer 4 cookies 5 rice 6 pasta	1 apples 2 bananas 3 beer 4 cookies 5 pasta 6 rice

这可能无关紧要，因为它只是一个购物清单，但想象一下，这是你的博士论文，或者你的计算机程序是为了终结世界饥饿。这个错误更加令人担忧，因为它很微妙，人眼很难发现。

问题在于上下文，具体来说， $A$ 和 $B$ 之间的上下文。为了让像“在 s_list 的第 5 行添加面条”这样的指令有意义，它们必须处于正确的上下文。幸运的是，交换很容易实现，它会产生两个新的补丁 $B_{1}$ 和 $A_{1}$ ，它们执行与 $A$ 和 $B$ 相同的更改，但它们之间的上下文不同。

练习
补丁 $A_{1}$ 与 $A$ 相同。它在购物清单的第 3 行添加了“啤酒”。但是补丁 $B_{1}$ 应该做什么？

还有一个重要的细节需要注意！我们之前说过，获得正确的上下文是交换背后的动机——我们不能简单地以不同的顺序应用补丁 $AB$ ，因为这样会使上下文完全错误。但上下文不会影响 A 和 B 是否可以交换（或如何交换）。这纯粹是局部的事情。相反，A 和 B 的交换也不会影响全局上下文：序列 $AB$ 和 $B_{1}A_{1}$ （后者是前者的交换）从相同的上下文开始，并以相同的上下文结束。

重新审视复杂的撤消

既然我们知道了交换操作的作用，让我们看看如何使用它来撤消一个被其他补丁覆盖的补丁。我们首先做的是交换 Arjan 的啤酒和面条补丁。这给了我们到达相同上下文的另一种路线。但请注意 $B$ 和 $B_{1}$ 之间的细微差别！

commutation gives us two ways to get to the same patch — 交换给了我们两种到达同一个补丁的方法

将补丁进行交换的目的是将补丁 $A$ 推送到列表末尾，这样我们就可以简单地应用其逆运算。只是这里，我们想要的不是 $A$ 的逆运算，而是其邪恶的继姐 $A_{1}$ 的逆运算。应用该逆运算会发生以下情况：它会将我们带回到上下文 $b1$ ，就好像我们只应用了意大利面补丁，但没有应用啤酒补丁一样。

现在撤销操作已经完成。总结一下，当我们想要撤销的补丁被其他补丁埋藏时，我们会使用交换操作将其挤到补丁序列的末尾，然后计算交换后的补丁的逆运算。对于那些更注重顺序的人来说，一般方案看起来是这样的

Using commutation to handle a complex undo — 使用交换操作处理复杂的撤销操作

练习

想象一下相反的情况：Arjan 首先在列表中添加了意大利面，然后又添加了啤酒。

如果没有交换操作，如果他尝试删除意大利面补丁而不是啤酒补丁，具体会发生什么情况？
使用交换操作来解决此撤销操作。注意行号。

交换操作和补丁

每次我们定义一种补丁类型时，我们都必须定义它如何与其他补丁交换。大多数情况下，这非常简单。例如，当交换两个块补丁时，我们只需要调整它们的行偏移量。例如，我们想要在文件中的第 3 行添加内容，但如果我们使用补丁 $Y$ 在该行之前插入一行，原本的第 3 行现在就变成了第 4 行！因此，补丁 $X_{1}$ 将 "x" 插入到第 4 行，就像 $X$ 将 "x" 插入到第 3 行一样。

有些补丁无法交换。例如，你不能将添加文件与向其中添加内容的补丁进行交换。但现在，我们将重点关注可以交换的补丁。

合并

注意：这里可能是休息一下的好地方。我们将进入一个新的主题以及新的（但相似）的示例。

我们已经介绍了两个基本的 Darcs 操作：补丁逆运算和补丁交换操作。事实证明，这两个操作几乎是我们执行 Darcs 合并所需要的一切。

Arjan 和 Ganesh 正在一起构建一个购物清单，用于即将到来的 Darcs 黑客马拉松。Arjan 初始化了仓库并添加了一个名为 s_list 的文件，内容如下

1 apples
2 bananas
3 cookies
4 rice

然后他记录了他的更改，Ganesh 执行了 darcs get 命令以获取他的仓库的相同副本。请注意，Arjan 和 Ganesh 从相同的上下文开始。

Arjan 做了一个修改，该修改是在s_list中添加一行。他的新文件如下所示

1 apples
2 bananas
3 beer
4 cookies
5 rice

Arjan 的补丁将他带到了一个新的上下文 $a$

现在，在 Ganesh 的仓库中，他也进行了一项修改；他认为 s_list 很难理解，因此将文件名重命名为 shopping。请记住，此时，Ganesh 还没有看到 Arjan 的修改。他仍然从原始上下文 $o$ 开始，并通过他的补丁 $B$ 移动到了一个新的上下文 $b$

并行补丁

此时，Ganesh 决定获得 Arjan 更改的副本会很有用。粗略地说，我们想要将 Arjan 的补丁 A 拉入 Ganesh 的仓库 B。但是，存在一个主要问题！即，Arjan 的补丁将我们从上下文 $o$ 带到了上下文 $a$ 。将其拉入 Ganesh 的仓库中将涉及尝试将其应用到上下文 $b$ ，而我们根本不知道如何做到这一点。换句话说：Arjan 的补丁告诉我们向文件 s_list 添加一行；但是，在 Ganesh 的仓库中，s_list 不再存在，因为它已经被移动到了 shopping。我们如何知道 Arjan 的更改（添加一行 "beer"）应该应用于新的文件 shopping 而不是 s_list 呢？

Ganesh attempts to pull from Arjan — Ganesh 尝试从 Arjan 拉取代码

Arjan 和 Ganesh 的补丁从相同的上下文 o 开始，并分叉到不同的上下文 a 和 b。我们说他们的补丁彼此**平行**，并将其写为 $A\vee B$ 。在尝试从 Arjan 的仓库中拉取补丁时，我们正在尝试合并这两个补丁。基本方法是将并行补丁转换为顺序补丁 $BA_{1}$ ，这样 $A_{1}$ 与 $A$ 基本上做着相同的更改，但在 b 的上下文中。我们希望产生这种情况 ${}^{o}{B^{b}}{A_{1}^{c}}$

执行合并

将 Arjan 和 Ganesh 的并行补丁转换为顺序补丁只需要我们在本模块前面描述的逆和交换操作。

所以我们从 Ganesh 的补丁开始。在上下文表示法中，我们位于 ${}^{o}{B}^{b}$
我们计算逆补丁 $B^{-1}$ 。序列 $BB^{-1}$ 包括将 s_list 移动到购物，然后又移回来。我们回到了最初的上下文： ${}^{o}{B}^{b}{B^{-1}}^{o}$
现在我们可以毫无顾虑地应用 Arjan 的补丁： ${}^{o}{B}^{b}{B^{-1}}^{o}A^{a}$ ，但结果看起来并不那么有趣，因为我们基本上得到了与 Arjan 现在相同的东西，而不是合并。
我们只需要交换最后两个补丁， ${B}^{-1}{A}$ ，得到一对新的补丁 ${A_{1}}{B_{1}}^{-1}$ 。尽管如此，最终结果看起来并不那么有趣，因为它导致了与上一步完全相同的 state： ${}^{o}{B}^{b}{A_{1}}^{c}{{B_{1}}^{-1}}^{a}$
然而，一个关键的区别是，倒数第二个补丁恰好产生了我们想要的那个状态！现在我们所要做的就是丢弃 ${B_{1}}^{-1}$ 补丁，它只是在撤销Ganesh宝贵的成果。也就是说，通过简单地确定如何生成一个与 $B$ 可交换的 $A_{1}$ ，我们就确定了将更新Ganesh仓库的 $A$ 版本。

Merging via inverse and commutation — 通过逆运算和交换进行合并

所有这些的最终结果是，我们得到了我们想要的补丁， $A_{1}$ ，以及一个成功的合并。

合并是对称的

具体来说，我们讨论了Ganesh将Arjan的补丁拉入他的仓库，那么反过来呢？Arjan将Ganesh的补丁拉入他的仓库将以完全相同的方式进行，只是他正在寻找一个Ganesh补丁 $B_{1}$ 的交换版本，该版本将应用于他的仓库。如果Ganesh可以拉入Arjan的补丁，那么Arjan也可以拉入Ganesh的补丁，结果将完全相同。

定义（两个补丁的合并）:

两个补丁 $A$ 和 $B$ 的合并结果是两个补丁中的一个： $A_{1}$ 和 $B_{1}$ ，它们满足关系 $A\vee B\Longrightarrow B{A_{1}}\leftrightarrow A{B_{1}}$

合并定义描述了将两个并行补丁组合成补丁序列时应该发生的事情。内置的对称性对于darcs来说是至关重要的，因为darcs仓库完全由它的补丁定义。换句话说，

待写

与逆运算的交换性

合并的定义告诉我们我们想要合并看起来像什么。我们怎么会知道如何实际执行合并呢？答案来自交换和逆运算的以下性质：如果你可以将补丁 $A^{-1}$ 的逆运算与另一个补丁 $B$ 进行交换，那么你也可以将补丁本身与 $B_{1}$ 进行交换。

请注意，此属性的左侧完全符合合并定义中要求的关系。要了解为什么这一切有效，

待写

定义和属性

逆定义	$AA^{-1}$ 没有效果
逆的逆	$(A^{-1})^{-1}=A$
逆复合属性	$(AB)^{-1}=B^{-1}A^{-1}$
交换定义	$AB\leftrightarrow {B_{1}}{A_{1}}$
合并定义	$A\vee B\Longrightarrow B{A_{1}}\leftrightarrow A{B_{1}}$
逆交换属性	$B{A_{1}}\leftrightarrow A{B_{1}}$ 当且仅当 ${B_{1}}{A_{1}}^{-1}\leftrightarrow {A^{-1}}B$

下一页：更多补丁理论 | 上一页：撤销错误
主页：了解 Darcs