Mercurial > hg
view mercurial/copies.py @ 16719:e7bf09acd410
localrepo: add branchtip() method for faster single-branch lookups
For the PyPy repo with 744 branches and 843 branch heads, this brings
hg log -r default over NFS from:
CallCount Recursive Total(ms) Inline(ms) module:lineno(function)
3249 0 1.3222 1.3222 <open>
3244 0 0.6211 0.6211 <method 'close' of 'file' objects>
3243 0 0.0800 0.0800 <method 'read' of 'file' objects>
3241 0 0.0660 0.0660 <method 'seek' of 'file' objects>
3905 0 0.0476 0.0476 <zlib.decompress>
3281 0 2.6756 0.0472 mercurial.changelog:182(read)
+3281 0 2.5256 0.0453 +mercurial.revlog:881(revision)
+3276 0 0.0389 0.0196 +mercurial.changelog:28(decodeextra)
+6562 0 0.0123 0.0123 +<method 'split' of 'str' objects>
+6562 0 0.0408 0.0073 +mercurial.encoding:61(tolocal)
+3281 0 0.0054 0.0054 +<method 'index' of 'str' objects>
3241 0 2.2464 0.0456 mercurial.revlog:818(_loadchunk)
+3241 0 0.6205 0.6205 +<method 'close' of 'file' objects>
+3241 0 0.0765 0.0765 +<method 'read' of 'file' objects>
+3241 0 0.0660 0.0660 +<method 'seek' of 'file' objects>
+3241 0 1.4209 0.0135 +mercurial.store:374(__call__)
+3241 0 0.0122 0.0107 +mercurial.revlog:810(_addchunk)
3281 0 2.5256 0.0453 mercurial.revlog:881(revision)
+3280 0 0.0175 0.0175 +mercurial.revlog:305(rev)
+3281 0 2.2819 0.0119 +mercurial.revlog:847(_chunkraw)
+3281 0 0.0603 0.0083 +mercurial.revlog:945(_checkhash)
+3281 0 0.0051 0.0051 +mercurial.revlog:349(flags)
+3281 0 0.0040 0.0040 +<mercurial.mpatch.patches>
13682 0 0.0479 0.0248 <method 'decode' of 'str' objects>
+7418 0 0.0228 0.0076 +encodings.utf_8:15(decode)
+1 0 0.0003 0.0000 +encodings:71(search_function)
3248 0 1.3995 0.0246 mercurial.scmutil:218(__call__)
+3248 0 1.3222 1.3222 +<open>
+3248 0 0.0235 0.0184 +os.path:80(split)
+3248 0 0.0084 0.0068 +mercurial.scmutil:92(__call__)
Time: real 2.750 secs (user 0.680+0.000 sys 0.360+0.000)
down to:
CallCount Recursive Total(ms) Inline(ms) module:lineno(function)
55 31 0.0197 0.0163 <__import__>
+1 0 0.0006 0.0002 +mercurial.context:8(<module>)
+1 0 0.0042 0.0001 +mercurial.revlog:12(<module>)
+1 0 0.0002 0.0001 +mercurial.match:8(<module>)
+1 0 0.0003 0.0001 +mercurial.dirstate:7(<module>)
+1 0 0.0057 0.0001 +mercurial.changelog:8(<module>)
1 0 0.0117 0.0032 mercurial.localrepo:525(_readbranchcache)
+844 0 0.0015 0.0015 +<binascii.unhexlify>
+845 0 0.0010 0.0010 +<method 'split' of 'str' objects>
+843 0 0.0045 0.0009 +mercurial.encoding:61(tolocal)
+843 0 0.0004 0.0004 +<method 'setdefault' of 'dict' objects>
+1 0 0.0003 0.0003 +<method 'close' of 'file' objects>
3 0 0.0029 0.0029 <method 'read' of 'file' objects>
9 0 0.0018 0.0018 <open>
990 0 0.0017 0.0017 <binascii.unhexlify>
53 0 0.0016 0.0016 mercurial.demandimport:43(__init__)
862 0 0.0015 0.0015 <_codecs.utf_8_decode>
862 0 0.0037 0.0014 <method 'decode' of 'str' objects>
+862 0 0.0023 0.0008 +encodings.utf_8:15(decode)
981 0 0.0011 0.0011 <method 'split' of 'str' objects>
861 0 0.0046 0.0009 mercurial.encoding:61(tolocal)
+861 0 0.0037 0.0014 +<method 'decode' of 'str' objects>
862 0 0.0023 0.0008 encodings.utf_8:15(decode)
+862 0 0.0015 0.0015 +<_codecs.utf_8_decode>
4 0 0.0008 0.0008 <method 'close' of 'file' objects>
179 154 0.0202 0.0004 mercurial.demandimport:83(__getattribute__)
+36 11 0.0199 0.0003 +mercurial.demandimport:55(_load)
+72 0 0.0001 0.0001 +mercurial.demandimport:83(__getattribute__)
+36 0 0.0000 0.0000 +<getattr>
1 0 0.0015 0.0004 mercurial.tags:148(_readtagcache)
Time: real 0.060 secs (user 0.030+0.000 sys 0.010+0.000)
author | Brodie Rao <brodie@sf.io> |
---|---|
date | Sun, 13 May 2012 14:04:04 +0200 |
parents | 828fe2ca7cbb |
children | ad394c897b16 |
line wrap: on
line source
# 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. import util import heapq def _nonoverlap(d1, d2, d3): "Return list of elements in d1 not in d2 or d3" return sorted([d for d in d1 if d not in d3 and d not in d2]) def _dirname(f): s = f.rfind("/") if s == -1: return "" return f[:s] def _findlimit(repo, a, b): """Find the earliest revision that's an ancestor of a or b but not both, None if no such revision exists. """ # 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 working = len(cl) # pseudo rev for the working directory if a is None: a = working if b is None: b = working side = {a: -1, b: 1} visit = [-a, -b] heapq.heapify(visit) interesting = len(visit) hascommonancestor = False limit = working while interesting: r = -heapq.heappop(visit) if r == working: parents = [cl.rev(p) for p in repo.dirstate.parents()] else: parents = cl.parentrevs(r) for p in parents: if p < 0: continue 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 hascommonancestor = True if side[r]: limit = r # lowest rev visited interesting -= 1 if not hascommonancestor: return None return limit 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 # remove criss-crossed copies for k, v in t.items(): if k in src and v in dst: del t[k] return t def _tracefile(fctx, actx): '''return file context that is the ancestor of fctx present in actx''' stop = actx.rev() am = actx.manifest() for f in fctx.ancestors(): if am.get(f.path(), None) == f.filenode(): return f if f.rev() < stop: 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) # 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 = {} for f in b: if f not in a: ofctx = _tracefile(b[f], a) if ofctx: cm[f] = ofctx.path() # combine copies from dirstate if necessary if w is not None: cm = _chain(a, w, cm, _dirstatecopies(w)) return cm def _backwardcopies(a, b): # because the forward mapping is 1:n, we can lose renames here # in particular, we find renames better than copies f = _forwardcopies(b, a) r = {} for k, v in f.iteritems(): 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: return _backwardcopies(x, y) return _chain(x, y, _backwardcopies(x, a), _forwardcopies(a, y)) def mergecopies(repo, c1, c2, ca): """ Find moves and copies between context c1 and c2 that are relevant for merging. Returns two dicts, "copy" and "diverge". "copy" is a mapping from destination name -> source name, where source is in c1 and destination is in c2 or vice-versa. "diverge" is a mapping of source name -> list of destination names for divergent renames. """ # avoid silly behavior for update from empty dir if not c1 or not c2 or c1 == c2: return {}, {} # avoid silly behavior for parent -> working dir if c2.node() is None and c1.node() == repo.dirstate.p1(): return repo.dirstate.copies(), {} limit = _findlimit(repo, c1.rev(), c2.rev()) if limit is None: # no common ancestor, no copies return {}, {} 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) ctx = util.lrucachefunc(makectx) copy = {} fullcopy = {} diverge = {} 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 def checkcopies(f, m1, m2): '''check possible copies of f from m1 to m2''' 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) repo.ui.debug(" searching for copies back to rev %d\n" % limit) u1 = _nonoverlap(m1, m2, ma) u2 = _nonoverlap(m2, m1, ma) if u1: repo.ui.debug(" unmatched files in local:\n %s\n" % "\n ".join(u1)) if u2: repo.ui.debug(" unmatched files in other:\n %s\n" % "\n ".join(u2)) for f in u1: checkcopies(f, m1, m2) for f in u2: checkcopies(f, m2, m1) diverge2 = set() for of, fl in diverge.items(): if len(fl) == 1 or of in c2: del diverge[of] # not actually divergent, or not a rename else: diverge2.update(fl) # reverse map for below if fullcopy: repo.ui.debug(" all copies found (* = to merge, ! = divergent):\n") for f in fullcopy: note = "" if f in copy: note += "*" if f in diverge2: note += "!" repo.ui.debug(" %s -> %s %s\n" % (f, fullcopy[f], note)) del diverge2 if not fullcopy: return copy, diverge repo.ui.debug(" checking for directory renames\n") # generate a directory move map d1, d2 = c1.dirs(), c2.dirs() invalid = set([""]) 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 for dst, src in fullcopy.iteritems(): 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 invalid.add(dsrc) elif dsrc in d2 and ddst in d2: # directory wasn't entirely moved remotely invalid.add(dsrc) elif dsrc in dirmove and dirmove[dsrc] != ddst: # files from the same directory moved to two different places invalid.add(dsrc) 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: return copy, diverge for d in dirmove: repo.ui.debug(" dir %s -> %s\n" % (d, dirmove[d])) # 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 df = dirmove[d] + f[len(d):] if df not in copy: copy[f] = df repo.ui.debug(" file %s -> %s\n" % (f, copy[f])) break return copy, diverge