64 #self.ui.write("Going back to tip\n") |
64 #self.ui.write("Going back to tip\n") |
65 #self.repo.update(self.repo.changelog.tip()) |
65 #self.repo.update(self.repo.changelog.tip()) |
66 self.is_reset = True |
66 self.is_reset = True |
67 return 0 |
67 return 0 |
68 |
68 |
69 def candidates(self): |
69 def bisect(self): |
70 """ |
|
71 returns (anc, n_child) where anc is the set of the ancestors of head |
|
72 and n_child is a dictionary with the following mapping: |
|
73 node -> number of ancestors (self included) |
|
74 |
|
75 ancestors of goodnodes are used as lower limit. |
|
76 """ |
|
77 cl = self.repo.changelog |
70 cl = self.repo.changelog |
78 clparents = cl.parentrevs |
71 clparents = cl.parentrevs |
79 bad = self.badnode |
72 bad = self.badnode |
80 badrev = cl.rev(bad) |
73 badrev = cl.rev(bad) |
81 |
74 |
82 # add goodrevs and all ancestors to stop |
75 if not bad: |
83 stop = dict.fromkeys([cl.rev(n) for n in self.goodnodes]) |
|
84 for rev in xrange(cl.count(), -1, -1): |
|
85 if rev in stop: |
|
86 for prev in clparents(rev): |
|
87 stop[prev] = None |
|
88 |
|
89 if badrev in stop: |
|
90 raise util.Abort(_("Inconsistent state, %s:%s is good and bad") |
|
91 % (badrev, hg.short(bad))) |
|
92 |
|
93 # build a dict of node -> {ancestors} |
|
94 ancestors = {} |
|
95 count = {} |
|
96 for rev in xrange(badrev + 1): |
|
97 if not rev in stop: |
|
98 ancestors[rev] = {rev: 1} |
|
99 for p in clparents(rev): |
|
100 if not p in stop: |
|
101 # add parent ancestors to our ancestors |
|
102 ancestors[rev].update(ancestors[p]) |
|
103 count[rev] = len(ancestors[rev]) |
|
104 |
|
105 if badrev not in ancestors[badrev]: |
|
106 raise util.Abort(_("Could not find the first bad revision")) |
|
107 |
|
108 return ancestors[badrev], count |
|
109 |
|
110 def next(self): |
|
111 if not self.badnode: |
|
112 raise util.Abort(_("You should give at least one bad revision")) |
76 raise util.Abort(_("You should give at least one bad revision")) |
113 if not self.goodnodes: |
77 if not self.goodnodes: |
114 self.ui.warn(_("No good revision given\n")) |
78 self.ui.warn(_("No good revision given\n")) |
115 self.ui.warn(_("Marking the first revision as good\n")) |
79 self.ui.warn(_("Marking the first revision as good\n")) |
116 ancestors, count = self.candidates() |
80 |
|
81 # build ancestors array |
|
82 ancestors = [{}] * (cl.count() + 1) # an extra for [-1] |
|
83 |
|
84 # clear goodnodes from array |
|
85 for good in self.goodnodes: |
|
86 ancestors[cl.rev(good)] = None |
|
87 for rev in xrange(cl.count(), -1, -1): |
|
88 if ancestors[rev] is None: |
|
89 for prev in clparents(rev): |
|
90 ancestors[prev] = None |
|
91 |
|
92 if ancestors[badrev] is None: |
|
93 raise util.Abort(_("Inconsistent state, %s:%s is good and bad") |
|
94 % (badrev, hg.short(bad))) |
|
95 |
|
96 # accumulate ancestor lists |
|
97 for rev in xrange(badrev + 1): |
|
98 if ancestors[rev] == {}: |
|
99 ancestors[rev] = {rev: 1} |
|
100 for p in clparents(rev): |
|
101 if ancestors[p]: |
|
102 # add parent ancestors to our ancestors |
|
103 ancestors[rev].update(ancestors[p]) |
|
104 |
|
105 if badrev not in ancestors[badrev]: |
|
106 raise util.Abort(_("Could not find the first bad revision")) |
117 |
107 |
118 # have we narrowed it down to one entry? |
108 # have we narrowed it down to one entry? |
119 tot = len(ancestors) |
109 tot = len(ancestors[badrev]) |
120 if tot == 1: |
110 if tot == 1: |
121 self.ui.write(_("The first bad revision is:\n")) |
111 self.ui.write(_("The first bad revision is:\n")) |
122 displayer = cmdutil.show_changeset(self.ui, self.repo, {}) |
112 displayer = cmdutil.show_changeset(self.ui, self.repo, {}) |
123 displayer.show(changenode=self.badnode) |
113 displayer.show(changenode=self.badnode) |
124 return None |
114 return None |
125 |
115 |
126 # find the best node to test |
116 # find the best node to test |
127 best_rev = None |
117 best_rev = None |
128 best_len = -1 |
118 best_len = -1 |
129 for n in ancestors: |
119 for n in ancestors[badrev]: |
130 a = count[n] # number of ancestors |
120 a = len(ancestors[n]) # number of ancestors |
131 b = tot - a # number of non-ancestors |
121 b = tot - a # number of non-ancestors |
132 value = min(a, b) # how good is this test? |
122 value = min(a, b) # how good is this test? |
133 if value > best_len: |
123 if value > best_len: |
134 best_len = value |
124 best_len = value |
135 best_rev = n |
125 best_rev = n |
136 assert best_rev is not None |
126 assert best_rev is not None |
137 best_node = self.repo.changelog.node(best_rev) |
127 best_node = cl.node(best_rev) |
138 |
128 |
139 # compute the approximate number of remaining tests |
129 # compute the approximate number of remaining tests |
140 nb_tests = 0 |
130 nb_tests = 0 |
141 q, r = divmod(tot, 2) |
131 q, r = divmod(tot, 2) |
142 while q: |
132 while q: |