[PATCH] commit-reach: fix in_merge_bases_many bug

["Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com>]

From: Derrick Stolee <dstolee@microsoft.com>

Way back in f9b8908b (commit.c: use generation numbers for
in_merge_bases(), 2018-05-01), a heuristic was used to short-circuit
the in_merge_bases() walk. This works just fine as long as the
caller is checking only two commits, but when there are multiple,
there is a possibility that this heuristic is _very wrong_.

Some code moves since then has changed this method to
repo_in_merge_bases_many() inside commit-reach.c. The heuristic
computes the minimum generation number of the "reference" list, then
compares this number to the generation number of the "commit".

In a recent topic, a test was added that used in_merge_bases_many()
to test if a commit was reachable from a number of commits pulled
from a reflog. However, this highlighted the problem: if any of the
reference commits have a smaller generation number than the given
commit, then the walk is skipped _even if there exist some with
higher generation number_.

This heuristic is wrong! It must check the MAXIMUM generation number
of the reference commits, not the MINIMUM.

This highlights a testing gap. t6600-test-reach.sh covers many
methods in commit-reach.c, including in_merge_bases() and
get_merge_bases_many(), but since these methods either restrict to
two input commits or actually look for the full list of merge bases,
they don't check this heuristic!

Add a possible input to "test-tool reach" that tests
in_merge_bases_many() and add tests to t6600-test-reach.sh that
cover this heuristic. This includes cases for the reference commits
having generation above and below the generation of the input commit,
but also having maximum generation below the generation of the input
commit.

The fix itself is to swap min_generation with a max_generation in
repo_in_merge_bases_many().

Helped-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Reported-by: Srinidhi Kaushik <shrinidhi.kaushik@gmail.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
    Fix in_merge_bases_many() with commit-graphs
    
    Johannes alerted me to the difficulties Srinidhi was having with 
    in_merge_bases_many() and commit-graphs. Sorry that I hadn't seen that
    thread and the issues therein.
    
    After working with Johannes to investigate what was happening, we found
    a 2-year-old bug in the generation number checks!
    
    Thanks, -Stolee

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-739%2Fderrickstolee%2Fin-merge-bases-many-fix-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-739/derrickstolee/in-merge-bases-many-fix-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/739

 commit-reach.c        |  8 ++++----
 t/helper/test-reach.c |  2 ++
 t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++++
 3 files changed, 36 insertions(+), 4 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index efd5925cbb..50175b159e 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -321,7 +321,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,
 {
 	struct commit_list *bases;
 	int ret = 0, i;
-	uint32_t generation, min_generation = GENERATION_NUMBER_INFINITY;
+	uint32_t generation, max_generation = GENERATION_NUMBER_ZERO;
 
 	if (repo_parse_commit(r, commit))
 		return ret;
@@ -330,12 +330,12 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,
 			return ret;
 
 		generation = commit_graph_generation(reference[i]);
-		if (generation < min_generation)
-			min_generation = generation;
+		if (generation > max_generation)
+			max_generation = generation;
 	}
 
 	generation = commit_graph_generation(commit);
-	if (generation > min_generation)
+	if (generation > max_generation)
 		return ret;
 
 	bases = paint_down_to_common(r, commit,
diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
index 14a3655442..cda804ed79 100644
--- a/t/helper/test-reach.c
+++ b/t/helper/test-reach.c
@@ -107,6 +107,8 @@ int cmd__reach(int ac, const char **av)
 		printf("%s(A,B):%d\n", av[1], ref_newer(&oid_A, &oid_B));
 	else if (!strcmp(av[1], "in_merge_bases"))
 		printf("%s(A,B):%d\n", av[1], in_merge_bases(A, B));
+	else if (!strcmp(av[1], "in_merge_bases_many"))
+		printf("%s(A,X):%d\n", av[1], in_merge_bases_many(A, X_nr, X_array));
 	else if (!strcmp(av[1], "is_descendant_of"))
 		printf("%s(A,X):%d\n", av[1], repo_is_descendant_of(r, A, X));
 	else if (!strcmp(av[1], "get_merge_bases_many")) {
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 475564bee7..f807276337 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -110,6 +110,36 @@ test_expect_success 'in_merge_bases:miss' '
 	test_three_modes in_merge_bases
 '
 
+test_expect_success 'in_merge_bases_many:hit' '
+	cat >input <<-\EOF &&
+	A:commit-6-8
+	X:commit-6-9
+	X:commit-5-7
+	EOF
+	echo "in_merge_bases_many(A,X):1" >expect &&
+	test_three_modes in_merge_bases_many
+'
+
+test_expect_success 'in_merge_bases_many:miss' '
+	cat >input <<-\EOF &&
+	A:commit-6-8
+	X:commit-7-7
+	X:commit-8-6
+	EOF
+	echo "in_merge_bases_many(A,X):0" >expect &&
+	test_three_modes in_merge_bases_many
+'
+
+test_expect_success 'in_merge_bases_many:miss-heuristic' '
+	cat >input <<-\EOF &&
+	A:commit-6-8
+	X:commit-7-5
+	X:commit-6-6
+	EOF
+	echo "in_merge_bases_many(A,X):0" >expect &&
+	test_three_modes in_merge_bases_many
+'
+
 test_expect_success 'is_descendant_of:hit' '
 	cat >input <<-\EOF &&
 	A:commit-5-7

base-commit: 47ae905ffb98cc4d4fd90083da6bc8dab55d9ecc
-- 
gitgitgadget