Mercurial > hg

comparison hgext/hbisect.py @ 5724:13653ee67859

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
bisect: greatly simplify the ancestor accumulating loop
author Matt Mackall <mpm@selenic.com>
date Thu, 27 Dec 2007 23:55:39 -0600
parents e3b09819496b
children 8114d4c915a7
comparison
equal deleted inserted replaced
5723:e3b09819496b 5724:13653ee67859
88 88
89 if badrev in stop: 89 if badrev in stop:
90 raise util.Abort(_("Inconsistent state, %s:%s is good and bad") 90 raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
91 % (badrev, hg.short(bad))) 91 % (badrev, hg.short(bad)))
92 92
93 # build a dict of node -> [number of children, {}] 93 # build a dict of node -> {ancestors}
94 n_child = {badrev: [0, {}]} 94 ancestors = {}
95 count = {}
95 for rev in xrange(badrev + 1): 96 for rev in xrange(badrev + 1):
96 if rev not in n_child:
97 n_child[rev] = [0, {}]
98 # increment count of each parent
99 for p in clparents(rev):
100 if p != hg.nullrev:
101 n_child[p][0] += 1
102
103 for rev in xrange(badrev + 1):
104 for p in clparents(rev):
105 if p != hg.nullrev:
106 n_child[p][0] -= 1
107 if not rev in stop:
108 n_child[rev][1].update(n_child[p][1])
109 if n_child[p][0] == 0:
110 n_child[p] = len(n_child[p][1])
111 if not rev in stop: 97 if not rev in stop:
112 n_child[rev][1][rev] = 1 98 ancestors[rev] = {rev: 1}
113 if n_child[rev][0] == 0: 99 for p in clparents(rev):
114 if rev == badrev: 100 if not p in stop:
115 anc = n_child[rev][1] 101 # add parent ancestors to our ancestors
116 n_child[rev] = len(n_child[rev][1]) 102 ancestors[rev].update(ancestors[p])
117 103 count[rev] = len(ancestors[rev])
118 if badrev not in anc: 104
105 if badrev not in ancestors[badrev]:
119 raise util.Abort(_("Could not find the first bad revision")) 106 raise util.Abort(_("Could not find the first bad revision"))
120 107
121 return anc, n_child 108 return ancestors[badrev], count
122 109
123 def next(self): 110 def next(self):
124 if not self.badnode: 111 if not self.badnode:
125 raise util.Abort(_("You should give at least one bad revision")) 112 raise util.Abort(_("You should give at least one bad revision"))
126 if not self.goodnodes: 113 if not self.goodnodes:
127 self.ui.warn(_("No good revision given\n")) 114 self.ui.warn(_("No good revision given\n"))
128 self.ui.warn(_("Marking the first revision as good\n")) 115 self.ui.warn(_("Marking the first revision as good\n"))
129 ancestors, n_child = self.candidates() 116 ancestors, count = self.candidates()
130 117
131 # have we narrowed it down to one entry? 118 # have we narrowed it down to one entry?
132 tot = len(ancestors) 119 tot = len(ancestors)
133 if tot == 1: 120 if tot == 1:
134 self.ui.write(_("The first bad revision is:\n")) 121 self.ui.write(_("The first bad revision is:\n"))
138 125
139 # find the best node to test 126 # find the best node to test
140 best_rev = None 127 best_rev = None
141 best_len = -1 128 best_len = -1
142 for n in ancestors: 129 for n in ancestors:
143 a = n_child[n] # number of children 130 a = count[n] # number of ancestors
144 b = tot - a # number of ancestors 131 b = tot - a # number of non-ancestors
145 value = min(a, b) # how good is this test? 132 value = min(a, b) # how good is this test?
146 if value > best_len: 133 if value > best_len:
147 best_len = value 134 best_len = value
148 best_rev = n 135 best_rev = n
149 assert best_rev is not None 136 assert best_rev is not None