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

login
register
mail settings
Submitter Lucas Moscovicz
Date March 6, 2014, 11:19 p.m.
Message ID <a2d473ebec3a547b505a.1394147957@dev1037.prn2.facebook.com>
Download mbox | patch
Permalink /patch/3881/
State Accepted
Commit c1f666e273451d3b184b4b14e5ce7ed532f50675
Headers show

Comments

Lucas Moscovicz - March 6, 2014, 11:19 p.m.
# HG changeset patch
# User Lucas Moscovicz <lmoscovicz@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.

Patch

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]: