hbisect.py
258 lines
| 9.0 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> | ||||
|
r8228 | # | ||
|
r5775 | # Inspired by git bisect, extension skeleton taken from mq.py. | ||
# | ||||
|
r8225 | # This software may be used and distributed according to the terms of the | ||
|
r10263 | # GNU General Public License version 2 or any later version. | ||
|
r5775 | |||
|
r15135 | import os, error | ||
|
r5775 | from i18n import _ | ||
|
r7227 | from node import short, hex | ||
|
r6217 | import util | ||
|
r5775 | |||
def bisect(changelog, state): | ||||
|
r6858 | """find the next node (if any) for testing during a bisect search. | ||
returns a (nodes, number, good) tuple. | ||||
'nodes' is the final result of the bisect if 'number' is 0. | ||||
Otherwise 'number' indicates the remaining possible candidates for | ||||
the search and 'nodes' contains the next bisect target. | ||||
'good' is True if bisect is searching for a first good changeset, False | ||||
if searching for a first bad one. | ||||
""" | ||||
|
r5775 | clparents = changelog.parentrevs | ||
|
r8152 | skip = set([changelog.rev(n) for n in state['skip']]) | ||
|
r5775 | |||
|
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] | ||||
|
r9583 | goodrev = min(goodrevs) | ||
# build visit array | ||||
ancestors = [None] * (len(changelog) + 1) # an extra for [-1] | ||||
|
r14895 | # set nodes descended from goodrevs | ||
for rev in goodrevs: | ||||
ancestors[rev] = [] | ||||
|
r9583 | for rev in xrange(goodrev + 1, len(changelog)): | ||
for prev in clparents(rev): | ||||
if ancestors[prev] == []: | ||||
ancestors[rev] = [] | ||||
|
r5775 | |||
|
r5776 | # clear good revs from array | ||
|
r14894 | for rev in goodrevs: | ||
ancestors[rev] = None | ||||
|
r14893 | for rev in xrange(len(changelog), goodrev, -1): | ||
|
r5776 | 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 | ||
|
r14215 | good = False | ||
|
r5776 | badrev, ancestors = buildancestors(state['bad'], state['good']) | ||
if not ancestors: # looking for bad to good transition? | ||||
|
r14215 | good = True | ||
|
r5776 | badrev, ancestors = buildancestors(state['good'], state['bad']) | ||
|
r5777 | bad = changelog.node(badrev) | ||
|
r5776 | if not ancestors: # now we're confused | ||
|
r12005 | if len(state['bad']) == 1 and len(state['good']) == 1: | ||
raise util.Abort(_("starting revisions are not directly related")) | ||||
|
r12067 | raise util.Abort(_("inconsistent state, %s:%s is good and bad") | ||
|
r6217 | % (badrev, short(bad))) | ||
|
r5775 | |||
# 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? | ||||
|
r6858 | # or have all other possible candidates besides 'bad' have been skipped? | ||
|
r5775 | tot = len(candidates) | ||
|
r6858 | unskipped = [c for c in candidates if (c not in skip) and (c != badrev)] | ||
if tot == 1 or not unskipped: | ||||
return ([changelog.node(rev) for rev in candidates], 0, good) | ||||
|
r7902 | perfect = tot // 2 | ||
|
r5775 | |||
# find the best node to test | ||||
best_rev = None | ||||
best_len = -1 | ||||
|
r8463 | poison = set() | ||
|
r5775 | for rev in candidates: | ||
if rev in poison: | ||||
|
r8482 | # poison children | ||
poison.update(children.get(rev, [])) | ||||
|
r5775 | 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 | ||||
|
r7557 | if y < perfect and rev not in skip: # all downhill from here? | ||
|
r8482 | # poison children | ||
poison.update(children.get(rev, [])) | ||||
|
r5775 | continue | ||
for c in children.get(rev, []): | ||||
if ancestors[c]: | ||||
|
r8152 | ancestors[c] = list(set(ancestors[c] + a)) | ||
|
r5775 | else: | ||
ancestors[c] = a + [c] | ||||
assert best_rev is not None | ||||
best_node = changelog.node(best_rev) | ||||
|
r6858 | return ([best_node], tot, good) | ||
|
r7227 | |||
def load_state(repo): | ||||
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) | ||||
return state | ||||
def save_state(repo, state): | ||||
f = repo.opener("bisect.state", "w", atomictemp=True) | ||||
wlock = repo.wlock() | ||||
try: | ||||
for kind in state: | ||||
for node in state[kind]: | ||||
f.write("%s %s\n" % (kind, hex(node))) | ||||
|
r15057 | f.close() | ||
|
r7227 | finally: | ||
|
r8109 | wlock.release() | ||
|
r7227 | |||
|
r15135 | def get(repo, status): | ||
""" | ||||
Return a list of revision(s) that match the given status: | ||||
|
r15153 | - ``good``, ``bad``, ``skip``: csets explicitly marked as good/bad/skip | ||
- ``goods``, ``bads`` : csets topologicaly good/bad | ||||
- ``range`` : csets taking part in the bisection | ||||
- ``pruned`` : csets that are goods, bads or skipped | ||||
|
r15138 | - ``untested`` : csets whose fate is yet unknown | ||
|
r15147 | - ``ignored`` : csets ignored due to DAG topology | ||
|
r15135 | """ | ||
state = load_state(repo) | ||||
if status in ('good', 'bad', 'skip'): | ||||
return [repo.changelog.rev(n) for n in state[status]] | ||||
else: | ||||
|
r15146 | # In the floowing sets, we do *not* call 'bisect()' with more | ||
# than one level of recusrsion, because that can be very, very | ||||
# time consuming. Instead, we always develop the expression as | ||||
# much as possible. | ||||
# 'range' is all csets that make the bisection: | ||||
# - have a good ancestor and a bad descendant, or conversely | ||||
# that's because the bisection can go either way | ||||
range = '( bisect(bad)::bisect(good) | bisect(good)::bisect(bad) )' | ||||
|
r15136 | |||
|
r15153 | _t = [c.rev() for c in repo.set('bisect(good)::bisect(bad)')] | ||
# The sets of topologically good or bad csets | ||||
if len(_t) == 0: | ||||
# Goods are topologically after bads | ||||
goods = 'bisect(good)::' # Pruned good csets | ||||
bads = '::bisect(bad)' # Pruned bad csets | ||||
else: | ||||
# Goods are topologically before bads | ||||
goods = '::bisect(good)' # Pruned good csets | ||||
bads = 'bisect(bad)::' # Pruned bad csets | ||||
# 'pruned' is all csets whose fate is already known: good, bad, skip | ||||
skips = 'bisect(skip)' # Pruned skipped csets | ||||
pruned = '( (%s) | (%s) | (%s) )' % (goods, bads, skips) | ||||
|
r15136 | |||
|
r15146 | # 'untested' is all cset that are- in 'range', but not in 'pruned' | ||
untested = '( (%s) - (%s) )' % (range, pruned) | ||||
|
r15136 | |||
|
r15147 | # 'ignored' is all csets that were not used during the bisection | ||
# due to DAG topology, but may however have had an impact. | ||||
# Eg., a branch merged between bads and goods, but whose branch- | ||||
# point is out-side of the range. | ||||
iba = '::bisect(bad) - ::bisect(good)' # Ignored bads' ancestors | ||||
iga = '::bisect(good) - ::bisect(bad)' # Ignored goods' ancestors | ||||
ignored = '( ( (%s) | (%s) ) - (%s) )' % (iba, iga, range) | ||||
|
r15136 | if status == 'range': | ||
|
r15146 | return [c.rev() for c in repo.set(range)] | ||
|
r15137 | elif status == 'pruned': | ||
|
r15146 | return [c.rev() for c in repo.set(pruned)] | ||
|
r15138 | elif status == 'untested': | ||
|
r15146 | return [c.rev() for c in repo.set(untested)] | ||
|
r15147 | elif status == 'ignored': | ||
return [c.rev() for c in repo.set(ignored)] | ||||
|
r15153 | elif status == "goods": | ||
return [c.rev() for c in repo.set(goods)] | ||||
elif status == "bads": | ||||
return [c.rev() for c in repo.set(bads)] | ||||
|
r15136 | |||
else: | ||||
raise error.ParseError(_('invalid bisect state')) | ||||
|
r15154 | |||
def label(repo, node, short=False): | ||||
rev = repo.changelog.rev(node) | ||||
# Try explicit sets | ||||
if rev in get(repo, 'good'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r15154 | return _('good') | ||
if rev in get(repo, 'bad'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r15154 | return _('bad') | ||
if rev in get(repo, 'skip'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r15154 | return _('skipped') | ||
if rev in get(repo, 'untested'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r15154 | return _('untested') | ||
if rev in get(repo, 'ignored'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r15154 | return _('ignored') | ||
# Try implicit sets | ||||
if rev in get(repo, 'goods'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r15154 | return _('good (implicit)') | ||
if rev in get(repo, 'bads'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r15154 | return _('bad (implicit)') | ||
return None | ||||
def shortlabel(label): | ||||
if label: | ||||
return label[0].upper() | ||||
return None | ||||