revset: optimized _revancestors method based on order of revisions
authorLucas Moscovicz <lmoscovicz@fb.com>
Fri, 07 Feb 2014 13:44:57 -0800
changeset 20691 c1f666e27345
parent 20690 13c0327eeb6f
child 20692 7af341082b76
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.
mercurial/revset.py
--- a/mercurial/revset.py	Fri Feb 07 10:32:02 2014 -0800
+++ b/mercurial/revset.py	Fri Feb 07 13:44:57 2014 -0800
@@ -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]: