--- a/hgext/hbisect.py Thu Dec 27 23:55:40 2007 -0600
+++ b/hgext/hbisect.py Thu Dec 27 23:55:40 2007 -0600
@@ -10,141 +10,73 @@
from mercurial import hg, util, cmdutil
import os, array
-class bisect(object):
- """dichotomic search in the DAG of changesets"""
- def __init__(self, ui, repo):
- self.repo = repo
- self.ui = ui
- self.state = {'good': [], 'bad': [], 'skip': []}
+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)
- p = self.repo.join("bisect.state")
- if os.path.exists(p):
- for l in self.repo.opener("bisect.state"):
- kind, node = l[:-1].split()
- node = self.repo.lookup(node)
- if kind not in self.state:
- raise util.Abort(_("unknown bisect kind %s") % kind)
- self.state[kind].append(node)
+ # build ancestors array
+ ancestors = [[]] * (changelog.count() + 1) # an extra for [-1]
- def write(self):
- f = self.repo.opener("bisect.state", "w")
- for kind in self.state:
- for node in self.state[kind]:
- f.write("%s %s\n" % (kind, hg.hex(node)))
-
- def init(self):
- """start a new bisection"""
- p = self.repo.join("bisect.state")
- if os.path.exists(p):
- os.unlink(p)
+ # 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
- def bisect(self):
- cl = self.repo.changelog
- clparents = cl.parentrevs
- # only the earliest bad revision matters
- badrev = min([cl.rev(n) for n in self.state['bad']])
- bad = cl.node(badrev)
-
- # build ancestors array
- ancestors = [[]] * (cl.count() + 1) # an extra for [-1]
-
- # clear good revs from array
- for node in self.state['good']:
- ancestors[cl.rev(node)] = None
- for rev in xrange(cl.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)))
- if ancestors[badrev] is None:
- raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
- % (badrev, hg.short(bad)))
-
- # accumulate ancestor lists
- for rev in xrange(badrev + 1):
- if ancestors[rev] == []:
- p1, p2 = clparents(rev)
- a1, a2 = ancestors[p1], ancestors[p2]
- if a1:
- if a2:
- # merge ancestor lists
- a = dict.fromkeys(a2)
- a.update(dict.fromkeys(a1))
- a[rev] = None
- ancestors[rev] = array.array("l", a.keys())
- else:
- ancestors[rev] = a1 + array.array("l", [rev])
- elif a2:
- ancestors[rev] = a2 + array.array("l", [rev])
+ # accumulate ancestor lists
+ for rev in xrange(badrev + 1):
+ if ancestors[rev] == []:
+ p1, p2 = clparents(rev)
+ a1, a2 = ancestors[p1], ancestors[p2]
+ if a1:
+ if a2:
+ # merge ancestor lists
+ a = dict.fromkeys(a2)
+ a.update(dict.fromkeys(a1))
+ a[rev] = None
+ ancestors[rev] = array.array("l", a.keys())
else:
- ancestors[rev] = array.array("l", [rev])
-
- if badrev not in ancestors[badrev]:
- raise util.Abort(_("Could not find the first bad revision"))
-
- # have we narrowed it down to one entry?
- tot = len(ancestors[badrev])
- if tot == 1:
- return (bad, 0)
+ ancestors[rev] = a1 + array.array("l", [rev])
+ elif a2:
+ ancestors[rev] = a2 + array.array("l", [rev])
+ else:
+ ancestors[rev] = array.array("l", [rev])
- # find the best node to test
- best_rev = None
- best_len = -1
- skip = dict.fromkeys([cl.rev(n) for n in self.state['skip']])
- for n in ancestors[badrev]:
- if n in skip:
- continue
- a = len(ancestors[n]) # number of ancestors
- b = tot - a # number of non-ancestors
- value = min(a, b) # how good is this test?
- if value > best_len:
- best_len = value
- best_rev = n
- assert best_rev is not None
- best_node = cl.node(best_rev)
+ if badrev not in ancestors[badrev]:
+ raise util.Abort(_("Could not find the first bad revision"))
- return (best_node, tot)
-
- def next(self):
- """find and update to the next revision to test"""
- if self.state['good'] and self.state['bad']:
- node, changesets = self.bisect()
+ # have we narrowed it down to one entry?
+ tot = len(ancestors[badrev])
+ if tot == 1:
+ return (bad, 0)
- if changesets == 0:
- self.ui.write(_("The first bad revision is:\n"))
- displayer = cmdutil.show_changeset(self.ui, self.repo, {})
- displayer.show(changenode=node)
- elif node is not None:
- # compute the approximate number of remaining tests
- tests, size = 0, 2
- while size <= changesets:
- tests, size = tests + 1, size * 2
- rev = self.repo.changelog.rev(node)
- self.ui.write(_("Testing changeset %s:%s "
- "(%s changesets remaining, ~%s tests)\n")
- % (rev, hg.short(node), changesets, tests))
- cmdutil.bail_if_changed(self.repo)
- return hg.clean(self.repo, node)
+ # find the best node to test
+ best_rev = None
+ best_len = -1
+ skip = dict.fromkeys([changelog.rev(n) for n in state['skip']])
+ for n in ancestors[badrev]:
+ if n in skip:
+ continue
+ a = len(ancestors[n]) # number of ancestors
+ b = tot - a # number of non-ancestors
+ value = min(a, b) # how good is this test?
+ if value > best_len:
+ best_len = value
+ best_rev = n
+ assert best_rev is not None
+ best_node = changelog.node(best_rev)
- def good(self, rev=None):
- """mark revision as good and update to the next revision to test"""
- self.state['good'].append(self.repo.lookup(rev or '.'))
- self.write()
- return self.next()
+ return (best_node, tot)
- def skip(self, rev=None):
- """mark revision as skipped and update to the next revision to test"""
- self.state['skip'].append(self.repo.lookup(rev or '.'))
- self.write()
- return self.next()
-
- def bad(self, rev=None):
- """mark revision as bad and update to the next revision to test"""
- self.state['bad'].append(self.repo.lookup(rev or '.'))
- self.write()
- return self.next()
-
-def bisect_run(ui, repo, node=None, extra=None,
+def bisect(ui, repo, rev=None, extra=None,
reset=None, good=None, bad=None, skip=None):
"""Subdivision search of changesets
@@ -162,9 +94,9 @@
"""
# backward compatibility
- if node in "good bad reset init".split():
+ if rev in "good bad reset init".split():
ui.warn(_("(use of 'hg bisect <cmd>' is deprecated)\n"))
- cmd, node, extra = node, extra, None
+ cmd, rev, extra = rev, extra, None
if cmd == "good":
good = True
elif cmd == "bad":
@@ -174,20 +106,60 @@
elif extra or good + bad + skip + reset > 1:
raise util.Abort("Incompatible arguments")
- b = bisect(ui, repo)
+ if reset:
+ p = repo.join("bisect.state")
+ if os.path.exists(p):
+ os.unlink(p)
+ return
+
+ # load state
+ state = {'good': [], 'bad': [], 'skip': []}
+ if os.path.exists(repo.join("bisect.state")):
+ for l in repo.opener("bisect.state"):
+ kind, node = l[:-1].split()
+ node = repo.lookup(node)
+ if kind not in state:
+ raise util.Abort(_("unknown bisect kind %s") % kind)
+ state[kind].append(node)
+
+ # update state
+ node = repo.lookup(rev or '.')
if good:
- return b.good(node)
+ state['good'].append(node)
elif bad:
- return b.bad(node)
+ state['bad'].append(node)
elif skip:
- return b.skip(node)
- elif reset:
- return b.init()
- else:
- return b.next()
+ state['skip'].append(node)
+
+ # save state
+ f = repo.opener("bisect.state", "w")
+ for kind in state:
+ for node in state[kind]:
+ f.write("%s %s\n" % (kind, hg.hex(node)))
+
+ if not state['good'] or not state['bad']:
+ return
+
+ # actually bisect
+ node, changesets = _bisect(repo.changelog, state)
+ if changesets == 0:
+ ui.write(_("The first bad revision is:\n"))
+ displayer = cmdutil.show_changeset(ui, repo, {})
+ displayer.show(changenode=node)
+ elif node is not None:
+ # 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)
+ ui.write(_("Testing changeset %s:%s "
+ "(%s changesets remaining, ~%s tests)\n")
+ % (rev, hg.short(node), changesets, tests))
+ cmdutil.bail_if_changed(repo)
+ return hg.clean(repo, node)
cmdtable = {
- "bisect": (bisect_run,
+ "bisect": (bisect,
[('r', 'reset', False, _('reset bisect state')),
('g', 'good', False, _('mark changeset good')),
('b', 'bad', False, _('mark changeset bad')),