Mercurial > public > mercurial-scm > hg

comparison mercurial/revset.py @ 20691:c1f666e27345

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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.
author Lucas Moscovicz <lmoscovicz@fb.com>
date Fri, 07 Feb 2014 13:44:57 -0800
parents 13c0327eeb6f
children 7af341082b76
comparison
equal deleted inserted replaced
20690:13c0327eeb6f 20691:c1f666e27345
20 def _revancestors(repo, revs, followfirst): 20 def _revancestors(repo, revs, followfirst):
21 """Like revlog.ancestors(), but supports followfirst.""" 21 """Like revlog.ancestors(), but supports followfirst."""
22 cut = followfirst and 1 or None 22 cut = followfirst and 1 or None
23 cl = repo.changelog 23 cl = repo.changelog
24 24
25 # Implementation to be changed in later patches based on revs order.
26 h = list(revs)
27 for i in xrange(len(h)):
28 h[i] = -h[i]
29 heapq.heapify(h)
30 seen = set([node.nullrev])
31 def iterate(): 25 def iterate():
26 revqueue, revsnode = None, None
27 h = []
28
29 revs.descending()
30 revqueue = util.deque(revs)
31 if revqueue:
32 revsnode = revqueue.popleft()
33 heapq.heappush(h, -revsnode)
34
35 seen = set([node.nullrev])
32 while h: 36 while h:
33 current = -heapq.heappop(h) 37 current = -heapq.heappop(h)
34 if current not in seen: 38 if current not in seen:
39 if revsnode and current == revsnode:
40 if revqueue:
41 revsnode = revqueue.popleft()
42 heapq.heappush(h, -revsnode)
35 seen.add(current) 43 seen.add(current)
36 yield current 44 yield current
37 for parent in cl.parentrevs(current)[:cut]: 45 for parent in cl.parentrevs(current)[:cut]:
38 if parent != node.nullrev: 46 if parent != node.nullrev:
39 heapq.heappush(h, -parent) 47 heapq.heappush(h, -parent)