Git bisect does not find commit introducing the bug

Git bisect does not find commit introducing the bug

[Alex Hoffman]

Hi there,

According to the documentation "git bisect" is designed "to find the
commit that introduced a bug" .
I have found a situation in which it does not returns the commit I expected.
In order to reproduce the problem:

1. mkdir test; cd test;
git clone https://github.com/entbugger/git-bisect-issue.git
cd git-bisect-issue

The tag "v.bad" is one bad version and tag "v.good" is the first good
version. A good version is one having the line "FEATURE2" in
file1.txt, which was introduced in "v.good".

2. Copy test scripts to another folder to make sure they are not
overridden by 'git bisect'
cp *.sh ../
cd ..
./search-bug-git.sh

3. Run ./search-bug-git.sh to search for the commit introducing the
bug. It finds that the commit 04c6f4b9ed with the message "Feature 1"
is the first one introducing the bug.

First of all this is confusing, as this commit cannot be reached
starting from "v.good". Then I expected the commit with the message
"Introduce bug" to be returned by 'git bisect', as it is the first
commit  between "v.good" and "v.bad" that does not contain the line
"FEATURE2" in file1.txt, which is what I understand by the commit
"that introduced a bug" (cited from the manpage of git bisect).

Thanks for looking to this,

Best regards,
VG

Re: Git bisect does not find commit introducing the bug

[Stephan Beyer]

Hi,

On 02/17/2017 11:29 PM, Alex Hoffman wrote:
> According to the documentation "git bisect" is designed "to find the
> commit that introduced a bug" .
> I have found a situation in which it does not returns the commit I expected.
> In order to reproduce the problem:

For the others who are too lazy to clone your repo and run the scripts,
the history is like that (read from bottom to top) and I marked the
commit found by git bisect and the on you expected:

*   7a9e952 (bisect bad) <BAD>
|\
| *   671cec2 <BAD> <--- expected
| |\
| * | 04c6f4b <BAD> <--- found
* | |   3915157 <GOOD>
|\ \ \
| | |/
| |/|
| * | f4154e9 (bisect good) <GOOD>
| * | 85855bf <BAD>
| |/
* | f1a36f5 <BAD>
|/
* 1b7fb88 <BAD>

The <BAD> and <GOOD> markers are set by your definition of what good and
what bad commits are.

> First of all this is confusing, as this commit cannot be reached
> starting from "v.good".

Hm, IMHO it shows that your example is pretty artificial (although you
might have come across it in a real-world scenario): you introduced a
new feature in f4154e9 (and it worked) and you broke that feature by
making the merge 671cec2. However, the feature (that broke in 671cec2)
did not even exist in 04c6f4b; so a test on the feature would not fail
(leading to "bisect bad" as in the example), it would not exist (leading
to "bisect skip").

And if we are not talking about passing or failing tests but about
crashing, bisect finds the right thing: f4154e9 was not crashing, but
04c6f4b is crashing. Yes, it's not the commit that introduced the crash
(which would be the first commit in the repo) but it's the first
crashing commit after the one marked as good.

So I'd consider this a feature or rather correct behavior, not a bug.

In other words: bisect assumes that your repo is usually in a good state
and you have a commit that changes it to a bad state. In your case you
have a repo that is in a bad state and you have a commit that switches
it to a good state and later you merge a bad-state branch and you have a
bad state again. It is not made for that use-case, I think.

Cheers
  Stephan

Re: Git bisect does not find commit introducing the bug

[Johannes Sixt]

Am 18.02.2017 um 00:21 schrieb Stephan Beyer:
> On 02/17/2017 11:29 PM, Alex Hoffman wrote:
> *   7a9e952 (bisect bad) <BAD>
> |\
> | *   671cec2 <BAD> <--- expected
> | |\
> | * | 04c6f4b <BAD> <--- found
> * | |   3915157 <GOOD>
> |\ \ \
> | | |/
> | |/|
> | * | f4154e9 (bisect good) <GOOD>
> | * | 85855bf <BAD>
> | |/
> * | f1a36f5 <BAD>
> |/
> * 1b7fb88 <BAD>
>
> The <BAD> and <GOOD> markers are set by your definition of what good and
> what bad commits are.
>
> [...]
> In other words: bisect assumes that your repo is usually in a good state
> and you have a commit that changes it to a bad state. In your case you
> have a repo that is in a bad state and you have a commit that switches
> it to a good state and later you merge a bad-state branch and you have a
> bad state again. It is not made for that use-case, I think.

