Re: Git bisect does not find commit introducing the bug

From: Christian Couder <christian.couder@gmail.com>
Date: Feb 18, 2017, 19:58 UTC
Message-ID: <CAP8UFD3ngMvVy2XLzYNn9OFbS+zQpWTW=pravpHhA-0PcDVhfg@mail.gmail.com>
In-Reply-To: <CAMX8fZW2y+iPRfSbXVcHufbM+CsqgekS_0WnCEJ++=njy_TvKg@mail.gmail.com>

On Sat, Feb 18, 2017 at 7:36 PM, Alex Hoffman <spec@gal.ro> wrote:

Show 17 quoted lines

>> But this is not how Git works. Git computes graph differences, i.e., it
>> subtracts from the commits reachable from v.bad those that are reachable
>> from v.good. This leaves more than just those on some path from v.good to
>> v.bad. And it should work this way. Consider this history:
>>
>> --o--o--o--G--X
>>    \           \
>>     x--x--x--x--X--B--
>>
>> When you find B bad and G good, than any one of the x or X may have
>> introduced the breakage, not just one of the X.
>>
>
> Thank you for clarifying how git bisect works. How did you find that
> out? Did you check the source code? If that is not documented in the
> man page may be it worth documenting it in order to avoid future
> confusion for other users.

At the end of the git-bisect man page (in the SEE ALSO section) there is a link to https://github.com/git/git/blob/master/Documentation/git-bisect-lk2009.txt which has a lot of details about how bisect works.

Show 10 quoted lines

> Let's consider your example with distinct names for nodes:
>
> --o1--o2--o3--G--X1
>     \                \
>      x1--x2--x3--x4--X1--B--
>
> It makes sense that git bisect is expecting a single transition, as
> this is a precondition for a binary search to work. My definition of
> "the transition" is a commit with at least one of its parents as a
> good version, but the commit itself a bad version.

What if a commit C has one good parent A and one bad parent B? Isn't it more likely that the first bad commit is B instead of C?

> I hope we agree
> that git bisect's mission is to search for this transition (as I
> suppose that most of people need such a functionality from git, if not
> exactly from git bisect).

The goal is to find the first bad commit, which is a commit that has only good parents.

> How could be x1 or x3 be the transition, if
> chances are that o1 is not a good version?

As o1 is an ancestor of G, then o1 is considered good by the bisect algorithm. If it was bad, it would means that there is a transition from bad to good between o1 and G. But when a good commit is an ancestor of the bad commit, git bisect makes the assumption that there is no transition from bad to good in the graph.

Show 11 quoted lines

> Of course it would make
> sense to me if bisect would check o1 whether good and only then to
> check also x1-x3, but this is not what git makes (at least not in my
> initial example).
>
> If you consider that git bisect's mission is different from finding
> the transition, could you please explain what exact commit git bisect
> is supposed to return (ideally with terms from the graph theory) and
> when it makes sense to return that? Because I do not see any sense in
> looking in the path x1-x3 without knowing that those commits may be a
> transition.

I hope it makes sense with the above explanations.

Show 9 quoted lines

>> Oh, IMO git bisect was well thought through. If it considered just paths
>> from good to bad, it would not given the correct answer. See the example
>> history above. Bisect authors would not have deemed that sufficiently good
>
> You definitely convinced me that git MUST search more than only in the
> paths between good and bad commits, as the good commit G does not have
> to be the first good commit (thank you for that). My problem/confusion
> is that it returns something that does not make sense to me, because
> it does not make sure it returns a transition.

git bisect makes some assumptions that are true most of the time, so in practice it works well most of the time.