Re: Git bisect does not find commit introducing the bug

Below is a correction of the first proposed algorithm:

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