Correct. The assumption of bisection is that there is only one 
transition between GOOD and BAD. By violating that assumption, anything 
can happen.

-- Hannes

Re: Git bisect does not find commit introducing the bug

[Alex Hoffman]

>> First of all this is confusing, as this commit cannot be reached
>> starting from "v.good".

> Hm, IMHO it shows that your example is pretty artificial (although you
> might have come across it in a real-world scenario): you introduced a
> new feature in f4154e9 (and it worked) and you broke that feature by
> making the merge 671cec2. However, the feature (that broke in 671cec2)
> did not even exist in 04c6f4b; so a test on the feature would not fail
> (leading to "bisect bad" as in the example), it would not exist (leading
> to "bisect skip").

No one commented the fact, that I find this very confusing. Don't you
find this confusing? I will underline, that 'git bisect good v.good'
will fail if the commit 'v.good' is not a parent of the bad commit,
meaning there MUST be at least a path between 'v.good' and 'v.bad',
thus I would expect it looks on this path ONLY. Beside that, this is
what I understand by 'binary search' (to search on this commit path).
You might find this example artificial, but I doubt git is/was
intentionally designed to work with  'natural' examples only (no
matter how you define 'natural' and 'artificial').



>> In other words: bisect assumes that your repo is usually in a good state
>> and you have a commit that changes it to a bad state. In your case you
>> have a repo that is in a bad state and you have a commit that switches
>> it to a good state and later you merge a bad-state branch and you have a
>> bad state again. It is not made for that use-case, I think.

> Correct. The assumption of bisection is that there is only one transition between GOOD and BAD. By violating that assumption, anything can happen.

I did not find that in the manpage or did I miss it? Why would someone
assume that the commit graph looks in a certain way? I assume, that
'git bisect' was not thought through and that it considers the first
directed path between v.good and v.bad, instead of all paths (in my
example graph there are two such paths). I will also underline that
git bisect was designed to work with multiple good commits and one bad
commit (also multiple paths), but probably NOT with multiple paths
between the same pair of good and bad commits.

VG


2017-02-18 10:12 GMT+01:00 Johannes Sixt <j6t@kdbg.org>:
> Am 18.02.2017 um 00:21 schrieb Stephan Beyer:
>>
>> On 02/17/2017 11:29 PM, Alex Hoffman wrote:
>> *   7a9e952 (bisect bad) <BAD>
>> |\
>> | *   671cec2 <BAD> <--- expected
>> | |\
>> | * | 04c6f4b <BAD> <--- found
>> * | |   3915157 <GOOD>
>> |\ \ \
>> | | |/
>> | |/|
>> | * | f4154e9 (bisect good) <GOOD>
>> | * | 85855bf <BAD>
>> | |/
>> * | f1a36f5 <BAD>
>> |/
>> * 1b7fb88 <BAD>
>>
>> The <BAD> and <GOOD> markers are set by your definition of what good and
>> what bad commits are.
>>
>> [...]
>> In other words: bisect assumes that your repo is usually in a good state
>> and you have a commit that changes it to a bad state. In your case you
>> have a repo that is in a bad state and you have a commit that switches
>> it to a good state and later you merge a bad-state branch and you have a
>> bad state again. It is not made for that use-case, I think.
>
>
> Correct. The assumption of bisection is that there is only one transition
> between GOOD and BAD. By violating that assumption, anything can happen.
>
> -- Hannes
>

Re: Git bisect does not find commit introducing the bug

[Johannes Sixt]

Am 18.02.2017 um 12:15 schrieb Alex Hoffman:
> No one commented the fact, that I find this very confusing. Don't you
> find this confusing? I will underline, that 'git bisect good v.good'
> will fail if the commit 'v.good' is not a parent of the bad commit,
> meaning there MUST be at least a path between 'v.good' and 'v.bad',
> thus I would expect it looks on this path ONLY. Beside that, this is
> what I understand by 'binary search' (to search on this commit path).

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.

>> Correct. The assumption of bisection is that there is only one
>> transition between GOOD and BAD. By violating that assumption,
>> anything  can happen.
>
> I did not find that in the manpage or did I miss it? Why would someone
> assume that the commit graph looks in a certain way?

There is no restriction in the commit graph. The only restriction, 
actually assumption, is that there is *one* transition from good to bad 
and no transition from bad to good. Otherwise, bisection cannot work.

