# revlog.py - storage back-end for mercurial

#

# Copyright 2005-2007 Olivia Mackall <olivia@selenic.com>

#

# This software may be used and distributed according to the terms of the

# GNU General Public License version 2 or any later version.

"""Storage back-end for Mercurial.

This provides efficient delta storage with O(1) retrieve and append

and O(changes) merge between branches.

"""

from __future__ import absolute_import

import binascii

import collections

import contextlib

import errno

import io

import os

import struct

import zlib

# import stuff from node for others to import from revlog

from .node import (

    bin,

    hex,

    nullrev,

    sha1nodeconstants,

    short,

    wdirrev,

)

from .i18n import _

from .pycompat import getattr

from .revlogutils.constants import (

    ALL_KINDS,

    CHANGELOGV2,

    COMP_MODE_DEFAULT,

    COMP_MODE_INLINE,

    COMP_MODE_PLAIN,

    FEATURES_BY_VERSION,

    FLAG_GENERALDELTA,

    FLAG_INLINE_DATA,

    INDEX_HEADER,

    KIND_CHANGELOG,

    REVLOGV0,

    REVLOGV1,

    REVLOGV1_FLAGS,

    REVLOGV2,

    REVLOGV2_FLAGS,

    REVLOG_DEFAULT_FLAGS,

    REVLOG_DEFAULT_FORMAT,

    REVLOG_DEFAULT_VERSION,

    SUPPORTED_FLAGS,

)

from .revlogutils.flagutil import (

    REVIDX_DEFAULT_FLAGS,

    REVIDX_ELLIPSIS,

    REVIDX_EXTSTORED,

    REVIDX_FLAGS_ORDER,

    REVIDX_HASCOPIESINFO,

    REVIDX_ISCENSORED,

    REVIDX_RAWTEXT_CHANGING_FLAGS,

)

from .thirdparty import attr

from . import (

    ancestor,

    dagop,

    error,

    mdiff,

    policy,

    pycompat,

    templatefilters,

    util,

)

from .interfaces import (

    repository,

    util as interfaceutil,

)

from .revlogutils import (

    deltas as deltautil,

    docket as docketutil,

    flagutil,

    nodemap as nodemaputil,

    revlogv0,

    sidedata as sidedatautil,

)

from .utils import (

    storageutil,

    stringutil,

)

# blanked usage of all the name to prevent pyflakes constraints

# We need these name available in the module for extensions.

REVLOGV0

REVLOGV1

REVLOGV2

FLAG_INLINE_DATA

FLAG_GENERALDELTA

REVLOG_DEFAULT_FLAGS

REVLOG_DEFAULT_FORMAT

REVLOG_DEFAULT_VERSION

REVLOGV1_FLAGS

REVLOGV2_FLAGS

REVIDX_ISCENSORED

REVIDX_ELLIPSIS

REVIDX_HASCOPIESINFO

REVIDX_EXTSTORED

REVIDX_DEFAULT_FLAGS

REVIDX_FLAGS_ORDER

REVIDX_RAWTEXT_CHANGING_FLAGS

parsers = policy.importmod('parsers')

rustancestor = policy.importrust('ancestor')

rustdagop = policy.importrust('dagop')

rustrevlog = policy.importrust('revlog')

# Aliased for performance.

_zlibdecompress = zlib.decompress

# max size of revlog with inline data

_maxinline = 131072

_chunksize = 1048576

# Flag processors for REVIDX_ELLIPSIS.

def ellipsisreadprocessor(rl, text):

    return text, False

def ellipsiswriteprocessor(rl, text):

    return text, False

def ellipsisrawprocessor(rl, text):

    return False

ellipsisprocessor = (

    ellipsisreadprocessor,

    ellipsiswriteprocessor,

    ellipsisrawprocessor,

)

def offset_type(offset, type):

    if (type & ~flagutil.REVIDX_KNOWN_FLAGS) != 0:

        raise ValueError(b'unknown revlog index flags')

    return int(int(offset) << 16 | type)

def _verify_revision(rl, skipflags, state, node):

    """Verify the integrity of the given revlog ``node`` while providing a hook

    point for extensions to influence the operation."""

    if skipflags:

        state[b'skipread'].add(node)

    else:

        # Side-effect: read content and verify hash.

        rl.revision(node)

# True if a fast implementation for persistent-nodemap is available

#

# We also consider we have a "fast" implementation in "pure" python because

# people using pure don't really have performance consideration (and a

# wheelbarrow of other slowness source)

HAS_FAST_PERSISTENT_NODEMAP = rustrevlog is not None or util.safehasattr(

    parsers, 'BaseIndexObject'

)

@attr.s(slots=True, frozen=True)

