# dagop.py - graph ancestry and topology algorithm for revset

#

# Copyright 2010 Olivia Mackall <olivia@selenic.com>

#

# 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

from .thirdparty import attr

from .node import nullrev

from . import (

    error,

    mdiff,

    patch,

    pycompat,

    scmutil,

    smartset,

)

baseset = smartset.baseset

generatorset = smartset.generatorset

# possible maximum depth between null and wdir()

maxlogdepth = 0x80000000

def _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse):

    """Walk DAG using 'pfunc' from the given 'revs' nodes

    'pfunc(rev)' should return the parent/child revisions of the given 'rev'

    if 'reverse' is True/False respectively.

    Scan ends at the stopdepth (exlusive) if specified. Revisions found

    earlier than the startdepth are omitted.

    """

    if startdepth is None:

        startdepth = 0

    if stopdepth is None:

        stopdepth = maxlogdepth

    if stopdepth == 0:

        return

    if stopdepth < 0:

        raise error.ProgrammingError(b'negative stopdepth')

    if reverse:

        heapsign = -1  # max heap

    else:

        heapsign = +1  # min heap

    # load input revs lazily to heap so earlier revisions can be yielded

    # without fully computing the input revs

    revs.sort(reverse)

    irevs = iter(revs)

    pendingheap = []  # [(heapsign * rev, depth), ...] (i.e. lower depth first)

    inputrev = next(irevs, None)

    if inputrev is not None:

        heapq.heappush(pendingheap, (heapsign * inputrev, 0))

    lastrev = None

    while pendingheap:

        currev, curdepth = heapq.heappop(pendingheap)

        currev = heapsign * currev

        if currev == inputrev:

            inputrev = next(irevs, None)

            if inputrev is not None:

                heapq.heappush(pendingheap, (heapsign * inputrev, 0))

        # rescan parents until curdepth >= startdepth because queued entries

        # of the same revision are iterated from the lowest depth

        foundnew = currev != lastrev

        if foundnew and curdepth >= startdepth:

            lastrev = currev

            yield currev

        pdepth = curdepth + 1

        if foundnew and pdepth < stopdepth:

            for prev in pfunc(currev):

                if prev != nullrev:

                    heapq.heappush(pendingheap, (heapsign * prev, pdepth))

def filectxancestors(fctxs, followfirst=False):

    """Like filectx.ancestors(), but can walk from multiple files/revisions,

    and includes the given fctxs themselves

    Yields (rev, {fctx, ...}) pairs in descending order.

    """

    visit = {}

    visitheap = []

    def addvisit(fctx):

        rev = scmutil.intrev(fctx)

        if rev not in visit:

            visit[rev] = set()

            heapq.heappush(visitheap, -rev)  # max heap

        visit[rev].add(fctx)

    if followfirst:

        cut = 1

    else:

        cut = None

    for c in fctxs:

        addvisit(c)

    while visit:

        currev = -(heapq.heappop(visitheap))

        curfctxs = visit.pop(currev)

        yield currev, curfctxs

        for c in curfctxs:

            for parent in c.parents()[:cut]:

                addvisit(parent)

    assert not visitheap

def filerevancestors(fctxs, followfirst=False):

    """Like filectx.ancestors(), but can walk from multiple files/revisions,

    and includes the given fctxs themselves

    Returns a smartset.

    """

    gen = (rev for rev, _cs in filectxancestors(fctxs, followfirst))

    return generatorset(gen, iterasc=False)

def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, cutfunc):

    if followfirst:

        cut = 1

    else:

        cut = None

    cl = repo.changelog

    def plainpfunc(rev):

        try:

            return cl.parentrevs(rev)[:cut]

        except error.WdirUnsupported:

            return (pctx.rev() for pctx in repo[rev].parents()[:cut])

    if cutfunc is None:

        pfunc = plainpfunc

    else:

        pfunc = lambda rev: [r for r in plainpfunc(rev) if not cutfunc(r)]

        revs = revs.filter(lambda rev: not cutfunc(rev))

    return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=True)

