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)) |
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 |
|