[PATCH 9 of 9 RFC] 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 dfa0bd8589d381e22a1a74aaf1332f5737eaff91
# Parent  655bab06401501ab0050858bcbc7ec65f8aa18fd
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
@@ -20,20 +20,31 @@
     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 = []
+
+        if revs.order == 'desc':
+            revqueue = util.deque(revs)
+            if revqueue:
+                revsnode = revqueue.popleft()
+                heapq.heappush(h, -revsnode)
+        else:
+            h = [-r for r in revs]
+            heapq.heapify(h)
+
+        seen = set([node.nullrev])
         while h:
             current = -heapq.heappop(h)
             if current not in seen:
-                    seen.add(current)
-                    yield current
-                    for parent in cl.parentrevs(current)[:cut]:
-                        heapq.heappush(h, -parent)
+                if revsnode and current == revsnode:
+                    if revqueue:
+                        revsnode = revqueue.popleft()
+                        heapq.heappush(-revsnode)
+                seen.add(current)
+                yield current
+                for parent in cl.parentrevs(current)[:cut]:
+                    heapq.heappush(h, -parent)
 
     return descgeneratorset(iterate())