Re: [PATCH v2 7/7] commit-reach: terminate merge-base walk when one paint side is exhausted

[Derrick Stolee <stolee@gmail.com>]

On 6/24/2026 8:14 AM, Kristofer Karlsson via GitGitGadget wrote:
> From: Kristofer Karlsson <krka@spotify.com>
> 
> Add an early termination check to paint_down_to_common() using the
> per-side counters introduced earlier. Once the walk enters the
> finite-generation region, terminate early when one side's exclusive
> count drops to zero -- no new merge-base can form without both paint
> sides meeting.

Having this as the last patch is truly a nice climax moment for the
patch series!

> @@ -94,6 +94,9 @@ ends when one of the following conditions holds:
>  
>    1. The queue is empty.
>    2. The queue contains only stale entries.
> +  3. Side exhaustion: no pure PARENT1 or pure PARENT2 commits
> +     remain in the queue, no pending merge-base candidates exist,
> +     and the walk has entered the finite-generation region.
...> +Side-exhaustion condition
> +~~~~~~~~~~~~~~~~~~~~~~~~~
> +A new merge-base requires commits from both sides to meet. When one
> +side's exclusive counter reaches zero and there are no pending
> +merge-base candidates, no future traversal step can produce a new
> +candidate.
> +
> +This optimization only activates in the finite-generation region
> +where topological ordering holds. In that region, children are
> +always visited before parents, so paint flags are final at visit
> +time and an exhausted side cannot reappear. In the INFINITY region,
> +commit-date ordering can violate this guarantee, so the check is
> +skipped.
> +

And these doc updates inline make me happy.

>  Related documentation
>  ---------------------
>  
> diff --git a/commit-reach.c b/commit-reach.c
> index e0d9874f99..f79d0b64d6 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -133,17 +133,30 @@ static void paint_queue_put(struct paint_state *state,
>  
>  static struct commit *paint_queue_get(struct paint_state *state)
>  {
> -	struct commit *commit;
> +	struct commit *commit = prio_queue_get(&state->queue);
>  
> -	if (!state->p1_count && !state->p2_count &&
> -	    !state->pending_merge_bases)
> +	if (!commit)
>  		return NULL;
I see how the previous implementation has a termination condition
before calling prio_queue_get(), which is technically more
efficient. It does make this initial diff a bit more complicated
because we are moving the prio_queue_get() line.

If the introduction of the method in patch 5/7 looked like this:

+static struct commit *paint_queue_get(struct paint_state *state)
+{
+	struct commit *commit = prio_queue_get(&state->queue);
+
+	if (!commit)
+		return NULL;
+
+	if (!state->p1_count && !state->p2_count &&
+	    !state->pending_merge_bases)
+		return NULL;
+
+	commit->object.flags &= ~ENQUEUED;
+	paint_count_update(state, commit->object.flags, -1);
+	return commit;
+}

Then this diff would look cleaner.

(This is the nittiest of nitpicks so feel free to ignore if this
doesn't bother you at all.)

> -	commit = prio_queue_get(&state->queue);
> -	if (commit) {
> -		commit->object.flags &= ~ENQUEUED;
> -		paint_count_update(state, commit->object.flags, -1);
> +	commit->object.flags &= ~ENQUEUED;
> +
> +	if (!state->pending_merge_bases) {
> +		if (!state->p1_count && !state->p2_count)
> +			return NULL;
> +		/*
> +		 * Side exhaustion: a new merge-base can only form
> +		 * when both PARENT1-only and PARENT2-only commits
> +		 * remain in the queue. In the finite-generation
> +		 * region the queue is ordered topologically, so
> +		 * no future step can add paint to visited commits
> +		 * and an exhausted side cannot reappear.
> +		 */
> +		if ((!state->p1_count || !state->p2_count) &&
> +		    commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
> +			return NULL;
>  	}
> +
> +	paint_count_update(state, commit->object.flags, -1);
>  	return commit;
>  }

I like how the crux of this implementation is entirely within
paint_queue_get() now.

> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
> index c1109fb42f..03175befb3 100755
> --- a/t/t6600-test-reach.sh
> +++ b/t/t6600-test-reach.sh
> @@ -332,12 +332,12 @@ test_expect_success 'merge-base --all commit-walk steps' '
>  	cp commit-graph-full .git/objects/info/commit-graph &&
>  	GIT_TRACE2_EVENT="$(pwd)/trace-full.txt" \
>  		git merge-base --all commit-9-9 commit-9-1 >actual &&
> -	test_trace2_data paint_down_to_common steps 80 <trace-full.txt &&
> +	test_trace2_data paint_down_to_common steps 9 <trace-full.txt &&
>  
>  	cp commit-graph-half .git/objects/info/commit-graph &&
>  	GIT_TRACE2_EVENT="$(pwd)/trace-half.txt" \
>  		git merge-base --all commit-9-9 commit-9-1 >actual &&
> -	test_trace2_data paint_down_to_common steps 81 <trace-half.txt
> +	test_trace2_data paint_down_to_common steps 57 <trace-half.txt
>  '
I love to see these steps change. If you take my suggestion to
update more tests with these checks, then this diff will get bigger
(but in a deserved way).

Also, when I suggested that 'test_all_modes' creates the trace
files on our behalf, I forgot to mention that this specific test
that you added in patch 4/7 simplifies by running the merge-base
check under 'test_all_modes' and then checking the trace2 data
on the three well-known files afterwards.

Thanks,
-Stolee