最近的一篇论文对版本控制提出了一种新的数学观点。我最初是从pijul了解到这一点的，pijul是一种新的版本控制系统(VCS)，它的灵感来自于那篇论文。但是如果你浏览pijul主页，你不会发现它与现有的VCS有什么不同的细节。所以我做了一点挖掘，这一系列的博客帖子就是结果。
在第一部分(即这一部分)，我将回顾一下论文中发展起来的一些理论。具体地说，我将描述一种考虑补丁和合并的方法，它保证永远不会有合并冲突。在第二部分，我将展示pijul如何将该理论付诸实践，在第三部分，我将深入研究pijul的实现。
在进入补丁理论之前，有一个简短的警告：任何真正的VCS都需要处理很多繁琐的细节(目录、二进制文件、文件重命名等)。为了直截了当地谈到有趣的新想法，我将跳过所有这些。对于这些帖子而言，VCS只需要跟踪单个文件，您应该将其视为行列表。
补丁是两个文件之间的区别。在本系列的后面部分，我们将探讨一些疯狂的新想法，所以让我们从一些熟悉的、令人欣慰的东西开始吧。我们在这里讨论的补丁类型可以追溯到Unix的早期：
为了真正拥有有用的VCS，您还需要能够删除行。但是删除行会增加一些复杂性，所以我们稍后再处理它们。
举个例子，让我们从一个简单的文件开始：我今天早上的待办事项列表。
回过头来看清单，我意识到我忘了一些重要的东西。这是新的一条：
为了从原来的待办事项清单转到新的待办事项清单，我增加了袜子这一行。在原始Unix“diff”实用程序的格式中，补丁程序将如下所示：
“1a2”行是一个代码，它告诉我们要在输入文件的第1行之后添加一些东西，下一位显然告诉我们要插入什么。
由于本博客不是命令行工具，我们将用漂亮的图表而不是平面文件来表示补丁。下面是我们将如何绘制上面的面片：
希望它是不言而喻的，但以防万一：一个箭头从左边到右边，表示右边的线与左边的线相同。右边没有箭头的线是添加的线，因为补丁不允许重新排列线，所以保证线不会交叉。
在我们的符号中确实有一些隐含的东西需要大声说出来：对我们来说，补丁绑定到特定的输入文件。这是我们与经典Unix方式不同的第一点：我们使用“diff”生成的经典Unix补丁原则上可以应用于任何输入文件，并且它仍然会在第一行之后插入“*穿上袜子”。在很多情况下，这并不是你想要的，但有时是你想要的。
补丁最棒的地方在于，它们可以让多个人编辑同一个文件，然后合并他们所做的更改。假设我的妻子也决定将一些事情放在我的待办事项列表中：她提取原始文件并添加一行：
现在我的待办事项清单有两个新版本：我穿袜子的和我妻子扔垃圾的。让我们把它们都画在一起：
这就带来了合并：因为我更喜欢将我的待办事项列表作为一个单一文件，所以我想合并我妻子的更改和我自己的更改。在这个例子中，结果应该是什么是非常明显的，但是让我们来看一下合并的一般问题。我们将缓慢而谨慎地完成此操作，我们的端点可能与您习惯的不同。
首先，我需要为一个显而易见的概念介绍一些符号：两个补丁的组合是通过应用一个补丁，然后应用另一个补丁而得到的补丁。因为我们的“补丁”还包括原始文件，所以您不能只组合两个旧补丁。如果p是从文件O到文件A的补丁，r是从A到B的补丁，那么您可以合成这两个补丁(但只能按一个顺序！)。为了获得从O到B的补丁，我将这篇作文写成pr：首先应用p，然后应用r。
使用我们的图表可视化面片合成相当容易：要计算两条路径的合成，只需“跟着箭头走”
我将从补丁组成的角度仔细定义什么是合并。我将以一种非常数学教授的方式来定义：我会给出一个精确的定义，然后是一些例子，只有在后面我才会解释为什么这个定义是有意义的。所以定义是这样的：如果p和q是两个不同的补丁，将文件O分别定位到文件A和B，则p和q的合并是一对补丁r和s，使得。
R和s分别将A和B带到公共输出文件M，并且。
我们可以用一个简单的图表来说明这个定义，其中大写字母表示文件，小写字母是它们之间的补丁：
数学家(或任何想听起来很花哨的人)不会说pr=qs，而是会说上图是通勤的。
这不是合并，因为它不符合条件pr=qs：沿着顶部路径合成面片给出。
具体地说，两个补丁在最终列表中的哪一双鞋来自原始文件的问题上存在分歧。这就是条件pr=qs背后的真正含义：这意味着对于哪条线来自哪里永远不会有任何模棱两可的地方。如果您习惯于对您最喜欢的VCS使用责备或注释命令，您可能可以想象为什么这种模棱两可是不好的。
当然，合并补丁是一个古老的想法，所以我只想简单地解释一下上面的表示与“传统”合并有何不同：传统上，合并是由算法定义的(有很多算法)。这些算法将尝试自动找到一个好的合并；如果它们找不到，您将被要求提供一个。
我们将采取一种不同的方法：不是从算法开始，而是从我们希望良好的合并满足的属性列表开始。最后，我们会发现有一个唯一的合并可以满足所有这些属性(对我们来说幸运的是，还会有一个有效的算法来找到它)。
合并的主要问题是它们不是唯一的。这本身并不是一个大问题：许多伟大的事情并不是独一无二的。问题是，我们通常希望自动合并，而自动系统需要一个明确的答案。最后，我们将通过定义一个特殊的合并类(称为完美合并)来处理这个问题，它将是唯一的。在此之前，我们将通过一些例子来探讨这个问题。
让我们从一个愚蠢的示例开始，在该示例中，我们的合并工具决定添加一些额外的废话：
当然，任何理智的合并工具都不会这样做，但根据我们在上一节中的规则，它仍然是有效的合并。显然，我们必须收紧规则才能排除这种情况。
根据上面的规则，这两个合并都是有效的，但您需要实际了解这些行的含义，才能确定第一个合并更好(特别是如果外面下雨的话)。任何合理的自动合并工具都会拒绝选择，而是要求用户手动进行合并。
上面的例子非常简单，但是一般情况下，您如何确定合并是否明确并且可以自动执行呢？在现有的工具中，细节取决于合并算法。既然我们从一种非算法的方法开始，让我们看看这会导致什么结果：我们将不再明确指定我们可以做哪些合并，而是描述理想的合并应该具有的属性。
我即将给出的定义背后的主要思想是，它永远不会引起任何遗憾。也就是说，无论将来发生什么，我们总是可以通过合并来表示历史，就像我们可以使用原始分支一样。显然，这是一个很好的属性；就我个人而言，我认为为什么它是理想合并的定义属性的好选择并不明显，但我们稍后会谈到这一点。
现在假设补丁p和q的原始创建者继续在他们自己的个人分支上工作，这些分支在将来的某个时候合并到文件F：
我们说合并(r，s)是完美合并，如果对于合并(u，v)的每个可能的回声，存在唯一的补丁w，使得u=rvand v=sw。(在数学术语中，图是交换的。)我们将称w为延续，因为它告诉我们如何从合并的文件继续工作。重复一遍，如果对于每一个可能的未来，都有唯一的延续，那么合并就是完美的。
让我们举几个例子来探索我们定义的各个方面。首先，一个完美合并的例子：
要真正证明这是一个完美的合并需要付出一些努力；我将把它留作练习。看到一些不完美的例子会更有趣。
让我们从一个愚蠢的合并示例开始，它引入了一个不必要的行：
事实证明(令人惊讶，令人惊讶)这并不是完美的合并。为了理解我们对合并完美的定义如何排除这样的合并，下面是一个没有延续的可能未来的示例：
因为我们的补丁不能删除线条，所以没有办法从合并到未来。
下面是另一个示例，合并文件中两行的顺序有歧义的情况：
这不是一个完美的合并，因为有一个没有有效延续的未来：假设我和我的妻子手动创建了所需的合并。
现在，在合并和未来之间放置什么补丁(称为w)才能使一切通勤呢？唯一的可能性是。
这不是合法的补丁，因为补丁不允许交换线路。
如果您一直在偶然阅读有关pijul的内容，您可能会遇到“推出”这个词。事实证明，我们用来定义完美合并的模式在数学中非常常见。具体地说，在范畴论中，假设您有以下图表(其中大写字母是对象，小写字母是态射)：
如果对于每个u和v，存在唯一的w使得图可交换，则(r，s)称为(p，q)的推出。换句话说，我们上面所说的“完美合并”也可以称为“将文件作为对象，将补丁作为态射的类别中的推出”。在本文的大部分时间里，我们将忽略一般的数学术语，而偏爱更直观、更具体于文件和补丁的语言。
完美合并的主要问题是它们并不总是存在的。事实上，我们已经看到一个例子：
上面的一对面片没有完美的融合。我们还没有实际证明这一点，但直觉上这是相当清楚的，我们前面也讨论了为什么一个潜在的合并不是完美的。好的，所以不是每一对补丁都能完美地出现。您可能已经知道这一点，因为Mergecconflicts就是这样产生的：VCS不知道如何自行合并补丁，所以您需要手动解决一些冲突。
现在我们来看论文中最酷的部分：处理合并冲突的一个完全不同的想法。关键部分是，我们不是凑合不完美的合并，而是扩大合并可以产生的对象集。也就是说，不是每一对补丁都可以完美地合并到一个文件中，但也许它们可以合并到其他文件中。这个想法在数学中非常常见，甚至有一些一般性的抽象废话表明它总是可以做到的：有一种抽象的方法来泛化文件，以便每对泛化文件的补丁都可以完美地合并。这里的神奇之处在于，在这个特殊的案例中，抽象的胡言乱语凝聚成了完全明确和可管理的东西。
文件是行的有序列表。拼图1(“图形”和“文件”的混合体)是线条的有向图形。(是的，我知道这是一个糟糕的名字，但它比“文件和补丁类别的自由有限补全中的对象”要好得多，这是论文的称呼。)换句话说，文件坚持让它的行按严格的线性顺序排列，而拼图允许它们是任何有向图。很容易看出放松行的严格顺序是如何解决我们前面的合并问题的。例如，下面是之前给我们带来问题的那种完美的合并：
回想起来，这是一个非常明显的解决方案：如果我们不知道应该放什么订单和垃圾，我们应该只产生一个不指定订单的输出。有一点不太明显(但在论文中得到了证明)的是，当我们在Graggles世界而不是文件世界工作时，每一对补丁都有一个独特的完美合并。更酷的是，完美的合并很容易计算。稍后我将对其进行描述，但首先我必须说明补丁是如何推广到Graggles的。
两个图(例如，A和B)之间的面片是从A的直线到B的直线的函数(称为p)，它尊重偏序，因为如果A中存在从x到y的路径，则B中也存在从p(X)到p(Y)的路径。在这个意义上，如果A中存在从x到y的路径，那么在B中也存在从p(X)到p(Y)的路径。(此条件是两个文件之间的补丁不允许更改顺序这一事实的延伸。)下面是一个示例：
现在来看合并算法：假设我们有一个从曲线图A到曲线图B的面片p和从A到C的另一个曲面片q。为了计算p和q的完美合并，
每当B中的一行和C中的一行共享A中的“父”时，将它们折叠成一行。
就这样：两个步骤。以下是上一个示例的算法：我们希望合并这两个面片：
对于第二步，我们看到这两个“待办事项”行都来自原始文件中的同一行，因此我们将这两行合并为一个。对“work”行执行相同的操作后，我们将获得所需的输出：
通过将文件推广到Graggles，我们得到了一个非常好的好处：每对补丁都有一个(唯一的)完美合并，我们可以很容易地计算它。但是有一个明显的缺陷：我们使用的所有工具(编辑器、编译器等)。在文件上工作，而不是在Graggles上。这就是本文停止提供指导的地方，但有一个简单的解决方案：每当合并产生不是文件的东西时，只需制作一个新的补丁将其转换为文件即可。我们将其称为展平，下面是一个示例：
如果你的眼睛现在还没有变得呆滞(抱歉，这是一篇很长的帖子)，你可能觉得有点被骗了：我向你承诺了一个新的框架，它可以避免手动合并解决方案的陷阱，但是平坦化看起来非常像手动合并解决方案。我将在下一篇文章中更详细地回答这一批评，在那里我将演示pijul工具以及它与git的不同之处。但是这里有一个小问题：扁平化和手动合并解决方案之间的区别在于，扁平化对VCS是完全透明的：它和其他任何补丁一样都是普通的补丁。这意味着我们可以做一些有趣的事情，比如重新排序或还原补丁，即使在存在冲突的合并的情况下也是如此。关于这一点的更多信息将在下一篇文章中介绍。
现在终于到了解决我在这篇文章一开始就搁置的问题的时候了：我描述的系统基于不能删除行的补丁，我们显然需要在任何实际的系统中允许删除。不幸的是，这篇论文在这里帮不上忙：它声称您可以将删除合并到我描述的系统中，而不需要进行任何真正的更改，但是这篇论文中存在一个错误。具体地说，如果您调整定义以允许删除，则Graggles类别将不再在推送下关闭。以下是本文中的合并算法不完美的一个示例：
(由于这篇帖子已经拖得够久了，我把它留作练习，看看问题出在哪里)。
幸运的是，在我们最初的补丁系统中有一个模仿行删除的技巧。我是从Pijul那里得到这个想法的，但我会用稍微不同的方式来表达它。其想法是允许“重影”行，而不是实际删除它们。也就是说，我们将拼图中的每一条线都标记为“活动的”或“幽灵的”，然后我们在补丁中添加一条额外的规则：一条活动的线可以变成鬼线，但不能反之亦然。我们将画灰色的幻影线，并且指向幻影线的箭头将被虚线。这是一个删除“鞋”行的补丁。
剩下的最后一步是扩展完美的合并算法，用虚线覆盖新的Graggles。事实证明，这很简单；以下是新的算法：
对于具有共同父级的每一对线，将它们“折叠”成一条线，如果其中一条线是重影，则将折叠的线设置为重影。
斜体字是唯一的新部分，它几乎不会增加任何额外的复杂性。
我(非常详细地)向您展示了一种思考VCS中补丁的数学方法，尽管我还没有表现出很大的动机。不过，至少下次有人开始喋喋不休地谈论“补丁理论”时，你会对他们在说什么有所了解。
在下一篇文章中，我将讨论pijul，这是一个松散地基于我在这篇文章中描述的算法的VCS。在那里，你将看到几个(玩具)例子，其中pijul坚实的数学基础帮助它避免了一些更成熟的VCS绊倒的角落案例。
我要感谢Pierre-Étienne Meunier对这篇帖子草稿的评论和更正。当然，剩下的任何错误都是我自己的责任。
他说：这篇文章的早期版本称它们为“digles”(用于有向图文件)，但几年后我觉得“graggles”听起来好一点。另外，如果你把它念错了一点，它就符合皮朱尔的整个鸟类主题。