# revlog.py - storage back-end for mercurial

#

# Copyright 2005-2007 Matt Mackall <mpm@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 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,

    nullhex,

    nullid,

    nullrev,

    short,

    wdirfilenodeids,

    wdirhex,

    wdirid,

    wdirrev,

)

from .i18n import _

from .revlogutils.constants import (

    FLAG_GENERALDELTA,

    FLAG_INLINE_DATA,

    REVLOGV0,

    REVLOGV1,

    REVLOGV1_FLAGS,

    REVLOGV2,

    REVLOGV2_FLAGS,

    REVLOG_DEFAULT_FLAGS,

    REVLOG_DEFAULT_FORMAT,

    REVLOG_DEFAULT_VERSION,

)

from .revlogutils.flagutil import (

    REVIDX_DEFAULT_FLAGS,

    REVIDX_ELLIPSIS,

    REVIDX_EXTSTORED,

    REVIDX_FLAGS_ORDER,

    REVIDX_ISCENSORED,

    REVIDX_RAWTEXT_CHANGING_FLAGS,

)

from .thirdparty import (

    attr,

)

from . import (

    ancestor,

    dagop,

    error,

    mdiff,

    policy,

    pycompat,

    repository,

    templatefilters,

    util,

)

from .revlogutils import (

    deltas as deltautil,

    flagutil,

)

from .utils import (

    interfaceutil,

    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_EXTSTORED

REVIDX_DEFAULT_FLAGS

REVIDX_FLAGS_ORDER

REVIDX_RAWTEXT_CHANGING_FLAGS

parsers = policy.importmod(r'parsers')

rustancestor = policy.importrust(r'ancestor')

rustdagop = policy.importrust(r'dagop')

# 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 getoffset(q):

    return int(q >> 16)

def gettype(q):

    return int(q & 0xFFFF)

def offset_type(offset, type):

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

        raise ValueError('unknown revlog index flags')

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

@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()

    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)

# index v0:

#  4 bytes: offset

#  4 bytes: compressed length

#  4 bytes: base rev

#  4 bytes: link rev

# 20 bytes: parent 1 nodeid

# 20 bytes: parent 2 nodeid

# 20 bytes: nodeid

indexformatv0 = struct.Struct(">4l20s20s20s")

indexformatv0_pack = indexformatv0.pack

indexformatv0_unpack = indexformatv0.unpack

class revlogoldindex(list):

    def __getitem__(self, i):

        if i == -1:

            return (0, 0, 0, -1, -1, -1, -1, nullid)

        return list.__getitem__(self, i)

class revlogoldio(object):

    def __init__(self):

        self.size = indexformatv0.size

    def parseindex(self, data, inline):

        s = self.size

        index = []

        nodemap = {nullid: nullrev}

        n = off = 0

        l = len(data)

        while off + s <= l:

            cur = data[off:off + s]

            off += s

            e = indexformatv0_unpack(cur)

            # transform to revlogv1 format

            e2 = (offset_type(e[0], 0), e[1], -1, e[2], e[3],

                  nodemap.get(e[4], nullrev), nodemap.get(e[5], nullrev), e[6])

            index.append(e2)

            nodemap[e[6]] = n

            n += 1

        return revlogoldindex(index), nodemap, None

    def packentry(self, entry, node, version, rev):

        if gettype(entry[0]):

            raise error.RevlogError(_('index entry flags need revlog '

                                      'version 1'))

        e2 = (getoffset(entry[0]), entry[1], entry[3], entry[4],

              node(entry[5]), node(entry[6]), entry[7])

        return indexformatv0_pack(*e2)

# index ng:

#  6 bytes: offset

#  2 bytes: flags

#  4 bytes: compressed length

#  4 bytes: uncompressed length

#  4 bytes: base rev

#  4 bytes: link rev

#  4 bytes: parent 1 rev

#  4 bytes: parent 2 rev

# 32 bytes: nodeid

indexformatng = struct.Struct(">Qiiiiii20s12x")

indexformatng_pack = indexformatng.pack

versionformat = struct.Struct(">I")

versionformat_pack = versionformat.pack

versionformat_unpack = versionformat.unpack

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

# signed integer)

_maxentrysize = 0x7fffffff