> I assume, that
> 'git bisect' was not thought through and that it considers the first
> directed path between v.good and v.bad, instead of all paths (in my
> example graph there are two such paths). I will also underline that
> git bisect was designed to work with multiple good commits and one bad
> commit (also multiple paths), but probably NOT with multiple paths
> between the same pair of good and bad commits.

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 ;)

-- Hannes

Re: Git bisect does not find commit introducing the bug

[Alex Hoffman]

> 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.

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. 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). How could be x1 or x3 be the transition, if
chances are that o1 is not a good version? 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.


> 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.

VG

PS: thank you for continuing this discussion.

Re: Git bisect does not find commit introducing the bug

[Christian Couder]

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

> 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.

> 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.

>> 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.

Re: Git bisect does not find commit introducing the bug

[Philip Oakley]

From: "Alex Hoffman" <spec@gal.ro>
>> 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.

Any suggestions for improving the documentation are always worthwhile. As 
someone who asked, what extra info would have helped?

Even beetter if it looks like a patch ;-)

>
> 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. 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). How could be x1 or x3 be the transition, if
> chances are that o1 is not a good version? 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.
>
>
>> 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.
>
> VG
>
> PS: thank you for continuing this discussion.
>
--
Philip 

Re: Git bisect does not find commit introducing the bug

[Hilco Wijbenga]

On 18 February 2017 at 10:36, Alex Hoffman <spec@gal.ro> wrote:
> 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.

If multiple transitions from GOOD to BAD happen, then I don't see how
binary search is useful/possible. The same is true for a simple list
of numbers, say, 1 5 6 2 3 4. You can't use binary search here because
you can't "throw away" all numbers to the left (or right) of your
pivot. Or am I missing your point?

Re: Git bisect does not find commit introducing the bug

[Johannes Sixt]

Am 18.02.2017 um 19:36 schrieb Alex Hoffman:
> Let's consider your example with distinct names for nodes:
>
> --o1--o2--o3--G--X1
>     \                \
>      x1--x2--x3--x4--X2--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.

But that is not the definition of transition that lets you pin-point the 
breaking commit precisly. Assume x3 is the commit introducing the 
breakage in the graph above. Even though you only know initially that G 
is good and B is bad, would you not prefer to find x3 instead of X2? As 
Christian said, a transition is when a commit is bad and all its parents 
are good, and this definition lets you find x3.

> 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). How could be x1 or x3 be the transition, if
> chances are that o1 is not a good version?

By declaring G as good, it is implied that o1 is also good. If it is in 
fact bad, the assumptions of git bisect are violated (because there 
would be a transition from bad to good at o2, o3, or G), and anything 
can happen.

> 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.

And I do not see a reason why git bisect should not look at those 
commits. If x3 is the commit that broke my program, I do prefer to be 
pointed at x3 rather than X2.

-- Hannes

Re: Git bisect does not find commit introducing the bug

[Alex Hoffman]

> 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.
>

Thanks for pointing out the SEE ALSO section. I think it makes sense
to include/describe the entire algorithm in the man page itself,
although I am not sure whether the graphs would be always correctly
visually represented in the man page format.

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

OK, bisect's mission is more exact than I thought, which is good. M

> 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.

The assumption that there is no transition from bad to good in the
graph did not hold in my example and it does not hold when a feature
was recently introduced and gets broken relative shortly afterwards.
But I consider it is easy to change the algorithm not to assume, but
rather to check it.

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

Whatever the definition of "most of the time" everyone might have, I
think there is room for improvement. Below I am trying to make a small
change to the current algorithm in order to deal with the assumption
that sometimes does not hold (e.g in my example), by explicitly
validating the check.

> --o1--o2--o3--G--X1
>     \                \
>      x1--x2--x3--x4--X2--B--
>       \              /
>        y1--y2--y3

Step 1a. (Unchanged) keep only the commits that:

        a) are ancestor of the "bad" commit (including the "bad" commit itself),
        b) are not ancestor of a "good" commit (excluding the "good" commits).

The following graph results:
      x1--x2--x3--x4--X2--B--
       \              /
        y1--y2--y3

Step 1b. (New) Mark all root commits of the resulting graph (i.e
commits without parents) as unconfirmed (unconfirmed=node that has
only bad parents). Remove all root commits that user already confirmed
(e.g if user already marked its parent as good right before starting
bisect run). For every unconfirmed root commit check if it has any
good parents. In the example above check whether x1 has good parents.
     If the current root element has any parents and none of them is
