Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted

[Derrick Stolee <stolee@gmail.com>]

On 6/12/2026 11:21 AM, Kristofer Karlsson wrote:
> On Fri, 12 Jun 2026 at 17:04, Derrick Stolee <stolee@gmail.com> wrote:
>>> So the actual halt condition would be:
>>>
>>>     no non-stale P1|P2 candidates in the queue
>>>     AND (no pure-P1 OR no pure-P2)
>>
>> And since STALE is added only after both P1 and P2 bits, the two
>> conditions are identical to how queue_has_nonstale() terminates the
>> loop.
> 
> No, I think this part is different. I can demonstrate with an example queue
> state: [P1, stale, P1, stale, stale]
> With the old code, the non-stale tracker would consider this to be non-stale
> since it still has two P1 commits to process.
> My new approach would instead consider that a valid halt state - we
> can't find any new merge-bases at that point.

Ah. this is indeed the detail I missed. For any i in {1, 2}, if Pi
only appears alongside the STALE bit, then we can stop the walk. This
tracks because the other bit can't contribute any new information.

A data shape that makes this particularly helpful is the "release
branch" data shape that I used to justify the --negotiation-include
option [1].

[1] https://lore.kernel.org/git/62e5ef1a4b800cb18b2e934f45303095d545613b.1779207896.git.gitgitgadget@gmail.com/

Suppose developers are merging into 'main' frequently. On occasion,
the tip of 'main' is merged into a new 'release' branch. Thus, the
first-parent history of 'release' is long and completely separate
from the commit history of 'main'. To reach the queue_has_nonstale()
exit condition, we'd need to walk the entire history.

However, if we focus on the single-side condition you are proposing,
we can stop walking once everything in the queue that is reachable
form 'main' is also reachable from that top merge-base.
>>> If this reasoning is correct, then the walk only terminates after
>>> merge-base candidates have either been processed or marked STALE,
>>> and the counterexample should produce [B] rather than [B, C].
>> That's the correct distinction: we need the set [B] and not [B,C]
>> but we need to discover that B can reach C to remove it from the
>> result set.
> 
> Yes, and I think that part works since we visit them in generational order,
> so B can invalidate C before C is reached.
> 
>> I think there is potential merit in "switching walk modes" to DFS
>> when all queued commits have both P1 and P2, but it comes with a
>> lot of complications. So tread carefully if you go down this road.
>>
> 
> On the DFS point: I may be misunderstanding the suggestion, but my current
> approach depends quite heavily on generation ordering. The reason the
> STALE propagation is safe is that, in the finite-generation region,
> descendants are processed before ancestors. If we switch to DFS, I think we
> would lose that ordering property unless the DFS is constrained in some
> additional way.
My thought was focused on the case of "all queued commits have P1 and P2"
and then we could determine which should be non-stale using DFS focused
only on the current queued set.

But I think your single-sided approach is a better way to get the gains
that you want. I think that case is much more likely to occur.

Thanks for your persistence in working on this through my
misunderstanding.

Thanks,
-Stolee