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:04 UTC
Message-ID
<8d0902ca-98b7-44a4-a23b-51de44ab6daa@gmail.com>
In-Reply-To
<CAL71e4OmPzpCXh-zZ8NsT6L4zVKnXV1gqiFZ2w0XgMJhD=LArQ@mail.gmail.com>
On 6/12/2026 10:32 AM, Kristofer Karlsson wrote:
Show 9 quoted lines
> 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)

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.

> 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.

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.

Thanks, -Stolee

Previous: Kristofer KarlssonNext: Kristofer Karlsson
Message 4 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.