Re: [PATCH v3 8/8] commit-reach: move min_generation check into paint_queue_get()
- From
Derrick Stolee <stolee@gmail.com>
- Date
- Jun 26, 2026, 14:42 UTC
- Message-ID
- <34ff8be2-1b3c-480f-ae27-9d65875e6e62@gmail.com>
- In-Reply-To
- <4b9f192d98b8e8f2d30eed4261a73e766eeafcc2.1782479286.git.gitgitgadget@gmail.com>
On 6/26/2026 9:08 AM, Kristofer Karlsson via GitGitGadget wrote:
Show 11 quoted lines
> 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.
Show 7 quoted lines
> @@ -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.
Show 17 quoted lines
> 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.
Show 9 quoted lines
> 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.
Show 30 quoted lines
> }
>
> @@ -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.
Show 12 quoted lines
> 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