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

class stablerange(object):

    def __init__(self):

        self._depthcache = {}

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

        """warm the cache up to 'heads'"""

        repo = repo.unfiltered()

        for r in repo.revs("::%ld", heads):

            self.depthrev(repo, r)

    def depthrev(self, repo, rev):

        repo = repo.unfiltered()

        cl = repo.changelog

        cache = self._depthcache

        nullrev = nodemod.nullrev

        stack = [rev]

        while stack:

            revdepth = None

            current = stack[-1]

            revdepth = cache.get(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 = cache.get(p1)

                if parentdepth is None:

                    stack.append(p1)

                else:

                    revdepth = parentdepth + 1

            else:

                # merge case

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

            if revdepth is not None:

                cache[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._subrangescache.get(rangeid)

        if cached is not None:

            return cached

        value = self._subranges(repo, rangeid)

        self._subrangescache[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:

            parents = func(rev)

            self._parentscache[rev] = parents

        return parents

    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 = self._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[rev] == expected:

                    break

                expected -= 1

            value = (expected - 1, rev)

            self._inheritancecache[merge] = value

        return value

    @staticmethod

    def _depthmerge(cl, rev, p1, p2, stack, cache):

        # sub method to simplify the main 'depthrev' one

        revdepth = None

        depth_p1 = cache.get(p1)

        depth_p2 = cache.get(p2)

        missingparent = False

        if depth_p1 is None:

            stack.append(p1)

            missingparent = True

        if depth_p2 is None:

            stack.append(p2)

            missingparent = True

        if missingparent:

            return None

        # computin depth of a merge

        # XXX the common ancestors heads could be cached

        ancnodes = cl.commonancestorsheads(cl.node(p1), cl.node(p2))

        ancrevs = [cl.rev(a) for a in ancnodes]

        anyunkown = False

        ancdepth = []

        for r in ancrevs:

            d = cache.get(r)

            if d is None:

                anyunkown = True

                stack.append(r)

            ancdepth.append((r, d))

        if anyunkown:

            return None

        if not ancrevs:

            # unrelated branch, (no common root)

            revdepth = depth_p1 + depth_p2 + 1

        elif len(ancrevs) == 1:

            # one unique branch point:

            # we can compute depth without any walk

            depth_anc = ancdepth[0][1]

            revdepth = depth_p1 + (depth_p2 - depth_anc) + 1

        else:

            # multiple ancestors, we pick one that is

            # * the deepest (less changeset outside of it),

            # * lowest revs because more chance to have descendant of other "above"

            anc, revdepth = max(ancdepth, key=lambda x: (x[1], -x[0]))

            revdepth += len(cl.findmissingrevs(common=[anc], heads=[rev]))

        return revdepth

    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)