git - 由 'recursive' 策略进行的 merge

Question

我知道当有多个共同祖先时 git merge recursive 实际上会发生，它会创建一个虚拟提交来 merge 这些共同祖先，然后再继续 merge 最近的提交(对不起，我不确定是否应该有一个术语这)。

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

任何人都可以详细解释 git merge recursive 的实际执行情况，并通过示例和可能的流程图来帮助更好地可视化吗？

Answer 1

您可以找到 description here (另见 part 2):

When is merge recursive needed?

(Git 2.30，2020 年第一季度，将有 new merge-ort strategy )

What if we find "two common ancestors"? The branch explorer view below shows an alternative in which there are two possible "common ancestors".

Please note: the example is a little bit forced since there's not a good reason – initially – for the developer merging from changeset 11 into 16 instead of merging from changeset 15 (the latest from the branch main at the point of the merge).
But let's assume it has to be done for a reason, let's say, changeset 11 was stable and 13 and 15 weren't at the time, for instance.

The point is: between 15 and 16 there's not a single unique ancestor, but rather, two ancestors at the same "distance": 12 and 11.

虽然这不会经常发生，但它确实很可能发生在长期存在的分支或复杂的分支拓扑中。 (上面描述的案例是解决“多祖先”问题的最短案例，但它也可能发生在“交叉” merge 之间的多个变更集和分支中)。
一种解决方案是“选择”其中一个祖先作为 merge 的有效祖先(这是 Mercurial 采用的选项)，但它有许多缺点。

How merge recursive works?

When more than one valid ancestor is found, the recursive-merge strategy will create a new unique "virtual ancestor" merging the ones initially found.

The following image depicts the algorithm:

A new ancestor 2 will be used as "ancestor" to merge the "src" and "dst".

The "merge recursive strategy" is able to find a better solution than just "selecting one of the two" as I'll describe below.

注意: merge 递归策略最初是 merge “fredrik”策略(参见 commit e4cf17c，2005 年 9 月，Git v0.99.7a)，在 之后。弗雷德里克·库维宁 .
这是一个 python script , 起始于 commit 720d150 ，它说明了原始算法。
有关详细信息，请参阅第 17 页的“ Current Concepts in Version Control Systems from Petr Baudiˇs 2009-09-11”。

|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)

(是的，我也不知道怎么读)

In case of conflict, the main idea of the algorithm is to simply leave the conflict markers in place when using the result as a base for further merges.
This means that earlier conflicts are properly propagated as well as conflicting changes in newer revisions.

这是指 revctrl.org/CrissCrossMerge ，它描述了 中递归 merge 的上下文交叉 merge .

A criss-cross merge is an ancestry graph in which minimal common ancestors are not unique.
The simplest example with scalars is something like:

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

The story one can tell here is that Bob and Claire made some change independently, then each merged the changes together.
They conflicted, and Bob (of course) decided his change was better, while Claire (typically) picked her version.
Now, we need to merge again. This should be a conflict.

