# obsutil.py - utility functions for obsolescence

#

# Copyright 2017 Boris Feld <boris.feld@octobus.net>

#

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

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

from __future__ import absolute_import

def closestpredecessors(repo, nodeid):

    """yield the list of next predecessors pointing on visible changectx nodes

    This function respect the repoview filtering, filtered revision will be

    considered missing.

    """

    precursors = repo.obsstore.precursors

    stack = [nodeid]

    seen = set(stack)

    while stack:

        current = stack.pop()

        currentpreccs = precursors.get(current, ())

        for prec in currentpreccs:

            precnodeid = prec[0]

            # Basic cycle protection

            if precnodeid in seen:

                continue

            seen.add(precnodeid)

            if precnodeid in repo:

                yield precnodeid

            else:

                stack.append(precnodeid)

def successorssets(repo, initialnode, cache=None):

    """Return set of all latest successors of initial nodes

    The successors set of a changeset A are the group of revisions that succeed

    A. It succeeds A as a consistent whole, each revision being only a partial

    replacement. The successors set contains non-obsolete changesets only.

    This function returns the full list of successor sets which is why it

    returns a list of tuples and not just a single tuple. Each tuple is a valid

    successors set. Note that (A,) may be a valid successors set for changeset A

    (see below).

    In most cases, a changeset A will have a single element (e.g. the changeset

    A is replaced by A') in its successors set. Though, it is also common for a

    changeset A to have no elements in its successor set (e.g. the changeset

    has been pruned). Therefore, the returned list of successors sets will be

    [(A',)] or [], respectively.

    When a changeset A is split into A' and B', however, it will result in a

    successors set containing more than a single element, i.e. [(A',B')].

    Divergent changesets will result in multiple successors sets, i.e. [(A',),

    (A'')].

    If a changeset A is not obsolete, then it will conceptually have no

    successors set. To distinguish this from a pruned changeset, the successor

    set will contain itself only, i.e. [(A,)].

    Finally, successors unknown locally are considered to be pruned (obsoleted

    without any successors).

    The optional `cache` parameter is a dictionary that may contain precomputed

    successors sets. It is meant to reuse the computation of a previous call to

    `successorssets` when multiple calls are made at the same time. The cache

    dictionary is updated in place. The caller is responsible for its life

    span. Code that makes multiple calls to `successorssets` *must* use this

    cache mechanism or suffer terrible performance.

    """

    succmarkers = repo.obsstore.successors

    # Stack of nodes we search successors sets for

    toproceed = [initialnode]

    # set version of above list for fast loop detection

    # element added to "toproceed" must be added here

    stackedset = set(toproceed)

    if cache is None:

        cache = {}

    # This while loop is the flattened version of a recursive search for

    # successors sets

    #

    # def successorssets(x):

    #    successors = directsuccessors(x)

    #    ss = [[]]

    #    for succ in directsuccessors(x):

    #        # product as in itertools cartesian product

    #        ss = product(ss, successorssets(succ))

    #    return ss

    #

    # But we can not use plain recursive calls here:

    # - that would blow the python call stack

    # - obsolescence markers may have cycles, we need to handle them.

    #

    # The `toproceed` list act as our call stack. Every node we search

    # successors set for are stacked there.

    #

    # The `stackedset` is set version of this stack used to check if a node is

    # already stacked. This check is used to detect cycles and prevent infinite

    # loop.

    #

    # successors set of all nodes are stored in the `cache` dictionary.

    #

    # After this while loop ends we use the cache to return the successors sets

    # for the node requested by the caller.

    while toproceed:

        # Every iteration tries to compute the successors sets of the topmost

        # node of the stack: CURRENT.

        #

        # There are four possible outcomes:

        #

        # 1) We already know the successors sets of CURRENT:

        #    -> mission accomplished, pop it from the stack.

        # 2) Node is not obsolete:

        #    -> the node is its own successors sets. Add it to the cache.

        # 3) We do not know successors set of direct successors of CURRENT:

        #    -> We add those successors to the stack.

        # 4) We know successors sets of all direct successors of CURRENT:

        #    -> We can compute CURRENT successors set and add it to the

        #       cache.

        #

        current = toproceed[-1]

        if current in cache:

            # case (1): We already know the successors sets

            stackedset.remove(toproceed.pop())

        elif current not in succmarkers:

            # case (2): The node is not obsolete.

            if current in repo:

                # We have a valid last successors.

                cache[current] = [(current,)]

            else:

                # Final obsolete version is unknown locally.

                # Do not count that as a valid successors

                cache[current] = []

        else:

            # cases (3) and (4)

            #

            # We proceed in two phases. Phase 1 aims to distinguish case (3)

            # from case (4):

            #

            #     For each direct successors of CURRENT, we check whether its

            #     successors sets are known. If they are not, we stack the

            #     unknown node and proceed to the next iteration of the while

            #     loop. (case 3)

            #

            #     During this step, we may detect obsolescence cycles: a node

            #     with unknown successors sets but already in the call stack.

            #     In such a situation, we arbitrary set the successors sets of

            #     the node to nothing (node pruned) to break the cycle.

            #

            #     If no break was encountered we proceed to phase 2.

            #

            # Phase 2 computes successors sets of CURRENT (case 4); see details

            # in phase 2 itself.

            #

            # Note the two levels of iteration in each phase.

            # - The first one handles obsolescence markers using CURRENT as

            #   precursor (successors markers of CURRENT).

            #

            #   Having multiple entry here means divergence.

            #

            # - The second one handles successors defined in each marker.

            #

            #   Having none means pruned node, multiple successors means split,

            #   single successors are standard replacement.

            #

            for mark in sorted(succmarkers[current]):

                for suc in mark[1]:

                    if suc not in cache:

                        if suc in stackedset:

                            # cycle breaking

                            cache[suc] = []

                        else:

                            # case (3) If we have not computed successors sets

                            # of one of those successors we add it to the

                            # `toproceed` stack and stop all work for this

                            # iteration.

                            toproceed.append(suc)

                            stackedset.add(suc)

                            break

                else:

                    continue

                break

            else:

                # case (4): we know all successors sets of all direct

                # successors

                #

                # Successors set contributed by each marker depends on the

                # successors sets of all its "successors" node.

                #

                # Each different marker is a divergence in the obsolescence

                # history. It contributes successors sets distinct from other

                # markers.

                #

                # Within a marker, a successor may have divergent successors

                # sets. In such a case, the marker will contribute multiple

                # divergent successors sets. If multiple successors have

                # divergent successors sets, a Cartesian product is used.

                #

                # At the end we post-process successors sets to remove

                # duplicated entry and successors set that are strict subset of

                # another one.

                succssets = []

                for mark in sorted(succmarkers[current]):

                    # successors sets contributed by this marker

                    markss = [[]]

                    for suc in mark[1]:

                        # cardinal product with previous successors

                        productresult = []

                        for prefix in markss:

                            for suffix in cache[suc]:

                                newss = list(prefix)

                                for part in suffix:

                                    # do not duplicated entry in successors set

                                    # first entry wins.

                                    if part not in newss:

                                        newss.append(part)

                                productresult.append(newss)

                        markss = productresult

                    succssets.extend(markss)

                # remove duplicated and subset

                seen = []

                final = []

                candidate = sorted(((set(s), s) for s in succssets if s),

                                   key=lambda x: len(x[1]), reverse=True)

                for setversion, listversion in candidate:

                    for seenset in seen:

                        if setversion.issubset(seenset):

                            break

                    else:

                        final.append(listversion)

                        seen.append(setversion)

                final.reverse() # put small successors set first

                cache[current] = final

    return cache[initialnode]