( )⚙ D6418 copies: split up _chain() in naive chaining and filtering steps

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6418

copies: split up _chain() in naive chaining and filtering steps
ClosedPublic

Authored by martinvonz on May 21 2019, 8:32 PM.

Details

Reviewers
pulkit
Group Reviewers
hg-reviewers
Commits
rHGf3d06d37e194: copies: split up _chain() in naive chaining and filtering steps
Summary

The function now has two clearly defined steps. The first step is the
actual chaining. This step is very cheap. The second step is filtering
out invalid copies. This step is expensive. For changeset-centric copy
tracing, I want to do the filtering step only at the end. This patch
prepares for that.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Revision Contents
Changeset List

PathPackages
Mmercurial/copies.py (54 lines)

Diff 15263

mercurial/copies.py

# o 0 a0 # o 0 a0
# #
# When _findlimit is called, a and b are revs 3 and 0, so limit will be 2, # 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 # 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. # 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. # This only occurs when a is a descendent of b or visa-versa.
return min(limit, a, b) return min(limit, a, b)
def _chain(src, dst, a, b): def _chainandfilter(src, dst, a, b):
"""chain two sets of copies 'a' and '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 # 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 # 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 # 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 # where a file existed in 'src' and remained under that name in 'mid' and
# then was renamed between 'mid' and 'dst'. # then was renamed between 'mid' and 'dst'.
# #
# case src mid dst result # case src mid dst result
# 1 x y - - # 1 x y - -
# 2 x y y x->y # 2 x y y x->y
# 3 x y x - # 3 x y x -
# 4 x y z x->z # 4 x y z x->z
# 5 - x y - # 5 - x y -
# 6 x x y 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().
# Initialize result ('t') from 'a'. This catches cases 1 & 2. We'll remove t = _chain(a, b)
# case 1 later. We'll also catch cases 3 & 4 here. Case 4 will be _filter(src, dst, t)
# overwritten later, and case 3 will be removed later. return t
t = a.copy()
for k, v in b.iteritems():
if v in t:
# Found a chain, i.e. cases 3 & 4. We'll remove case 3 later.
t[k] = t[v]
else:
# Renamed only in 'b', i.e. cases 5 & 6. We'll remove case 5 later.
t[k] = v
def _filter(src, dst, t):
"""filters out invalid copies after chaining"""
for k, v in list(t.items()): for k, v in list(t.items()):
# remove copies from files that didn't exist, i.e. case 5 # remove copies from files that didn't exist
if v not in src: if v not in src:
del t[k] del t[k]
# remove criss-crossed copies, i.e. case 3 # remove criss-crossed copies
elif k in src and v in dst: elif k in src and v in dst:
del t[k] del t[k]
# remove copies to files that were then removed, i.e. case 1 # remove copies to files that were then removed
# and file 'y' in cases 3 & 4 (in case of rename)
elif k not in dst: elif k not in dst:
del t[k] 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 return t
def _tracefile(fctx, am, limit): def _tracefile(fctx, am, limit):
"""return file context that is the ancestor of fctx present in ancestor """return file context that is the ancestor of fctx present in ancestor
manifest am, stopping after the first ancestor lower than limit""" manifest am, stopping after the first ancestor lower than limit"""
for f in fctx.ancestors(): for f in fctx.ancestors():
if am.get(f.path(), None) == f.filenode(): if am.get(f.path(), None) == f.filenode():
childcopies = childctx.p1copies() childcopies = childctx.p1copies()
else: else:
assert r == childctx.p2().rev() assert r == childctx.p2().rev()
parent = 2 parent = 2
childcopies = childctx.p2copies() childcopies = childctx.p2copies()
if not match.always(): if not match.always():
childcopies = {dst: src for dst, src in childcopies.items() childcopies = {dst: src for dst, src in childcopies.items()
if match(dst)} if match(dst)}
childcopies = _chain(a, childctx, copies, childcopies) childcopies = _chainandfilter(a, childctx, copies, childcopies)
heapq.heappush(work, (c, parent, childcopies)) heapq.heappush(work, (c, parent, childcopies))
assert False assert False
def _forwardcopies(a, b, match=None): def _forwardcopies(a, b, match=None):
"""find {dst@b: src@a} copy mapping where a is an ancestor of b""" """find {dst@b: src@a} copy mapping where a is an ancestor of b"""
match = a.repo().narrowmatch(match) match = a.repo().narrowmatch(match)
# check for working copy # check for working copy
if b.rev() is None: if b.rev() is None:
if a == b.p1(): if a == b.p1():
# short-circuit to avoid issues with merge states # short-circuit to avoid issues with merge states
return _dirstatecopies(b._repo, match) return _dirstatecopies(b._repo, match)
cm = _committedforwardcopies(a, b.p1(), match) cm = _committedforwardcopies(a, b.p1(), match)
# combine copies from dirstate if necessary # combine copies from dirstate if necessary
return _chain(a, b, cm, _dirstatecopies(b._repo, match)) return _chainandfilter(a, b, cm, _dirstatecopies(b._repo, match))
return _committedforwardcopies(a, b, match) return _committedforwardcopies(a, b, match)
def _backwardrenames(a, b, match): def _backwardrenames(a, b, match):
if a._repo.ui.config('experimental', 'copytrace') == 'off': if a._repo.ui.config('experimental', 'copytrace') == 'off':
return {} return {}
# Even though we're not taking copies into account, 1:n rename situations # 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 # can still exist (e.g. hg cp a b; hg mv a c). In those cases we
repo.ui.debug('debug.copies: search mode: forward\n') repo.ui.debug('debug.copies: search mode: forward\n')
return _forwardcopies(x, y, match=match) return _forwardcopies(x, y, match=match)
if a == y: if a == y:
if debug: if debug:
repo.ui.debug('debug.copies: search mode: backward\n') repo.ui.debug('debug.copies: search mode: backward\n')
return _backwardrenames(x, y, match=match) return _backwardrenames(x, y, match=match)
if debug: if debug:
repo.ui.debug('debug.copies: search mode: combined\n') repo.ui.debug('debug.copies: search mode: combined\n')
return _chain(x, y, _backwardrenames(x, a, match=match), return _chainandfilter(x, y, _backwardrenames(x, a, match=match),
_forwardcopies(a, y, match=match)) _forwardcopies(a, y, match=match))
def mergecopies(repo, c1, c2, base): def mergecopies(repo, c1, c2, base):
""" """
Finds moves and copies between context c1 and c2 that are relevant for Finds moves and copies between context c1 and c2 that are relevant for
merging. 'base' will be used as the merge base. merging. 'base' will be used as the merge base.
Copytracing is used in commands like rebase, merge, unshelve, etc to merge 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. files that were moved/ copied in one merge parent and modified in another.