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

import heapq

import os

import re

import struct

import zlib

# import stuff from node for others to import from revlog

from .node import (

    bin,

    hex,

    nullid,

    nullrev,

    wdirfilenodeids,

    wdirhex,

    wdirid,

    wdirrev,

)

from .i18n import _

from .thirdparty import (

    attr,

)

from . import (

    ancestor,

    error,

    mdiff,

    policy,

    pycompat,

    templatefilters,

    util,

)

from .utils import (

    stringutil,

)

parsers = policy.importmod(r'parsers')

# Aliased for performance.

_zlibdecompress = zlib.decompress

# revlog header flags

REVLOGV0 = 0

REVLOGV1 = 1

# Dummy value until file format is finalized.

# Reminder: change the bounds check in revlog.__init__ when this is changed.

REVLOGV2 = 0xDEAD

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

REVLOGV2_FLAGS = REVLOGV1_FLAGS

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

# bitmark for flags that could cause rawdata content change

REVIDX_RAWTEXT_CHANGING_FLAGS = REVIDX_ISCENSORED | REVIDX_EXTSTORED

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

}

_mdre = re.compile('\1\n')

def parsemeta(text):

    """return (metadatadict, metadatasize)"""

    # text can be buffer, so we can't use .startswith or .index

    if text[:2] != '\1\n':

        return None, None

    s = _mdre.search(text, 2).start()

    mtext = text[2:s]

    meta = {}

    for l in mtext.splitlines():

        k, v = l.split(": ", 1)

        meta[k] = v

    return meta, (s + 2)

def packmeta(meta, text):

    keys = sorted(meta)

    metatext = "".join("%s: %s\n" % (k, meta[k]) for k in keys)

    return "\1\n%s\1\n%s" % (metatext, text)

def _censoredtext(text):

    m, offs = parsemeta(text)

    return m and "censored" in m

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,

      and REVIDX_RAWTEXT_CHANGING_FLAGS if they can alter rawtext.

    - 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

        if p1 < p2:

            a = p1

            b = p2

        else:

            a = p2

            b = p1

        s = hashlib.sha1(a)

        s.update(b)

    s.update(text)

    return s.digest()

class _testrevlog(object):

    """minimalist fake revlog to use in doctests"""

    def __init__(self, data, density=0.5, mingap=0):

        """data is an list of revision payload boundaries"""

        self._data = data

        self._srdensitythreshold = density

        self._srmingapsize = mingap

    def start(self, rev):

        if rev == 0:

            return 0

        return self._data[rev - 1]

    def end(self, rev):

        return self._data[rev]

    def length(self, rev):

        return self.end(rev) - self.start(rev)

def _trimchunk(revlog, revs, startidx, endidx=None):

    """returns revs[startidx:endidx] without empty trailing revs

    Doctest Setup

    >>> revlog = _testrevlog([

    ...  5,  #0

    ...  10, #1

    ...  12, #2

    ...  12, #3 (empty)

    ...  17, #4

    ...  21, #5

    ...  21, #6 (empty)

    ... ])

    Contiguous cases:

    >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0)

    [0, 1, 2, 3, 4, 5]

    >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0, 5)

    [0, 1, 2, 3, 4]

    >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0, 4)

    [0, 1, 2]

    >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 2, 4)

    [2]

    >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 3)

    [3, 4, 5]

    >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 3, 5)

    [3, 4]

    Discontiguous cases:

    >>> _trimchunk(revlog, [1, 3, 5, 6], 0)

    [1, 3, 5]

    >>> _trimchunk(revlog, [1, 3, 5, 6], 0, 2)

    [1]

    >>> _trimchunk(revlog, [1, 3, 5, 6], 1, 3)

    [3, 5]

    >>> _trimchunk(revlog, [1, 3, 5, 6], 1)

    [3, 5]

    """

    length = revlog.length

    if endidx is None:

        endidx = len(revs)

    # Trim empty revs at the end, but never the very first revision of a chain

    while endidx > 1 and endidx > startidx and length(revs[endidx - 1]) == 0:

        endidx -= 1

    return revs[startidx:endidx]

def _segmentspan(revlog, revs):

    """Get the byte span of a segment of revisions

    revs is a sorted array of revision numbers

    >>> revlog = _testrevlog([

    ...  5,  #0

    ...  10, #1

    ...  12, #2

    ...  12, #3 (empty)

    ...  17, #4

    ... ])

    >>> _segmentspan(revlog, [0, 1, 2, 3, 4])

    17

    >>> _segmentspan(revlog, [0, 4])

    17

    >>> _segmentspan(revlog, [3, 4])

    5

    >>> _segmentspan(revlog, [1, 2, 3,])

    7

    >>> _segmentspan(revlog, [1, 3])

    7

    """

    if not revs:

        return 0

    return revlog.end(revs[-1]) - revlog.start(revs[0])

