[PATCH 2 of 4] revset: optimized _revancestors method based on order of revisions

[Lucas Moscovicz]

# HG changeset patch
# User Lucas Moscovicz <lmoscovicz at fb.com>
# Date 1391809497 28800
#      Fri Feb 07 13:44:57 2014 -0800
# Node ID a2d473ebec3a547b505a02b47d0f8f0ac95ca197
# Parent  279a4c4a90edea64fccb932519aee0e43bf1605f
revset: optimized _revancestors method based on order of revisions

If the revisions for which the ancestors are required are in descending order,
it lazily loads them into a heap to be able to yield values faster.

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -22,16 +22,24 @@
     cut = followfirst and 1 or None
     cl = repo.changelog
 
-    # Implementation to be changed in later patches based on revs order.
-    h = list(revs)
-    for i in xrange(len(h)):
-        h[i] = -h[i]
-    heapq.heapify(h)
-    seen = set([node.nullrev])
     def iterate():
+        revqueue, revsnode = None, None
+        h = []
+
+        revs.descending()
+        revqueue = util.deque(revs)
+        if revqueue:
+            revsnode = revqueue.popleft()
+            heapq.heappush(h, -revsnode)
+
+        seen = set([node.nullrev])
         while h:
             current = -heapq.heappop(h)
             if current not in seen:
+                if revsnode and current == revsnode:
+                    if revqueue:
+                        revsnode = revqueue.popleft()
+                        heapq.heappush(h, -revsnode)
                 seen.add(current)
                 yield current
                 for parent in cl.parentrevs(current)[:cut]: