# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@fb.com>
# Date 2014-03-26 23:21:30
# Node ID 85544a52ee84a360a9b8ea227800a966f3370f38
# Parent  6db8074f9150a5152375eef6b2a82774c6d991d7

revset: use an iterator instead of a dequeue in ancestors()

The dequeue was actually just used to be able to pop value one at a time.
Building the dequeue means we are reading all the input value at once at the
beginning of the evaluation. This defeat the lazyness of revset.

We replace the deque with iterator usage for the sake of simplicity and
lazyness.

This provide massive speedup to get the first result if the input set is big

max(::all())
before) wall 0.001917 comb 0.000000 user 0.000000 sys 0.000000 (best of 1115)
after)  wall 0.000107 comb 0.000000 user 0.000000 sys 0.000000 (best of 22222)

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -26,22 +26,24 @@ def _revancestors(repo, revs, followfirs
 
     def iterate():
         revs.sort(reverse=True)
-        revqueue = util.deque(revs)
-        if not revqueue:
+        irevs = iter(revs)
+        h = []
+        try:
+            inputrev = irevs.next()
+            heapq.heappush(h, -inputrev)
+        except StopIteration:
             return
 
-        h = []
-        inputrev = revqueue.popleft()
-        heapq.heappush(h, -inputrev)
-
         seen = set()
         while h:
             current = -heapq.heappop(h)
             if current not in seen:
                 if current == inputrev:
-                    if revqueue:
-                        inputrev = revqueue.popleft()
+                    try:
+                        inputrev = irevs.next()
                         heapq.heappush(h, -inputrev)
+                    except StopIteration:
+                        pass
                 seen.add(current)
                 yield current
                 for parent in cl.parentrevs(current)[:cut]: