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

On Sun, 26 Jul 2026 at 08:59, Elijah Newren <[email protected]> wrote:
>
>
> 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?

Oh, that's a nice catch. I had completely missed this V1_MAX
saturation case! I spent some time thinking about this edge-case
and fortunately I think it's very hard to trigger. You would need
to construct a graph with 1B generations, which is a very big git
graph indeed.

That said, regardless of how hard it is to trigger the code should
be correct. I agree that we could lump GENERATION_NUMBER_V1_MAX
together with GENERATION_NUMBER_INFINITY since they are both
topologically unordered values and naturally must be topologically
above any lower values.

I considered two approaches. Both are correct as far as I can tell
and both only matter for very large v1 graphs, so in practice
either should be fine.

Option A: remap V1_MAX to INFINITY at load time in
fill_commit_graph_info(). On the read side:

    uint32_t level = get_be32(...) >> 2;
    if (level >= GENERATION_NUMBER_V1_MAX)
        graph_data->generation = GENERATION_NUMBER_INFINITY;
    else
        graph_data->generation = level;

This is a fairly small change and everything downstream just
works. The write path already uses the separate topo_levels
slab so it would keep writing V1_MAX for backward compatibility.

The downside is that it conflates two distinct concepts: "not in
the commit-graph at all" and "in the graph but ordering has
saturated." This specifically affects the bloom filter checks
in blame.c, revision.c and last-modified.c where we check for
gen == INFINITY to mean specifically "not in the graph" because
a commit not in the graph cannot have a bloom filter.
With the remap, V1_MAX commits would unnecessarily skip bloom
filters. Not a correctness bug, but a performance regression
for those commits. Perhaps not a very important case though -- if
you have that many commits and notice performance issues you
should probably upgrade to v2 anyway.

That said, even if it technically works today, maybe new code
in the future would have stronger dependencies on the semantics
so it feels fragile.

Option B: introduce commit_graph_generation_topo_ceiling(r) that
returns the generation value where topological ordering is
no longer guaranteed -- V1_MAX for v1 graphs, INFINITY for v2 or
no graph. Then the early exit gates use:

    if (generation < state.topo_ceiling)
        /* in the topologically ordered region */

This keeps INFINITY meaning "not in the graph" and V1_MAX meaning
"saturated but present." Bloom filter checks continue to work
the same as before. It does introduce a new concept that callers
of the ordering gates need to be aware of, but the concept maps
directly to the underlying graph format difference.

I went with option B in my local v7 draft since it felt
like a less intrusive change, though it would be nice to hide
the v1/v2 differences more from the rest of the code.

Let me know if you have a preference or see issues with either
approach.

> 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?

You are right, the wording is misleading. I can update it to
something like this instead (will polish it more, just a draft):

    Note: A non-zero min_generation floor means that you are not
    guaranteed to find any merge-base, it is purely useful for
    determining the ancestry relation between the input commits.
    If it is set, the walk can terminate as soon as we have passed
    the bottom commit, because we then know that there is no direct
    ancestry.

Thanks, I really appreciate the careful review and spotting
this edge case!
Kristofer