When Histories Diverge: Building a Three-Way Merge From the Diff Up

Git's conflict marker feels like an accusation: two people touched the same place, and now the tool has stopped. That framing hides the useful part. A conflict is not a verdict about code quality. It is a report that two independent edit scripts cannot be composed without a choice. To read that report quickly, it helps to know what Git is comparing and why the comparison takes three inputs rather than two.

Start with a diff, not a merge

A diff is often described as a line-by-line comparison, but that undersells it. A diff is an alignment. Given two sequences, a diff tool finds a correspondence between elements and reports the edits needed to transform one into the other. In the classic formulation, the best diff is a shortest edit script: the fewest insertions and deletions that turn the left side into the right side. That script is tied to a longest common subsequence, because every element kept in the alignment is an element the edit script does not touch.

Practical tools approximate this. Python's difflib.SequenceMatcher returns opcodes, which are hunks in coordinates on both sides. An equal opcode is a matched run. replace, delete, and insert opcodes are edits. For merging, the important move is to restate those opcodes as edits against the base: each hunk says, 'in this range of the base, substitute this text from the side.'

from difflib import SequenceMatcher

def edits(base, side):
    return [(i1, i2, side[j1:j2])
            for tag, i1, i2, j1, j2 in
            SequenceMatcher(None, base, side).get_opcodes()
            if tag != 'equal']

That small function is the hinge. Once both sides are expressed as edits to the same base, merging becomes an interval problem rather than a line-by-line guess.

The common ancestor is the pivot

A two-way diff can tell you that two files differ. It cannot tell you who changed what, or whether one side is the original and the other is the revision. Three-way merging adds the missing coordinate: the common ancestor. With a base version, you can compute base -> ours and base -> theirs. Edits that occupy disjoint regions can be applied in either order. Edits that overlap require judgment.

The overlap rule has a subtle case: insertions. Two insertions at different offsets do not collide. Two insertions at the same offset do collide when their text differs, because there is no base text to anchor an order. Two identical insertions at the same offset can collapse into one edit. This is why a three-way merge can sometimes resolve cleanly even when both branches touched the same neighborhood: the changes are either separated or literally the same.

A small merger that emits markers

The following merger is deliberately abridged, but it shows the shape of the real thing. It computes edits from the base to each side, detects clashing pairs, and otherwise applies all edits from right to left so earlier offsets remain valid.

def clashes(a, b):
    if a[0] == a[1] and b[0] == b[1]:
        return a[0] == b[0] and a[2] != b[2]
    return max(a[0], b[0]) < min(a[1], b[1])

def merge(base, ours, theirs):
    left, right = edits(base, ours), edits(base, theirs)
    for a in left:
        for b in right:
            if clashes(a, b) and a[2] != b[2]:
                lo, hi = min(a[0], b[0]), max(a[1], b[1])
                return (base[:lo] + '<<<<<<< ours\n' +
                        base[lo:a[0]] + a[2] + base[a[1]:hi] +
                        '\n=======\n' +
                        base[lo:b[0]] + b[2] + base[b[1]:hi] +
                        '\n>>>>>>> theirs\n' + base[hi:])
    merged = base
    for start, end, text in sorted(left + right,
                                   key=lambda e: (e[0], e[1]),
                                   reverse=True):
        merged = merged[:start] + text + merged[end:]
    return merged

Production merge drivers handle more: rename detection, whitespace settings, union merges for specific file types, and recursive merges for criss-cross histories. But the core contract is visible here. A clean merge is a composition of non-clashing edit scripts. A conflict is the place where composition stops.

Why some conflicts cannot be engineered away

It is tempting to believe a better algorithm would eliminate conflicts. It cannot eliminate all of them, because the missing information is intent. If one branch changes a function to return null on missing input and another changes it to throw, the base text does not encode which policy the team wants. If two branches insert different imports at the same line, the base cannot decide the preferred order. The tool can only surface the choice.

This is also why 'take ours' and 'take theirs' are not resolutions. They are decisions made without reading the other side. A real resolution preserves the intended behavior of both changes where possible, then records the choice in tests or documentation. The conflict marker is a prompt to recover intent, not a formatting problem.

Habits for faster resolution

Use a diff3-style conflict view. git checkout --conflict=diff3 <path> shows the base section alongside each side, which often makes the intended composition obvious. Keep formatting-only changes in separate commits; a formatter that rewrites a whole file will collide with every nearby edit. Rebase or merge frequently enough that the common ancestor is recent. When a conflict is genuinely semantic, write a small test that fails before the resolution and passes after it.

Finally, read the conflict from the outside in. Identify the base hunk, name what each side was trying to accomplish, then compose. That habit turns a merge conflict from an interruption into a short design conversation with two authors and one shared history.