[PATCH 1 of 6 V3] treemanifest: create treemanifest class
Martin von Zweigbergk
martinvonz at google.com
Thu Mar 19 19:52:53 UTC 2015
# HG changeset patch
# User Martin von Zweigbergk <martinvonz at google.com>
# Date 1426788522 25200
# Thu Mar 19 11:08:42 2015 -0700
# Node ID 5b4a29d0093d1fce3230cf09cca111b2258380cb
# Parent 5cb459dc32d209653a3e5d77749cf989ab9a51e4
treemanifest: create treemanifest class
There are a number of problems with large and flat manifests. Copying
from http://mercurial.selenic.com/wiki/ManifestShardingPlan:
* manifest too large for RAM
* manifest resolution too much CPU (long delta chains)
* committing is slow because entire manifest has to be hashed
* impossible for narrow clone to leave out part of manifest as all is
needed to calculate new hash
* diffing two revisions involves traversing entire subdirectories
even if identical
This is a first step in a series introducing a manifest revlog per
directory.
This change adds a new manifest class: treemanifest, which is a tree
where each node has a dict of files (nodeids), a dict of flags, and a
dict of subdirectories (treemanifests). So far, it behaves just like
manifestdict, but it will later help us write one manifest revlog per
directory. The new class is still unused; it will be used after the
next change.
The code is not yet optimized. Running with it (see below) makes most
or all operations slower. Once we start storing manifest revlogs for
every directory, it should be possible to make many of these
operations much faster. The fastdelta() optimization has been
intentionally not implemented for the treemanifests. We can implement
it later if necessary.
All tests pass when run with the following patch (and without, of
couse):
--- a/mercurial/manifest.py Thu Mar 19 11:08:42 2015 -0700
+++ b/mercurial/manifest.py Thu Mar 19 11:15:50 2015 -0700
@@ -596,7 +596,7 @@ class manifest(revlog.revlog):
return None, None
def add(self, m, transaction, link, p1, p2, added, removed):
- if p1 in self._mancache:
+ if False and p1 in self._mancache:
# If our first parent is in the manifest cache, we can
# compute a delta here using properties we know about the
# manifest up-front, which may save time later for the
@@ -626,3 +626,5 @@ class manifest(revlog.revlog):
self._mancache[n] = (m, arraytext)
return n
+
+manifestdict = treemanifest
diff -r 5cb459dc32d2 -r 5b4a29d0093d mercurial/manifest.py
--- a/mercurial/manifest.py Tue Oct 28 22:32:18 2014 -0700
+++ b/mercurial/manifest.py Thu Mar 19 11:08:42 2015 -0700
@@ -328,6 +328,228 @@
+ content for start, end, content in x)
return deltatext, newaddlist
+def _splittopdir(f):
+ if '/' in f:
+ dir, subpath = f.split('/', 1)
+ return dir + '/', subpath
+ else:
+ return '', f
+
+class treemanifest(object):
+ def __init__(self, text=''):
+ self._dirs = {}
+ # Using _lazymanifest here is a little slower than plain old dicts
+ self._files = {}
+ self._flags = {}
+ lm = _lazymanifest(text)
+ for f, n, fl in lm.iterentries():
+ self[f] = n
+ if fl:
+ self.setflag(f, fl)
+
+ def __len__(self):
+ size = len(self._files)
+ for m in self._dirs.values():
+ size += m.__len__()
+ return size
+
+ def iteritems(self):
+ for p, n in sorted(self._dirs.items() + self._files.items()):
+ if p in self._files:
+ yield p, n
+ else:
+ for sf, sn in n.iteritems():
+ yield p + sf, sn
+
+ def iterkeys(self):
+ for p in sorted(self._dirs.keys() + self._files.keys()):
+ if p in self._files:
+ yield p
+ else:
+ for f in self._dirs[p].iterkeys():
+ yield p + f
+
+ def keys(self):
+ return list(self.iterkeys())
+
+ def __iter__(self):
+ return self.iterkeys()
+
+ def __contains__(self, f):
+ if f is None:
+ return False
+ dir, subpath = _splittopdir(f)
+ if dir:
+ if dir not in self._dirs:
+ return False
+ return self._dirs[dir].__contains__(subpath)
+ else:
+ return f in self._files
+
+ def get(self, f, default=None):
+ dir, subpath = _splittopdir(f)
+ if dir:
+ if dir not in self._dirs:
+ return default
+ return self._dirs[dir].get(subpath, default)
+ else:
+ return self._files.get(f, default)
+
+ def __getitem__(self, f):
+ dir, subpath = _splittopdir(f)
+ if dir:
+ return self._dirs[dir].__getitem__(subpath)
+ else:
+ return self._files[f]
+
+ def flags(self, f):
+ dir, subpath = _splittopdir(f)
+ if dir:
+ if dir not in self._dirs:
+ return ''
+ return self._dirs[dir].flags(subpath)
+ else:
+ if f in self._dirs:
+ return ''
+ return self._flags.get(f, '')
+
+ def find(self, f):
+ dir, subpath = _splittopdir(f)
+ if dir:
+ return self._dirs[dir].find(subpath)
+ else:
+ return self._files[f], self._flags.get(f, '')
+
+ def __delitem__(self, f):
+ dir, subpath = _splittopdir(f)
+ if dir:
+ self._dirs[dir].__delitem__(subpath)
+ # If the directory is now empty, remove it
+ if not self._dirs[dir]._dirs and not self._dirs[dir]._files:
+ del self._dirs[dir]
+ else:
+ del self._files[f]
+ if f in self._flags:
+ del self._flags[f]
+
+ def __setitem__(self, f, n):
+ assert n is not None
+ dir, subpath = _splittopdir(f)
+ if dir:
+ if dir not in self._dirs:
+ self._dirs[dir] = treemanifest()
+ self._dirs[dir].__setitem__(subpath, n)
+ else:
+ self._files[f] = n
+
+ def setflag(self, f, flags):
+ """Set the flags (symlink, executable) for path f."""
+ dir, subpath = _splittopdir(f)
+ if dir:
+ if dir not in self._dirs:
+ self._dirs[dir] = treemanifest()
+ self._dirs[dir].setflag(subpath, flags)
+ else:
+ self._flags[f] = flags
+
+ def copy(self):
+ copy = treemanifest()
+ for d in self._dirs:
+ copy._dirs[d] = self._dirs[d].copy()
+ copy._files = dict.copy(self._files)
+ copy._flags = dict.copy(self._flags)
+ return copy
+
+ def intersectfiles(self, files):
+ '''make a new treemanifest with the intersection of self with files
+
+ The algorithm assumes that files is much smaller than self.'''
+ ret = treemanifest()
+ for fn in files:
+ if fn in self:
+ ret[fn] = self[fn]
+ flags = self.flags(fn)
+ if flags:
+ ret.setflag(fn, flags)
+ return ret
+
+ def filesnotin(self, m2):
+ '''Set of files in this manifest that are not in the other'''
+ files = set(self.iterkeys())
+ files.difference_update(m2.iterkeys())
+ return files
+
+ @propertycache
+ def _alldirs(self):
+ return scmutil.dirs(self)
+
+ def dirs(self):
+ return self._alldirs
+
+ def hasdir(self, dir):
+ return dir in self._alldirs
+
+ def matches(self, match):
+ '''generate a new manifest filtered by the match argument'''
+ if match.always():
+ return self.copy()
+
+ files = match.files()
+ if (match.matchfn == match.exact or
+ (not match.anypats() and util.all(fn in self for fn in files))):
+ return self.intersectfiles(files)
+
+ m = self.copy()
+ for fn in m.keys():
+ if not match(fn):
+ del m[fn]
+ return m
+
+ def diff(self, m2, clean=False):
+ '''Finds changes between the current manifest and m2.
+
+ Args:
+ m2: the manifest to which this manifest should be compared.
+ clean: if true, include files unchanged between these manifests
+ with a None value in the returned dictionary.
+
+ The result is returned as a dict with filename as key and
+ values of the form ((n1,fl1),(n2,fl2)), where n1/n2 is the
+ nodeid in the current/other manifest and fl1/fl2 is the flag
+ in the current/other manifest. Where the file does not exist,
+ the nodeid will be None and the flags will be the empty
+ string.
+ '''
+ diff = {}
+
+ for fn, n1 in self.iteritems():
+ fl1 = self.flags(fn)
+ n2 = m2.get(fn, None)
+ fl2 = m2.flags(fn)
+ if n2 is None:
+ fl2 = ''
+ if n1 != n2 or fl1 != fl2:
+ diff[fn] = ((n1, fl1), (n2, fl2))
+ elif clean:
+ diff[fn] = None
+
+ for fn, n2 in m2.iteritems():
+ if fn not in self:
+ fl2 = m2.flags(fn)
+ diff[fn] = ((None, ''), (n2, fl2))
+
+ return diff
+
+ def text(self):
+ """Get the full data of this manifest as a bytestring."""
+ fl = self.keys()
+ _checkforbidden(fl)
+
+ hex, flags = revlog.hex, self.flags
+ # if this is changed to support newlines in filenames,
+ # be sure to check the templates/ dir again (especially *-raw.tmpl)
+ return ''.join("%s\0%s%s\n" % (f, hex(self[f]), flags(f)) for f in fl)
+
class manifest(revlog.revlog):
def __init__(self, opener):
# During normal operations, we expect to deal with not more than four
More information about the Mercurial-devel
mailing list