match: add visitchildrenset complement to visitdir
authorspectral <spectral@google.com>
Mon, 06 Aug 2018 12:52:33 -0700
changeset 47449 081cc9a95b652cef0ba1be9d37bdfb9338ffa45d
parent 47448 5a7df82de1421a9780e32d7a086741c43d40dbe1
child 47450 a3cabe9415e161f701aeeed978e387747f5abcc8
push id844
push usergszorc@mozilla.com
push dateWed, 08 Aug 2018 16:10:08 +0000
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
tests/test-match.py
--- a/mercurial/match.py
+++ b/mercurial/match.py
@@ -3,16 +3,17 @@
 #  Copyright 2008, 2009 Matt Mackall <mpm@selenic.com> and others
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
 from __future__ import absolute_import, print_function
 
 import copy
+import itertools
 import os
 import re
 
 from .i18n import _
 from . import (
     encoding,
     error,
     pathutil,
@@ -326,16 +327,48 @@ class basematcher(object):
         based on the match's primary, included, and excluded patterns.
 
         Returns the string 'all' if the given directory and all subdirectories
         should be visited. Otherwise returns True or False indicating whether
         the given directory should be visited.
         '''
         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.'''
         return False
 
     def isexact(self):
         '''Matcher will match exactly the list of files in .files() --
         optimization might be possible.'''
@@ -362,16 +395,19 @@ class alwaysmatcher(basematcher):
         return True
 
     def matchfn(self, f):
         return True
 
     def visitdir(self, dir):
         return 'all'
 
+    def visitchildrenset(self, dir):
+        return 'all'
+
     def __repr__(self):
         return r'<alwaysmatcher>'
 
 class nevermatcher(basematcher):
     '''Matches nothing.'''
 
     def __init__(self, root, cwd, badfn=None):
         super(nevermatcher, self).__init__(root, cwd, badfn)
@@ -385,16 +421,19 @@ class nevermatcher(basematcher):
         return True
 
     def prefix(self):
         return True
 
     def visitdir(self, dir):
         return False
 
+    def visitchildrenset(self, dir):
+        return set()
+
     def __repr__(self):
         return r'<nevermatcher>'
 
 class predicatematcher(basematcher):
     """A matcher adapter for a simple boolean function"""
 
     def __init__(self, root, cwd, predfn, predrepr=None, badfn=None):
         super(predicatematcher, self).__init__(root, cwd, badfn)
@@ -425,16 +464,25 @@ class patternmatcher(basematcher):
         if self._prefix and dir in self._fileset:
             return 'all'
         return ('.' in self._fileset or
                 dir in self._fileset or
                 dir in self._dirs or
                 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
 
     @encoding.strmethod
     def __repr__(self):
         return ('<patternmatcher patterns=%r>' % pycompat.bytestr(self._pats))
 
 class includematcher(basematcher):
@@ -459,16 +507,53 @@ class includematcher(basematcher):
             return 'all'
         return ('.' in self._roots or
                 dir in self._roots or
                 dir in self._dirs or
                 dir in self._parents or
                 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))
 
 class exactmatcher(basematcher):
     '''Matches the input files exactly. They are interpreted as paths, not
     patterns (so no kind-prefixes).
     '''
@@ -485,16 +570,35 @@ class exactmatcher(basematcher):
 
     @propertycache
     def _dirs(self):
         return set(util.dirs(self._fileset)) | {'.'}
 
     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
 
     @encoding.strmethod
     def __repr__(self):
         return ('<exactmatcher files=%r>' % self._files)
 
 class differencematcher(basematcher):
@@ -526,16 +630,41 @@ class differencematcher(basematcher):
         # because the "dir" in m1 may not be a file.
         return self._m1.files()
 
     def visitdir(self, dir):
         if self._m2.visitdir(dir) == 'all':
             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()
 
     @encoding.strmethod
     def __repr__(self):
         return ('<differencematcher m1=%r, m2=%r>' % (self._m1, self._m2))
 
 def intersectmatchers(m1, m2):
@@ -590,16 +719,35 @@ class intersectionmatcher(basematcher):
 
     def visitdir(self, dir):
         visit1 = self._m1.visitdir(dir)
         if visit1 == 'all':
             return self._m2.visitdir(dir)
         # 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()
 
     def isexact(self):
         return self._m1.isexact() or self._m2.isexact()
 
     @encoding.strmethod
     def __repr__(self):
@@ -671,16 +819,23 @@ class subdirmatcher(basematcher):
 
     def visitdir(self, dir):
         if dir == '.':
             dir = self._path
         else:
             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
 
     def prefix(self):
         return self._matcher.prefix() and not self._always
 
     @encoding.strmethod
     def __repr__(self):
@@ -743,16 +898,24 @@ class prefixdirmatcher(basematcher):
 
     def visitdir(self, dir):
         if dir == self._path:
             return self._matcher.visitdir('.')
         if dir.startswith(self._pathprefix):
             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()
 
     def prefix(self):
         return self._matcher.prefix()
 
     @encoding.strmethod
     def __repr__(self):
@@ -783,16 +946,35 @@ class unionmatcher(basematcher):
         r = False
         for m in self._matchers:
             v = m.visitdir(dir)
             if v == 'all':
                 return v
             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)
 
 def patkind(pattern, default=None):
     '''If pattern is 'kind:pat' with a known kind, return kind.'''
     return _patsplit(pattern, default)[0]
 
