mercurial/utils/compression.py

graft: don't remove from a list in a loop

This addresses a TODO added in a1381eea7c7d (graft: do not use
`.remove` on a smart set (regression), 2014-04-28). I couldn't measure
any speedup.

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

# compression.py - Mercurial utility functions for compression
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.


from __future__ import absolute_import, print_function

import bz2
import collections
import zlib

from ..pycompat import getattr
from .. import (
    error,
    i18n,
    pycompat,
)
from . import stringutil

safehasattr = pycompat.safehasattr


_ = i18n._

# compression code

SERVERROLE = b'server'
CLIENTROLE = b'client'

compewireprotosupport = collections.namedtuple(
    'compenginewireprotosupport', ('name', 'serverpriority', 'clientpriority'),
)


class propertycache(object):
    def __init__(self, func):
        self.func = func
        self.name = func.__name__

    def __get__(self, obj, type=None):
        result = self.func(obj)
        self.cachevalue(obj, result)
        return result

    def cachevalue(self, obj, value):
        # __dict__ assignment required to bypass __setattr__ (eg: repoview)
        obj.__dict__[self.name] = value


class compressormanager(object):
    """Holds registrations of various compression engines.

    This class essentially abstracts the differences between compression
    engines to allow new compression formats to be added easily, possibly from
    extensions.

    Compressors are registered against the global instance by calling its
    ``register()`` method.
    """

    def __init__(self):
        self._engines = {}
        # Bundle spec human name to engine name.
        self._bundlenames = {}
        # Internal bundle identifier to engine name.
        self._bundletypes = {}
        # Revlog header to engine name.
        self._revlogheaders = {}
        # Wire proto identifier to engine name.
        self._wiretypes = {}

    def __getitem__(self, key):
        return self._engines[key]

    def __contains__(self, key):
        return key in self._engines

    def __iter__(self):
        return iter(self._engines.keys())

    def register(self, engine):
        """Register a compression engine with the manager.

        The argument must be a ``compressionengine`` instance.
        """
        if not isinstance(engine, compressionengine):
            raise ValueError(_(b'argument must be a compressionengine'))

        name = engine.name()

        if name in self._engines:
            raise error.Abort(
                _(b'compression engine %s already registered') % name
            )

        bundleinfo = engine.bundletype()
        if bundleinfo:
            bundlename, bundletype = bundleinfo

            if bundlename in self._bundlenames:
                raise error.Abort(
                    _(b'bundle name %s already registered') % bundlename
                )
            if bundletype in self._bundletypes:
                raise error.Abort(
                    _(b'bundle type %s already registered by %s')
                    % (bundletype, self._bundletypes[bundletype])
                )

            # No external facing name declared.
            if bundlename:
                self._bundlenames[bundlename] = name

            self._bundletypes[bundletype] = name

        wiresupport = engine.wireprotosupport()
        if wiresupport:
            wiretype = wiresupport.name
            if wiretype in self._wiretypes:
                raise error.Abort(
                    _(
                        b'wire protocol compression %s already '
                        b'registered by %s'
                    )
                    % (wiretype, self._wiretypes[wiretype])
                )

            self._wiretypes[wiretype] = name

        revlogheader = engine.revlogheader()
        if revlogheader and revlogheader in self._revlogheaders:
            raise error.Abort(
                _(b'revlog header %s already registered by %s')
                % (revlogheader, self._revlogheaders[revlogheader])
            )

        if revlogheader:
            self._revlogheaders[revlogheader] = name

        self._engines[name] = engine

    @property
    def supportedbundlenames(self):
        return set(self._bundlenames.keys())

    @property
    def supportedbundletypes(self):
        return set(self._bundletypes.keys())

    def forbundlename(self, bundlename):
        """Obtain a compression engine registered to a bundle name.

        Will raise KeyError if the bundle type isn't registered.

        Will abort if the engine is known but not available.
        """
        engine = self._engines[self._bundlenames[bundlename]]
        if not engine.available():
            raise error.Abort(
                _(b'compression engine %s could not be loaded') % engine.name()
            )
        return engine

    def forbundletype(self, bundletype):
        """Obtain a compression engine registered to a bundle type.

        Will raise KeyError if the bundle type isn't registered.

        Will abort if the engine is known but not available.
        """
        engine = self._engines[self._bundletypes[bundletype]]
        if not engine.available():
            raise error.Abort(
                _(b'compression engine %s could not be loaded') % engine.name()
            )
        return engine

    def supportedwireengines(self, role, onlyavailable=True):
        """Obtain compression engines that support the wire protocol.

        Returns a list of engines in prioritized order, most desired first.

        If ``onlyavailable`` is set, filter out engines that can't be
        loaded.
        """
        assert role in (SERVERROLE, CLIENTROLE)

        attr = b'serverpriority' if role == SERVERROLE else b'clientpriority'

        engines = [self._engines[e] for e in self._wiretypes.values()]
        if onlyavailable:
            engines = [e for e in engines if e.available()]

        def getkey(e):
            # Sort first by priority, highest first. In case of tie, sort
            # alphabetically. This is arbitrary, but ensures output is
            # stable.
            w = e.wireprotosupport()
            return -1 * getattr(w, attr), w.name

        return list(sorted(engines, key=getkey))

    def forwiretype(self, wiretype):
        engine = self._engines[self._wiretypes[wiretype]]
        if not engine.available():
            raise error.Abort(
                _(b'compression engine %s could not be loaded') % engine.name()
            )
        return engine

    def forrevlogheader(self, header):
        """Obtain a compression engine registered to a revlog header.

        Will raise KeyError if the revlog header value isn't registered.
        """
        return self._engines[self._revlogheaders[header]]


