[PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph

[PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph

[Kristofer Karlsson via GitGitGadget]

Fixes a bug introduced by 93e5b1680e (commit-reach: early exit
paint_down_to_common for single merge-base, 2025-04-10) where git merge-base
can return the wrong result.

The bug requires all of the following to trigger:

 1. A v1 commit graph (topological levels only, no corrected commit dates).
    Generation v2 with corrected commit dates has been the default since
    2021, so only repos that have not rewritten their commit graph in over
    four years would be affected.
 2. git merge-base without --all (the common case, but --all is unaffected
    because it disables the early exit).
 3. A topology with clock skew: the correct merge base has a lower committer
    date than one of its ancestors that is also a common ancestor. With date
    ordering, the deeper ancestor pops first and the early exit fires before
    the correct result is found.

This two-patch series:

 1. Adds a test demonstrating the bug (clock-skew topology where the correct
    merge base has a lower date than its ancestor)
 2. Fixes it by tracking whether the queue is generation-ordered and gating
    the early exit on that flag

Kristofer Karlsson (2):
  t6600: add test for merge-base early exit with clock skew
  commit-reach: guard !FIND_ALL early exit with generation ordering
    check

 commit-reach.c        | 10 +++++++---
 t/t6600-test-reach.sh | 41 +++++++++++++++++++++++++++++++++++++++++
 2 files changed, 48 insertions(+), 3 deletions(-)


base-commit: 9aa172cd1f113276d360d4e48937dc95ef46b780
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2162%2Fspkrka%2Ffind-all-fix-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2162/spkrka/find-all-fix-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2162
-- 
gitgitgadget

[PATCH 1/2] t6600: add test for merge-base early exit with clock skew

[Kristofer Karlsson via GitGitGadget]

From: Kristofer Karlsson <krka@spotify.com>

Add a topology where the correct merge base (M2) has a lower
committer date than its ancestor (M1) due to clock skew.  With a
v1 commit graph (topological levels only, no corrected commit
dates), paint_down_to_common() falls back to commit-date ordering.
In that mode, M1 pops before M2, acquires both paint sides, and
the !FIND_ALL early exit fires -- returning the wrong merge base.

Mark the test as test_expect_failure to document the bug; the next
commit will fix it.

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 t/t6600-test-reach.sh | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index b5b314e570..1090104220 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -49,6 +49,42 @@ test_expect_success 'setup' '
 			git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i || return 1
 		done
 	done &&
+	# Build a topology with clock skew to test the !FIND_ALL early
+	# exit in paint_down_to_common().  M2 is the correct merge base
+	# of P1 and P2, but its ancestor M1 has a higher committer date
+	# due to clock skew.  With date-only ordering (v1 commit graph
+	# without corrected commit dates), M1 pops from the queue first,
+	# gets both paint sides, and the early exit fires before M2 is
+	# ever visited.
+	#
+	#        P1     P2          @7000
+	#        |     /  \
+	#        A    B    D        @6000
+	#       / \   |    |
+	#      |  M2--+    |        @2000 (correct merge base)
+	#       \ |        |
+	#        M1--------+        @5000 (clock skew: date > M2)
+	#        |
+	#       root                @1000
+	#
+	git checkout --orphan skew-orphan &&
+	skew_tree=$(git mktree </dev/null) &&
+	skew_commit () {
+		GIT_COMMITTER_DATE="@$1 +0000" GIT_AUTHOR_DATE="@$1 +0000" \
+			git commit-tree -m "$2" "$skew_tree" $3 $4 $5 $6
+	} &&
+	skew_root=$(skew_commit 1000 root) &&
+	skew_M1=$(skew_commit 5000 M1 -p "$skew_root") &&
+	skew_M2=$(skew_commit 2000 M2 -p "$skew_M1") &&
+	skew_A=$(skew_commit 6000 A -p "$skew_M1" -p "$skew_M2") &&
+	skew_B=$(skew_commit 6000 B -p "$skew_M2") &&
+	skew_D=$(skew_commit 6000 D -p "$skew_M1") &&
+	skew_P1=$(skew_commit 7000 P1 -p "$skew_A") &&
+	skew_P2=$(skew_commit 7000 P2 -p "$skew_B" -p "$skew_D") &&
+	git branch -f skew-P1 "$skew_P1" &&
+	git branch -f skew-P2 "$skew_P2" &&
+	git tag skew-M2 "$skew_M2" &&
+
 	git commit-graph write --reachable &&
 	mv .git/objects/info/commit-graph commit-graph-full &&
 	chmod u+w commit-graph-full &&
@@ -967,4 +1003,9 @@ test_expect_success 'merge-base without --all is one of --all results' '
 	grep -F -f single all
 '
 
+test_expect_failure 'merge-base without --all, clock skew, v1 commit-graph' '
+	git rev-parse skew-M2 >expect &&
+	merge_base_all_modes skew-P1 skew-P2
+'
+
 test_done
-- 
gitgitgadget

[PATCH 2/2] commit-reach: guard !FIND_ALL early exit with generation ordering check

[Kristofer Karlsson via GitGitGadget]

From: Kristofer Karlsson <krka@spotify.com>

When paint_down_to_common() falls back to commit-date ordering (for
v1 commit graphs without corrected commit dates), the !FIND_ALL early
exit incorrectly fires.  The exit assumes the queue is generation-
ordered, so the first RESULT commit found must be the shallowest.
With date ordering this is not guaranteed: a closer merge base with
a lower committer date (clock skew) may still be in the queue behind
deeper commits.

Add a gen_ordered flag that is cleared when the date fallback fires,
and require it for the early exit.

Update the test from the previous commit to test_expect_success.

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 commit-reach.c        | 10 +++++++---
 t/t6600-test-reach.sh |  2 +-
 2 files changed, 8 insertions(+), 4 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 5df471a313..708798a39b 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -108,11 +108,14 @@ static int paint_down_to_common(struct repository *r,
 		{ compare_commits_by_gen_then_commit_date }
 	};
 	int i;
+	int gen_ordered = 1;
 	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 	struct commit_list **tail = result;
 
-	if (!min_generation && !corrected_commit_dates_enabled(r))
+	if (!min_generation && !corrected_commit_dates_enabled(r)) {
 		queue.pq.compare = compare_commits_by_commit_date;
+		gen_ordered = 0;
+	}
 
 	one->object.flags |= PARENT1;
 	if (!n) {
@@ -147,11 +150,12 @@ static int paint_down_to_common(struct repository *r,
 				commit->object.flags |= RESULT;
 				tail = commit_list_append(commit, tail);
 				/*
-				 * The queue is generation-ordered; no
-				 * remaining common ancestor can be a
+				 * When the queue is generation-ordered,
+				 * no remaining common ancestor can be a
 				 * descendant of this one.
 				 */
 				if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
+				    gen_ordered &&
 				    generation < GENERATION_NUMBER_INFINITY)
 					break;
 			}
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 1090104220..0ff41381ff 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -1003,7 +1003,7 @@ test_expect_success 'merge-base without --all is one of --all results' '
 	grep -F -f single all
 '
 
-test_expect_failure 'merge-base without --all, clock skew, v1 commit-graph' '
+test_expect_success 'merge-base without --all, clock skew, v1 commit-graph' '
 	git rev-parse skew-M2 >expect &&
 	merge_base_all_modes skew-P1 skew-P2
 '
-- 
gitgitgadget

Re: [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph

[Junio C Hamano]

"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>
writes:

> Fixes a bug introduced by 93e5b1680e (commit-reach: early exit
> paint_down_to_common for single merge-base, 2025-04-10) where git merge-base
> can return the wrong result.
>
> The bug requires all of the following to trigger:
>
>  1. A v1 commit graph (topological levels only, no corrected commit dates).
>     Generation v2 with corrected commit dates has been the default since
>     2021, so only repos that have not rewritten their commit graph in over
>     four years would be affected.
>  2. git merge-base without --all (the common case, but --all is unaffected
>     because it disables the early exit).
>  3. A topology with clock skew: the correct merge base has a lower committer
>     date than one of its ancestors that is also a common ancestor. With date
>     ordering, the deeper ancestor pops first and the early exit fires before
>     the correct result is found.
>
> This two-patch series:
>
>  1. Adds a test demonstrating the bug (clock-skew topology where the correct
>     merge base has a lower date than its ancestor)
>  2. Fixes it by tracking whether the queue is generation-ordered and gating
>     the early exit on that flag

Where should this new "gen_ordered" flag go in the world with
kk/merge-base-exhaustion topic merged in?  Does it also belong
to the paint_state struct or can it be on-stack independent variable
to the function?

Re: [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph

[Kristofer Karlsson]

On Mon, 29 Jun 2026 at 19:50, Junio C Hamano <gitster@pobox.com> wrote:
>
> Where should this new "gen_ordered" flag go in the world with
> kk/merge-base-exhaustion topic merged in?  Does it also belong
> to the paint_state struct or can it be on-stack independent variable
> to the function?

I don't think kk/merge-base-exhaustion is ready to be merged as-is
and you are right that these two topics would conflict.
I will need to reroll v5 and exactly how/when I do that
depends on what we do here.

I wanted to quickly share this small patch as a bugfix
since the related code is already merged. I think the bug
itself might be a very unlikely edge case but I can't really be
sure.

My preference would be to merge this as-is, and then I can rework
v5 of kk/merge-base-exhaustion on top of it later - it will
add some delay but I don't want to rush it since it's a non-trivial
change.

The other option is to drop this topic if the risk is deemed low
enough, and then I will rework v5 to either apply a similar
gen_ordered flag or eliminate that different ordering entirely -
I see that as a good long-term goal that simplifies the code while
retaining or improving the performance.

I realize the timing is terrible, I wish I had spotted this a week
ago instead of right at the 2.55 finalization period.

Thanks,
Kristofer

Re: [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph

[Junio C Hamano]

Kristofer Karlsson <krka@spotify.com> writes:

> My preference would be to merge this as-is, and then I can rework
> v5 of kk/merge-base-exhaustion on top of it later - it will
> add some delay but I don't want to rush it since it's a non-trivial
> change.

That sounds very sensible.  Let's do that.

I've taken a look at both of these two patches and found the
solution quite sensible, but I'd prefer a second set of eyes
to confirm.

Thanks.