def revancestors(

    repo, revs, followfirst=False, startdepth=None, stopdepth=None, cutfunc=None

):

    r"""Like revlog.ancestors(), but supports additional options, includes

    the given revs themselves, and returns a smartset

    Scan ends at the stopdepth (exlusive) if specified. Revisions found

    earlier than the startdepth are omitted.

    If cutfunc is provided, it will be used to cut the traversal of the DAG.

    When cutfunc(X) returns True, the DAG traversal stops - revision X and

    X's ancestors in the traversal path will be skipped. This could be an

    optimization sometimes.

    Note: if Y is an ancestor of X, cutfunc(X) returning True does not

    necessarily mean Y will also be cut. Usually cutfunc(Y) also wants to

    return True in this case. For example,

        D     # revancestors(repo, D, cutfunc=lambda rev: rev == B)

        |\    # will include "A", because the path D -> C -> A was not cut.

        B C   # If "B" gets cut, "A" might want to be cut too.

        |/

        A

    """

    gen = _genrevancestors(

        repo, revs, followfirst, startdepth, stopdepth, cutfunc

    )

    return generatorset(gen, iterasc=False)

def _genrevdescendants(repo, revs, followfirst):

    if followfirst:

        cut = 1

    else:

        cut = None

    cl = repo.changelog

    first = revs.min()

    if first == nullrev:

        # Are there nodes with a null first parent and a non-null

        # second one? Maybe. Do we care? Probably not.

        yield first

        for i in cl:

            yield i

    else:

        seen = set(revs)

        for i in cl.revs(first):

            if i in seen:

                yield i

                continue

            for x in cl.parentrevs(i)[:cut]:

                if x != nullrev and x in seen:

                    seen.add(i)

                    yield i

                    break

def _builddescendantsmap(repo, startrev, followfirst):

    """Build map of 'rev -> child revs', offset from startrev"""

    cl = repo.changelog

    descmap = [[] for _rev in range(startrev, len(cl))]

    for currev in cl.revs(startrev + 1):

        p1rev, p2rev = cl.parentrevs(currev)

        if p1rev >= startrev:

            descmap[p1rev - startrev].append(currev)

        if not followfirst and p2rev != nullrev and p2rev >= startrev:

            descmap[p2rev - startrev].append(currev)

    return descmap

def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth):

    startrev = revs.min()

    descmap = _builddescendantsmap(repo, startrev, followfirst)

    def pfunc(rev):

        return descmap[rev - startrev]

    return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=False)

def revdescendants(repo, revs, followfirst, startdepth=None, stopdepth=None):

    """Like revlog.descendants() but supports additional options, includes

    the given revs themselves, and returns a smartset

    Scan ends at the stopdepth (exlusive) if specified. Revisions found

    earlier than the startdepth are omitted.

    """

    if startdepth is None and (stopdepth is None or stopdepth >= maxlogdepth):

        gen = _genrevdescendants(repo, revs, followfirst)

    else:

        gen = _genrevdescendantsofdepth(

            repo, revs, followfirst, startdepth, stopdepth

        )

    return generatorset(gen, iterasc=True)

def descendantrevs(revs, revsfn, parentrevsfn):

    """Generate revision number descendants in revision order.

    Yields revision numbers starting with a child of some rev in

    ``revs``. Results are ordered by revision number and are

    therefore topological. Each revision is not considered a descendant

    of itself.

    ``revsfn`` is a callable that with no argument iterates over all

    revision numbers and with a ``start`` argument iterates over revision

    numbers beginning with that value.

    ``parentrevsfn`` is a callable that receives a revision number and

    returns an iterable of parent revision numbers, whose values may include

    nullrev.

    """

    first = min(revs)

    if first == nullrev:

        for rev in revsfn():

            yield rev

        return

    seen = set(revs)

    for rev in revsfn(start=first + 1):

        for prev in parentrevsfn(rev):

            if prev != nullrev and prev in seen:

                seen.add(rev)

                yield rev

                break

