Re: [PATCH/RFC 2/6] commit-reach: introduce struct paint_queue with per-side counters

On Mon, 22 Jun 2026 at 22:23, Derrick Stolee <stolee@gmail.com> wrote:

I have been working on v2 locally and most of the changes landed nicely and were clear improvements but there's one point I would want to discuss a bit more.

For the termination conditions, I moved them into paint_queue_get() as you suggested. The all-zero check was straightforward since it only depends on the counters but the side-exhaustion check also needs to know whether we have entered the finite-generation region, so I pass last_gen (already a local in paint_down_to_common) as a parameter:

  static struct commit *paint_queue_get(struct paint_state *state,
                                        timestamp_t last_gen)

Inside, the two conditions merge nicely under a shared guard:

  if (!state->pending_merge_bases) {
      if (!state->p1_count && !state->p2_count)
          return NULL;
      if (last_gen < GENERATION_NUMBER_INFINITY &&
          (!state->p1_count || !state->p2_count))
          return NULL;
  }

Both conditions require pending_merge_bases == 0, so the nesting felt natural. The first is "nothing non-stale left" (works in any region). The second is "one side exhausted" (only in the finite region where topological ordering holds).

I think passing in last_gen into paint_queue_get() feels _slightly_ awkward but not too bad in practice. However, we also have my older (first) patch with the fast-exit if the caller only needs one merge base -- that has a separate break that also could be folded into paint_queue_get(). The messy part here is that we would need to also pass the mb_flags parameter to paint_queue_get().

Perhaps we should just let this remain as-is for now and follow up with _removing_ that optimization. I think the value of having it is much diminished (but not fully gone) by the side-exhaust approach.

Additionally there's a correctness argument to be made -- perhaps all callers _should_ care about multiple merge bases existing, and instead bail out if it finds more than one. The only use case where this matters today is "git merge-base A B" without --all.

Right now I am leaning towards simply passing in last_gen and containing all of the halt conditions there (except the old !FIND_ALL).

The nicest alternative I can think of is to let this part only break when the queue is empty:

  while ((commit = paint_queue_get(&state)))

and then adding a logical halt-section at the end of the while-loop (where all the useful variables we need are already available), and we could logically think of that as an optimization section, never strictly needed for correctness.

Good point, I have addressed that locally too.

Thanks, Kristofer