--- a/tests/test-match.py
+++ b/tests/test-match.py
@@ -11,130 +11,231 @@ from mercurial import (
 
 class BaseMatcherTests(unittest.TestCase):
 
     def testVisitdir(self):
         m = matchmod.basematcher('', '')
         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):
         m = matchmod.alwaysmatcher('', '')
         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):
         m = matchmod.nevermatcher('', '')
         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.
 
     def testVisitdir(self):
         m = matchmod.predicatematcher('', '', lambda *a: False)
         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):
         m = matchmod.match('x', '', patterns=['path:dir/subdir'])
         assert isinstance(m, matchmod.patternmatcher)
         self.assertTrue(m.visitdir('.'))
         self.assertTrue(m.visitdir('dir'))
         self.assertEqual(m.visitdir('dir/subdir'), 'all')
         # OPT: This should probably be 'all' if its parent is?
         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)
         self.assertTrue(m.visitdir('.'))
         self.assertFalse(m.visitdir('dir/subdir/x'))
         self.assertFalse(m.visitdir('folder'))
         # FIXME: These should probably be True.
         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)
         self.assertTrue(m.visitdir('.'))
         self.assertTrue(m.visitdir('dir'))
         self.assertFalse(m.visitdir('folder'))
         # OPT: these should probably be False.
         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):
         m = matchmod.match('x', '', include=['path:dir/subdir'])
         assert isinstance(m, matchmod.includematcher)
         self.assertTrue(m.visitdir('.'))
         self.assertTrue(m.visitdir('dir'))
         self.assertEqual(m.visitdir('dir/subdir'), 'all')
         # OPT: This should probably be 'all' if its parent is?
         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)
         self.assertTrue(m.visitdir('.'))
         self.assertTrue(m.visitdir('dir'))
         self.assertTrue(m.visitdir('dir/subdir'))
         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)
         self.assertTrue(m.visitdir('.'))
         self.assertTrue(m.visitdir('dir'))
         self.assertFalse(m.visitdir('folder'))
         # OPT: these should probably be False.
         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):
         m = matchmod.match('x', '', patterns=['dir/subdir/foo.txt'], exact=True)
         assert isinstance(m, matchmod.exactmatcher)
         self.assertTrue(m.visitdir('.'))
         self.assertTrue(m.visitdir('dir'))
         self.assertTrue(m.visitdir('dir/subdir'))
         self.assertFalse(m.visitdir('dir/subdir/foo.txt'))
         self.assertFalse(m.visitdir('dir/foo'))
         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):
         m1 = matchmod.alwaysmatcher('', '')
         m2 = matchmod.alwaysmatcher('', '')
         dm = matchmod.differencematcher(m1, m2)
         # dm should be equivalent to a nevermatcher.
         self.assertFalse(dm.visitdir('.'))
         self.assertFalse(dm.visitdir('dir'))
         self.assertFalse(dm.visitdir('dir/subdir'))
         self.assertFalse(dm.visitdir('dir/subdir/z'))
         self.assertFalse(dm.visitdir('dir/foo'))
         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('', '')
         dm = matchmod.differencematcher(m1, m2)
         # dm should be equivalent to a alwaysmatcher. OPT: if m2 is a
         # nevermatcher, we could return 'all' for these.
         #
         # We're testing Equal-to-True instead of just 'assertTrue' since
