|
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 or any later version. |
|
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 goodrev = min(goodrevs) |
|
35 # build visit array |
|
36 ancestors = [None] * (len(changelog) + 1) # an extra for [-1] |
|
37 |
|
38 # set nodes descended from goodrev |
|
39 ancestors[goodrev] = [] |
|
40 for rev in xrange(goodrev + 1, len(changelog)): |
|
41 for prev in clparents(rev): |
|
42 if ancestors[prev] == []: |
|
43 ancestors[rev] = [] |
|
44 |
|
45 # clear good revs from array |
|
46 for node in goodrevs: |
|
47 ancestors[node] = None |
|
48 for rev in xrange(len(changelog), -1, -1): |
|
49 if ancestors[rev] is None: |
|
50 for prev in clparents(rev): |
|
51 ancestors[prev] = None |
|
52 |
|
53 if ancestors[badrev] is None: |
|
54 return badrev, None |
|
55 return badrev, ancestors |
|
56 |
|
57 good = 0 |
|
58 badrev, ancestors = buildancestors(state['bad'], state['good']) |
|
59 if not ancestors: # looking for bad to good transition? |
|
60 good = 1 |
|
61 badrev, ancestors = buildancestors(state['good'], state['bad']) |
|
62 bad = changelog.node(badrev) |
|
63 if not ancestors: # now we're confused |
|
64 if len(state['bad']) == 1 and len(state['good']) == 1: |
|
65 raise util.Abort(_("starting revisions are not directly related")) |
|
66 raise util.Abort(_("inconsistent state, %s:%s is good and bad") |
|
67 % (badrev, short(bad))) |
|
68 |
|
69 # build children dict |
|
70 children = {} |
|
71 visit = [badrev] |
|
72 candidates = [] |
|
73 while visit: |
|
74 rev = visit.pop(0) |
|
75 if ancestors[rev] == []: |
|
76 candidates.append(rev) |
|
77 for prev in clparents(rev): |
|
78 if prev != -1: |
|
79 if prev in children: |
|
80 children[prev].append(rev) |
|
81 else: |
|
82 children[prev] = [rev] |
|
83 visit.append(prev) |
|
84 |
|
85 candidates.sort() |
|
86 # have we narrowed it down to one entry? |
|
87 # or have all other possible candidates besides 'bad' have been skipped? |
|
88 tot = len(candidates) |
|
89 unskipped = [c for c in candidates if (c not in skip) and (c != badrev)] |
|
90 if tot == 1 or not unskipped: |
|
91 return ([changelog.node(rev) for rev in candidates], 0, good) |
|
92 perfect = tot // 2 |
|
93 |
|
94 # find the best node to test |
|
95 best_rev = None |
|
96 best_len = -1 |
|
97 poison = set() |
|
98 for rev in candidates: |
|
99 if rev in poison: |
|
100 # poison children |
|
101 poison.update(children.get(rev, [])) |
|
102 continue |
|
103 |
|
104 a = ancestors[rev] or [rev] |
|
105 ancestors[rev] = None |
|
106 |
|
107 x = len(a) # number of ancestors |
|
108 y = tot - x # number of non-ancestors |
|
109 value = min(x, y) # how good is this test? |
|
110 if value > best_len and rev not in skip: |
|
111 best_len = value |
|
112 best_rev = rev |
|
113 if value == perfect: # found a perfect candidate? quit early |
|
114 break |
|
115 |
|
116 if y < perfect and rev not in skip: # all downhill from here? |
|
117 # poison children |
|
118 poison.update(children.get(rev, [])) |
|
119 continue |
|
120 |
|
121 for c in children.get(rev, []): |
|
122 if ancestors[c]: |
|
123 ancestors[c] = list(set(ancestors[c] + a)) |
|
124 else: |
|
125 ancestors[c] = a + [c] |
|
126 |
|
127 assert best_rev is not None |
|
128 best_node = changelog.node(best_rev) |
|
129 |
|
130 return ([best_node], tot, good) |
|
131 |
|
132 |
|
133 def load_state(repo): |
|
134 state = {'good': [], 'bad': [], 'skip': []} |
|
135 if os.path.exists(repo.join("bisect.state")): |
|
136 for l in repo.opener("bisect.state"): |
|
137 kind, node = l[:-1].split() |
|
138 node = repo.lookup(node) |
|
139 if kind not in state: |
|
140 raise util.Abort(_("unknown bisect kind %s") % kind) |
|
141 state[kind].append(node) |
|
142 return state |
|
143 |
|
144 |
|
145 def save_state(repo, state): |
|
146 f = repo.opener("bisect.state", "w", atomictemp=True) |
|
147 wlock = repo.wlock() |
|
148 try: |
|
149 for kind in state: |
|
150 for node in state[kind]: |
|
151 f.write("%s %s\n" % (kind, hex(node))) |
|
152 f.rename() |
|
153 finally: |
|
154 wlock.release() |
|
155 |