diff --git a/mercurial/match.py b/mercurial/match.py
--- a/mercurial/match.py
+++ b/mercurial/match.py
@@ -512,6 +512,50 @@
                 any(parentdir in self._roots
                     for parentdir in util.finddirs(dir)))
 
+    @propertycache
+    def _allparentschildren(matcherself):
+        ret = {}
+        # This is basically a reimplementation of util.dirs that stores the
+        # children instead of just a count of them.
+        class dirchildren(object):
+            def __init__(self, m):
+                self._dirs = {}
+                addpath = self.addpath
+                for f in m:
+                    addpath(f)
+
+            def addpath(self, path):
+                if path == '.':
+                    return
+                dirs = self._dirs
+                findsplitdirs = dirchildren._findsplitdirs
+                for d, b in findsplitdirs(path):
+                    if d not in matcherself._parents:
+                        continue
+                    dirs.setdefault(d, set()).add(b)
+
+            @staticmethod
+            def _findsplitdirs(path):
+                # yields (dirname, basename) tuples, walking back to the root.
+                # This is very similar to util.finddirs, except:
+                #  - produces a (dirname, basename) tuple, not just 'dirname'
+                #  - includes root dir
+                # Unlike manifest._splittopdir, this does not suffix `dirname`
+                # with a slash, and produces '.' for the root instead of ''.
+                oldpos = len(path)
+                pos = path.rfind('/')
+                while pos != -1:
+                    yield path[:pos], path[pos + 1:oldpos]
+                    oldpos = pos
+                    pos = path.rfind('/', 0, pos)
+                yield '.', path[:oldpos]
+
+            def get(self, path):
+                return self._dirs.get(path, set())
+
+        return dirchildren(itertools.chain(
+            matcherself._dirs, matcherself._roots, matcherself._parents))
+
     def visitchildrenset(self, dir):
         if self._prefix and dir in self._roots:
             return 'all'
@@ -524,30 +568,9 @@
                 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
+            return self._allparentschildren.get(dir) or set()
+        return set()
 
     @encoding.strmethod
     def __repr__(self):
@@ -576,7 +599,7 @@
         return dir in self._dirs
 
     def visitchildrenset(self, dir):
-        if dir in self._dirs:
+        if self._fileset and dir in self._dirs:
             candidates = self._dirs - {'.'}
             if dir != '.':
                 d = dir + '/'
@@ -1226,6 +1249,10 @@
     # util.dirs() does not include the root directory, so add it manually
     p.append('.')
 
+    # FIXME: all uses of this function convert these to sets, do so before
+    # returning.
+    # FIXME: all uses of this function do not need anything in 'roots' and
+    # 'dirs' to also be in 'parents', consider removing them before returning.
     return r, d, p
 
 def _explicitfiles(kindpats):