Three-Way Merge and How the Merge Base Is Chosen

A two-way comparison between two branch tips answers the wrong question. It reports every difference between the two trees, including all the work one side did that the other simply has not seen yet. If a file was renamed on one branch and untouched on the other, a two-way diff sees a deletion and an addition, and there is no way to tell whether that deletion was intentional. Three-way merge solves this by introducing a third tree — the merge base — and asking a narrower question for each file: what did each side change relative to the base?

The base is the cut point, not the current tip

For two commits on divergent lines, the merge base is a common ancestor that is not itself an ancestor of another common ancestor. In graph terms it is a maximal element of the set of shared ancestors, which for simple histories is the point where the branches forked. git merge-base A B prints one such commit; --all prints all of them.

The search is a breadth-first walk from both tips over parent edges, marking visited commits from each side, and stopping at the first commit reachable from both. Restricting the walk to commits reachable from both tips matters: an ancestor of the base that lies on only one side is not a candidate. In a repository with many branches and a long history this walk is the expensive part of a merge, which is why a commit-graph file that stores generation numbers can let the traversal skip large regions without reading commit objects.

With more than two parents the same logic generalises: an octopus merge uses a base reachable from all parents. The recursive strategy merges pairs and folds the results, which is one reason octopus merges are rare and discouraged when the branches touch the same files.

Per-file decisions from three inputs

For each path, the merge reads the base version, ours, and theirs, and decides. The rules are mechanical:

• Base absent, ours present, theirs absent: keep ours. Only one side added the file, so the addition survives.
• Base present, both sides identical: take that version, no conflict.
• Base present, one side unchanged: take the other side’s version. This is the case that makes three-way merge worth the extra tree: a change on one branch wins automatically even though the other branch’s tree differs from it in every other file.
• Both sides changed differently: conflict, unless the changes are in disjoint regions and a line-level merge can combine them.

The last case is where diff3 does the work. It computes a diff from base to ours and from base to theirs, then walks the two edit scripts together. A region edited by only one side is applied. A region edited by both sides in the same place is a conflict. Regions edited by both sides in different places are both applied, and the hunks shift by the offsets the other side’s insertions introduced. That offset accounting is the fragile part: a line-level merge has no notion of syntax, so two edits that are textually distant can still be semantically incompatible, and two edits that are textually adjacent can be trivially compatible.

GNU diff3 exposes the raw result with its -m mode, and Git uses the same model internally, emitting the familiar markers:

<<<<<<< ours
retry_limit = 3
=======
retry_limit = 5
>>>>>>> theirs

The markers are the merge’s admission of a case it cannot decide, not an error state. The file is written with the conflict left in place and the merge is left incomplete so that a human or a later automated step resolves it.

Criss-cross histories and multiple bases

A single base is not always available. Consider two branches that each merged the other at different points, then diverged again. Now neither tip’s ancestors include a commit that is an ancestor of the other tip without a further common ancestor in between: there are two merge bases, and each is a legitimate candidate.

Choosing one arbitrarily produces a result that depends on traversal order, and can resurrect changes that the other base would have suppressed. The recursive strategy handles this by merging the bases into a virtual ancestor first: it runs the same three-way procedure on the two base commits, and if that produces conflicts it leaves the conflict markers inside the virtual base tree. The virtual base is never written as a commit; it exists only for the duration of the merge. The effect is that a change made on both sides is treated as already present in the base, so it does not conflict.

This is a heuristic, not a theorem. Merging bases can itself hit multiple bases and recurse, and each recursion can introduce a conflict into the base. When that happens the conflict surfaces in the outer merge at a location that neither side touched directly, which is why a conflict can appear in a file whose two branch versions are identical.

What three-way merge cannot see

The base is a snapshot of content, and the merge algorithm only compares bytes at line granularity. Several classes of change are therefore invisible:

• Renames. Git infers them by matching deleted blobs to added blobs above a similarity threshold, defaulting to fifty percent. A rename with substantial edits can fall below the threshold, and the merge then treats the file as deleted on one side, producing a modify/delete conflict rather than carrying the edits across.
• Mode changes. A change from 100644 to 100755 is a one-bit difference in the tree entry, and a merge that sees both sides change mode differently reports a conflict even though the file content is untouched.
• Semantic conflicts. Two branches can add a function and a call to it under different names, or change a signature and its caller on opposite sides. The text merges cleanly; the build fails.
• Binary files. No line structure means no hunk merge. Any change on both sides is a conflict by construction.

There is a further asymmetry worth noting: the merge result depends on the base, and the base depends on when the branches forked. Merging a long-lived branch late produces a base far in the past, so the two sides have diverged more and the automatic resolution has more opportunity to go wrong. This is an argument about integration frequency rather than about the algorithm, and it is the reason short-lived branches reduce conflict volume rather than merely moving it.

Reading a conflicted merge

When the automatic pass fails, Git records the three stages in the index rather than overwriting them. Stage 1 holds the base blob, stage 2 ours, stage 3 theirs; an unconflicted path has only stage 0. git ls-files -u lists exactly those entries, and git checkout --ours <path> or --theirs extracts one stage without resolving anything.

Resolution is a write to the working tree followed by git add, which collapses the three stages to a single stage-0 entry. The merge commit is created only when no unmerged entries remain. Because the stages are stored, an automated resolver can read all three inputs and write its own result; that is how custom merge drivers and rerere work, described in conflict markers, merge drivers, and recorded resolutions.

A merge commit’s tree is not derived from its parents by any invariant the object model enforces. It is whatever the resolving party wrote. The object graph records that two lines were joined, and records the result, but not how the join was computed. That gap is why git show on a merge is uninformative by default and why a combined diff has to be requested explicitly.

Choosing between merge and replay

Three-way merge preserves the topology: both parent lines remain reachable, so the graph records that work happened in parallel. The cost is a merge commit per integration and a history whose first-parent line is not the same as its full ancestry. Replay by rebase produces a linear first-parent line at the cost of new commit ids and no record of the fork.

Neither is more correct. A merge is the only operation that can express a join of two lines; a rebase is the only operation that can present a branch as though it had been written on top of the current tip. Which one a repository uses is a policy question, examined in fast-forward, merge commits, and first-parent history. The mechanics underneath are the same in both cases: a base tree, two candidate trees, and a rule set that decides per file.