Re: [PATCH v3 8/8] commit-reach: move min_generation check into paint_queue_get()
From: Derrick Stolee <hidden>
Date: 2026-06-26 14:42:57
On 6/26/2026 9:08 AM, Kristofer Karlsson via GitGitGadget wrote:
From: Kristofer Karlsson <redacted> 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.
quoted hunk ↗ jump to hunk
@@ -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.
quoted hunk ↗ jump to hunk
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.
quoted hunk ↗ jump to hunk
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.
quoted hunk ↗ jump to hunk
}@@ -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.
quoted hunk ↗ jump to hunk
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