equal
deleted
inserted
replaced
10 from i18n import _ |
10 from i18n import _ |
11 from node import short |
11 from node import short |
12 import util |
12 import util |
13 |
13 |
14 def bisect(changelog, state): |
14 def bisect(changelog, state): |
|
15 """find the next node (if any) for testing during a bisect search. |
|
16 returns a (nodes, number, good) tuple. |
|
17 |
|
18 'nodes' is the final result of the bisect if 'number' is 0. |
|
19 Otherwise 'number' indicates the remaining possible candidates for |
|
20 the search and 'nodes' contains the next bisect target. |
|
21 'good' is True if bisect is searching for a first good changeset, False |
|
22 if searching for a first bad one. |
|
23 """ |
|
24 |
15 clparents = changelog.parentrevs |
25 clparents = changelog.parentrevs |
16 skip = dict.fromkeys([changelog.rev(n) for n in state['skip']]) |
26 skip = dict.fromkeys([changelog.rev(n) for n in state['skip']]) |
17 |
27 |
18 def buildancestors(bad, good): |
28 def buildancestors(bad, good): |
19 # only the earliest bad revision matters |
29 # only the earliest bad revision matters |
58 children[prev].append(rev) |
68 children[prev].append(rev) |
59 else: |
69 else: |
60 children[prev] = [rev] |
70 children[prev] = [rev] |
61 visit.append(prev) |
71 visit.append(prev) |
62 |
72 |
|
73 candidates.sort() |
63 # have we narrowed it down to one entry? |
74 # have we narrowed it down to one entry? |
|
75 # or have all other possible candidates besides 'bad' have been skipped? |
64 tot = len(candidates) |
76 tot = len(candidates) |
65 if tot == 1: |
77 unskipped = [c for c in candidates if (c not in skip) and (c != badrev)] |
66 return (bad, 0, good) |
78 if tot == 1 or not unskipped: |
|
79 return ([changelog.node(rev) for rev in candidates], 0, good) |
67 perfect = tot / 2 |
80 perfect = tot / 2 |
68 |
81 |
69 # find the best node to test |
82 # find the best node to test |
70 best_rev = None |
83 best_rev = None |
71 best_len = -1 |
84 best_len = -1 |
72 poison = {} |
85 poison = {} |
73 for rev in util.sort(candidates): |
86 for rev in candidates: |
74 if rev in poison: |
87 if rev in poison: |
75 for c in children.get(rev, []): |
88 for c in children.get(rev, []): |
76 poison[c] = True # poison children |
89 poison[c] = True # poison children |
77 continue |
90 continue |
78 |
91 |
100 ancestors[c] = a + [c] |
113 ancestors[c] = a + [c] |
101 |
114 |
102 assert best_rev is not None |
115 assert best_rev is not None |
103 best_node = changelog.node(best_rev) |
116 best_node = changelog.node(best_rev) |
104 |
117 |
105 return (best_node, tot, good) |
118 return ([best_node], tot, good) |