changeset 5723:e3b09819496b

bisect: switch to rev-based calculation

- use revlog.parentrevs in search loops
- calculate stop directly in O(N) without reachable
- move badrev check into candidates

--- a/hgext/hbisect.py	Thu Dec 27 23:55:39 2007 -0600
+++ b/hgext/hbisect.py	Thu Dec 27 23:55:39 2007 -0600
@@ -75,44 +75,49 @@
         ancestors of goodnodes are used as lower limit.
         """
         cl = self.repo.changelog
-        stop = {}
+        clparents = cl.parentrevs
         bad = self.badnode
-        for i in xrange(len(self.goodnodes)-1, -1, -1):
-            g = self.goodnodes[i]
-            if g in stop:
-                continue
-            stop.update(cl.reachable(g))
+        badrev = cl.rev(bad)
 
-        if bad in stop:
+        # add goodrevs and all ancestors to stop
+        stop = dict.fromkeys([cl.rev(n) for n in self.goodnodes])
+        for rev in xrange(cl.count(), -1, -1):
+            if rev in stop:
+                for prev in clparents(rev):
+                    stop[prev] = None
+
+        if badrev in stop:
             raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
-                             % (cl.rev(bad), hg.short(bad)))
+                             % (badrev, hg.short(bad)))
 
         # build a dict of node -> [number of children, {}]
-        n_child = {bad: [0, {}]}
-        for i in xrange(cl.rev(bad)+1):
-            n = cl.node(i)
-            if n not in n_child:
-                n_child[n] = [0, {}]
+        n_child = {badrev: [0, {}]}
+        for rev in xrange(badrev + 1):
+            if rev not in n_child:
+                n_child[rev] = [0, {}]
             # increment count of each parent
-            for p in cl.parents(n):
-                if p != hg.nullid:
+            for p in clparents(rev):
+                if p != hg.nullrev:
                     n_child[p][0] += 1
 
-        for i in xrange(cl.rev(bad)+1):
-            n = cl.node(i)
-            for p in cl.parents(n):
-                if p != hg.nullid:
+        for rev in xrange(badrev + 1):
+            for p in clparents(rev):
+                if p != hg.nullrev:
                     n_child[p][0] -= 1
-                    if not n in stop:
-                        n_child[n][1].update(n_child[p][1])
+                    if not rev in stop:
+                        n_child[rev][1].update(n_child[p][1])
                     if n_child[p][0] == 0:
                         n_child[p] = len(n_child[p][1])
-            if not n in stop:
-                n_child[n][1][n] = 1
-            if n_child[n][0] == 0:
-                if n == bad:
-                    anc = n_child[n][1]
-                n_child[n] = len(n_child[n][1])
+            if not rev in stop:
+                n_child[rev][1][rev] = 1
+            if n_child[rev][0] == 0:
+                if rev == badrev:
+                    anc = n_child[rev][1]
+                n_child[rev] = len(n_child[rev][1])
+
+        if badrev not in anc:
+            raise util.Abort(_("Could not find the first bad revision"))
+
         return anc, n_child
 
     def next(self):
@@ -126,15 +131,13 @@
         # have we narrowed it down to one entry?
         tot = len(ancestors)
         if tot == 1:
-            if self.badnode not in ancestors:
-                raise util.Abort(_("Could not find the first bad revision"))
             self.ui.write(_("The first bad revision is:\n"))
             displayer = cmdutil.show_changeset(self.ui, self.repo, {})
             displayer.show(changenode=self.badnode)
             return None
 
         # find the best node to test
-        best_node = None
+        best_rev = None
         best_len = -1
         for n in ancestors:
             a = n_child[n] # number of children
@@ -142,8 +145,9 @@
             value = min(a, b) # how good is this test?
             if value > best_len:
                 best_len = value
-                best_node = n
-        assert best_node is not None
+                best_rev = n
+        assert best_rev is not None
+        best_node = self.repo.changelog.node(best_rev)
 
         # compute the approximate number of remaining tests
         nb_tests = 0
@@ -152,10 +156,9 @@
             nb_tests += 1
             q, r = divmod(q, 2)
 
-        msg = _("Testing changeset %s:%s (%s changesets remaining, "
-                "~%s tests)\n") % (self.repo.changelog.rev(best_node),
-                                   hg.short(best_node), tot, nb_tests)
-        self.ui.write(msg)
+        self.ui.write(_("Testing changeset %s:%s "
+                        "(%s changesets remaining, ~%s tests)\n")
+                      % (best_rev, hg.short(best_node), tot, nb_tests))
         return best_node
 
     def autonext(self):