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

import math

import os

import sqlite3

import time

import weakref

from mercurial import (

    error,

    localrepo,

    node as nodemod,

    pycompat,

    scmutil,

    util,

)

from mercurial.i18n import _

from . import (

    stablesort,

    exthelper,

)

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(repo, 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 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

class stablerange_mergepoint(stablerangecached, stablerangedummy_mergepoint):

    """Stablerange implementation using 'mergepoint' based sorting

    """

    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)

                                                           limit=limit)

class stablerange(stablerangecached):

    def __init__(self, lrusize=2000):

        # The point up to which we have data in cache

        self._tiprev = None

        self._tipnode = None

        # cache the standard stable subranges or a range

        self._subrangescache = {}

        # To slices merge, we need to walk their descendant in reverse stable

        # sort order. For now we perform a full stable sort their descendant

        # and then use the relevant top most part. This order is going to be

        # the same for all ranges headed at the same merge. So we cache these

        # value to reuse them accross the same invocation.

        self._stablesortcache = util.lrucachedict(lrusize)

        # something useful to compute the above

        # mergerev -> stablesort, length

        self._stablesortprepared = util.lrucachedict(lrusize)

        # caching parent call # as we do so many of them

        self._parentscache = {}

        # The first part of the stable sorted list of revision of a merge will

        # shared with the one of others. This means we can reuse subranges

        # computed from that point to compute some of the subranges from the

        # merge.

        self._inheritancecache = {}

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

        """warm the cache up"""

        repo = repo.unfiltered()

        repo.depthcache.update(repo)

        cl = repo.changelog

        # subrange should be warmed from head to range to be able to benefit

        # from revsfromrange cache. otherwise each merge will trigger its own

        # stablesort.

        #

        # we use the revnumber as an approximation for depth

        ui = repo.ui

        starttime = timer()

        if upto is None:

            upto = len(cl) - 1

        if self._tiprev is None:

            revs = cl.revs(stop=upto)

            nbrevs = upto + 1

        else:

            assert cl.node(self._tiprev) == self._tipnode

            if upto <= self._tiprev:

                return

            revs = cl.revs(start=self._tiprev + 1, stop=upto)

            nbrevs = upto - self._tiprev

        rangeheap = []

        for idx, r in enumerate(revs):

            if not idx % 1000:

                ui.progress(_("filling depth cache"), idx, total=nbrevs)

            # warm up depth

            self.depthrev(repo, r)

            rangeheap.append((-r, (r, 0)))

        ui.progress(_("filling depth cache"), None, total=nbrevs)

        heappop = heapq.heappop

        heappush = heapq.heappush

        heapify = heapq.heapify