Note that this can happen equally well with a textual merger -- they have each edited the same place in the file, and when resolving the conflict they each choose to make the resulting text identical to their original version (i.e., they don't munge the two edits together somehow, they just pick one to win).

所以:

Another possible solution is to first merge 'b1' and 'c1' to a temporary node (basically, imagine that the 'X' in the diagram is actually a revision, not just edges crossing) and then use that as a base for merging 'b2' and 'c2'.

The interesting part is when merging 'b1' and 'c1' results in conflicts - the trick is that in that case, 'X' is included with the conflicts recorded inside (e.g. using the classical conflict markers).

Since both 'b2' and 'c2' had to resolve the same conflict, in the case they resolved it the same way they both remove the conflicts from 'X' in the same way and a clean merge results; if they resolved it in different ways, the conflicts from 'X' get propagated to the final merge result.

这就是 torek "git merge: how did I get a conflict in BASE file?" 中描述作为“不对称结果”:

"These asymmetric results were harmless, except for the time bomb itself plus the fact that you later ran a recursive merge.
You get to see the conflict. It's up to you to resolve it — again — but this time there's no easy ours/theirs trick, if that worked for persons C and D."

从 revctrl.org/CrissCrossMerge 恢复:

If a merge would result in more than two bases ('b1', 'c1, 'd1'), they are merged consecutively - first 'b1' with 'c1' and then the result with 'd1'.

This is what "Git"'s "recursive merge" strategy does.

使用 Git 2.29(2020 年第四季度)，为准备新的 merge 策略后端，确实提供了对冲突和递归 merge 策略角色的良好描述:
(同样，Git 2.30，2020 年第一季度，将有一个 new merge-ort strategy )
见 commit 1f3c9ba , commit e8eb99d , commit 2a7c16c , commit 1cb5887 , commit 6c74948 , commit a1d8b01 , commit a0601b2 , commit 3df4e3b , commit 3b6eb15 , commit bc29dff , commit 919df31 (2020 年 8 月 10 日)作者: Elijah Newren ( newren ) .
(由 Junio C Hamano -- gitster -- 在 commit 36d225c 中 merge ，2020 年 8 月 19 日)

t6425: be more flexible with rename/delete conflict messages

^{Signed-off-by: Elijah Newren}

First, there's a basic conflict type known as modify/delete, which is a content conflict.
It occurs when one side deletes a file, but the other modifies it.

There is also a path conflict known as a rename/delete.
This occurs when one side deletes a path, and the other renames it.
This is not a content conflict, it is a path conflict.
It will often occur in combination with a content conflict, though, namely a modify/delete.
As such, these two were often combined.

Another type of conflict that can exist is a directory/file conflict.For example, one side adds a new file at some path, and the other side of history adds a directory at the same path.
The path that was "added" could have been put there by a rename, though.
Thus, we have the possibility of a single path being affected by a modify/delete, a rename/delete, and a directory/file conflict.

In part, this was a natural by-product of merge-recursive's design.
Since it was doing a four way merge with the contents of the working tree being the fourth factor it had to consider, it had working tree handling spread all over the code.
It also had directory/file conflict handling spread everywhere through all the other types of conflicts.

A natural outgrowth of this kind of structure is conflict messages that combine all the different types that the current codepath is considering.

However, if we want to make the different conflict types orthogonal and avoid repeating ourselves and getting very brittle code, then we need to split the messages from these different conflict types apart.
Besides, trying to determine all possible permutations is a royal mess.
The code to handle the rename/delete/directory/file conflict output is already somewhat hard to parse, and is somewhat brittle.
But if we really wanted to go that route, then we'd have to have special handling for the following types of combinations:

• rename/add/delete: on side of history that didn't rename the given file, remove the file instead and place an unrelated file in the way of the rename
• rename/rename(2to1)/mode conflict/delete/delete: two different files, one executable and the other not, are renamed to the same location, each side deletes the source file that the other side renames
• rename/rename(1to2)/add/add: file renamed differently on each side of history, with each side placing an unrelated file in the way of the other
• rename/rename(1to2)/content conflict/file location/(D/F)/(D/F)/: both sides modify a file in conflicting way, both rename that file but to different paths, one side renames the directory which the other side had renamed that file into causing it to possibly need a transitive rename, and each side puts a directory in the way of the other's path.

Let's back away from this path of insanity, and allow the different types of conflicts to be handled by separate pieces of non-repeated code by allowing the conflict messages to be split into their separate types. (If multiple conflict types affect a single path, the conflict messages can be printed sequentially.) Start this path with a simple change: modify this test to be more flexible and accept the output either merge backend (recursive or the new ort) will produce.

请注意，Git 2.22(2019 年第二季度)将改进递归 merge 策略，因为 git merge-recursive"后端最近(Git 2.18)学习了一种新的启发式方法
根据同一目录中其他文件的方式推断文件移动
感动。
由于这本质上不如基于文件本身的内容相似性(而不是基于其邻居正在做什么)的启发式方法，它有时会给出最终用户意想不到的结果。这已被调低以将重命名的路径留在索引中较高/冲突的阶段，因此
用户可以检查并确认结果。
见 commit 8c8e5bd , commit e62d112 , commit 6d169fd , commit e0612a1 , commit 8daec1d , commit e2d563d , commit c336ab8 , commit 3f9c92e , commit e9cd1b5 , commit 967d6be , commit 043622b , commit 93a02c5 , commit e3de888 , commit 259ccb6 , commit 5ec1e72 (2019 年 4 月 5 日)作者: Elijah Newren ( newren ) .
(由 Junio C Hamano -- gitster -- 在 commit 96379f0 中 merge ，2019 年 5 月 8 日)

merge-recursive: switch directory rename detection default

When all of x/a, x/b, and x/c have moved to z/a, z/b, and z/c on onebranch, there is a question about whether x/d added on a different branch should remain at x/d or appear at z/d when the two branches are merged.
There are different possible viewpoints here:

A) The file was placed at x/d; it's unrelated to the other files in x/ so it doesn't matter that all the files from x/ moved to z/ on one branch; x/d should still remain at x/d.

B) x/d is related to the other files in x/, and x/ was renamed to z/; therefore x/d should be moved to z/d.

