6 # This software may be used and distributed according to the terms |
6 # This software may be used and distributed according to the terms |
7 # of the GNU General Public License, incorporated herein by reference. |
7 # of the GNU General Public License, incorporated herein by reference. |
8 |
8 |
9 from mercurial.i18n import _ |
9 from mercurial.i18n import _ |
10 from mercurial import hg, util, commands, cmdutil |
10 from mercurial import hg, util, commands, cmdutil |
11 import os, sys, sets |
11 import os, sys |
12 |
12 |
13 class bisect(object): |
13 class bisect(object): |
14 """dichotomic search in the DAG of changesets""" |
14 """dichotomic search in the DAG of changesets""" |
15 def __init__(self, ui, repo): |
15 def __init__(self, ui, repo): |
16 self.repo = repo |
16 self.repo = repo |
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 __ancestors_and_nb_ancestors(self, head, stop=None): |
69 def __ancestors_and_nb_ancestors(self, head): |
70 """ |
70 """ |
71 returns (anc, n_child) where anc is the set of the ancestors of head |
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: |
72 and n_child is a dictionary with the following mapping: |
73 node -> number of ancestors (self included) |
73 node -> number of ancestors (self included) |
74 |
74 |
75 ancestors of goodrevs are used as lower limit. |
75 ancestors of goodrevs are used as lower limit. |
76 """ |
76 """ |
77 cl = self.repo.changelog |
77 cl = self.repo.changelog |
78 if not stop: |
78 stop = {} |
79 stop = sets.Set([]) |
79 for i in xrange(len(self.goodrevs)-1, -1, -1): |
80 for i in xrange(len(self.goodrevs)-1, -1, -1): |
80 g = self.goodrevs[i] |
81 g = self.goodrevs[i] |
81 if g in stop: |
82 if g in stop: |
82 continue |
83 continue |
83 stop.update(cl.reachable(g)) |
84 stop.update(cl.reachable(g)) |
84 |
85 def num_children(a): |
85 def num_children(a): |
86 """ |
86 """ |
87 returns a dictionnary with the following mapping |
87 returns a dictionary with the following mapping |
88 node -> [number of children, empty set] |
88 node -> [number of children, empty set] |
89 """ |
89 """ |
90 d = {a: [0, sets.Set([])]} |
90 d = {a: [0, {}]} |
91 for i in xrange(cl.rev(a)+1): |
91 for i in xrange(cl.rev(a)+1): |
92 n = cl.node(i) |
92 n = cl.node(i) |
93 if not d.has_key(n): |
93 if n not in d: |
94 d[n] = [0, sets.Set([])] |
94 d[n] = [0, {}] |
95 parents = [p for p in cl.parents(n) if p != hg.nullid] |
95 parents = [p for p in cl.parents(n) if p != hg.nullid] |
96 for p in parents: |
96 for p in parents: |
97 d[p][0] += 1 |
97 d[p][0] += 1 |
98 return d |
98 return d |
99 |
99 |
105 n = cl.node(i) |
105 n = cl.node(i) |
106 parents = [p for p in cl.parents(n) if p != hg.nullid] |
106 parents = [p for p in cl.parents(n) if p != hg.nullid] |
107 for p in parents: |
107 for p in parents: |
108 n_child[p][0] -= 1 |
108 n_child[p][0] -= 1 |
109 if not n in stop: |
109 if not n in stop: |
110 n_child[n][1].union_update(n_child[p][1]) |
110 n_child[n][1].update(n_child[p][1]) |
111 if n_child[p][0] == 0: |
111 if n_child[p][0] == 0: |
112 n_child[p] = len(n_child[p][1]) |
112 n_child[p] = len(n_child[p][1]) |
113 if not n in stop: |
113 if not n in stop: |
114 n_child[n][1].add(n) |
114 n_child[n][1][n] = 1 |
115 if n_child[n][0] == 0: |
115 if n_child[n][0] == 0: |
116 if n == head: |
116 if n == head: |
117 anc = n_child[n][1] |
117 anc = n_child[n][1] |
118 n_child[n] = len(n_child[n][1]) |
118 n_child[n] = len(n_child[n][1]) |
119 return anc, n_child |
119 return anc, n_child |
126 self.ui.warn(_("Marking the first revision as good\n")) |
126 self.ui.warn(_("Marking the first revision as good\n")) |
127 ancestors, num_ancestors = self.__ancestors_and_nb_ancestors( |
127 ancestors, num_ancestors = self.__ancestors_and_nb_ancestors( |
128 self.badrev) |
128 self.badrev) |
129 tot = len(ancestors) |
129 tot = len(ancestors) |
130 if tot == 1: |
130 if tot == 1: |
131 if ancestors.pop() != self.badrev: |
131 if self.badrev not in ancestors: |
132 raise util.Abort(_("Could not find the first bad revision")) |
132 raise util.Abort(_("Could not find the first bad revision")) |
133 self.ui.write(_("The first bad revision is:\n")) |
133 self.ui.write(_("The first bad revision is:\n")) |
134 displayer = cmdutil.show_changeset(self.ui, self.repo, {}) |
134 displayer = cmdutil.show_changeset(self.ui, self.repo, {}) |
135 displayer.show(changenode=self.badrev) |
135 displayer.show(changenode=self.badrev) |
136 return None |
136 return None |