@@ -144,32 +245,60 @@ class DifferenceMatcherTests(unittest.Te
         self.assertEqual(dm.visitdir('.'), True)
         self.assertEqual(dm.visitdir('dir'), True)
         self.assertEqual(dm.visitdir('dir/subdir'), True)
         self.assertEqual(dm.visitdir('dir/subdir/z'), True)
         self.assertEqual(dm.visitdir('dir/foo'), True)
         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'])
         dm = matchmod.differencematcher(m1, m2)
         self.assertEqual(dm.visitdir('.'), True)
         self.assertEqual(dm.visitdir('dir'), True)
         self.assertFalse(dm.visitdir('dir/subdir'))
         # OPT: We should probably return False for these; we don't because
         # patternmatcher.visitdir() (our m2) doesn't return 'all' for subdirs of
         # an 'all' pattern, just True.
         self.assertEqual(dm.visitdir('dir/subdir/z'), True)
         self.assertEqual(dm.visitdir('dir/subdir/x'), True)
         # OPT: We could return 'all' for these.
         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):
         m1 = matchmod.match('', '', include=['path:dir/subdir'])
         m2 = matchmod.match('', '', include=['rootfilesin:dir'])
         dm = matchmod.differencematcher(m1, m2)
         self.assertEqual(dm.visitdir('.'), True)
         self.assertEqual(dm.visitdir('dir'), True)
