通过“递归”策略进行合并

我知道 git merge 递归实际上发生在有超过 1 个共同祖先的情况下，并且它将创建一个虚拟提交来合并这些共同祖先，然后再继续合并最近的提交（抱歉，我不确定是否应该有一个术语这）。

但我一直在尝试查找有关 git merge 递归策略实际如何详细工作的更多信息，但找不到太多信息。

谁能详细解释 git merge 递归的真正执行方式，并提供示例和可能的流程图来帮助更好地可视化？

你可以找到一个描述在这里 http://blog.plasticscm.com/2011/09/merge-recursive-strategy.html（也可以看看part 2 http://blog.plasticscm.com/2012/01/more-on-recursive-merge-strategy.html):

什么时候需要合并递归？

（Git 2.30，2020 年第一季度，将有new合并策略 https://stackoverflow.com/a/64950077/6309)

如果我们找到“两个共同祖先”怎么办？下面的分支资源管理器视图显示了另一种选择，其中有两个可能的“共同祖先”。

请注意：该示例有点牵强，因为最初没有充分的理由让开发人员从变更集 11 合并到 16，而不是从变更集 15（合并时主分支的最新版本）合并。
但我们假设这样做是有原因的，例如，变更集 11 是稳定的，而变更集 13 和 15 当时还不稳定。

关键是：在 15 和 16 之间，没有一个唯一的祖先，而是有两个处于相同“距离”的祖先：12 和 11。

虽然这种情况不会经常发生，但对于长期存在的分支或复杂的分支拓扑来说，确实很可能发生。 （上面描述的情况是导致“多祖先”问题的最短的一种情况，但在“交叉”合并之间的多个变更集和分支也可能发生这种情况）。

一种解决方案是“选择”祖先之一作为合并的有效祖先（这是 Mercurial 采取的选项），但它有很多缺点。

合并递归如何工作？

当找到多个有效祖先时，递归合并策略将创建一个新的唯一“虚拟祖先”，合并最初找到的祖先。

下图描述了该算法：

新的祖先 2 将用作“祖先”来合并“src”和“dst”。

正如我将在下面描述的，“合并递归策略”能够找到比“选择两者之一”更好的解决方案。

注意：合并递归策略最初是合并“fredrik”策略（参见提交 e4cf17c https://github.com/git/git/commit/e4cf17ce0db2dab7c9525a732f86c5e3df3b4ed0，2005 年 9 月，Git v0.99.7a)，之后弗雷德里克·奎维宁.
那是个蟒蛇脚本 https://github.com/git/git/blob/f88ed172e7a391bd907798ad2a3347a83cd24317/git-merge-fredrik.py，发起于提交 720d150 https://github.com/git/git/commit/720d150c48fc35fca13c6dfb3c76d60e4ee83b87，它说明了原始算法。

有关更多详细信息，请考虑“Petr Baudi 的版本控制系统的当前概念 2009-09-11 https://pdfs.semanticscholar.org/4490/4c70bc91e1bed4fe02b9e2282f031b7c90ea.pdf”，第 17 页。

|B| = 1 : b(B) = B0
|B| = 2 : b(B) = M(LCA(B0, B1), B0, B1)
M(B, x, y) = ∆−1
(b(B), x ∪ y)
m(x, y) = M(LCA(x, y), x, y)

（是的，我也不知道如何阅读）

如果发生冲突，该算法的主要思想是在使用结果作为进一步合并的基础时简单地将冲突标记保留在适当的位置。
这意味着早期的冲突以及新版本中的冲突更改都会得到正确传播。

这是指revctrl.org/CrissCrossMerge https://web.archive.org/web/20100905180220/http://revctrl.org/CrissCrossMerge，它描述了递归合并的上下文交叉合并.

交叉合并是一种祖先图，其中最小共同祖先不是唯一的。
最简单的标量示例如下：

  a
 / \
b1  c1
|\ /|
| X |
|/ \|
b2  c2

这里可以讲述的故事是，鲍勃和克莱尔独立进行了一些更改，然后各自将更改合并在一起。
他们发生了冲突，鲍勃（当然）认为他的改变更好，而克莱尔（通常）选择了她的版本。
现在，我们需要再次合并。这应该是一个冲突。

请注意，这在文本合并中同样可以发生——他们每个人都编辑了文件中的相同位置，并且在解决冲突时，他们每个人都选择使结果文本与其原始版本相同（即，他们不合并）以某种方式将两个编辑放在一起，他们只是选择一个获胜）。

So:

另一种可能的解决方案是首先合并 'b1' and 'c1' 到一个临时节点（基本上，想象一下 'X图中的“实际上是一个修订版，而不仅仅是边缘交叉），然后将其用作合并的基础”b2' and 'c2'.

有趣的部分是合并时'b1' and 'c1'导致冲突 - 诀窍是在这种情况下，'X' 包含在内部记录的冲突中（例如使用经典冲突标记）。

由于两者'b2' and 'c2' 必须解决相同的冲突，在这种情况下，他们以相同的方式解决了冲突，他们都从 'X' 以同样的方式得到一个干净的合并结果；如果他们以不同的方式解决问题，冲突就会来自‘X' 传播到最终的合并结果。

就是这样torek https://stackoverflow.com/users/1256452/torek描述于“git merge：我是如何在 BASE 文件中遇到冲突的？” https://stackoverflow.com/a/55957650/6309作为“不对称结果”：

“这些不对称结果是无害的，除了定时炸弹本身以及您后来运行递归合并的事实。
你会看到冲突。由你来解决它——again——但这一次，我们/他们的伎俩并不容易，如果这对人有效的话C and D."

恢复自revctrl.org/CrissCrossMerge:

如果合并会产生两个以上的碱基 ('b1', 'c1, 'd1')，它们连续合并 - 首先 'b1' with 'c1' 然后结果是 'd1'.

这就是“Git”的“递归合并”策略的作用。

在 Git 2.29（2020 年第 4 季度）中，为新的合并策略后端做准备，确实提供了对冲突和合并策略角色的良好描述。递归的合并策略：

（同样，Git 2.30，2020 年第一季度，将有一个new合并策略 https://stackoverflow.com/a/64950077/6309)

See commit 1f3c9ba https://github.com/git/git/commit/1f3c9ba707d8ac00bfa5f2afc76146a1149102a1, commit e8eb99d https://github.com/git/git/commit/e8eb99d4a6b2505c15a2be916d611f4e7f9cde2f, commit 2a7c16c https://github.com/git/git/commit/2a7c16c9802b25de3497f60b2f3776d1a02477bb, commit 1cb5887 https://github.com/git/git/commit/1cb588775f3b5fef9c10b1f9b580521007b390ea, commit 6c74948 https://github.com/git/git/commit/6c74948f2065bcab445a2db6d489147f84c73a53, commit a1d8b01 https://github.com/git/git/commit/a1d8b01775d3dec8b641974821fe512be7fef2bb, commit a0601b2 https://github.com/git/git/commit/a0601b2eb3213d125b1e9b40215e9ba4959af6e9, commit 3df4e3b https://github.com/git/git/commit/3df4e3bb092ec007d1967038baaf9fc39acaff8d, commit 3b6eb15 https://github.com/git/git/commit/3b6eb15d2b419c26bf1490b932c45913a1acb601, commit bc29dff https://github.com/git/git/commit/bc29dffe5987d0cff9fd012b5105daa4b1a535bf, commit 919df31 https://github.com/git/git/commit/919df3195553af05c884d51588d12134d8dfab2a (10 Aug 2020) by Elijah Newren (newren) https://github.com/newren.
^{(Merged by Junio C Hamano -- gitster -- https://github.com/gitster in commit 36d225c https://github.com/git/git/commit/36d225c7d4205bcc52301d78a132f4a851895812, 19 Aug 2020)}

t6425 https://github.com/git/git/commit/1f3c9ba707d8ac00bfa5f2afc76146a1149102a1：更灵活地重命名/删除冲突消息

^{Signed-off-by: Elijah Newren}

首先，有一个基本冲突类型称为修改/删除，这是内容冲突.
当一侧删除文件而另一侧修改该文件时，就会发生这种情况。

还有一个称为重命名/删除的路径冲突.
当一侧删除路径，而另一侧重命名它时，就会发生这种情况。
这不是内容冲突，而是路径冲突。
不过，它通常会与内容冲突一起发生，即修改/删除。
因此，这两者经常被结合起来。

另一种可能存在的冲突是目录/文件冲突。 例如，一侧在某个路径添加新文件，而历史记录的另一侧在同一路径添加目录。
不过，“添加”的路径可以通过重命名放置在那里。
因此，单个路径可能会受到修改/删除、重命名/删除和目录/文件冲突的影响。

在某种程度上，这是合并递归设计的自然副产品。
由于它正在进行四路合并，工作树的内容是它必须考虑的第四个因素，因此它的工作树处理遍布整个代码。
它还通过所有其他类型的冲突将目录/文件冲突处理扩展到各处。

这种结构的自然产物是冲突消息，它结合了当前代码路径正在考虑的所有不同类型。

然而，如果我们想让不同的冲突类型正交并避免重复自己并得到非常脆弱的代码，那么我们需要将来自这些不同冲突类型的消息分开。
此外，尝试确定所有可能的排列是一个royal mess.
处理重命名/删除/目录/文件冲突输出的代码已经有些难以解析，而且有些脆弱。
但如果我们真的想走这条路，那么我们必须对以下类型的组合进行特殊处理：

• 重命名/添加/删除：在未重命名给定文件的历史记录一侧，删除该文件并以重命名的方式放置一个不相关的文件
• 重命名/重命名(2to1)/模式冲突/删除/删除：两个不同的文件，一个可执行文件，另一个不可执行文件，被重命名到同一位置，每一方都删除另一方重命名的源文件
• 重命名/重命名(1to2)/添加/添加：文件在历史记录的每一侧以不同的方式重命名，每一侧都以另一侧的方式放置不相关的文件
• 重命名/重命名(1to2)/内容冲突/文件位置/(D/F)/(D/F)/：双方都以冲突的方式修改文件，双方都重命名该文件，但路径不同，一方重命名另一方将该文件重命名为的目录，导致它可能需要传递重命名，并且双方都将一个目录放入走别人的路。

让我们远离这种疯狂的道路，通过允许将冲突消息拆分为不同的类型，允许不同类型的冲突由单独的非重复代码片段来处理。 （如果多个冲突类型影响单个路径，则可以按顺序打印冲突消息。）通过简单的更改启动此路径：修改此测试以使其更加灵活并接受合并后端（递归或新的 ort）将产生的输出。

请注意，Git 2.22（2019 年第 2 季度）将改进递归合并策略，因为 git merge-recursive”后端最近（Git 2.18）学习了一种新的启发式方法 根据同一目录中其他文件的方式推断文件移动 感动了。

由于这种启发式方法本质上不如基于文件本身内容相似性（而不是基于其邻居正在执行的操作）的启发式方法稳健，因此有时会给出最终用户意想不到的结果。这已被缓和，以便将重命名的路径保留在索引中较高/冲突的阶段中，以便 用户可以检查并确认结果。

See commit 8c8e5bd https://github.com/git/git/commit/8c8e5bd6eb331d055aa7fa6345f6dcdadd658979, commit e62d112 https://github.com/git/git/commit/e62d11239cad847d1c55684f6c4ba939adc8e053, commit 6d169fd https://github.com/git/git/commit/6d169fd321c0da4b20c13d08bbe19d55cab12e11, commit e0612a1 https://github.com/git/git/commit/e0612a192a82280132ce2d3893c610b3db54c8ee, commit 8daec1d https://github.com/git/git/commit/8daec1df03de7db13d5d551a8b54f32fc6021132, commit e2d563d https://github.com/git/git/commit/e2d563dfa9951683a118e728dee99bd07a90e52d, commit c336ab8 https://github.com/git/git/commit/c336ab859347036eb5d538a9bd741fb9a95da36a, commit 3f9c92e https://github.com/git/git/commit/3f9c92ec99222515c6ebac1dc12d0bc3a6d4ae08, commit e9cd1b5 https://github.com/git/git/commit/e9cd1b5ca4438769c369126f1d9f963fc93bb471, commit 967d6be https://github.com/git/git/commit/967d6be725b10ac1ea39d50770b358166523fe22, commit 043622b https://github.com/git/git/commit/043622b2e9fd7b5e4b07404c4896080a602cc139, commit 93a02c5 https://github.com/git/git/commit/93a02c5553a293aa0ae34293304332dbc0fee431, commit e3de888 https://github.com/git/git/commit/e3de888ca052f7962c1a2e2f83b4640c40847ab2, commit 259ccb6 https://github.com/git/git/commit/259ccb6cc324912ea18b151d9c236ac17610c2f5, commit 5ec1e72 https://github.com/git/git/commit/5ec1e72823735b5682389589b6bee774ae70fa49 (05 Apr 2019) by Elijah Newren (newren) https://github.com/newren.
^{(Merged by Junio C Hamano -- gitster -- https://github.com/gitster in commit 96379f0 https://github.com/git/git/commit/96379f043f4d49de265c73430e74b8b6c7686e1c, 08 May 2019)}

merge-recursive：切换目录重命名检测默认值

当所有的x/a, x/b, and x/c已经搬到z/a, z/b, and z/c在一个 分支，有一个问题是x/d添加到不同的分支应保留在x/d或出现在z/d当两个分支合并时。
这里有不同的可能观点：

A) 文件放置在x/d处；它与其他文件无关x/所以来自的所有文件并不重要x/搬去z/在一根树枝上；x/d仍应保持在x/d.

B) x/d与其他文件相关x/, and x/被重命名为z/;所以x/d应移至z/d.

由于之前无法检测目录重命名 Git 2.18，用户体验(A)无论上下文如何。
Choice (B)在 Git 2.18 中实现，无法返回(A)，并一直沿用至今。
然而，一位用户报告说，合并结果与他们的预期不符，导致默认值的更改出现问题，特别是因为目录重命名检测移动文件时没有打印任何通知。

请注意，这里还有第三种可能性：

C) 根据上下文和内容有不同的答案，Git 无法确定，所以这是一个冲突。
使用索引中的较高阶段来记录冲突并通知用户潜在的问题，而不是默默地为他们选择解决方案。

添加一个选项，供用户指定是否使用的偏好 目录重命名检测，默认为(C).
即使目录重命名检测处于打开状态，也会添加有关移入新目录的文件的通知消息。

在 Git 2.31（2021 年第一季度）中，“ORT”合并策略（我认为在此介绍 https://stackoverflow.com/a/64950077/6309）影响传统的递归策略。

See commit c5a6f65 https://github.com/git/git/commit/c5a6f65527aa3b6f5d7cf25437a88d8727ab0646, commit e2e9dc0 https://github.com/git/git/commit/e2e9dc030cb37619256ec995b05412623043e74c, commit 04af187 https://github.com/git/git/commit/04af1879b9313a83aea46791bad8963e14e7651e, commit 43c1dcc https://github.com/git/git/commit/43c1dccb91c0d56b0b00f1b452a1a7204c4242da, commit 1c7873c https://github.com/git/git/commit/1c7873cdf4a7e84755c54e3f9ef10599041565d0, commit 101bc5b https://github.com/git/git/commit/101bc5bc2d73484d288a43fdcf1c00bc04b080e4, commit 6784574 https://github.com/git/git/commit/67845745c1ab7dcce72116fb58f99630d14e12cc (03 Dec 2020) by Elijah Newren (newren) https://github.com/newren.
^{(Merged by Junio C Hamano -- gitster -- https://github.com/gitster in commit 85cf82f https://github.com/git/git/commit/85cf82ff01ed975c31b75540afb1b251da5259fd, 06 Jan 2021)}

merge-ort https://github.com/git/git/commit/c5a6f65527aa3b6f5d7cf25437a88d8727ab0646：添加修改/删除处理和延迟输出处理

^{Signed-off-by: Elijah Newren}

这里的重点是添加一个path_msg()它将对有关合并的警告/冲突/通知消息进行排队以供以后处理，并将它们存储在pathname -> strbuf map.
这似乎是一个很大的变化，但它实际上只是：

• 声明必要的地图和一些评论
• 初始化和数据记录
• 一堆在打印/空闲时间迭代地图的代码
• 至少一个调用者，以避免出现未使用函数的错误（我们以实现修改/删除冲突处理的形式提供）。

在这个阶段，可能还不清楚为什么我选择延迟输出处理。
原因有多种：

1. 如果合并会覆盖脏更改，则应该中止 在工作树中。
   在发生重命名检测并且完成对重命名条目的完整处理之前，我们无法正确确定更改是否会被覆盖。
   警告/冲突/通知消息会在中间代码路径中出现，因此除非我们希望在合并中止时打印虚假的冲突/警告消息，否则我们需要保存这些消息并仅在相关时打印它们。

2. 单个路径可以有多个消息，并且我们希望给定路径的所有消息一起出现，而不是按冲突/警告类型对它们进行分组。
   这已经是一个问题了merge-recursive.c但由于冲突类型的分裂而变得更加重要，正如提交消息中所讨论的那样1f3c9ba707 https://github.com/git/git/commit/1f3c9ba707d8ac00bfa5f2afc76146a1149102a1 ("t6425：更灵活地重命名/删除冲突消息”，2020-08-10，Git 2.29）

3. 某些调用者可能希望避免在某些情况下显示输出，例如最终结果是干净的合并。
   Rebase 通常就是这样做的。

4. 某些调用者可能不希望输出发送到 stdout 甚至 stderr，但可能希望完全用它做其他事情。
   例如，一个--remerge-diff选项git show or git log -p动态重新合并以及针对重新合并版本的差异合并提交将受益于 stdout/stderr 不以标准形式写入。