From: Kristofer Karlsson Date: Fri, 12 Jun 2026 14:32:35 GMT Subject: Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted Message-ID: In-Reply-To: <0b3f7429-a4fb-4f7a-bf7b-5a0edeb1db52@gmail.com> On 6/12/2026 2:52 PM, Derrick Stolee wrote: > The STALE bit is pushed from commits that have bits for both sides > of the merge. This isn't something that we can learn from just > walking each side: we need some amount of walking within the > intersection. > > This doesn't matter if we are looking for a single merge base, but > when we want the full set of independent merge bases, then the STALE > bit becomes very important. Thank you for the quick and detailed response and your counterexample graph is exactly the right thing to worry about. > A X > /| __/| > | |/ | > | B | > | | | > .......... > | | __/ > \|/ > C > > In this example, B can reach C through some long list of commits. > This makes B (and X) have much higher generation number than C. > After exhausting both sides of A...X, we have B and C in the queue > with both side bits and neither are stale. But we need to walk > from B to C to discover that C should be stale. I think your response helped me identify a mistake in how I described the halt condition. 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) In your example, B and C are both non-stale P1|P2 commits after both sides are exhausted. Therefore the walk continues. When B is processed it propagates STALE toward C through the d-chain, and because the finite-generation region is processed in descending generation order, that propagation reaches C before C is popped. 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]. Thanks, Kristofer