mercurial/hbisect.py

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mercurial/hbisect.py	Mon Dec 31 18:20:34 2007 -0600
@@ -0,0 +1,94 @@
+# changelog bisection for mercurial
+#
+# Copyright 2007 Matt Mackall
+# Copyright 2005, 2006 Benoit Boissinot <[e-mail]>
+# Inspired by git bisect, extension skeleton taken from mq.py.
+#
+# This software may be used and distributed according to the terms
+# of the GNU General Public License, incorporated herein by reference.
+
+from i18n import _
+import hg, util
+
+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]
+
+    # 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
+
+    if ancestors[badrev] is None:
+        raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
+                         % (badrev, hg.short(bad)))
+
+    # build children dict
+    children = {}
+    visit = [badrev]
+    candidates = []
+    while visit:
+        rev = visit.pop(0)
+        if ancestors[rev] == []:
+            candidates.append(rev)
+            for prev in clparents(rev):
+                if prev != -1:
+                    if prev in children:
+                        children[prev].append(rev)
+                    else:
+                        children[prev] = [rev]
+                        visit.append(prev)
+
+    candidates.sort()
+    # have we narrowed it down to one entry?
+    tot = len(candidates)
+    if tot == 1:
+        return (bad, 0)
+    perfect = tot / 2
+
+    # find the best node to test
+    best_rev = None
+    best_len = -1
+    poison = {}
+    for rev in candidates:
+        if rev in poison:
+            for c in children.get(rev, []):
+                poison[c] = True # poison children
+            continue
+
+        a = ancestors[rev] or [rev]
+        ancestors[rev] = None
+
+        x = len(a) # number of ancestors
+        y = tot - x # number of non-ancestors
+        value = min(x, y) # how good is this test?
+        if value > best_len and rev not in skip:
+            best_len = value
+            best_rev = rev
+            if value == perfect: # found a perfect candidate? quit early
+                break
+
+        if y < perfect: # all downhill from here?
+            for c in children.get(rev, []):
+                poison[c] = True # poison children
+            continue
+
+        for c in children.get(rev, []):
+            if ancestors[c]:
+                ancestors[c] = dict.fromkeys(ancestors[c] + a).keys()
+            else:
+                ancestors[c] = a + [c]
+
+    assert best_rev is not None
+    best_node = changelog.node(best_rev)
+
+    return (best_node, tot)