hbisect.py
118 lines
| 4.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> | ||||
# 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 _ | ||||
|
r6217 | from node import short | ||
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 | ||
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 | ||||
|
r6750 | ancestors = [[]] * (len(changelog) + 1) # an extra for [-1] | ||
|
r5775 | |||
|
r5776 | # clear good revs from array | ||
for node in goodrevs: | ||||
ancestors[node] = None | ||||
|
r6750 | for rev in xrange(len(changelog), -1, -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 | ||
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") | ||
|
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) | ||||
|
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) | ||||
|
r6858 | return ([best_node], tot, good) | ||