good, we can delete all paths from it until to the next commit that
has a parent in the ancestors of GOOD. In the example above to delete
the path x1-x3 and x1-y3. Also add new resulting root commits to the
list of unconfirmed commits (commit x4).
     Otherwise mark it as confirmed.

Step2. Continue the existing algorithm.


If this improvement works (i.e you do not find any bugs in it and it
is feasible to implement, which seems to me) the following would be
its advantages:
1. An assumption less, as we explicitly check the assumption.
2. It might be quicker, because we delete parts of graph that cannot
contain transitions.
3. It returns more exact results.

VG

Re: Git bisect does not find commit introducing the bug

[Alex Hoffman]

Below is a correction of the first proposed algorithm:

>--o1--o2--o3--G --X1
>    \                \
>     x1--x2--x3--x4--X2--B--
>      \              /
>       y1--y2--y3
>
Step 1a. (Unchanged) keep only the commits that:

        a) are ancestor of the "bad" commit (including the "bad" commit itself),
        b) are not ancestor of a "good" commit (excluding the "good" commits).

The following graph results:
      x1--x2--x3--x4--X2--B--
       \              /
        y1--y2--y3

Step 1b. (New) Mark all commits of the resulting graph as unconfirmed
(unconfirmed=node without good ancestors).
Mark as confirmed all descendants of commits that user marked
explicitly as good (e.g if user already marked its parent/grand
parent/... as good right before starting bisect run).
Step 1c. From all unconfirmed root commits build a set SET_GOOD of
those with any good parents in the original graph (root commit =
commit without parents in the resulting graph) and one SET_BAD for
commits with only BAD parents. To build a set means to ask explicitly
the user (or the command passed in git bisect run) whether any of its
parents is good. In the example above find out whether x1 has any good
parents or no parent at all and if so add it to SET_GOOD, otherwise to
SET_BAD.
Mark as confirmed each commit in SET_GOOD and all its descendants.
For every commit in SET_BAD delete all paths from it until to the next
confirmed commit. In the example above if x1 is in SET_BAD delete the
path x1-x3 and x1-y3. If any new root commits result (commit x4), redo
step 1c with them.


Step2. Continue the existing algorithm.

If this improvement works (i.e you do not find any bugs in it and it
is feasible to implement, which seems to me) the following would be
its advantages:
1. An assumption less, as we explicitly check the assumption.
2. It might be quicker, because we delete parts of graph that cannot
contain transitions.
3. It returns more exact results.

VG

Re: Git bisect does not find commit introducing the bug

[Christian Couder]

On Sun, Feb 19, 2017 at 12:32 PM, Alex Hoffman <spec@gal.ro> wrote:
>> 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.
>
> Thanks for pointing out the SEE ALSO section. I think it makes sense
> to include/describe the entire algorithm in the man page itself,
> although I am not sure whether the graphs would be always correctly
> visually represented in the man page format.

It would possibly be very long to describe the entire algorithm, as it
can be quite complex in some cases and it is difficult to understand
without graphs. Maybe we could describe it, or some parts of it, in a
separate document and provide links at different places in the man
page.
Anyway feel free to send patches.

>> The goal is to find the first bad commit, which is a commit that has
>> only good parents.
>
> OK, bisect's mission is more exact than I thought, which is good. M

Good that you seem to agree with this goal.

>> 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.
>
> The assumption that there is no transition from bad to good in the
> graph did not hold in my example and it does not hold when a feature
> was recently introduced and gets broken relative shortly afterwards.
> But I consider it is easy to change the algorithm not to assume, but
> rather to check it.

I don't think the default algorithm will change soon, but there have
been discussions for a long time about adding options to use different
algorithms.

For example people have been discussing a "--first-parent" option for
many years as well as recently. It would bisect only along the first
parents of the involved commits, and it could help find the merge
commit that introduced a bug in the mainline.

>> git bisect makes some assumptions that are true most of the time, so
>> in practice it works well most of the time.
>
> Whatever the definition of "most of the time" everyone might have, I
> think there is room for improvement.

So feel free to send patches that would implement an option with the
improvements you want.

