comparison mercurial/ancestor.py @ 18090:9abc55ef85b5

revlog: move ancestor generation out to a new class

This refactoring is to prepare for implementing lazy membership.

18089:0127366df8fe

# Copyright 2006 Matt Mackall <[e-mail]>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.

import heapq
from node import nullrev

def ancestor(a, b, pfunc):
    """
    Returns the common ancestor of a and b that is furthest from a

                # visit later
                thisvisit.add(p)

    missing.reverse()
    return missing

18090:9abc55ef85b5

# Copyright 2006 Matt Mackall <[e-mail]>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.

import heapq, util
from node import nullrev

def ancestor(a, b, pfunc):
    """
    Returns the common ancestor of a and b that is furthest from a

                # visit later
                thisvisit.add(p)

    missing.reverse()
    return missing

class lazyancestors(object):
    def __init__(self, cl, revs, stoprev=0, inclusive=False):
        """Create a new object generating ancestors for the given revs. Does
        not generate revs lower than stoprev.

        This is computed lazily starting from revs. The object only supports
        iteration.

        cl should be a changelog and revs should be an iterable. inclusive is
        a boolean that indicates whether revs should be included. Revs lower
        than stoprev will not be generated.

        Result does not include the null revision."""
        self._parentrevs = cl.parentrevs
        self._initrevs = revs
        self._stoprev = stoprev
        self._inclusive = inclusive

    def __iter__(self):
        """Generate the ancestors of _initrevs in reverse topological order.

        If inclusive is False, yield a sequence of revision numbers starting
        with the parents of each revision in revs, i.e., each revision is *not*
        considered an ancestor of itself.  Results are in breadth-first order:
        parents of each rev in revs, then parents of those, etc.

        If inclusive is True, yield all the revs first (ignoring stoprev),
        then yield all the ancestors of revs as when inclusive is False.
        If an element in revs is an ancestor of a different rev it is not
        yielded again."""
        seen = set()
        revs = self._initrevs
        if self._inclusive:
            for rev in revs:
                yield rev
            seen.update(revs)

        parentrevs = self._parentrevs
        stoprev = self._stoprev
        visit = util.deque(revs)

        while visit:
            for parent in parentrevs(visit.popleft()):
                if parent >= stoprev and parent not in seen:
                    visit.append(parent)
                    seen.add(parent)
                    yield parent