class _revisioninfo(object):

    """Information about a revision that allows building its fulltext

    node:       expected hash of the revision

    p1, p2:     parent revs of the revision

    btext:      built text cache consisting of a one-element list

    cachedelta: (baserev, uncompressed_delta) or None

    flags:      flags associated to the revision storage

    One of btext[0] or cachedelta must be set.

    """

    node = attr.ib()

    p1 = attr.ib()

    p2 = attr.ib()

    btext = attr.ib()

    textlen = attr.ib()

    cachedelta = attr.ib()

    flags = attr.ib()

@interfaceutil.implementer(repository.irevisiondelta)

@attr.s(slots=True)

class revlogrevisiondelta(object):

    node = attr.ib()

    p1node = attr.ib()

    p2node = attr.ib()

    basenode = attr.ib()

    flags = attr.ib()

    baserevisionsize = attr.ib()

    revision = attr.ib()

    delta = attr.ib()

    sidedata = attr.ib()

    protocol_flags = attr.ib()

    linknode = attr.ib(default=None)

@interfaceutil.implementer(repository.iverifyproblem)

@attr.s(frozen=True)

class revlogproblem(object):

    warning = attr.ib(default=None)

    error = attr.ib(default=None)

    node = attr.ib(default=None)

def parse_index_v1(data, inline):

    # call the C implementation to parse the index data

    index, cache = parsers.parse_index2(data, inline)

    return index, cache

def parse_index_v2(data, inline):

    # call the C implementation to parse the index data

    index, cache = parsers.parse_index2(data, inline, revlogv2=True)

    return index, cache

def parse_index_cl_v2(data, inline):

    # call the C implementation to parse the index data

    assert not inline

    from .pure.parsers import parse_index_cl_v2

    index, cache = parse_index_cl_v2(data)

    return index, cache

if util.safehasattr(parsers, 'parse_index_devel_nodemap'):

    def parse_index_v1_nodemap(data, inline):

        index, cache = parsers.parse_index_devel_nodemap(data, inline)

        return index, cache

else:

    parse_index_v1_nodemap = None

def parse_index_v1_mixed(data, inline):

    index, cache = parse_index_v1(data, inline)

    return rustrevlog.MixedIndex(index), cache

# corresponds to uncompressed length of indexformatng (2 gigs, 4-byte

# signed integer)

_maxentrysize = 0x7FFFFFFF

