Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- Jun 12, 2026, 14:32 UTC
- Message-ID
- <CAL71e4OmPzpCXh-zZ8NsT6L4zVKnXV1gqiFZ2w0XgMJhD=LArQ@mail.gmail.com>
- In-Reply-To
- <0b3f7429-a4fb-4f7a-bf7b-5a0edeb1db52@gmail.com>
On 6/12/2026 2:52 PM, Derrick Stolee wrote:
Show 8 quoted lines
> 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.
Show 15 quoted lines
> 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