comparison mercurial/revset.py @ 20691:c1f666e27345

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.

20690:13c0327eeb6f

def _revancestors(repo, revs, followfirst):
    """Like revlog.ancestors(), but supports followfirst."""
    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():
        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)

20691:c1f666e27345

def _revancestors(repo, revs, followfirst):
    """Like revlog.ancestors(), but supports followfirst."""
    cut = followfirst and 1 or None
    cl = repo.changelog

    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]:
                    if parent != node.nullrev:
                        heapq.heappush(h, -parent)