Re: [PATCH v2 5/7] commit-reach: introduce struct paint_state with per-side counters

[Derrick Stolee <stolee@gmail.com>]

On 6/24/2026 8:14 AM, Kristofer Karlsson via GitGitGadget wrote:
>  Termination
>  -----------
>  
> -The walk uses a `nonstale_queue` wrapper around `prio_queue` that
> -tracks `max_nonstale`: the lowest-priority non-stale commit enqueued
> -so far. Once that commit is dequeued, every remaining entry is known
> -to be STALE and the loop terminates. Specifically, the main loop
> +The walk tracks the number of commits of each type in the queue
> +(PARENT1-only, PARENT2-only, pending merge-base). The main loop
>  ends when one of the following conditions holds:
>  
>    1. The queue is empty.
> -  2. `max_nonstale` has been dequeued, meaning the queue only contains
> -     STALE entries.
> +  2. The queue contains only stale entries.

I'm grateful to see these changes happening to the doc in real-
time. I know it was extra work, but I'm grateful right now.

Hopefully future historians will also benefit from this effort.

> +static void paint_count_update(struct paint_state *state,
> +			       unsigned flags, int delta)
> +{
> +	switch (flags & (PARENT1 | PARENT2 | STALE)) {
> +	case PARENT1:
> +		state->p1_count += delta;
> +		break;
> +
> +	case PARENT2:
> +		state->p2_count += delta;
> +		break;
> +
> +	case PARENT1 | PARENT2:
> +		state->pending_merge_bases += delta;
> +		break;
> +
> +	case PARENT1 | PARENT2 | STALE:
> +		break;
> +
> +	default:
> +		BUG("unexpected paint state");
> +	}
> +}

I like the use of 'delta' to allow reuse of this switch.

> +
> +static void paint_queue_put(struct paint_state *state,
> +			    struct commit *c, unsigned add_flags)
> +{
> +	unsigned old_flags = c->object.flags;
> +	c->object.flags |= add_flags;
> +
> +	if (old_flags & ENQUEUED) {
> +		paint_count_update(state, old_flags, -1);
> +		paint_count_update(state, c->object.flags, 1);
> +	} else {
> +		c->object.flags |= ENQUEUED;
> +		prio_queue_put(&state->queue, c);
> +		paint_count_update(state, c->object.flags, 1);
> +	}
> +}

ok: if we are already in the queue then we have old flags and
may need to subtract their values because they were counted
already. Otherwise, we need to queue it for the first time and
only add the values. Makes sense.

> +
> +static struct commit *paint_queue_get(struct paint_state *state)
> +{

Since we are going to make this a more complete termination
condition, we may want to make that very explicit with a doc-
comment. Something along the lines of "dequeue a commit when
possible, but also signal termination of the walk when we
conclude that no more merge bases will be discovered due to
internal state."

> @@ -187,12 +253,11 @@ static int paint_down_to_common(struct repository *r,
>  				return error(_("could not parse commit %s"),
>  					     oid_to_hex(&p->object.oid));
>  			}
> -			p->object.flags |= flags;
> -			nonstale_queue_put_dedup(&queue, p);
> +			paint_queue_put(&state, p, flags);

I like how this simplifies the flag-assignment logic somewhat.

You mentioned in your cover letter how the min_generation value
can add extra termination conditions. It may be a good idea to
insert min_generation into the paint_queue struct and make it a
termination condition for paint_queue_get(). If you consider this
direction, then I'd make it a separate patch on top of this one
_before_ adding the one-sided change. The extra tests that cover
the exact number of walked commits can help to guarantee the same
behavior, assuming that some of those tests check a non-zero
min_generation input. (It may be good to add such trace tests in
an earlier patch to help confidence in this case.)

Thanks,
-Stolee