[PATCH v8 08/10] commit-reach: terminate merge-base walk when one paint side is exhausted

["Kristofer Karlsson via GitGitGadget" <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
ordered 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 optimization is gated by gen_ordered (which excludes v1
commit-graphs that use the date-ordering fallback) and by a
generation check against topo_ceiling. topo_ceiling is
GENERATION_NUMBER_INFINITY for v2 graphs and
GENERATION_NUMBER_V1_MAX for v1 graphs, so that saturated commits
are treated as unordered. Together these ensure the check only
fires in the ordered region where topological ordering holds.

The same topo_ceiling boundary is applied to the existing
single-result early exit so that all generation-dependent gates
express the same saturation-aware boundary consistently.

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       | 25 +++++++++++++++++--
 commit-reach.c                                | 20 ++++++++++++---
 t/t6600-test-reach.sh                         |  4 +--
 3 files changed, 41 insertions(+), 8 deletions(-)

diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index acf32bacd4..2393bb03b6 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -76,7 +76,11 @@ its child.
 Commits not in the commit-graph have generation INFINITY; v1
 commit-graphs saturate at V1_MAX. Both place commits in the
 unordered region. Any optimization that depends on generation
-ordering must account for this saturation boundary.
+ordering must account for this saturation boundary. The early
+exit gates compare against a topological ceiling --
+`GENERATION_NUMBER_V1_MAX` for v1 graphs and
+`GENERATION_NUMBER_INFINITY` for v2 graphs -- so that saturated
+commits are treated as unordered.
 
 With generation ordering, values in the unordered region exceed
 those in the ordered region. The walk may therefore transition
@@ -103,6 +107,9 @@ ends when one of the following conditions holds:
      a caller-supplied `min_generation` threshold.
   4. Single result: the caller only needs one merge base, one has
      been found, and the walk has entered the ordered region.
+  5. 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 ordered region.
 
 Stale entry condition
 ~~~~~~~~~~~~~~~~~~~~~
@@ -113,6 +120,16 @@ 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 ordered region,
+where paint flags are final at visit time; in the unordered region,
+a side that appears exhausted could reappear through late paint
+propagation.
+
 Generation cutoff
 ~~~~~~~~~~~~~~~~~
 Some callers (notably `remove_redundant()`) supply a `min_generation`
@@ -158,12 +175,16 @@ ordering via `compare_commits_by_commit_date`. Because commit
 dates are not monotonic (clock skew, rebases, etc.), the queue
 may visit commits out of topological order.
 
-This disables the optimization that depends on generation ordering:
+This disables the optimizations that depend on generation ordering:
 
   - *Single result*: the first merge-base candidate found may not
     be the shallowest, because a deeper ancestor with a higher
     commit date can be dequeued first.
 
+  - *Side exhaustion*: one paint side can appear to drain from the
+    queue while commits from that side are still waiting with lower
+    dates, causing premature termination.
+
 Related documentation
 ---------------------
 
diff --git a/commit-reach.c b/commit-reach.c
index 0f5ffec36e..7c5bbe00c3 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -90,6 +90,7 @@ struct paint_state {
 	size_t parent2_count;
 	size_t mb_candidate_count;
 	int gen_ordered;
+	timestamp_t topo_ceiling;
 };
 
 static void paint_count_update(struct paint_state *state,
@@ -150,9 +151,17 @@ static struct commit *paint_queue_get(struct paint_state *state)
 	 * still include this commit, so the last non-stale commit
 	 * sees a non-zero count and is returned for processing.
 	 */
-	if (!state->parent1_count && !state->parent2_count &&
-	    !state->mb_candidate_count)
-		return NULL;
+	if (!state->mb_candidate_count) {
+		/* only stale entries remain */
+		if (!state->parent1_count && !state->parent2_count)
+			return NULL;
+
+		/* one side is exhausted */
+		if ((!state->parent1_count || !state->parent2_count) &&
+		    state->gen_ordered &&
+		    commit_graph_generation(commit) < state->topo_ceiling)
+			return NULL;
+	}
 
 	paint_count_update(state, commit->object.flags, -1);
 	return commit;
@@ -180,6 +189,9 @@ static int paint_down_to_common(struct repository *r,
 	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 	struct commit_list **tail = result;
 
+	state.topo_ceiling = corrected_commit_dates_enabled(r)
+		? GENERATION_NUMBER_INFINITY
+		: GENERATION_NUMBER_V1_MAX;
 	if (!min_generation && !corrected_commit_dates_enabled(r)) {
 		state.queue.compare = compare_commits_by_commit_date;
 		state.gen_ordered = 0;
@@ -222,7 +234,7 @@ static int paint_down_to_common(struct repository *r,
 				 */
 				if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
 				    state.gen_ordered &&
-				    generation < GENERATION_NUMBER_INFINITY)
+				    generation < state.topo_ceiling)
 					break;
 			}
 			/* Mark parents of a found merge stale */
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 9f3a8f4743..23417897c8 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -297,7 +297,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' '
@@ -414,7 +414,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 81
 '
 
 test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
-- 
gitgitgadget