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

import heapq

import math

from mercurial import (

    commands,

    cmdutil,

    localrepo,

    node as nodemod,

    scmutil,

)

from mercurial.i18n import _

from . import (

    exthelper,

)

eh = exthelper.exthelper()

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

### Stable topological sorting ###

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

@eh.command(

    'debugstablesort',

    [

        ('', 'rev', [], 'heads to start from'),

    ] + commands.formatteropts,

    _(''))

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

    """display the ::REVS set topologically sorted in a stable way

    """

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

    displayer = cmdutil.show_changeset(ui, repo, opts, buffered=True)

    for r in stablesort(repo, revs):

        ctx = repo[r]

        displayer.show(ctx)

        displayer.flush(ctx)

    displayer.close()

def stablesort(repo, revs, mergecallback=None):

    """return '::revs' topologically sorted in "stable" order

    This is a depth first traversal starting from 'nullrev', using node as a

    tie breaker.

    """

    # Various notes:

    #

    # * Bitbucket is used dates as tie breaker, that might be a good idea.

    #

    # * It seemds we can traverse in the same order from (one) head to bottom,

    #   if we the following record data for each merge:

    #

    #  - highest (stablesort-wise) common ancestors,

    #  - order of parents (tablesort-wise)

    cl = repo.changelog

    parents = cl.parentrevs

    nullrev = nodemod.nullrev

    n = cl.node

    # step 1: We need a parents -> children mapping for 2 reasons.

    #

    # * we build the order from nullrev to tip

    #

    # * we need to detect branching

    children = collections.defaultdict(list)

    for r in cl.ancestors(revs, inclusive=True):

        p1, p2 = parents(r)

        children[p1].append(r)

        if p2 != nullrev:

            children[p2].append(r)

    # step two: walk back up

    # * pick lowest node in case of branching

    # * stack disregarded part of the branching

    # * process merge when both parents are yielded

    # track what changeset has been

    seen = [0] * (max(revs) + 2)

    seen[-1] = True # nullrev is known

    # starts from repository roots

    # reuse the list form the mapping as we won't need it again anyway

    stack = children[nullrev]

    if not stack:

        return []

    if 1 < len(stack):

        stack.sort(key=n, reverse=True)

    # list of rev, maybe we should yield, but since we built a children mapping we are 'O(N)' already

    result = []

    current = stack.pop()

    while current is not None or stack:

        if current is None:

            # previous iteration reached a merge or an unready merge,

            current = stack.pop()

            if seen[current]:

                current = None

                continue

        p1, p2 = parents(current)

        if not (seen[p1] and seen[p2]):

            # we can't iterate on this merge yet because other child is not

            # yielded yet (and we are topo sorting) we can discard it for now

            # because it will be reached from the other child.

            current = None

            continue

        assert not seen[current]

        seen[current] = True

        result.append(current) # could be yield, cf earlier comment

        if mergecallback is not None and p2 != nullrev:

            mergecallback(result, current)

        cs = children[current]

        if not cs:

            current = None

        elif 1 == len(cs):

            current = cs[0]

        else:

            cs.sort(key=n, reverse=True)

            current = cs.pop() # proceed on smallest

            stack.extend(cs)   # stack the rest for later

    assert len(result) == len(set(result))

    return result

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

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

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

        # The point up to which we have data in cache

        self._tiprev = None

        self._tipnode = None

        # cache the 'depth' of a changeset, the size of '::rev'

        self._depthcache = {}

        # 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 = {}

        # something useful to compute the above

        # mergerev -> stablesort, length

        self._stablesortprepared = {}

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

        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

        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

        heapify(rangeheap)

        while rangeheap:

            value = heappop(rangeheap)

            if value in original:

                if not seen % 1000:

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

                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)

    def depthrev(self, repo, rev):

        repo = repo.unfiltered()

        cl = repo.changelog

        depth = self._getdepth

        nullrev = nodemod.nullrev

        stack = [rev]

        while stack:

            revdepth = None

            current = stack[-1]

            revdepth = depth(current)

            if revdepth is not None:

                stack.pop()

                continue

            p1, p2 = self._parents(current, cl.parentrevs)

            if p1 == nullrev:

                # root case

                revdepth = 1

            elif p2 == nullrev:

                # linear commit case

                parentdepth = depth(p1)

                if parentdepth is None:

                    stack.append(p1)

                else:

                    revdepth = parentdepth + 1

            else:

                # merge case

                revdepth = self._depthmerge(cl, current, p1, p2, stack)

            if revdepth is not None:

                self._setdepth(current, revdepth)

                stack.pop()

        # actual_depth = len(list(cl.ancestors([rev], inclusive=True)))

        # assert revdepth == actual_depth, (rev, revdepth, actual_depth)

        return revdepth

    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:

                    allrevs = stablesort(repo, [headrev],

                                         mergecallback=self._filestablesortcache)

                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: