# HG changeset patch
# User Drew Gottlieb <drgott@google.com>
# Date 1427764259 25200
# Node ID a2292da6d821beb0c846eafe3a1edafa22608302
# Parent  4fdf5eac5b39b9137945c64e6f370be1bcb0d2ee
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.

diff -r 4fdf5eac5b39 -r a2292da6d821 mercurial/manifest.py
--- 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.