Three-Way Merge

The most feared operation in git is a surprisingly small algorithm. Merging is not magic and not clever. It is a region-by-region comparison of three versions of a file, with a handful of outcomes, and a rule for when it must give up. After this lesson your program merges two edited versions of a file against their common ancestor and writes the same conflict markers git does.

Why three, not two

Compare only yours and theirs and you hit an unanswerable question. Your file has a line theirs lacks: did you add it, or did they delete it? The right merge differs (keep it or drop it), so a two-way merger can only guess.

The base, the common ancestor, answers it. A line that is in base and yours but not theirs was deleted by them: drop it. A line that is not in base but is in yours was added by you: keep it. The base comes from walking the commit graph to the last shared commit, which is what the merge-base lesson computes.

The algorithm

1. Diff base against ours, and base against theirs, with the diff you already wrote. Each diff is a list of hunks: "base lines start up to (not including) end were replaced by these lines". A pure insertion has start == end.
2. Walk the hunks of both sides in order of position and gather them into clusters. A hunk joins the cluster being built when its start is at or before the cluster's end, so changes that overlap, or merely touch, share a cluster. Two changes with at least one untouched base line between them are independent.
3. For each cluster:
   • Only one side has hunks in it: take that side's version of the region. This covers "only we edited", "only they edited", and the independent edits that make most merges clean.
   • Both sides have hunks: build each side's version of the cluster's base range. If the two versions are identical, take it (both made the same change, which is not a conflict). Otherwise it is a conflict.

The cluster rule decides the famous cases. If you change line 2 and they change line 3, that is a conflict even though the lines differ, because the hunks touch. If you change line 2 and they change line 4, line 3 separates them and both edits apply.

Conflict markers

<<<<<<< ours
(this side's version of the region)
=======
(their version of the region)
>>>>>>> theirs

Before writing a conflict, move the lines that both versions share at the start and at the end of the region outside the markers, so only the genuinely different part is marked. A line both sides left unchanged inside a changed region is not worth making the reader compare. Git does this and more (it also fuses conflicts that sit a few lines apart); this exercise stops here, and its tests avoid conflicts close enough for that to matter.

The markers escalate the decision to the one party with authority: you. Note what merging does not know. It never reads meaning. If you rename a function and they add a call to the old name, the merge is clean and the build is broken. The textual merge is a floor, which is why CI runs on merge results.

Common mistakes

• Treating a change that touches the other side's change as independent. Touching is a conflict.
• Calling identical edits on both sides a conflict, or dropping one of two different insertions at the same position.
• Comparing ours with theirs and ignoring base, which gets deletions wrong.
• Leaving the unchanged first or last line of a conflict inside the markers.
• Losing base lines between clusters, or emitting them twice.

Your exercise

The starter reads the three files and provides changes, your diff from the last lesson reshaped into hunks. You write merge3: clusters, the identical-change rule, the conflict markers with trimming, and the conflict count. The expected outputs were checked against git merge-file wherever its extra tidying cannot change the result.