Hello, On 10/02/2020 14:58, Derrick Stolee via GitGitGadget wrote: > From: Derrick Stolee <dstolee@xxxxxxxxxxxxx> > > 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@xxxxxx> > Reported-by: Srinidhi Kaushik <shrinidhi.kaushik@xxxxxxxxx> > Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx> > --- > 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