compengines = compressormanager()


class compressionengine(object):
    """Base class for compression engines.

    Compression engines must implement the interface defined by this class.
    """

    def name(self):
        """Returns the name of the compression engine.

        This is the key the engine is registered under.

        This method must be implemented.
        """
        raise NotImplementedError()

    def available(self):
        """Whether the compression engine is available.

        The intent of this method is to allow optional compression engines
        that may not be available in all installations (such as engines relying
        on C extensions that may not be present).
        """
        return True

    def bundletype(self):
        """Describes bundle identifiers for this engine.

        If this compression engine isn't supported for bundles, returns None.

        If this engine can be used for bundles, returns a 2-tuple of strings of
        the user-facing "bundle spec" compression name and an internal
        identifier used to denote the compression format within bundles. To
        exclude the name from external usage, set the first element to ``None``.

        If bundle compression is supported, the class must also implement
        ``compressstream`` and `decompressorreader``.

        The docstring of this method is used in the help system to tell users
        about this engine.
        """
        return None

    def wireprotosupport(self):
        """Declare support for this compression format on the wire protocol.

        If this compression engine isn't supported for compressing wire
        protocol payloads, returns None.

        Otherwise, returns ``compenginewireprotosupport`` with the following
        fields:

        * String format identifier
        * Integer priority for the server
        * Integer priority for the client

        The integer priorities are used to order the advertisement of format
        support by server and client. The highest integer is advertised
        first. Integers with non-positive values aren't advertised.

        The priority values are somewhat arbitrary and only used for default
        ordering. The relative order can be changed via config options.

        If wire protocol compression is supported, the class must also implement
        ``compressstream`` and ``decompressorreader``.
        """
        return None

    def revlogheader(self):
        """Header added to revlog chunks that identifies this engine.

        If this engine can be used to compress revlogs, this method should
        return the bytes used to identify chunks compressed with this engine.
        Else, the method should return ``None`` to indicate it does not
        participate in revlog compression.
        """
        return None

    def compressstream(self, it, opts=None):
        """Compress an iterator of chunks.

        The method receives an iterator (ideally a generator) of chunks of
        bytes to be compressed. It returns an iterator (ideally a generator)
        of bytes of chunks representing the compressed output.

        Optionally accepts an argument defining how to perform compression.
        Each engine treats this argument differently.
        """
        raise NotImplementedError()

    def decompressorreader(self, fh):
        """Perform decompression on a file object.

        Argument is an object with a ``read(size)`` method that returns
        compressed data. Return value is an object with a ``read(size)`` that
        returns uncompressed data.
        """
        raise NotImplementedError()

    def revlogcompressor(self, opts=None):
        """Obtain an object that can be used to compress revlog entries.

        The object has a ``compress(data)`` method that compresses binary
        data. This method returns compressed binary data or ``None`` if
        the data could not be compressed (too small, not compressible, etc).
        The returned data should have a header uniquely identifying this
        compression format so decompression can be routed to this engine.
        This header should be identified by the ``revlogheader()`` return
        value.

        The object has a ``decompress(data)`` method that decompresses
        data. The method will only be called if ``data`` begins with
        ``revlogheader()``. The method should return the raw, uncompressed
        data or raise a ``StorageError``.

        The object is reusable but is not thread safe.
        """
        raise NotImplementedError()


