comparison mercurial/smartset.py @ 35501:12a46ad67a3c

smartset: split generatorset classes to avoid cycle

I uncovered a cycle manifesting in a memory leak by running
`hgperfrevset '::tip'`. The cycle was due to generatorset.__init__
assigning a bound method to self.__contains__. Internet sleuthing
revealed that assigning a bound method to an instance attribute
always creates a cycle.

This commit creates two new variants of generatorset for the special
cases of ascending and descending generators. The special
implementations of __contains__ have been extracted to these classes
where they are defined as __contains__.

generatorset now implements __new__ and changes the spawned type to
one of the new classes if needed.

Differential Revision: https://phab.mercurial-scm.org/D1780

35500:87918218da70

    >>> xs = generatorset([0, 1, 4], iterasc=True)
    >>> assert xs.last() == xs.last()
    >>> xs.last()  # cached
    4
    """
    def __init__(self, gen, iterasc=None):
        """
        gen: a generator producing the values for the generatorset.
        """
        self._gen = gen
        self._asclist = None
        self._cache = {}
        self._genlist = []
        self._finished = False
        self._ascending = True
        if iterasc is not None:
            if iterasc:
                self.fastasc = self._iterator
                self.__contains__ = self._asccontains
            else:
                self.fastdesc = self._iterator
                self.__contains__ = self._desccontains

    def __nonzero__(self):
        # Do not use 'for r in self' because it will enforce the iteration
        # order (default ascending), possibly unrolling a whole descending
        # iterator.

        # Use new values only, as existing values would be cached.
        for l in self._consumegen():
            if l == x:
                return True

        self._cache[x] = False
        return False

    def _asccontains(self, x):
        """version of contains optimised for ascending generator"""
        if x in self._cache:
            return self._cache[x]

        # Use new values only, as existing values would be cached.
        for l in self._consumegen():
            if l == x:
                return True
            if l > x:
                break

        self._cache[x] = False
        return False

    def _desccontains(self, x):
        """version of contains optimised for descending generator"""
        if x in self._cache:
            return self._cache[x]

        # Use new values only, as existing values would be cached.
        for l in self._consumegen():
            if l == x:
                return True
            if l < x:
                break

        self._cache[x] = False
        return False

    def __iter__(self):

            return self.last()
        return next(it(), None)

    def __repr__(self):
        d = {False: '-', True: '+'}[self._ascending]
        return '<%s%s>' % (type(self).__name__, d)

def spanset(repo, start=0, end=None):
    """Create a spanset that represents a range of repository revisions

    start: first revision included the set (default to 0)

35501:12a46ad67a3c

    >>> xs = generatorset([0, 1, 4], iterasc=True)
    >>> assert xs.last() == xs.last()
    >>> xs.last()  # cached
    4
    """
    def __new__(cls, gen, iterasc=None):
        if iterasc is None:
            typ = cls
        elif iterasc:
            typ = _generatorsetasc
        else:
            typ = _generatorsetdesc

        return super(generatorset, cls).__new__(typ)

    def __init__(self, gen, iterasc=None):
        """
        gen: a generator producing the values for the generatorset.
        """
        self._gen = gen
        self._asclist = None
        self._cache = {}
        self._genlist = []
        self._finished = False
        self._ascending = True

    def __nonzero__(self):
        # Do not use 'for r in self' because it will enforce the iteration
        # order (default ascending), possibly unrolling a whole descending
        # iterator.

        # Use new values only, as existing values would be cached.
        for l in self._consumegen():
            if l == x:
                return True

        self._cache[x] = False
        return False

    def __iter__(self):

            return self.last()
        return next(it(), None)

    def __repr__(self):
        d = {False: '-', True: '+'}[self._ascending]
        return '<%s%s>' % (type(self).__name__.lstrip('_'), d)

class _generatorsetasc(generatorset):
    """Special case of generatorset optimized for ascending generators."""

    fastasc = generatorset._iterator

    def __contains__(self, x):
        if x in self._cache:
            return self._cache[x]

        # Use new values only, as existing values would be cached.
        for l in self._consumegen():
            if l == x:
                return True
            if l > x:
                break

        self._cache[x] = False
        return False

class _generatorsetdesc(generatorset):
    """Special case of generatorset optimized for descending generators."""

    fastdesc = generatorset._iterator

    def __contains__(self, x):
        if x in self._cache:
            return self._cache[x]

        # Use new values only, as existing values would be cached.
        for l in self._consumegen():
            if l == x:
                return True
            if l < x:
                break

        self._cache[x] = False
        return False

def spanset(repo, start=0, end=None):
    """Create a spanset that represents a range of repository revisions

    start: first revision included the set (default to 0)