class revlog(object):

    """

    the underlying revision storage object

    A revlog consists of two parts, an index and the revision data.

    The index is a file with a fixed record size containing

    information on each revision, including its nodeid (hash), the

    nodeids of its parents, the position and offset of its data within

    the data file, and the revision it's based on. Finally, each entry

    contains a linkrev entry that can serve as a pointer to external

    data.

    The revision data itself is a linear collection of data chunks.

    Each chunk represents a revision and is usually represented as a

    delta against the previous chunk. To bound lookup time, runs of

    deltas are limited to about 2 times the length of the original

    version data. This makes retrieval of a version proportional to

    its size, or O(1) relative to the number of revisions.

    Both pieces of the revlog are written to in an append-only

    fashion, which means we never need to rewrite a file to insert or

    remove data, and can use some simple techniques to avoid the need

    for locking while reading.

    If checkambig, indexfile is opened with checkambig=True at

    writing, to avoid file stat ambiguity.

    If mmaplargeindex is True, and an mmapindexthreshold is set, the

    index will be mmapped rather than read if it is larger than the

    configured threshold.

    If censorable is True, the revlog can have censored revisions.

    If `upperboundcomp` is not None, this is the expected maximal gain from

    compression for the data content.

    `concurrencychecker` is an optional function that receives 3 arguments: a

    file handle, a filename, and an expected position. It should check whether

    the current position in the file handle is valid, and log/warn/fail (by

    raising).

    Internal details

    ----------------

    A large part of the revlog logic deals with revisions' "index entries", tuple

    objects that contains the same "items" whatever the revlog version.

    Different versions will have different ways of storing these items (sometimes

    not having them at all), but the tuple will always be the same. New fields

    are usually added at the end to avoid breaking existing code that relies

    on the existing order. The field are defined as follows:

    [0] offset:

            The byte index of the start of revision data chunk.

            That value is shifted up by 16 bits. use "offset = field >> 16" to

            retrieve it.

        flags:

            A flag field that carries special information or changes the behavior

            of the revision. (see `REVIDX_*` constants for details)

            The flag field only occupies the first 16 bits of this field,

            use "flags = field & 0xFFFF" to retrieve the value.

    [1] compressed length:

            The size, in bytes, of the chunk on disk

    [2] uncompressed length:

            The size, in bytes, of the full revision once reconstructed.

    [3] base rev:

            Either the base of the revision delta chain (without general

            delta), or the base of the delta (stored in the data chunk)

            with general delta.

    [4] link rev:

            Changelog revision number of the changeset introducing this

            revision.

    [5] parent 1 rev:

            Revision number of the first parent

    [6] parent 2 rev:

            Revision number of the second parent

    [7] node id:

            The node id of the current revision

    [8] sidedata offset:

            The byte index of the start of the revision's side-data chunk.

    [9] sidedata chunk length:

            The size, in bytes, of the revision's side-data chunk.

    [10] data compression mode:

            two bits that detail the way the data chunk is compressed on disk.

            (see "COMP_MODE_*" constants for details). For revlog version 0 and

            1 this will always be COMP_MODE_INLINE.

    [11] side-data compression mode:

            two bits that detail the way the sidedata chunk is compressed on disk.

            (see "COMP_MODE_*" constants for details)

    """

    _flagserrorclass = error.RevlogError

    def __init__(

        self,

        opener,

        target,

        radix,

        postfix=None,  # only exist for `tmpcensored` now

        checkambig=False,

        mmaplargeindex=False,

        censorable=False,

        upperboundcomp=None,

        persistentnodemap=False,

        concurrencychecker=None,

        trypending=False,

    ):

        """

        create a revlog object

        opener is a function that abstracts the file opening operation

        and can be used to implement COW semantics or the like.

        `target`: a (KIND, ID) tuple that identify the content stored in

        this revlog. It help the rest of the code to understand what the revlog

        is about without having to resort to heuristic and index filename

        analysis. Note: that this must be reliably be set by normal code, but

        that test, debug, or performance measurement code might not set this to

        accurate value.

        """

        self.upperboundcomp = upperboundcomp

        self.radix = radix

        self._docket_file = None

        self._indexfile = None

        self._datafile = None

        self._nodemap_file = None

        self.postfix = postfix

        self._trypending = trypending

        self.opener = opener

        if persistentnodemap:

            self._nodemap_file = nodemaputil.get_nodemap_file(self)

        assert target[0] in ALL_KINDS

        assert len(target) == 2

        self.target = target

        #  When True, indexfile is opened with checkambig=True at writing, to

        #  avoid file stat ambiguity.

        self._checkambig = checkambig

        self._mmaplargeindex = mmaplargeindex

        self._censorable = censorable

        # 3-tuple of (node, rev, text) for a raw revision.

        self._revisioncache = None

        # Maps rev to chain base rev.

        self._chainbasecache = util.lrucachedict(100)

        # 2-tuple of (offset, data) of raw data from the revlog at an offset.

        self._chunkcache = (0, b'')

        # How much data to read and cache into the raw revlog data cache.

        self._chunkcachesize = 65536

        self._maxchainlen = None

        self._deltabothparents = True

        self.index = None

        self._docket = None

        self._nodemap_docket = None

        # Mapping of partial identifiers to full nodes.

        self._pcache = {}

        # Mapping of revision integer to full node.

        self._compengine = b'zlib'

        self._compengineopts = {}

        self._maxdeltachainspan = -1

        self._withsparseread = False

        self._sparserevlog = False

        self.hassidedata = False

        self._srdensitythreshold = 0.50

        self._srmingapsize = 262144

        # Make copy of flag processors so each revlog instance can support

        # custom flags.

        self._flagprocessors = dict(flagutil.flagprocessors)

        # 2-tuple of file handles being used for active writing.

        self._writinghandles = None

        # prevent nesting of addgroup

        self._adding_group = None

        self._loadindex()

        self._concurrencychecker = concurrencychecker

    def _init_opts(self):

        """process options (from above/config) to setup associated default revlog mode

        These values might be affected when actually reading on disk information.

        The relevant values are returned for use in _loadindex().

        * newversionflags:

            version header to use if we need to create a new revlog

        * mmapindexthreshold:

            minimal index size for start to use mmap

        * force_nodemap:

            force the usage of a "development" version of the nodemap code

        """

        mmapindexthreshold = None

        opts = self.opener.options

        if b'changelogv2' in opts and self.revlog_kind == KIND_CHANGELOG:

            new_header = CHANGELOGV2

        elif b'revlogv2' in opts:

            new_header = REVLOGV2

        elif b'revlogv1' in opts:

            new_header = REVLOGV1 | FLAG_INLINE_DATA

            if b'generaldelta' in opts:

                new_header |= FLAG_GENERALDELTA

        elif b'revlogv0' in self.opener.options:

            new_header = REVLOGV0

        else:

            new_header = REVLOG_DEFAULT_VERSION