From: Kristofer Karlsson Date: Fri, 12 Jun 2026 15:21:20 GMT Subject: Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted Message-ID: In-Reply-To: <8d0902ca-98b7-44a4-a23b-51de44ab6daa@gmail.com> On Fri, 12 Jun 2026 at 17:04, Derrick Stolee 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. > > 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. So I think I may not fully understand the DFS idea, and I am not sure if that type of optimization would be orthogonal to tweaking the halt condition or not. Thanks, Kristofer