Mercurial > hg
comparison hgext/hbisect.py @ 5724:13653ee67859
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 |