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

}

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

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

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

    """

    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 _slicechunk(revlog, revs):

    """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.

    """

    start = revlog.start

    length = revlog.length

    if len(revs) <= 1:

        yield revs

        return

    startbyte = start(revs[0])

    endbyte = start(revs[-1]) + length(revs[-1])

    readdata = deltachainspan = endbyte - startbyte

    chainpayload = sum(length(r) for r in revs)

    if deltachainspan:

        density = chainpayload / float(deltachainspan)

    else:

        density = 1.0

    # Store the gaps in a heap to have them sorted by decreasing size

    gapsheap = []

    heapq.heapify(gapsheap)

    prevend = None

    for i, rev in enumerate(revs):

        revstart = start(rev)

        revlen = length(rev)

        # Skip empty revisions to form larger holes

        if revlen == 0:

            continue

        if prevend is not None:

            gapsize = revstart - prevend

            # only consider holes that are large enough

            if gapsize > revlog._srmingapsize:

                heapq.heappush(gapsheap, (-gapsize, i))

        prevend = revstart + revlen

    # Collect the indices of the largest holes until the density is acceptable

    indicesheap = []

    heapq.heapify(indicesheap)

    while gapsheap and density < revlog._srdensitythreshold:

        oppgapsize, gapidx = heapq.heappop(gapsheap)

        heapq.heappush(indicesheap, gapidx)

        # the gap sizes are stored as negatives to be sorted decreasingly

        # by the heap

        readdata -= (-oppgapsize)

        if readdata > 0:

            density = chainpayload / float(readdata)

        else:

            density = 1.0

    # Cut the revs at collected indices

    previdx = 0

    while indicesheap:

        idx = heapq.heappop(indicesheap)

        chunk = _trimchunk(revlog, revs, previdx, idx)

        if chunk:

            yield chunk

        previdx = idx

    chunk = _trimchunk(revlog, revs, previdx)

    if chunk:

        yield chunk

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

class _deltainfo(object):

    distance = attr.ib()

    deltalen = attr.ib()

    data = attr.ib()

    base = attr.ib()

    chainbase = attr.ib()

    chainlen = attr.ib()

    compresseddeltalen = attr.ib()

class _deltacomputer(object):

    def __init__(self, revlog):

        self.revlog = revlog

    def _getcandidaterevs(self, p1, p2, cachedelta):

        """

        Provides revisions that present an interest to be diffed against,

        grouped by level of easiness.

        """

        revlog = self.revlog

        curr = len(revlog)

        prev = curr - 1

        p1r, p2r = revlog.rev(p1), revlog.rev(p2)

        # should we try to build a delta?

        if prev != nullrev and revlog.storedeltachains:

            tested = set()

            # This condition is true most of the time when processing

            # changegroup data into a generaldelta repo. The only time it

            # isn't true is if this is the first revision in a delta chain

            # or if ``format.generaldelta=true`` disabled ``lazydeltabase``.

            if cachedelta and revlog._generaldelta and revlog._lazydeltabase:

                # Assume what we received from the server is a good choice

                # build delta will reuse the cache

                yield (cachedelta[0],)

                tested.add(cachedelta[0])

            if revlog._generaldelta:

                # exclude already lazy tested base if any

                parents = [p for p in (p1r, p2r)

                           if p != nullrev and p not in tested]

                if parents and not revlog._aggressivemergedeltas:

                    # Pick whichever parent is closer to us (to minimize the

                    # chance of having to build a fulltext).

                    parents = [max(parents)]

                tested.update(parents)

                yield parents

            if prev not in tested:

                # other approach failed try against prev to hopefully save us a

                # fulltext.

                yield (prev,)

    def buildtext(self, revinfo, fh):

        """Builds a fulltext version of a revision

        revinfo: _revisioninfo instance that contains all needed info

        fh:      file handle to either the .i or the .d revlog file,

                 depending on whether it is inlined or not

        """

        btext = revinfo.btext

        if btext[0] is not None:

            return btext[0]

        revlog = self.revlog

        cachedelta = revinfo.cachedelta

        flags = revinfo.flags

        node = revinfo.node

        baserev = cachedelta[0]

        delta = cachedelta[1]

        # special case deltas which replace entire base; no need to decode

        # base revision. this neatly avoids censored bases, which throw when

        # they're decoded.

        hlen = struct.calcsize(">lll")

        if delta[:hlen] == mdiff.replacediffheader(revlog.rawsize(baserev),

                                                   len(delta) - hlen):

            btext[0] = delta[hlen:]

        else:

            # deltabase is rawtext before changed by flag processors, which is

            # equivalent to non-raw text

            basetext = revlog.revision(baserev, _df=fh, raw=False)

            btext[0] = mdiff.patch(basetext, delta)

        try:

            res = revlog._processflags(btext[0], flags, 'read', raw=True)

            btext[0], validatehash = res

            if validatehash:

                revlog.checkhash(btext[0], node, p1=revinfo.p1, p2=revinfo.p2)

            if flags & REVIDX_ISCENSORED:

                raise RevlogError(_('node %s is not censored') % node)

        except CensoredNodeError:

            # must pass the censored index flag to add censored revisions

            if not flags & REVIDX_ISCENSORED:

                raise

        return btext[0]

    def _builddeltadiff(self, base, revinfo, fh):

        revlog = self.revlog

        t = self.buildtext(revinfo, fh)

        if revlog.iscensored(base):

            # deltas based on a censored revision must replace the

            # full content in one patch, so delta works everywhere

            header = mdiff.replacediffheader(revlog.rawsize(base), len(t))

            delta = header + t

        else:

            ptext = revlog.revision(base, _df=fh, raw=True)

            delta = mdiff.textdiff(ptext, t)

        return delta

    def _builddeltainfo(self, revinfo, base, fh):

        # can we use the cached delta?

        if revinfo.cachedelta and revinfo.cachedelta[0] == base:

            delta = revinfo.cachedelta[1]

        else:

            delta = self._builddeltadiff(base, revinfo, fh)

        revlog = self.revlog

        header, data = revlog.compress(delta)

        deltalen = len(header) + len(data)

        chainbase = revlog.chainbase(base)

        offset = revlog.end(len(revlog) - 1)

        dist = deltalen + offset - revlog.start(chainbase)

        if revlog._generaldelta:

            deltabase = base

        else:

            deltabase = chainbase

        chainlen, compresseddeltalen = revlog._chaininfo(base)

        chainlen += 1

        compresseddeltalen += deltalen

        return _deltainfo(dist, deltalen, (header, data), deltabase,

                         chainbase, chainlen, compresseddeltalen)

    def finddeltainfo(self, revinfo, fh):

        """Find an acceptable delta against a candidate revision

        revinfo: information about the revision (instance of _revisioninfo)

        fh:      file handle to either the .i or the .d revlog file,

                 depending on whether it is inlined or not

        Returns the first acceptable candidate revision, as ordered by

        _getcandidaterevs

        """

        cachedelta = revinfo.cachedelta

        p1 = revinfo.p1

        p2 = revinfo.p2

        revlog = self.revlog

        deltainfo = None

        for candidaterevs in self._getcandidaterevs(p1, p2, cachedelta):

            nominateddeltas = []

            for candidaterev in candidaterevs:

                # no delta for rawtext-changing revs (see "candelta" for why)

                if revlog.flags(candidaterev) & REVIDX_RAWTEXT_CHANGING_FLAGS:

                    continue

                candidatedelta = self._builddeltainfo(revinfo, candidaterev, fh)

                if revlog._isgooddeltainfo(candidatedelta, revinfo.textlen):

                    nominateddeltas.append(candidatedelta)

            if nominateddeltas:

                deltainfo = min(nominateddeltas, key=lambda x: x.deltalen)

                break

        return deltainfo

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

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