[PATCH 3 of 3] add support for multiple possible bisect results (issue1228, issue1182)

[Bernhard Leiner]

# HG changeset patch
# User Bernhard Leiner <bleiner at gmail.com>
# Date 1217707810 -7200
# Node ID b324f125c5ddd136f52f84766cab61ffc17dcd45
# Parent  7d6622eaad08d3ab8cdcc61109c0cc99eeadcc5e
add support for multiple possible bisect results (issue1228, issue1182)

The _real_ reason for both issue issue1228 and issue1182 is that bisect can not
handle cases where there are multiple possibilites for the result.

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

Which one is the first bad revision? It might 1, 2, 3 or 4!

This patch adds support for detecting and printing multiple bisect results.
(by the way: this is also the way such bisects are handles by git)


Note that this patch does not only fix the reported Assertion Error but also
the problem of a non converging bisect (as reported in msg6313 of issue1182).
This can easily reproduced by the following steps:

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

diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -324,23 +324,33 @@
         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
         # compute the approximate number of remaining tests
         tests, size = 0, 2
         while size <= changesets:
             tests, size = tests + 1, size * 2
-        rev = repo.changelog.rev(node)
+        rev = repo.changelog.rev(nodes[0])
         ui.write(_("Testing changeset %s:%s "
                    "(%s changesets remaining, ~%s tests)\n")
-                 % (rev, short(node), changesets, tests))
+                 % (rev, short(nodes[0]), changesets, tests))
         if not noupdate:
             cmdutil.bail_if_changed(repo)
-            return hg.clean(repo, node)
+            return hg.clean(repo, nodes[0])
 
 def branch(ui, repo, label=None, **opts):
     """set or show the current branch name
diff --git a/mercurial/hbisect.py b/mercurial/hbisect.py
--- a/mercurial/hbisect.py
+++ b/mercurial/hbisect.py
@@ -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) tupple.
+
+    'nodes' is the final result of the bisect if 'number' is 0.
+    Otherwise 'number' indicates the remaining possible candiates 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
@@ -101,6 +113,6 @@
                 ancestors[c] = a + [c]
 
     assert best_rev is not None
-    best_node = changelog.node(best_rev)
+    best_node = [changelog.node(best_rev)]
 
     return (best_node, tot, good)