changeset 24552: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.

--- a/mercurial/manifest.py	Mon Mar 30 17:21:49 2015 -0700
+++ b/mercurial/manifest.py	Mon Mar 30 18:10:59 2015 -0700
@@ -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.