hbisect.py
300 lines
| 10.4 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 | |||
|
r25952 | from __future__ import absolute_import | ||
|
r25113 | import collections | ||
|
r25952 | |||
from .i18n import _ | ||||
from .node import ( | ||||
hex, | ||||
short, | ||||
) | ||||
from . import ( | ||||
error, | ||||
) | ||||
|
r5775 | |||
|
r35126 | def bisect(repo, 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. | ||||
""" | ||||
|
r35126 | changelog = repo.changelog | ||
|
r5775 | clparents = changelog.parentrevs | ||
|
r8152 | skip = set([changelog.rev(n) for n in state['skip']]) | ||
|
r5775 | |||
|
r5776 | def buildancestors(bad, good): | ||
badrev = min([changelog.rev(n) for n in bad]) | ||||
|
r35128 | ancestors = collections.defaultdict(lambda: None) | ||
|
r35127 | for rev in repo.revs("descendants(%ln) - ancestors(%ln)", good, good): | ||
|
r14895 | ancestors[rev] = [] | ||
|
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 | ||
|
r20094 | if (len(state['bad']) == 1 and len(state['good']) == 1 and | ||
state['bad'] != state['good']): | ||||
|
r26587 | raise error.Abort(_("starting revisions are not directly related")) | ||
raise error.Abort(_("inconsistent state, %s:%s is good and bad") | ||||
|
r6217 | % (badrev, short(bad))) | ||
|
r5775 | |||
# build children dict | ||||
children = {} | ||||
|
r25113 | visit = collections.deque([badrev]) | ||
|
r5775 | candidates = [] | ||
while visit: | ||||
|
r16803 | rev = visit.popleft() | ||
|
r5775 | 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: | ||||
|
r30389 | return ([changelog.node(c) for c 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 | |||
|
r30066 | def extendrange(repo, state, nodes, good): | ||
# bisect is incomplete when it ends on a merge node and | ||||
# one of the parent was not checked. | ||||
parents = repo[nodes[0]].parents() | ||||
if len(parents) > 1: | ||||
if good: | ||||
side = state['bad'] | ||||
else: | ||||
side = state['good'] | ||||
num = len(set(i.node() for i in parents) & set(side)) | ||||
if num == 1: | ||||
return parents[0].ancestor(parents[1]) | ||||
return None | ||||
|
r7227 | |||
def load_state(repo): | ||||
|
r16647 | state = {'current': [], 'good': [], 'bad': [], 'skip': []} | ||
|
r27525 | for l in repo.vfs.tryreadlines("bisect.state"): | ||
kind, node = l[:-1].split() | ||||
node = repo.lookup(node) | ||||
if kind not in state: | ||||
raise error.Abort(_("unknown bisect kind %s") % kind) | ||||
state[kind].append(node) | ||||
|
r7227 | return state | ||
def save_state(repo, state): | ||||
|
r23877 | f = repo.vfs("bisect.state", "w", atomictemp=True) | ||
|
r27853 | with repo.wlock(): | ||
|
r18358 | for kind in sorted(state): | ||
|
r7227 | for node in state[kind]: | ||
f.write("%s %s\n" % (kind, hex(node))) | ||||
|
r15057 | f.close() | ||
|
r7227 | |||
|
r30065 | def resetstate(repo): | ||
"""remove any bisect state from the repository""" | ||||
if repo.vfs.exists("bisect.state"): | ||||
repo.vfs.unlink("bisect.state") | ||||
|
r30126 | def checkstate(state): | ||
"""check we have both 'good' and 'bad' to define a range | ||||
Raise Abort exception otherwise.""" | ||||
if state['good'] and state['bad']: | ||||
return True | ||||
if not state['good']: | ||||
raise error.Abort(_('cannot bisect (no known good revisions)')) | ||||
else: | ||||
raise error.Abort(_('cannot bisect (no known bad revisions)')) | ||||
|
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 | ||
|
r17424 | - ``goods``, ``bads`` : csets topologically good/bad | ||
|
r15153 | - ``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 | ||
|
r16647 | - ``current`` : the cset currently being bisected | ||
|
r15135 | """ | ||
state = load_state(repo) | ||||
|
r16647 | if status in ('good', 'bad', 'skip', 'current'): | ||
return map(repo.changelog.rev, state[status]) | ||||
|
r15135 | else: | ||
|
r17493 | # In the following sets, we do *not* call 'bisect()' with more | ||
|
r17509 | # than one level of recursion, because that can be very, very | ||
|
r15146 | # 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 | |||
|
r15404 | _t = repo.revs('bisect(good)::bisect(bad)') | ||
|
r15153 | # 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. | ||||
|
r17424 | # E.g., a branch merged between bads and goods, but whose branch- | ||
|
r15147 | # 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': | ||
|
r15404 | return repo.revs(range) | ||
|
r15137 | elif status == 'pruned': | ||
|
r15404 | return repo.revs(pruned) | ||
|
r15138 | elif status == 'untested': | ||
|
r15404 | return repo.revs(untested) | ||
|
r15147 | elif status == 'ignored': | ||
|
r15404 | return repo.revs(ignored) | ||
|
r15153 | elif status == "goods": | ||
|
r15404 | return repo.revs(goods) | ||
|
r15153 | elif status == "bads": | ||
|
r15404 | return repo.revs(bads) | ||
|
r15136 | else: | ||
raise error.ParseError(_('invalid bisect state')) | ||||
|
r15154 | |||
|
r15406 | def label(repo, node): | ||
|
r15154 | 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') | ||
|
r16647 | if rev in get(repo, 'untested') or rev in get(repo, 'current'): | ||
|
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 | ||||
|
r30067 | |||
def printresult(ui, repo, state, displayer, nodes, good): | ||||
if len(nodes) == 1: | ||||
# narrowed it down to a single revision | ||||
if good: | ||||
ui.write(_("The first good revision is:\n")) | ||||
else: | ||||
ui.write(_("The first bad revision is:\n")) | ||||
displayer.show(repo[nodes[0]]) | ||||
extendnode = extendrange(repo, state, nodes, good) | ||||
if extendnode is not None: | ||||
ui.write(_('Not all ancestors of this changeset have been' | ||||
' checked.\nUse bisect --extend to continue the ' | ||||
'bisection from\nthe common ancestor, %s.\n') | ||||
% extendnode) | ||||
else: | ||||
# multiple possible revisions | ||||
if good: | ||||
ui.write(_("Due to skipped revisions, the first " | ||||
"good revision could be any of:\n")) | ||||
else: | ||||
ui.write(_("Due to skipped revisions, the first " | ||||
"bad revision could be any of:\n")) | ||||
for n in nodes: | ||||
displayer.show(repo[n]) | ||||
displayer.close() | ||||