@@ -177,244 +306,462 @@ class DifferenceMatcherTests(unittest.Te
         self.assertFalse(dm.visitdir('dir/foo'))
         self.assertFalse(dm.visitdir('folder'))
         # OPT: We should probably return False for these; we don't because
         # patternmatcher.visitdir() (our m2) doesn't return 'all' for subdirs of
         # an 'all' pattern, just True.
         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):
         m1 = matchmod.alwaysmatcher('', '')
         m2 = matchmod.alwaysmatcher('', '')
         im = matchmod.intersectmatchers(m1, m2)
         # im should be equivalent to a alwaysmatcher.
         self.assertEqual(im.visitdir('.'), 'all')
         self.assertEqual(im.visitdir('dir'), 'all')
         self.assertEqual(im.visitdir('dir/subdir'), 'all')
         self.assertEqual(im.visitdir('dir/subdir/z'), 'all')
         self.assertEqual(im.visitdir('dir/foo'), 'all')
         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('', '')
         im = matchmod.intersectmatchers(m1, m2)
         # im should be equivalent to a nevermatcher.
         self.assertFalse(im.visitdir('.'))
         self.assertFalse(im.visitdir('dir'))
         self.assertFalse(im.visitdir('dir/subdir'))
         self.assertFalse(im.visitdir('dir/subdir/z'))
         self.assertFalse(im.visitdir('dir/foo'))
         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'])
         im = matchmod.intersectmatchers(m1, m2)
         self.assertEqual(im.visitdir('.'), True)
         self.assertEqual(im.visitdir('dir'), True)
         self.assertEqual(im.visitdir('dir/subdir'), 'all')
         self.assertFalse(im.visitdir('dir/foo'))
         self.assertFalse(im.visitdir('folder'))
         # OPT: We should probably return 'all' for these; we don't because
         # patternmatcher.visitdir() (our m2) doesn't return 'all' for subdirs of
         # an 'all' pattern, just True.
         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):
         m1 = matchmod.match('', '', include=['path:dir/subdir'])
         m2 = matchmod.match('', '', include=['rootfilesin:dir'])
         im = matchmod.intersectmatchers(m1, m2)
         self.assertEqual(im.visitdir('.'), True)
         self.assertEqual(im.visitdir('dir'), True)
         self.assertFalse(im.visitdir('dir/subdir'))
         self.assertFalse(im.visitdir('dir/foo'))
         self.assertFalse(im.visitdir('folder'))
         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):
         m1 = matchmod.match('', '', include=['path:dir/subdir'])
         m2 = matchmod.match('', '', include=['path:folder'])
         im = matchmod.intersectmatchers(m1, m2)
         # FIXME: is True correct here?
         self.assertEqual(im.visitdir('.'), True)
         self.assertFalse(im.visitdir('dir'))
         self.assertFalse(im.visitdir('dir/subdir'))
         self.assertFalse(im.visitdir('dir/foo'))
         self.assertFalse(im.visitdir('folder'))
         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):
         m1 = matchmod.match('', '', include=['path:dir/subdir/x'])
         m2 = matchmod.match('', '', include=['path:dir/subdir'])
         im = matchmod.intersectmatchers(m1, m2)
         self.assertEqual(im.visitdir('.'), True)
         self.assertEqual(im.visitdir('dir'), True)
         self.assertEqual(im.visitdir('dir/subdir'), True)
         self.assertFalse(im.visitdir('dir/foo'))
         self.assertFalse(im.visitdir('folder'))
         self.assertFalse(im.visitdir('dir/subdir/z'))
         # 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):
         m1 = matchmod.match('', '', include=['path:dir/subdir/x'])
         m2 = matchmod.match('', '', include=['path:dir/subdir/z'])
         im = matchmod.intersectmatchers(m1, m2)
         # OPT: these next three could probably be False as well.
         self.assertEqual(im.visitdir('.'), True)
         self.assertEqual(im.visitdir('dir'), True)
         self.assertEqual(im.visitdir('dir/subdir'), True)
         self.assertFalse(im.visitdir('dir/foo'))
         self.assertFalse(im.visitdir('folder'))
         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):
         m1 = matchmod.alwaysmatcher('', '')
         m2 = matchmod.alwaysmatcher('', '')
         um = matchmod.unionmatcher([m1, m2])
         # um should be equivalent to a alwaysmatcher.
         self.assertEqual(um.visitdir('.'), 'all')
         self.assertEqual(um.visitdir('dir'), 'all')
         self.assertEqual(um.visitdir('dir/subdir'), 'all')
         self.assertEqual(um.visitdir('dir/subdir/z'), 'all')
         self.assertEqual(um.visitdir('dir/foo'), 'all')
         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('', '')
         um = matchmod.unionmatcher([m1, m2])
         # um should be equivalent to a alwaysmatcher.
         self.assertEqual(um.visitdir('.'), 'all')
         self.assertEqual(um.visitdir('dir'), 'all')
         self.assertEqual(um.visitdir('dir/subdir'), 'all')
         self.assertEqual(um.visitdir('dir/subdir/z'), 'all')
         self.assertEqual(um.visitdir('dir/foo'), 'all')
         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('', '')
         um = matchmod.unionmatcher([m1, m2])
         # um should be equivalent to a alwaysmatcher.
         self.assertEqual(um.visitdir('.'), 'all')
         self.assertEqual(um.visitdir('dir'), 'all')
         self.assertEqual(um.visitdir('dir/subdir'), 'all')
         self.assertEqual(um.visitdir('dir/subdir/z'), 'all')
         self.assertEqual(um.visitdir('dir/foo'), 'all')
         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'])
         um = matchmod.unionmatcher([m1, m2])
         self.assertEqual(um.visitdir('.'), 'all')
         self.assertEqual(um.visitdir('dir'), 'all')
         self.assertEqual(um.visitdir('dir/subdir'), 'all')
         self.assertEqual(um.visitdir('dir/foo'), 'all')
         self.assertEqual(um.visitdir('folder'), 'all')
         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):
         m1 = matchmod.match('', '', include=['path:dir/subdir'])
         m2 = matchmod.match('', '', include=['rootfilesin:dir'])
         um = matchmod.unionmatcher([m1, m2])
         self.assertEqual(um.visitdir('.'), True)
         self.assertEqual(um.visitdir('dir'), True)
         self.assertEqual(um.visitdir('dir/subdir'), 'all')
         self.assertFalse(um.visitdir('dir/foo'))
         self.assertFalse(um.visitdir('folder'))
         # OPT: These two should probably be 'all' not True.
         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):
         m1 = matchmod.match('', '', include=['path:dir/subdir'])
         m2 = matchmod.match('', '', include=['path:folder'])
         um = matchmod.unionmatcher([m1, m2])
         self.assertEqual(um.visitdir('.'), True)
         self.assertEqual(um.visitdir('dir'), True)
         self.assertEqual(um.visitdir('dir/subdir'), 'all')
         self.assertFalse(um.visitdir('dir/foo'))
         self.assertEqual(um.visitdir('folder'), 'all')
         # OPT: These should probably be 'all' not True.
         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):
         m1 = matchmod.match('', '', include=['path:dir/subdir/x'])
         m2 = matchmod.match('', '', include=['path:dir/subdir'])
         um = matchmod.unionmatcher([m1, m2])
         self.assertEqual(um.visitdir('.'), True)
         self.assertEqual(um.visitdir('dir'), True)
         self.assertEqual(um.visitdir('dir/subdir'), 'all')
         self.assertFalse(um.visitdir('dir/foo'))
         self.assertFalse(um.visitdir('folder'))
         self.assertEqual(um.visitdir('dir/subdir/x'), 'all')
         # 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):
         m1 = matchmod.match('', '', include=['path:dir/subdir/x'])
         m2 = matchmod.match('', '', include=['path:dir/subdir/z'])
         um = matchmod.unionmatcher([m1, m2])
         # OPT: these next three could probably be False as well.
         self.assertEqual(um.visitdir('.'), True)
         self.assertEqual(um.visitdir('dir'), True)
         self.assertEqual(um.visitdir('dir/subdir'), True)
         self.assertFalse(um.visitdir('dir/foo'))
         self.assertFalse(um.visitdir('folder'))
         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):
         m = matchmod.match('', '', include=['path:dir/subdir'])
         sm = matchmod.subdirmatcher('dir', m)
 
         self.assertEqual(sm.visitdir('.'), True)
         self.assertEqual(sm.visitdir('subdir'), 'all')
         # OPT: These next two should probably be 'all' not True.
         self.assertEqual(sm.visitdir('subdir/x'), True)
         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):
         m = matchmod.match(util.localpath('root/d'), 'e/f',
                 ['../a.txt', 'b.txt'])
         pm = matchmod.prefixdirmatcher('root', 'd/e/f', 'd', m)
 
         # `m` elides 'd' because it's part of the root, and the rest of the
@@ -439,10 +786,32 @@ class PrefixdirMatcherTests(unittest.Tes
         self.assertEqual(m.visitdir('e/f/g'), False)
 
         self.assertEqual(pm.visitdir('.'), True)
         self.assertEqual(pm.visitdir('d'), True)
         self.assertEqual(pm.visitdir('d/e'), True)
         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__)