match: add visitchildrenset complement to visitdir

`visitdir(d)` lets a caller query whether the directory is part of the matcher.
It can receive a response of 'all' (yes, and all children, you can stop calling
visitdir now), False (no, and no children either), or True (yes, either
something in this directory or a child is part of the matcher).

`visitchildrenset(d)` augments that by instead of returning True, it returns a
list of items to actually investigate.  With this, code can be modified from:

    for f in self.all_items:
        if match.visitdir(self.dir + '/' + f):
            <do stuff>

to be:

    for f in self.all_items.intersect(match.visitchildrenset(self.dir)):
        <do stuff>

use of this function can provide significant performance improvements,
especially when using narrow (so that the matcher is much smaller than the stuff
we see on disk) and/or treemanifests (so that we can avoid loading manifests for
trees that aren't part of the matcher).

Differential Revision: https://phab.mercurial-scm.org/D4130

mercurial/match.py

@@ -8,6 +8,7 b''
 from __future__ import absolute_import, print_function
 
 import copy
+import itertools
 import os
 import re
 
@@ -331,6 +332,38 b' class basematcher(object):'
         '''
         return True
 
+    def visitchildrenset(self, dir):
+        '''Decides whether a directory should be visited based on whether it
+        has potential matches in it or one of its subdirectories, and
+        potentially lists which subdirectories of that directory should be
+        visited. This is based on the match's primary, included, and excluded
+        patterns.
+
+        This function is very similar to 'visitdir', and the following mapping
+        can be applied:
+
+             visitdir | visitchildrenlist
+            ----------+-------------------
+             False    | set()
+             'all'    | 'all'
+             True     | 'this' OR non-empty set of subdirs to visit
+
+        Example:
+          Assume matchers ['path:foo/bar', 'rootfilesin:qux'], we would return
+          the following values (assuming the implementation of visitchildrenset
+          is capable of recognizing this; some implementations are not).
+
+          '.' -> {'foo', 'qux'}
+          'baz' -> set()
+          'foo' -> {'bar'}
+          # Ideally this would be 'all', but since the prefix nature of matchers
+          # is applied to the entire matcher, we have to downgrade to this
+          # 'this' due to the non-prefix 'rootfilesin'-kind matcher.
+          'foo/bar' -> 'this'
+          'qux' -> 'this'
+        '''
+        return 'this'
+
     def always(self):
         '''Matcher will match everything and .files() will be empty --
         optimization might be possible.'''
@@ -367,6 +400,9 b' class alwaysmatcher(basematcher):'
     def visitdir(self, dir):
         return 'all'
 
+    def visitchildrenset(self, dir):
+        return 'all'
+
     def __repr__(self):
         return r'<alwaysmatcher>'
 
@@ -390,6 +426,9 b' class nevermatcher(basematcher):'
     def visitdir(self, dir):
         return False
 
+    def visitchildrenset(self, dir):
+        return set()
+
     def __repr__(self):
         return r'<nevermatcher>'
 
@@ -430,6 +469,15 b' class patternmatcher(basematcher):'
                 any(parentdir in self._fileset
                     for parentdir in util.finddirs(dir)))
 
+    def visitchildrenset(self, dir):
+        ret = self.visitdir(dir)
+        if ret is True:
+            return 'this'
+        elif not ret:
+            return set()
+        assert ret == 'all'
+        return 'all'
+
     def prefix(self):
         return self._prefix
 
@@ -464,6 +512,43 b' class includematcher(basematcher):'
                 any(parentdir in self._roots
                     for parentdir in util.finddirs(dir)))
 
+    def visitchildrenset(self, dir):
+        if self._prefix and dir in self._roots:
+            return 'all'
+        # Note: this does *not* include the 'dir in self._parents' case from
+        # visitdir, that's handled below.
+        if ('.' in self._roots or
+            dir in self._roots or
+            dir in self._dirs or
+            any(parentdir in self._roots
+                for parentdir in util.finddirs(dir))):
+            return 'this'
+
+        ret = set()
+        if dir in self._parents:
+            # We add a '/' on to `dir` so that we don't return items that are
+            # prefixed by `dir` but are actually siblings of `dir`.
+            suffixeddir = dir + '/' if dir != '.' else ''
+            # Look in all _roots, _dirs, and _parents for things that start with
+            # 'suffixeddir'.
+            for d in [q for q in
+                      itertools.chain(self._roots, self._dirs, self._parents) if
+                      q.startswith(suffixeddir)]:
+                # Don't emit '.' in the response for the root directory
+                if not suffixeddir and d == '.':
+                    continue
+
+                # We return the item name without the `suffixeddir` prefix or a
+                # slash suffix
+                d = d[len(suffixeddir):]
+                if '/' in d:
+                    # This is a subdirectory-of-a-subdirectory, i.e.
+                    # suffixeddir='foo/', d was 'foo/bar/baz' before removing
+                    # 'foo/'.
+                    d = d[:d.index('/')]
+                ret.add(d)
+        return ret
+
     @encoding.strmethod
     def __repr__(self):
         return ('<includematcher includes=%r>' % pycompat.bytestr(self._pats))
@@ -490,6 +575,25 b' class exactmatcher(basematcher):'
     def visitdir(self, dir):
         return dir in self._dirs
 
+    def visitchildrenset(self, dir):
+        if dir in self._dirs:
+            candidates = self._dirs - {'.'}
+            if dir != '.':
+                d = dir + '/'
+                candidates = set(c[len(d):] for c in candidates if
+                                 c.startswith(d))
+            # self._dirs includes all of the directories, recursively, so if
+            # we're attempting to match foo/bar/baz.txt, it'll have '.', 'foo',
+            # 'foo/bar' in it. Thus we can safely ignore a candidate that has a
+            # '/' in it, indicating a it's for a subdir-of-a-subdir; the
+            # immediate subdir will be in there without a slash.
+            ret = set(c for c in candidates if '/' not in c)
+            # We need to emit 'this' for foo/bar, not set(), not {'baz.txt'}.
+            if not ret:
+                return 'this'
+            return ret
+        return set()
+
     def isexact(self):
         return True
 
@@ -531,6 +635,31 b' class differencematcher(basematcher):'
             return False
         return bool(self._m1.visitdir(dir))
 
+    def visitchildrenset(self, dir):
+        m2_set = self._m2.visitchildrenset(dir)
+        if m2_set == 'all':
+            return set()
+        m1_set = self._m1.visitchildrenset(dir)
+        # Possible values for m1: 'all', 'this', set(...), set()
+        # Possible values for m2:        'this', set(...), set()
+        # If m2 has nothing under here that we care about, return m1, even if
+        # it's 'all'. This is a change in behavior from visitdir, which would
+        # return True, not 'all', for some reason.
+        if not m2_set:
+            return m1_set
+        if m1_set in ['all', 'this']:
+            # Never return 'all' here if m2_set is any kind of non-empty (either
+            # 'this' or set(foo)), since m2 might return set() for a
+            # subdirectory.
+            return 'this'
+        # Possible values for m1:         set(...), set()
+        # Possible values for m2: 'this', set(...)
+        # We ignore m2's set results. They're possibly incorrect:
+        #  m1 = path:dir/subdir, m2=rootfilesin:dir, visitchildrenset('.'):
+        #    m1 returns {'dir'}, m2 returns {'dir'}, if we subtracted we'd
+        #    return set(), which is *not* correct, we still need to visit 'dir'!
+        return m1_set
+
     def isexact(self):
         return self._m1.isexact()
 
@@ -595,6 +724,25 b' class intersectionmatcher(basematcher):'
         # bool() because visit1=True + visit2='all' should not be 'all'
         return bool(visit1 and self._m2.visitdir(dir))
 
+    def visitchildrenset(self, dir):
+        m1_set = self._m1.visitchildrenset(dir)
+        if not m1_set:
+            return set()
+        m2_set = self._m2.visitchildrenset(dir)
+        if not m2_set:
+            return set()
+
+        if m1_set == 'all':
+            return m2_set
+        elif m2_set == 'all':
+            return m1_set
+
+        if m1_set == 'this' or m2_set == 'this':
+            return 'this'
+
+        assert isinstance(m1_set, set) and isinstance(m2_set, set)
+        return m1_set.intersection(m2_set)
+
     def always(self):
         return self._m1.always() and self._m2.always()
 
@@ -676,6 +824,13 b' class subdirmatcher(basematcher):'
             dir = self._path + "/" + dir
         return self._matcher.visitdir(dir)
 
+    def visitchildrenset(self, dir):
+        if dir == '.':
+            dir = self._path
+        else:
+            dir = self._path + "/" + dir
+        return self._matcher.visitchildrenset(dir)
+
     def always(self):
         return self._always
 
@@ -748,6 +903,14 b' class prefixdirmatcher(basematcher):'
             return self._matcher.visitdir(dir[len(self._pathprefix):])
         return dir in self._pathdirs
 
+    def visitchildrenset(self, dir):
+        if dir == self._path:
+            return self._matcher.visitchildrenset('.')
+        if dir.startswith(self._pathprefix):
+            return self._matcher.visitchildrenset(dir[len(self._pathprefix):])
+        if dir in self._pathdirs:
+            return 'this'
+
     def isexact(self):
         return self._matcher.isexact()
 
@@ -788,6 +951,25 b' class unionmatcher(basematcher):'
             r |= v
         return r
 
+    def visitchildrenset(self, dir):
+        r = set()
+        this = False
+        for m in self._matchers:
+            v = m.visitchildrenset(dir)
+            if not v:
+                continue
+            if v == 'all':
+                return v
+            if this or v == 'this':
+                this = True
+                # don't break, we might have an 'all' in here.
+                continue
+            assert isinstance(v, set)
+            r = r.union(v)
+        if this:
+            return 'this'
+        return r
+
     @encoding.strmethod
     def __repr__(self):
         return ('<unionmatcher matchers=%r>' % self._matchers)

tests/test-match.py

@@ -16,6 +16,11 b' class BaseMatcherTests(unittest.TestCase'
         self.assertTrue(m.visitdir('.'))
         self.assertTrue(m.visitdir('dir'))
 
+    def testVisitchildrenset(self):
+        m = matchmod.basematcher('', '')
+        self.assertEqual(m.visitchildrenset('.'), 'this')
+        self.assertEqual(m.visitchildrenset('dir'), 'this')
+
 class AlwaysMatcherTests(unittest.TestCase):
 
     def testVisitdir(self):
@@ -23,6 +28,11 b' class AlwaysMatcherTests(unittest.TestCa'
         self.assertEqual(m.visitdir('.'), 'all')
         self.assertEqual(m.visitdir('dir'), 'all')
 
+    def testVisitchildrenset(self):
+        m = matchmod.alwaysmatcher('', '')
+        self.assertEqual(m.visitchildrenset('.'), 'all')
+        self.assertEqual(m.visitchildrenset('dir'), 'all')
+
 class NeverMatcherTests(unittest.TestCase):
 
     def testVisitdir(self):
@@ -30,6 +40,11 b' class NeverMatcherTests(unittest.TestCas'
         self.assertFalse(m.visitdir('.'))
         self.assertFalse(m.visitdir('dir'))
 
+    def testVisitchildrenset(self):
+        m = matchmod.nevermatcher('', '')
+        self.assertEqual(m.visitchildrenset('.'), set())
+        self.assertEqual(m.visitchildrenset('dir'), set())
+
 class PredicateMatcherTests(unittest.TestCase):
     # predicatematcher does not currently define either of these methods, so
     # this is equivalent to BaseMatcherTests.
@@ -39,6 +54,11 b' class PredicateMatcherTests(unittest.Tes'
         self.assertTrue(m.visitdir('.'))
         self.assertTrue(m.visitdir('dir'))
 
+    def testVisitchildrenset(self):
+        m = matchmod.predicatematcher('', '', lambda *a: False)
+        self.assertEqual(m.visitchildrenset('.'), 'this')
+        self.assertEqual(m.visitchildrenset('dir'), 'this')
+
 class PatternMatcherTests(unittest.TestCase):
 
     def testVisitdirPrefix(self):
@@ -51,6 +71,16 b' class PatternMatcherTests(unittest.TestC'
         self.assertTrue(m.visitdir('dir/subdir/x'))
         self.assertFalse(m.visitdir('folder'))
 
+    def testVisitchildrensetPrefix(self):
+        m = matchmod.match('x', '', patterns=['path:dir/subdir'])
+        assert isinstance(m, matchmod.patternmatcher)
+        self.assertEqual(m.visitchildrenset('.'), 'this')
+        self.assertEqual(m.visitchildrenset('dir'), 'this')
+        self.assertEqual(m.visitchildrenset('dir/subdir'), 'all')
+        # OPT: This should probably be 'all' if its parent is?
+        self.assertEqual(m.visitchildrenset('dir/subdir/x'), 'this')
+        self.assertEqual(m.visitchildrenset('folder'), set())
+
     def testVisitdirRootfilesin(self):
         m = matchmod.match('x', '', patterns=['rootfilesin:dir/subdir'])
         assert isinstance(m, matchmod.patternmatcher)
@@ -61,6 +91,15 b' class PatternMatcherTests(unittest.TestC'
         self.assertFalse(m.visitdir('dir'))
         self.assertFalse(m.visitdir('dir/subdir'))
 
+    def testVisitchildrensetRootfilesin(self):
+        m = matchmod.match('x', '', patterns=['rootfilesin:dir/subdir'])
+        assert isinstance(m, matchmod.patternmatcher)
+        self.assertEqual(m.visitchildrenset('.'), 'this')
+        self.assertEqual(m.visitchildrenset('dir/subdir/x'), set())
+        self.assertEqual(m.visitchildrenset('folder'), set())
+        self.assertEqual(m.visitchildrenset('dir'), set())
+        self.assertEqual(m.visitchildrenset('dir/subdir'), set())
+
     def testVisitdirGlob(self):
         m = matchmod.match('x', '', patterns=['glob:dir/z*'])
         assert isinstance(m, matchmod.patternmatcher)
@@ -71,6 +110,16 b' class PatternMatcherTests(unittest.TestC'
         self.assertTrue(m.visitdir('dir/subdir'))
         self.assertTrue(m.visitdir('dir/subdir/x'))
 
+    def testVisitchildrensetGlob(self):
+        m = matchmod.match('x', '', patterns=['glob:dir/z*'])
+        assert isinstance(m, matchmod.patternmatcher)
+        self.assertEqual(m.visitchildrenset('.'), 'this')
+        self.assertEqual(m.visitchildrenset('folder'), set())
+        self.assertEqual(m.visitchildrenset('dir'), 'this')
+        # OPT: these should probably be set().
+        self.assertEqual(m.visitchildrenset('dir/subdir'), 'this')
+        self.assertEqual(m.visitchildrenset('dir/subdir/x'), 'this')
+
 class IncludeMatcherTests(unittest.TestCase):
 
     def testVisitdirPrefix(self):
@@ -83,6 +132,16 b' class IncludeMatcherTests(unittest.TestC'
         self.assertTrue(m.visitdir('dir/subdir/x'))
         self.assertFalse(m.visitdir('folder'))
 
+    def testVisitchildrensetPrefix(self):
+        m = matchmod.match('x', '', include=['path:dir/subdir'])
+        assert isinstance(m, matchmod.includematcher)
+        self.assertEqual(m.visitchildrenset('.'), {'dir'})
+        self.assertEqual(m.visitchildrenset('dir'), {'subdir'})
+        self.assertEqual(m.visitchildrenset('dir/subdir'), 'all')
+        # OPT: This should probably be 'all' if its parent is?
+        self.assertEqual(m.visitchildrenset('dir/subdir/x'), 'this')
+        self.assertEqual(m.visitchildrenset('folder'), set())
+
     def testVisitdirRootfilesin(self):
         m = matchmod.match('x', '', include=['rootfilesin:dir/subdir'])
         assert isinstance(m, matchmod.includematcher)
@@ -92,6 +151,15 b' class IncludeMatcherTests(unittest.TestC'
         self.assertFalse(m.visitdir('dir/subdir/x'))
         self.assertFalse(m.visitdir('folder'))
 
+    def testVisitchildrensetRootfilesin(self):
+        m = matchmod.match('x', '', include=['rootfilesin:dir/subdir'])
+        assert isinstance(m, matchmod.includematcher)
+        self.assertEqual(m.visitchildrenset('.'), {'dir'})
+        self.assertEqual(m.visitchildrenset('dir'), {'subdir'})
+        self.assertEqual(m.visitchildrenset('dir/subdir'), 'this')
+        self.assertEqual(m.visitchildrenset('dir/subdir/x'), set())
+        self.assertEqual(m.visitchildrenset('folder'), set())
+
     def testVisitdirGlob(self):
         m = matchmod.match('x', '', include=['glob:dir/z*'])
         assert isinstance(m, matchmod.includematcher)
@@ -102,6 +170,16 b' class IncludeMatcherTests(unittest.TestC'
         self.assertTrue(m.visitdir('dir/subdir'))
         self.assertTrue(m.visitdir('dir/subdir/x'))
 
+    def testVisitchildrensetGlob(self):
+        m = matchmod.match('x', '', include=['glob:dir/z*'])
+        assert isinstance(m, matchmod.includematcher)
+        self.assertEqual(m.visitchildrenset('.'), {'dir'})
+        self.assertEqual(m.visitchildrenset('folder'), set())
+        self.assertEqual(m.visitchildrenset('dir'), 'this')
+        # OPT: these should probably be set().
+        self.assertEqual(m.visitchildrenset('dir/subdir'), 'this')
+        self.assertEqual(m.visitchildrenset('dir/subdir/x'), 'this')
+
 class ExactMatcherTests(unittest.TestCase):
 
     def testVisitdir(self):
@@ -115,6 +193,16 b' class ExactMatcherTests(unittest.TestCas'
         self.assertFalse(m.visitdir('dir/subdir/x'))
         self.assertFalse(m.visitdir('folder'))
 
+    def testVisitchildrenset(self):
+        m = matchmod.match('x', '', patterns=['dir/subdir/foo.txt'], exact=True)
+        assert isinstance(m, matchmod.exactmatcher)
+        self.assertEqual(m.visitchildrenset('.'), {'dir'})
+        self.assertEqual(m.visitchildrenset('dir'), {'subdir'})
+        self.assertEqual(m.visitchildrenset('dir/subdir'), 'this')
+        self.assertEqual(m.visitchildrenset('dir/subdir/x'), set())
+        self.assertEqual(m.visitchildrenset('dir/subdir/foo.txt'), set())
+        self.assertEqual(m.visitchildrenset('folder'), set())
+
 class DifferenceMatcherTests(unittest.TestCase):
 
     def testVisitdirM2always(self):
@@ -130,6 +218,19 b' class DifferenceMatcherTests(unittest.Te'
         self.assertFalse(dm.visitdir('dir/subdir/x'))
         self.assertFalse(dm.visitdir('folder'))
 
+    def testVisitchildrensetM2always(self):
+        m1 = matchmod.alwaysmatcher('', '')
+        m2 = matchmod.alwaysmatcher('', '')
+        dm = matchmod.differencematcher(m1, m2)
+        # dm should be equivalent to a nevermatcher.
+        self.assertEqual(dm.visitchildrenset('.'), set())
+        self.assertEqual(dm.visitchildrenset('dir'), set())
+        self.assertEqual(dm.visitchildrenset('dir/subdir'), set())
+        self.assertEqual(dm.visitchildrenset('dir/subdir/z'), set())
+        self.assertEqual(dm.visitchildrenset('dir/foo'), set())
+        self.assertEqual(dm.visitchildrenset('dir/subdir/x'), set())
+        self.assertEqual(dm.visitchildrenset('folder'), set())
+
     def testVisitdirM2never(self):
         m1 = matchmod.alwaysmatcher('', '')
         m2 = matchmod.nevermatcher('', '')
@@ -149,6 +250,19 b' class DifferenceMatcherTests(unittest.Te'
         self.assertEqual(dm.visitdir('dir/subdir/x'), True)
         self.assertEqual(dm.visitdir('folder'), True)
 
+    def testVisitchildrensetM2never(self):
+        m1 = matchmod.alwaysmatcher('', '')
+        m2 = matchmod.nevermatcher('', '')
+        dm = matchmod.differencematcher(m1, m2)
+        # dm should be equivalent to a alwaysmatcher.
+        self.assertEqual(dm.visitchildrenset('.'), 'all')
+        self.assertEqual(dm.visitchildrenset('dir'), 'all')
+        self.assertEqual(dm.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(dm.visitchildrenset('dir/subdir/z'), 'all')
+        self.assertEqual(dm.visitchildrenset('dir/foo'), 'all')
+        self.assertEqual(dm.visitchildrenset('dir/subdir/x'), 'all')
+        self.assertEqual(dm.visitchildrenset('folder'), 'all')
+
     def testVisitdirM2SubdirPrefix(self):
         m1 = matchmod.alwaysmatcher('', '')
         m2 = matchmod.match('', '', patterns=['path:dir/subdir'])
@@ -165,6 +279,21 b' class DifferenceMatcherTests(unittest.Te'
         self.assertEqual(dm.visitdir('dir/foo'), True)
         self.assertEqual(dm.visitdir('folder'), True)
 
+    def testVisitchildrensetM2SubdirPrefix(self):
+        m1 = matchmod.alwaysmatcher('', '')
+        m2 = matchmod.match('', '', patterns=['path:dir/subdir'])
+        dm = matchmod.differencematcher(m1, m2)
+        self.assertEqual(dm.visitchildrenset('.'), 'this')
+        self.assertEqual(dm.visitchildrenset('dir'), 'this')
+        self.assertEqual(dm.visitchildrenset('dir/subdir'), set())
+        self.assertEqual(dm.visitchildrenset('dir/foo'), 'all')
+        self.assertEqual(dm.visitchildrenset('folder'), 'all')
+        # OPT: We should probably return set() for these; we don't because
+        # patternmatcher.visitdir() (our m2) doesn't return 'all' for subdirs of
+        # an 'all' pattern, just 'this'.
+        self.assertEqual(dm.visitchildrenset('dir/subdir/z'), 'this')
+        self.assertEqual(dm.visitchildrenset('dir/subdir/x'), 'this')
+
     # We're using includematcher instead of patterns because it behaves slightly
     # better (giving narrower results) than patternmatcher.
     def testVisitdirIncludeIncludfe(self):
@@ -182,6 +311,21 b' class DifferenceMatcherTests(unittest.Te'
         self.assertEqual(dm.visitdir('dir/subdir/z'), True)
         self.assertEqual(dm.visitdir('dir/subdir/x'), True)
 
+    def testVisitchildrensetIncludeInclude(self):
+        m1 = matchmod.match('', '', include=['path:dir/subdir'])
+        m2 = matchmod.match('', '', include=['rootfilesin:dir'])
+        dm = matchmod.differencematcher(m1, m2)
+        self.assertEqual(dm.visitchildrenset('.'), {'dir'})
+        self.assertEqual(dm.visitchildrenset('dir'), {'subdir'})
+        self.assertEqual(dm.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(dm.visitchildrenset('dir/foo'), set())
+        self.assertEqual(dm.visitchildrenset('folder'), set())
+        # OPT: We should probably return set() for these; we don't because
+        # patternmatcher.visitdir() (our m2) doesn't return 'all' for subdirs of
+        # an 'all' pattern, just 'this'.
+        self.assertEqual(dm.visitchildrenset('dir/subdir/z'), 'this')
+        self.assertEqual(dm.visitchildrenset('dir/subdir/x'), 'this')
+
 class IntersectionMatcherTests(unittest.TestCase):
 
     def testVisitdirM2always(self):
@@ -197,6 +341,19 b' class IntersectionMatcherTests(unittest.'
         self.assertEqual(im.visitdir('dir/subdir/x'), 'all')
         self.assertEqual(im.visitdir('folder'), 'all')
 
+    def testVisitchildrensetM2always(self):
+        m1 = matchmod.alwaysmatcher('', '')
+        m2 = matchmod.alwaysmatcher('', '')
+        im = matchmod.intersectmatchers(m1, m2)
+        # im should be equivalent to a alwaysmatcher.
+        self.assertEqual(im.visitchildrenset('.'), 'all')
+        self.assertEqual(im.visitchildrenset('dir'), 'all')
+        self.assertEqual(im.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(im.visitchildrenset('dir/subdir/z'), 'all')
+        self.assertEqual(im.visitchildrenset('dir/foo'), 'all')
+        self.assertEqual(im.visitchildrenset('dir/subdir/x'), 'all')
+        self.assertEqual(im.visitchildrenset('folder'), 'all')
+
     def testVisitdirM2never(self):
         m1 = matchmod.alwaysmatcher('', '')
         m2 = matchmod.nevermatcher('', '')
@@ -210,6 +367,19 b' class IntersectionMatcherTests(unittest.'
         self.assertFalse(im.visitdir('dir/subdir/x'))
         self.assertFalse(im.visitdir('folder'))
 
+    def testVisitchildrensetM2never(self):
+        m1 = matchmod.alwaysmatcher('', '')
+        m2 = matchmod.nevermatcher('', '')
+        im = matchmod.intersectmatchers(m1, m2)
+        # im should be equivalent to a nevermqtcher.
+        self.assertEqual(im.visitchildrenset('.'), set())
+        self.assertEqual(im.visitchildrenset('dir'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir/z'), set())
+        self.assertEqual(im.visitchildrenset('dir/foo'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir/x'), set())
+        self.assertEqual(im.visitchildrenset('folder'), set())
+
     def testVisitdirM2SubdirPrefix(self):
         m1 = matchmod.alwaysmatcher('', '')
         m2 = matchmod.match('', '', patterns=['path:dir/subdir'])
@@ -225,6 +395,19 b' class IntersectionMatcherTests(unittest.'
         self.assertEqual(im.visitdir('dir/subdir/z'), True)
         self.assertEqual(im.visitdir('dir/subdir/x'), True)
 
+    def testVisitchildrensetM2SubdirPrefix(self):
+        m1 = matchmod.alwaysmatcher('', '')
+        m2 = matchmod.match('', '', include=['path:dir/subdir'])
+        im = matchmod.intersectmatchers(m1, m2)
+        self.assertEqual(im.visitchildrenset('.'), {'dir'})
+        self.assertEqual(im.visitchildrenset('dir'), {'subdir'})
+        self.assertEqual(im.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(im.visitchildrenset('dir/foo'), set())
+        self.assertEqual(im.visitchildrenset('folder'), set())
+        # OPT: We should probably return 'all' for these
+        self.assertEqual(im.visitchildrenset('dir/subdir/z'), 'this')
+        self.assertEqual(im.visitchildrenset('dir/subdir/x'), 'this')
+
     # We're using includematcher instead of patterns because it behaves slightly
     # better (giving narrower results) than patternmatcher.
     def testVisitdirIncludeIncludfe(self):
@@ -239,6 +422,18 b' class IntersectionMatcherTests(unittest.'
         self.assertFalse(im.visitdir('dir/subdir/z'))
         self.assertFalse(im.visitdir('dir/subdir/x'))
 
+    def testVisitchildrensetIncludeInclude(self):
+        m1 = matchmod.match('', '', include=['path:dir/subdir'])
+        m2 = matchmod.match('', '', include=['rootfilesin:dir'])
+        im = matchmod.intersectmatchers(m1, m2)
+        self.assertEqual(im.visitchildrenset('.'), {'dir'})
+        self.assertEqual(im.visitchildrenset('dir'), 'this')
+        self.assertEqual(im.visitchildrenset('dir/subdir'), set())
+        self.assertEqual(im.visitchildrenset('dir/foo'), set())
+        self.assertEqual(im.visitchildrenset('folder'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir/z'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir/x'), set())
+
     # We're using includematcher instead of patterns because it behaves slightly
     # better (giving narrower results) than patternmatcher.
     def testVisitdirIncludeInclude2(self):
@@ -254,6 +449,19 b' class IntersectionMatcherTests(unittest.'
         self.assertFalse(im.visitdir('dir/subdir/z'))
         self.assertFalse(im.visitdir('dir/subdir/x'))
 
+    def testVisitchildrensetIncludeInclude2(self):
+        m1 = matchmod.match('', '', include=['path:dir/subdir'])
+        m2 = matchmod.match('', '', include=['path:folder'])
+        im = matchmod.intersectmatchers(m1, m2)
+        # FIXME: is set() correct here?
+        self.assertEqual(im.visitchildrenset('.'), set())
+        self.assertEqual(im.visitchildrenset('dir'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir'), set())
+        self.assertEqual(im.visitchildrenset('dir/foo'), set())
+        self.assertEqual(im.visitchildrenset('folder'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir/z'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir/x'), set())
+
     # We're using includematcher instead of patterns because it behaves slightly
     # better (giving narrower results) than patternmatcher.
     def testVisitdirIncludeInclude3(self):
@@ -269,6 +477,19 b' class IntersectionMatcherTests(unittest.'
         # OPT: this should probably be 'all' not True.
         self.assertEqual(im.visitdir('dir/subdir/x'), True)
 
+    def testVisitchildrensetIncludeInclude3(self):
+        m1 = matchmod.match('', '', include=['path:dir/subdir/x'])
+        m2 = matchmod.match('', '', include=['path:dir/subdir'])
+        im = matchmod.intersectmatchers(m1, m2)
+        self.assertEqual(im.visitchildrenset('.'), {'dir'})
+        self.assertEqual(im.visitchildrenset('dir'), {'subdir'})
+        self.assertEqual(im.visitchildrenset('dir/subdir'), {'x'})
+        self.assertEqual(im.visitchildrenset('dir/foo'), set())
+        self.assertEqual(im.visitchildrenset('folder'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir/z'), set())
+        # OPT: this should probably be 'all' not 'this'.
+        self.assertEqual(im.visitchildrenset('dir/subdir/x'), 'this')
+
     # We're using includematcher instead of patterns because it behaves slightly
     # better (giving narrower results) than patternmatcher.
     def testVisitdirIncludeInclude4(self):
@@ -284,6 +505,19 b' class IntersectionMatcherTests(unittest.'
         self.assertFalse(im.visitdir('dir/subdir/z'))
         self.assertFalse(im.visitdir('dir/subdir/x'))
 
+    def testVisitchildrensetIncludeInclude4(self):
+        m1 = matchmod.match('', '', include=['path:dir/subdir/x'])
+        m2 = matchmod.match('', '', include=['path:dir/subdir/z'])
+        im = matchmod.intersectmatchers(m1, m2)
+        # OPT: these next two could probably be set() as well.
+        self.assertEqual(im.visitchildrenset('.'), {'dir'})
+        self.assertEqual(im.visitchildrenset('dir'), {'subdir'})
+        self.assertEqual(im.visitchildrenset('dir/subdir'), set())
+        self.assertEqual(im.visitchildrenset('dir/foo'), set())
+        self.assertEqual(im.visitchildrenset('folder'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir/z'), set())
+        self.assertEqual(im.visitchildrenset('dir/subdir/x'), set())
+
 class UnionMatcherTests(unittest.TestCase):
 
     def testVisitdirM2always(self):
@@ -299,6 +533,19 b' class UnionMatcherTests(unittest.TestCas'
         self.assertEqual(um.visitdir('dir/subdir/x'), 'all')
         self.assertEqual(um.visitdir('folder'), 'all')
 
+    def testVisitchildrensetM2always(self):
+        m1 = matchmod.alwaysmatcher('', '')
+        m2 = matchmod.alwaysmatcher('', '')
+        um = matchmod.unionmatcher([m1, m2])
+        # um should be equivalent to a alwaysmatcher.
+        self.assertEqual(um.visitchildrenset('.'), 'all')
+        self.assertEqual(um.visitchildrenset('dir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir/z'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/foo'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir/x'), 'all')
+        self.assertEqual(um.visitchildrenset('folder'), 'all')
+
     def testVisitdirM1never(self):
         m1 = matchmod.nevermatcher('', '')
         m2 = matchmod.alwaysmatcher('', '')
@@ -312,6 +559,19 b' class UnionMatcherTests(unittest.TestCas'
         self.assertEqual(um.visitdir('dir/subdir/x'), 'all')
         self.assertEqual(um.visitdir('folder'), 'all')
 
+    def testVisitchildrensetM1never(self):
+        m1 = matchmod.nevermatcher('', '')
+        m2 = matchmod.alwaysmatcher('', '')
+        um = matchmod.unionmatcher([m1, m2])
+        # um should be equivalent to a alwaysmatcher.
+        self.assertEqual(um.visitchildrenset('.'), 'all')
+        self.assertEqual(um.visitchildrenset('dir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir/z'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/foo'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir/x'), 'all')
+        self.assertEqual(um.visitchildrenset('folder'), 'all')
+
     def testVisitdirM2never(self):
         m1 = matchmod.alwaysmatcher('', '')
         m2 = matchmod.nevermatcher('', '')
@@ -325,6 +585,19 b' class UnionMatcherTests(unittest.TestCas'
         self.assertEqual(um.visitdir('dir/subdir/x'), 'all')
         self.assertEqual(um.visitdir('folder'), 'all')
 
+    def testVisitchildrensetM2never(self):
+        m1 = matchmod.alwaysmatcher('', '')
+        m2 = matchmod.nevermatcher('', '')
+        um = matchmod.unionmatcher([m1, m2])
+        # um should be equivalent to a alwaysmatcher.
+        self.assertEqual(um.visitchildrenset('.'), 'all')
+        self.assertEqual(um.visitchildrenset('dir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir/z'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/foo'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir/x'), 'all')
+        self.assertEqual(um.visitchildrenset('folder'), 'all')
+
     def testVisitdirM2SubdirPrefix(self):
         m1 = matchmod.alwaysmatcher('', '')
         m2 = matchmod.match('', '', patterns=['path:dir/subdir'])
@@ -337,6 +610,18 b' class UnionMatcherTests(unittest.TestCas'
         self.assertEqual(um.visitdir('dir/subdir/z'), 'all')
         self.assertEqual(um.visitdir('dir/subdir/x'), 'all')
 
+    def testVisitchildrensetM2SubdirPrefix(self):
+        m1 = matchmod.alwaysmatcher('', '')
+        m2 = matchmod.match('', '', include=['path:dir/subdir'])
+        um = matchmod.unionmatcher([m1, m2])
+        self.assertEqual(um.visitchildrenset('.'), 'all')
+        self.assertEqual(um.visitchildrenset('dir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/foo'), 'all')
+        self.assertEqual(um.visitchildrenset('folder'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir/z'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir/x'), 'all')
+
     # We're using includematcher instead of patterns because it behaves slightly
     # better (giving narrower results) than patternmatcher.
     def testVisitdirIncludeIncludfe(self):
@@ -352,6 +637,19 b' class UnionMatcherTests(unittest.TestCas'
         self.assertEqual(um.visitdir('dir/subdir/z'), True)
         self.assertEqual(um.visitdir('dir/subdir/x'), True)
 
+    def testVisitchildrensetIncludeInclude(self):
+        m1 = matchmod.match('', '', include=['path:dir/subdir'])
+        m2 = matchmod.match('', '', include=['rootfilesin:dir'])
+        um = matchmod.unionmatcher([m1, m2])
+        self.assertEqual(um.visitchildrenset('.'), {'dir'})
+        self.assertEqual(um.visitchildrenset('dir'), 'this')
+        self.assertEqual(um.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/foo'), set())
+        self.assertEqual(um.visitchildrenset('folder'), set())
+        # OPT: These next two could be 'all' instead of 'this'.
+        self.assertEqual(um.visitchildrenset('dir/subdir/z'), 'this')
+        self.assertEqual(um.visitchildrenset('dir/subdir/x'), 'this')
+
     # We're using includematcher instead of patterns because it behaves slightly
     # better (giving narrower results) than patternmatcher.
     def testVisitdirIncludeInclude2(self):
@@ -367,6 +665,19 b' class UnionMatcherTests(unittest.TestCas'
         self.assertEqual(um.visitdir('dir/subdir/z'), True)
         self.assertEqual(um.visitdir('dir/subdir/x'), True)
 
+    def testVisitchildrensetIncludeInclude2(self):
+        m1 = matchmod.match('', '', include=['path:dir/subdir'])
+        m2 = matchmod.match('', '', include=['path:folder'])
+        um = matchmod.unionmatcher([m1, m2])
+        self.assertEqual(um.visitchildrenset('.'), {'folder', 'dir'})
+        self.assertEqual(um.visitchildrenset('dir'), {'subdir'})
+        self.assertEqual(um.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/foo'), set())
+        self.assertEqual(um.visitchildrenset('folder'), 'all')
+        # OPT: These next two could be 'all' instead of 'this'.
+        self.assertEqual(um.visitchildrenset('dir/subdir/z'), 'this')
+        self.assertEqual(um.visitchildrenset('dir/subdir/x'), 'this')
+
     # We're using includematcher instead of patterns because it behaves slightly
     # better (giving narrower results) than patternmatcher.
     def testVisitdirIncludeInclude3(self):
@@ -382,6 +693,19 b' class UnionMatcherTests(unittest.TestCas'
         # OPT: this should probably be 'all' not True.
         self.assertEqual(um.visitdir('dir/subdir/z'), True)
 
+    def testVisitchildrensetIncludeInclude3(self):
+        m1 = matchmod.match('', '', include=['path:dir/subdir/x'])
+        m2 = matchmod.match('', '', include=['path:dir/subdir'])
+        um = matchmod.unionmatcher([m1, m2])
+        self.assertEqual(um.visitchildrenset('.'), {'dir'})
+        self.assertEqual(um.visitchildrenset('dir'), {'subdir'})
+        self.assertEqual(um.visitchildrenset('dir/subdir'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/foo'), set())
+        self.assertEqual(um.visitchildrenset('folder'), set())
+        self.assertEqual(um.visitchildrenset('dir/subdir/x'), 'all')
+        # OPT: this should probably be 'all' not 'this'.
+        self.assertEqual(um.visitchildrenset('dir/subdir/z'), 'this')
+
     # We're using includematcher instead of patterns because it behaves slightly
     # better (giving narrower results) than patternmatcher.
     def testVisitdirIncludeInclude4(self):
@@ -397,6 +721,18 b' class UnionMatcherTests(unittest.TestCas'
         self.assertEqual(um.visitdir('dir/subdir/z'), 'all')
         self.assertEqual(um.visitdir('dir/subdir/x'), 'all')
 
+    def testVisitchildrensetIncludeInclude4(self):
+        m1 = matchmod.match('', '', include=['path:dir/subdir/x'])
+        m2 = matchmod.match('', '', include=['path:dir/subdir/z'])
+        um = matchmod.unionmatcher([m1, m2])
+        self.assertEqual(um.visitchildrenset('.'), {'dir'})
+        self.assertEqual(um.visitchildrenset('dir'), {'subdir'})
+        self.assertEqual(um.visitchildrenset('dir/subdir'), {'x', 'z'})
+        self.assertEqual(um.visitchildrenset('dir/foo'), set())
+        self.assertEqual(um.visitchildrenset('folder'), set())
+        self.assertEqual(um.visitchildrenset('dir/subdir/z'), 'all')
+        self.assertEqual(um.visitchildrenset('dir/subdir/x'), 'all')
+
 class SubdirMatcherTests(unittest.TestCase):
 
     def testVisitdir(self):
@@ -410,6 +746,17 b' class SubdirMatcherTests(unittest.TestCa'
         self.assertEqual(sm.visitdir('subdir/z'), True)
         self.assertFalse(sm.visitdir('foo'))
 
+    def testVisitchildrenset(self):
+        m = matchmod.match('', '', include=['path:dir/subdir'])
+        sm = matchmod.subdirmatcher('dir', m)
+
+        self.assertEqual(sm.visitchildrenset('.'), {'subdir'})
+        self.assertEqual(sm.visitchildrenset('subdir'), 'all')
+        # OPT: These next two should probably be 'all' not 'this'.
+        self.assertEqual(sm.visitchildrenset('subdir/x'), 'this')
+        self.assertEqual(sm.visitchildrenset('subdir/z'), 'this')
+        self.assertEqual(sm.visitchildrenset('foo'), set())
+
 class PrefixdirMatcherTests(unittest.TestCase):
 
     def testVisitdir(self):
@@ -444,5 +791,27 b' class PrefixdirMatcherTests(unittest.Tes'
         self.assertEqual(pm.visitdir('d/e/f'), True)
         self.assertEqual(pm.visitdir('d/e/f/g'), False)
 
+    def testVisitchildrenset(self):
+        m = matchmod.match(util.localpath('root/d'), 'e/f',
+                ['../a.txt', 'b.txt'])
+        pm = matchmod.prefixdirmatcher('root', 'd/e/f', 'd', m)
+
+        # OPT: visitchildrenset could possibly return {'e'} and {'f'} for these
+        # next two, respectively; patternmatcher does not have this
+        # optimization.
+        self.assertEqual(m.visitchildrenset('.'), 'this')
+        self.assertEqual(m.visitchildrenset('e'), 'this')
+        self.assertEqual(m.visitchildrenset('e/f'), 'this')
+        self.assertEqual(m.visitchildrenset('e/f/g'), set())
+
+        # OPT: visitchildrenset could possibly return {'d'}, {'e'}, and {'f'}
+        # for these next three, respectively; patternmatcher does not have this
+        # optimization.
+        self.assertEqual(pm.visitchildrenset('.'), 'this')
+        self.assertEqual(pm.visitchildrenset('d'), 'this')
+        self.assertEqual(pm.visitchildrenset('d/e'), 'this')
+        self.assertEqual(pm.visitchildrenset('d/e/f'), 'this')
+        self.assertEqual(pm.visitchildrenset('d/e/f/g'), set())
+
 if __name__ == '__main__':
     silenttestrunner.main(__name__)