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

[Derrick Stolee <stolee@gmail.com>]

On 6/12/2026 10:32 AM, Kristofer Karlsson wrote:
> The required condition must then not be simply "one side exhausted".
> The walk must also continue while non-stale P1|P2 commits remain in the
> queue, since those still need STALE propagation - they are still
> merge-base candidates.
> 
> 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. 
> 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.

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.

Thanks,
-Stolee