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