Documentation/technical/paint-down-to-common.adoc

Merge-Base Computation and paint_down_to_common()
==================================================

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:

 1. *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.

 2. *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.

[[generation-regions]]
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:

  1. The queue is empty.
  2. The queue contains only stale entries.
  3. Generation cutoff: the dequeued commit's generation is below
     a caller-supplied `min_generation` threshold.
  4. Single result: the caller only needs one merge base, one has
     been found, and the walk has entered the ordered region.
  5. 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.

Related documentation
---------------------

  - `Documentation/technical/commit-graph.adoc` -- generation numbers
    and the reachability closure property.