merge-base: Finding the Common Ancestor

A three-way merge starts with one question: what is the common ancestor? That is the BASE of the BASE, OURS and THEIRS you merged last time, and git merge-base A B answers it. After this lesson your program reads real commit objects, rebuilds the history graph, and answers merge-base --all and merge-base --is-ancestor the way git does, including the awkward case where there is more than one answer.

Ancestors and the "best" common ancestor

The ancestors of a commit are the commit itself, its parents, their parents, and so on. A commit is its own ancestor, which makes "is A an ancestor of B" true when A is B.

The common ancestors of A and B are the commits in both ancestor sets. Many commits qualify: if X is common, so is every ancestor of X. The merge needs the closest ones, so a common ancestor is best (git says: a merge base) when no other common ancestor descends from it. Here is a graph with a merge:

        r (root)
       / \
      p   q
       \ /
        m (merge of p and q)
       / \
      s   t

s and t have the common ancestors m, p, q and r. Only m is best, because p, q and r are all ancestors of m. Three-way merge against m leaves far less to reconcile than against r.

When there are two answers

History does not always have one best ancestor. After two branches merge into each other (a criss-cross), their tips can share two best common ancestors, neither of which is an ancestor of the other:

      a
     / \
    x   y
    |\ /|
    | X |        x merged into the right branch, y into the left
    |/ \|
    m1  m2

For m1 and m2 the common ancestors are a, x and y. a is an ancestor of both x and y, so it is not best, but x and y are each best. So the answer is a set, and git merge-base --all prints all of its members. Plain git merge-base prints one of them and the default merge strategy handles the rest by merging the bases first. In this exercise the answer is always the whole set.

An algorithm that is easy to get right

1. Compute the ancestor set of A and of B by a walk with a seen set (the same walk as git log, without the ordering).
2. Intersect them: the common ancestors.
3. Remove every common ancestor that is a proper ancestor of another common ancestor. What remains is the best set.

Step 3 can be done by walking from each common ancestor to its parents and marking everything reached as covered. It costs more than git's own method, which paints commits with "reached from A" and "reached from B" flags in a single date-ordered pass, but it is short and clearly correct.

Edge cases

• If B descends from A, the merge base of A and B is A itself. This is what makes a fast-forward detectable: A is an ancestor of B exactly when A is the merge base of A and B.
• The merge base of a commit with itself is that commit.
• Two histories with no shared root have no common ancestor. Git prints nothing and exits with status 1; the exercise prints NONE.
• A parent that was never provided (a shallow history) simply ends that branch of the walk.

Common mistakes

• Taking the common ancestor with the newest timestamp. Clocks lie; use the graph, not dates.
• Returning every common ancestor, or only the first one found.
• Forgetting that a commit is its own ancestor, which breaks the "B descends from A" case.
• Removing the wrong things in step 3: remove a common ancestor only if it is a proper ancestor of another common ancestor.

Your exercise

The starter parses the commit objects into a parent table and prints your answers. You write ancestors and merge_bases. The repositories in the tests were built with real git, including a criss-cross merge, an octopus merge and two unrelated roots, and every answer was checked against git merge-base --all and git merge-base --is-ancestor.