[PATCH 8 of 9 RFC] revset: changed ancestors revset to return lazy generators

[Lucas Moscovicz]

# HG changeset patch
# User Lucas Moscovicz <lmoscovicz at fb.com>
# Date 1391797922 28800
#      Fri Feb 07 10:32:02 2014 -0800
# Node ID 655bab06401501ab0050858bcbc7ec65f8aa18fd
# Parent  35e93209ef29f786911232f9f37ad95661abf3d9
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
@@ -6,7 +6,7 @@
 # GNU General Public License version 2 or any later version.
 
 import re
-import parser, util, error, discovery, hbisect, phases
+import parser, util, error, discovery, hbisect, phases, heapq
 import node
 import match as matchmod
 from i18n import _
@@ -19,14 +19,23 @@
     """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]:
+                        heapq.heappush(h, -parent)
+
+    return descgeneratorset(iterate())
 
 def _revdescendants(repo, revs, followfirst):
     """Like revlog.descendants() but supports followfirst."""
@@ -309,7 +318,7 @@
         repo.changelog.filteredrevs), 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):
@@ -765,7 +774,7 @@
         else:
             return baseset([])
     else:
-        s = set(_revancestors(repo, [c.rev()], followfirst)) | set([c.rev()])
+        s = _revancestors(repo, baseset([c.rev()]), followfirst)
 
     return baseset([r for r in subset if r in s])