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

From: Kristofer Karlsson <krka@spotify.com>
Date: Jun 23, 2026, 14:09 UTC
Message-ID: <CAL71e4PzjdNCaVRtXg7wh9s6DxBeA4ock1aTzq8VPxKCmE-obA@mail.gmail.com>
In-Reply-To: <509fa950-fb9b-468d-b917-6c0eb7823d64@gmail.com>

On Tue, 23 Jun 2026 at 15:50, Derrick Stolee <stolee@gmail.com> wrote:

Show 24 quoted lines

>
> > 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;
> >   }
>
> This looks good to me. I'm not even bothered by the last_gen
> parameter. You do make a good point about it being a potentially
> leaky abstraction.

Agreed, I am not also bothered by it.

Show 16 quoted lines

> > 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().
>
> How much of this data that you are passing into the method could be
> state in the paint_queue struct? Could we have the paint_queue manage
> all of the state necessary to make decisions around the walk
> termination?

Good idea, I think adding last_gen to the struct is doable and makes it cleaner. If needed we could also add the mb_flags there (but would be a followup patch) Minor note: I renamed the struct to paint_state so that I could rename the prio_queue to queue and not have "queue.queue" which felt confusing in the code.

Show 5 quoted lines

> Or, could we do a peek into the queue to see the "top" commit, and
> check if it is a finite commit or not? I know that 'last_gen' is
> supposed to be the commit walked in the previous cycle, but it seems
> that we only care about "the remaining commits are finite" as our
> condition.

Yes, peeking into the queue would work too, but it would feel awkward,

  commit = prio_queue_peek();
  if (halt conditions) return NULL;
  prio_queue_get();

And if we get first, the condition is not valid - that said, it would be doable to instead put the halt conditions _between_ popping the commit and updating the counters. I am not sure how ugly or confusing it would be, but I could add a comment to explain why that sequencing is important. (Popping the commit and updating the counters may lead to temporary 0 counts, but then when we enqueue parents of the commits they move away from the 0 anyway). It would become something like:

// dry-/pseudo-coded
  commit *paint_queue_pop() {
    commit = prio_queue_pop();
    if (!commit) return NULL;
    if (halt_condition(state, commit.generation)) return NULL;
    // important: don't decrement counters before checking the halt condition
    paint_count_update(state, commit->object.flags, -1);
    return commit;
  }

Show 6 quoted lines

> > Right now I am leaning towards simply passing in last_gen and
> > containing all of the halt conditions there
> > (except the old !FIND_ALL).
>
> This is a good start, but hopefully storing the data in the
> struct would be a good way to handle that.

Sounds good, I will massage the code a bit, store the relevant pieces in the struct and see how clean I can make it.

Thanks, Kristofer