Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted
- From
Derrick Stolee <stolee@gmail.com>
- Date
- Jun 12, 2026, 15:04 UTC
- Message-ID
- <8d0902ca-98b7-44a4-a23b-51de44ab6daa@gmail.com>
- In-Reply-To
- <CAL71e4OmPzpCXh-zZ8NsT6L4zVKnXV1gqiFZ2w0XgMJhD=LArQ@mail.gmail.com>
On 6/12/2026 10:32 AM, Kristofer Karlsson wrote:
Show 9 quoted lines
> 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