class _CompressedStreamReader(object):
    def __init__(self, fh):
        if safehasattr(fh, 'unbufferedread'):
            self._reader = fh.unbufferedread
        else:
            self._reader = fh.read
        self._pending = []
        self._pos = 0
        self._eof = False

    def _decompress(self, chunk):
        raise NotImplementedError()

    def read(self, l):
        buf = []
        while True:
            while self._pending:
                if len(self._pending[0]) > l + self._pos:
                    newbuf = self._pending[0]
                    buf.append(newbuf[self._pos : self._pos + l])
                    self._pos += l
                    return b''.join(buf)

                newbuf = self._pending.pop(0)
                if self._pos:
                    buf.append(newbuf[self._pos :])
                    l -= len(newbuf) - self._pos
                else:
                    buf.append(newbuf)
                    l -= len(newbuf)
                self._pos = 0

            if self._eof:
                return b''.join(buf)
            chunk = self._reader(65536)
            self._decompress(chunk)
            if not chunk and not self._pending and not self._eof:
                # No progress and no new data, bail out
                return b''.join(buf)


class _GzipCompressedStreamReader(_CompressedStreamReader):
    def __init__(self, fh):
        super(_GzipCompressedStreamReader, self).__init__(fh)
        self._decompobj = zlib.decompressobj()

    def _decompress(self, chunk):
        newbuf = self._decompobj.decompress(chunk)
        if newbuf:
            self._pending.append(newbuf)
        d = self._decompobj.copy()
        try:
            d.decompress(b'x')
            d.flush()
            if d.unused_data == b'x':
                self._eof = True
        except zlib.error:
            pass


class _BZ2CompressedStreamReader(_CompressedStreamReader):
    def __init__(self, fh):
        super(_BZ2CompressedStreamReader, self).__init__(fh)
        self._decompobj = bz2.BZ2Decompressor()

    def _decompress(self, chunk):
        newbuf = self._decompobj.decompress(chunk)
        if newbuf:
            self._pending.append(newbuf)
        try:
            while True:
                newbuf = self._decompobj.decompress(b'')
                if newbuf:
                    self._pending.append(newbuf)
                else:
                    break
        except EOFError:
            self._eof = True


class _TruncatedBZ2CompressedStreamReader(_BZ2CompressedStreamReader):
    def __init__(self, fh):
        super(_TruncatedBZ2CompressedStreamReader, self).__init__(fh)
        newbuf = self._decompobj.decompress(b'BZ')
        if newbuf:
            self._pending.append(newbuf)


class _ZstdCompressedStreamReader(_CompressedStreamReader):
    def __init__(self, fh, zstd):
        super(_ZstdCompressedStreamReader, self).__init__(fh)
        self._zstd = zstd
        self._decompobj = zstd.ZstdDecompressor().decompressobj()

    def _decompress(self, chunk):
        newbuf = self._decompobj.decompress(chunk)
        if newbuf:
            self._pending.append(newbuf)
        try:
            while True:
                newbuf = self._decompobj.decompress(b'')
                if newbuf:
                    self._pending.append(newbuf)
                else:
                    break
        except self._zstd.ZstdError:
            self._eof = True


