Re: Git bisect does not find commit introducing the bug

[Alex Hoffman <spec@gal.ro>]

> 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