Mercurial > hg > mercurial-source

comparison mercurial/hbisect.py @ 5775:2dd202a6e15b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
5774:c850a8640981 5775:2dd202a6e15b
1 # changelog bisection for mercurial
2 #
3 # Copyright 2007 Matt Mackall
4 # Copyright 2005, 2006 Benoit Boissinot <benoit.boissinot@ens-lyon.org>
5 # Inspired by git bisect, extension skeleton taken from mq.py.
6 #
7 # This software may be used and distributed according to the terms
8 # of the GNU General Public License, incorporated herein by reference.
9
10 from i18n import _
11 import hg, util
12
13 def bisect(changelog, state):
14 clparents = changelog.parentrevs
15 # only the earliest bad revision matters
16 badrev = min([changelog.rev(n) for n in state['bad']])
17 bad = changelog.node(badrev)
18 skip = dict.fromkeys([changelog.rev(n) for n in state['skip']])
19
20 # build ancestors array
21 ancestors = [[]] * (changelog.count() + 1) # an extra for [-1]
22
23 # clear good revs from array
24 for node in state['good']:
25 ancestors[changelog.rev(node)] = None
26 for rev in xrange(changelog.count(), -1, -1):
27 if ancestors[rev] is None:
28 for prev in clparents(rev):
29 ancestors[prev] = None
30
31 if ancestors[badrev] is None:
32 raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
33 % (badrev, hg.short(bad)))
34
35 # build children dict
36 children = {}
37 visit = [badrev]
38 candidates = []
39 while visit:
40 rev = visit.pop(0)
41 if ancestors[rev] == []:
42 candidates.append(rev)
43 for prev in clparents(rev):
44 if prev != -1:
45 if prev in children:
46 children[prev].append(rev)
47 else:
48 children[prev] = [rev]
49 visit.append(prev)
50
51 candidates.sort()
52 # have we narrowed it down to one entry?
53 tot = len(candidates)
54 if tot == 1:
55 return (bad, 0)
56 perfect = tot / 2
57
58 # find the best node to test
59 best_rev = None
60 best_len = -1
61 poison = {}
62 for rev in candidates:
63 if rev in poison:
64 for c in children.get(rev, []):
65 poison[c] = True # poison children
66 continue
67
68 a = ancestors[rev] or [rev]
69 ancestors[rev] = None
70
71 x = len(a) # number of ancestors
72 y = tot - x # number of non-ancestors
73 value = min(x, y) # how good is this test?
74 if value > best_len and rev not in skip:
75 best_len = value
76 best_rev = rev
77 if value == perfect: # found a perfect candidate? quit early
78 break
79
80 if y < perfect: # all downhill from here?
81 for c in children.get(rev, []):
82 poison[c] = True # poison children
83 continue
84
85 for c in children.get(rev, []):
86 if ancestors[c]:
87 ancestors[c] = dict.fromkeys(ancestors[c] + a).keys()
88 else:
89 ancestors[c] = a + [c]
90
91 assert best_rev is not None
92 best_node = changelog.node(best_rev)
93
94 return (best_node, tot)