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
--- a/mercurial/revset.py Tue Mar 11 14:36:40 2014 +0900
+++ b/mercurial/revset.py Fri Feb 07 10:32:02 2014 -0800
@@ -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 @@
"""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 @@
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 @@
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)