# 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 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, 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 = repo.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 = repo.stablerange.rangelength

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

    return ranges

@eh.command(

    'debugstablerange',

    [

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

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

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

    ],

    _(''))

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

    # prewarm depth cache

    unfi = repo.unfiltered()

    node = unfi.changelog.node

    stablerange = unfi.stablerange

    depth = stablerange.depthrev

    length = stablerange.rangelength

    subranges = stablerange.subranges

    if not revs:

        raise error.Abort('no revisions specified')

    repo.stablerange.warmup(repo, max(revs))

    if opts['subranges']:

        ranges = subrangesclosure(repo, revs)

    else:

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

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

            )

    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 stablerange(object):

    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

        original = set(rangeheap)

        seen = 0

        # progress report is showing up in the profile for small and fast

        # repository so we build that complicated work around.

        progress_each = 100

        progress_last = time.time()

        heapify(rangeheap)

        while rangeheap:

            value = heappop(rangeheap)

            if value in original:

                if not seen % progress_each:

                    # if a lot of time passed, report more often

                    progress_new = time.time()

                    if (1 < progress_each) and (0.1 < progress_new - progress_last):

                        progress_each /= 10

                    ui.progress(_("filling stablerange cache"), seen, total=nbrevs)

                    progress_last = progress_new

                seen += 1

                original.remove(value) # might have been added from other source

            __, rangeid = value

            if self._getsub(rangeid) is None:

                for sub in self.subranges(repo, rangeid):

                    if self._getsub(sub) is None:

                        heappush(rangeheap, (-sub[0], sub))

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

        self._tiprev = upto

        self._tipnode = cl.node(upto)

        duration = timer() - starttime

        repo.ui.log('evoext-cache', 'updated stablerange cache in %.4f seconds\n',

                    duration)

    def depthrev(self, repo, rev):

        return repo.depthcache.get(rev)

    def rangelength(self, repo, rangeid):

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

        return self.depthrev(repo, headrev) - index

    def subranges(self, repo, rangeid):

        cached = self._getsub(rangeid)

        if cached is not None:

            return cached

        value = self._subranges(repo, rangeid)

        self._setsub(rangeid, value)

        return value

    def revsfromrange(self, repo, rangeid):

        headrev, index = rangeid

        rangelength = self.rangelength(repo, rangeid)

        if rangelength == 1:

            revs = [headrev]

        else:

            # get all revs under heads in stable order

            #

            # note: In the general case we can just walk down and then request

            # data about the merge. But I'm not sure this function will be even

            # call for the general case.

            allrevs = self._stablesortcache.get(headrev)

            if allrevs is None:

                allrevs = self._getrevsfrommerge(repo, headrev)

                if allrevs is None:

                    mc = self._filestablesortcache

                    allrevs = stablesort.stablesort(repo, [headrev],

                                                    mergecallback=mc)

                self._stablesortcache[headrev] = allrevs

            # takes from index

            revs = allrevs[index:]

        # sanity checks

        assert len(revs) == rangelength

        return revs

    def _parents(self, rev, func):

        parents = self._parentscache.get(rev)

        if parents is None:

            parents = func(rev)

            self._parentscache[rev] = parents

        return parents

    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

    def _filestablesortcache(self, sortedrevs, merge):

        if merge not in self._stablesortprepared:

            self._stablesortprepared[merge] = (sortedrevs, len(sortedrevs))

    def _getrevsfrommerge(self, repo, merge):

        prepared = self._stablesortprepared.get(merge)

        if prepared is None:

            return None

        mergedepth = self.depthrev(repo, merge)

        allrevs = prepared[0][:prepared[1]]

        nbextrarevs = prepared[1] - mergedepth

        if not nbextrarevs:

            return allrevs

        anc = repo.changelog.ancestors([merge], inclusive=True)

        top = []

        counter = nbextrarevs

        for rev in reversed(allrevs):

            if rev in anc:

                top.append(rev)

            else:

                counter -= 1

                if counter <= 0:

                    break

        bottomidx = prepared[1] - (nbextrarevs + len(top))

        revs = allrevs[:bottomidx]

        revs.extend(reversed(top))

        return revs

    def _inheritancepoint(self, repo, merge):

        """Find the inheritance point of a Merge

        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.

        That point is latest point in the stable sorted list where the depth of the

        revisions match its index (that means all revision earlier in the stable sorted

        list are its ancestors, no dangling unrelated branches exists).

        """

        value = self._inheritancecache.get(merge)

        if value is None:

            revs = self.revsfromrange(repo, (merge, 0))

            i = reversed(revs)

            i.next() # pop the merge

            expected = len(revs) - 1

            # Since we do warmup properly, we can expect the cache to be hot

            # for everythin under the merge we investigate

            cache = repo.depthcache

            # note: we cannot do a binary search because element under the

            # inherited point might have mismatching depth because of inner

            # branching.

            for rev in i:

                if cache.get(rev) == expected:

                    break

                expected -= 1

            value = (expected - 1, rev)

            self._inheritancecache[merge] = value

        return value

    def _subranges(self, repo, rangeid):

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

            return []

        slicepoint = self._slicepoint(repo, rangeid)

        # make sure we have cache for all relevant parent first to prevent

        # recursion (python is bad with recursion

        stack = []

        current = rangeid

        while current is not None:

            current = self._cold_reusable(repo, current, slicepoint)

            if current is not None:

                stack.append(current)

        while stack:

            # these call will directly compute the subranges

            self.subranges(repo, stack.pop())

        return self._slicesrangeat(repo, rangeid, slicepoint)