class _zlibengine(compressionengine):
    def name(self):
        return b'zlib'

    def bundletype(self):
        """zlib compression using the DEFLATE algorithm.

        All Mercurial clients should support this format. The compression
        algorithm strikes a reasonable balance between compression ratio
        and size.
        """
        return b'gzip', b'GZ'

    def wireprotosupport(self):
        return compewireprotosupport(b'zlib', 20, 20)

    def revlogheader(self):
        return b'x'

    def compressstream(self, it, opts=None):
        opts = opts or {}

        z = zlib.compressobj(opts.get(b'level', -1))
        for chunk in it:
            data = z.compress(chunk)
            # Not all calls to compress emit data. It is cheaper to inspect
            # here than to feed empty chunks through generator.
            if data:
                yield data

        yield z.flush()

    def decompressorreader(self, fh):
        return _GzipCompressedStreamReader(fh)

    class zlibrevlogcompressor(object):
        def __init__(self, level=None):
            self._level = level

        def compress(self, data):
            insize = len(data)
            # Caller handles empty input case.
            assert insize > 0

            if insize < 44:
                return None

            elif insize <= 1000000:
                if self._level is None:
                    compressed = zlib.compress(data)
                else:
                    compressed = zlib.compress(data, self._level)
                if len(compressed) < insize:
                    return compressed
                return None

            # zlib makes an internal copy of the input buffer, doubling
            # memory usage for large inputs. So do streaming compression
            # on large inputs.
            else:
                if self._level is None:
                    z = zlib.compressobj()
                else:
                    z = zlib.compressobj(level=self._level)
                parts = []
                pos = 0
                while pos < insize:
                    pos2 = pos + 2 ** 20
                    parts.append(z.compress(data[pos:pos2]))
                    pos = pos2
                parts.append(z.flush())

                if sum(map(len, parts)) < insize:
                    return b''.join(parts)
                return None

        def decompress(self, data):
            try:
                return zlib.decompress(data)
            except zlib.error as e:
                raise error.StorageError(
                    _(b'revlog decompress error: %s')
                    % stringutil.forcebytestr(e)
                )

    def revlogcompressor(self, opts=None):
        level = None
        if opts is not None:
            level = opts.get(b'zlib.level')
        return self.zlibrevlogcompressor(level)


compengines.register(_zlibengine())


class _bz2engine(compressionengine):
    def name(self):
        return b'bz2'

    def bundletype(self):
        """An algorithm that produces smaller bundles than ``gzip``.

        All Mercurial clients should support this format.

        This engine will likely produce smaller bundles than ``gzip`` but
        will be significantly slower, both during compression and
        decompression.

        If available, the ``zstd`` engine can yield similar or better
        compression at much higher speeds.
        """
        return b'bzip2', b'BZ'

    # We declare a protocol name but don't advertise by default because
    # it is slow.
    def wireprotosupport(self):
        return compewireprotosupport(b'bzip2', 0, 0)

    def compressstream(self, it, opts=None):
        opts = opts or {}
        z = bz2.BZ2Compressor(opts.get(b'level', 9))
        for chunk in it:
            data = z.compress(chunk)
            if data:
                yield data

        yield z.flush()

    def decompressorreader(self, fh):
        return _BZ2CompressedStreamReader(fh)


compengines.register(_bz2engine())


class _truncatedbz2engine(compressionengine):
    def name(self):
        return b'bz2truncated'

    def bundletype(self):
        return None, b'_truncatedBZ'

    # We don't implement compressstream because it is hackily handled elsewhere.

    def decompressorreader(self, fh):
        return _TruncatedBZ2CompressedStreamReader(fh)


compengines.register(_truncatedbz2engine())


class _noopengine(compressionengine):
    def name(self):
        return b'none'

    def bundletype(self):
        """No compression is performed.

        Use this compression engine to explicitly disable compression.
        """
        return b'none', b'UN'

    # Clients always support uncompressed payloads. Servers don't because
    # unless you are on a fast network, uncompressed payloads can easily
    # saturate your network pipe.
    def wireprotosupport(self):
        return compewireprotosupport(b'none', 0, 10)

    # We don't implement revlogheader because it is handled specially
    # in the revlog class.

    def compressstream(self, it, opts=None):
        return it

    def decompressorreader(self, fh):
        return fh

    class nooprevlogcompressor(object):
        def compress(self, data):
            return None

    def revlogcompressor(self, opts=None):
        return self.nooprevlogcompressor()


compengines.register(_noopengine())