class revlogio(object):

    def __init__(self):

        self.size = indexformatng.size

    def parseindex(self, data, inline):

        # call the C implementation to parse the index data

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

        return index, getattr(index, 'nodemap', None), cache

    def packentry(self, entry, node, version, rev):

        p = indexformatng_pack(*entry)

        if rev == 0:

            p = versionformat_pack(version) + p[4:]

        return p

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.

    """

    def __init__(self, opener, indexfile, datafile=None, checkambig=False,

                 mmaplargeindex=False, censorable=False,

                 upperboundcomp=None):

        """

        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.

        """

        self.upperboundcomp = upperboundcomp

        self.indexfile = indexfile

        self.datafile = datafile or (indexfile[:-2] + ".d")

        self.opener = opener

        #  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, '')

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

        self._chunkcachesize = 65536

        self._maxchainlen = None

        self._deltabothparents = True

        self.index = []

        # Mapping of partial identifiers to full nodes.

        self._pcache = {}

        # Mapping of revision integer to full node.

        self._nodecache = {nullid: nullrev}

        self._nodepos = None

        self._compengine = 'zlib'

        self._compengineopts = {}

        self._maxdeltachainspan = -1

        self._withsparseread = False

        self._sparserevlog = 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

        self._loadindex()

    def _loadindex(self):

        mmapindexthreshold = None

        opts = getattr(self.opener, 'options', {}) or {}

        if 'revlogv2' in opts:

            newversionflags = REVLOGV2 | FLAG_INLINE_DATA

        elif 'revlogv1' in opts:

            newversionflags = REVLOGV1 | FLAG_INLINE_DATA

            if 'generaldelta' in opts:

                newversionflags |= FLAG_GENERALDELTA

        elif getattr(self.opener, 'options', None) is not None:

            # If options provided but no 'revlog*' found, the repository

            # would have no 'requires' file in it, which means we have to

            # stick to the old format.

            newversionflags = REVLOGV0

        else:

            newversionflags = REVLOG_DEFAULT_VERSION

        if 'chunkcachesize' in opts:

            self._chunkcachesize = opts['chunkcachesize']

        if 'maxchainlen' in opts:

            self._maxchainlen = opts['maxchainlen']

        if 'deltabothparents' in opts:

            self._deltabothparents = opts['deltabothparents']

        self._lazydelta = bool(opts.get('lazydelta', True))

        self._lazydeltabase = False

        if self._lazydelta:

            self._lazydeltabase = bool(opts.get('lazydeltabase', False))

        if 'compengine' in opts:

            self._compengine = opts['compengine']

        if 'zlib.level' in opts:

            self._compengineopts['zlib.level'] = opts['zlib.level']

        if 'zstd.level' in opts:

            self._compengineopts['zstd.level'] = opts['zstd.level']

        if 'maxdeltachainspan' in opts:

            self._maxdeltachainspan = opts['maxdeltachainspan']

        if self._mmaplargeindex and 'mmapindexthreshold' in opts:

            mmapindexthreshold = opts['mmapindexthreshold']

        self._sparserevlog = bool(opts.get('sparse-revlog', False))

        withsparseread = bool(opts.get('with-sparse-read', False))

        # sparse-revlog forces sparse-read

        self._withsparseread = self._sparserevlog or withsparseread

        if 'sparse-read-density-threshold' in opts:

            self._srdensitythreshold = opts['sparse-read-density-threshold']

        if 'sparse-read-min-gap-size' in opts:

            self._srmingapsize = opts['sparse-read-min-gap-size']

        if opts.get('enableellipsis'):

            self._flagprocessors[REVIDX_ELLIPSIS] = ellipsisprocessor

        # revlog v0 doesn't have flag processors

        for flag, processor in opts.get(b'flagprocessors', {}).iteritems():

            flagutil.insertflagprocessor(flag, processor, self._flagprocessors)

        if self._chunkcachesize <= 0:

            raise error.RevlogError(_('revlog chunk cache size %r is not '

                                      'greater than 0') % self._chunkcachesize)

        elif self._chunkcachesize & (self._chunkcachesize - 1):

            raise error.RevlogError(_('revlog chunk cache size %r is not a '

                                      'power of 2') % self._chunkcachesize)

        indexdata = ''

        self._initempty = True

        try:

            with self._indexfp() as f:

                if (mmapindexthreshold is not None and

                    self.opener.fstat(f).st_size >= mmapindexthreshold):

                    # TODO: should .close() to release resources without

                    # relying on Python GC

                    indexdata = util.buffer(util.mmapread(f))

                else:

                    indexdata = f.read()

            if len(indexdata) > 0:

                versionflags = versionformat_unpack(indexdata[:4])[0]

                self._initempty = False

            else:

                versionflags = newversionflags

        except IOError as inst:

            if inst.errno != errno.ENOENT:

                raise

            versionflags = newversionflags

        self.version = versionflags

        flags = versionflags & ~0xFFFF

        fmt = versionflags & 0xFFFF

        if fmt == REVLOGV0:

            if flags:

                raise error.RevlogError(_('unknown flags (%#04x) in version %d '

                                          'revlog %s') %

                                        (flags >> 16, fmt, self.indexfile))

            self._inline = False

            self._generaldelta = False

        elif fmt == REVLOGV1:

            if flags & ~REVLOGV1_FLAGS:

                raise error.RevlogError(_('unknown flags (%#04x) in version %d '

                                          'revlog %s') %

                                        (flags >> 16, fmt, self.indexfile))

            self._inline = versionflags & FLAG_INLINE_DATA

            self._generaldelta = versionflags & FLAG_GENERALDELTA

        elif fmt == REVLOGV2:

            if flags & ~REVLOGV2_FLAGS:

                raise error.RevlogError(_('unknown flags (%#04x) in version %d '

                                          'revlog %s') %

                                        (flags >> 16, fmt, self.indexfile))

            self._inline = versionflags & FLAG_INLINE_DATA

            # generaldelta implied by version 2 revlogs.

            self._generaldelta = True

        else:

            raise error.RevlogError(_('unknown version (%d) in revlog %s') %

                                    (fmt, self.indexfile))

        # sparse-revlog can't be on without general-delta (issue6056)

        if not self._generaldelta:

            self._sparserevlog = False

        self._storedeltachains = True

        self._io = revlogio()

        if self.version == REVLOGV0:

            self._io = revlogoldio()

        try:

            d = self._io.parseindex(indexdata, self._inline)

        except (ValueError, IndexError):

            raise error.RevlogError(_("index %s is corrupted") %