hbisect.py
105 lines
| 3.3 KiB
| text/x-python
|
PythonLexer
/ mercurial / hbisect.py
|
r5775 | # changelog bisection for mercurial | ||
# | ||||
# Copyright 2007 Matt Mackall | ||||
# 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. | ||||
from i18n import _ | ||||
import hg, util | ||||
def bisect(changelog, state): | ||||
clparents = changelog.parentrevs | ||||
skip = dict.fromkeys([changelog.rev(n) for n in state['skip']]) | ||||
|
r5776 | def buildancestors(bad, good): | ||
# only the earliest bad revision matters | ||||
badrev = min([changelog.rev(n) for n in bad]) | ||||
goodrevs = [changelog.rev(n) for n in good] | ||||
# build ancestors array | ||||
ancestors = [[]] * (changelog.count() + 1) # an extra for [-1] | ||||
|
r5775 | |||
|
r5776 | # clear good revs from array | ||
for node in goodrevs: | ||||
ancestors[node] = None | ||||
for rev in xrange(changelog.count(), -1, -1): | ||||
if ancestors[rev] is None: | ||||
for prev in clparents(rev): | ||||
ancestors[prev] = None | ||||
|
r5775 | |||
|
r5776 | if ancestors[badrev] is None: | ||
|
r5777 | return badrev, None | ||
|
r5776 | return badrev, ancestors | ||
good = 0 | ||||
badrev, ancestors = buildancestors(state['bad'], state['good']) | ||||
if not ancestors: # looking for bad to good transition? | ||||
good = 1 | ||||
badrev, ancestors = buildancestors(state['good'], state['bad']) | ||||
|
r5777 | bad = changelog.node(badrev) | ||
|
r5776 | if not ancestors: # now we're confused | ||
|
r5775 | 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: | ||||
|
r5776 | return (bad, 0, good) | ||
|
r5775 | 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) | ||||
|
r5776 | return (best_node, tot, good) | ||