# 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 . import (

    match as matchmod,

    node,

    pathutil,

    pycompat,

    util,

)

from .utils import stringutil

from .revlogutils import flagutil

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

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

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

        value = None

        e = merge_caches.pop(rev, None)

        if e is not None:

            return e

        changes = None

        if flags(rev) & HASCOPIESINFO:

            changes = changelogrevision(rev).changes

        value = (p1, p2, changes)

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

            # XXX some case we over cache, IGNORE

            merge_caches[rev] = value

        return value

    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 (node.nullrev, b.rev()):

        return {}

    repo = a.repo().unfiltered()

    children = {}

    cl = repo.changelog

    isancestor = cached_is_ancestor(cl.isancestorrev)

    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)

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

        revinfo = _revinfo_getter(repo)

        return _combine_changeset_copies(

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

        )

    else:

        revinfo = _revinfo_getter_extra(repo)

        return _combine_changeset_copies_extra(

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

        )

def _combine_changeset_copies(

    revs, children, targetrev, revinfo, match, isancestor

):

    """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 = {}

    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, changes = revinfo(c)

            childcopies = {}

            if r == p1:

                parent = 1

                if changes is not None:

                    childcopies = changes.copied_from_p1

            else:

                assert r == p2

                parent = 2

                if changes is not None:

                    childcopies = changes.copied_from_p2

            if not alwaysmatch:

                childcopies = {

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

                }

            newcopies = copies

            if childcopies:

                newcopies = copies.copy()

                for dest, source in pycompat.iteritems(childcopies):

                    prev = copies.get(source)

                    if prev is not None and prev[1] is not None:

                        source = prev[1]

                    newcopies[dest] = (c, source)

                assert newcopies is not copies

            if changes is not None:

                for f in changes.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()

                        newcopies[f] = (c, None)

            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.

                #

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

                    _merge_copies_dict(

                        othercopies, newcopies, isancestor, changes

                    )

                else:

                    _merge_copies_dict(

                        newcopies, othercopies, isancestor, changes

                    )

                    all_copies[c] = newcopies

    final_copies = {}

    for dest, (tt, source) in all_copies[targetrev].items():

        if source is not None:

            final_copies[dest] = source

    return final_copies

def _merge_copies_dict(minor, major, isancestor, changes):

    """merge two copies-mapping together, minor and major

    In case of conflict, value from "major" will be picked.

    - `isancestors(low_rev, high_rev)`: callable return True if `low_rev` is an

                                        ancestors of `high_rev`,

    - `ismerged(path)`: callable return True if `path` have been merged in the

                        current revision,

    """

    for dest, value in major.items():

        other = minor.get(dest)

        if other is None:

            minor[dest] = value

        else:

            new_tt = value[0]

            other_tt = other[0]

            if value[1] == other[1]:

                continue

            # content from "major" wins, unless it is older

            # than the branch point or there is a merge

            if new_tt == other_tt:

                minor[dest] = value

            elif (

                changes is not None

                and value[1] is None

                and dest in changes.salvaged

            ):

                pass

            elif (

                changes is not None

                and other[1] is None

                and dest in changes.salvaged

            ):

                minor[dest] = value

            elif changes is not None and dest in changes.merged:

                minor[dest] = value

            elif not isancestor(new_tt, other_tt):

                if value[1] is not None:

                    minor[dest] = value

                elif isancestor(other_tt, new_tt):

                    minor[dest] = value

def _revinfo_getter_extra(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

    * ismerged: a callback to know if file was merged in that revision

    """

    cl = repo.changelog

    parents = cl.parentrevs

    def get_ismerged(rev):

        ctx = repo[rev]

        def ismerged(path):

            if path not in ctx.files():

                return False

            fctx = ctx[path]

            parents = fctx._filelog.parents(fctx._filenode)

            nb_parents = 0

            for n in parents:

                if n != node.nullid:

                    nb_parents += 1

            return nb_parents >= 2

        return ismerged

    def revinfo(rev):

        p1, p2 = parents(rev)

        ctx = repo[rev]

        p1copies, p2copies = ctx._copies

        removed = ctx.filesremoved()

        return p1, p2, p1copies, p2copies, removed, get_ismerged(rev)

    return revinfo

def _combine_changeset_copies_extra(

    revs, children, targetrev, revinfo, match, isancestor

):

    """version of `_combine_changeset_copies` that works with the Google

    specific "extra" based storage for copy information"""

    all_copies = {}

    alwaysmatch = match.always()

    for r in revs:

        copies = all_copies.pop(r, None)