> Below I am trying to make a small
> change to the current algorithm in order to deal with the assumption
> that sometimes does not hold (e.g in my example), by explicitly
> validating the check.
>
>> --o1--o2--o3--G--X1
>>     \                \
>>      x1--x2--x3--x4--X2--B--
>>       \              /
>>        y1--y2--y3
>
> Step 1a. (Unchanged) keep only the commits that:
>
>         a) are ancestor of the "bad" commit (including the "bad" commit itself),
>         b) are not ancestor of a "good" commit (excluding the "good" commits).
>
> The following graph results:
>       x1--x2--x3--x4--X2--B--
>        \              /
>         y1--y2--y3

I would say that the above graph is missing X1.

> Step 1b. (New) Mark all root commits of the resulting graph (i.e
> commits without parents) as unconfirmed (unconfirmed=node that has
> only bad parents). Remove all root commits that user already confirmed
> (e.g if user already marked its parent as good right before starting
> bisect run). For every unconfirmed root commit check if it has any
> good parents. In the example above check whether x1 has good parents.

I think I understand the above...

>      If the current root element has any parents and none of them is
> good, we can delete all paths from it until to the next commit that
> has a parent in the ancestors of GOOD. In the example above to delete
> the path x1-x3 and x1-y3. Also add new resulting root commits to the
> list of unconfirmed commits (commit x4).
>      Otherwise mark it as confirmed.

... but I don't understand the logic of the above. If the root element
has a bad parent, then it means that the "first bad commit" is either
the bad parent or one of its ancestors, so it is not logical to delete
it. In your example if x1 has one bad parent, this bad parent and its
ancestors should be included in the search of the first bad commit.

Otherwise the goal is not any more to find the first bad commit.

PS: I saw that you have just sent another version of the algorithm,
but I don't want to take a look at it right now. Anyway I am keeping
my above comments as they might still be useful.

> Step2. Continue the existing algorithm.
>
>
> If this improvement works (i.e you do not find any bugs in it and it
> is feasible to implement, which seems to me)

As you describe it, I don't think it is compatible with the goal of
finding the first bad commit.
Also there are many things that are feasible to implement, but it
doesn't mean that someone will soon make the effort to implement them
in a way that looks good enough to be deemed worth merging into the
current code base.

> the following would be
> its advantages:
> 1. An assumption less, as we explicitly check the assumption.

Checking can be costly. If the probability that the check will fail is
very low, while the cost of checking is high, it is less costly on
average to not check.

> 2. It might be quicker, because we delete parts of graph that cannot
> contain transitions.

I don't agree that it's a good idea to delete what you suggest above.
Or if you think that the goal should not be to find the "first bad
commit" in the above case, then you should explain what the goal
should be.

> 3. It returns more exact results.

Yeah, but checking every commit related to the good and bad commits
would also return more exact results. (This can probably be done using
`git rebase --exec ...` by the way.) One could even print a nice graph
with all the good and bad commits. The problem is that it would not be
efficient. If git bisect makes some assumptions, it is because they
have been deemed reasonable and they have worked well in practice.
It's also because the goal of git bisect is to be efficient, otherwise
there would be no point in using a binary search algorithm in the
first place.

Re: Git bisect does not find commit introducing the bug

[Johannes Sixt]

Am 19.02.2017 um 12:32 schrieb Alex Hoffman:
> The assumption that there is no transition from bad to good in the
> graph did not hold in my example and it does not hold when a feature
> was recently introduced and gets broken relative shortly afterwards.

Then you must adjust your definition of "good": All commits that do not 
have the feature, yet, are "good": since they do not have the feature in 
the first place, they cannot have the breakage that you found in the 
feature.

That is exactly the situation in your original example! But you 
constructed the condition of goodness in such a simplistic way 
(depending on the presence of a string), that it was impossible to 
distinguish between "does not have the feature at all" and "has the 
feature, but it is broken".

-- Hannes

Re: Git bisect does not find commit introducing the bug

[Alex Hoffman]

> Then you must adjust your definition of "good": All commits that do not have
> the feature, yet, are "good": since they do not have the feature in the
> first place, they cannot have the breakage that you found in the feature.
>
> That is exactly the situation in your original example! But you constructed
> the condition of goodness in such a simplistic way (depending on the
> presence of a string), that it was impossible to distinguish between "does
> not have the feature at all" and "has the feature, but it is broken".

