Re: [PATCH v6 01/10] Documentation/technical: add paint-down-to-common doc

On Sat, Jul 11, 2026 at 6:27 AM Kristofer Karlsson via GitGitGadget
[off-list ref] wrote:

From: Kristofer Karlsson <redacted>

Add a technical document describing the paint_down_to_common()
algorithm used for merge-base computation, covering the paint
walk, generation number regions, and termination conditions.

Thanks, this is really nice.

+In the finite region, generation ordering guarantees topological
+traversal: children are always visited before their parents. This
+means that paint on already-visited commits is final -- no future
+traversal step can add paint to them.

This is the critical invariant.

I think there's a small hole here, however.  For a v1 commit-graph,
generation numbers saturate at GENERATION_NUMBER_V1_MAX; from
Documentation/technical/commit-graph.adoc:

"""
We use the macro GENERATION_NUMBER_V1_MAX = 0x3FFFFFFF for commits whose
topological levels (generation number v1) are computed to be at least
this value. We limit at this value since it is the largest value that
can be stored in the commit-graph file using the 30 bits available
to topological levels. This presents another case where a commit can
have generation number equal to that of a parent.
"""

+In the INFINITY region, commit-date ordering can violate this: a
+parent with a later date can be visited before a child with an earlier
+date. Paint flags are therefore NOT final at visit time, and a
+commit visited with only one side's paint may later gain the other.

Perhaps we could lump GENERATION_NUMBER_V1_MAX the same as INFINITY
for this algorithm, since GENERATION_NUMBER_V1_MAX can also violate
the ordering we want?

+Generation cutoff
+~~~~~~~~~~~~~~~~~
+Some callers (notably `remove_redundant()`) supply a `min_generation`
+threshold -- the minimum generation of the input commits. No merge
+base can have a generation below this threshold, so the walk
+terminates as soon as it dequeues such a commit.

?  I'm not sure I'm following the wording here.  Typically a
merge-base is a common ancestor of the inputs, and ancestors have a
strictly lower generation than their descendants, and there's no limit
to how far back we might need to read to find a merge base.

I think what makes the min_generation cutoff safe is that callers
passing a nonzero min_generation (remove_redundant() and
repo_in_merge_bases_many()) don't need those deeper merge bases at
all: they only need to determine reachability among the input commits,
all of which sit at or above min_generation.

Is there a risk that with the current wording of this paragraph that
future callers might be tempted to pass a nonzero min_generation and
still expect a complete MERGE_BASE_FIND_ALL result?