Mercurial > hg > mercurial-source
changeset 24685:a2292da6d821
treemanifest: make treemanifest.matches() faster
By converting treemanifest.matches() into a recursively additivie operation,
it becomes O(n).
The old matches function made a copy of the entire manifest and deleted
files that didn't match. With tree manifests, this was an O(n log n) operation
because del() was O(log n).
This change speeds up the command
"hg status --rev .^ 'relglob:*.js'
on the Mozilla repo, now taking 2.53s, down from 3.51s.
author | Drew Gottlieb <drgott@google.com> |
---|---|
date | Mon, 30 Mar 2015 18:10:59 -0700 |
parents | 4fdf5eac5b39 |
children | afc29e29d569 |
files | mercurial/manifest.py |
diffstat | 1 files changed, 22 insertions(+), 5 deletions(-) [+] |
line wrap: on
line diff
--- a/mercurial/manifest.py +++ b/mercurial/manifest.py @@ -522,11 +522,28 @@ if match.always(): return self.copy() - m = self.copy() - for fn in m.keys(): - if not match(fn): - del m[fn] - return m + return self._matches(match) + + def _matches(self, match): + '''recursively generate a new manifest filtered by the match argument. + ''' + + ret = treemanifest(self._dir) + + for fn in self._files: + fullp = self._subpath(fn) + if not match(fullp): + continue + ret._files[fn] = self._files[fn] + if fn in self._flags: + ret._flags[fn] = self._flags[fn] + + for dir, subm in self._dirs.iteritems(): + m = subm._matches(match) + if not m._isempty(): + ret._dirs[dir] = m + + return ret def diff(self, m2, clean=False): '''Finds changes between the current manifest and m2.