Re: git bisect for reachable commits only

Guys,

thanks for discussion, I will try to reply in bulk here. First, assuming the common ancestor is GOOD based on the fact that some descendant given as GOOD is pretty bad idea. It may be, but may not be. In the git-flow like workflows new features (aka branches) are created from trunk (master/develop/...) sporadically, but later they will mutual merging. I would say more probably they have not common base, then have.

Second, I don't ask "create a new algorithm to find all transition from good/old to bad/new", not nesessary. If programmer feels something suspicious, he/she can create another bisect session with narrowed commit range.

Third, testing of any specific commit can be very expensive operation. In my case - shutdown servers/refresh dbs/clean/rebuild in eclipse/running servers/dropping browser cache/running app in browser/going through some pages/view UI. Some of steps of course are automated, but some not. Anyway I spend 5-10 min for every iteration. So knowing what commit is bad or good is very valuable, then I'm very interested to hunt the bug-introduced commit with minimal count of testing.

Scenario 4 (I will keep my previous mail numbering for possible later reference)
                 z1----z2---z3
                /     /      \
    G----x1----x2----/---x3---x4--B
          \         /   /
           y1--y2--y3--y4

This is the happy straight case with closed DAG (hehe, git for
scientists) between given G good and B bad commits.
Ideal bisect will check first the shortest way between G & B:
x1/x2/x3/x4. Let name first-bug commit we are really hunting H and
current first-bug candidate as h.
If h == x1 or x2 -> stop, found
If h == x3, bisect will try to test y2/y3/y4 path only
If h == x4, bisect will select shortest path z1/z2 (keeping in mind,
that x2 is already tested and is good)
  If h == z1 - found
  if h == z2 - looking in path y1/y2/y3

Scenario 5.
              v1-------v2
             /          \
        w1--/---w2-------w3---------w4--w5
       /   /   /                         \
      /   /   /            z1----z2---z3  \
     /   /   /            /     /      \   \
    C3--C2--C1--G--x1----x2----/---x3---x4--x5--x6--B
                    \         /   /
                     y1--y2--y3--y4

Unhappy case, we have side branches which may introduce bug behaviour,
we need to look it through to figure out why it was done, what problem
was solved for that and so on.
Let looking in shortest path x1-x6. If h == x1..x4 - happy use case of
scenario 4. If discover that h == x5, we are forgetting about z/y
paths, but first we looking for nearest common commit (C1). As far as
we agree that currently is not clear when the new feature was
introduced we need to explicit check commit C1 whether it contains a
feature we are hunting bug up.
if C1 is good then pretty possible bad transition was happend in w2-w5
commits. Else (C1 is bad) assume that there is no transition from good
to bad, then assume H == x5 (stop)
if C1 is good and h == w4/w5 => stop,
  else if h == w3, new roundtrip, forgetting about w1 commit(not
interesting), testing C2, if bad - stop H == w3, if good, v1/v2
commits are to test.
  else if h == w2, forgetting C2 testing, just testing C3. If bad,
stop, H == w3, if good, w1 to test.

Using this approach we can safe working with ever octopus merging (personally I'm not using, but why not)

Scenario 6.
                    z1---z2---z3
                   /    /       \
    C1--G--x1----x2----/------x3 |
     \      \         /         \|
      \      y1--y2--y3--y4--y5--y6--B
       \              \         /|
        \              w1--w2-w3 |
         \                      /
          v1------------------v2

Important note. Before start every side circuit based on common ancestor user should be explicitly warned, that this is not just ordinal intermediate bisect commit testing, but possible new round trips with new commit/steps counts For example, if current shortest path is x1-x6, bisect should say about only 6 commits (3 after bisect), not calculating commits in other paths. Reaching node decision, bisect will stay and prompt for testing new common ancestor with clear instructions what happens, if it will be good or bad, (new unchecked commits and new left bisect steps, in case good and stop or switch to other path in case of octopus).

I have another request to get git bisect more user-friendly, regarding rolling back last step or steps, if accidentally 'git bisect bad' or 'good' was wrong entered, but I think it worth for another thread.

Cheers, Oleg