In this article, I explain three-way merge, scalar merge, and Git's "recursive merge" algorithm. I analyze how recursive merge fares in various simple criss-cross merge scenarios, and find several cases where it produces questionable results or unnecessary conflicts.
Background
This article is going to be for the real merge nerds. To understand it, you will have to understand what a merge base is and why it is significant, and possibly also something about git-imerge and incremental merge diagrams.
A big part of using version control in general, and Git in particular, is merging branches together. Consider the following Git history, where letters and numbers denote commits and time progresses from left to right (→):
---0---1---2---3 ← main
\
A---B---C ← branch
If the changes that have been made on branch (A, B, and C) are OK, then the next task is to merge branch into main. The problem is that other work (1, 2, and 3) has been added to main since the work on branch was started. So the changes on main and the changes on branch have to be merged together, producing a merge commit M:
---0---1---2---3
\ \
\ M
\ /
A---B---C
Usually, this is done using the three-way merge algorithm. Three-way merge considers only three states of the project: the tip of each branch (i.e., 3 and C), and the "merge base". The merge base is, roughly speaking, the most recent that was on both of the branches that are being merged. In this case, it is commit 0.
So let's simplify the diagram by omitting intermediate commits:
---0 ⋯ 3
⋱ \
C - M
and then deform it to a rectangular grid, which will make it easier to recognize patterns:
0 ⋯ 3 ⋮ | C---M
Now, time progresses downwards and to the right (↘)
Scalar merge
Let's simplify the situation still further by discussing not a merge of source trees, but rather a "scalar merge". A scalar merge is a merge of "scalars". Scalars have no internal structure. They are either identical or different, and if they're different then there is no way to subdivide them. For example, if every file had only a single line, then the files would act like scalars.
Note that in real-life merges, files are (approximately) broken into hunks with differences, and the hunks are treated like scalars. So if we can get a better understanding of scalar merges, then we can apply what we learn to actual merges.
Three-way merge
How does three-way merge work? The rules for three-way merges are as follows. I will use lower-case letters to indicate the contents of files.
No change on either branch:
a---a a---a | | → | | a---? a---a
That is, if the contents didn't change on either branch, then the result of the merge is the same as the original contents.
Change on one branch (from contents a to contents b) but not on the other:
a---b a---b | | → | | a---? a---b a---a a---a | | → | | b---? b---b
In this scenario, one of the branches changed the contents from a to b, but the other branch didn't change the contents. In this case, the result of the merge is b.
Note that these pairs of diagrams are mirror images of each other, reflected along the diagonal. A general property of three-way merge is that it doesn't care which branch is which. From now on I won't bother showing diagrams that are mirror-images of each other.
This rule is the bread and butter of three-way merge. Look for it in the examples below.
The same change on both branches:
a---b a---b | | → | | b---? b---b
In this scenario, both branches changed the contents from a to b. In this case, three-way merge selects b as the result of the merge.
This is a slightly more questionable rule than the previous one. Why was the same change made on two different branches? Often this scenario arises due to cherry-picking. Even though this rule is less robust than the previous rule, in real life there would be a lot more merge conflicts without it.
There is only one scalar merge pattern that three-way merge can't resolve:
Different changes on the two branches:
a---b a---b | | → | | c---? c---X ← conflict
In this scenario, one branch changed the contents from a to b, but the other changed the contents from a to c. There's no way for three-way merge to resolve this merge, so it results in a conflict (which I will denote with X). In real life, conflicts have to be resolved by a human.
Criss-cross merges
But it is not always the case that a merge has a single merge base. Consider, for example, a criss-cross merge:
---0-------1---2---3---4 ← main
\ \ / \
\ \ / \
\ \ / \
\ ⋅ ? ← desired merge commit
\ / \ /
\ / \ /
\ / \ /
A---B---C---D ← branch
In this scanario, part of branch has been merged into main, but also part of main has been merged into branch. This merge has two merge bases, 1 and A. What happens if we now try to merge the rest of branch (commits B and D) into main? This is tricky because there are some changes (namely 1 and A) that are on both branches, but neither merge base includes both of those changes.
By default, Git tries to perform a merge like this using "recursive merge". This algorithm first does a synthetic helper merge H between the two merge bases, 1 and A:
---0-------1---2---3---4 ← main
\ \ ⋅
\ \ ⋅
\ \ ⋅
\ H
\ / ⋅
\ / ⋅
\ / ⋅
A---B---C---D ← branch
Then it computes the three-way merge between 4 and D using H as the merge base:
---0-------1---2---3---4 ← main
\ \ ⋅ \
\ \ ⋅ \
\ \ ⋅ \
\ H M
\ / ⋅ /
\ / ⋅ /
\ / ⋅ /
A---B---C---D ← branch
The helper merge H is useful because it includes the changes from commits 1 and A, but doesn't include any commits twice. So it is a reasonable choice of merge base for the final merge M.
Recursive merge
Let's simplify the criss-cross merge to its bare minimum:
---A-------B---D---F ← main
\ \ / \
\ \ / \
\ \ / \
\ ⋅ ? ← desired merge commit
\ / \ /
\ / \ /
\ / \ /
C---E---G ← branch
Now let's rearrange it on a rectangular grid to make the patterns easier to recognize:
A---B---D | | | C---⋅---F | | | E---G---?
By default, Git uses the "recursive merge" algorithm to deal with merges that have multiple merge bases. How does recursive merge deal with this particular scenario? And, more importantly, does it always do the right thing?
Recursive merge first tries to create a helper merge H by doing a three-way merge of B and C using A as the merge base:
A---B---D | | | C--(H)--F | | | E---G---?
Since this is done by three-way merge, this helper merge only depends on the upper-left square:
A---B | | C---?
Then it does a three-way merge between F and G, using H as the merge base, producing M:
A---B---D | | | C--(H)--F | | | E---G---M
This is also a three-way merge, this time involving the lower-right square:
H---F | | G---?
Each of the merges (H and M) is done using three-way merge, following the rules from the previous section. But there is one very curious and important twist:
If the helper merge H results in a conflict, it might be that the recursive merge can succeed anyway. For example, in this scenario:
a---b---d a---b---d a---b---d | | | | | | | | | c---⋅---f → c--(X)--f → c--(X)--f | | | | | | | | | e---f---? e---f---? e---f---f
Note that the first merge conflicts, because it doesn't match any of our three-way merge patterns:
a---b | | c--(X)
But recursive merge continues anyway. Now it tries to perform the three-way merge from the lower-right square:
(X)--f | | f---?
But this is a recognized three-way merge pattern, and its result doesn't depend on what "(X)" is. So the resolution is f, because f is the value at the tip of each branch:
(X)--f | | f---f
The bottom line is that recursive merge always resolves any criss-cross merge where the two tips have the same contents to those contents, regardless of what happened earlier:
*---*---* *---*---* | | | | | | *---⋅---f → *---⋅---f | | | | | | *---f---? *---f---f
Menagerie of merges
How well does recursive merge match real-life expectations?
There are some scenarios that recursive merge handles just fine. There are others where it gives questionable non-conflict results, and still others where it produces a conflict even though the user's intention was arguably possible to infer. Let's go through some examples.
Scenarios where recursive merge succeeds
This section presents several scenarios where recursive merge gives a result that seems to align with what the user probably intended:
Same change made on both branches, staggered:
a---a---b a---a---b | | | | | | b---⋅---b → b--(b)--b | | | | | | b---b---? b---b---b
Different changes made on each branch, staggered:
a---b---b a---b---b | | | | | | a---⋅---b → a--(b)--b | | | | | | c---d---? c---d---d
In this case the user has already resolved the combination of b and c, namely d, so that should be the overall result.
Change b preferred over change d:
a---b---c a---b---c | | | | | | a---⋅---c → a--(b)--c | | | | | | d---b---? d---b---c
In this case the user has already decided that when merging b and d, the result b is preferred. So the result of applying change c to b should be c, just as it is in the first row.
Same resolution on both branches. Note that in this case the helper merge conflicts, but the final merge nevertheless works out as hoped because it matches the third three-way merge pattern:
a---b---b a---b---b | | | | | | c---⋅---d → c--(X)--d | | | | | | c---d---? c---d---d
Same final state on both branches:
a---b---d a---b---d | | | | | | c---⋅---f → c--(X)--f | | | | | | e---f---? e---f---f
Scenarios where recursive merge gives questionable results
There are some scenarios where recursive merge gives an answer (i.e., not a conflict), but it is not clear that the answer is the correct one:
Change b made then reverted on one branch; kept on the other branch. Note that there are two patterns in this family:
a---b---a a---b---a | | | | | | a---⋅---a → a--(b)--a | | | | | | b---b---? b---b---a a---b---a a---b---a | | | | | | b---⋅---b → b--(b)--b | | | | | | b---b---? b---b---b
Worryingly, recursive merge gives different answers for the two scenarios, even though they are logically pretty similar. In both of these scenarios, the pre-existing merges are consistent with three-way merges. Indeed, they might have been done automatically without any user attention. But they each use the following, less reliable three-way merge rule for one of those pre-existing merges:
a---b | | * * | | b---b
There are two plausible narratives here:
- Maybe change b was implemented then reverted on one branch, but then it was independently implemented on the other branch, possibly for another reason. In this case, it would be correct to keep b as the merge resolution.
- Maybe change b was cherry-picked from one branch to the other, then on one branch it was discovered that the change was bad, so it was reverted. In that case, one would want the revert back to a to be used as the merge resolution.
Since the correct result depends on facts that can't be known to the merge algorithm, it would probably be better to treat this as a merge conflict and ask the user to intervene.
Same change made then reverted on both branches:
a---b---a a---b---a | | | | | | b---⋅---b → b--(b)--b | | | | | | a---b---? a---b---b
In this case, arguably since change b was made then reverted on each of the branches, then the user merges are not needed, and the final result should be a. An alternative interpretation (which I think is less persuasive) is that the pre-done merges in both cases favored contents b over a, so the final result should also favor b. I think that the result should either be a conflict or a, whereas recursive merge gives b.
Scenarios where recursive merge unnecessarily (?) produces conflicts
There are also cases where the intention of the user seems relatively clear, but the recursive merge strategy produces conflicts. In some of these cases, it could be that git could do better than the recursive merge strategy, requiring the user to resolve fewer conflicts manually.
Most of these scenarios involve reverted changes:
Change b was made and reverted on one branch; a different change was made on the other branch:
a---b---a a---b---a | | | | | | c---⋅---c → c--(X)--c | | | | | | c---d---? c---d---X
Arguably, since b was reverted, merge d is irrelevant: it only shows how to merge b and c, but we don't want b in the final result. So the correct resolution in this scenario should be c:
a---b---a a---b---a | | | | | | c---⋅---c → c---⋅---c | | | | | | c---d---? c---d---c
Different changes made and reverted on each branch:
a---b---a a---b---a | | | | | | c---⋅---c → c--(X)--c | | | | | | a---b---? a---b---X
This scenario is similar to the previous case, but now both user-supplied merges are irrelevant because they merge changes b and c respectively, neither of which we want in the final result. Arguably, the result should be a:
a---b---a a---b---a | | | | | | c---⋅---c → c---⋅---c | | | | | | a---b---? a---b---a
Change b made and reverted on one branch, but it had no effect on the other branch:
a---b---a a---b---a | | | | | | c---⋅---c → c--(X)--c | | | | | | d---d---? d---d---X
In this scenario, change b was made then reverted on one branch, meaning that it should probably have no effect on the result. Moreover, when it was merged with the changes c and d made on the other branch, it was also ignored in favor of the other branch's tip d. So arguably, the correct resolution of this merge should be d:
a---b---a a---b---a | | | | | | c---⋅---c → c---⋅---c | | | | | | d---d---? d---d---d
Change b made and reverted on one branch:
a---b---a a---b---a | | | | | | c---⋅---c → c--(X)--c | | | | | | d---e---? d---e---X
This is a slightly less clear extension of the previous case. In this scenario, change b was made and reverted on one branch. Therefore, it, and merge e, are both irrelevant to the final result, and the correct resolution should arguably be d:
a---b---a a---b---a | | | | | | c---⋅---c → c---⋅---c | | | | | | d---e---? d---e---d
The example that motivated this study
There is one more interesting scenario, where recursive merge produces a conflict, but the correct merge resolution is pretty clear. This does not involve any reverts. This is the example that motivated this whole investigation:
The helper merge conflicts, but the exact same conflict has already been resolved by the user in one of the pre-existing merges:
a---b---d a---b---d | | | | | | c---⋅---e → c--(X)--e | | | | | | c---f---? c---f---X
In this case, recursive merge is unable to compute the helper merge because of a conflict between the change made in b and the change made in c. But recursive merge doesn't notice that that conflict has already been resolved by the user (twice!) in the form of commits f and e. Using this fact, we can fill in the middle blank:
a---b---d a---b---d | | | | | | c---⋅---e → c--(f)--e | | | | | | c---f---? c---f---?
Now note that merge e already includes all of the changes from both branches: b, c, and also d. But now the lower right corner can be done by three-way merge:
a---b---d a---b---d | | | | | | c--(f)--e → c--(f)--e | | | | | | c---f---? c---f---e
Therefore, e can be taken as the correct resolution in this scenario, and no conflict need be resolved by the user.
Seven-way merge
I think that these criss-cross scenarios could theoretically be handled better by a new "Seven-way merge algorithm" that takes into account the patterns of seven commits that can appear in a merge with two merge bases. It would match those commits to a table of seven-way merge rules, and return the appropriate result (which will sometimes be a conflict). This algorithm could be applied one hunk at a time. I think that there is a good chance that it would result in fewer incorrect merges and fewer unnecessary conflicts.
One big question is, would this approach generalize to tackling even more complicated merges? For example, what if the merge has even more than two merge bases? Can seven-way merges be composed?
How often does it come up?
Seven-way merge would probably only be useful for merges with multiple merge bases. Do these come up often enough to make the effort worthwhile?
Maybe not. I sampled a few largish repositories (see below), and only on the order of 1% of merges in those repos have multiple merge bases. And not even all of those merges are criss-cross merges (some have three or more merge bases).
On the other hand, merge conflicts are a very frustrating aspect of working with Git, and almost everybody has experienced merge conflicts that were too difficult to resolve. Moreover, when a multiple-merge-base merge fails, it can fail in a most baffling way, with conflict markers nested inside of other conflict markers, that is almost impossible to make sense out of. 7-way merge might be able to produce more understandable conflicts in some of these cases. Finally, some workflows generate more criss-cross merges than we might be accustomed to (I've heard of a very large repository in which more like 10% of merges have multiple merge bases). Is it possible that smarter handling of criss-cross merges could remove some of this frustration?
If we decide to pursue this, I would suggest the following as next steps:
- Choose some public repositories with various workflows (i.e., don't just pick the best-organized projects). Perhaps include both well-maintained projects but also "run of the mill" projects. Locate merges in the history that had more than one merge base. Check if they had conflicts. Also check whether there were diff hunks that didn't conflict, but where users changed the automatic merge resolution (sometimes these will be incorrect merges).
- Implement smarter handling of criss-cross merges. Instead of trying to find a clever algorithm that does the right thing in all situations, I think that it would be better to recognize some of the above patterns using a table that also tells how to handle the corresponding scenario. At first this can be a hacky, inefficient implementation.
- Apply the standard recursive merge algorithm and the new criss-cross merge algorithm to the sample of real-life merges. Compare the numbers of conflicts and the numbers of seemingly incorrect merges. Decide which of the patterns should be enabled and which should be treated as conflicts.
- If the results are encouraging, implement whatever is decided on in Git, so that users get a little bit better help with their merges.
Appendix: numbers of merge bases
What fraction of merge commits have multiple merge bases? I ran the following to count the number of non-octopus merges with each number of merge bases in the project's default branch:
for f in $(git rev-list --min-parents=2 --max-parents=2 HEAD)
do
echo "$f" $(git merge-base --all $f^1 $f^2)
done | awk '{print NF-1}' | sort -n | uniq -c
I ran the above command in git/git, torvalds/linux, and a large proprietary repository.
Note that 7-way merge as strictly described above would only apply to merges with exactly two merge bases.
git/git
In git/git, 1.39% of merges have exactly two merge bases:
| Merge bases | Count |
|---|---|
| 0 | 6 |
| 1 | 15416 |
| 2 | 223 |
| 3 | 69 |
| 4 | 40 |
| 5 | 42 |
| 6 | 26 |
| 7 | 26 |
| 8 | 17 |
| 9 | 17 |
| 10 | 20 |
| 11 | 15 |
| 12 | 13 |
| 13 | 7 |
| 14 | 10 |
| 15 | 8 |
| 16 | 5 |
| 17 | 3 |
| 18 | 1 |
| 19 | 4 |
| 20 | 6 |
| 21 | 2 |
| 22 | 6 |
| 23 | 6 |
| 24 | 2 |
| 26 | 3 |
| 28 | 3 |
| 29 | 1 |
| 34 | 1 |
| 38 | 1 |
| 40 | 1 |
| 42 | 1 |
| 47 | 1 |
| 65 | 1 |
torvalds/linux
In torvalds/linux, 2.51% of merges have exactly two merge bases:
| Merge bases | Count |
|---|---|
| 0 | 3 |
| 1 | 63182 |
| 2 | 1634 |
| 3 | 212 |
| 4 | 81 |
| 5 | 37 |
| 6 | 21 |
| 7 | 17 |
| 8 | 9 |
| 9 | 5 |
| 10 | 7 |
| 12 | 2 |
| 13 | 1 |
| 29 | 1 |
| 52 | 1 |
| 53 | 1 |
| 55 | 1 |
| 78 | 1 |
| 85 | 1 |
| 93 | 2 |
Example large proprietary repository
In this repository, 0.88% of merges have exactly two merge bases:
| Merge bases | Count |
|---|---|
| 0 | 4 |
| 1 | 330375 |
| 2 | 2948 |
| 3 | 29 |
| 4 | 5 |
| 7 | 1 |
| 13 | 1 |
