Re: [PATCH] commit-reach: fix in_merge_bases_many bug

[Srinidhi Kaushik <shrinidhi.kaushik@gmail.com>]

Hello,

On 10/02/2020 14:58, Derrick Stolee via GitGitGadget wrote:
> 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;

This is correct; good catch.

>  	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

Thanks Derrick and Johannes, for identifying the problem
and fixing the bug.

-- 
Srinidhi Kaushik