[PATCH 4 of 4] treemanifest: make treemanifest.matches() faster

[Drew Gottlieb]

# HG changeset patch
# User Drew Gottlieb <drgott at google.com>
# Date 1427764259 25200
#      Mon Mar 30 18:10:59 2015 -0700
# Node ID f9aab64dc4e7009cef4b27e1f513bc15b2abbacc
# Parent  0a665bd18b18eb6a27e82475ad13810378637478
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 --git a/mercurial/manifest.py b/mercurial/manifest.py
--- 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.