Merge Bases and the Three-Way Merge Walk

Two versions of a file and no common reference give no way to decide which side changed what. If a line reads differently in each, either side may have edited it, or both may have edited it in the same way, or one side may be the original and the other an edit. A merge tool needs a third version to answer that, and in a version control system the third version is a commit: the most recent common ancestor of the two branches. Most of the difficulty in merging is not in combining text but in choosing that ancestor correctly.

The base is what makes “changed” meaningful

Given three versions of a file, the combination rule is simple. A region that is identical in the base and in one side was changed only by the other side, so the other side’s version is taken. A region changed identically on both sides is taken once. A region changed differently on both sides is a conflict, because no rule can prefer one without discarding work.

That rule is why a two-way merge cannot work. With only the two tips, every difference is ambiguous, and a tool that guesses produces silent losses. It is also why the choice of base matters: an older base makes more regions look changed on both sides, and a base from the wrong branch makes whole files appear rewritten.

The base is a commit, not a snapshot of the branch point at the time the branch was created. Branches do not record their origins. The base is computed from the graph every time a merge runs, which means it can change as history changes, and it can be ambiguous when history is not a simple fork.

The best common ancestor

The set of common ancestors is the intersection of the two commits’ ancestor sets. Most of that set is irrelevant: an ancestor of another common ancestor is too old to be useful, because using it would attribute changes made after it to both sides. The useful members are the maximal elements, those not reachable from any other common ancestor. Git calls these the merge bases.

Computing them naively would require materialising both ancestor sets. Implementations instead walk backwards from both tips, marking each commit with which side reached it, and stop expanding a commit once it is known to be reachable from a commit already marked as common. Because the walk is over a graph without a natural order, the frontier is kept in a priority queue ordered by commit date, which is a heuristic: it finds the answer faster on typical histories but does not change which commits qualify.

A linear history has exactly one merge base, the fork point. A history where the branches have merged before has several, and choosing one of them is not a valid simplification; the handling of that case is described under criss-cross merges. Unrelated histories have none at all, which is why merging two independently created repositories requires an explicit flag: without a base there is no three-way rule, and the only options are to take one side or to treat every path as added on both sides.

def ancestors(start, parents):
    seen, stack = set(), [start]
    while stack:
        c = stack.pop()
        if c not in seen:
            seen.add(c)
            stack.extend(parents.get(c, ()))
    return seen

def merge_bases(a, b, parents):
    common = ancestors(a, parents) & ancestors(b, parents)
    # Keep only the maximal elements: drop any common ancestor that another
    # common ancestor can reach. This is the definition, not the fast path.
    return {c for c in common
            if not any(c in ancestors(o, parents) - {o} for o in common if o != c)}

Walking two diffs against one base

With the base fixed, the merge computes two diffs: base to one side and base to the other. Both are expressed as hunks over base line ranges, which is what makes them comparable. The hunks are then walked in order of their base position.

A hunk from one side whose base range does not overlap any hunk from the other side is applied unchanged. Two hunks whose ranges overlap and whose replacement text is identical collapse into one. Two overlapping hunks with different text produce a conflict covering the union of their ranges, with the base text, the first side, and the second side all preserved.

This is the diff3 procedure, and its granularity is inherited entirely from the diff algorithm that produced the hunks. A minimal diff that splits a changed block into two hunks a few lines apart creates two conflict regions where a human would see one. A diff that merges two nearby changes into one hunk creates a larger conflict than necessary. That sensitivity is the reason merge tools offer alternative diff algorithms, and the reason a conflict can look unreasonable without the merge being wrong.

Insertions at the same point are a special case worth naming. Two branches that each add a line at the same position in a file have hunks with empty base ranges that coincide. Whether that is a conflict depends on whether the inserted text is identical; when it is not, the result is a conflict over a zero-length region, which is why the markers can appear between two lines with nothing of the base between them.

Markers are a serialisation of three versions

A conflicted region is written into the working file with seven-character markers: <<<<<<< followed by the first side’s label, the first side’s lines, =======, the second side’s lines, and >>>>>>> followed by the second side’s label. The labels default to the branch names or commit descriptions involved.

The default style discards the base text from the file, which means the reader cannot see what the region looked like before either side changed it. An alternative style inserts a ||||||| section holding the base lines between the first side and the separator, which usually makes the intent of each side obvious and shortens the time to resolve. A third style trims lines common to both sides out of the conflict, leaving only the genuinely divergent part, at the cost of a marker layout that some tools parse poorly.

The markers are ordinary text. Nothing prevents committing a file that still contains them, and nothing detects the mistake afterwards except a search. Conflict state lives in the index, not in the file, so a file with markers that has been added is committed as resolved.

Renames move the merge to another path

A path that exists in the base and in only one side, and does not exist in the other, is a deletion. If the other side added a path with similar content, the merge may interpret the pair as a rename and merge the two versions of the file under the new name. Similarity is estimated from the proportion of shared lines, and the threshold is a percentage that can be configured.

Renames complicate the walk because the two diffs are no longer over the same path set. The merge has to pair deletions with additions before it can compare content, and the pairing is heuristic. A file renamed and heavily edited may fall below the similarity threshold and be treated as a delete plus an add, which turns a clean merge into a delete/modify conflict. A file split into two may be paired with one half and not the other.

What a merge commit does not record

The result of a merge is a tree and a list of parents. The decisions taken to produce it are not stored. If the merge resolved a conflict by choosing one side, the merge commit’s diff against that side is empty for the affected region, while its diff against the other side shows the whole change; neither diff reveals that a decision was made. Changes introduced during a merge that appear in neither parent are possible and are conventionally called evil merges, and no structural check distinguishes them from an ordinary resolution.

This is also why the same conflict recurs: merging the same two branches again re-runs the same procedure against a possibly different base and reaches the same impasse, with no memory of the previous resolution. Tools that record resolutions do so by hashing the conflicted text, which is a separate mechanism described with criss-cross merges and rename conflicts.

Binary files have no line structure to merge, so a conflict on a binary path is resolved by choosing one whole version; the marker mechanism cannot apply. Mode changes, symbolic links, and submodule pointers are merged as scalar values with the same three-way rule, which produces conflicts that cannot be edited as text at all.