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

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(+)

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(-)

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

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?

On Mon, 29 Jun 2026 at 19:50, Junio C Hamano <gitster@pobox.com> wrote:

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

Kristofer Karlsson <krka@spotify.com> writes:

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.

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

Excellent description of a good observation.

The solution is simple and straight-forward.

The flag is initialized to true but we drop it when generation order is not in effect, and the early exit requires the flag to be still true.

Let's mark it for 'next'.  Thanks.