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