Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- Jun 13, 2026, 14:08 UTC
- Message-ID
- <CAL71e4PD+zT2jLjjvC7EuYX5z6v_VafnWOUDHeEDBq2LGOK7Pw@mail.gmail.com>
- In-Reply-To
- <CAL71e4NRvmDagFAJE-0HYwiLPSfhVVQO2qZe-EJPVXxeC4PWqg@mail.gmail.com>
On Fri, 13 Jun 2026, Kristofer Karlsson wrote:
> In both shapes, C is the only merge-base. But in shape 2, the > walk through X's ancestry is P1-only: STALE propagates through > C's ancestors but never reaches D's lineage.
I have to add a self-correction here: STALE does reach D through the main line. The real issue is that the bypass branch has a low generation number, so max_nonstale keeps the loop alive until the stale frontier drains all the way down.
In our monorepo, the concrete trigger is imported repositories. An import merge brings in a separate history with its own root at generation 0. As soon as the walk crosses one such import above the merge-base, max_nonstale forces it to drain the entire main graph. Instrumenting paint_down_to_common confirms this: `merge-base --all HEAD HEAD~1000` takes 2.3M steps, of which almost all are stale.
Thanks, Kristofer