def _slicechunk(revlog, revs, targetsize=None):

    """slice revs to reduce the amount of unrelated data to be read from disk.

    ``revs`` is sliced into groups that should be read in one time.

    Assume that revs are sorted.

    The initial chunk is sliced until the overall density (payload/chunks-span

    ratio) is above `revlog._srdensitythreshold`. No gap smaller than

    `revlog._srmingapsize` is skipped.

    If `targetsize` is set, no chunk larger than `targetsize` will be yield.

    For consistency with other slicing choice, this limit won't go lower than

    `revlog._srmingapsize`.

    If individual revisions chunk are larger than this limit, they will still

    be raised individually.

    >>> revlog = _testrevlog([

    ...  5,  #00 (5)

    ...  10, #01 (5)

    ...  12, #02 (2)

    ...  12, #03 (empty)

    ...  27, #04 (15)

    ...  31, #05 (4)

    ...  31, #06 (empty)

    ...  42, #07 (11)

    ...  47, #08 (5)

    ...  47, #09 (empty)

    ...  48, #10 (1)

    ...  51, #11 (3)

    ...  74, #12 (23)

    ...  85, #13 (11)

    ...  86, #14 (1)

    ...  91, #15 (5)

    ... ])

    >>> list(_slicechunk(revlog, list(range(16))))

    [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]]

    >>> list(_slicechunk(revlog, [0, 15]))

    [[0], [15]]

    >>> list(_slicechunk(revlog, [0, 11, 15]))

    [[0], [11], [15]]

    >>> list(_slicechunk(revlog, [0, 11, 13, 15]))

    [[0], [11, 13, 15]]

    >>> list(_slicechunk(revlog, [1, 2, 3, 5, 8, 10, 11, 14]))

    [[1, 2], [5, 8, 10, 11], [14]]

    Slicing with a maximum chunk size

    >>> list(_slicechunk(revlog, [0, 11, 13, 15], 15))

    [[0], [11], [13], [15]]

    >>> list(_slicechunk(revlog, [0, 11, 13, 15], 20))

    [[0], [11], [13, 15]]

    """

    if targetsize is not None:

        targetsize = max(targetsize, revlog._srmingapsize)

    for chunk in _slicechunktodensity(revlog, revs,

                                      revlog._srdensitythreshold,

                                      revlog._srmingapsize):

        for subchunk in _slicechunktosize(revlog, chunk, targetsize):

            yield subchunk

def _slicechunktosize(revlog, revs, targetsize):

    """slice revs to match the target size

    This is intended to be used on chunk that density slicing selected by that

    are still too large compared to the read garantee of revlog. This might

    happens when "minimal gap size" interrupted the slicing or when chain are

    built in a way that create large blocks next to each other.

    >>> revlog = _testrevlog([

    ...  3,  #0 (3)

    ...  5,  #1 (2)

    ...  6,  #2 (1)

    ...  8,  #3 (2)

    ...  8,  #4 (empty)

    ...  11, #5 (3)

    ...  12, #6 (1)

    ...  13, #7 (1)

    ...  14, #8 (1)

    ... ])

    Cases where chunk is already small enough

    >>> list(_slicechunktosize(revlog, [0], 3))

    [[0]]

    >>> list(_slicechunktosize(revlog, [6, 7], 3))

    [[6, 7]]

    >>> list(_slicechunktosize(revlog, [0], None))

    [[0]]

    >>> list(_slicechunktosize(revlog, [6, 7], None))

    [[6, 7]]

    cases where we need actual slicing

    >>> list(_slicechunktosize(revlog, [0, 1], 3))

    [[0], [1]]

    >>> list(_slicechunktosize(revlog, [1, 3], 3))

    [[1], [3]]

    >>> list(_slicechunktosize(revlog, [1, 2, 3], 3))

    [[1, 2], [3]]

    >>> list(_slicechunktosize(revlog, [3, 5], 3))

    [[3], [5]]

    >>> list(_slicechunktosize(revlog, [3, 4, 5], 3))

    [[3], [5]]

    >>> list(_slicechunktosize(revlog, [5, 6, 7, 8], 3))

    [[5], [6, 7, 8]]

    >>> list(_slicechunktosize(revlog, [0, 1, 2, 3, 4, 5, 6, 7, 8], 3))

    [[0], [1, 2], [3], [5], [6, 7, 8]]

    Case with too large individual chunk (must return valid chunk)

    >>> list(_slicechunktosize(revlog, [0, 1], 2))

    [[0], [1]]

    >>> list(_slicechunktosize(revlog, [1, 3], 1))

    [[1], [3]]

    >>> list(_slicechunktosize(revlog, [3, 4, 5], 2))

    [[3], [5]]

    """

    assert targetsize is None or 0 <= targetsize

    if targetsize is None or _segmentspan(revlog, revs) <= targetsize:

        yield revs

        return

    startrevidx = 0

    startdata = revlog.start(revs[0])

    endrevidx = 0

    iterrevs = enumerate(revs)

    next(iterrevs) # skip first rev.

    for idx, r in iterrevs: