From: Derrick Stolee Date: Fri, 12 Jun 2026 15:04:38 GMT Subject: Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted Message-ID: <8d0902ca-98b7-44a4-a23b-51de44ab6daa@gmail.com> In-Reply-To: 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