Re: [PATCH v3 8/8] commit-reach: move min_generation check into paint_queue_get()

[Derrick Stolee <stolee@gmail.com>]

On 6/26/2026 9:08 AM, Kristofer Karlsson via GitGitGadget wrote:
> From: Kristofer Karlsson <krka@spotify.com>
> 
> Consolidate the min_generation termination condition into
> paint_queue_get(), alongside the existing stale-entry and
> side-exhaustion checks.
> 
> Move last_gen into struct paint_state so that
> commit_graph_generation() is called exactly once per dequeued commit
> and the result is shared across all termination checks and the
> monotonicity BUG assertion.  The loop body in paint_down_to_common()
> reads state.last_gen instead of recomputing the generation number.

Thanks for incorporating this change into this version.

> +  4. Generation cutoff: the dequeued commit's generation is below
> +     a caller-supplied `min_generation` threshold.

Technically, this was always a termination condition of the walk,
but now we are correcting the documentation to match. It was just
not part of the termination in the dequeue method until now.

> @@ -89,6 +89,8 @@ struct paint_state {
>  	int p1_count;
>  	int p2_count;
>  	int pending_merge_bases;
> +	timestamp_t min_generation;
> +	timestamp_t last_gen;
>  };

I'm happy that these details are being imported into the struct.

My first reaction is that last_gen shouldn't be here because we
can see a generation from the dequeued commit. I'll read on to
be sure.
  
>  static void paint_count_update(struct paint_state *state,
> @@ -138,11 +140,23 @@ static void paint_queue_put(struct paint_state *state,
>  static struct commit *paint_queue_get(struct paint_state *state)
>  {
>  	struct commit *commit = prio_queue_get(&state->queue);
> +	timestamp_t generation;
>  
>  	if (!commit)
>  		return NULL;
>  
>  	commit->object.flags &= ~ENQUEUED;
> +	generation = commit_graph_generation(commit);
> +
> +	if (generation > state->last_gen)
> +		BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
> +		    generation, state->last_gen,
> +		    oid_to_hex(&commit->object.oid));

Oh I see. It's just for this condition.

Does this case still break without 'state->min_generation' in the
condition?

> +	state->last_gen = generation;

This is an appropriate use of this value. My concerns are no longer
valid. Thanks for letting me think out loud.

> +	/* generation cutoff */
> +	if (generation < state->min_generation)
> +		return NULL;

And here's the crux. Again, impossible for this to halt when
min_generation is zero.

>  	if (!state->pending_merge_bases) {
>  		/* only stale entries remain */
> @@ -151,7 +165,7 @@ static struct commit *paint_queue_get(struct paint_state *state)
>  
>  		/* one side is exhausted */
>  		if ((!state->p1_count || !state->p2_count) &&
> -		    commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
> +		    generation < GENERATION_NUMBER_INFINITY)
>  			return NULL;

Good reuse of the value.

>  	}
>  
> @@ -177,9 +191,10 @@ static int paint_down_to_common(struct repository *r,
>  	struct commit *commit;
>  	int i;
>  	int steps = 0;
> -	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
>  	struct commit_list **tail = result;
>  
> +	state.min_generation = min_generation;
> +	state.last_gen = GENERATION_NUMBER_INFINITY;
>  	if (!min_generation && !corrected_commit_dates_enabled(r))
>  		state.queue.compare = compare_commits_by_commit_date;
>  
> @@ -196,18 +211,8 @@ static int paint_down_to_common(struct repository *r,
>  	while ((commit = paint_queue_get(&state))) {
>  		struct commit_list *parents;
>  		int flags;
> -		timestamp_t generation = commit_graph_generation(commit);
>  		steps++;
>  
> -		if (generation > last_gen)
> -			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
> -			    generation, last_gen,
> -			    oid_to_hex(&commit->object.oid));
> -		last_gen = generation;
> -
> -		if (generation < min_generation)
> -			break;
> -

I'm happy this is getting cleaned up.

>  		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
>  		if (flags == (PARENT1 | PARENT2)) {
>  			if (!(commit->object.flags & RESULT)) {
> @@ -219,7 +224,7 @@ static int paint_down_to_common(struct repository *r,
>  				 * descendant of this one.
>  				 */
>  				if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
> -				    generation < GENERATION_NUMBER_INFINITY)
> +				    state.last_gen < GENERATION_NUMBER_INFINITY)
>  					break;
>  			}
>  			/* Mark parents of a found merge stale */

And here's another termination condition. We are now leaking the
abstraction of the 'state.last_gen' which give me some bad feelings.

We are getting to the point where I'd leave such a thing for a
follow-up, but since you are needing to re-roll, then this is
another case where we can move this into the paint_queue_get(). I
don't think this is me "raising the bar" from earlier recommendations,
because I was asking for all loop termination to be in the get()
method, if possible.

But also: I'm not looking at the full method right now to see if
terminating _at this location in the loop_ is critical. So it may
very well be impossible to move this into the get() call, in which
case please ignore this suggestion and use state.last_gen.

Thanks,
-Stolee