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:48 UTC
- Message-ID
- <8c06cc48-d036-4d01-98d3-e94b5edb389c@gmail.com>
- In-Reply-To
- <CAL71e4MFb3UUKBr1P4ZwtK3o1gvUHMs+siCpLTXKkW6Vx=BxRg@mail.gmail.com>
On 6/12/2026 11:21 AM, Kristofer Karlsson wrote:
Show 16 quoted lines
> On Fri, 12 Jun 2026 at 17:04, Derrick Stolee <stolee@gmail.com> 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.
Ah. this is indeed the detail I missed. For any i in {1, 2}, if Pi only appears alongside the STALE bit, then we can stop the walk. This tracks because the other bit can't contribute any new information.
A data shape that makes this particularly helpful is the "release branch" data shape that I used to justify the --negotiation-include option [1].
[1] https://lore.kernel.org/git/62e5ef1a4b800cb18b2e934f45303095d545613b.1779207896.git.gitgitgadget@gmail.com/
Suppose developers are merging into 'main' frequently. On occasion, the tip of 'main' is merged into a new 'release' branch. Thus, the first-parent history of 'release' is long and completely separate from the commit history of 'main'. To reach the queue_has_nonstale() exit condition, we'd need to walk the entire history.
However, if we focus on the single-side condition you are proposing, we can stop walking once everything in the queue that is reachable form 'main' is also reachable from that top merge-base.
Show 21 quoted lines
>>> 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.
My thought was focused on the case of "all queued commits have P1 and P2" and then we could determine which should be non-stale using DFS focused only on the current queued set.
But I think your single-sided approach is a better way to get the gains that you want. I think that case is much more likely to occur.
Thanks for your persistence in working on this through my misunderstanding.
Thanks, -Stolee