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

import os

from .i18n import _

from . import (

    match as matchmod,

    node,

    pathutil,

    util,

)

from .utils import (

    stringutil,

)

def _findlimit(repo, ctxa, ctxb):

    """

    Find the last revision that needs to be checked to ensure that a full

    transitive closure for file copies can be properly calculated.

    Generally, this means finding the earliest revision number that's an

    ancestor of a or b but not both, except when a or b is a direct descendent

    of the other, in which case we can return the minimum revnum of a and b.

    """

    # basic idea:

    # - mark a and b with different sides

    # - if a parent's children are all on the same side, the parent is

    #   on that side, otherwise it is on no side

    # - walk the graph in topological order with the help of a heap;

    #   - add unseen parents to side map

    #   - clear side of any parent that has children on different sides

    #   - track number of interesting revs that might still be on a side

    #   - track the lowest interesting rev seen

    #   - quit when interesting revs is zero

    cl = repo.changelog

    wdirparents = None

    a = ctxa.rev()

    b = ctxb.rev()

    if a is None:

        wdirparents = (ctxa.p1(), ctxa.p2())

        a = node.wdirrev

    if b is None:

        assert not wdirparents

        wdirparents = (ctxb.p1(), ctxb.p2())

        b = node.wdirrev

    side = {a: -1, b: 1}

    visit = [-a, -b]

    heapq.heapify(visit)

    interesting = len(visit)

    limit = node.wdirrev

    while interesting:

        r = -heapq.heappop(visit)

        if r == node.wdirrev:

            parents = [pctx.rev() for pctx in wdirparents]

        else:

            parents = cl.parentrevs(r)

        if parents[1] == node.nullrev:

            parents = parents[:1]

        for p in parents:

            if p not in side:

                # first time we see p; add it to visit

                side[p] = side[r]

                if side[p]:

                    interesting += 1

                heapq.heappush(visit, -p)

            elif side[p] and side[p] != side[r]:

                # p was interesting but now we know better

                side[p] = 0

                interesting -= 1

        if side[r]:

            limit = r # lowest rev visited

            interesting -= 1

    # Consider the following flow (see test-commit-amend.t under issue4405):

    # 1/ File 'a0' committed

    # 2/ File renamed from 'a0' to 'a1' in a new commit (call it 'a1')

    # 3/ Move back to first commit

    # 4/ Create a new commit via revert to contents of 'a1' (call it 'a1-amend')

    # 5/ Rename file from 'a1' to 'a2' and commit --amend 'a1-msg'

    #

    # During the amend in step five, we will be in this state:

    #

    # @  3 temporary amend commit for a1-amend

    # |

    # o  2 a1-amend

    # |

    # | o  1 a1

    # |/

    # o  0 a0

    #

    # When _findlimit is called, a and b are revs 3 and 0, so limit will be 2,

    # yet the filelog has the copy information in rev 1 and we will not look

    # back far enough unless we also look at the a and b as candidates.

    # This only occurs when a is a descendent of b or visa-versa.

    return min(limit, a, b)

def _chainandfilter(src, dst, a, b):

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

    # When chaining 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().

    t = _chain(a, b)

    _filter(src, dst, t)

    return t

def _filter(src, dst, t):

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

    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 b.iteritems():

        if v in t:

            t[k] = t[v]

        else:

            t[k] = v

    return t

def _tracefile(fctx, am, limit):

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

    manifest am, stopping after the first ancestor lower than limit"""

    for f in fctx.ancestors():

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

            return f

        if not f.isintroducedafter(limit):

            return None

def _dirstatecopies(repo, match=None):

    ds = repo.dirstate

    c = ds.copies().copy()

    for k in list(c):

        if ds[k] not in '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"""

    return (repo.ui.config('experimental', 'copies.read-from') in

            ('changeset-only', 'compatibility'))

def _committedforwardcopies(a, b, 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('devel', 'debug.copies')

    dbg = repo.ui.debug

    if debug:

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

            % (a, b))

    limit = _findlimit(repo, a, b)

    if debug:

        dbg('debug.copies:      search limit: %d\n' % limit)

    am = a.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('debug.copies:      missing files to search: %d\n' % len(missing))

    for f in sorted(missing):

        if debug:

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

        fctx = b[f]

        fctx._ancestrycontext = ancestrycontext

        if debug:

            start = util.timer()

        ofctx = _tracefile(fctx, am, limit)

        if ofctx:

            if debug:

                dbg('debug.copies:          rename of: %s\n' % ofctx._path)

            cm[f] = ofctx.path()

        if debug:

            dbg('debug.copies:          time: %f seconds\n'

                % (util.timer() - start))

    return cm

def _changesetforwardcopies(a, b, match):

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

        return {}

    repo = a.repo()

    children = {}

    cl = repo.changelog

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

    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)

    roots = set(children) - set(missingrevs)

    # 'work' contains 3-tuples of a (revision number, parent number, copies).

    # The parent number is only used for knowing which parent the copies dict

    # came from.

    work = [(r, 1, {}) for r in roots]

    heapq.heapify(work)

    while work:

        r, i1, copies1 = heapq.heappop(work)

        if work and work[0][0] == r:

            # We are tracing copies from both parents

            r, i2, copies2 = heapq.heappop(work)

            copies = {}

            allcopies = set(copies1) | set(copies2)

            # TODO: perhaps this filtering should be done as long as ctx

            # is merge, whether or not we're tracing from both parent.

            for dst in allcopies:

                if not match(dst):

                    continue

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

                if dst in copies1:

                    # If it was copied on the p1 side, mark it as copied from

                    # that side, even if it was also copied on the p2 side.

                    copies[dst] = copies1[dst]

                else:

                    copies[dst] = copies2[dst]

        else:

            copies = copies1

        if r == b.rev():

            _filter(a, b, copies)

            return copies

            childctx = repo[c]

            if r == childctx.p1().rev():

                parent = 1

                childcopies = childctx.p1copies()

            else:

                assert r == childctx.p2().rev()

                parent = 2

                childcopies = childctx.p2copies()

            if not match.always():

                childcopies = {dst: src for dst, src in childcopies.items()

                               if match(dst)}

            for f in childctx.filesremoved():

                if f in childcopies:

                    del childcopies[f]

            heapq.heappush(work, (c, parent, childcopies))

    assert False

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

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

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

    # check for working copy

    if b.rev() is None:

        if a == b.p1():

            # short-circuit to avoid issues with merge states

            return _dirstatecopies(b._repo, match)

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

        # combine copies from dirstate if necessary

        return _chainandfilter(a, b, cm, _dirstatecopies(b._repo, match))

    return _committedforwardcopies(a, b, match)

def _backwardrenames(a, b, match):

    if a._repo.ui.config('experimental', 'copytrace') == '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(f.iteritems()):

        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('devel', 'debug.copies')

    if debug:

        repo.ui.debug('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('debug.copies: search mode: forward\n')

        return _forwardcopies(x, y, match=match)

    if a == y:

        if debug:

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

        return _backwardrenames(x, y, match=match)

    if debug:

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

    return _chainandfilter(x, y, _backwardrenames(x, a, match=match),