# 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 _chain(src, dst, a, b):

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

    # 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

    # Initialize result ('t') from 'a'. This catches cases 1 & 2. We'll remove

    # case 1 later. We'll also catch cases 3 & 4 here. Case 4 will be

    # overwritten later, and case 3 will be removed later.

    t = a.copy()

    for k, v in b.iteritems():

        if v in t:

            # found a chain, i.e. cases 3 & 4.

            if t[v] != k:

                # file wasn't renamed back to itself (i.e. case 4, not 3)

                t[k] = t[v]

            # file is a copy of an existing file, i.e. case 6.

            t[k] = v

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

        # remove criss-crossed copies, i.e. case 3

        if k in src and v in dst:

            del t[k]

        # remove copies to files that were then removed, i.e. case 1

        # and file 'y' in cases 3 & 4 (in case of rename)

        elif k not in dst:

            del t[k]

    return t

def _tracefile(fctx, am, limit=node.nullrev):

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

            ctx = repo[r]

            p1man, p2man = ctx.p1().manifest(), ctx.p2().manifest()

            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

                if dst not in copies2:

                    # Copied on p1 side: mark as copy from p1 side if it didn't

                    # already exist on p2 side

                    if dst not in p2man:

                        copies[dst] = copies1[dst]

                elif dst not in copies1:

                    # Copied on p2 side: mark as copy from p2 side if it didn't

                    # already exist on p1 side

                    if dst not in p1man:

                        copies[dst] = copies2[dst]

                else:

                    # Copied on both sides: mark as copy from p1 side

                    copies[dst] = copies1[dst]

        else:

            copies = copies1

        if r == b.rev():

            return copies

        for c in children[r]:

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

            childcopies = _chain(a, childctx, copies, childcopies)

            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 _chain(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 _chain(x, y, _backwardrenames(x, a, match=match),

                  _forwardcopies(a, y, match=match))

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