Mercurial > hg

comparison hgext/hbisect.py @ 5725:8114d4c915a7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
bisect: turn ancestors into an array This makes things faster and eliminates the separate stop hash
author Matt Mackall <mpm@selenic.com>
date Thu, 27 Dec 2007 23:55:39 -0600
parents 13653ee67859
children 19cbe2aea2bc
comparison
equal deleted inserted replaced
5724:13653ee67859 5725:8114d4c915a7
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:
148 % (best_rev, hg.short(best_node), tot, nb_tests)) 138 % (best_rev, hg.short(best_node), tot, nb_tests))
149 return best_node 139 return best_node
150 140
151 def autonext(self): 141 def autonext(self):
152 """find and update to the next revision to test""" 142 """find and update to the next revision to test"""
153 node = self.next() 143 node = self.bisect()
154 if node is not None: 144 if node is not None:
155 cmdutil.bail_if_changed(self.repo) 145 cmdutil.bail_if_changed(self.repo)
156 return hg.clean(self.repo, node) 146 return hg.clean(self.repo, node)
157 147
158 def autogood(self, rev=None): 148 def autogood(self, rev=None):