Add support for multiple possible bisect results (issue1228, issue1182)

Add support for multiple possible bisect results (issue1228, issue1182)

The real reason for both issue is that bisect can not handle cases where there
are multiple possibilities for the result.

Example (from issue1228):
rev 0 -> good
rev 1 -> skipped
rev 2 -> skipped
rev 3 -> skipped
rev 4 -> bad

Note that this patch does not only fix the reported Assertion Error but also
the problem of a non converging bisect:

hg init
for i in `seq 3`; do echo $i > $i; hg add $i; hg ci -m$i; done
hg bisect -b 2
hg bisect -g 0
hg bisect -s

From this state on, you can:
 a) mark as bad forever (non converging!)
 b) mark as good to get an inconsistent state
 c) skip for the Assertion Error

Minor description and code edits by pmezard.

--- a/mercurial/commands.py	Tue Jul 15 18:10:37 2008 -0500
+++ b/mercurial/commands.py	Sat Aug 02 22:10:10 2008 +0200
@@ -324,12 +324,23 @@
         return
 
     # actually bisect
-    node, changesets, good = hbisect.bisect(repo.changelog, state)
+    nodes, changesets, good = hbisect.bisect(repo.changelog, state)
     if changesets == 0:
-        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:
+        transition = (good and "good" or "bad")
+        if len(nodes) == 1:
+            # narrowed it down to a single revision
+            ui.write(_("The first %s revision is:\n") % transition)
+            displayer.show(changenode=nodes[0])
+        else:
+            # multiple possible revisions
+            ui.write(_("Due to skipped revisions, the first "
+                       "%s revision could be any of:\n") % transition)
+            for n in nodes:
+                displayer.show(changenode=n)
+    else:
+        assert len(nodes) == 1 # only a single node can be tested next
+        node = nodes[0]
         # compute the approximate number of remaining tests
         tests, size = 0, 2
         while size <= changesets:

--- a/mercurial/hbisect.py	Tue Jul 15 18:10:37 2008 -0500
+++ b/mercurial/hbisect.py	Sat Aug 02 22:10:10 2008 +0200
@@ -12,6 +12,16 @@
 import util
 
 def bisect(changelog, state):
+    """find the next node (if any) for testing during a bisect search.
+    returns a (nodes, number, good) tuple.
+
+    'nodes' is the final result of the bisect if 'number' is 0.
+    Otherwise 'number' indicates the remaining possible candidates for
+    the search and 'nodes' contains the next bisect target.
+    'good' is True if bisect is searching for a first good changeset, False
+    if searching for a first bad one.
+    """
+
     clparents = changelog.parentrevs
     skip = dict.fromkeys([changelog.rev(n) for n in state['skip']])
 
@@ -62,9 +72,11 @@
 
     candidates.sort()
     # have we narrowed it down to one entry?
+    # or have all other possible candidates besides 'bad' have been skipped?
     tot = len(candidates)
-    if tot == 1:
-        return (bad, 0, good)
+    unskipped = [c for c in candidates if (c not in skip) and (c != badrev)]
+    if tot == 1 or not unskipped:
+        return ([changelog.node(rev) for rev in candidates], 0, good)
     perfect = tot / 2
 
     # find the best node to test
@@ -103,4 +115,4 @@
     assert best_rev is not None
     best_node = changelog.node(best_rev)
 
-    return (best_node, tot, good)
+    return ([best_node], tot, good)