Mercurial > hg
view mercurial/hbisect.py @ 5775:2dd202a6e15b
bisect: make bisect a built-in command
author | Matt Mackall <mpm@selenic.com> |
---|---|
date | Mon, 31 Dec 2007 18:20:34 -0600 |
parents | hgext/hbisect.py@c850a8640981 |
children | 35ec669cdd43 |
line wrap: on
line source
# 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 # only the earliest bad revision matters badrev = min([changelog.rev(n) for n in state['bad']]) bad = changelog.node(badrev) skip = dict.fromkeys([changelog.rev(n) for n in state['skip']]) # build ancestors array ancestors = [[]] * (changelog.count() + 1) # an extra for [-1] # clear good revs from array for node in state['good']: ancestors[changelog.rev(node)] = None for rev in xrange(changelog.count(), -1, -1): if ancestors[rev] is None: for prev in clparents(rev): ancestors[prev] = None if ancestors[badrev] is None: 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: return (bad, 0) 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) return (best_node, tot)