# coding: utf8

# copies.py - copy detection for Mercurial

#

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

import os

from .i18n import _

from .node import (

    nullid,

    nullrev,

)

from . import (

    match as matchmod,

    pathutil,

    policy,

    pycompat,

    util,

)

from .utils import stringutil

from .revlogutils import (

    flagutil,

    sidedata as sidedatamod,

)

rustmod = policy.importrust("copy_tracing")

def _filter(src, dst, t):

    """filters out invalid copies after chaining"""

    # When _chain()'ing copies in 'a' (from 'src' via some other commit 'mid')

    # with copies in 'b' (from 'mid' to 'dst'), we can get the different cases

    # in the following table (not including trivial cases). For example, case 6

    # is where a file existed in 'src' and remained under that name in 'mid' and

    # then was renamed between 'mid' and 'dst'.

    #

    # case src mid dst result

    #   1   x   y   -    -

    #   2   x   y   y   x->y

    #   3   x   y   x    -

    #   4   x   y   z   x->z

    #   5   -   x   y    -

    #   6   x   x   y   x->y

    #

    # _chain() takes care of chaining the copies in 'a' and 'b', but it

    # cannot tell the difference between cases 1 and 2, between 3 and 4, or

    # between 5 and 6, so it includes all cases in its result.

    # Cases 1, 3, and 5 are then removed by _filter().

    for k, v in list(t.items()):

        if k == v:  # case 3

            del t[k]

        elif v not in src:  # case 5

            # remove copies from files that didn't exist

            del t[k]

        elif k not in dst:  # case 1

            # remove copies to files that were then removed

            del t[k]

def _chain(prefix, suffix):

    """chain two sets of copies 'prefix' and 'suffix'"""

    result = prefix.copy()

    for key, value in pycompat.iteritems(suffix):

        result[key] = prefix.get(value, value)

    return result

def _tracefile(fctx, am, basemf):

    """return file context that is the ancestor of fctx present in ancestor

    manifest am

    Note: we used to try and stop after a given limit, however checking if that

    limit is reached turned out to be very expensive. we are better off

    disabling that feature."""

    for f in fctx.ancestors():

        path = f.path()

        if am.get(path, None) == f.filenode():

            return path

        if basemf and basemf.get(path, None) == f.filenode():

            return path

def _dirstatecopies(repo, match=None):

    ds = repo.dirstate

    c = ds.copies().copy()

    for k in list(c):

        if ds[k] not in b'anm' or (match and not match(k)):

            del c[k]

    return c

def _computeforwardmissing(a, b, match=None):

    """Computes which files are in b but not a.

    This is its own function so extensions can easily wrap this call to see what

    files _forwardcopies is about to process.

    """

    ma = a.manifest()

    mb = b.manifest()

    return mb.filesnotin(ma, match=match)

def usechangesetcentricalgo(repo):

    """Checks if we should use changeset-centric copy algorithms"""

    if repo.filecopiesmode == b'changeset-sidedata':

        return True

    readfrom = repo.ui.config(b'experimental', b'copies.read-from')

    changesetsource = (b'changeset-only', b'compatibility')

    return readfrom in changesetsource

