From: Kristofer Karlsson <krka@spotify.com>
Date: Tue, 23 Jun 2026 10:13:10 GMT
Subject: Re: [PATCH/RFC 2/6] commit-reach: introduce struct paint_queue with per-side counters
Message-ID: <CAL71e4NFHz_zVCWPvmTO8UPNyaKkDFqNQdd3CJykoiGmEhfUTA@mail.gmail.com>
In-Reply-To: <8d07f5a9-82fa-4aed-b407-363e659f6851@gmail.com>

On Mon, 22 Jun 2026 at 22:23, Derrick Stolee <stolee@gmail.com> wrote:
>
> On 6/22/2026 3:14 PM, Kristofer Karlsson wrote:
> >
> > On Mon, 22 Jun 2026 at 20:10, Derrick Stolee <stolee@gmail.com> wrote:
> >>
> >> When possible, I like to try to make loops only have one terminating
> >> condition. Should we have paint_queue_get() return NULL when it sees
> >> this internal state condition?
> >
> > Possibly, but that would couple the paint_queue struct very tightly with
> > the usage. Not a problem in practice since it only has one call site, and
> > it's unlikely that we want to add more of them but it may feel more natural
> > to let the paint_queue purely have the queue semantics and counters,
> > and keep the halt condition within the function itself. I don't feel
> > super-strongly about this and can change it if needed, I will just need to
> > verify that nothing else gets complex as a result, I have not fully thought
> > through the effects.
>
> Hm. Interesting. The coupling is perhaps expected, because the data
> structure tracks counts that don't otherwise need to be tracked.
> Maybe the terminating condition method could be descriptively named
> to say why it would be completing.
>

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.

> I just worry about the idea that a negative number (or an addition
> overflow) would create conditions for termination that we did not
> intend. That's why using the nonzero status as true/false combined
> with ands and ors is better.

Good point, I have addressed that locally too.

Thanks,
Kristofer