|
28
|
1 # changelog bisection for mercurial
|
|
|
2 #
|
|
|
3 # Copyright 2007 Matt Mackall
|
|
|
4 # Copyright 2005, 2006 Benoit Boissinot <benoit.boissinot@ens-lyon.org>
|
|
|
5 #
|
|
|
6 # Inspired by git bisect, extension skeleton taken from mq.py.
|
|
|
7 #
|
|
|
8 # This software may be used and distributed according to the terms of the
|
|
|
9 # GNU General Public License version 2, incorporated herein by reference.
|
|
|
10
|
|
|
11 import os
|
|
|
12 from i18n import _
|
|
|
13 from node import short, hex
|
|
|
14 import util
|
|
|
15
|
|
|
16 def bisect(changelog, state):
|
|
|
17 """find the next node (if any) for testing during a bisect search.
|
|
|
18 returns a (nodes, number, good) tuple.
|
|
|
19
|
|
|
20 'nodes' is the final result of the bisect if 'number' is 0.
|
|
|
21 Otherwise 'number' indicates the remaining possible candidates for
|
|
|
22 the search and 'nodes' contains the next bisect target.
|
|
|
23 'good' is True if bisect is searching for a first good changeset, False
|
|
|
24 if searching for a first bad one.
|
|
|
25 """
|
|
|
26
|
|
|
27 clparents = changelog.parentrevs
|
|
|
28 skip = set([changelog.rev(n) for n in state['skip']])
|
|
|
29
|
|
|
30 def buildancestors(bad, good):
|
|
|
31 # only the earliest bad revision matters
|
|
|
32 badrev = min([changelog.rev(n) for n in bad])
|
|
|
33 goodrevs = [changelog.rev(n) for n in good]
|
|
|
34 # build ancestors array
|
|
|
35 ancestors = [[]] * (len(changelog) + 1) # an extra for [-1]
|
|
|
36
|
|
|
37 # clear good revs from array
|
|
|
38 for node in goodrevs:
|
|
|
39 ancestors[node] = None
|
|
|
40 for rev in xrange(len(changelog), -1, -1):
|
|
|
41 if ancestors[rev] is None:
|
|
|
42 for prev in clparents(rev):
|
|
|
43 ancestors[prev] = None
|
|
|
44
|
|
|
45 if ancestors[badrev] is None:
|
|
|
46 return badrev, None
|
|
|
47 return badrev, ancestors
|
|
|
48
|
|
|
49 good = 0
|
|
|
50 badrev, ancestors = buildancestors(state['bad'], state['good'])
|
|
|
51 if not ancestors: # looking for bad to good transition?
|
|
|
52 good = 1
|
|
|
53 badrev, ancestors = buildancestors(state['good'], state['bad'])
|
|
|
54 bad = changelog.node(badrev)
|
|
|
55 if not ancestors: # now we're confused
|
|
|
56 raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
|
|
|
57 % (badrev, short(bad)))
|
|
|
58
|
|
|
59 # build children dict
|
|
|
60 children = {}
|
|
|
61 visit = [badrev]
|
|
|
62 candidates = []
|
|
|
63 while visit:
|
|
|
64 rev = visit.pop(0)
|
|
|
65 if ancestors[rev] == []:
|
|
|
66 candidates.append(rev)
|
|
|
67 for prev in clparents(rev):
|
|
|
68 if prev != -1:
|
|
|
69 if prev in children:
|
|
|
70 children[prev].append(rev)
|
|
|
71 else:
|
|
|
72 children[prev] = [rev]
|
|
|
73 visit.append(prev)
|
|
|
74
|
|
|
75 candidates.sort()
|
|
|
76 # have we narrowed it down to one entry?
|
|
|
77 # or have all other possible candidates besides 'bad' have been skipped?
|
|
|
78 tot = len(candidates)
|
|
|
79 unskipped = [c for c in candidates if (c not in skip) and (c != badrev)]
|
|
|
80 if tot == 1 or not unskipped:
|
|
|
81 return ([changelog.node(rev) for rev in candidates], 0, good)
|
|
|
82 perfect = tot // 2
|
|
|
83
|
|
|
84 # find the best node to test
|
|
|
85 best_rev = None
|
|
|
86 best_len = -1
|
|
|
87 poison = set()
|
|
|
88 for rev in candidates:
|
|
|
89 if rev in poison:
|
|
|
90 # poison children
|
|
|
91 poison.update(children.get(rev, []))
|
|
|
92 continue
|
|
|
93
|
|
|
94 a = ancestors[rev] or [rev]
|
|
|
95 ancestors[rev] = None
|
|
|
96
|
|
|
97 x = len(a) # number of ancestors
|
|
|
98 y = tot - x # number of non-ancestors
|
|
|
99 value = min(x, y) # how good is this test?
|
|
|
100 if value > best_len and rev not in skip:
|
|
|
101 best_len = value
|
|
|
102 best_rev = rev
|
|
|
103 if value == perfect: # found a perfect candidate? quit early
|
|
|
104 break
|
|
|
105
|
|
|
106 if y < perfect and rev not in skip: # all downhill from here?
|
|
|
107 # poison children
|
|
|
108 poison.update(children.get(rev, []))
|
|
|
109 continue
|
|
|
110
|
|
|
111 for c in children.get(rev, []):
|
|
|
112 if ancestors[c]:
|
|
|
113 ancestors[c] = list(set(ancestors[c] + a))
|
|
|
114 else:
|
|
|
115 ancestors[c] = a + [c]
|
|
|
116
|
|
|
117 assert best_rev is not None
|
|
|
118 best_node = changelog.node(best_rev)
|
|
|
119
|
|
|
120 return ([best_node], tot, good)
|
|
|
121
|
|
|
122
|
|
|
123 def load_state(repo):
|
|
|
124 state = {'good': [], 'bad': [], 'skip': []}
|
|
|
125 if os.path.exists(repo.join("bisect.state")):
|
|
|
126 for l in repo.opener("bisect.state"):
|
|
|
127 kind, node = l[:-1].split()
|
|
|
128 node = repo.lookup(node)
|
|
|
129 if kind not in state:
|
|
|
130 raise util.Abort(_("unknown bisect kind %s") % kind)
|
|
|
131 state[kind].append(node)
|
|
|
132 return state
|
|
|
133
|
|
|
134
|
|
|
135 def save_state(repo, state):
|
|
|
136 f = repo.opener("bisect.state", "w", atomictemp=True)
|
|
|
137 wlock = repo.wlock()
|
|
|
138 try:
|
|
|
139 for kind in state:
|
|
|
140 for node in state[kind]:
|
|
|
141 f.write("%s %s\n" % (kind, hex(node)))
|
|
|
142 f.rename()
|
|
|
143 finally:
|
|
|
144 wlock.release()
|
|
|
145
|