def _committedforwardcopies(a, b, base, match):

    """Like _forwardcopies(), but b.rev() cannot be None (working copy)"""

    # files might have to be traced back to the fctx parent of the last

    # one-side-only changeset, but not further back than that

    repo = a._repo

    if usechangesetcentricalgo(repo):

        return _changesetforwardcopies(a, b, match)

    debug = repo.ui.debugflag and repo.ui.configbool(b'devel', b'debug.copies')

    dbg = repo.ui.debug

    if debug:

        dbg(b'debug.copies:    looking into rename from %s to %s\n' % (a, b))

    am = a.manifest()

    basemf = None if base is None else base.manifest()

    # find where new files came from

    # we currently don't try to find where old files went, too expensive

    # this means we can miss a case like 'hg rm b; hg cp a b'

    cm = {}

    # Computing the forward missing is quite expensive on large manifests, since

    # it compares the entire manifests. We can optimize it in the common use

    # case of computing what copies are in a commit versus its parent (like

    # during a rebase or histedit). Note, we exclude merge commits from this

    # optimization, since the ctx.files() for a merge commit is not correct for

    # this comparison.

    forwardmissingmatch = match

    if b.p1() == a and b.p2().node() == nullid:

        filesmatcher = matchmod.exact(b.files())

        forwardmissingmatch = matchmod.intersectmatchers(match, filesmatcher)

    if repo.ui.configbool(b'devel', b'copy-tracing.trace-all-files'):

        missing = list(b.walk(match))

        # _computeforwardmissing(a, b, match=forwardmissingmatch)

        if debug:

            dbg(b'debug.copies:      searching all files: %d\n' % len(missing))

    else:

        missing = _computeforwardmissing(a, b, match=forwardmissingmatch)

        if debug:

            dbg(

                b'debug.copies:      missing files to search: %d\n'

                % len(missing)

            )

    ancestrycontext = a._repo.changelog.ancestors([b.rev()], inclusive=True)

    for f in sorted(missing):

        if debug:

            dbg(b'debug.copies:        tracing file: %s\n' % f)

        fctx = b[f]

        fctx._ancestrycontext = ancestrycontext

        if debug:

            start = util.timer()

        opath = _tracefile(fctx, am, basemf)

        if opath:

            if debug:

                dbg(b'debug.copies:          rename of: %s\n' % opath)

            cm[f] = opath

        if debug:

            dbg(

                b'debug.copies:          time: %f seconds\n'

                % (util.timer() - start)

            )

    return cm

def _revinfo_getter(repo, match):

    """returns a function that returns the following data given a <rev>"

    * p1: revision number of first parent

    * p2: revision number of first parent

    * changes: a ChangingFiles object

    """

    cl = repo.changelog

    parents = cl.parentrevs

    flags = cl.flags

    HASCOPIESINFO = flagutil.REVIDX_HASCOPIESINFO

    changelogrevision = cl.changelogrevision

    if rustmod is not None:

        def revinfo(rev):

            p1, p2 = parents(rev)

            if flags(rev) & HASCOPIESINFO:

                raw = changelogrevision(rev)._sidedata.get(sidedatamod.SD_FILES)

            else:

                raw = None

            return (p1, p2, raw)

    else:

        def revinfo(rev):

            p1, p2 = parents(rev)

            if flags(rev) & HASCOPIESINFO:

                changes = changelogrevision(rev).changes

            else:

                changes = None

            return (p1, p2, changes)

    return revinfo

def cached_is_ancestor(is_ancestor):

    """return a cached version of is_ancestor"""

    cache = {}

    def _is_ancestor(anc, desc):

        if anc > desc:

            return False

        elif anc == desc:

            return True

        key = (anc, desc)

        ret = cache.get(key)

        if ret is None:

            ret = cache[key] = is_ancestor(anc, desc)

        return ret

    return _is_ancestor

