bisect: handle search for bad to good transitions

bisect: handle search for bad to good transitions

Automatically detect whether we're looking for a bad to good
transition rather than the usual good to bad transition by detecting
when badrev is inside the good set and flipping good/bad.

--- a/mercurial/commands.py	Mon Dec 31 18:20:34 2007 -0600
+++ b/mercurial/commands.py	Mon Dec 31 18:20:34 2007 -0600
@@ -258,11 +258,6 @@
     working directory as bad or good and bisect will either update to
     another candidate changeset or announce that it has found the bad
     revision.
-
-    Note: bisect expects bad revisions to be descendants of good
-    revisions. If you are looking for the point at which a problem was
-    fixed, then make the problem-free state \"bad\" and the
-    problematic state \"good.\"
     """
     # backward compatibility
     if rev in "good bad reset init".split():
@@ -317,9 +312,9 @@
         return
 
     # actually bisect
-    node, changesets = hbisect.bisect(repo.changelog, state)
+    node, changesets, good = hbisect.bisect(repo.changelog, state)
     if changesets == 0:
-        ui.write(_("The first bad revision is:\n"))
+        ui.write(_("The first %s revision is:\n") % (good and "good" or "bad"))
         displayer = cmdutil.show_changeset(ui, repo, {})
         displayer.show(changenode=node)
     elif node is not None:

--- a/mercurial/hbisect.py	Mon Dec 31 18:20:34 2007 -0600
+++ b/mercurial/hbisect.py	Mon Dec 31 18:20:34 2007 -0600
@@ -12,25 +12,36 @@
 
 def bisect(changelog, state):
     clparents = changelog.parentrevs
-    # only the earliest bad revision matters
-    badrev = min([changelog.rev(n) for n in state['bad']])
-    bad = changelog.node(badrev)
     skip = dict.fromkeys([changelog.rev(n) for n in state['skip']])
 
-    # build ancestors array
-    ancestors = [[]] * (changelog.count() + 1) # an extra for [-1]
+    def buildancestors(bad, good):
+        # only the earliest bad revision matters
+        badrev = min([changelog.rev(n) for n in bad])
+        goodrevs = [changelog.rev(n) for n in good]
+        # build ancestors array
+        ancestors = [[]] * (changelog.count() + 1) # an extra for [-1]
 
-    # clear good revs from array
-    for node in state['good']:
-        ancestors[changelog.rev(node)] = None
-    for rev in xrange(changelog.count(), -1, -1):
-        if ancestors[rev] is None:
-            for prev in clparents(rev):
-                ancestors[prev] = None
+        # clear good revs from array
+        for node in goodrevs:
+            ancestors[node] = None
+        for rev in xrange(changelog.count(), -1, -1):
+            if ancestors[rev] is None:
+                for prev in clparents(rev):
+                    ancestors[prev] = None
 
-    if ancestors[badrev] is None:
+        if ancestors[badrev] is None:
+            return None, None
+        return badrev, ancestors
+
+    good = 0
+    badrev, ancestors = buildancestors(state['bad'], state['good'])
+    if not ancestors: # looking for bad to good transition?
+        good = 1
+        badrev, ancestors = buildancestors(state['good'], state['bad'])
+    if not ancestors: # now we're confused
         raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
                          % (badrev, hg.short(bad)))
+    bad = changelog.node(badrev)
 
     # build children dict
     children = {}
@@ -52,7 +63,7 @@
     # have we narrowed it down to one entry?
     tot = len(candidates)
     if tot == 1:
-        return (bad, 0)
+        return (bad, 0, good)
     perfect = tot / 2
 
     # find the best node to test
@@ -91,4 +102,4 @@
     assert best_rev is not None
     best_node = changelog.node(best_rev)
 
-    return (best_node, tot)
+    return (best_node, tot, good)

--- a/tests/test-bisect	Mon Dec 31 18:20:34 2007 -0600
+++ b/tests/test-bisect	Mon Dec 31 18:20:34 2007 -0600
@@ -31,3 +31,13 @@
 hg bisect -g
 hg bisect -b
 hg bisect -g
+
+echo % bisect reverse test
+hg bisect -r
+hg bisect -b null
+hg bisect -g tip
+hg bisect -g
+hg bisect -g
+hg bisect -g
+hg bisect -b
+hg bisect -g

--- a/tests/test-bisect.out	Mon Dec 31 18:20:34 2007 -0600
+++ b/tests/test-bisect.out	Mon Dec 31 18:20:34 2007 -0600
@@ -214,3 +214,20 @@
 date:        Thu Jan 01 00:00:29 1970 +0000
 summary:     msg 29
 
+% bisect reverse test
+Testing changeset 15:e7fa0811edb0 (32 changesets remaining, ~5 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Testing changeset 7:03750880c6b5 (16 changesets remaining, ~4 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Testing changeset 3:b53bea5e2fcb (8 changesets remaining, ~3 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Testing changeset 1:5cd978ea5149 (4 changesets remaining, ~2 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Testing changeset 2:db07c04beaca (2 changesets remaining, ~1 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+The first good revision is:
+changeset:   2:db07c04beaca
+user:        test
+date:        Thu Jan 01 00:00:02 1970 +0000
+summary:     msg 2
+