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

From: Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
Date: Jun 26, 2026, 13:08 UTC
Message-ID: <f3572a8a89c74fad54a9e53be6f0e34daa2d50c2.1782479286.git.gitgitgadget@gmail.com>
In-Reply-To: <pull.2149.v3.git.1782479286.gitgitgadget@gmail.com>

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.

The check also waits for pending_merge_bases to reach zero, ensuring all merge-base candidates have been dequeued and recorded before exiting.

The INFINITY gate ensures correctness: commits without a commit-graph entry have GENERATION_NUMBER_INFINITY and are ordered by commit date, which is not topologically reliable. The optimization only fires once the walk enters the finite-generation region where ordering guarantees hold.

Widen the existing generation-monotonicity BUG assertion to fire unconditionally, not only when min_generation is set. The side-exhaustion optimization depends on correct generation ordering, so the assertion should always be active.

Step counts measured with trace2 on git.git with commit-graph:

  merge-base --all v2.0.0 v2.55.0-rc1:
    before: 72264 steps    after: 44589 steps

  merge-base --all v2.55.0-rc1 v2.55.0-rc1~5:
    before:   110 steps    after:     7 steps

Helped-by: Derrick Stolee <stolee@gmail.com>
Helped-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 .../technical/paint-down-to-common.adoc       | 17 +++++++++++++++++
 commit-reach.c                                | 19 +++++++++++++++----
 t/t6600-test-reach.sh                         |  4 ++--
 3 files changed, 34 insertions(+), 6 deletions(-)

diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index 0f4e1892a5..983dfcf233 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -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.
 
 Stale entry condition
 ~~~~~~~~~~~~~~~~~~~~~
@@ -104,6 +107,20 @@ existing candidates by proving one is an ancestor of another, but
 `remove_redundant()` handles that as a post-processing step, so it
 is safe to exit early.
 
+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.
+
 Related documentation
 ---------------------
 
diff --git a/commit-reach.c b/commit-reach.c
index ee0e0fdf6e..0248d6fedb 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -131,6 +131,10 @@ static void paint_queue_put(struct paint_state *state,
 	}
 }
 
+/*
+ * Dequeue the next commit for the paint walk, or return NULL when
+ * no more merge bases can be discovered.
+ */
 static struct commit *paint_queue_get(struct paint_state *state)
 {
 	struct commit *commit = prio_queue_get(&state->queue);
@@ -140,9 +144,16 @@ static struct commit *paint_queue_get(struct paint_state *state)
 
 	commit->object.flags &= ~ENQUEUED;
 
-	if (!state->p1_count && !state->p2_count &&
-	    !state->pending_merge_bases)
-		return NULL;
+	if (!state->pending_merge_bases) {
+		/* only stale entries remain */
+		if (!state->p1_count && !state->p2_count)
+			return NULL;
+
+		/* one side is exhausted */
+		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;
@@ -188,7 +199,7 @@ static int paint_down_to_common(struct repository *r,
 		timestamp_t generation = commit_graph_generation(commit);
 		steps++;
 
-		if (min_generation && generation > last_gen)
+		if (generation > last_gen)
 			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
 			    generation, last_gen,
 			    oid_to_hex(&commit->object.oid));
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 51f3d70492..6365007560 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -220,7 +220,7 @@ test_expect_success 'in_merge_bases_many:self' '
 	EOF
 	echo "in_merge_bases_many(A,X):1" >expect &&
 	test_all_modes in_merge_bases_many &&
-	test_paint_down_steps 45 2 25 3
+	test_paint_down_steps 45 1 25 1
 '
 
 test_expect_success 'is_descendant_of:hit' '
@@ -337,7 +337,7 @@ test_expect_success 'merge-base --all commit-walk steps' '
 	>input &&
 	git rev-parse commit-9-1 >expect &&
 	run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
-	test_paint_down_steps 81 80 81 81
+	test_paint_down_steps 81 9 57 10
 '
 
 test_expect_success 'reduce_heads' '

-- 
gitgitgadget