hbisect.py
328 lines
| 10.8 KiB
| text/x-python
|
PythonLexer
/ mercurial / hbisect.py
|
r5775 | # changelog bisection for mercurial | ||
# | ||||
|
r47575 | # Copyright 2007 Olivia Mackall | ||
|
r5775 | # 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 | |||
|
r25113 | import collections | ||
|
r44064 | import contextlib | ||
|
r25952 | |||
from .i18n import _ | ||||
from .node import ( | ||||
hex, | ||||
short, | ||||
) | ||||
|
r43346 | 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. | ||||
""" | ||||
|
r42501 | repo = repo.unfiltered() | ||
|
r35126 | changelog = repo.changelog | ||
|
r5775 | clparents = changelog.parentrevs | ||
|
r43347 | skip = {changelog.rev(n) for n in state[b'skip']} | ||
|
r5775 | |||
|
r5776 | def buildancestors(bad, good): | ||
badrev = min([changelog.rev(n) for n in bad]) | ||||
|
r35128 | ancestors = collections.defaultdict(lambda: None) | ||
|
r50336 | for rev in repo.revs(b"(%ln::%d) - (::%ln)", good, badrev, good): | ||
|
r14895 | ancestors[rev] = [] | ||
|
r5776 | if ancestors[badrev] is None: | ||
|
r5777 | return badrev, None | ||
|
r5776 | return badrev, ancestors | ||
|
r14215 | good = False | ||
|
r43347 | badrev, ancestors = buildancestors(state[b'bad'], state[b'good']) | ||
|
r43346 | if not ancestors: # looking for bad to good transition? | ||
|
r14215 | good = True | ||
|
r43347 | badrev, ancestors = buildancestors(state[b'good'], state[b'bad']) | ||
|
r5777 | bad = changelog.node(badrev) | ||
|
r43346 | if not ancestors: # now we're confused | ||
if ( | ||||
|
r43347 | len(state[b'bad']) == 1 | ||
and len(state[b'good']) == 1 | ||||
and state[b'bad'] != state[b'good'] | ||||
|
r43346 | ): | ||
|
r43347 | raise error.Abort(_(b"starting revisions are not directly related")) | ||
|
r43346 | raise error.Abort( | ||
|
r43347 | _(b"inconsistent state, %d:%s is good and bad") | ||
|
r43346 | % (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 | ||||
|
r43346 | x = len(a) # number of ancestors | ||
y = tot - x # number of non-ancestors | ||||
value = min(x, y) # how good is this test? | ||||
|
r5775 | if value > best_len and rev not in skip: | ||
best_len = value | ||||
best_rev = rev | ||||
|
r43346 | if value == perfect: # found a perfect candidate? quit early | ||
|
r5775 | break | ||
|
r43346 | 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 | |||
|
r43346 | |||
|
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: | ||||
|
r43347 | side = state[b'bad'] | ||
|
r30066 | else: | ||
|
r43347 | side = state[b'good'] | ||
|
r44937 | num = len({i.node() for i in parents} & set(side)) | ||
|
r30066 | if num == 1: | ||
return parents[0].ancestor(parents[1]) | ||||
return None | ||||
|
r7227 | |||
|
r43346 | |||
|
r7227 | def load_state(repo): | ||
|
r43347 | state = {b'current': [], b'good': [], b'bad': [], b'skip': []} | ||
for l in repo.vfs.tryreadlines(b"bisect.state"): | ||||
|
r27525 | kind, node = l[:-1].split() | ||
|
r42501 | node = repo.unfiltered().lookup(node) | ||
|
r27525 | if kind not in state: | ||
|
r43347 | raise error.Abort(_(b"unknown bisect kind %s") % kind) | ||
|
r27525 | state[kind].append(node) | ||
|
r7227 | return state | ||
def save_state(repo, state): | ||||
|
r43347 | f = repo.vfs(b"bisect.state", b"w", atomictemp=True) | ||
|
r27853 | with repo.wlock(): | ||
|
r18358 | for kind in sorted(state): | ||
|
r7227 | for node in state[kind]: | ||
|
r43347 | f.write(b"%s %s\n" % (kind, hex(node))) | ||
|
r15057 | f.close() | ||
|
r7227 | |||
|
r43346 | |||
|
r30065 | def resetstate(repo): | ||
"""remove any bisect state from the repository""" | ||||
|
r43347 | if repo.vfs.exists(b"bisect.state"): | ||
repo.vfs.unlink(b"bisect.state") | ||||
|
r30065 | |||
|
r43346 | |||
|
r30126 | def checkstate(state): | ||
"""check we have both 'good' and 'bad' to define a range | ||||
|
r46487 | Raise StateError exception otherwise.""" | ||
|
r43347 | if state[b'good'] and state[b'bad']: | ||
|
r30126 | return True | ||
|
r43347 | if not state[b'good']: | ||
|
r46487 | raise error.StateError(_(b'cannot bisect (no known good revisions)')) | ||
|
r30126 | else: | ||
|
r46487 | raise error.StateError(_(b'cannot bisect (no known bad revisions)')) | ||
|
r30126 | |||
|
r43346 | |||
|
r44064 | @contextlib.contextmanager | ||
def restore_state(repo, state, node): | ||||
try: | ||||
yield | ||||
finally: | ||||
state[b'current'] = [node] | ||||
save_state(repo, state) | ||||
|
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) | ||||
|
r43347 | if status in (b'good', b'bad', b'skip', b'current'): | ||
|
r42501 | return map(repo.unfiltered().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 | ||||
|
r43347 | range = b'( bisect(bad)::bisect(good) | bisect(good)::bisect(bad) )' | ||
|
r15136 | |||
|
r43347 | _t = repo.revs(b'bisect(good)::bisect(bad)') | ||
|
r15153 | # The sets of topologically good or bad csets | ||
if len(_t) == 0: | ||||
# Goods are topologically after bads | ||||
|
r43347 | goods = b'bisect(good)::' # Pruned good csets | ||
bads = b'::bisect(bad)' # Pruned bad csets | ||||
|
r15153 | else: | ||
# Goods are topologically before bads | ||||
|
r43347 | goods = b'::bisect(good)' # Pruned good csets | ||
bads = b'bisect(bad)::' # Pruned bad csets | ||||
|
r15153 | |||
# 'pruned' is all csets whose fate is already known: good, bad, skip | ||||
|
r43347 | skips = b'bisect(skip)' # Pruned skipped csets | ||
pruned = b'( (%s) | (%s) | (%s) )' % (goods, bads, skips) | ||||
|
r15136 | |||
|
r15146 | # 'untested' is all cset that are- in 'range', but not in 'pruned' | ||
|
r43347 | untested = b'( (%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. | ||
|
r43347 | iba = b'::bisect(bad) - ::bisect(good)' # Ignored bads' ancestors | ||
iga = b'::bisect(good) - ::bisect(bad)' # Ignored goods' ancestors | ||||
ignored = b'( ( (%s) | (%s) ) - (%s) )' % (iba, iga, range) | ||||
|
r15147 | |||
|
r43347 | if status == b'range': | ||
|
r15404 | return repo.revs(range) | ||
|
r43347 | elif status == b'pruned': | ||
|
r15404 | return repo.revs(pruned) | ||
|
r43347 | elif status == b'untested': | ||
|
r15404 | return repo.revs(untested) | ||
|
r43347 | elif status == b'ignored': | ||
|
r15404 | return repo.revs(ignored) | ||
|
r43347 | elif status == b"goods": | ||
|
r15404 | return repo.revs(goods) | ||
|
r43347 | elif status == b"bads": | ||
|
r15404 | return repo.revs(bads) | ||
|
r15136 | else: | ||
|
r43347 | raise error.ParseError(_(b'invalid bisect state')) | ||
|
r15154 | |||
|
r43346 | |||
|
r15406 | def label(repo, node): | ||
|
r15154 | rev = repo.changelog.rev(node) | ||
# Try explicit sets | ||||
|
r43347 | if rev in get(repo, b'good'): | ||
|
r15308 | # i18n: bisect changeset status | ||
|
r43347 | return _(b'good') | ||
if rev in get(repo, b'bad'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r43347 | return _(b'bad') | ||
if rev in get(repo, b'skip'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r43347 | return _(b'skipped') | ||
if rev in get(repo, b'untested') or rev in get(repo, b'current'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r43347 | return _(b'untested') | ||
if rev in get(repo, b'ignored'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r43347 | return _(b'ignored') | ||
|
r15154 | |||
# Try implicit sets | ||||
|
r43347 | if rev in get(repo, b'goods'): | ||
|
r15308 | # i18n: bisect changeset status | ||
|
r43347 | return _(b'good (implicit)') | ||
if rev in get(repo, b'bads'): | ||||
|
r15308 | # i18n: bisect changeset status | ||
|
r43347 | return _(b'bad (implicit)') | ||
|
r15154 | |||
return None | ||||
|
r43346 | |||
|
r30067 | def printresult(ui, repo, state, displayer, nodes, good): | ||
|
r42501 | repo = repo.unfiltered() | ||
|
r30067 | if len(nodes) == 1: | ||
# narrowed it down to a single revision | ||||
if good: | ||||
|
r43347 | ui.write(_(b"The first good revision is:\n")) | ||
|
r30067 | else: | ||
|
r43347 | ui.write(_(b"The first bad revision is:\n")) | ||
|
r30067 | displayer.show(repo[nodes[0]]) | ||
extendnode = extendrange(repo, state, nodes, good) | ||||
if extendnode is not None: | ||||
|
r43346 | ui.write( | ||
_( | ||||
|
r43347 | b'Not all ancestors of this changeset have been' | ||
b' checked.\nUse bisect --extend to continue the ' | ||||
b'bisection from\nthe common ancestor, %s.\n' | ||||
|
r43346 | ) | ||
% extendnode | ||||
) | ||||
|
r30067 | else: | ||
# multiple possible revisions | ||||
if good: | ||||
|
r43346 | ui.write( | ||
_( | ||||
|
r43347 | b"Due to skipped revisions, the first " | ||
b"good revision could be any of:\n" | ||||
|
r43346 | ) | ||
) | ||||
|
r30067 | else: | ||
|
r43346 | ui.write( | ||
_( | ||||
|
r43347 | b"Due to skipped revisions, the first " | ||
b"bad revision could be any of:\n" | ||||
|
r43346 | ) | ||
) | ||||
|
r30067 | for n in nodes: | ||
displayer.show(repo[n]) | ||||
displayer.close() | ||||