class subsetparentswalker:

    r"""Scan adjacent ancestors in the graph given by the subset

    This computes parent-child relations in the sub graph filtered by

    a revset. Primary use case is to draw a revisions graph.

    In the following example, we consider that the node 'f' has edges to all

    ancestor nodes, but redundant paths are eliminated. The edge 'f'->'b'

    is eliminated because there is a path 'f'->'c'->'b' for example.

          - d - e -

         /         \

        a - b - c - f

    If the node 'c' is filtered out, the edge 'f'->'b' is activated.

          - d - e -

         /         \

        a - b -(c)- f

    Likewise, if 'd' and 'e' are filtered out, this edge is fully eliminated

    since there is a path 'f'->'c'->'b'->'a' for 'f'->'a'.

           (d) (e)

        a - b - c - f

    Implementation-wise, 'f' is passed down to 'a' as unresolved through the

    'f'->'e'->'d'->'a' path, whereas we do also remember that 'f' has already

    been resolved while walking down the 'f'->'c'->'b'->'a' path. When

    processing the node 'a', the unresolved 'f'->'a' path is eliminated as

    the 'f' end is marked as resolved.

    Ancestors are searched from the tipmost revision in the subset so the

    results can be cached. You should specify startrev to narrow the search

    space to ':startrev'.

    """

    def __init__(self, repo, subset, startrev=None):

        if startrev is not None:

            subset = repo.revs(b'%d:null', startrev) & subset

        # equivalent to 'subset = subset.sorted(reverse=True)', but there's

        # no such function.

        fastdesc = subset.fastdesc

        if fastdesc:

            desciter = fastdesc()

        else:

            if not subset.isdescending() and not subset.istopo():

                subset = smartset.baseset(subset)

                subset.sort(reverse=True)

            desciter = iter(subset)

        self._repo = repo

        self._changelog = repo.changelog

        self._subset = subset

        # scanning state (see _scanparents):

        self._tovisit = []

        self._pendingcnt = {}

        self._pointers = {}

        self._parents = {}

        self._inputhead = nullrev  # reassigned by self._advanceinput()

        self._inputtail = desciter

        self._bottomrev = nullrev

        self._advanceinput()

    def parentsset(self, rev):

        """Look up parents of the given revision in the subset, and returns

        as a smartset"""

        return smartset.baseset(self.parents(rev))

    def parents(self, rev):

        """Look up parents of the given revision in the subset

        The returned revisions are sorted by parent index (p1/p2).

        """

        self._scanparents(rev)

        return [r for _c, r in sorted(self._parents.get(rev, []))]

    def _parentrevs(self, rev):

        try:

            revs = self._changelog.parentrevs(rev)

            if revs[-1] == nullrev:

                return revs[:-1]

            return revs

        except error.WdirUnsupported:

            return tuple(pctx.rev() for pctx in self._repo[None].parents())

    def _advanceinput(self):

        """Advance the input iterator and set the next revision to _inputhead"""

        if self._inputhead < nullrev:

            return

        try:

            self._inputhead = next(self._inputtail)

        except StopIteration:

            self._bottomrev = self._inputhead

            self._inputhead = nullrev - 1

    def _scanparents(self, stoprev):

        """Scan ancestors until the parents of the specified stoprev are

        resolved"""

        # 'tovisit' is the queue of the input revisions and their ancestors.

        # It will be populated incrementally to minimize the initial cost

        # of computing the given subset.

        #

        # For to-visit revisions, we keep track of

        # - the number of the unresolved paths: pendingcnt[rev],

        # - dict of the unresolved descendants and chains: pointers[rev][0],

        # - set of the already resolved descendants: pointers[rev][1].

        #

        # When a revision is visited, 'pointers[rev]' should be popped and

        # propagated to its parents accordingly.

        #

        # Once all pending paths have been resolved, 'pendingcnt[rev]' becomes

        # 0 and 'parents[rev]' contains the unsorted list of parent revisions

        # and p1/p2 chains (excluding linear paths.) The p1/p2 chains will be

        # used as a sort key preferring p1. 'len(chain)' should be the number

        # of merges between two revisions.

        subset = self._subset

        tovisit = self._tovisit  # heap queue of [-rev]

        pendingcnt = self._pendingcnt  # {rev: count} for visited revisions

        pointers = self._pointers  # {rev: [{unresolved_rev: chain}, resolved]}

        parents = self._parents  # {rev: [(chain, rev)]}