# 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 errno

import hashlib

import os

import struct

import zlib

# import stuff from node for others to import from revlog

from .node import (

    bin,

    hex,

    nullid,

    nullrev,

    wdirhex,

    wdirid,

    wdirrev,

)

from .i18n import _

from . import (

    ancestor,

    error,

    mdiff,

    policy,

    pycompat,

    templatefilters,

    util,

)

parsers = policy.importmod(r'parsers')

_pack = struct.pack

_unpack = struct.unpack

# Aliased for performance.

_zlibdecompress = zlib.decompress

# revlog header flags

REVLOGV0 = 0

REVLOGV1 = 1

FLAG_INLINE_DATA = (1 << 16)

FLAG_GENERALDELTA = (1 << 17)

REVLOG_DEFAULT_FLAGS = FLAG_INLINE_DATA

REVLOG_DEFAULT_FORMAT = REVLOGV1

REVLOG_DEFAULT_VERSION = REVLOG_DEFAULT_FORMAT | REVLOG_DEFAULT_FLAGS

REVLOGV1_FLAGS = FLAG_INLINE_DATA | FLAG_GENERALDELTA

# revlog index flags

REVIDX_ISCENSORED = (1 << 15) # revision has censor metadata, must be verified

REVIDX_ELLIPSIS = (1 << 14) # revision hash does not match data (narrowhg)

REVIDX_EXTSTORED = (1 << 13) # revision data is stored externally

REVIDX_DEFAULT_FLAGS = 0

# stable order in which flags need to be processed and their processors applied

REVIDX_FLAGS_ORDER = [

    REVIDX_ISCENSORED,

    REVIDX_ELLIPSIS,

    REVIDX_EXTSTORED,

]

REVIDX_KNOWN_FLAGS = util.bitsfrom(REVIDX_FLAGS_ORDER)

# max size of revlog with inline data

_maxinline = 131072

_chunksize = 1048576

RevlogError = error.RevlogError

LookupError = error.LookupError

CensoredNodeError = error.CensoredNodeError

ProgrammingError = error.ProgrammingError

# Store flag processors (cf. 'addflagprocessor()' to register)

_flagprocessors = {

    REVIDX_ISCENSORED: None,

}

def addflagprocessor(flag, processor):

    """Register a flag processor on a revision data flag.

    Invariant:

    - Flags need to be defined in REVIDX_KNOWN_FLAGS and REVIDX_FLAGS_ORDER.

    - Only one flag processor can be registered on a specific flag.

    - flagprocessors must be 3-tuples of functions (read, write, raw) with the

      following signatures:

          - (read)  f(self, rawtext) -> text, bool

          - (write) f(self, text) -> rawtext, bool

          - (raw)   f(self, rawtext) -> bool

      "text" is presented to the user. "rawtext" is stored in revlog data, not

      directly visible to the user.

      The boolean returned by these transforms is used to determine whether

      the returned text can be used for hash integrity checking. For example,

      if "write" returns False, then "text" is used to generate hash. If

      "write" returns True, that basically means "rawtext" returned by "write"

      should be used to generate hash. Usually, "write" and "read" return

      different booleans. And "raw" returns a same boolean as "write".

      Note: The 'raw' transform is used for changegroup generation and in some

      debug commands. In this case the transform only indicates whether the

      contents can be used for hash integrity checks.

    """

    if not flag & REVIDX_KNOWN_FLAGS:

        msg = _("cannot register processor on unknown flag '%#x'.") % (flag)

        raise ProgrammingError(msg)

    if flag not in REVIDX_FLAGS_ORDER:

        msg = _("flag '%#x' undefined in REVIDX_FLAGS_ORDER.") % (flag)

        raise ProgrammingError(msg)

    if flag in _flagprocessors:

        msg = _("cannot register multiple processors on flag '%#x'.") % (flag)

        raise error.Abort(msg)

    _flagprocessors[flag] = processor

def getoffset(q):

    return int(q >> 16)

def gettype(q):

    return int(q & 0xFFFF)

