##// END OF EJS Templates
merge with stable...
merge with stable This should correct an earlier couple of bad merges (5433856b2558 and 596960a4ad0d, now pruned) that accidentally brought in a change that had been marked obsolete (244ac996a821).

File last commit:

r20641:3db9e798 default
r20860:81d6dc8c merge default
Show More
copies.py
424 lines | 13.4 KiB | text/x-python | PythonLexer
Matt Mackall
copies: move findcopies code to its own module...
r6274 # copies.py - copy detection for Mercurial
#
# Copyright 2008 Matt Mackall <mpm@selenic.com>
#
Martin Geisler
updated license to be explicit about GPL version 2
r8225 # This software may be used and distributed according to the terms of the
Matt Mackall
Update license to GPLv2+
r10263 # GNU General Public License version 2 or any later version.
Matt Mackall
copies: move findcopies code to its own module...
r6274
Simon Heimberg
separate import lines from mercurial and general python modules
r8312 import util
import heapq
Matt Mackall
copies: move findcopies code to its own module...
r6274
def _nonoverlap(d1, d2, d3):
"Return list of elements in d1 not in d2 or d3"
Matt Mackall
replace util.sort with sorted built-in...
r8209 return sorted([d for d in d1 if d not in d3 and d not in d2])
Matt Mackall
copies: move findcopies code to its own module...
r6274
def _dirname(f):
s = f.rfind("/")
if s == -1:
return ""
return f[:s]
Matt Mackall
copies: refactor symmetricdifference as _findlimit...
r6431 def _findlimit(repo, a, b):
Patrick Mezard
copies: don't report copies with unrelated branch
r10179 """Find the earliest revision that's an ancestor of a or b but not both,
None if no such revision exists.
"""
Matt Mackall
symmetricdifference: move back to copies...
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
Matt Mackall
copies: refactor symmetricdifference as _findlimit...
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
Matt Mackall
copies: teach symmetric difference about working revisions...
r6430
cl = repo.changelog
Matt Mackall
add __len__ and __iter__ methods to repo and revlog
r6750 working = len(cl) # pseudo rev for the working directory
Matt Mackall
copies: teach symmetric difference about working revisions...
r6430 if a is None:
a = working
if b is None:
b = working
Matt Mackall
symmetricdifference: move back to copies...
r6429
side = {a: -1, b: 1}
visit = [-a, -b]
heapq.heapify(visit)
interesting = len(visit)
Patrick Mezard
copies: don't report copies with unrelated branch
r10179 hascommonancestor = False
Matt Mackall
copies: refactor symmetricdifference as _findlimit...
r6431 limit = working
Matt Mackall
symmetricdifference: move back to copies...
r6429
while interesting:
r = -heapq.heappop(visit)
Matt Mackall
copies: teach symmetric difference about working revisions...
r6430 if r == working:
parents = [cl.rev(p) for p in repo.dirstate.parents()]
else:
parents = cl.parentrevs(r)
for p in parents:
Patrick Mezard
copies: don't report copies with unrelated branch
r10179 if p < 0:
continue
Matt Mackall
symmetricdifference: move back to copies...
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
Patrick Mezard
copies: don't report copies with unrelated branch
r10179 hascommonancestor = True
Matt Mackall
copies: teach symmetric difference about working revisions...
r6430 if side[r]:
Matt Mackall
copies: refactor symmetricdifference as _findlimit...
r6431 limit = r # lowest rev visited
Matt Mackall
copies: teach symmetric difference about working revisions...
r6430 interesting -= 1
Patrick Mezard
copies: don't report copies with unrelated branch
r10179
if not hascommonancestor:
return None
Matt Mackall
copies: refactor symmetricdifference as _findlimit...
r6431 return limit
Matt Mackall
symmetricdifference: move back to copies...
r6429
Matt Mackall
copies: rewrite copy detection for non-merge users...
r15775 def _chain(src, dst, a, b):
'''chain two sets of copies a->b'''
t = a.copy()
for k, v in b.iteritems():
if v in t:
# found a chain
if t[v] != k:
# file wasn't renamed back to itself
t[k] = t[v]
if v not in dst:
# chain was a rename, not a copy
del t[v]
if v in src:
# file is a copy of an existing file
t[k] = v
Matt Mackall
copies: eliminate criss-crosses when chaining...
r15976
# remove criss-crossed copies
for k, v in t.items():
if k in src and v in dst:
del t[k]
Matt Mackall
copies: rewrite copy detection for non-merge users...
r15775 return t
Mads Kiilerich
diff: search beyond ancestor when detecting renames...
r20294 def _tracefile(fctx, am, limit=-1):
'''return file context that is the ancestor of fctx present in ancestor
manifest am, stopping after the first ancestor lower than limit'''
Matt Mackall
copies: rewrite copy detection for non-merge users...
r15775
for f in fctx.ancestors():
if am.get(f.path(), None) == f.filenode():
return f
Mads Kiilerich
diff: search beyond ancestor when detecting renames...
r20294 if f.rev() < limit:
Matt Mackall
copies: rewrite copy detection for non-merge users...
r15775 return None
def _dirstatecopies(d):
ds = d._repo.dirstate
c = ds.copies().copy()
for k in c.keys():
if ds[k] not in 'anm':
del c[k]
return c
def _forwardcopies(a, b):
'''find {dst@b: src@a} copy mapping where a is an ancestor of b'''
# check for working copy
w = None
if b.rev() is None:
w = b
b = w.p1()
if a == b:
# short-circuit to avoid issues with merge states
return _dirstatecopies(w)
Mads Kiilerich
diff: search beyond ancestor when detecting renames...
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
limit = _findlimit(a._repo, a.rev(), b.rev())
if limit is None:
limit = -1
am = a.manifest()
Matt Mackall
copies: rewrite copy detection for non-merge users...
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 = {}
Siddharth Agarwal
copies._forwardcopies: use set operations to find missing files...
r18878 missing = set(b.manifest().iterkeys())
missing.difference_update(a.manifest().iterkeys())
for f in missing:
Mads Kiilerich
diff: search beyond ancestor when detecting renames...
r20294 ofctx = _tracefile(b[f], am, limit)
Siddharth Agarwal
copies._forwardcopies: use set operations to find missing files...
r18878 if ofctx:
cm[f] = ofctx.path()
Matt Mackall
copies: rewrite copy detection for non-merge users...
r15775
# combine copies from dirstate if necessary
if w is not None:
cm = _chain(a, w, cm, _dirstatecopies(w))
return cm
Siddharth Agarwal
copies: do not track backward copies, only renames (issue3739)...
r18136 def _backwardrenames(a, b):
# 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.
Matt Mackall
copies: rewrite copy detection for non-merge users...
r15775 f = _forwardcopies(b, a)
r = {}
Mads Kiilerich
copies: make the loss in _backwardcopies more stable...
r18355 for k, v in sorted(f.iteritems()):
Siddharth Agarwal
copies: do not track backward copies, only renames (issue3739)...
r18136 # remove copies
if v in a:
continue
Matt Mackall
copies: rewrite copy detection for non-merge users...
r15775 r[v] = k
return r
def pathcopies(x, y):
'''find {dst@y: src@x} copy mapping for directed compare'''
if x == y or not x or not y:
return {}
a = y.ancestor(x)
if a == x:
return _forwardcopies(x, y)
if a == y:
Siddharth Agarwal
copies: do not track backward copies, only renames (issue3739)...
r18136 return _backwardrenames(x, y)
return _chain(x, y, _backwardrenames(x, a), _forwardcopies(a, y))
Matt Mackall
copies: split the copies api for "normal" and merge cases (API)
r15774
Matt Mackall
copies: remove checkdirs options...
r16169 def mergecopies(repo, c1, c2, ca):
Matt Mackall
copies: move findcopies code to its own module...
r6274 """
Matt Mackall
copies: add docstring for mergecopies
r16168 Find moves and copies between context c1 and c2 that are relevant
for merging.
Siddharth Agarwal
copies: separate moves via directory renames from explicit copies...
r18134 Returns four dicts: "copy", "movewithdir", "diverge", and
"renamedelete".
Matt Mackall
copies: add docstring for mergecopies
r16168
Matt Mackall
copies: fix mergecopies doc mapping direction
r16177 "copy" is a mapping from destination name -> source name,
Matt Mackall
copies: add docstring for mergecopies
r16168 where source is in c1 and destination is in c2 or vice-versa.
Siddharth Agarwal
copies: separate moves via directory renames from explicit copies...
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.
Matt Mackall
copies: add docstring for mergecopies
r16168 "diverge" is a mapping of source name -> list of destination names
for divergent renames.
Thomas Arendsen Hein
merge: warn about file deleted in one branch and renamed in other (issue3074)...
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.
Matt Mackall
copies: move findcopies code to its own module...
r6274 """
# avoid silly behavior for update from empty dir
Matt Mackall
copies: teach symmetric difference about working revisions...
r6430 if not c1 or not c2 or c1 == c2:
Siddharth Agarwal
copies: separate moves via directory renames from explicit copies...
r18134 return {}, {}, {}, {}
Matt Mackall
copies: move findcopies code to its own module...
r6274
Matt Mackall
copies: teach copies about dirstate.copies...
r6646 # avoid silly behavior for parent -> working dir
Matt Mackall
misc: replace .parents()[0] with p1()
r13878 if c2.node() is None and c1.node() == repo.dirstate.p1():
Siddharth Agarwal
copies: separate moves via directory renames from explicit copies...
r18134 return repo.dirstate.copies(), {}, {}, {}
Matt Mackall
copies: teach copies about dirstate.copies...
r6646
Matt Mackall
copies: refactor symmetricdifference as _findlimit...
r6431 limit = _findlimit(repo, c1.rev(), c2.rev())
Patrick Mezard
copies: don't report copies with unrelated branch
r10179 if limit is None:
# no common ancestor, no copies
Siddharth Agarwal
copies: separate moves via directory renames from explicit copies...
r18134 return {}, {}, {}, {}
Matt Mackall
copies: move findcopies code to its own module...
r6274 m1 = c1.manifest()
m2 = c2.manifest()
ma = ca.manifest()
def makectx(f, n):
if len(n) != 20: # in a working context?
if c1.rev() is None:
return c1.filectx(f)
return c2.filectx(f)
return repo.filectx(f, fileid=n)
Matt Mackall
fix memory usage of revlog caches by limiting cache size [issue1639]
r9097 ctx = util.lrucachefunc(makectx)
Matt Mackall
copies: move findcopies code to its own module...
r6274 copy = {}
Siddharth Agarwal
copies: separate moves via directory renames from explicit copies...
r18134 movewithdir = {}
Matt Mackall
copies: move findcopies code to its own module...
r6274 fullcopy = {}
diverge = {}
Durham Goode
copies: refactor checkcopies() into a top level method...
r19178 def _checkcopies(f, m1, m2):
checkcopies(ctx, f, m1, m2, ca, limit, diverge, copy, fullcopy)
Matt Mackall
copies: move findcopies code to its own module...
r6274
Martin Geisler
do not attempt to translate ui.debug output
r9467 repo.ui.debug(" searching for copies back to rev %d\n" % limit)
Matt Mackall
copies: move findcopies code to its own module...
r6274
u1 = _nonoverlap(m1, m2, ma)
u2 = _nonoverlap(m2, m1, ma)
if u1:
Martin Geisler
do not attempt to translate ui.debug output
r9467 repo.ui.debug(" unmatched files in local:\n %s\n"
Matt Mackall
copies: move findcopies code to its own module...
r6274 % "\n ".join(u1))
if u2:
Martin Geisler
do not attempt to translate ui.debug output
r9467 repo.ui.debug(" unmatched files in other:\n %s\n"
Matt Mackall
copies: move findcopies code to its own module...
r6274 % "\n ".join(u2))
for f in u1:
Durham Goode
copies: refactor checkcopies() into a top level method...
r19178 _checkcopies(f, m1, m2)
Matt Mackall
copies: move findcopies code to its own module...
r6274 for f in u2:
Durham Goode
copies: refactor checkcopies() into a top level method...
r19178 _checkcopies(f, m2, m1)
Matt Mackall
copies: move findcopies code to its own module...
r6274
Thomas Arendsen Hein
merge: warn about file deleted in one branch and renamed in other (issue3074)...
r16794 renamedelete = {}
Thomas Arendsen Hein
merge: show renamed on one and deleted on the other side in debug output
r16795 renamedelete2 = set()
Martin Geisler
replace set-like dictionaries with real sets...
r8152 diverge2 = set()
Matt Mackall
copies: move findcopies code to its own module...
r6274 for of, fl in diverge.items():
Thomas Arendsen Hein
merge: do not warn about copy and rename in the same transaction (issue2113)
r16792 if len(fl) == 1 or of in c1 or of in c2:
Dan Villiom Podlaski Christiansen
copies: don't detect copies as "divergent renames"...
r12683 del diverge[of] # not actually divergent, or not a rename
Thomas Arendsen Hein
merge: warn about file deleted in one branch and renamed in other (issue3074)...
r16794 if of not in c1 and of not in c2:
# renamed on one side, deleted on the other side, but filter
# out files that have been renamed and then deleted
renamedelete[of] = [f for f in fl if f in c1 or f in c2]
Thomas Arendsen Hein
merge: show renamed on one and deleted on the other side in debug output
r16795 renamedelete2.update(fl) # reverse map for below
Matt Mackall
copies: move findcopies code to its own module...
r6274 else:
Martin Geisler
replace set-like dictionaries with real sets...
r8152 diverge2.update(fl) # reverse map for below
Matt Mackall
copies: move findcopies code to its own module...
r6274
Mads Kiilerich
copies: when both sides made the same copy, report it as a copy...
r20641 bothnew = sorted([d for d in m1 if d in m2 and d not in ma])
if bothnew:
repo.ui.debug(" unmatched files new in both:\n %s\n"
% "\n ".join(bothnew))
bothdiverge, _copy, _fullcopy = {}, {}, {}
for f in bothnew:
checkcopies(ctx, f, m1, m2, ca, limit, bothdiverge, _copy, _fullcopy)
checkcopies(ctx, f, m2, m1, ca, limit, bothdiverge, _copy, _fullcopy)
for of, fl in bothdiverge.items():
if len(fl) == 2 and fl[0] == fl[1]:
copy[fl[0]] = of # not actually divergent, just matching renames
Matt Mackall
copies: move findcopies code to its own module...
r6274 if fullcopy:
Thomas Arendsen Hein
merge: show renamed on one and deleted on the other side in debug output
r16795 repo.ui.debug(" all copies found (* = to merge, ! = divergent, "
"% = renamed and deleted):\n")
Mads Kiilerich
copies: report found copies sorted
r18362 for f in sorted(fullcopy):
Matt Mackall
copies: move findcopies code to its own module...
r6274 note = ""
Matt Mackall
many, many trivial check-code fixups
r10282 if f in copy:
note += "*"
if f in diverge2:
note += "!"
Thomas Arendsen Hein
merge: show renamed on one and deleted on the other side in debug output
r16795 if f in renamedelete2:
note += "%"
Siddharth Agarwal
copies: make debug messages more sensible...
r18135 repo.ui.debug(" src: '%s' -> dst: '%s' %s\n" % (fullcopy[f], f,
note))
Matt Mackall
copies: move findcopies code to its own module...
r6274 del diverge2
Matt Mackall
copies: remove checkdirs options...
r16169 if not fullcopy:
Siddharth Agarwal
copies: separate moves via directory renames from explicit copies...
r18134 return copy, movewithdir, diverge, renamedelete
Matt Mackall
copies: move findcopies code to its own module...
r6274
Martin Geisler
do not attempt to translate ui.debug output
r9467 repo.ui.debug(" checking for directory renames\n")
Matt Mackall
copies: move findcopies code to its own module...
r6274
# generate a directory move map
Matt Mackall
copies: use ctx.dirs() for directory rename detection
r16178 d1, d2 = c1.dirs(), c2.dirs()
Bryan O'Sullivan
scmutil: use new dirs class in dirstate and context...
r18899 d1.addpath('/')
d2.addpath('/')
Matt Mackall
copies: re-include root directory in directory rename detection (issue3511)
r17055 invalid = set()
Matt Mackall
copies: move findcopies code to its own module...
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
Dirkjan Ochtman
use dict.iteritems() rather than dict.items()...
r7622 for dst, src in fullcopy.iteritems():
Matt Mackall
copies: move findcopies code to its own module...
r6274 dsrc, ddst = _dirname(src), _dirname(dst)
if dsrc in invalid:
# already seen to be uninteresting
continue
elif dsrc in d1 and ddst in d1:
# directory wasn't entirely moved locally
Benoit Boissinot
copies: use set instead of dict
r8468 invalid.add(dsrc)
Matt Mackall
copies: move findcopies code to its own module...
r6274 elif dsrc in d2 and ddst in d2:
# directory wasn't entirely moved remotely
Benoit Boissinot
copies: use set instead of dict
r8468 invalid.add(dsrc)
Matt Mackall
copies: move findcopies code to its own module...
r6274 elif dsrc in dirmove and dirmove[dsrc] != ddst:
# files from the same directory moved to two different places
Benoit Boissinot
copies: use set instead of dict
r8468 invalid.add(dsrc)
Matt Mackall
copies: move findcopies code to its own module...
r6274 else:
# looks good so far
dirmove[dsrc + "/"] = ddst + "/"
for i in invalid:
if i in dirmove:
del dirmove[i]
del d1, d2, invalid
if not dirmove:
Siddharth Agarwal
copies: separate moves via directory renames from explicit copies...
r18134 return copy, movewithdir, diverge, renamedelete
Matt Mackall
copies: move findcopies code to its own module...
r6274
for d in dirmove:
Siddharth Agarwal
copies: make debug messages more sensible...
r18135 repo.ui.debug(" discovered dir src: '%s' -> dst: '%s'\n" %
(d, dirmove[d]))
Matt Mackall
copies: move findcopies code to its own module...
r6274
# check unaccounted nonoverlapping files against directory moves
for f in u1 + u2:
if f not in fullcopy:
for d in dirmove:
if f.startswith(d):
# new file added in a directory that was moved, move it
Matt Mackall
copies: skip directory rename checks when not merging...
r6425 df = dirmove[d] + f[len(d):]
Matt Mackall
copies: don't double-detect items in the directory copy check
r6426 if df not in copy:
Siddharth Agarwal
copies: separate moves via directory renames from explicit copies...
r18134 movewithdir[f] = df
Siddharth Agarwal
copies: make debug messages more sensible...
r18135 repo.ui.debug((" pending file src: '%s' -> "
"dst: '%s'\n") % (f, df))
Matt Mackall
copies: move findcopies code to its own module...
r6274 break
Siddharth Agarwal
copies: separate moves via directory renames from explicit copies...
r18134 return copy, movewithdir, diverge, renamedelete
Durham Goode
copies: refactor checkcopies() into a top level method...
r19178
def checkcopies(ctx, f, m1, m2, ca, limit, diverge, copy, fullcopy):
"""
check possible copies of f from m1 to m2
ctx = function accepting (filename, node) that returns a filectx.
f = the filename to check
m1 = the source manifest
m2 = the destination manifest
ca = the changectx of the common ancestor
limit = the rev number to not search beyond
diverge = record all diverges in this dict
copy = record all non-divergent copies in this dict
fullcopy = record all copies in this dict
"""
ma = ca.manifest()
def _related(f1, f2, limit):
# 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:
return f1 # a match
g1, g2 = f1.ancestors(), f2.ancestors()
try:
f1r, f2r = f1.rev(), f2.rev()
if f1r is None:
f1 = g1.next()
if f2r is None:
f2 = g2.next()
while True:
f1r, f2r = f1.rev(), f2.rev()
if f1r > f2r:
f1 = g1.next()
elif f2r > f1r:
f2 = g2.next()
elif f1 == f2:
return f1 # a match
elif f1r == f2r or f1r < limit or f2r < limit:
return False # copy no longer relevant
except StopIteration:
return False
of = None
seen = set([f])
for oc in ctx(f, m1[f]).ancestors():
ocr = oc.rev()
of = oc.path()
if of in seen:
# check limit late - grab last rename before
if ocr < limit:
break
continue
seen.add(of)
fullcopy[f] = of # remember for dir rename detection
if of not in m2:
continue # no match, keep looking
if m2[of] == ma.get(of):
break # no merge needed, quit early
c2 = ctx(of, m2[of])
cr = _related(oc, c2, ca.rev())
if cr and (of == f or of == c2.path()): # non-divergent
copy[f] = of
of = None
break
if of in ma:
diverge.setdefault(of, []).append(f)