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

#

# Copyright 2010 Matt Mackall <mpm@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.

from __future__ import absolute_import

import heapq

from . import (

    error,

    mdiff,

    node,

    patch,

    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('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 != node.nullrev:

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

    visit = {}

    def addvisit(fctx):

        rev = fctx.rev()

        if rev not in visit:

            visit[rev] = set()

        visit[rev].add(fctx)

    if followfirst:

        cut = 1

    else:

        cut = None

    while visit:

        rev = max(visit)

        c = visit[rev].pop()

        if not visit[rev]:

            del visit[rev]

        yield c

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

            addvisit(parent)

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

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

    nullrev = node.nullrev

    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

    nullrev = node.nullrev

    descmap = [[] for _rev in xrange(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:

        gen = _genrevdescendants(repo, revs, followfirst)

    else:

        gen = _genrevdescendantsofdepth(repo, revs, followfirst,

                                        startdepth, stopdepth)

    return generatorset(gen, iterasc=True)

def _reachablerootspure(repo, minroot, roots, heads, includepath):

    """return (heads(::<roots> and ::<heads>))

    If includepath is True, return (<roots>::<heads>)."""

    if not roots:

        return []

    parentrevs = repo.changelog.parentrevs

    roots = set(roots)

    visit = list(heads)

    reachable = set()

    seen = {}

    # prefetch all the things! (because python is slow)

    reached = reachable.add

    dovisit = visit.append

    nextvisit = visit.pop

    # open-code the post-order traversal due to the tiny size of

    # sys.getrecursionlimit()

    while visit:

        rev = nextvisit()

        if rev in roots:

            reached(rev)

            if not includepath:

                continue

        parents = parentrevs(rev)

        seen[rev] = parents

        for parent in parents:

            if parent >= minroot and parent not in seen:

                dovisit(parent)

    if not reachable:

        return baseset()

    if not includepath:

        return reachable

    for rev in sorted(seen):

        for parent in seen[rev]:

            if parent in reachable:

                reached(rev)

    return reachable

def reachableroots(repo, roots, heads, includepath=False):

    """return (heads(::<roots> and ::<heads>))

    If includepath is True, return (<roots>::<heads>)."""

    if not roots:

        return baseset()

    minroot = roots.min()

    roots = list(roots)

    heads = list(heads)

    try:

        revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)

    except AttributeError:

        revs = _reachablerootspure(repo, minroot, roots, heads, includepath)

    revs = baseset(revs)

    revs.sort()

    return revs

def _changesrange(fctx1, fctx2, linerange2, diffopts):

    """Return `(diffinrange, linerange1)` where `diffinrange` is True

    if diff from fctx2 to fctx1 has changes in linerange2 and

    `linerange1` is the new line range for fctx1.

    """

    blocks = mdiff.allblocks(fctx1.data(), fctx2.data(), diffopts)

    filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2)

    diffinrange = any(stype == '!' for _, stype in filteredblocks)

    return diffinrange, linerange1

def blockancestors(fctx, fromline, toline, followfirst=False):

    """Yield ancestors of `fctx` with respect to the block of lines within

    `fromline`-`toline` range.

    """

    diffopts = patch.diffopts(fctx._repo.ui)

    fctx = fctx.introfilectx()

    visit = {(fctx.linkrev(), fctx.filenode()): (fctx, (fromline, toline))}

    while visit:

        c, linerange2 = visit.pop(max(visit))

        pl = c.parents()

        if followfirst:

            pl = pl[:1]

        if not pl:

            # The block originates from the initial revision.

            yield c, linerange2

            continue

        inrange = False

        for p in pl:

            inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts)

            inrange = inrange or inrangep

            if linerange1[0] == linerange1[1]:

                # Parent's linerange is empty, meaning that the block got

                # introduced in this revision; no need to go futher in this

                # branch.

                continue

            # Set _descendantrev with 'c' (a known descendant) so that, when

            # _adjustlinkrev is called for 'p', it receives this descendant

            # (as srcrev) instead possibly topmost introrev.

            p._descendantrev = c.rev()

            visit[p.linkrev(), p.filenode()] = p, linerange1

        if inrange:

            yield c, linerange2

def blockdescendants(fctx, fromline, toline):

    """Yield descendants of `fctx` with respect to the block of lines within

    `fromline`-`toline` range.

    """

    # First possibly yield 'fctx' if it has changes in range with respect to

    # its parents.

    try:

        c, linerange1 = next(blockancestors(fctx, fromline, toline))

    except StopIteration:

        pass

    else:

        if c == fctx:

            yield c, linerange1

    diffopts = patch.diffopts(fctx._repo.ui)

    fl = fctx.filelog()

    seen = {fctx.filerev(): (fctx, (fromline, toline))}

    for i in fl.descendants([fctx.filerev()]):

        c = fctx.filectx(i)

        inrange = False

        for x in fl.parentrevs(i):

            try:

                p, linerange2 = seen[x]

            except KeyError:

                # nullrev or other branch

                continue

            inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts)

            inrange = inrange or inrangep

            # If revision 'i' has been seen (it's a merge) and the line range

            # previously computed differs from the one we just got, we take the

            # surrounding interval. This is conservative but avoids loosing

            # information.

            if i in seen and seen[i][1] != linerange1:

                lbs, ubs = zip(linerange1, seen[i][1])

                linerange1 = min(lbs), max(ubs)

            seen[i] = c, linerange1

        if inrange:

            yield c, linerange1

def toposort(revs, parentsfunc, firstbranch=()):

    """Yield revisions from heads to roots one (topo) branch at a time.

    This function aims to be used by a graph generator that wishes to minimize

    the number of parallel branches and their interleaving.

    Example iteration order (numbers show the "true" order in a changelog):

      o  4

      |

      o  1

      |

      | o  3

      | |

      | o  2

      |/

      o  0

    Note that the ancestors of merges are understood by the current

    algorithm to be on the same branch. This means no reordering will

    occur behind a merge.

    """

    ### Quick summary of the algorithm

    #

    # This function is based around a "retention" principle. We keep revisions

    # in memory until we are ready to emit a whole branch that immediately

    # "merges" into an existing one. This reduces the number of parallel

    # branches with interleaved revisions.

    #

    # During iteration revs are split into two groups:

    # A) revision already emitted

    # B) revision in "retention". They are stored as different subgroups.

    #

    # for each REV, we do the following logic:

    #

    #   1) if REV is a parent of (A), we will emit it. If there is a

    #   retention group ((B) above) that is blocked on REV being

    #   available, we emit all the revisions out of that retention

    #   group first.

    #