copies.py
805 lines
| 29.2 KiB
| text/x-python
|
PythonLexer
/ mercurial / copies.py
|
r6274 | # copies.py - copy detection for Mercurial | ||
# | ||||
# Copyright 2008 Matt Mackall <mpm@selenic.com> | ||||
# | ||||
|
r8225 | # This software may be used and distributed according to the terms of the | ||
|
r10263 | # GNU General Public License version 2 or any later version. | ||
|
r6274 | |||
|
r25924 | from __future__ import absolute_import | ||
|
r34180 | import collections | ||
|
r8312 | import heapq | ||
|
r34180 | import os | ||
|
r6274 | |||
|
r34847 | from .i18n import _ | ||
|
r25924 | from . import ( | ||
|
r33869 | match as matchmod, | ||
|
r28000 | node, | ||
|
r25924 | pathutil, | ||
util, | ||||
) | ||||
|
r39402 | from .utils import ( | ||
stringutil, | ||||
) | ||||
|
r25924 | |||
|
r41438 | def _findlimit(repo, ctxa, ctxb): | ||
|
r23071 | """ | ||
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. | ||||
|
r10179 | """ | ||
|
r23071 | |||
|
r6429 | # 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 | ||||
|
r6431 | # - track number of interesting revs that might still be on a side | ||
# - track the lowest interesting rev seen | ||||
# - quit when interesting revs is zero | ||||
|
r6430 | |||
cl = repo.changelog | ||||
|
r41439 | wdirparents = None | ||
|
r41438 | a = ctxa.rev() | ||
b = ctxb.rev() | ||||
|
r6430 | if a is None: | ||
|
r41439 | wdirparents = (ctxa.p1(), ctxa.p2()) | ||
|
r41267 | a = node.wdirrev | ||
|
r6430 | if b is None: | ||
|
r41439 | assert not wdirparents | ||
wdirparents = (ctxb.p1(), ctxb.p2()) | ||||
|
r41267 | b = node.wdirrev | ||
|
r6429 | |||
side = {a: -1, b: 1} | ||||
visit = [-a, -b] | ||||
heapq.heapify(visit) | ||||
interesting = len(visit) | ||||
|
r41267 | limit = node.wdirrev | ||
|
r6429 | |||
while interesting: | ||||
r = -heapq.heappop(visit) | ||||
|
r41267 | if r == node.wdirrev: | ||
|
r41439 | parents = [pctx.rev() for pctx in wdirparents] | ||
|
r6430 | else: | ||
parents = cl.parentrevs(r) | ||||
|
r41437 | if parents[1] == node.nullrev: | ||
parents = parents[:1] | ||||
|
r6430 | for p in parents: | ||
|
r6429 | 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 | ||||
|
r6430 | if side[r]: | ||
|
r6431 | limit = r # lowest rev visited | ||
|
r6430 | interesting -= 1 | ||
|
r10179 | |||
|
r23071 | # 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 | ||||
# | ||||
|
r23139 | # When _findlimit is called, a and b are revs 3 and 0, so limit will be 2, | ||
|
r23071 | # 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) | ||||
|
r6429 | |||
|
r42565 | def _chainandfilter(src, dst, a, b): | ||
"""chain two sets of copies 'a' and 'b' and filter result""" | ||||
|
r42413 | |||
# 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 | ||||
|
r42565 | # | ||
# _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(). | ||||
|
r42413 | |||
|
r42565 | 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'""" | ||||
|
r15775 | t = a.copy() | ||
for k, v in b.iteritems(): | ||||
if v in t: | ||||
|
r42440 | t[k] = t[v] | ||
|
r42416 | else: | ||
|
r15775 | t[k] = v | ||
return t | ||||
|
r42427 | def _tracefile(fctx, am, limit): | ||
|
r35422 | """return file context that is the ancestor of fctx present in ancestor | ||
manifest am, stopping after the first ancestor lower than limit""" | ||||
|
r15775 | |||
for f in fctx.ancestors(): | ||||
if am.get(f.path(), None) == f.filenode(): | ||||
return f | ||||
|
r42427 | if not f.isintroducedafter(limit): | ||
|
r15775 | return None | ||
|
r41918 | def _dirstatecopies(repo, match=None): | ||
ds = repo.dirstate | ||||
|
r15775 | c = ds.copies().copy() | ||
|
r34350 | for k in list(c): | ||
|
r35421 | if ds[k] not in 'anm' or (match and not match(k)): | ||
|
r15775 | del c[k] | ||
return c | ||||
|
r24782 | def _computeforwardmissing(a, b, match=None): | ||
|
r24011 | """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. | ||||
""" | ||||
|
r24782 | ma = a.manifest() | ||
mb = b.manifest() | ||||
|
r31256 | return mb.filesnotin(ma, match=match) | ||
|
r24011 | |||
|
r42284 | def usechangesetcentricalgo(repo): | ||
"""Checks if we should use changeset-centric copy algorithms""" | ||||
|
r42318 | return (repo.ui.config('experimental', 'copies.read-from') in | ||
('changeset-only', 'compatibility')) | ||||
|
r42284 | |||
|
r35423 | def _committedforwardcopies(a, b, match): | ||
"""Like _forwardcopies(), but b.rev() cannot be None (working copy)""" | ||||
|
r20294 | # files might have to be traced back to the fctx parent of the last | ||
# one-side-only changeset, but not further back than that | ||||
|
r40093 | repo = a._repo | ||
|
r41922 | |||
|
r42284 | if usechangesetcentricalgo(repo): | ||
|
r41922 | return _changesetforwardcopies(a, b, match) | ||
|
r40093 | 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)) | ||||
|
r41438 | limit = _findlimit(repo, a, b) | ||
|
r40093 | if debug: | ||
dbg('debug.copies: search limit: %d\n' % limit) | ||||
|
r20294 | am = a.manifest() | ||
|
r15775 | # 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 = {} | ||||
|
r28000 | |||
# 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 | ||||
|
r33869 | if b.p1() == a and b.p2().node() == node.nullid: | ||
|
r42102 | filesmatcher = matchmod.exact(b.files()) | ||
|
r33869 | forwardmissingmatch = matchmod.intersectmatchers(match, filesmatcher) | ||
|
r28000 | missing = _computeforwardmissing(a, b, match=forwardmissingmatch) | ||
|
r23980 | ancestrycontext = a._repo.changelog.ancestors([b.rev()], inclusive=True) | ||
|
r40093 | |||
if debug: | ||||
|
r42396 | dbg('debug.copies: missing files to search: %d\n' % len(missing)) | ||
|
r40093 | |||
|
r42396 | for f in sorted(missing): | ||
|
r40093 | if debug: | ||
dbg('debug.copies: tracing file: %s\n' % f) | ||||
|
r23980 | fctx = b[f] | ||
fctx._ancestrycontext = ancestrycontext | ||||
|
r40093 | |||
|
r40094 | if debug: | ||
start = util.timer() | ||||
|
r23980 | ofctx = _tracefile(fctx, am, limit) | ||
|
r18878 | if ofctx: | ||
|
r40093 | if debug: | ||
dbg('debug.copies: rename of: %s\n' % ofctx._path) | ||||
|
r18878 | cm[f] = ofctx.path() | ||
|
r40094 | if debug: | ||
|
r40112 | dbg('debug.copies: time: %f seconds\n' | ||
|
r40094 | % (util.timer() - start)) | ||
|
r35423 | return cm | ||
|
r41922 | 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)} | ||||
|
r42565 | childcopies = _chainandfilter(a, childctx, copies, childcopies) | ||
|
r41922 | heapq.heappush(work, (c, parent, childcopies)) | ||
assert False | ||||
|
r35423 | def _forwardcopies(a, b, match=None): | ||
"""find {dst@b: src@a} copy mapping where a is an ancestor of b""" | ||||
|
r40487 | match = a.repo().narrowmatch(match) | ||
|
r35423 | # check for working copy | ||
if b.rev() is None: | ||||
|
r35424 | if a == b.p1(): | ||
|
r35423 | # short-circuit to avoid issues with merge states | ||
|
r41918 | return _dirstatecopies(b._repo, match) | ||
|
r35423 | |||
|
r35424 | cm = _committedforwardcopies(a, b.p1(), match) | ||
# combine copies from dirstate if necessary | ||||
|
r42565 | return _chainandfilter(a, b, cm, _dirstatecopies(b._repo, match)) | ||
|
r35424 | return _committedforwardcopies(a, b, match) | ||
|
r15775 | |||
|
r41919 | def _backwardrenames(a, b, match): | ||
|
r34079 | if a._repo.ui.config('experimental', 'copytrace') == 'off': | ||
|
r26013 | return {} | ||
|
r18136 | # 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. | ||||
|
r41919 | # 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. | ||||
|
r15775 | f = _forwardcopies(b, a) | ||
r = {} | ||||
|
r18355 | for k, v in sorted(f.iteritems()): | ||
|
r41919 | if match and not match(v): | ||
continue | ||||
|
r18136 | # remove copies | ||
if v in a: | ||||
continue | ||||
|
r15775 | r[v] = k | ||
return r | ||||
|
r24782 | def pathcopies(x, y, match=None): | ||
|
r35422 | """find {dst@y: src@x} copy mapping for directed compare""" | ||
|
r40093 | 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)) | ||||
|
r15775 | if x == y or not x or not y: | ||
return {} | ||||
a = y.ancestor(x) | ||||
if a == x: | ||||
|
r40093 | if debug: | ||
repo.ui.debug('debug.copies: search mode: forward\n') | ||||
|
r24782 | return _forwardcopies(x, y, match=match) | ||
|
r15775 | if a == y: | ||
|
r40093 | if debug: | ||
repo.ui.debug('debug.copies: search mode: backward\n') | ||||
|
r41919 | return _backwardrenames(x, y, match=match) | ||
|
r40093 | if debug: | ||
repo.ui.debug('debug.copies: search mode: combined\n') | ||||
|
r42565 | return _chainandfilter(x, y, _backwardrenames(x, a, match=match), | ||
_forwardcopies(a, y, match=match)) | ||||
|
r15774 | |||
|
r30186 | def mergecopies(repo, c1, c2, base): | ||
|
r6274 | """ | ||
|
r42287 | Finds moves and copies between context c1 and c2 that are relevant for | ||
|
r34080 | 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: | ||||
|
r33821 | |||
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``` | ||||
|
r30581 | Returns five dicts: "copy", "movewithdir", "diverge", "renamedelete" and | ||
"dirmove". | ||||
|
r16168 | |||
|
r16177 | "copy" is a mapping from destination name -> source name, | ||
|
r16168 | where source is in c1 and destination is in c2 or vice-versa. | ||
|
r18134 | "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. | ||||
|
r16168 | "diverge" is a mapping of source name -> list of destination names | ||
for divergent renames. | ||||
|
r16794 | |||
"renamedelete" is a mapping of source name -> list of destination | ||||
names for files deleted in c1 that were renamed in c2 or vice-versa. | ||||
|
r30581 | |||
"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. | ||||
|
r42287 | |||
This function calls different copytracing algorithms based on config. | ||||
|
r6274 | """ | ||
# avoid silly behavior for update from empty dir | ||||
|
r6430 | if not c1 or not c2 or c1 == c2: | ||
|
r30581 | return {}, {}, {}, {}, {} | ||
|
r6274 | |||
|
r41918 | narrowmatch = c1.repo().narrowmatch() | ||
|
r6646 | # avoid silly behavior for parent -> working dir | ||
|
r13878 | if c2.node() is None and c1.node() == repo.dirstate.p1(): | ||
|
r41918 | return _dirstatecopies(repo, narrowmatch), {}, {}, {}, {} | ||
|
r6646 | |||
|
r34080 | copytracing = repo.ui.config('experimental', 'copytrace') | ||
|
r42411 | 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 {}, {}, {}, {}, {} | ||||
|
r34080 | |||
|
r42412 | if usechangesetcentricalgo(repo): | ||
# The heuristics don't make sense when we need changeset-centric algos | ||||
return _fullcopytracing(repo, c1, c2, base) | ||||
|
r26013 | # 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. | ||||
|
r39402 | if copytracing == 'heuristics': | ||
|
r34365 | # 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 | ||||
|
r34312 | if _isfullcopytraceable(repo, c1, base): | ||
|
r34289 | return _fullcopytracing(repo, c1, c2, base) | ||
|
r34180 | return _heuristicscopytracing(repo, c1, c2, base) | ||
|
r34080 | else: | ||
return _fullcopytracing(repo, c1, c2, base) | ||||
|
r26013 | |||
|
r34312 | def _isfullcopytraceable(repo, c1, base): | ||
|
r34365 | """ 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. | ||||
|
r34517 | |||
`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. | ||||
|
r34289 | """ | ||
|
r34312 | if c1.rev() is None: | ||
c1 = c1.p1() | ||||
|
r34365 | if c1.mutable() and base.mutable(): | ||
|
r34312 | sourcecommitlimit = repo.ui.configint('experimental', | ||
'copytrace.sourcecommitlimit') | ||||
commits = len(repo.revs('%d::%d', base.rev(), c1.rev())) | ||||
return commits < sourcecommitlimit | ||||
|
r34289 | return False | ||
|
r42408 | def _checksinglesidecopies(src, dsts1, m1, m2, mb, c2, base, | ||
copy, renamedelete): | ||||
if src not in m2: | ||||
# deleted on side 2 | ||||
if src not in m1: | ||||
# renamed on side 1, deleted on side 2 | ||||
renamedelete[src] = dsts1 | ||||
elif m2[src] != mb[src]: | ||||
if not _related(c2[src], base[src]): | ||||
return | ||||
# modified on side 2 | ||||
for dst in dsts1: | ||||
if dst not in m2: | ||||
# dst not added on side 2 (handle as regular | ||||
# "both created" case in manifestmerge otherwise) | ||||
copy[dst] = src | ||||
|
r34080 | def _fullcopytracing(repo, c1, c2, base): | ||
""" The full copytracing algorithm which finds all the new files that were | ||||
added from merge base up to the top commit and for each file it checks if | ||||
this file was copied from another file. | ||||
This is pretty slow when a lot of changesets are involved but will track all | ||||
the copies. | ||||
""" | ||||
|
r6274 | m1 = c1.manifest() | ||
m2 = c2.manifest() | ||||
|
r30186 | mb = base.manifest() | ||
|
r6274 | |||
|
r42408 | copies1 = pathcopies(base, c1) | ||
copies2 = pathcopies(base, c2) | ||||
inversecopies1 = {} | ||||
inversecopies2 = {} | ||||
for dst, src in copies1.items(): | ||||
inversecopies1.setdefault(src, []).append(dst) | ||||
for dst, src in copies2.items(): | ||||
inversecopies2.setdefault(src, []).append(dst) | ||||
copy = {} | ||||
diverge = {} | ||||
renamedelete = {} | ||||
allsources = set(inversecopies1) | set(inversecopies2) | ||||
for src in allsources: | ||||
dsts1 = inversecopies1.get(src) | ||||
dsts2 = inversecopies2.get(src) | ||||
if dsts1 and dsts2: | ||||
# copied/renamed on both sides | ||||
if src not in m1 and src not in m2: | ||||
# renamed on both sides | ||||
dsts1 = set(dsts1) | ||||
dsts2 = set(dsts2) | ||||
# If there's some overlap in the rename destinations, we | ||||
# consider it not divergent. For example, if side 1 copies 'a' | ||||
# to 'b' and 'c' and deletes 'a', and side 2 copies 'a' to 'c' | ||||
# and 'd' and deletes 'a'. | ||||
if dsts1 & dsts2: | ||||
for dst in (dsts1 & dsts2): | ||||
copy[dst] = src | ||||
else: | ||||
diverge[src] = sorted(dsts1 | dsts2) | ||||
elif src in m1 and src in m2: | ||||
# copied on both sides | ||||
dsts1 = set(dsts1) | ||||
dsts2 = set(dsts2) | ||||
for dst in (dsts1 & dsts2): | ||||
copy[dst] = src | ||||
# TODO: Handle cases where it was renamed on one side and copied | ||||
# on the other side | ||||
elif dsts1: | ||||
# copied/renamed only on side 1 | ||||
_checksinglesidecopies(src, dsts1, m1, m2, mb, c2, base, | ||||
copy, renamedelete) | ||||
elif dsts2: | ||||
# copied/renamed only on side 2 | ||||
_checksinglesidecopies(src, dsts2, m2, m1, mb, c1, base, | ||||
copy, renamedelete) | ||||
renamedeleteset = set() | ||||
divergeset = set() | ||||
|
r42410 | for dsts in diverge.values(): | ||
|
r42408 | divergeset.update(dsts) | ||
|
r42410 | for dsts in renamedelete.values(): | ||
|
r42408 | renamedeleteset.update(dsts) | ||
|
r6274 | |||
|
r26659 | # find interesting file sets from manifests | ||
|
r40002 | addedinm1 = m1.filesnotin(mb, repo.narrowmatch()) | ||
addedinm2 = m2.filesnotin(mb, repo.narrowmatch()) | ||||
|
r42409 | u1 = sorted(addedinm1 - addedinm2) | ||
u2 = sorted(addedinm2 - addedinm1) | ||||
header = " unmatched files in %s" | ||||
if u1: | ||||
repo.ui.debug("%s:\n %s\n" % (header % 'local', "\n ".join(u1))) | ||||
if u2: | ||||
repo.ui.debug("%s:\n %s\n" % (header % 'other', "\n ".join(u2))) | ||||
|
r6274 | |||
|
r42408 | fullcopy = copies1.copy() | ||
fullcopy.update(copies2) | ||||
|
r42342 | if not fullcopy: | ||
return copy, {}, diverge, renamedelete, {} | ||||
if repo.ui.debugflag: | ||||
|
r16795 | repo.ui.debug(" all copies found (* = to merge, ! = divergent, " | ||
"% = renamed and deleted):\n") | ||||
|
r18362 | for f in sorted(fullcopy): | ||
|
r6274 | note = "" | ||
|
r10282 | if f in copy: | ||
note += "*" | ||||
|
r26317 | if f in divergeset: | ||
|
r10282 | note += "!" | ||
|
r26658 | if f in renamedeleteset: | ||
|
r16795 | note += "%" | ||
|
r18135 | repo.ui.debug(" src: '%s' -> dst: '%s' %s\n" % (fullcopy[f], f, | ||
note)) | ||||
|
r26317 | del divergeset | ||
|
r6274 | |||
|
r9467 | repo.ui.debug(" checking for directory renames\n") | ||
|
r6274 | |||
# generate a directory move map | ||||
|
r16178 | d1, d2 = c1.dirs(), c2.dirs() | ||
|
r17055 | invalid = set() | ||
|
r6274 | dirmove = {} | ||
# examine each file copy for a potential directory move, which is | ||||
# when all the files in a directory are moved to a new directory | ||||
|
r7622 | for dst, src in fullcopy.iteritems(): | ||
|
r25282 | dsrc, ddst = pathutil.dirname(src), pathutil.dirname(dst) | ||
|
r6274 | if dsrc in invalid: | ||
# already seen to be uninteresting | ||||
continue | ||||
elif dsrc in d1 and ddst in d1: | ||||
# directory wasn't entirely moved locally | ||||
|
r39299 | invalid.add(dsrc) | ||
|
r6274 | elif dsrc in d2 and ddst in d2: | ||
# directory wasn't entirely moved remotely | ||||
|
r39299 | invalid.add(dsrc) | ||
elif dsrc in dirmove and dirmove[dsrc] != ddst: | ||||
|
r6274 | # files from the same directory moved to two different places | ||
|
r39299 | invalid.add(dsrc) | ||
|
r6274 | else: | ||
# looks good so far | ||||
|
r39299 | dirmove[dsrc] = ddst | ||
|
r6274 | |||
for i in invalid: | ||||
if i in dirmove: | ||||
del dirmove[i] | ||||
del d1, d2, invalid | ||||
if not dirmove: | ||||
|
r30581 | return copy, {}, diverge, renamedelete, {} | ||
|
r6274 | |||
|
r39299 | dirmove = {k + "/": v + "/" for k, v in dirmove.iteritems()} | ||
|
r6274 | for d in dirmove: | ||
|
r18135 | repo.ui.debug(" discovered dir src: '%s' -> dst: '%s'\n" % | ||
(d, dirmove[d])) | ||||
|
r6274 | |||
|
r30183 | movewithdir = {} | ||
|
r6274 | # check unaccounted nonoverlapping files against directory moves | ||
|
r42408 | for f in u1 + u2: | ||
|
r6274 | if f not in fullcopy: | ||
for d in dirmove: | ||||
if f.startswith(d): | ||||
# new file added in a directory that was moved, move it | ||||
|
r6425 | df = dirmove[d] + f[len(d):] | ||
|
r6426 | if df not in copy: | ||
|
r18134 | movewithdir[f] = df | ||
|
r18135 | repo.ui.debug((" pending file src: '%s' -> " | ||
"dst: '%s'\n") % (f, df)) | ||||
|
r6274 | break | ||
|
r30581 | return copy, movewithdir, diverge, renamedelete, dirmove | ||
|
r19178 | |||
|
r34180 | def _heuristicscopytracing(repo, c1, c2, base): | ||
""" Fast copytracing using filename heuristics | ||||
Assumes that moves or renames are of following two types: | ||||
1) Inside a directory only (same directory name but different filenames) | ||||
2) Move from one directory to another | ||||
(same filenames but different directory names) | ||||
Works only when there are no merge commits in the "source branch". | ||||
Source branch is commits from base up to c2 not including base. | ||||
If merge is involved it fallbacks to _fullcopytracing(). | ||||
Can be used by setting the following config: | ||||
[experimental] | ||||
copytrace = heuristics | ||||
|
r34847 | |||
In some cases the copy/move candidates found by heuristics can be very large | ||||
in number and that will make the algorithm slow. The number of possible | ||||
candidates to check can be limited by using the config | ||||
`experimental.copytrace.movecandidateslimit` which defaults to 100. | ||||
|
r34180 | """ | ||
if c1.rev() is None: | ||||
c1 = c1.p1() | ||||
if c2.rev() is None: | ||||
c2 = c2.p1() | ||||
copies = {} | ||||
changedfiles = set() | ||||
m1 = c1.manifest() | ||||
if not repo.revs('%d::%d', base.rev(), c2.rev()): | ||||
# If base is not in c2 branch, we switch to fullcopytracing | ||||
repo.ui.debug("switching to full copytracing as base is not " | ||||
"an ancestor of c2\n") | ||||
return _fullcopytracing(repo, c1, c2, base) | ||||
ctx = c2 | ||||
while ctx != base: | ||||
if len(ctx.parents()) == 2: | ||||
# To keep things simple let's not handle merges | ||||
repo.ui.debug("switching to full copytracing because of merges\n") | ||||
return _fullcopytracing(repo, c1, c2, base) | ||||
changedfiles.update(ctx.files()) | ||||
ctx = ctx.p1() | ||||
cp = _forwardcopies(base, c2) | ||||
for dst, src in cp.iteritems(): | ||||
if src in m1: | ||||
copies[dst] = src | ||||
# file is missing if it isn't present in the destination, but is present in | ||||
# the base and present in the source. | ||||
# Presence in the base is important to exclude added files, presence in the | ||||
# source is important to exclude removed files. | ||||
|
r36364 | filt = lambda f: f not in m1 and f in base and f in c2 | ||
missingfiles = [f for f in changedfiles if filt(f)] | ||||
|
r34180 | |||
if missingfiles: | ||||
basenametofilename = collections.defaultdict(list) | ||||
dirnametofilename = collections.defaultdict(list) | ||||
for f in m1.filesnotin(base.manifest()): | ||||
basename = os.path.basename(f) | ||||
dirname = os.path.dirname(f) | ||||
basenametofilename[basename].append(f) | ||||
dirnametofilename[dirname].append(f) | ||||
for f in missingfiles: | ||||
basename = os.path.basename(f) | ||||
dirname = os.path.dirname(f) | ||||
samebasename = basenametofilename[basename] | ||||
samedirname = dirnametofilename[dirname] | ||||
movecandidates = samebasename + samedirname | ||||
# f is guaranteed to be present in c2, that's why | ||||
# c2.filectx(f) won't fail | ||||
f2 = c2.filectx(f) | ||||
|
r34847 | # we can have a lot of candidates which can slow down the heuristics | ||
# config value to limit the number of candidates moves to check | ||||
maxcandidates = repo.ui.configint('experimental', | ||||
'copytrace.movecandidateslimit') | ||||
if len(movecandidates) > maxcandidates: | ||||
repo.ui.status(_("skipping copytracing for '%s', more " | ||||
"candidates than the limit: %d\n") | ||||
% (f, len(movecandidates))) | ||||
continue | ||||
|
r34180 | for candidate in movecandidates: | ||
f1 = c1.filectx(candidate) | ||||
|
r37410 | if _related(f1, f2): | ||
|
r34180 | # if there are a few related copies then we'll merge | ||
# changes into all of them. This matches the behaviour | ||||
# of upstream copytracing | ||||
copies[candidate] = f | ||||
return copies, {}, {}, {}, {} | ||||
|
r37410 | def _related(f1, f2): | ||
|
r30138 | """return True if f1 and f2 filectx have a common ancestor | ||
Walk back to common ancestor to see if the two files originate | ||||
from the same file. Since workingfilectx's rev() is None it messes | ||||
up the integer comparison logic, hence the pre-step check for | ||||
None (f1 and f2 can only be workingfilectx's initially). | ||||
""" | ||||
if f1 == f2: | ||||
|
r41873 | return True # a match | ||
|
r30138 | |||
g1, g2 = f1.ancestors(), f2.ancestors() | ||||
try: | ||||
f1r, f2r = f1.linkrev(), f2.linkrev() | ||||
if f1r is None: | ||||
f1 = next(g1) | ||||
if f2r is None: | ||||
f2 = next(g2) | ||||
while True: | ||||
f1r, f2r = f1.linkrev(), f2.linkrev() | ||||
if f1r > f2r: | ||||
f1 = next(g1) | ||||
elif f2r > f1r: | ||||
f2 = next(g2) | ||||
|
r37410 | else: # f1 and f2 point to files in the same linkrev | ||
return f1 == f2 # true if they point to the same file | ||||
|
r30138 | except StopIteration: | ||
return False | ||||
|
r34788 | def duplicatecopies(repo, wctx, rev, fromrev, skiprev=None): | ||
|
r35422 | """reproduce copies from fromrev to rev in the dirstate | ||
|
r22901 | |||
If skiprev is specified, it's a revision that should be used to | ||||
filter copy records. Any copies that occur between fromrev and | ||||
skiprev will not be duplicated, even if they appear in the set of | ||||
copies between fromrev and rev. | ||||
|
r35422 | """ | ||
|
r22901 | exclude = {} | ||
|
r39402 | ctraceconfig = repo.ui.config('experimental', 'copytrace') | ||
bctrace = stringutil.parsebool(ctraceconfig) | ||||
|
r26013 | if (skiprev is not None and | ||
|
r39402 | (ctraceconfig == 'heuristics' or bctrace or bctrace is None)): | ||
|
r34079 | # copytrace='off' skips this line, but not the entire function because | ||
|
r26013 | # the line below is O(size of the repo) during a rebase, while the rest | ||
# of the function is much faster (and is required for carrying copy | ||||
# metadata across the rebase anyway). | ||||
|
r22901 | exclude = pathcopies(repo[fromrev], repo[skiprev]) | ||
for dst, src in pathcopies(repo[fromrev], repo[rev]).iteritems(): | ||||
if dst in exclude: | ||||
continue | ||||
|
r42509 | if dst in wctx: | ||
wctx[dst].markcopied(src) | ||||