Criss-Cross Merges, Virtual Ancestors, and Rename Conflicts

A three-way merge assumes one base. Histories that merge back and forth violate the assumption in a way that is not rare in long-lived branches: two branches merge each other’s work in both orders, and afterwards neither tip is an ancestor of the other, yet each contains commits the other also contains. The set of maximal common ancestors then has more than one element, and picking one of them is not merely imprecise, it can produce a merge that silently reverts work.

The criss-cross that defeats a single base

Consider two branches that fork from a common commit. Branch A gains a commit that renames a function. Branch B gains a commit that changes the function’s body. Then A merges B, and B merges A. Each merge commit has both prior tips as parents, so both merge commits are common ancestors of the two current tips, and neither merge commit is an ancestor of the other.

Merging the two tips again now has two candidate bases. Taking the first merge commit as base means the second branch’s view of the rename is not represented: the base contains the renamed function, the branch that did not perform the rename appears to have renamed it back, and the merge reports a conflict or, worse, applies a change that undoes the rename. Taking the other base produces the mirror-image error. There is no single commit whose tree represents the common state of the two branches, because the common state is the combination of both merges.

The general condition is that the merge base set has more than one element. git merge-base --all prints the whole set, and printing more than one line is the signal that the simple procedure does not apply.

Building an ancestor that never existed

The recursive strategy resolves this by constructing a tree that represents the merge of the bases. It takes the merge bases, merges them pairwise using the same three-way procedure, and uses the result as the base for the real merge. When there are more than two, the intermediate results are merged in turn until one tree remains. That tree corresponds to no commit; it exists only for the duration of the operation.

The construction is recursive because merging the bases can itself encounter multiple bases, which is exactly what happens after repeated criss-crossing. Each level reduces the count, so the recursion terminates, but the work grows with the number of bases and with the size of the trees they contain.

The synthetic base has a weakness that no implementation detail removes. If the inner merge of the bases conflicts, there is no human to resolve it, and the strategy must choose. Recursive leaves the conflict markers in the synthetic base, which means the outer merge can then see a base containing marker text and produce conflicts whose content includes those markers. The resulting conflict is often described as bogus: it does not correspond to a disagreement between the two tips at all, but to an ambiguity in reconstructing their common state.

Recursive and its rewrite

The recursive strategy performed the inner merges by materialising the base trees and running the ordinary merge machinery over a temporary index, which meant the inner merges could touch on-disk state and were comparatively expensive. The ort strategy is a rewrite of the same algorithm with the inner merges performed entirely in memory. It produces the same results in principle, handles rename detection across the whole merge rather than per-path, and avoids the temporary on-disk state.

Ort also improved the treatment of directory renames. When one side moves many files out of a directory into another, the merge can infer that the directory itself moved and apply the other side’s changes to the files at their new locations. The inference requires enough of the directory’s files to have moved to make the pattern unambiguous; when the evidence is weak, the merge declines to infer and reports a conflict rather than guessing. The threshold and the behaviour are configurable, and disabling the inference entirely is possible for repositories where a directory move is not a reliable signal.

Neither strategy can recover information the base does not contain. A virtual ancestor is a best-effort reconstruction, and every conflict inside it is a place where the reconstruction is a guess.

Rename conflicts with no correct answer

Rename detection pairs a deleted path with an added path by content similarity, computed by the diff machinery, and the pairing is a matching problem, not a lookup. Several shapes of conflict follow directly from that.

A file renamed differently on each side is a one-to-two conflict: the base path is gone, and two new paths exist, each holding a version of the content. The merge cannot choose a name, so both paths are left with conflict entries. The reverse, two different base files renamed to the same new path, is a two-to-one conflict: the new path has two incompatible contents and no obvious original. A rename on one side combined with a modification on the other is mergeable, because the content merge is well defined once the paths are paired.

A rename combined with an addition at the old path is a rename/add conflict. One side moved the file away; the other side created a new file where it used to be. Both outcomes are legitimate, and the merge keeps the renamed file and the new file, reporting the situation so a human can decide whether the new file was meant to replace the old one.

Deletion against modification is the most common and the most consequential. One side deleted the file, the other changed it. The merge leaves the modified version in the working tree with a conflict, because silently deleting loses work and silently keeping loses the intent to delete. There is no third option that preserves both.

In each case the index holds stage entries rather than a single resolved blob: the base version at stage one, one side at stage two, the other at stage three, with the paths arranged to reflect what each side did. Resolution is the act of writing a stage-zero entry at each path that should survive and removing the rest.

git merge-base --all main topic        # more than one line means a criss-cross
git merge --no-commit topic            # stop before recording the result
git ls-files --stage --diff-filter=U   # inspect stages 1, 2, 3
git checkout --ours -- path/to/file    # take one side's blob, then git add
git rerere status                      # what the recorded resolutions cover

Remembering a resolution by its content

A conflict is reproducible, and the same one tends to recur across rebases, repeated merges, and cherry-picks. The rerere mechanism exploits that by hashing the conflicted region and storing the resolution under that hash.

When a merge leaves conflicts, the conflicted hunks are normalised and hashed, and the hash names a directory under the repository’s metadata. The preimage, the conflicted text as produced, and the postimage, the text after resolution, are stored as files. On a later merge, the same hash is computed before the user sees anything, and a recorded postimage is applied automatically. The mechanism is content-addressed like the object store, and it has the same property: it matches the exact conflict, not the intent behind it. A resolution recorded for one conflict does not transfer to a conflict whose surrounding context differs, which is why a small change elsewhere in the file can defeat it.

Rerere can also record a resolution that was wrong, and it will then reapply it faithfully. The recorded data lives outside the object graph, is not transferred by push, and is not shared between clones. Its main value is within one developer’s repeated rebase of a long-lived branch against a moving upstream, where the same handful of conflicts recur at every step.

Where the strategy boundary sits

Choosing a merge strategy is choosing which classes of ambiguity are resolved by rule and which are surfaced. A strategy that resolves more is faster and produces fewer interruptions, at the risk of a decision the author would not have made. A strategy that resolves less leaves work that a human must do but never invents an answer.

The octopus strategy sits at one end: it merges more than two heads in one commit and refuses to proceed if any conflict arises, which makes it suitable only for combining independent branches. The default two-head strategy sits in the middle, resolving textual conflicts by rule where the three-way comparison is unambiguous and stopping otherwise. Nothing in the system resolves a genuine disagreement about intent, because intent is not in the repository; the merge machinery only has trees, and the trees are consistent with more than one story about what was meant.

The conflict shapes described here all reduce to the same primitive: two diffs against a base, as covered in the three-way walk. When the base is synthetic, that primitive is applied twice, and the reliability of the outer result is bounded by the reliability of the inner one.