# HG changeset patch
# User Lucas Moscovicz <lmoscovicz@fb.com>
# Date 2014-02-07 18:32:02
# Node ID 13c0327eeb6f4a8d44c940295025ebe14759165c
# Parent  401f9b661a2d90dd6c933034addd5a9a5253c734

revset: changed ancestors revset to return lazy generators

This will not improve revsets like "::tip" but will do when that gets
intersected or substracted with another revset.

Performance Benchmarking:

$ time hg log -qr "draft() and ::tip"
...

real  0m3.961s
user  0m3.640s
sys 0m0.313s

$ time ./hg log -qr "draft() and ::tip"
...

real  0m1.080s
user  0m0.987s
sys 0m0.083s

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -8,6 +8,7 @@
 import re
 import parser, util, error, discovery, hbisect, phases
 import node
+import heapq
 import match as matchmod
 import ancestor as ancestormod
 from i18n import _
@@ -20,14 +21,24 @@ def _revancestors(repo, revs, followfirs
     """Like revlog.ancestors(), but supports followfirst."""
     cut = followfirst and 1 or None
     cl = repo.changelog
-    visit = util.deque(revs)
+
+    # 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])
-    while visit:
-        for parent in cl.parentrevs(visit.popleft())[:cut]:
-            if parent not in seen:
-                visit.append(parent)
-                seen.add(parent)
-                yield parent
+    def iterate():
+        while h:
+            current = -heapq.heappop(h)
+            if current not in seen:
+                seen.add(current)
+                yield current
+                for parent in cl.parentrevs(current)[:cut]:
+                    if parent != node.nullrev:
+                        heapq.heappush(h, -parent)
+
+    return descgeneratorset(iterate())
 
 def _revdescendants(repo, revs, followfirst):
     """Like revlog.descendants() but supports followfirst."""
@@ -312,7 +323,7 @@ def _ancestors(repo, subset, x, followfi
     args = getset(repo, spanset(repo), x)
     if not args:
         return baseset([])
-    s = set(_revancestors(repo, args, followfirst)) | set(args)
+    s = _revancestors(repo, args, followfirst)
     return subset.filter(lambda r: r in s)
 
 def ancestors(repo, subset, x):
@@ -784,7 +795,7 @@ def _follow(repo, subset, x, name, follo
         else:
             return baseset([])
     else:
-        s = set(_revancestors(repo, [c.rev()], followfirst)) | set([c.rev()])
+        s = _revancestors(repo, baseset([c.rev()]), followfirst)
 
     return subset.filter(lambda r: r in s)