# Code dedicated to the computation and properties of "stable ranges"

#

# These stable ranges are use for obsolescence markers discovery

#

# Copyright 2017 Pierre-Yves David <pierre-yves.david@ens-lyon.org>

#

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

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

import abc

import functools

import heapq

import math

import os

import time

from mercurial import (

    error,

    node as nodemod,

    pycompat,

    scmutil,

    util,

)

from mercurial.i18n import _

from . import (

    stablesort,

    exthelper,

    utility,

)

filterparents = utility.filterparents

eh = exthelper.exthelper()

eh.merge(stablesort.eh)

# prior to hg-4.2 there are not util.timer

if util.safehasattr(util, 'timer'):

    timer = util.timer

elif util.safehasattr(time, "perf_counter"):

    timer = time.perf_counter

elif getattr(pycompat, 'osname', os.name) == 'nt':

    timer = time.clock

else:

    timer = time.time

#################################

### Stable Range computation  ###

#################################

def _hlp2(i):

    """return highest power of two lower than 'i'"""

    return 2 ** int(math.log(i - 1, 2))

def subrangesclosure(repo, stablerange, heads):

    """set of all standard subrange under heads

    This is intended for debug purposes. Range are returned from largest to

    smallest in terms of number of revision it contains."""

    subranges = stablerange.subranges

    toproceed = [(r, 0, ) for r in heads]

    ranges = set(toproceed)

    while toproceed:

        entry = toproceed.pop()

        for r in subranges(repo, entry):

            if r not in ranges:

                ranges.add(r)

                toproceed.append(r)

    ranges = list(ranges)

    n = repo.changelog.node

    rangelength = stablerange.rangelength

    ranges.sort(key=lambda r: (-rangelength(repo, r), n(r[0])))

    return ranges

_stablerangemethodmap = {

    'branchpoint': lambda repo: repo.stablerange,

    'basic-branchpoint': lambda repo: stablerangebasic(),

    'basic-mergepoint': lambda repo: stablerangedummy_mergepoint(),

    'mergepoint': lambda repo: stablerange_mergepoint(),

}

@eh.command(

    'debugstablerange',

    [

        ('r', 'rev', [], 'operate on (rev, 0) ranges for rev in REVS'),

        ('', 'subranges', False, 'recursively display data for subranges too'),

        ('', 'verify', False, 'checks subranges content (EXPENSIVE)'),

        ('', 'method', 'branchpoint',

         'method to use, one of "branchpoint", "mergepoint"')

    ],

    _(''))

def debugstablerange(ui, repo, **opts):

    """display standard stable subrange for a set of ranges

    Range as displayed as '<node>-<index> (<rev>, <depth>, <length>)', use

    --verbose to get the extra details in ().

    """

    short = nodemod.short

    revs = scmutil.revrange(repo, opts['rev'])

    if not revs:

        raise error.Abort('no revisions specified')

    if ui.verbose:

        template = '%s-%d (%d, %d, %d)'

        def _rangestring(repo, rangeid):

            return template % (

                short(node(rangeid[0])),

                rangeid[1],

                rangeid[0],

                depth(unfi, rangeid[0]),

                length(unfi, rangeid)

            )

    else:

        template = '%s-%d'

        def _rangestring(repo, rangeid):

            return template % (

                short(node(rangeid[0])),

                rangeid[1],

            )

    # prewarm depth cache

    unfi = repo.unfiltered()

    node = unfi.changelog.node

    method = opts['method']

    getstablerange = _stablerangemethodmap.get(method)

    if getstablerange is None:

        raise error.Abort('unknown stable sort method: "%s"' % method)

    stablerange = getstablerange(unfi)

    depth = stablerange.depthrev

    length = stablerange.rangelength

    subranges = stablerange.subranges

    stablerange.warmup(repo, max(revs))

    if opts['subranges']:

        ranges = subrangesclosure(unfi, stablerange, revs)

    else:

        ranges = [(r, 0) for r in revs]

    for r in ranges:

        subs = subranges(unfi, r)

        subsstr = ', '.join(_rangestring(unfi, s) for s in subs)

        rstr = _rangestring(unfi, r)

        if opts['verify']:

            status = 'leaf'

            if 1 < length(unfi, r):

                status = 'complete'

                revs = set(stablerange.revsfromrange(unfi, r))

                subrevs = set()

                for s in subs:

                    subrevs.update(stablerange.revsfromrange(unfi, s))

                if revs != subrevs:

                    status = 'missing'

            ui.status('%s [%s] - %s\n' % (rstr, status, subsstr))

        else:

            ui.status('%s - %s\n' % (rstr, subsstr))

