Show More
@@ -1,363 +1,367 b'' | |||||
1 | # ancestor.py - generic DAG ancestor algorithm for mercurial |
|
1 | # ancestor.py - generic DAG ancestor algorithm for mercurial | |
2 | # |
|
2 | # | |
3 | # Copyright 2006 Matt Mackall <mpm@selenic.com> |
|
3 | # Copyright 2006 Matt Mackall <mpm@selenic.com> | |
4 | # |
|
4 | # | |
5 | # This software may be used and distributed according to the terms of the |
|
5 | # This software may be used and distributed according to the terms of the | |
6 | # GNU General Public License version 2 or any later version. |
|
6 | # GNU General Public License version 2 or any later version. | |
7 |
|
7 | |||
8 | from __future__ import absolute_import |
|
8 | from __future__ import absolute_import | |
9 |
|
9 | |||
10 | import collections |
|
10 | import collections | |
11 | import heapq |
|
11 | import heapq | |
12 |
|
12 | |||
13 | from .node import nullrev |
|
13 | from .node import nullrev | |
14 |
|
14 | |||
15 | def commonancestorsheads(pfunc, *nodes): |
|
15 | def commonancestorsheads(pfunc, *nodes): | |
16 | """Returns a set with the heads of all common ancestors of all nodes, |
|
16 | """Returns a set with the heads of all common ancestors of all nodes, | |
17 | heads(::nodes[0] and ::nodes[1] and ...) . |
|
17 | heads(::nodes[0] and ::nodes[1] and ...) . | |
18 |
|
18 | |||
19 | pfunc must return a list of parent vertices for a given vertex. |
|
19 | pfunc must return a list of parent vertices for a given vertex. | |
20 | """ |
|
20 | """ | |
21 | if not isinstance(nodes, set): |
|
21 | if not isinstance(nodes, set): | |
22 | nodes = set(nodes) |
|
22 | nodes = set(nodes) | |
23 | if nullrev in nodes: |
|
23 | if nullrev in nodes: | |
24 | return set() |
|
24 | return set() | |
25 | if len(nodes) <= 1: |
|
25 | if len(nodes) <= 1: | |
26 | return nodes |
|
26 | return nodes | |
27 |
|
27 | |||
28 | allseen = (1 << len(nodes)) - 1 |
|
28 | allseen = (1 << len(nodes)) - 1 | |
29 | seen = [0] * (max(nodes) + 1) |
|
29 | seen = [0] * (max(nodes) + 1) | |
30 | for i, n in enumerate(nodes): |
|
30 | for i, n in enumerate(nodes): | |
31 | seen[n] = 1 << i |
|
31 | seen[n] = 1 << i | |
32 | poison = 1 << (i + 1) |
|
32 | poison = 1 << (i + 1) | |
33 |
|
33 | |||
34 | gca = set() |
|
34 | gca = set() | |
35 | interesting = len(nodes) |
|
35 | interesting = len(nodes) | |
36 | nv = len(seen) - 1 |
|
36 | nv = len(seen) - 1 | |
37 | while nv >= 0 and interesting: |
|
37 | while nv >= 0 and interesting: | |
38 | v = nv |
|
38 | v = nv | |
39 | nv -= 1 |
|
39 | nv -= 1 | |
40 | if not seen[v]: |
|
40 | if not seen[v]: | |
41 | continue |
|
41 | continue | |
42 | sv = seen[v] |
|
42 | sv = seen[v] | |
43 | if sv < poison: |
|
43 | if sv < poison: | |
44 | interesting -= 1 |
|
44 | interesting -= 1 | |
45 | if sv == allseen: |
|
45 | if sv == allseen: | |
46 | gca.add(v) |
|
46 | gca.add(v) | |
47 | sv |= poison |
|
47 | sv |= poison | |
48 | if v in nodes: |
|
48 | if v in nodes: | |
49 | # history is linear |
|
49 | # history is linear | |
50 | return {v} |
|
50 | return {v} | |
51 | if sv < poison: |
|
51 | if sv < poison: | |
52 | for p in pfunc(v): |
|
52 | for p in pfunc(v): | |
53 | sp = seen[p] |
|
53 | sp = seen[p] | |
54 | if p == nullrev: |
|
54 | if p == nullrev: | |
55 | continue |
|
55 | continue | |
56 | if sp == 0: |
|
56 | if sp == 0: | |
57 | seen[p] = sv |
|
57 | seen[p] = sv | |
58 | interesting += 1 |
|
58 | interesting += 1 | |
59 | elif sp != sv: |
|
59 | elif sp != sv: | |
60 | seen[p] |= sv |
|
60 | seen[p] |= sv | |
61 | else: |
|
61 | else: | |
62 | for p in pfunc(v): |
|
62 | for p in pfunc(v): | |
63 | if p == nullrev: |
|
63 | if p == nullrev: | |
64 | continue |
|
64 | continue | |
65 | sp = seen[p] |
|
65 | sp = seen[p] | |
66 | if sp and sp < poison: |
|
66 | if sp and sp < poison: | |
67 | interesting -= 1 |
|
67 | interesting -= 1 | |
68 | seen[p] = sv |
|
68 | seen[p] = sv | |
69 | return gca |
|
69 | return gca | |
70 |
|
70 | |||
71 | def ancestors(pfunc, *orignodes): |
|
71 | def ancestors(pfunc, *orignodes): | |
72 | """ |
|
72 | """ | |
73 | Returns the common ancestors of a and b that are furthest from a |
|
73 | Returns the common ancestors of a and b that are furthest from a | |
74 | root (as measured by longest path). |
|
74 | root (as measured by longest path). | |
75 |
|
75 | |||
76 | pfunc must return a list of parent vertices for a given vertex. |
|
76 | pfunc must return a list of parent vertices for a given vertex. | |
77 | """ |
|
77 | """ | |
78 | def deepest(nodes): |
|
78 | def deepest(nodes): | |
79 | interesting = {} |
|
79 | interesting = {} | |
80 | count = max(nodes) + 1 |
|
80 | count = max(nodes) + 1 | |
81 | depth = [0] * count |
|
81 | depth = [0] * count | |
82 | seen = [0] * count |
|
82 | seen = [0] * count | |
83 | mapping = [] |
|
83 | mapping = [] | |
84 | for (i, n) in enumerate(sorted(nodes)): |
|
84 | for (i, n) in enumerate(sorted(nodes)): | |
85 | depth[n] = 1 |
|
85 | depth[n] = 1 | |
86 | b = 1 << i |
|
86 | b = 1 << i | |
87 | seen[n] = b |
|
87 | seen[n] = b | |
88 | interesting[b] = 1 |
|
88 | interesting[b] = 1 | |
89 | mapping.append((b, n)) |
|
89 | mapping.append((b, n)) | |
90 | nv = count - 1 |
|
90 | nv = count - 1 | |
91 | while nv >= 0 and len(interesting) > 1: |
|
91 | while nv >= 0 and len(interesting) > 1: | |
92 | v = nv |
|
92 | v = nv | |
93 | nv -= 1 |
|
93 | nv -= 1 | |
94 | dv = depth[v] |
|
94 | dv = depth[v] | |
95 | if dv == 0: |
|
95 | if dv == 0: | |
96 | continue |
|
96 | continue | |
97 | sv = seen[v] |
|
97 | sv = seen[v] | |
98 | for p in pfunc(v): |
|
98 | for p in pfunc(v): | |
99 | if p == nullrev: |
|
99 | if p == nullrev: | |
100 | continue |
|
100 | continue | |
101 | dp = depth[p] |
|
101 | dp = depth[p] | |
102 | nsp = sp = seen[p] |
|
102 | nsp = sp = seen[p] | |
103 | if dp <= dv: |
|
103 | if dp <= dv: | |
104 | depth[p] = dv + 1 |
|
104 | depth[p] = dv + 1 | |
105 | if sp != sv: |
|
105 | if sp != sv: | |
106 | interesting[sv] += 1 |
|
106 | interesting[sv] += 1 | |
107 | nsp = seen[p] = sv |
|
107 | nsp = seen[p] = sv | |
108 | if sp: |
|
108 | if sp: | |
109 | interesting[sp] -= 1 |
|
109 | interesting[sp] -= 1 | |
110 | if interesting[sp] == 0: |
|
110 | if interesting[sp] == 0: | |
111 | del interesting[sp] |
|
111 | del interesting[sp] | |
112 | elif dv == dp - 1: |
|
112 | elif dv == dp - 1: | |
113 | nsp = sp | sv |
|
113 | nsp = sp | sv | |
114 | if nsp == sp: |
|
114 | if nsp == sp: | |
115 | continue |
|
115 | continue | |
116 | seen[p] = nsp |
|
116 | seen[p] = nsp | |
117 | interesting.setdefault(nsp, 0) |
|
117 | interesting.setdefault(nsp, 0) | |
118 | interesting[nsp] += 1 |
|
118 | interesting[nsp] += 1 | |
119 | interesting[sp] -= 1 |
|
119 | interesting[sp] -= 1 | |
120 | if interesting[sp] == 0: |
|
120 | if interesting[sp] == 0: | |
121 | del interesting[sp] |
|
121 | del interesting[sp] | |
122 | interesting[sv] -= 1 |
|
122 | interesting[sv] -= 1 | |
123 | if interesting[sv] == 0: |
|
123 | if interesting[sv] == 0: | |
124 | del interesting[sv] |
|
124 | del interesting[sv] | |
125 |
|
125 | |||
126 | if len(interesting) != 1: |
|
126 | if len(interesting) != 1: | |
127 | return [] |
|
127 | return [] | |
128 |
|
128 | |||
129 | k = 0 |
|
129 | k = 0 | |
130 | for i in interesting: |
|
130 | for i in interesting: | |
131 | k |= i |
|
131 | k |= i | |
132 | return set(n for (i, n) in mapping if k & i) |
|
132 | return set(n for (i, n) in mapping if k & i) | |
133 |
|
133 | |||
134 | gca = commonancestorsheads(pfunc, *orignodes) |
|
134 | gca = commonancestorsheads(pfunc, *orignodes) | |
135 |
|
135 | |||
136 | if len(gca) <= 1: |
|
136 | if len(gca) <= 1: | |
137 | return gca |
|
137 | return gca | |
138 | return deepest(gca) |
|
138 | return deepest(gca) | |
139 |
|
139 | |||
140 | class incrementalmissingancestors(object): |
|
140 | class incrementalmissingancestors(object): | |
141 | '''persistent state used to calculate missing ancestors incrementally |
|
141 | '''persistent state used to calculate missing ancestors incrementally | |
142 |
|
142 | |||
143 | Although similar in spirit to lazyancestors below, this is a separate class |
|
143 | Although similar in spirit to lazyancestors below, this is a separate class | |
144 | because trying to support contains and missingancestors operations with the |
|
144 | because trying to support contains and missingancestors operations with the | |
145 | same internal data structures adds needless complexity.''' |
|
145 | same internal data structures adds needless complexity.''' | |
146 | def __init__(self, pfunc, bases): |
|
146 | def __init__(self, pfunc, bases): | |
147 | self.bases = set(bases) |
|
147 | self.bases = set(bases) | |
148 | if not self.bases: |
|
148 | if not self.bases: | |
149 | self.bases.add(nullrev) |
|
149 | self.bases.add(nullrev) | |
150 | self.pfunc = pfunc |
|
150 | self.pfunc = pfunc | |
151 |
|
151 | |||
152 | def hasbases(self): |
|
152 | def hasbases(self): | |
153 | '''whether the common set has any non-trivial bases''' |
|
153 | '''whether the common set has any non-trivial bases''' | |
154 | return self.bases and self.bases != {nullrev} |
|
154 | return self.bases and self.bases != {nullrev} | |
155 |
|
155 | |||
156 | def addbases(self, newbases): |
|
156 | def addbases(self, newbases): | |
157 | '''grow the ancestor set by adding new bases''' |
|
157 | '''grow the ancestor set by adding new bases''' | |
158 | self.bases.update(newbases) |
|
158 | self.bases.update(newbases) | |
159 |
|
159 | |||
160 | def removeancestorsfrom(self, revs): |
|
160 | def removeancestorsfrom(self, revs): | |
161 | '''remove all ancestors of bases from the set revs (in place)''' |
|
161 | '''remove all ancestors of bases from the set revs (in place)''' | |
162 | bases = self.bases |
|
162 | bases = self.bases | |
163 | pfunc = self.pfunc |
|
163 | pfunc = self.pfunc | |
164 | revs.difference_update(bases) |
|
164 | revs.difference_update(bases) | |
165 | # nullrev is always an ancestor |
|
165 | # nullrev is always an ancestor | |
166 | revs.discard(nullrev) |
|
166 | revs.discard(nullrev) | |
167 | if not revs: |
|
167 | if not revs: | |
168 | return |
|
168 | return | |
169 | # anything in revs > start is definitely not an ancestor of bases |
|
169 | # anything in revs > start is definitely not an ancestor of bases | |
170 | # revs <= start needs to be investigated |
|
170 | # revs <= start needs to be investigated | |
171 | start = max(bases) |
|
171 | start = max(bases) | |
172 | keepcount = sum(1 for r in revs if r > start) |
|
172 | keepcount = sum(1 for r in revs if r > start) | |
173 | if len(revs) == keepcount: |
|
173 | if len(revs) == keepcount: | |
174 | # no revs to consider |
|
174 | # no revs to consider | |
175 | return |
|
175 | return | |
176 |
|
176 | |||
177 | for curr in xrange(start, min(revs) - 1, -1): |
|
177 | for curr in xrange(start, min(revs) - 1, -1): | |
178 | if curr not in bases: |
|
178 | if curr not in bases: | |
179 | continue |
|
179 | continue | |
180 | revs.discard(curr) |
|
180 | revs.discard(curr) | |
181 | bases.update(pfunc(curr)) |
|
181 | bases.update(pfunc(curr)) | |
182 | if len(revs) == keepcount: |
|
182 | if len(revs) == keepcount: | |
183 | # no more potential revs to discard |
|
183 | # no more potential revs to discard | |
184 | break |
|
184 | break | |
185 |
|
185 | |||
186 | def missingancestors(self, revs): |
|
186 | def missingancestors(self, revs): | |
187 | '''return all the ancestors of revs that are not ancestors of self.bases |
|
187 | '''return all the ancestors of revs that are not ancestors of self.bases | |
188 |
|
188 | |||
189 | This may include elements from revs. |
|
189 | This may include elements from revs. | |
190 |
|
190 | |||
191 | Equivalent to the revset (::revs - ::self.bases). Revs are returned in |
|
191 | Equivalent to the revset (::revs - ::self.bases). Revs are returned in | |
192 | revision number order, which is a topological order.''' |
|
192 | revision number order, which is a topological order.''' | |
193 | revsvisit = set(revs) |
|
193 | revsvisit = set(revs) | |
194 | basesvisit = self.bases |
|
194 | basesvisit = self.bases | |
195 | pfunc = self.pfunc |
|
195 | pfunc = self.pfunc | |
196 | bothvisit = revsvisit.intersection(basesvisit) |
|
196 | bothvisit = revsvisit.intersection(basesvisit) | |
197 | revsvisit.difference_update(bothvisit) |
|
197 | revsvisit.difference_update(bothvisit) | |
198 | if not revsvisit: |
|
198 | if not revsvisit: | |
199 | return [] |
|
199 | return [] | |
200 |
|
200 | |||
201 | start = max(max(revsvisit), max(basesvisit)) |
|
201 | start = max(max(revsvisit), max(basesvisit)) | |
202 | # At this point, we hold the invariants that: |
|
202 | # At this point, we hold the invariants that: | |
203 | # - revsvisit is the set of nodes we know are an ancestor of at least |
|
203 | # - revsvisit is the set of nodes we know are an ancestor of at least | |
204 | # one of the nodes in revs |
|
204 | # one of the nodes in revs | |
205 | # - basesvisit is the same for bases |
|
205 | # - basesvisit is the same for bases | |
206 | # - bothvisit is the set of nodes we know are ancestors of at least one |
|
206 | # - bothvisit is the set of nodes we know are ancestors of at least one | |
207 | # of the nodes in revs and one of the nodes in bases. bothvisit and |
|
207 | # of the nodes in revs and one of the nodes in bases. bothvisit and | |
208 | # revsvisit are mutually exclusive, but bothvisit is a subset of |
|
208 | # revsvisit are mutually exclusive, but bothvisit is a subset of | |
209 | # basesvisit. |
|
209 | # basesvisit. | |
210 | # Now we walk down in reverse topo order, adding parents of nodes |
|
210 | # Now we walk down in reverse topo order, adding parents of nodes | |
211 | # already visited to the sets while maintaining the invariants. When a |
|
211 | # already visited to the sets while maintaining the invariants. When a | |
212 | # node is found in both revsvisit and basesvisit, it is removed from |
|
212 | # node is found in both revsvisit and basesvisit, it is removed from | |
213 | # revsvisit and added to bothvisit. When revsvisit becomes empty, there |
|
213 | # revsvisit and added to bothvisit. When revsvisit becomes empty, there | |
214 | # are no more ancestors of revs that aren't also ancestors of bases, so |
|
214 | # are no more ancestors of revs that aren't also ancestors of bases, so | |
215 | # exit. |
|
215 | # exit. | |
216 |
|
216 | |||
217 | missing = [] |
|
217 | missing = [] | |
218 | for curr in xrange(start, nullrev, -1): |
|
218 | for curr in xrange(start, nullrev, -1): | |
219 | if not revsvisit: |
|
219 | if not revsvisit: | |
220 | break |
|
220 | break | |
221 |
|
221 | |||
222 | if curr in bothvisit: |
|
222 | if curr in bothvisit: | |
223 | bothvisit.remove(curr) |
|
223 | bothvisit.remove(curr) | |
224 | # curr's parents might have made it into revsvisit through |
|
224 | # curr's parents might have made it into revsvisit through | |
225 | # another path |
|
225 | # another path | |
226 | for p in pfunc(curr): |
|
226 | for p in pfunc(curr): | |
227 | revsvisit.discard(p) |
|
227 | revsvisit.discard(p) | |
228 | basesvisit.add(p) |
|
228 | basesvisit.add(p) | |
229 | bothvisit.add(p) |
|
229 | bothvisit.add(p) | |
230 | continue |
|
230 | continue | |
231 |
|
231 | |||
232 | if curr in revsvisit: |
|
232 | if curr in revsvisit: | |
233 | missing.append(curr) |
|
233 | missing.append(curr) | |
234 | revsvisit.remove(curr) |
|
234 | revsvisit.remove(curr) | |
235 | thisvisit = revsvisit |
|
235 | thisvisit = revsvisit | |
236 | othervisit = basesvisit |
|
236 | othervisit = basesvisit | |
237 | elif curr in basesvisit: |
|
237 | elif curr in basesvisit: | |
238 | thisvisit = basesvisit |
|
238 | thisvisit = basesvisit | |
239 | othervisit = revsvisit |
|
239 | othervisit = revsvisit | |
240 | else: |
|
240 | else: | |
241 | # not an ancestor of revs or bases: ignore |
|
241 | # not an ancestor of revs or bases: ignore | |
242 | continue |
|
242 | continue | |
243 |
|
243 | |||
244 | for p in pfunc(curr): |
|
244 | for p in pfunc(curr): | |
245 | if p == nullrev: |
|
245 | if p == nullrev: | |
246 | pass |
|
246 | pass | |
247 | elif p in othervisit or p in bothvisit: |
|
247 | elif p in othervisit or p in bothvisit: | |
248 | # p is implicitly in thisvisit. This means p is or should be |
|
248 | # p is implicitly in thisvisit. This means p is or should be | |
249 | # in bothvisit |
|
249 | # in bothvisit | |
250 | revsvisit.discard(p) |
|
250 | revsvisit.discard(p) | |
251 | basesvisit.add(p) |
|
251 | basesvisit.add(p) | |
252 | bothvisit.add(p) |
|
252 | bothvisit.add(p) | |
253 | else: |
|
253 | else: | |
254 | # visit later |
|
254 | # visit later | |
255 | thisvisit.add(p) |
|
255 | thisvisit.add(p) | |
256 |
|
256 | |||
257 | missing.reverse() |
|
257 | missing.reverse() | |
258 | return missing |
|
258 | return missing | |
259 |
|
259 | |||
260 | class lazyancestors(object): |
|
260 | class lazyancestors(object): | |
261 | def __init__(self, pfunc, revs, stoprev=0, inclusive=False): |
|
261 | def __init__(self, pfunc, revs, stoprev=0, inclusive=False): | |
262 | """Create a new object generating ancestors for the given revs. Does |
|
262 | """Create a new object generating ancestors for the given revs. Does | |
263 | not generate revs lower than stoprev. |
|
263 | not generate revs lower than stoprev. | |
264 |
|
264 | |||
265 | This is computed lazily starting from revs. The object supports |
|
265 | This is computed lazily starting from revs. The object supports | |
266 | iteration and membership. |
|
266 | iteration and membership. | |
267 |
|
267 | |||
268 | cl should be a changelog and revs should be an iterable. inclusive is |
|
268 | cl should be a changelog and revs should be an iterable. inclusive is | |
269 | a boolean that indicates whether revs should be included. Revs lower |
|
269 | a boolean that indicates whether revs should be included. Revs lower | |
270 | than stoprev will not be generated. |
|
270 | than stoprev will not be generated. | |
271 |
|
271 | |||
272 | Result does not include the null revision.""" |
|
272 | Result does not include the null revision.""" | |
273 | self._parentrevs = pfunc |
|
273 | self._parentrevs = pfunc | |
274 | self._initrevs = revs |
|
274 | self._initrevs = revs | |
275 | self._stoprev = stoprev |
|
275 | self._stoprev = stoprev | |
276 | self._inclusive = inclusive |
|
276 | self._inclusive = inclusive | |
277 |
|
277 | |||
278 | # Initialize data structures for __contains__. |
|
278 | # Initialize data structures for __contains__. | |
279 | # For __contains__, we use a heap rather than a deque because |
|
279 | # For __contains__, we use a heap rather than a deque because | |
280 | # (a) it minimizes the number of parentrevs calls made |
|
280 | # (a) it minimizes the number of parentrevs calls made | |
281 | # (b) it makes the loop termination condition obvious |
|
281 | # (b) it makes the loop termination condition obvious | |
282 | # Python's heap is a min-heap. Multiply all values by -1 to convert it |
|
282 | # Python's heap is a min-heap. Multiply all values by -1 to convert it | |
283 | # into a max-heap. |
|
283 | # into a max-heap. | |
284 | self._containsvisit = [-rev for rev in revs] |
|
284 | self._containsvisit = [-rev for rev in revs] | |
285 | heapq.heapify(self._containsvisit) |
|
285 | heapq.heapify(self._containsvisit) | |
286 | if inclusive: |
|
286 | if inclusive: | |
287 | self._containsseen = set(revs) |
|
287 | self._containsseen = set(revs) | |
288 | else: |
|
288 | else: | |
289 | self._containsseen = set() |
|
289 | self._containsseen = set() | |
290 |
|
290 | |||
291 | def __nonzero__(self): |
|
291 | def __nonzero__(self): | |
292 | """False if the set is empty, True otherwise.""" |
|
292 | """False if the set is empty, True otherwise.""" | |
293 | try: |
|
293 | try: | |
294 | next(iter(self)) |
|
294 | next(iter(self)) | |
295 | return True |
|
295 | return True | |
296 | except StopIteration: |
|
296 | except StopIteration: | |
297 | return False |
|
297 | return False | |
298 |
|
298 | |||
299 | __bool__ = __nonzero__ |
|
299 | __bool__ = __nonzero__ | |
300 |
|
300 | |||
301 | def __iter__(self): |
|
301 | def __iter__(self): | |
302 | """Generate the ancestors of _initrevs in reverse topological order. |
|
302 | """Generate the ancestors of _initrevs in reverse topological order. | |
303 |
|
303 | |||
304 | If inclusive is False, yield a sequence of revision numbers starting |
|
304 | If inclusive is False, yield a sequence of revision numbers starting | |
305 | with the parents of each revision in revs, i.e., each revision is *not* |
|
305 | with the parents of each revision in revs, i.e., each revision is *not* | |
306 | considered an ancestor of itself. Results are in breadth-first order: |
|
306 | considered an ancestor of itself. Results are in breadth-first order: | |
307 | parents of each rev in revs, then parents of those, etc. |
|
307 | parents of each rev in revs, then parents of those, etc. | |
308 |
|
308 | |||
309 | If inclusive is True, yield all the revs first (ignoring stoprev), |
|
309 | If inclusive is True, yield all the revs first (ignoring stoprev), | |
310 | then yield all the ancestors of revs as when inclusive is False. |
|
310 | then yield all the ancestors of revs as when inclusive is False. | |
311 | If an element in revs is an ancestor of a different rev it is not |
|
311 | If an element in revs is an ancestor of a different rev it is not | |
312 | yielded again.""" |
|
312 | yielded again.""" | |
313 | seen = set() |
|
313 | seen = set() | |
314 | revs = self._initrevs |
|
314 | revs = self._initrevs | |
315 | if self._inclusive: |
|
315 | if self._inclusive: | |
316 | for rev in revs: |
|
316 | for rev in revs: | |
317 | yield rev |
|
317 | yield rev | |
318 | seen.update(revs) |
|
318 | seen.update(revs) | |
319 |
|
319 | |||
320 | parentrevs = self._parentrevs |
|
320 | parentrevs = self._parentrevs | |
321 | stoprev = self._stoprev |
|
321 | stoprev = self._stoprev | |
322 | visit = collections.deque(revs) |
|
322 | visit = collections.deque(revs) | |
323 |
|
323 | |||
324 | see = seen.add |
|
324 | see = seen.add | |
325 | schedule = visit.append |
|
325 | schedule = visit.append | |
326 |
|
326 | |||
327 | while visit: |
|
327 | while visit: | |
328 | for parent in parentrevs(visit.popleft()): |
|
328 | for parent in parentrevs(visit.popleft()): | |
329 | if parent >= stoprev and parent not in seen: |
|
329 | if parent >= stoprev and parent not in seen: | |
330 | schedule(parent) |
|
330 | schedule(parent) | |
331 | see(parent) |
|
331 | see(parent) | |
332 | yield parent |
|
332 | yield parent | |
333 |
|
333 | |||
334 | def __contains__(self, target): |
|
334 | def __contains__(self, target): | |
335 | """Test whether target is an ancestor of self._initrevs.""" |
|
335 | """Test whether target is an ancestor of self._initrevs.""" | |
336 | # Trying to do both __iter__ and __contains__ using the same visit |
|
336 | # Trying to do both __iter__ and __contains__ using the same visit | |
337 | # heap and seen set is complex enough that it slows down both. Keep |
|
337 | # heap and seen set is complex enough that it slows down both. Keep | |
338 | # them separate. |
|
338 | # them separate. | |
339 | seen = self._containsseen |
|
339 | seen = self._containsseen | |
340 | if target in seen: |
|
340 | if target in seen: | |
341 | return True |
|
341 | return True | |
|
342 | # Only integer target is valid, but some callers expect 'None in self' | |||
|
343 | # to be False. So we explicitly allow it. | |||
|
344 | if target is None: | |||
|
345 | return False | |||
342 |
|
346 | |||
343 | parentrevs = self._parentrevs |
|
347 | parentrevs = self._parentrevs | |
344 | visit = self._containsvisit |
|
348 | visit = self._containsvisit | |
345 | stoprev = self._stoprev |
|
349 | stoprev = self._stoprev | |
346 | heappop = heapq.heappop |
|
350 | heappop = heapq.heappop | |
347 | heappush = heapq.heappush |
|
351 | heappush = heapq.heappush | |
348 | see = seen.add |
|
352 | see = seen.add | |
349 |
|
353 | |||
350 | targetseen = False |
|
354 | targetseen = False | |
351 |
|
355 | |||
352 | while visit and -visit[0] > target and not targetseen: |
|
356 | while visit and -visit[0] > target and not targetseen: | |
353 | for parent in parentrevs(-heappop(visit)): |
|
357 | for parent in parentrevs(-heappop(visit)): | |
354 | if parent < stoprev or parent in seen: |
|
358 | if parent < stoprev or parent in seen: | |
355 | continue |
|
359 | continue | |
356 | # We need to make sure we push all parents into the heap so |
|
360 | # We need to make sure we push all parents into the heap so | |
357 | # that we leave it in a consistent state for future calls. |
|
361 | # that we leave it in a consistent state for future calls. | |
358 | heappush(visit, -parent) |
|
362 | heappush(visit, -parent) | |
359 | see(parent) |
|
363 | see(parent) | |
360 | if parent == target: |
|
364 | if parent == target: | |
361 | targetseen = True |
|
365 | targetseen = True | |
362 |
|
366 | |||
363 | return targetseen |
|
367 | return targetseen |
General Comments 0
You need to be logged in to leave comments.
Login now