On Tue, 23 Jun 2026 at 15:50, Derrick Stolee [off-list ref] wrote:

quoted

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.

quoted

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.

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

quoted

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