class abstractstablerange(object):

    """The official API for a stablerange"""

    __metaclass__ = abc.ABCMeta

    @abc.abstractmethod

    def subranges(self, repo, rangeid):

        """return the stable sub-ranges of a rangeid"""

        raise NotImplemented()

    @abc.abstractmethod

    def revsfromrange(self, repo, rangeid):

        """return revision contained in a range"""

        raise NotImplemented()

    @abc.abstractmethod

    def depthrev(self, repo, rev):

        """depth a revision"""

        # Exist to allow basic implementation to ignore the depthcache

        # Could be demoted to _depthrev.

        raise NotImplemented()

    @abc.abstractmethod

    def warmup(self, repo, upto=None):

        """warmup the stable range cache"""

        raise NotImplemented()

    @abc.abstractmethod

    def rangelength(self, repo, rangeid):

        """number of revision in <range>"""

        raise NotImplemented()

    def _slicepoint(self, repo, rangeid):

        """find the standard slicing point for a range"""

        rangedepth = self.depthrev(repo, rangeid[0])

        step = _hlp2(rangedepth)

        standard_start = 0

        while standard_start < rangeid[1] and 0 < step:

            if standard_start + step < rangedepth:

                standard_start += step

            step //= 2

        if rangeid[1] == standard_start:

            slicesize = _hlp2(self.rangelength(repo, rangeid))

            slicepoint = rangeid[1] + slicesize

        else:

            assert standard_start < rangedepth

            slicepoint = standard_start

        return slicepoint

class stablerangebasic(abstractstablerange):

    """a very dummy implementation of stablerange

    the implementation is here to lay down the basic algorithm in the stable

    range in a inefficient but easy to read manners. It should be used by test

    to validate output."""

    __metaclass__ = abc.ABCMeta

    def _sortfunction(self, repo, headrev):

        return stablesort.stablesort_branchpoint(repo, [headrev])

    def warmup(self, repo, upto=None):

        # no cache to warm for basic implementation

        pass

    def depthrev(self, repo, rev):

        """depth a revision"""

        return len(repo.revs('::%d', rev))

    def revsfromrange(self, repo, rangeid):

        """return revision contained in a range

        The range `(<head>, <skip>)` contains all revisions stable-sorted from

        <head>, skipping the <index>th lower revisions.

        """

        headrev, index = rangeid[0], rangeid[1]

        revs = self._sortfunction(repo, headrev)

        return revs[index:]

    def rangelength(self, repo, rangeid):

        """number of revision in <range>"""

        return len(self.revsfromrange(repo, rangeid))

    def subranges(self, repo, rangeid):

        """return the stable sub-ranges of a rangeid"""

        headrev, index = rangeid[0], rangeid[1]

        if self.rangelength(repo, rangeid) == 1:

            return []

        slicepoint = self._slicepoint(repo, rangeid)

        # search for range defining the lower set of revision

        #

        # we walk the lower set from the top following the stable order of the

        # current "head" of the lower range.

        #

        # As soon as the revision in the lowerset diverges from the one in the

        # range being generated, we emit the range and start a new one.

        result = []

        lowerrevs = self.revsfromrange(repo, rangeid)[:(slicepoint - index)]

        head = None

        headrange = None

        skip = None

        for rev in lowerrevs[::-1]:

            if head is None:

                head = rev

                headrange = self.revsfromrange(repo, (head, 0))

                skip = self.depthrev(repo, rev) - 1

            elif rev != headrange[skip - 1]:

                result.append((head, skip))

                head = rev

                headrange = self.revsfromrange(repo, (head, 0))

                skip = self.depthrev(repo, rev) - 1

            else:

                skip -= 1

        result.append((head, skip))

        result.reverse()

        # top part is trivial

        top = (headrev, slicepoint)

        result.append(top)

        # double check the result

        initialrevs = self.revsfromrange(repo, rangeid)

        subrangerevs = sum((self.revsfromrange(repo, sub) for sub in result),

                           [])

        assert initialrevs == subrangerevs

        return result

