# revlogdeltas.py - Logic around delta computation for revlog

#

# Copyright 2005-2007 Matt Mackall <mpm@selenic.com>

# Copyright 2018 Octobus <contact@octobus.net>

#

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

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

"""Helper class to compute deltas stored inside revlogs"""

from __future__ import absolute_import

import collections

import struct

# import stuff from node for others to import from revlog

from ..node import (

    nullrev,

)

from ..i18n import _

from .constants import (

    REVIDX_ISCENSORED,

    REVIDX_RAWTEXT_CHANGING_FLAGS,

)

from ..thirdparty import (

    attr,

)

from .. import (

    error,

    mdiff,

)

# maximum <delta-chain-data>/<revision-text-length> ratio

LIMIT_DELTA2TEXT = 2

class _testrevlog(object):

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

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

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

        self._data = data

        self._srdensitythreshold = density

        self._srmingapsize = mingap

        self._snapshot = set(snapshot)

        self.index = None

    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 __len__(self):

        return len(self._data)

    def issnapshot(self, rev):

        return rev in self._snapshot

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.

    >>> data = [

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

    ... ]

    >>> revlog = _testrevlog(data, snapshot=range(16))

    >>> 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], targetsize=15))

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

    >>> list(slicechunk(revlog, [0, 11, 13, 15], targetsize=20))

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

    """

    if targetsize is not None:

        targetsize = max(targetsize, revlog._srmingapsize)

    # targetsize should not be specified when evaluating delta candidates:

    # * targetsize is used to ensure we stay within specification when reading,

    densityslicing = getattr(revlog.index, 'slicechunktodensity', None)

    if densityslicing is None:

        densityslicing = lambda x, y, z: _slicechunktodensity(revlog, x, y, z)

    for chunk in densityslicing(revs,

                                revlog._srdensitythreshold,

                                revlog._srmingapsize):

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

            yield subchunk

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

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

    >>> data = [

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

    ... ]

    == All snapshots cases ==

    >>> revlog = _testrevlog(data, snapshot=range(9))

    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]]

    == No Snapshot cases ==

    >>> revlog = _testrevlog(data)

    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], [4, 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]]

    == mixed case ==

    >>> revlog = _testrevlog(data, snapshot=[0, 1, 2])

    >>> list(_slicechunktosize(revlog, list(range(9)), 5))

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

    """

    assert targetsize is None or 0 <= targetsize

    startdata = revlog.start(revs[0])

    enddata = revlog.end(revs[-1])

    fullspan = enddata - startdata

    if targetsize is None or fullspan <= targetsize:

        yield revs

        return

    startrevidx = 0

    endrevidx = 1

    iterrevs = enumerate(revs)

    next(iterrevs) # skip first rev.

    # first step: get snapshots out of the way

    for idx, r in iterrevs:

        span = revlog.end(r) - startdata

        snapshot = revlog.issnapshot(r)

        if span <= targetsize and snapshot:

            endrevidx = idx + 1

        else:

            chunk = _trimchunk(revlog, revs, startrevidx, endrevidx)

            if chunk:

                yield chunk

            startrevidx = idx

            startdata = revlog.start(r)

            endrevidx = idx + 1

        if not snapshot:

            break

    # for the others, we use binary slicing to quickly converge toward valid

    # chunks (otherwise, we might end up looking for start/end of many

    # revisions). This logic is not looking for the perfect slicing point, it

    # focuses on quickly converging toward valid chunks.

    nbitem = len(revs)

    while (enddata - startdata) > targetsize:

        endrevidx = nbitem

        if nbitem - startrevidx <= 1:

            break # protect against individual chunk larger than limit

        localenddata = revlog.end(revs[endrevidx - 1])

        span = localenddata - startdata

        while span > targetsize:

            if endrevidx - startrevidx <= 1:

                break # protect against individual chunk larger than limit

            endrevidx -= (endrevidx - startrevidx) // 2

            localenddata = revlog.end(revs[endrevidx - 1])

            span = localenddata - startdata

        chunk = _trimchunk(revlog, revs, startrevidx, endrevidx)

        if chunk:

            yield chunk

        startrevidx = endrevidx

        startdata = revlog.start(revs[startrevidx])

    chunk = _trimchunk(revlog, revs, startrevidx)

    if chunk:

        yield chunk

def _slicechunktodensity(revlog, revs, targetdensity=0.5,

                         mingapsize=0):

    """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 `targetdensity`. No gap smaller than `mingapsize` is

    skipped.

    >>> 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(_slicechunktodensity(revlog, list(range(16))))

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

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

    [[0], [15]]

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

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

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

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

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

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

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

    ...                           mingapsize=20))

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

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

    ...                           targetdensity=0.95))

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

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

    ...                           targetdensity=0.95, mingapsize=12))

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

    """

    start = revlog.start

    length = revlog.length

    if len(revs) <= 1:

        yield revs

        return

    deltachainspan = segmentspan(revlog, revs)

    if deltachainspan < mingapsize:

        yield revs

        return

    readdata = deltachainspan

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

    if deltachainspan:

        density = chainpayload / float(deltachainspan)

    else:

        density = 1.0

    if density >= targetdensity:

        yield revs

        return

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

    gaps = []

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

                gaps.append((gapsize, i))

        prevend = revstart + revlen

    # sort the gaps to pop them from largest to small

    gaps.sort()

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

    selected = []

    while gaps and density < targetdensity:

        gapsize, gapidx = gaps.pop()

        selected.append(gapidx)

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

        # by the heap

        readdata -= gapsize

        if readdata > 0:

            density = chainpayload / float(readdata)

        else:

            density = 1.0

    selected.sort()

    # Cut the revs at collected indices

    previdx = 0

    for idx in selected:

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

        if chunk:

            yield chunk

        previdx = idx

    chunk = _trimchunk(revlog, revs, previdx)

    if chunk:

        yield chunk

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)

    # If we have a non-emtpy delta candidate, there are nothing to trim

    if revs[endidx - 1] < len(revlog):

        # Trim empty revs at the end, except 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])