def _changesetforwardcopies(a, b, match):

    if a.rev() in (nullrev, b.rev()):

        return {}

    repo = a.repo().unfiltered()

    children = {}

    cl = repo.changelog

    isancestor = cl.isancestorrev

    # To track rename from "A" to B, we need to gather all parent → children

    # edges that are contains in `::B` but not in `::A`.

    #

    #

    # To do so, we need to gather all revisions exclusive¹ to "B" (ie¹: `::b -

    # ::a`) and also all the "roots point", ie the parents of the exclusive set

    # that belong to ::a. These are exactly all the revisions needed to express

    # the parent → children we need to combine.

    #

    # [1] actually, we need to gather all the edges within `(::a)::b`, ie:

    # excluding paths that leads to roots that are not ancestors of `a`. We

    # keep this out of the explanation because it is hard enough without this special case..

    parents = cl._uncheckedparentrevs

    graph_roots = (nullrev, nullrev)

    ancestors = cl.ancestors([a.rev()], inclusive=True)

    revs = cl.findmissingrevs(common=[a.rev()], heads=[b.rev()])

    roots = set()

    has_graph_roots = False

    # iterate over `only(B, A)`

    for r in revs:

        ps = parents(r)

        if ps == graph_roots:

            has_graph_roots = True

        else:

            p1, p2 = ps

            # find all the "root points" (see larger comment above)

            if p1 != nullrev and p1 in ancestors:

                roots.add(p1)

            if p2 != nullrev and p2 in ancestors:

                roots.add(p2)

    if not roots:

        # no common revision to track copies from

        return {}

    if has_graph_roots:

        # this deal with the special case mentionned in the [1] footnotes. We

        # must filter out revisions that leads to non-common graphroots.

        roots = list(roots)

        m = min(roots)

        h = [b.rev()]

        roots_to_head = cl.reachableroots(m, h, roots, includepath=True)

        roots_to_head = set(roots_to_head)

        revs = [r for r in revs if r in roots_to_head]

    if repo.filecopiesmode == b'changeset-sidedata':

        # When using side-data, we will process the edges "from" the children.

        # We iterate over the childre, gathering previous collected data for

        # the parents. Do know when the parents data is no longer necessary, we

        # keep a counter of how many children each revision has.

        #

        # An interresting property of `children_count` is that it only contains

        # revision that will be relevant for a edge of the graph. So if a

        # children has parent not in `children_count`, that edges should not be

        # processed.

        children_count = dict((r, 0) for r in roots)

        for r in revs:

            for p in cl.parentrevs(r):

                if p == nullrev:

                    continue

                children_count[r] = 0

                if p in children_count:

                    children_count[p] += 1

        revinfo = _revinfo_getter(repo, match)

        return _combine_changeset_copies(

            revs, children_count, b.rev(), revinfo, match, isancestor

        )

    else:

        # When not using side-data, we will process the edges "from" the parent.

        # so we need a full mapping of the parent -> children relation.

        children = dict((r, []) for r in roots)

        for r in revs:

            for p in cl.parentrevs(r):

                if p == nullrev:

                    continue

                children[r] = []

                if p in children:

                    children[p].append(r)

        x = revs.pop()

        assert x == b.rev()

        revs.extend(roots)

        revs.sort()

        revinfo = _revinfo_getter_extra(repo)

        return _combine_changeset_copies_extra(

            revs, children, b.rev(), revinfo, match, isancestor

        )

def _combine_changeset_copies(

    revs, children_count, targetrev, revinfo, match, isancestor

):

    """combine the copies information for each item of iterrevs

    revs: sorted iterable of revision to visit

    children_count: a {parent: <number-of-relevant-children>} mapping.

    targetrev: the final copies destination revision (not in iterrevs)

    revinfo(rev): a function that return (p1, p2, p1copies, p2copies, removed)

    match: a matcher

    It returns the aggregated copies information for `targetrev`.

    """

    alwaysmatch = match.always()

    if rustmod is not None:

        final_copies = rustmod.combine_changeset_copies(

            list(revs), children_count, targetrev, revinfo, isancestor

        )

    else:

        isancestor = cached_is_ancestor(isancestor)

        all_copies = {}

        # iterate over all the "children" side of copy tracing "edge"

        for current_rev in revs:

            p1, p2, changes = revinfo(current_rev)

            current_copies = None

            # iterate over all parents to chain the existing data with the

            # data from the parent → child edge.

            for parent, parent_rev in ((1, p1), (2, p2)):

                if parent_rev == nullrev:

                    continue

                remaining_children = children_count.get(parent_rev)

                if remaining_children is None:

                    continue

                remaining_children -= 1

                children_count[parent_rev] = remaining_children

                if remaining_children:

                    copies = all_copies.get(parent_rev, None)

                else:

                    copies = all_copies.pop(parent_rev, None)

                if copies is None:

                    # this is a root