class stablerangedummy_mergepoint(stablerangebasic):

    """a very dummy implementation of stablerange use 'mergepoint' sorting

    """

    def _sortfunction(self, repo, headrev):

        return stablesort.stablesort_mergepoint_head_basic(repo, [headrev])

class stablerangecached(abstractstablerange):

    """an implementation of stablerange using caching"""

    __metaclass__ = abc.ABCMeta

    def __init__(self):

        # cache the standard stable subranges or a range

        self._subrangescache = {}

        super(stablerangecached, self).__init__()

    def depthrev(self, repo, rev):

        return repo.depthcache.get(rev)

    def rangelength(self, repo, rangeid):

        """number of revision in <range>"""

        headrev, index = rangeid[0], rangeid[1]

        return self.depthrev(repo, headrev) - index

    def subranges(self, repo, rangeid):

        assert 0 <= rangeid[1] <= rangeid[0], rangeid

        cached = self._getsub(rangeid)

        if cached is not None:

            return cached

        value = self._subranges(repo, rangeid)

        self._setsub(rangeid, value)

        return value

    def _getsub(self, rev):

        """utility function used to access the subranges cache

        This mostly exist to help the on disk persistence"""

        return self._subrangescache.get(rev)

    def _setsub(self, rev, value):

        """utility function used to set the subranges cache

        This mostly exist to help the on disk persistence."""

        self._subrangescache[rev] = value

class stablerange_mergepoint(stablerangecached):

    """Stablerange implementation using 'mergepoint' based sorting

    """

    def __init__(self):

        self._sortcache = stablesort.stablesortcache()

        super(stablerange_mergepoint, self).__init__()

    def warmup(self, repo, upto=None):

        # no cache to warm for basic implementation

        pass

    def revsfromrange(self, repo, rangeid):

        """return revision contained in a range

        The range `(<head>, <skip>)` contains all revisions stable-sorted from

        <head>, skipping the <index>th lower revisions.

        """

        limit = self.rangelength(repo, rangeid)

        return self._sortcache.get(repo, rangeid[0], limit=limit)

    def _stableparent(self, repo, headrev):

        """The parent of the changeset with reusable subrange

        For non-merge it is simple, there is a single parent. For Mercurial we

        have to find the right one. Since the stable sort use merge-point, we

        know that one of REV parents stable sort is a subset of REV stable

        sort. In other word:

            sort(::REV) = sort(::min(parents(REV))

                          + sort(only(max(parents(REV)), min(parents(REV)))

                          + [REV]

        We are looking for that `min(parents(REV))`. Since the subrange are

        based on the sort, we can reuse its subrange as well.

        """

        ps = filterparents(repo.changelog.parentrevs(headrev))

        if not ps:

            return nodemod.nullrev

        elif len(ps) == 1:

            return ps[0]

        else:

            tiebreaker = stablesort._mergepoint_tie_breaker(repo)

            return min(ps, key=tiebreaker)

    def _parentrange(self, repo, rangeid):

        stable_parent = self._stableparent(repo, rangeid[0])

        stable_parent_depth = self.depthrev(repo, stable_parent)

        stable_parent_range = (stable_parent, rangeid[1])

        return stable_parent_depth, stable_parent_range