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

import os

from .i18n import _

from .revlogutils.flagutil import REVIDX_SIDEDATA

from . import (

    error,

    match as matchmod,

    node,

    pathutil,

    pycompat,

    util,

)

from .revlogutils import sidedata as sidedatamod

from .utils import stringutil

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 2

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

        # remove copies from files that didn't exist

        if v not in src:

            del t[k]

        # remove criss-crossed copies

        elif k in src and v in dst:

            del t[k]

        # remove copies to files that were then removed

        elif k not in dst:

            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() == node.nullid:

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

        forwardmissingmatch = matchmod.intersectmatchers(match, filesmatcher)

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

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

    if debug:

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

    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 _revinfogetter(repo):

    """return a function that return multiple data given a <rev>"i

    * p1: revision number of first parent

    * p2: revision number of first parent

    * p1copies: mapping of copies from p1

    * p2copies: mapping of copies from p2

    * removed: a list of removed files

    """

    cl = repo.changelog

    parents = cl.parentrevs

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

        changelogrevision = cl.changelogrevision

        flags = cl.flags

        # A small cache to avoid doing the work twice for merges

        #

        # In the vast majority of cases, if we ask information for a revision

        # about 1 parent, we'll later ask it for the other. So it make sense to

        # keep the information around when reaching the first parent of a merge

        # and dropping it after it was provided for the second parents.

        #

        # It exists cases were only one parent of the merge will be walked. It

        # happens when the "destination" the copy tracing is descendant from a

        # new root, not common with the "source". In that case, we will only walk

        # through merge parents that are descendant of changesets common

        # between "source" and "destination".

        #

        # With the current case implementation if such changesets have a copy

        # information, we'll keep them in memory until the end of

        # _changesetforwardcopies. We don't expect the case to be frequent

        # enough to matters.

        #

        # In addition, it would be possible to reach pathological case, were

        # many first parent are met before any second parent is reached. In

        # that case the cache could grow. If this even become an issue one can

        # safely introduce a maximum cache size. This would trade extra CPU/IO

        # time to save memory.

        merge_caches = {}

        def revinfo(rev):

            p1, p2 = parents(rev)

            if flags(rev) & REVIDX_SIDEDATA:

                e = merge_caches.pop(rev, None)

                if e is not None:

                    return e

                c = changelogrevision(rev)

                p1copies = c.p1copies

                p2copies = c.p2copies

                removed = c.filesremoved

                if p1 != node.nullrev and p2 != node.nullrev:

                    # XXX some case we over cache, IGNORE

                    merge_caches[rev] = (p1, p2, p1copies, p2copies, removed)

            else:

                p1copies = {}

                p2copies = {}

                removed = []

            return p1, p2, p1copies, p2copies, removed

    else:

        def revinfo(rev):

            p1, p2 = parents(rev)

            ctx = repo[rev]

            p1copies, p2copies = ctx._copies

            removed = ctx.filesremoved()

            return p1, p2, p1copies, p2copies, removed

    return revinfo

def _changesetforwardcopies(a, b, match):

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

        return {}

    repo = a.repo().unfiltered()

    children = {}

    revinfo = _revinfogetter(repo)

    cl = repo.changelog

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

    mrset = set(missingrevs)

    roots = set()

    for r in missingrevs:

        for p in cl.parentrevs(r):

            if p == node.nullrev:

                continue

            if p not in children:

                children[p] = [r]

            else:

                children[p].append(r)

            if p not in mrset:

                roots.add(p)

    if not roots:

        # no common revision to track copies from

        return {}

    min_root = min(roots)

    from_head = set(

        cl.reachableroots(min_root, [b.rev()], list(roots), includepath=True)

    )

    iterrevs = set(from_head)

    iterrevs &= mrset

    iterrevs.update(roots)

    iterrevs.remove(b.rev())

    revs = sorted(iterrevs)

    return _combinechangesetcopies(revs, children, b.rev(), revinfo, match)

def _combinechangesetcopies(revs, children, targetrev, revinfo, match):

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

    revs: sorted iterable of revision to visit

    children: a {parent: [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`.

    """

    all_copies = {}

    alwaysmatch = match.always()

    for r in revs:

        copies = all_copies.pop(r, None)

        if copies is None:

            # this is a root

            copies = {}

        for i, c in enumerate(children[r]):

            p1, p2, p1copies, p2copies, removed = revinfo(c)

            if r == p1:

                parent = 1

                childcopies = p1copies

            else:

                assert r == p2

                parent = 2

                childcopies = p2copies

            if not alwaysmatch:

                childcopies = {

                    dst: src for dst, src in childcopies.items() if match(dst)

                }

            newcopies = copies

            if childcopies:

                newcopies = _chain(newcopies, childcopies)

                # _chain makes a copies, we can avoid doing so in some

                # simple/linear cases.

                assert newcopies is not copies

            for f in removed:

                if f in newcopies:

                    if newcopies is copies:

                        # copy on write to avoid affecting potential other

                        # branches.  when there are no other branches, this

                        # could be avoided.

                        newcopies = copies.copy()

                    del newcopies[f]

            othercopies = all_copies.get(c)

            if othercopies is None:

                all_copies[c] = newcopies

            else:

                # we are the second parent to work on c, we need to merge our

                # work with the other.

                #

                # Unlike when copies are stored in the filelog, we consider

                # it a copy even if the destination already existed on the

                # other branch. It's simply too expensive to check if the

                # file existed in the manifest.

                #

                # In case of conflict, parent 1 take precedence over parent 2.

                # This is an arbitrary choice made anew when implementing

                # changeset based copies. It was made without regards with

                # potential filelog related behavior.

                if parent == 1:

                    othercopies.update(newcopies)

                else:

                    newcopies.update(othercopies)

                    all_copies[c] = newcopies

    return all_copies[targetrev]

def _forwardcopies(a, b, base=None, match=None):

    """find {dst@b: src@a} copy mapping where a is an ancestor of b"""

    if base is None:

        base = a

    match = a.repo().narrowmatch(match)

    # check for working copy

    if b.rev() is None:

        cm = _committedforwardcopies(a, b.p1(), base, match)

        # combine copies from dirstate if necessary

        copies = _chain(cm, _dirstatecopies(b._repo, match))

    else:

        copies = _committedforwardcopies(a, b, base, match)

    return copies

def _backwardrenames(a, b, match):

    if a._repo.ui.config(b'experimental', b'copytrace') == b'off':

        return {}

    # Even though we're not taking copies into account, 1:n rename situations

    # can still exist (e.g. hg cp a b; hg mv a c). In those cases we

    # arbitrarily pick one of the renames.

    # We don't want to pass in "match" here, since that would filter

    # the destination by it. Since we're reversing the copies, we want

    # to filter the source instead.

    f = _forwardcopies(b, a)

    r = {}

    for k, v in sorted(pycompat.iteritems(f)):

        if match and not match(v):

            continue

        # remove copies

        if v in a:

            continue