Johannes, thank you for correctly identifying the error in my logic.
Indeed I was using the term 'bad' also for the commit without the
feature. In order to find the commit introducing the bug in my example
a new state is needed, which would make 'git bisect' a bit more
complicated than the user 'most of the time' probably needs. Or do you
think, it would make sense to ask the user for this state (if e.g 'git
bisect' would be started with a new parameter)?

Re: Git bisect does not find commit introducing the bug

[Jacob Keller]

On Sun, Feb 19, 2017 at 11:05 AM, Alex Hoffman <spec@gal.ro> wrote:
>> Then you must adjust your definition of "good": All commits that do not have
>> the feature, yet, are "good": since they do not have the feature in the
>> first place, they cannot have the breakage that you found in the feature.
>>
>> That is exactly the situation in your original example! But you constructed
>> the condition of goodness in such a simplistic way (depending on the
>> presence of a string), that it was impossible to distinguish between "does
>> not have the feature at all" and "has the feature, but it is broken".
>
> Johannes, thank you for correctly identifying the error in my logic.
> Indeed I was using the term 'bad' also for the commit without the
> feature. In order to find the commit introducing the bug in my example
> a new state is needed, which would make 'git bisect' a bit more
> complicated than the user 'most of the time' probably needs. Or do you
> think, it would make sense to ask the user for this state (if e.g 'git
> bisect' would be started with a new parameter)?

If a commit doesn't have the feature, then it is by definition, not
containing a broken feature, and you can simply use the "good" state.
There is no need for a different state. If you can't test the commit
because it's broken in some other way, you can use "git bisect skip"
but that isn't what you want in this case.

Thanks,
Jake

Re: Git bisect does not find commit introducing the bug

[Oleg Taranenko]

>>> Then you must adjust your definition of "good": All commits that do not have
>>> the feature, yet, are "good": since they do not have the feature in the
>>> first place, they cannot have the breakage that you found in the feature.
>>>
>>> That is exactly the situation in your original example! But you constructed
>>> the condition of goodness in such a simplistic way (depending on the
>>> presence of a string), that it was impossible to distinguish between "does
>>> not have the feature at all" and "has the feature, but it is broken".
>>
>> Johannes, thank you for correctly identifying the error in my logic.
>> Indeed I was using the term 'bad' also for the commit without the
>> feature. In order to find the commit introducing the bug in my example
>> a new state is needed, which would make 'git bisect' a bit more
>> complicated than the user 'most of the time' probably needs. Or do you
>> think, it would make sense to ask the user for this state (if e.g 'git
>> bisect' would be started with a new parameter)?


> If a commit doesn't have the feature, then it is by definition, not
> containing a broken feature, and you can simply use the "good" state.
> There is no need for a different state. If you can't test the commit
> because it's broken in some other way, you can use "git bisect skip"
> but that isn't what you want in this case.

Commits missing feature == 'good' commit is a very confusing one.

Looks like in real life it happens much often, then git developers can
imagine. For multi-branch/multi-feature workflow it's pretty easy not
to recognize whether it is missing or not developed yet, especially on
retrospective view where cherry-picking/squashing/merging is being
used. My experience shows most annoying bugs are generating after a
heavy merge (evil merge) with conflicts resolutions, where developer
is not involved in the knowing what happens on counterpart changes.
Then feature can be disappeared after it was worked & tested in its
own branches.

@Alex, I'm pretty interesting in fixing this weird bisect behaviour as
well, as far as I struggled on it last summer and continue struggling
so far :) If you want we can join to your efforts on fixing.

Cheers, Oleg

Re: Git bisect does not find commit introducing the bug

[Junio C Hamano]

Christian Couder <christian.couder@gmail.com> writes:

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

I think we need to clarify the documentation and ask you to stop
using such fuzzy phrases like "assumptions" and "most of the time"
;-).

For bisection to work, "git bisect" requires a very simple thing,
which is that your history is bisectable wrt one particular "trait",
i.e. what you are interested in (e.g. the trait may be "the commit
has this feature in a broken form").

What does it mean for a history to be "bisectable", then?

A bisectable history has commits with the "trait" and commits
without the "trait".  Given any commit with the "trait", all commits
that are decendant of such commit must have the "trait".  Also given
any commit without the "trait", all commits that are ancestor of
such a commit must not have the "trait".

And your goal is to find one commit with the "trait" whose direct
parent commits all lack the "trait".

If and only if you can formulate your problem into the above form,
"git bisect" can help you by not requiring you to check each and
every commit in the history.

Depending on the way you define the "trait", your history may not be
bisectable, but by formulating the "trait" carefully, many such
history can be made bisectable.  In the "Recently some commit broke
feature X.  Before then the feature used to work.  In an ancient
past, the feature did not even exist" example, if you set "trying to
use feature X breaks" as the "trait", your history is not bisectable
unless you ignore the ancient part that did not even have the
feature.  If you restate your "trait" to "feature X does not exist
in a broken form", however, the history becomes bisectable.

Historically, we called commits with "trait" BAD and others GOOD,
because bisection was used primarily to hunt for bugs.  It may be
easier to understand if the user thinks of commits without "trait"
as OLD (i.e. commits in the older part of the history are not yet
contaminated), and commits with "trait" as NEW (i.e. at some point,
there is an event to introduce the "trait" and newer part of the
history is contaminated by that event ever since).

Re: Git bisect does not find commit introducing the bug

[Jakub Narębski]

W dniu 20.02.2017 o 08:38, Oleg Taranenko pisze:

>>>> Then you must adjust your definition of "good": All commits that do not have
>>>> the feature, yet, are "good": since they do not have the feature in the
>>>> first place, they cannot have the breakage that you found in the feature.
>>>>
>>>> That is exactly the situation in your original example! But you constructed
>>>> the condition of goodness in such a simplistic way (depending on the
>>>> presence of a string), that it was impossible to distinguish between "does
>>>> not have the feature at all" and "has the feature, but it is broken".
>>>
>>> Johannes, thank you for correctly identifying the error in my logic.
>>> Indeed I was using the term 'bad' also for the commit without the
>>> feature. In order to find the commit introducing the bug in my example
>>> a new state is needed, which would make 'git bisect' a bit more
>>> complicated than the user 'most of the time' probably needs. Or do you
>>> think, it would make sense to ask the user for this state (if e.g 'git
>>> bisect' would be started with a new parameter)?
> 
>> If a commit doesn't have the feature, then it is by definition, not
>> containing a broken feature, and you can simply use the "good" state.
>> There is no need for a different state. If you can't test the commit
>> because it's broken in some other way, you can use "git bisect skip"
>> but that isn't what you want in this case.
> 
> Commits missing feature == 'good' commit is a very confusing one.

Nowadays you can change the names for 'old' and 'new' with
`git bisect terms`.  HTH.
 
> Looks like in real life it happens much often, then git developers can
> imagine. For multi-branch/multi-feature workflow it's pretty easy not
> to recognize whether it is missing or not developed yet, especially on
> retrospective view where cherry-picking/squashing/merging is being
> used. My experience shows most annoying bugs are generating after a
> heavy merge (evil merge) with conflicts resolutions, where developer
> is not involved in the knowing what happens on counterpart changes.
> Then feature can be disappeared after it was worked & tested in its
> own branches.

Good to know about this problem.

> @Alex, I'm pretty interesting in fixing this weird bisect behaviour as
> well, as far as I struggled on it last summer and continue struggling
> so far :) If you want we can join to your efforts on fixing.

Anyway, I don't think it is feasible to weaken the assumption that there
is only one transition from 'old' ('good') to 'new' ('bad'); this is
what allows O(log(N)) operations.  See bisection method of root finding,
that is finding zeros of a continuous function.

Best,
-- 
Jakub Narębski

Re: Git bisect does not find commit introducing the bug

[Oleg Taranenko]

> Anyway, I don't think it is feasible to weaken the assumption that there
> is only one transition from 'old' ('good') to 'new' ('bad'); this is
> what allows O(log(N)) operations.  See bisection method of root finding,
> that is finding zeros of a continuous function.

I don't intended to change default behaviour of git bisect, I can
estimate what drawback it could bring.
I'd rather implement something like

git bisect start --bisect-strategy=missing-feature

by default current state is being used.

git config value would be also useful.

Oleg

Re: Git bisect does not find commit introducing the bug

[Alex Hoffman]

I see two different problems each with a different assumption (see the
definition of "bisectable" in the email of Junio C Hamano):

1. (Current) Assume the entire history graph is bisectable. DO: Search
where in the entire graph the first 'trait'/transition occurs.
2. (New) Assume only the graph between one good commit and one bad
commit is bisectable. DO: Search where the first transition occurs in
the graph between these two commits.

It seems that the real world needs a solution also for the second
problem (example if the good commit is the FIRST good commit of a
feature or if the good commit is not the first good commit, but you
definitely know, that it broke first somewhere in between the good and
bad commit).

I find the way to go as Oleg proposed is gittish enough (with a new
parameter --strategy). Beside I would underline that also the second
problem is a bisect problem, just for another graph, thus it makes
perfect sense to extend 'git bisect' for this.

Does that look reasonably?

Re: Git bisect does not find commit introducing the bug

[Jakub Narębski]

W dniu 20.02.2017 o 21:31, Alex Hoffman pisze:
> I see two different problems each with a different assumption (see the
> definition of "bisectable" in the email of Junio C Hamano):
> 
> 1. (Current) Assume the entire history graph is bisectable. DO: Search
> where in the entire graph the first 'trait'/transition occurs.
>
> 2. (New) Assume only the graph between one good commit and one bad
> commit is bisectable. DO: Search where the first transition occurs in
> the graph between these two commits.

If `git bisect` is/would be affected by `git log` history-related options
then this is what `--strict-ancestor` option gives/would give.

-- 
Jakub Narębski

Re: Git bisect does not find commit introducing the bug

[Alex Hoffman]

> If `git bisect` is/would be affected by `git log` history-related options
> then this is what `--strict-ancestor` option gives/would give.

Exactly my thoughts. All that needs to be changed in the 2nd problem
is the graph where to search.

But first we must agree about the usefulness of the 2nd problem. Any
thoughts/comments/votes for/against?

Re: Git bisect does not find commit introducing the bug

[Philip Oakley]

From: "Jakub Narębski" <jnareb@gmail.com>
>W dniu 20.02.2017 o 21:31, Alex Hoffman pisze:
>> I see two different problems each with a different assumption (see the
>> definition of "bisectable" in the email of Junio C Hamano):
>>
>> 1. (Current) Assume the entire history graph is bisectable. DO: Search
>> where in the entire graph the first 'trait'/transition occurs.
>>
>> 2. (New) Assume only the graph between one good commit and one bad
>> commit is bisectable. DO: Search where the first transition occurs in
>> the graph between these two commits.
>
> If `git bisect` is/would be affected by `git log` history-related options
> then this is what `--strict-ancestor` option gives/would give.
>
isn't that spelt `--ancestry-path` ?
(--ancestry-path has it's own issues such as needing an --first-parent-show 
option, but that's possibly a by the by)
--
Philip 

Re: Git bisect does not find commit introducing the bug

[Alex Hoffman]

> isn't that spelt `--ancestry-path` ?
> (--ancestry-path has it's own issues such as needing an --first-parent-show
> option, but that's possibly a by the by)

Indeed it is spelled `--ancestry-path`. And interestingly enough you
may use it multiple times with the wanted effect in our case (e.g when
the user has multiple good commit and a single bad commit before
running the bisect itself). Also it is `--first-parent` (not
`--first-parent-show`), but I do not understand why do we need this
option? What kind of issues does `--ancestry-path` have?

Best regards,
VG

Re: Git bisect does not find commit introducing the bug

[Philip Oakley]

From: "Alex Hoffman" <spec@gal.ro>
>> isn't that spelt `--ancestry-path` ?
>> (--ancestry-path has it's own issues such as needing 
>> an --first-parent-show
>> option, but that's possibly a by the by)
>
> Indeed it is spelled `--ancestry-path`. And interestingly enough you
> may use it multiple times with the wanted effect in our case (e.g when
> the user has multiple good commit and a single bad commit before
> running the bisect itself).

> Also it is `--first-parent` (not `--first-parent-show`),

My spelling was deliberate ;-)

If you use the currently coded --first-parent with a properly relevant 
commit for --ancestry-path then you get nothing. The purpose of 
ancestry-path is to find the ancestry chain that deviates from being a 
first-parent traversal [1], but the first-parent want to hold the walk to 
just the first parent chain - a contradiction.

Adding the -show at the end is my attempt to indicate that it is for the 
second aspect, that of selecting which commits to show/use.

I had an initial discussion back at [2], but failed then too.

> but I do not understand why do we need this
> option? What kind of issues does `--ancestry-path` have?
>
> Best regards,
> VG
>
--
Philip

[1] \git\Documentation\technical\api-revision-walking.txt ["two 
diff_options, one for path limiting, another for output"]
[2] 
https://public-inbox.org/git/2FA1998250474E76A386B82AD635E56A@PhilipOakley/