git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

Previous: Kristofer KarlssonNext: Kristofer Karlsson
Message 6 of 10 in “[RFC] commit-reach: terminate merge-base walk when one paint side is exhausted”
  1. Kristofer KarlssonJun 12, 2026
  2. Derrick StoleeJun 12, 2026
  3. Kristofer KarlssonJun 12, 2026
  4. Derrick StoleeJun 12, 2026
  5. Kristofer KarlssonJun 12, 2026
  6. Derrick StoleeJun 12, 2026
  7. Kristofer KarlssonJun 13, 2026
  8. Kristofer KarlssonJun 13, 2026
  9. Elijah NewrenJun 14, 2026
  10. Kristofer KarlssonJun 14, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.