Merge-Base Computation and paint_down_to

The function paint_down_to_common() in commit-reach.c computes merge bases by walking the commit graph backwards from two sets of tips and finding where their ancestry meets.

Use cases

Computing merge bases is used in two different ways:

Finding all merge bases (merge-base --all, merge-tree, merge, rebase). A merge base is a common ancestor that is not itself an ancestor of another common ancestor.
Ancestry checks (in_merge_bases, used by merge-base --is-ancestor, branch -d, fetch). These ask: "is commit A an ancestor of commit B?" If a common ancestor equals one of the inputs, that input is necessarily the only merge base — no other common ancestor can be both as recent and not an ancestor of it.

Both use cases share the same algorithm and implementation.

Algorithm

Given a commit one and a set of commits twos[], the walk paints commits with two colors:

PARENT1: reachable from one
PARENT2: reachable from any commit in twos[]

The walk uses a priority queue ordered by generation number (highest first), breaking ties by commit date. Each step dequeues the highest-priority commit and propagates its paint flags to its parents, enqueuing any parent that gained new flags. When a commit receives both PARENT1 and PARENT2, it is a merge-base candidate. A candidate gains the STALE flag so its ancestors propagate staleness — any deeper common ancestor is necessarily redundant.

Topologically ordered and unordered generation regions

Commits fall into two regions based on whether their generation numbers provide a topological ordering guarantee:

    +------------------------------------------+
    |          Unordered region                |
    |  generation = INFINITY or V1_MAX         |
    |  queue order: heuristic (commit date)    |
    +------------------------------------------+
                      |
                      v
    +------------------------------------------+
    |          Ordered region                  |
    |  generation = finite, unsaturated        |
    |  queue order: topological                |
    +------------------------------------------+

In the ordered region, a child’s generation is strictly greater than its parent’s. Same-generation commits are necessarily independent, so the queue always processes children before their parents.

In the unordered region, parent-child pairs can share the same generation number, so topological order is not guaranteed. The queue uses commit-date as a heuristic, which typically produces a reasonable traversal order but may process a parent before its child.

Commits not in the commit-graph have generation INFINITY; v1 commit-graphs saturate at V1_MAX. Both place commits in the unordered region. Any optimization that depends on generation ordering must account for this saturation boundary. The early exit gates compare against a topological ceiling — GENERATION_NUMBER_V1_MAX for v1 graphs and GENERATION_NUMBER_INFINITY for v2 graphs — so that saturated commits are treated as unordered.

With generation ordering, values in the unordered region exceed those in the ordered region. The walk may therefore transition from the unordered region into the ordered region, but never in the reverse direction. Without a commit-graph, every commit has INFINITY and the walk operates entirely in the unordered region.

In the ordered region, paint on a dequeued commit is final — no future step can add flags to it. In the unordered region, a dequeued commit may later gain additional paint. Paint flags are only added, never removed, bounding the number of re-enqueues per commit.

Termination

The walk tracks the number of commits of each type in the queue (PARENT1-only, PARENT2-only, pending merge-base). The main loop ends when one of the following conditions holds:

The queue is empty.
The queue contains only stale entries.
Generation cutoff: the dequeued commit’s generation is below a caller-supplied min_generation threshold.
Single result: the caller only needs one merge base, one has been found, and the walk has entered the ordered region.
Side exhaustion: no pure PARENT1 or pure PARENT2 commits remain in the queue, no pending merge-base candidates exist, and the walk has entered the ordered region.

Stale entry condition

Once all queued entries are stale, no new merge-base candidates can be discovered — that requires at least one non-stale commit from each side meeting. Continuing the walk could still invalidate existing candidates by proving one is an ancestor of another, but remove_redundant() handles that as a post-processing step, so it is safe to exit early.

Side-exhaustion condition

A new merge-base requires commits from both sides to meet. When one side’s exclusive counter reaches zero and there are no pending merge-base candidates, no future traversal step can produce a new candidate. This optimization only activates in the ordered region, where paint flags are final at visit time; in the unordered region, a side that appears exhausted could reappear through late paint propagation.

Generation cutoff

Some callers (notably remove_redundant()) supply a min_generation threshold equal to the minimum generation of the input commits. These callers only need to determine reachability among the inputs, not find deep merge bases, so the walk can safely terminate when it dequeues a commit below this threshold.

Single result

When only one merge base is needed and the walk is in the ordered region with generation ordering, the first candidate found is necessarily the highest-generation common ancestor. No remaining commit in the queue can be a descendant of this candidate (generation ordering guarantees children are visited first), so it cannot be redundant and the walk can stop immediately.

Merge-Base Computation and paint_down_to_common()