# 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 .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(a, b):

    """chain two sets of copies 'a' and 'b'"""

    t = a.copy()

    for k, v in pycompat.iteritems(b):

        if v in t:

            t[k] = t[v]

        else:

            t[k] = v

    return t

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

        def revinfo(rev):

            p1, p2 = parents(rev)

            if flags(rev) & REVIDX_SIDEDATA:

                c = changelogrevision(rev)

                p1copies = c.p1copies

                p2copies = c.p2copies

                removed = c.filesremoved

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

    all_copies = {r: {} for r in roots}

    alwaysmatch = match.always()

    for r in sorted(iterrevs):

        copies = all_copies.pop(r)

        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)

                }

            if childcopies:

                newcopies = _chain(newcopies, childcopies)

            for f in removed:

                if f in newcopies:

                    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[b.rev()]

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

        r[v] = k

    return r

def pathcopies(x, y, match=None):

    """find {dst@y: src@x} copy mapping for directed compare"""

    repo = x._repo

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

    if debug:

        repo.ui.debug(

            b'debug.copies: searching copies from %s to %s\n' % (x, y)

        )

    if x == y or not x or not y:

        return {}

    a = y.ancestor(x)

    if a == x:

        if debug:

            repo.ui.debug(b'debug.copies: search mode: forward\n')

        if y.rev() is None and x == y.p1():

            # short-circuit to avoid issues with merge states

            return _dirstatecopies(repo, match)

        copies = _forwardcopies(x, y, match=match)

    elif a == y:

        if debug:

            repo.ui.debug(b'debug.copies: search mode: backward\n')

        copies = _backwardrenames(x, y, match=match)

    else:

        if debug:

            repo.ui.debug(b'debug.copies: search mode: combined\n')

        base = None

        if a.rev() != node.nullrev:

            base = x

        copies = _chain(

            _backwardrenames(x, a, match=match),

            _forwardcopies(a, y, base, match=match),

        )

    _filter(x, y, copies)

    return copies

def mergecopies(repo, c1, c2, base):

    """

    Finds moves and copies between context c1 and c2 that are relevant for

    merging. 'base' will be used as the merge base.

    Copytracing is used in commands like rebase, merge, unshelve, etc to merge

    files that were moved/ copied in one merge parent and modified in another.

    For example:

    o          ---> 4 another commit

    |

    |   o      ---> 3 commit that modifies a.txt

    |  /

    o /        ---> 2 commit that moves a.txt to b.txt

    |/

    o          ---> 1 merge base

    If we try to rebase revision 3 on revision 4, since there is no a.txt in

    revision 4, and if user have copytrace disabled, we prints the following

    message:

    ```other changed <file> which local deleted```

    Returns five dicts: "copy", "movewithdir", "diverge", "renamedelete" and

    "dirmove".

    "copy" is a mapping from destination name -> source name,

    where source is in c1 and destination is in c2 or vice-versa.

    "movewithdir" is a mapping from source name -> destination name,

    where the file at source present in one context but not the other

    needs to be moved to destination by the merge process, because the

    other context moved the directory it is in.

    "diverge" is a mapping of source name -> list of destination names

    for divergent renames.

    "renamedelete" is a mapping of source name -> list of destination

    names for files deleted in c1 that were renamed in c2 or vice-versa.

    "dirmove" is a mapping of detected source dir -> destination dir renames.

    This is needed for handling changes to new files previously grafted into

    renamed directories.

    This function calls different copytracing algorithms based on config.

    """

    # avoid silly behavior for update from empty dir

    if not c1 or not c2 or c1 == c2:

        return {}, {}, {}, {}, {}

    narrowmatch = c1.repo().narrowmatch()

    # avoid silly behavior for parent -> working dir

    if c2.node() is None and c1.node() == repo.dirstate.p1():

        return _dirstatecopies(repo, narrowmatch), {}, {}, {}, {}

    copytracing = repo.ui.config(b'experimental', b'copytrace')

    if stringutil.parsebool(copytracing) is False:

        # stringutil.parsebool() returns None when it is unable to parse the

        # value, so we should rely on making sure copytracing is on such cases

        return {}, {}, {}, {}, {}

    if usechangesetcentricalgo(repo):

        # The heuristics don't make sense when we need changeset-centric algos

        return _fullcopytracing(repo, c1, c2, base)

    # Copy trace disabling is explicitly below the node == p1 logic above

    # because the logic above is required for a simple copy to be kept across a

    # rebase.

    if copytracing == b'heuristics':

        # Do full copytracing if only non-public revisions are involved as

        # that will be fast enough and will also cover the copies which could

        # be missed by heuristics

        if _isfullcopytraceable(repo, c1, base):

            return _fullcopytracing(repo, c1, c2, base)

        return _heuristicscopytracing(repo, c1, c2, base)

    else:

        return _fullcopytracing(repo, c1, c2, base)

def _isfullcopytraceable(repo, c1, base):

    """ Checks that if base, source and destination are all no-public branches,

    if yes let's use the full copytrace algorithm for increased capabilities

    since it will be fast enough.

    `experimental.copytrace.sourcecommitlimit` can be used to set a limit for

    number of changesets from c1 to base such that if number of changesets are

    more than the limit, full copytracing algorithm won't be used.

    """

    if c1.rev() is None:

        c1 = c1.p1()

    if c1.mutable() and base.mutable():

        sourcecommitlimit = repo.ui.configint(

            b'experimental', b'copytrace.sourcecommitlimit'

        )

        commits = len(repo.revs(b'%d::%d', base.rev(), c1.rev()))

        return commits < sourcecommitlimit