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

Previous: Derrick StoleeNext: Derrick Stolee
Message 3 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.