hbisect.py
299 lines
| 10.3 KiB
| text/x-python
|
PythonLexer
/ hgext / hbisect.py
|
r1862 | # bisect extension for mercurial | ||
# | ||||
# Copyright 2005, 2006 Benoit Boissinot <benoit.boissinot@ens-lyon.org> | ||||
# 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. | ||||
|
r2348 | from mercurial.i18n import gettext as _ | ||
|
r1862 | from mercurial.demandload import demandload | ||
|
r2348 | demandload(globals(), "os sys sets mercurial:hg,util,commands") | ||
|
r1862 | |||
versionstr = "0.0.3" | ||||
def lookup_rev(ui, repo, rev=None): | ||||
"""returns rev or the checked-out revision if rev is None""" | ||||
if not rev is None: | ||||
return repo.lookup(rev) | ||||
parents = [p for p in repo.dirstate.parents() if p != hg.nullid] | ||||
if len(parents) != 1: | ||||
|
r2348 | raise util.Abort(_("unexpected number of parents, " | ||
"please commit or revert")) | ||||
|
r1862 | return parents.pop() | ||
def check_clean(ui, repo): | ||||
modified, added, removed, deleted, unknown = repo.changes() | ||||
if modified or added or removed: | ||||
ui.warn("Repository is not clean, please commit or revert\n") | ||||
sys.exit(1) | ||||
class bisect(object): | ||||
"""dichotomic search in the DAG of changesets""" | ||||
def __init__(self, ui, repo): | ||||
self.repo = repo | ||||
self.path = repo.join("bisect") | ||||
self.opener = util.opener(self.path) | ||||
self.ui = ui | ||||
self.goodrevs = [] | ||||
self.badrev = None | ||||
self.good_dirty = 0 | ||||
self.bad_dirty = 0 | ||||
self.good_path = "good" | ||||
self.bad_path = "bad" | ||||
if os.path.exists(os.path.join(self.path, self.good_path)): | ||||
self.goodrevs = self.opener(self.good_path).read().splitlines() | ||||
self.goodrevs = [hg.bin(x) for x in self.goodrevs] | ||||
if os.path.exists(os.path.join(self.path, self.bad_path)): | ||||
r = self.opener(self.bad_path).read().splitlines() | ||||
if r: | ||||
self.badrev = hg.bin(r.pop(0)) | ||||
|
r2735 | def write(self): | ||
|
r1862 | if not os.path.isdir(self.path): | ||
return | ||||
f = self.opener(self.good_path, "w") | ||||
f.write("\n".join([hg.hex(r) for r in self.goodrevs])) | ||||
if len(self.goodrevs) > 0: | ||||
f.write("\n") | ||||
f = self.opener(self.bad_path, "w") | ||||
if self.badrev: | ||||
f.write(hg.hex(self.badrev) + "\n") | ||||
def init(self): | ||||
"""start a new bisection""" | ||||
if os.path.isdir(self.path): | ||||
|
r2348 | raise util.Abort(_("bisect directory already exists\n")) | ||
|
r1862 | os.mkdir(self.path) | ||
check_clean(self.ui, self.repo) | ||||
return 0 | ||||
def reset(self): | ||||
"""finish a bisection""" | ||||
if os.path.isdir(self.path): | ||||
sl = [os.path.join(self.path, p) | ||||
for p in [self.bad_path, self.good_path]] | ||||
for s in sl: | ||||
if os.path.exists(s): | ||||
os.unlink(s) | ||||
os.rmdir(self.path) | ||||
# Not sure about this | ||||
#self.ui.write("Going back to tip\n") | ||||
#self.repo.update(self.repo.changelog.tip()) | ||||
return 1 | ||||
def num_ancestors(self, head=None, stop=None): | ||||
""" | ||||
returns a dict with the mapping: | ||||
node -> number of ancestors (self included) | ||||
for all nodes who are ancestor of head and | ||||
not in stop. | ||||
""" | ||||
if head is None: | ||||
head = self.badrev | ||||
return self.__ancestors_and_nb_ancestors(head, stop)[1] | ||||
def ancestors(self, head=None, stop=None): | ||||
""" | ||||
returns the set of the ancestors of head (self included) | ||||
who are not in stop. | ||||
""" | ||||
if head is None: | ||||
head = self.badrev | ||||
return self.__ancestors_and_nb_ancestors(head, stop)[0] | ||||
def __ancestors_and_nb_ancestors(self, head, stop=None): | ||||
""" | ||||
if stop is None then ancestors of goodrevs are used as | ||||
lower limit. | ||||
returns (anc, n_child) where anc is the set of the ancestors of head | ||||
and n_child is a dictionary with the following mapping: | ||||
node -> number of ancestors (self included) | ||||
""" | ||||
cl = self.repo.changelog | ||||
if not stop: | ||||
stop = sets.Set([]) | ||||
for i in xrange(len(self.goodrevs)-1, -1, -1): | ||||
g = self.goodrevs[i] | ||||
if g in stop: | ||||
continue | ||||
stop.update(cl.reachable(g)) | ||||
def num_children(a): | ||||
""" | ||||
returns a dictionnary with the following mapping | ||||
node -> [number of children, empty set] | ||||
""" | ||||
d = {a: [0, sets.Set([])]} | ||||
for i in xrange(cl.rev(a)+1): | ||||
n = cl.node(i) | ||||
if not d.has_key(n): | ||||
d[n] = [0, sets.Set([])] | ||||
parents = [p for p in cl.parents(n) if p != hg.nullid] | ||||
for p in parents: | ||||
d[p][0] += 1 | ||||
return d | ||||
if head in stop: | ||||
|
r2348 | raise util.Abort(_("Unconsistent state, %s:%s is good and bad") | ||
% (cl.rev(head), hg.short(head))) | ||||
|
r1862 | n_child = num_children(head) | ||
for i in xrange(cl.rev(head)+1): | ||||
n = cl.node(i) | ||||
parents = [p for p in cl.parents(n) if p != hg.nullid] | ||||
for p in parents: | ||||
n_child[p][0] -= 1 | ||||
if not n in stop: | ||||
n_child[n][1].union_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].add(n) | ||||
if n_child[n][0] == 0: | ||||
if n == head: | ||||
anc = n_child[n][1] | ||||
n_child[n] = len(n_child[n][1]) | ||||
return anc, n_child | ||||
def next(self): | ||||
if not self.badrev: | ||||
|
r2348 | raise util.Abort(_("You should give at least one bad revision")) | ||
|
r1862 | if not self.goodrevs: | ||
|
r2348 | self.ui.warn(_("No good revision given\n")) | ||
self.ui.warn(_("Marking the first revision as good\n")) | ||||
|
r1862 | ancestors, num_ancestors = self.__ancestors_and_nb_ancestors( | ||
self.badrev) | ||||
tot = len(ancestors) | ||||
if tot == 1: | ||||
if ancestors.pop() != self.badrev: | ||||
|
r2348 | raise util.Abort(_("Could not find the first bad revision")) | ||
self.ui.write(_("The first bad revision is:\n")) | ||||
displayer = commands.show_changeset(self.ui, self.repo, {}) | ||||
displayer.show(changenode=self.badrev) | ||||
return None | ||||
|
r1862 | best_rev = None | ||
best_len = -1 | ||||
for n in ancestors: | ||||
l = num_ancestors[n] | ||||
l = min(l, tot - l) | ||||
if l > best_len: | ||||
best_len = l | ||||
best_rev = n | ||||
|
r2348 | assert best_rev is not None | ||
nb_tests = 0 | ||||
q, r = divmod(tot, 2) | ||||
while q: | ||||
nb_tests += 1 | ||||
q, r = divmod(q, 2) | ||||
msg = _("Testing changeset %s:%s (%s changesets remaining, " | ||||
"~%s tests)\n") % (self.repo.changelog.rev(best_rev), | ||||
hg.short(best_rev), tot, nb_tests) | ||||
self.ui.write(msg) | ||||
|
r1862 | return best_rev | ||
def autonext(self): | ||||
"""find and update to the next revision to test""" | ||||
check_clean(self.ui, self.repo) | ||||
rev = self.next() | ||||
|
r2348 | if rev is not None: | ||
|
r2808 | return hg.clean(self.repo, rev) | ||
|
r1862 | |||
def good(self, rev): | ||||
self.goodrevs.append(rev) | ||||
def autogood(self, rev=None): | ||||
"""mark revision as good and update to the next revision to test""" | ||||
check_clean(self.ui, self.repo) | ||||
rev = lookup_rev(self.ui, self.repo, rev) | ||||
self.good(rev) | ||||
if self.badrev: | ||||
|
r2348 | return self.autonext() | ||
|
r1862 | |||
def bad(self, rev): | ||||
self.badrev = rev | ||||
def autobad(self, rev=None): | ||||
"""mark revision as bad and update to the next revision to test""" | ||||
check_clean(self.ui, self.repo) | ||||
rev = lookup_rev(self.ui, self.repo, rev) | ||||
self.bad(rev) | ||||
if self.goodrevs: | ||||
self.autonext() | ||||
# should we put it in the class ? | ||||
def test(ui, repo, rev): | ||||
"""test the bisection code""" | ||||
b = bisect(ui, repo) | ||||
rev = repo.lookup(rev) | ||||
ui.write("testing with rev %s\n" % hg.hex(rev)) | ||||
anc = b.ancestors() | ||||
while len(anc) > 1: | ||||
if not rev in anc: | ||||
ui.warn("failure while bisecting\n") | ||||
sys.exit(1) | ||||
ui.write("it worked :)\n") | ||||
new_rev = b.next() | ||||
ui.write("choosing if good or bad\n") | ||||
if rev in b.ancestors(head=new_rev): | ||||
b.bad(new_rev) | ||||
ui.write("it is bad\n") | ||||
else: | ||||
b.good(new_rev) | ||||
ui.write("it is good\n") | ||||
anc = b.ancestors() | ||||
|
r2348 | #repo.update(new_rev, force=True) | ||
|
r1862 | for v in anc: | ||
if v != rev: | ||||
ui.warn("fail to found cset! :(\n") | ||||
return 1 | ||||
ui.write("Found bad cset: %s\n" % hg.hex(b.badrev)) | ||||
ui.write("Everything is ok :)\n") | ||||
return 0 | ||||
def bisect_run(ui, repo, cmd=None, *args): | ||||
"""bisect extension: dichotomic search in the DAG of changesets | ||||
for subcommands see "hg bisect help\" | ||||
""" | ||||
def help_(cmd=None, *args): | ||||
"""show help for a given bisect subcommand or all subcommands""" | ||||
cmdtable = bisectcmdtable | ||||
if cmd: | ||||
doc = cmdtable[cmd][0].__doc__ | ||||
synopsis = cmdtable[cmd][2] | ||||
ui.write(synopsis + "\n") | ||||
ui.write("\n" + doc + "\n") | ||||
return | ||||
|
r2348 | ui.write(_("list of subcommands for the bisect extension\n\n")) | ||
|
r1862 | cmds = cmdtable.keys() | ||
cmds.sort() | ||||
m = max([len(c) for c in cmds]) | ||||
for cmd in cmds: | ||||
doc = cmdtable[cmd][0].__doc__.splitlines(0)[0].rstrip() | ||||
ui.write(" %-*s %s\n" % (m, cmd, doc)) | ||||
b = bisect(ui, repo) | ||||
bisectcmdtable = { | ||||
|
r2348 | "init": (b.init, 0, _("hg bisect init")), | ||
"bad": (b.autobad, 1, _("hg bisect bad [<rev>]")), | ||||
"good": (b.autogood, 1, _("hg bisect good [<rev>]")), | ||||
"next": (b.autonext, 0, _("hg bisect next")), | ||||
"reset": (b.reset, 0, _("hg bisect reset")), | ||||
"help": (help_, 1, _("hg bisect help [<subcommand>]")), | ||||
|
r1862 | } | ||
if not bisectcmdtable.has_key(cmd): | ||||
|
r2348 | ui.warn(_("bisect: Unknown sub-command\n")) | ||
|
r1862 | return help_() | ||
if len(args) > bisectcmdtable[cmd][1]: | ||||
|
r2348 | ui.warn(_("bisect: Too many arguments\n")) | ||
|
r1862 | return help_() | ||
|
r2735 | try: | ||
return bisectcmdtable[cmd][0](*args) | ||||
finally: | ||||
b.write() | ||||
|
r1862 | |||
cmdtable = { | ||||
|
r2348 | "bisect": (bisect_run, [], _("hg bisect [help|init|reset|next|good|bad]")), | ||
|
r1862 | #"bisect-test": (test, [], "hg bisect-test rev"), | ||
} | ||||