def offset_type(offset, type):

    if (type & ~REVIDX_KNOWN_FLAGS) != 0:

        raise ValueError('unknown revlog index flags')

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

_nullhash = hashlib.sha1(nullid)

def hash(text, p1, p2):

    """generate a hash from the given text and its parent hashes

    This hash combines both the current file contents and its history

    in a manner that makes it easy to distinguish nodes with the same

    content in the revision graph.

    """

    # As of now, if one of the parent node is null, p2 is null

    if p2 == nullid:

        # deep copy of a hash is faster than creating one

        s = _nullhash.copy()

        s.update(p1)

    else:

        # none of the parent nodes are nullid

        l = [p1, p2]

        l.sort()

        s = hashlib.sha1(l[0])

        s.update(l[1])

    s.update(text)

    return s.digest()

# 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 = ">4l20s20s20s"

class revlogoldio(object):

    def __init__(self):

        self.size = struct.calcsize(indexformatv0)

    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 = _unpack(indexformatv0, 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

        # add the magic null revision at -1

        index.append((0, 0, 0, -1, -1, -1, -1, nullid))

        return index, nodemap, None

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

        if gettype(entry[0]):

            raise 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 _pack(indexformatv0, *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 = ">Qiiiiii20s12x"

versionformat = ">I"

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

# signed integer)

_maxentrysize = 0x7fffffff

class revlogio(object):

    def __init__(self):

        self.size = struct.calcsize(indexformatng)

    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 = _pack(indexformatng, *entry)

        if rev == 0:

            p = _pack(versionformat, 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.

    """

    def __init__(self, opener, indexfile, datafile=None, checkambig=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.

        """

        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

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

        self._cache = 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._aggressivemergedeltas = False

        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'

        v = REVLOG_DEFAULT_VERSION

        opts = getattr(opener, 'options', None)

        if opts is not None:

                if 'generaldelta' in opts:

                    v |= FLAG_GENERALDELTA

            else:

                v = 0

            if 'chunkcachesize' in opts:

                self._chunkcachesize = opts['chunkcachesize']

            if 'maxchainlen' in opts:

                self._maxchainlen = opts['maxchainlen']

            if 'aggressivemergedeltas' in opts:

                self._aggressivemergedeltas = opts['aggressivemergedeltas']

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

            if 'compengine' in opts:

                self._compengine = opts['compengine']

        if self._chunkcachesize <= 0:

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

                                'than 0') % self._chunkcachesize)

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

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

                                'of 2') % self._chunkcachesize)

        indexdata = ''

        self._initempty = True

        try:

            f = self.opener(self.indexfile)

            indexdata = f.read()

            f.close()

            if len(indexdata) > 0:

                v = struct.unpack(versionformat, indexdata[:4])[0]

                self._initempty = False

        except IOError as inst:

            if inst.errno != errno.ENOENT:

                raise

        self.version = v

        self._inline = v & FLAG_INLINE_DATA

        self._generaldelta = v & FLAG_GENERALDELTA

        flags = v & ~0xFFFF

        fmt = v & 0xFFFF

        if fmt == REVLOGV0:

            if flags:

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

                                    'revlog %s') %

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

        elif fmt == REVLOGV1:

            if flags & ~REVLOGV1_FLAGS:

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

                                    'revlog %s') %

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

        else:

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

                              (fmt, self.indexfile))

        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 RevlogError(_("index %s is corrupted") % (self.indexfile))

        self.index, nodemap, self._chunkcache = d

        if nodemap is not None:

            self.nodemap = self._nodecache = nodemap

        if not self._chunkcache:

            self._chunkclear()

        # revnum -> (chain-length, sum-delta-length)

        self._chaininfocache = {}

        # revlog header -> revlog compressor

        self._decompressors = {}

    @util.propertycache

    def _compressor(self):

        return util.compengines[self._compengine].revlogcompressor()

    def tip(self):

        return self.node(len(self.index) - 2)

    def __contains__(self, rev):

        return 0 <= rev < len(self)