由于之前无法检测目录重命名
Git 2.18，用户体验 (A)不管上下文。
选择 (B)在 Git 2.18 中实现，没有返回 (A) 的选项，并从那时起一直在使用。
但是，一位用户报告说 merge 结果不符合他们的预期，这使得更改默认值存在问题，特别是因为目录重命名检测移动文件时没有打印通知。
请注意，这里还有第三种可能性:

C) There are different answers depending on the context and content that cannot be determined by Git, so this is a conflict.
Use a higher stage in the index to record the conflict and notify the user of the potential issue instead of silently selecting a resolution for them.

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

在 Git 2.31(2021 年第一季度)中，“ORT” merge 策略(即我 presented here)会影响旧的递归策略。
见 commit c5a6f65 , commit e2e9dc0 , commit 04af187 , commit 43c1dcc , commit 1c7873c , commit 101bc5b , commit 6784574 (2020 年 12 月 3 日)作者 Elijah Newren ( newren ) .
(由 Junio C Hamano -- gitster -- 在 commit 85cf82f 中 merge ，2021 年 1 月 6 日)

merge-ort: add modify/delete handling and delayed output processing

^{Signed-off-by: Elijah Newren}

The focus here is on adding a path_msg() which will queue up warning/conflict/notice messages about the merge for later processing, storing these in a pathname -> strbuf map.
It might seem like a big change, but it really just is:

• declaration of necessary map with some comments
• initialization and recording of data
• a bunch of code to iterate over the map at print/free time
• at least one caller in order to avoid an error about having an unused function (which we provide in the form of implementing modify/delete conflict handling).

At this stage, it is probably not clear why I am opting for delayed output processing.
There are multiple reasons:

1. Merges are supposed to abort if they would overwrite dirty changesin the working tree.
   We cannot correctly determine whether changes would be overwritten until both rename detection has occurred and full processing of entries with the renames has finalized.
   Warning/conflict/notice messages come up at intermediate codepaths along the way, so unless we want spurious conflict/warning messages being printed when the merge will be aborted anyway, we need tosave these messages and only print them when relevant.

2. There can be multiple messages for a single path, and we want all messages for a give path to appear together instead of having them grouped by conflict/warning type.
   This was a problem already with merge-recursive.c but became even more important due to the splitting apart of conflict types as discussed in the commit message for 1f3c9ba707 ("t6425: be more flexible with rename/delete conflict messages", 2020-08-10, Git 2.29)

3. Some callers might want to avoid showing the output in certain cases, such as if the end result is a clean merge.
   Rebases have typically done this.

4. Some callers might not want the output to go to stdout or even stderr, but might want to do something else with it entirely.
   For example, a --remerge-diff option to git show or git log -p that remerges on the fly and diffs merge commits against the remerged version would benefit from stdout/stderr not being written to in the standard form.