{"thread":{"id":"65885","subject":"[PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph","startedAt":"2026-06-29T13:19:24Z","lastAt":"2026-07-08T17:24:35Z","messageCount":7,"participants":["Kristofer Karlsson via GitGitGadget","Junio C Hamano","Kristofer Karlsson"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"546665","messageId":"pull.2162.git.1782739162.gitgitgadget@gmail.com","threadId":"65885","inReplyTo":null,"subject":"[PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-29T13:19:19Z","receivedAt":"2026-06-29T13:19:24Z","isPatch":true,"body":"Fixes a bug introduced by 93e5b1680e (commit-reach: early exit\npaint_down_to_common for single merge-base, 2025-04-10) where git merge-base\ncan return the wrong result.\n\nThe bug requires all of the following to trigger:\n\n 1. A v1 commit graph (topological levels only, no corrected commit dates).\n Generation v2 with corrected commit dates has been the default since\n 2021, so only repos that have not rewritten their commit graph in over\n four years would be affected.\n 2. git merge-base without --all (the common case, but --all is unaffected\n because it disables the early exit).\n 3. A topology with clock skew: the correct merge base has a lower committer\n date than one of its ancestors that is also a common ancestor. With date\n ordering, the deeper ancestor pops first and the early exit fires before\n the correct result is found.\n\nThis two-patch series:\n\n 1. Adds a test demonstrating the bug (clock-skew topology where the correct\n merge base has a lower date than its ancestor)\n 2. Fixes it by tracking whether the queue is generation-ordered and gating\n the early exit on that flag\n\nKristofer Karlsson (2):\n t6600: add test for merge-base early exit with clock skew\n commit-reach: guard !FIND_ALL early exit with generation ordering\n check\n\n commit-reach.c | 10 +++++++---\n t/t6600-test-reach.sh | 41 +++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 48 insertions(+), 3 deletions(-)\n\n\nbase-commit: 9aa172cd1f113276d360d4e48937dc95ef46b780\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2162%2Fspkrka%2Ffind-all-fix-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2162/spkrka/find-all-fix-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2162\n-- \ngitgitgadget\n"},{"id":"546666","messageId":"c10ff61519d34a942037af26919e45b669071115.1782739162.git.gitgitgadget@gmail.com","threadId":"65885","inReplyTo":"pull.2162.git.1782739162.gitgitgadget@gmail.com","subject":"[PATCH 1/2] t6600: add test for merge-base early exit with clock skew","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-29T13:19:20Z","receivedAt":"2026-06-29T13:19:26Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nAdd a topology where the correct merge base (M2) has a lower\ncommitter date than its ancestor (M1) due to clock skew. With a\nv1 commit graph (topological levels only, no corrected commit\ndates), paint_down_to_common() falls back to commit-date ordering.\nIn that mode, M1 pops before M2, acquires both paint sides, and\nthe !FIND_ALL early exit fires -- returning the wrong merge base.\n\nMark the test as test_expect_failure to document the bug; the next\ncommit will fix it.\n\nSigned-off-by: Kristofer Karlsson \n---\n t/t6600-test-reach.sh | 41 +++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 41 insertions(+)\n\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex b5b314e570..1090104220 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -49,6 +49,42 @@ test_expect_success 'setup' '\n \t\t\tgit tag -a -m \"$x-$i\" tag-$x-$i commit-$x-$i || return 1\n \t\tdone\n \tdone &&\n+\t# Build a topology with clock skew to test the !FIND_ALL early\n+\t# exit in paint_down_to_common(). M2 is the correct merge base\n+\t# of P1 and P2, but its ancestor M1 has a higher committer date\n+\t# due to clock skew. With date-only ordering (v1 commit graph\n+\t# without corrected commit dates), M1 pops from the queue first,\n+\t# gets both paint sides, and the early exit fires before M2 is\n+\t# ever visited.\n+\t#\n+\t# P1 P2 @7000\n+\t# | / \\\n+\t# A B D @6000\n+\t# / \\ | |\n+\t# | M2--+ | @2000 (correct merge base)\n+\t# \\ | |\n+\t# M1--------+ @5000 (clock skew: date > M2)\n+\t# |\n+\t# root @1000\n+\t#\n+\tgit checkout --orphan skew-orphan &&\n+\tskew_tree=$(git mktree expect &&\n+\tmerge_base_all_modes skew-P1 skew-P2\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"546667","messageId":"ba3f2bb6e8463eb2f101ebf5c7d8d83d353731a2.1782739162.git.gitgitgadget@gmail.com","threadId":"65885","inReplyTo":"pull.2162.git.1782739162.gitgitgadget@gmail.com","subject":"[PATCH 2/2] commit-reach: guard !FIND_ALL early exit with generation ordering check","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-29T13:19:21Z","receivedAt":"2026-06-29T13:19:27Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nWhen paint_down_to_common() falls back to commit-date ordering (for\nv1 commit graphs without corrected commit dates), the !FIND_ALL early\nexit incorrectly fires. The exit assumes the queue is generation-\nordered, so the first RESULT commit found must be the shallowest.\nWith date ordering this is not guaranteed: a closer merge base with\na lower committer date (clock skew) may still be in the queue behind\ndeeper commits.\n\nAdd a gen_ordered flag that is cleared when the date fallback fires,\nand require it for the early exit.\n\nUpdate the test from the previous commit to test_expect_success.\n\nSigned-off-by: Kristofer Karlsson \n---\n commit-reach.c | 10 +++++++---\n t/t6600-test-reach.sh | 2 +-\n 2 files changed, 8 insertions(+), 4 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 5df471a313..708798a39b 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -108,11 +108,14 @@ static int paint_down_to_common(struct repository *r,\n \t\t{ compare_commits_by_gen_then_commit_date }\n \t};\n \tint i;\n+\tint gen_ordered = 1;\n \ttimestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n \tstruct commit_list **tail = result;\n \n-\tif (!min_generation && !corrected_commit_dates_enabled(r))\n+\tif (!min_generation && !corrected_commit_dates_enabled(r)) {\n \t\tqueue.pq.compare = compare_commits_by_commit_date;\n+\t\tgen_ordered = 0;\n+\t}\n \n \tone->object.flags |= PARENT1;\n \tif (!n) {\n@@ -147,11 +150,12 @@ static int paint_down_to_common(struct repository *r,\n \t\t\t\tcommit->object.flags |= RESULT;\n \t\t\t\ttail = commit_list_append(commit, tail);\n \t\t\t\t/*\n-\t\t\t\t * The queue is generation-ordered; no\n-\t\t\t\t * remaining common ancestor can be a\n+\t\t\t\t * When the queue is generation-ordered,\n+\t\t\t\t * no remaining common ancestor can be a\n \t\t\t\t * descendant of this one.\n \t\t\t\t */\n \t\t\t\tif (!(mb_flags & MERGE_BASE_FIND_ALL) &&\n+\t\t\t\t gen_ordered &&\n \t\t\t\t generation < GENERATION_NUMBER_INFINITY)\n \t\t\t\t\tbreak;\n \t\t\t}\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex 1090104220..0ff41381ff 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -1003,7 +1003,7 @@ test_expect_success 'merge-base without --all is one of --all results' '\n \tgrep -F -f single all\n '\n \n-test_expect_failure 'merge-base without --all, clock skew, v1 commit-graph' '\n+test_expect_success 'merge-base without --all, clock skew, v1 commit-graph' '\n \tgit rev-parse skew-M2 >expect &&\n \tmerge_base_all_modes skew-P1 skew-P2\n '\n-- \ngitgitgadget\n"},{"id":"546689","messageId":"xmqqldbxw81i.fsf@gitster.g","threadId":"65885","inReplyTo":"pull.2162.git.1782739162.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-29T17:50:01Z","receivedAt":"2026-06-29T17:50:07Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" \nwrites:\n\n> Fixes a bug introduced by 93e5b1680e (commit-reach: early exit\n> paint_down_to_common for single merge-base, 2025-04-10) where git merge-base\n> can return the wrong result.\n>\n> The bug requires all of the following to trigger:\n>\n> 1. A v1 commit graph (topological levels only, no corrected commit dates).\n> Generation v2 with corrected commit dates has been the default since\n> 2021, so only repos that have not rewritten their commit graph in over\n> four years would be affected.\n> 2. git merge-base without --all (the common case, but --all is unaffected\n> because it disables the early exit).\n> 3. A topology with clock skew: the correct merge base has a lower committer\n> date than one of its ancestors that is also a common ancestor. With date\n> ordering, the deeper ancestor pops first and the early exit fires before\n> the correct result is found.\n>\n> This two-patch series:\n>\n> 1. Adds a test demonstrating the bug (clock-skew topology where the correct\n> merge base has a lower date than its ancestor)\n> 2. Fixes it by tracking whether the queue is generation-ordered and gating\n> the early exit on that flag\n\nWhere should this new \"gen_ordered\" flag go in the world with\nkk/merge-base-exhaustion topic merged in? Does it also belong\nto the paint_state struct or can it be on-stack independent variable\nto the function?\n\n"},{"id":"546696","messageId":"CAL71e4P4GbYYv1LdarAbeodm06q841wj4gdGpn0QYADQjOB5gw@mail.gmail.com","threadId":"65885","inReplyTo":"xmqqldbxw81i.fsf@gitster.g","subject":"Re: [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-29T18:27:38Z","receivedAt":"2026-06-29T18:27:50Z","isPatch":true,"body":"On Mon, 29 Jun 2026 at 19:50, Junio C Hamano wrote:\n>\n> Where should this new \"gen_ordered\" flag go in the world with\n> kk/merge-base-exhaustion topic merged in? Does it also belong\n> to the paint_state struct or can it be on-stack independent variable\n> to the function?\n\nI don't think kk/merge-base-exhaustion is ready to be merged as-is\nand you are right that these two topics would conflict.\nI will need to reroll v5 and exactly how/when I do that\ndepends on what we do here.\n\nI wanted to quickly share this small patch as a bugfix\nsince the related code is already merged. I think the bug\nitself might be a very unlikely edge case but I can't really be\nsure.\n\nMy preference would be to merge this as-is, and then I can rework\nv5 of kk/merge-base-exhaustion on top of it later - it will\nadd some delay but I don't want to rush it since it's a non-trivial\nchange.\n\nThe other option is to drop this topic if the risk is deemed low\nenough, and then I will rework v5 to either apply a similar\ngen_ordered flag or eliminate that different ordering entirely -\nI see that as a good long-term goal that simplifies the code while\nretaining or improving the performance.\n\nI realize the timing is terrible, I wish I had spotted this a week\nago instead of right at the 2.55 finalization period.\n\nThanks,\nKristofer\n"},{"id":"546697","messageId":"xmqqa4sdw55v.fsf@gitster.g","threadId":"65885","inReplyTo":"CAL71e4P4GbYYv1LdarAbeodm06q841wj4gdGpn0QYADQjOB5gw@mail.gmail.com","subject":"Re: [PATCH 0/2] commit-reach: fix !FIND_ALL early exit with v1 commit graph","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-29T18:52:12Z","receivedAt":"2026-06-29T18:52:15Z","isPatch":true,"body":"Kristofer Karlsson writes:\n\n> My preference would be to merge this as-is, and then I can rework\n> v5 of kk/merge-base-exhaustion on top of it later - it will\n> add some delay but I don't want to rush it since it's a non-trivial\n> change.\n\nThat sounds very sensible. Let's do that.\n\nI've taken a look at both of these two patches and found the\nsolution quite sensible, but I'd prefer a second set of eyes\nto confirm.\n\nThanks.\n"},{"id":"547513","messageId":"xmqqjyr5v1gu.fsf@gitster.g","threadId":"65885","inReplyTo":"ba3f2bb6e8463eb2f101ebf5c7d8d83d353731a2.1782739162.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/2] commit-reach: guard !FIND_ALL early exit with generation ordering check","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-07-08T17:24:33Z","receivedAt":"2026-07-08T17:24:35Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" \nwrites:\n\n> From: Kristofer Karlsson \n>\n> When paint_down_to_common() falls back to commit-date ordering (for\n> v1 commit graphs without corrected commit dates), the !FIND_ALL early\n> exit incorrectly fires. The exit assumes the queue is generation-\n> ordered, so the first RESULT commit found must be the shallowest.\n> With date ordering this is not guaranteed: a closer merge base with\n> a lower committer date (clock skew) may still be in the queue behind\n> deeper commits.\n\nExcellent description of a good observation.\n\n> Add a gen_ordered flag that is cleared when the date fallback fires,\n> and require it for the early exit.\n\nThe solution is simple and straight-forward.\n\nThe flag is initialized to true but we drop it when generation order\nis not in effect, and the early exit requires the flag to be still\ntrue.\n\n> Update the test from the previous commit to test_expect_success.\n>\n> Signed-off-by: Kristofer Karlsson \n> ---\n\nLet's mark it for 'next'. Thanks.\n\n> commit-reach.c | 10 +++++++---\n> t/t6600-test-reach.sh | 2 +-\n> 2 files changed, 8 insertions(+), 4 deletions(-)\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 5df471a313..708798a39b 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -108,11 +108,14 @@ static int paint_down_to_common(struct repository *r,\n> \t\t{ compare_commits_by_gen_then_commit_date }\n> \t};\n> \tint i;\n> +\tint gen_ordered = 1;\n> \ttimestamp_t last_gen = GENERATION_NUMBER_INFINITY;\n> \tstruct commit_list **tail = result;\n> \n> -\tif (!min_generation && !corrected_commit_dates_enabled(r))\n> +\tif (!min_generation && !corrected_commit_dates_enabled(r)) {\n> \t\tqueue.pq.compare = compare_commits_by_commit_date;\n> +\t\tgen_ordered = 0;\n> +\t}\n> \n> \tone->object.flags |= PARENT1;\n> \tif (!n) {\n> @@ -147,11 +150,12 @@ static int paint_down_to_common(struct repository *r,\n> \t\t\t\tcommit->object.flags |= RESULT;\n> \t\t\t\ttail = commit_list_append(commit, tail);\n> \t\t\t\t/*\n> -\t\t\t\t * The queue is generation-ordered; no\n> -\t\t\t\t * remaining common ancestor can be a\n> +\t\t\t\t * When the queue is generation-ordered,\n> +\t\t\t\t * no remaining common ancestor can be a\n> \t\t\t\t * descendant of this one.\n> \t\t\t\t */\n> \t\t\t\tif (!(mb_flags & MERGE_BASE_FIND_ALL) &&\n> +\t\t\t\t gen_ordered &&\n> \t\t\t\t generation < GENERATION_NUMBER_INFINITY)\n> \t\t\t\t\tbreak;\n> \t\t\t}\n> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\n> index 1090104220..0ff41381ff 100755\n> --- a/t/t6600-test-reach.sh\n> +++ b/t/t6600-test-reach.sh\n> @@ -1003,7 +1003,7 @@ test_expect_success 'merge-base without --all is one of --all results' '\n> \tgrep -F -f single all\n> '\n> \n> -test_expect_failure 'merge-base without --all, clock skew, v1 commit-graph' '\n> +test_expect_success 'merge-base without --all, clock skew, v1 commit-graph' '\n> \tgit rev-parse skew-M2 >expect &&\n> \tmerge_base_all_modes skew-P1 skew-P2\n> '\n"}]}