class _zstdengine(compressionengine):
    def name(self):
        return b'zstd'

    @propertycache
    def _module(self):
        # Not all installs have the zstd module available. So defer importing
        # until first access.
        try:
            from .. import zstd  # pytype: disable=import-error

            # Force delayed import.
            zstd.__version__
            return zstd
        except ImportError:
            return None

    def available(self):
        return bool(self._module)

    def bundletype(self):
        """A modern compression algorithm that is fast and highly flexible.

        Only supported by Mercurial 4.1 and newer clients.

        With the default settings, zstd compression is both faster and yields
        better compression than ``gzip``. It also frequently yields better
        compression than ``bzip2`` while operating at much higher speeds.

        If this engine is available and backwards compatibility is not a
        concern, it is likely the best available engine.
        """
        return b'zstd', b'ZS'

    def wireprotosupport(self):
        return compewireprotosupport(b'zstd', 50, 50)

    def revlogheader(self):
        return b'\x28'

    def compressstream(self, it, opts=None):
        opts = opts or {}
        # zstd level 3 is almost always significantly faster than zlib
        # while providing no worse compression. It strikes a good balance
        # between speed and compression.
        level = opts.get(b'level', 3)

        zstd = self._module
        z = zstd.ZstdCompressor(level=level).compressobj()
        for chunk in it:
            data = z.compress(chunk)
            if data:
                yield data

        yield z.flush()

    def decompressorreader(self, fh):
        return _ZstdCompressedStreamReader(fh, self._module)

    class zstdrevlogcompressor(object):
        def __init__(self, zstd, level=3):
            # TODO consider omitting frame magic to save 4 bytes.
            # This writes content sizes into the frame header. That is
            # extra storage. But it allows a correct size memory allocation
            # to hold the result.
            self._cctx = zstd.ZstdCompressor(level=level)
            self._dctx = zstd.ZstdDecompressor()
            self._compinsize = zstd.COMPRESSION_RECOMMENDED_INPUT_SIZE
            self._decompinsize = zstd.DECOMPRESSION_RECOMMENDED_INPUT_SIZE

        def compress(self, data):
            insize = len(data)
            # Caller handles empty input case.
            assert insize > 0

            if insize < 50:
                return None

            elif insize <= 1000000:
                compressed = self._cctx.compress(data)
                if len(compressed) < insize:
                    return compressed
                return None
            else:
                z = self._cctx.compressobj()
                chunks = []
                pos = 0
                while pos < insize:
                    pos2 = pos + self._compinsize
                    chunk = z.compress(data[pos:pos2])
                    if chunk:
                        chunks.append(chunk)
                    pos = pos2
                chunks.append(z.flush())

                if sum(map(len, chunks)) < insize:
                    return b''.join(chunks)
                return None

        def decompress(self, data):
            insize = len(data)

            try:
                # This was measured to be faster than other streaming
                # decompressors.
                dobj = self._dctx.decompressobj()
                chunks = []
                pos = 0
                while pos < insize:
                    pos2 = pos + self._decompinsize
                    chunk = dobj.decompress(data[pos:pos2])
                    if chunk:
                        chunks.append(chunk)
                    pos = pos2
                # Frame should be exhausted, so no finish() API.

                return b''.join(chunks)
            except Exception as e:
                raise error.StorageError(
                    _(b'revlog decompress error: %s')
                    % stringutil.forcebytestr(e)
                )

    def revlogcompressor(self, opts=None):
        opts = opts or {}
        level = opts.get(b'zstd.level')
        if level is None:
            level = opts.get(b'level')
        if level is None:
            level = 3
        return self.zstdrevlogcompressor(self._module, level=level)


compengines.register(_zstdengine())


def bundlecompressiontopics():
    """Obtains a list of available bundle compressions for use in help."""
    # help.makeitemsdocs() expects a dict of names to items with a .__doc__.
    items = {}

    # We need to format the docstring. So use a dummy object/type to hold it
    # rather than mutating the original.
    class docobject(object):
        pass

    for name in compengines:
        engine = compengines[name]

        if not engine.available():
            continue

        bt = engine.bundletype()
        if not bt or not bt[0]:
            continue

        doc = b'``%s``\n    %s' % (bt[0], pycompat.getdoc(engine.bundletype))

        value = docobject()
        value.__doc__ = pycompat.sysstr(doc)
        value._origdoc = engine.bundletype.__doc__
        value._origfunc = engine.bundletype

        items[bt[0]] = value

    return items


i18nfunctions = bundlecompressiontopics().values()