Use a new RecursivePackageProvider to ask skyframe for the correct package nodes in ConfiguredTargetQueryEnvironemnt. This lets us support recursive target patterns with cquery.

PiperOrigin-RevId: 198879650

6 files changed, 325 insertions, 157 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/query2/ConfiguredTargetQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/ConfiguredTargetQueryEnvironment.java
index 345a4bbca8..5cbbe5a080 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/ConfiguredTargetQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/ConfiguredTargetQueryEnvironment.java
@@ -62,6 +62,7 @@ import com.google.devtools.build.lib.skyframe.ConfiguredTargetValue;
 import com.google.devtools.build.lib.skyframe.GraphBackedRecursivePackageProvider;
 import com.google.devtools.build.lib.skyframe.PackageValue;
 import com.google.devtools.build.lib.skyframe.RecursivePackageProviderBackedTargetPatternResolver;
+import com.google.devtools.build.lib.skyframe.RecursivePkgValueRootPackageExtractor;
 import com.google.devtools.build.lib.skyframe.SkyFunctions;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue;
@@ -90,15 +91,14 @@ import javax.annotation.Nullable;
  *
  * <p>This environment can theoretically be used for multiple queries, but currently is only ever
  * used for one over the course of its lifetime. If this ever changed to be used for multiple, the
- * {@link accessor} field should be initialized on a per-query basis not a per-environment basis.
+ * {@link ConfiguredTargetAccessor} field should be initialized on a per-query basis not a
+ * per-environment basis.
  *
- * <p>There is currently a limited way to specify a configuration in the query syntax via
- * {@link ConfigFunction}. This currently still limits the user to choosing the 'target', 'host', or
- * null configurations. It shouldn't be terribly difficult to expand this with
- * {@link OptionsDiffForReconstruction} to handle fully customizable configurations if the need
- * arises in the future.
- *
- * <p>On the other end, recursive target patterns are not supported.
+ * <p>There is currently a limited way to specify a configuration in the query syntax via {@link
+ * ConfigFunction}. This currently still limits the user to choosing the 'target', 'host', or null
+ * configurations. It shouldn't be terribly difficult to expand this with {@link
+ * OptionsDiffForReconstruction} to handle fully customizable configurations if the need arises in
+ * the future.
  *
  * <p>Aspects are also not supported, but probably should be in some fashion.
  */
@@ -219,7 +219,8 @@ public class ConfiguredTargetQueryEnvironment
   private void beforeEvaluateQuery() throws InterruptedException, QueryException {
     graph = walkableGraphSupplier.get();
     GraphBackedRecursivePackageProvider graphBackedRecursivePackageProvider =
-        new GraphBackedRecursivePackageProvider(graph, ALL_PATTERNS, pkgPath);
+        new GraphBackedRecursivePackageProvider(
+            graph, ALL_PATTERNS, pkgPath, new RecursivePkgValueRootPackageExtractor());
     resolver =
         new RecursivePackageProviderBackedTargetPatternResolver(
             graphBackedRecursivePackageProvider,
@@ -627,23 +628,9 @@ public class ConfiguredTargetQueryEnvironment
         configuredTargetKeyExtractor, SkyQueryEnvironment.DEFAULT_THREAD_COUNT);
   }
 
+  /** Target patterns are resolved on the fly so no pre-work to be done here. */
   @Override
-  protected void preloadOrThrow(QueryExpression caller, Collection<String> patterns)
-      throws QueryException, TargetParsingException, InterruptedException {
-    for (String pattern : patterns) {
-      if (TargetPattern.defaultParser()
-          .parse(pattern)
-          .getType()
-          .equals(TargetPattern.Type.TARGETS_BELOW_DIRECTORY)) {
-        // TODO(bazel-team): allow recursive patterns if the pattern is present in the graph? We
-        // could do a mini-eval here to update the graph to contain the necessary nodes for
-        // GraphBackedRecursivePackageProvider, since all the package loading and directory
-        // traversal should already be done.
-        throw new QueryException(
-            "Recursive pattern '" + pattern + "' is not supported in configured target query");
-      }
-    }
-  }
+  protected void preloadOrThrow(QueryExpression caller, Collection<String> patterns) {}
 
   public static QueryOptions parseOptions(String rawOptions) throws QueryException {
     List<String> options = new ArrayList<>(Arrays.asList(rawOptions.split(" ")));
diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index fb2281a2aa..311171cc4a 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -96,6 +96,7 @@ import com.google.devtools.build.lib.skyframe.RecursivePackageProviderBackedTarg
 import com.google.devtools.build.lib.skyframe.TargetPatternValue;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
 import com.google.devtools.build.lib.skyframe.TransitiveTraversalValue;
+import com.google.devtools.build.lib.skyframe.TraversalInfoRootPackageExtractor;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
@@ -254,7 +255,8 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
       graph = result.getWalkableGraph();
       blacklistPatternsSupplier = InterruptibleSupplier.Memoize.of(new BlacklistSupplier(graph));
       graphBackedRecursivePackageProvider =
-          new GraphBackedRecursivePackageProvider(graph, universeTargetPatternKeys, pkgPath);
+          new GraphBackedRecursivePackageProvider(
+              graph, universeTargetPatternKeys, pkgPath, new TraversalInfoRootPackageExtractor());
     }
 
     if (executor == null) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
index aa22453702..18b2c0dd9b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
@@ -13,17 +13,12 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import static com.google.common.collect.ImmutableSet.toImmutableSet;
-
-import com.google.common.base.Function;
-import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
 import com.google.common.base.Throwables;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import com.google.common.collect.Sets.SetView;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
@@ -42,7 +37,6 @@ import com.google.devtools.build.lib.rules.repository.RepositoryDirectoryValue;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
-import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import com.google.devtools.build.skyframe.WalkableGraph;
@@ -61,17 +55,21 @@ import java.util.logging.Logger;
 public final class GraphBackedRecursivePackageProvider extends AbstractRecursivePackageProvider {
 
   private final WalkableGraph graph;
+  private final RootPackageExtractor rootPackageExtractor;
   private final ImmutableList<TargetPatternKey> universeTargetPatternKeys;
 
-  private static final Logger logger = Logger.getLogger(
-      GraphBackedRecursivePackageProvider.class.getName());
+  private static final Logger logger =
+      Logger.getLogger(GraphBackedRecursivePackageProvider.class.getName());
 
-  public GraphBackedRecursivePackageProvider(WalkableGraph graph,
+  public GraphBackedRecursivePackageProvider(
+      WalkableGraph graph,
       ImmutableList<TargetPatternKey> universeTargetPatternKeys,
-      PathPackageLocator pkgPath) {
+      PathPackageLocator pkgPath,
+      RootPackageExtractor rootPackageExtractor) {
     super(pkgPath);
     this.graph = Preconditions.checkNotNull(graph);
     this.universeTargetPatternKeys = Preconditions.checkNotNull(universeTargetPatternKeys);
+    this.rootPackageExtractor = rootPackageExtractor;
   }
 
   @Override
@@ -111,8 +109,13 @@ public final class GraphBackedRecursivePackageProvider extends AbstractRecursive
 
     SetView<SkyKey> unknownKeys = Sets.difference(pkgKeys, packages.keySet());
     if (!Iterables.isEmpty(unknownKeys)) {
-      logger.warning("Unable to find " + unknownKeys + " in the batch lookup of " + pkgKeys
-          + ". Successfully looked up " + packages.keySet());
+      logger.warning(
+          "Unable to find "
+              + unknownKeys
+              + " in the batch lookup of "
+              + pkgKeys
+              + ". Successfully looked up "
+              + packages.keySet());
     }
     for (Map.Entry<SkyKey, Exception> missingOrExceptionEntry :
         graph.getMissingAndExceptions(unknownKeys).entrySet()) {
@@ -158,9 +161,7 @@ public final class GraphBackedRecursivePackageProvider extends AbstractRecursive
     return packageLookupValue.packageExists();
   }
 
-  @Override
-  public Iterable<PathFragment> getPackagesUnderDirectory(
-      ExtendedEventHandler eventHandler,
+  private List<Root> checkValidDirectoryAndGetRoots(
       RepositoryName repository,
       PathFragment directory,
       ImmutableSet<PathFragment> blacklistedSubdirectories,
@@ -203,125 +204,27 @@ public final class GraphBackedRecursivePackageProvider extends AbstractRecursive
       }
       roots.add(Root.fromPath(repositoryValue.getPath()));
     }
-
-    // If we found a TargetsBelowDirectory pattern in the universe that contains this directory,
-    // then we can look for packages in and under it in the graph. If we didn't find one, then the
-    // directory wasn't in the universe, so return an empty list.
-    ImmutableList.Builder<PathFragment> builder = ImmutableList.builder();
-    for (Root root : roots) {
-      RootedPath rootedDir = RootedPath.toRootedPath(root, directory);
-      TraversalInfo info =
-          new TraversalInfo(rootedDir, blacklistedSubdirectories, excludedSubdirectories);
-      collectPackagesUnder(eventHandler, repository, ImmutableSet.of(info), builder);
-    }
-    return builder.build();
+    return roots;
   }
 
-  private void collectPackagesUnder(
+  @Override
+  public Iterable<PathFragment> getPackagesUnderDirectory(
       ExtendedEventHandler eventHandler,
-      final RepositoryName repository,
-      Set<TraversalInfo> traversals,
-      ImmutableList.Builder<PathFragment> builder)
+      RepositoryName repository,
+      PathFragment directory,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
+      ImmutableSet<PathFragment> excludedSubdirectories)
       throws InterruptedException {
-    Map<TraversalInfo, SkyKey> traversalToKeyMap =
-        Maps.asMap(
-            traversals,
-            new Function<TraversalInfo, SkyKey>() {
-              @Override
-              public SkyKey apply(TraversalInfo traversalInfo) {
-                return CollectPackagesUnderDirectoryValue.key(
-                    repository, traversalInfo.rootedDir, traversalInfo.blacklistedSubdirectories);
-              }
-            });
-    Map<SkyKey, SkyValue> values = graph.getSuccessfulValues(traversalToKeyMap.values());
-
-    ImmutableSet.Builder<TraversalInfo> subdirTraversalBuilder = ImmutableSet.builder();
-    for (Map.Entry<TraversalInfo, SkyKey> entry : traversalToKeyMap.entrySet()) {
-      TraversalInfo info = entry.getKey();
-      SkyKey key = entry.getValue();
-      SkyValue val = values.get(key);
-      CollectPackagesUnderDirectoryValue collectPackagesValue =
-          (CollectPackagesUnderDirectoryValue) val;
-      if (collectPackagesValue != null) {
-        if (collectPackagesValue.isDirectoryPackage()) {
-          builder.add(info.rootedDir.getRootRelativePath());
-        }
-
-        if (collectPackagesValue.getErrorMessage() != null) {
-          eventHandler.handle(Event.error(collectPackagesValue.getErrorMessage()));
-        }
-
-        ImmutableMap<RootedPath, Boolean> subdirectoryTransitivelyContainsPackages =
-            collectPackagesValue.getSubdirectoryTransitivelyContainsPackagesOrErrors();
-        for (RootedPath subdirectory : subdirectoryTransitivelyContainsPackages.keySet()) {
-          if (subdirectoryTransitivelyContainsPackages.get(subdirectory)) {
-            PathFragment subdirectoryRelativePath = subdirectory.getRootRelativePath();
-            ImmutableSet<PathFragment> blacklistedSubdirectoriesBeneathThisSubdirectory =
-                info.blacklistedSubdirectories
-                    .stream()
-                    .filter(pathFragment -> pathFragment.startsWith(subdirectoryRelativePath))
-                    .collect(toImmutableSet());
-            ImmutableSet<PathFragment> excludedSubdirectoriesBeneathThisSubdirectory =
-                info.excludedSubdirectories
-                    .stream()
-                    .filter(pathFragment -> pathFragment.startsWith(subdirectoryRelativePath))
-                    .collect(toImmutableSet());
-            if (!excludedSubdirectoriesBeneathThisSubdirectory.contains(subdirectoryRelativePath)) {
-              subdirTraversalBuilder.add(
-                  new TraversalInfo(
-                      subdirectory,
-                      blacklistedSubdirectoriesBeneathThisSubdirectory,
-                      excludedSubdirectoriesBeneathThisSubdirectory));
-            }
-          }
-        }
-      }
-    }
-
-    ImmutableSet<TraversalInfo> subdirTraversals = subdirTraversalBuilder.build();
-    if (!subdirTraversals.isEmpty()) {
-      collectPackagesUnder(eventHandler, repository, subdirTraversals, builder);
-    }
-  }
-
-  private static final class TraversalInfo {
-    private final RootedPath rootedDir;
-    // Set of blacklisted directories. The graph is assumed to be prepopulated with
-    // CollectPackagesUnderDirectoryValue nodes whose keys have blacklisted packages embedded in
-    // them. Therefore, we need to be careful to request and use the same sort of keys here in our
-    // traversal.
-    private final ImmutableSet<PathFragment> blacklistedSubdirectories;
-    // Set of directories, targets under which should be excluded from the traversal results.
-    // Excluded directory information isn't part of the graph keys in the prepopulated graph, so we
-    // need to perform the filtering ourselves.
-    private final ImmutableSet<PathFragment> excludedSubdirectories;
-
-    private TraversalInfo(
-        RootedPath rootedDir,
-        ImmutableSet<PathFragment> blacklistedSubdirectories,
-        ImmutableSet<PathFragment> excludedSubdirectories) {
-      this.rootedDir = rootedDir;
-      this.blacklistedSubdirectories = blacklistedSubdirectories;
-      this.excludedSubdirectories = excludedSubdirectories;
-    }
-
-    @Override
-    public int hashCode() {
-      return Objects.hashCode(rootedDir, blacklistedSubdirectories, excludedSubdirectories);
-    }
-
-    @Override
-    public boolean equals(Object obj) {
-      if (this == obj) {
-        return true;
-      }
-      if (obj instanceof TraversalInfo) {
-        TraversalInfo otherTraversal = (TraversalInfo) obj;
-        return Objects.equal(rootedDir, otherTraversal.rootedDir)
-            && Objects.equal(blacklistedSubdirectories, otherTraversal.blacklistedSubdirectories)
-            && Objects.equal(excludedSubdirectories, otherTraversal.excludedSubdirectories);
-      }
-      return false;
-    }
+    List<Root> roots =
+        checkValidDirectoryAndGetRoots(
+            repository, directory, blacklistedSubdirectories, excludedSubdirectories);
+    return rootPackageExtractor.getPackagesFromRoots(
+        graph,
+        roots,
+        eventHandler,
+        repository,
+        directory,
+        blacklistedSubdirectories,
+        excludedSubdirectories);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValueRootPackageExtractor.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValueRootPackageExtractor.java
new file mode 100644
index 0000000000..3adda7e20f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValueRootPackageExtractor.java
@@ -0,0 +1,71 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.skyframe;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.events.ExtendedEventHandler;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Root;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.WalkableGraph;
+import java.util.LinkedHashSet;
+import java.util.List;
+
+/** Looks up {@link RecursivePkgValue}s of given roots in a {@link WalkableGraph}. */
+public class RecursivePkgValueRootPackageExtractor implements RootPackageExtractor {
+
+  public Iterable<PathFragment> getPackagesFromRoots(
+      WalkableGraph graph,
+      List<Root> roots,
+      ExtendedEventHandler eventHandler,
+      RepositoryName repository,
+      PathFragment directory,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
+      ImmutableSet<PathFragment> excludedSubdirectories)
+      throws InterruptedException {
+    LinkedHashSet<PathFragment> packageNames = new LinkedHashSet<>();
+    for (Root root : roots) {
+      // Note: no need to check if lookup == null because it will never be null.
+      // {@link RecursivePkgFunction} handles all errors in a keep_going build.
+      // In a nokeep_going build, we would never reach this part of the code.
+      RecursivePkgValue lookup =
+          (RecursivePkgValue)
+              graph.getValue(
+                  RecursivePkgValue.key(
+                      repository,
+                      RootedPath.toRootedPath(root, directory),
+                      blacklistedSubdirectories));
+      Preconditions.checkState(
+          lookup != null,
+          "Root %s in repository %s could not be found in the graph.",
+          root.asPath(),
+          repository.getName());
+      for (String packageName : lookup.getPackages()) {
+        // TODO(bazel-team): Make RecursivePkgValue return NestedSet<PathFragment> so this transform
+        // is unnecessary.
+        PathFragment packageNamePathFragment = PathFragment.create(packageName);
+        if (!Iterables.any(
+            excludedSubdirectories,
+            excludedSubdirectory -> packageNamePathFragment.startsWith(excludedSubdirectory))) {
+          packageNames.add(packageNamePathFragment);
+        }
+      }
+    }
+
+    return packageNames;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RootPackageExtractor.java b/src/main/java/com/google/devtools/build/lib/skyframe/RootPackageExtractor.java
new file mode 100644
index 0000000000..553262edc2
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RootPackageExtractor.java
@@ -0,0 +1,35 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.skyframe;
+
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.events.ExtendedEventHandler;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Root;
+import com.google.devtools.build.skyframe.WalkableGraph;
+import java.util.List;
+
+/** An interface for returning recursive packages under a given set of roots. */
+public interface RootPackageExtractor {
+  Iterable<PathFragment> getPackagesFromRoots(
+      WalkableGraph graph,
+      List<Root> roots,
+      ExtendedEventHandler eventHandler,
+      RepositoryName repository,
+      PathFragment directory,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
+      ImmutableSet<PathFragment> excludedSubdirectories)
+      throws InterruptedException;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TraversalInfoRootPackageExtractor.java b/src/main/java/com/google/devtools/build/lib/skyframe/TraversalInfoRootPackageExtractor.java
new file mode 100644
index 0000000000..f5bbfc3c7b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TraversalInfoRootPackageExtractor.java
@@ -0,0 +1,170 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.skyframe;
+
+import static com.google.common.collect.ImmutableSet.toImmutableSet;
+
+import com.google.common.base.Function;
+import com.google.common.base.Objects;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Maps;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.ExtendedEventHandler;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Root;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+import com.google.devtools.build.skyframe.WalkableGraph;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/** Looks up values under {@link TraversalInfo}s of given roots in a {@link WalkableGraph}. */
+public class TraversalInfoRootPackageExtractor implements RootPackageExtractor {
+
+  public Iterable<PathFragment> getPackagesFromRoots(
+      WalkableGraph graph,
+      List<Root> roots,
+      ExtendedEventHandler eventHandler,
+      RepositoryName repository,
+      PathFragment directory,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
+      ImmutableSet<PathFragment> excludedSubdirectories)
+      throws InterruptedException {
+    // If we found a TargetsBelowDirectory pattern in the universe that contains this directory,
+    // then we can look for packages in and under it in the graph. If we didn't find one, then the
+    // directory wasn't in the universe, so return an empty list.
+    ImmutableList.Builder<PathFragment> builder = ImmutableList.builder();
+    for (Root root : roots) {
+      RootedPath rootedDir = RootedPath.toRootedPath(root, directory);
+      TraversalInfo info =
+          new TraversalInfo(rootedDir, blacklistedSubdirectories, excludedSubdirectories);
+      collectPackagesUnder(graph, eventHandler, repository, ImmutableSet.of(info), builder);
+    }
+    return builder.build();
+  }
+
+  private void collectPackagesUnder(
+      WalkableGraph graph,
+      ExtendedEventHandler eventHandler,
+      final RepositoryName repository,
+      Set<TraversalInfo> traversals,
+      ImmutableList.Builder<PathFragment> builder)
+      throws InterruptedException {
+    Map<TraversalInfo, SkyKey> traversalToKeyMap =
+        Maps.asMap(
+            traversals,
+            new Function<TraversalInfo, SkyKey>() {
+              @Override
+              public SkyKey apply(TraversalInfo traversalInfo) {
+                return CollectPackagesUnderDirectoryValue.key(
+                    repository, traversalInfo.rootedDir, traversalInfo.blacklistedSubdirectories);
+              }
+            });
+    Map<SkyKey, SkyValue> values = graph.getSuccessfulValues(traversalToKeyMap.values());
+
+    ImmutableSet.Builder<TraversalInfo> subdirTraversalBuilder = ImmutableSet.builder();
+    for (Map.Entry<TraversalInfo, SkyKey> entry : traversalToKeyMap.entrySet()) {
+      TraversalInfo info = entry.getKey();
+      SkyKey key = entry.getValue();
+      SkyValue val = values.get(key);
+      CollectPackagesUnderDirectoryValue collectPackagesValue =
+          (CollectPackagesUnderDirectoryValue) val;
+      if (collectPackagesValue != null) {
+        if (collectPackagesValue.isDirectoryPackage()) {
+          builder.add(info.rootedDir.getRootRelativePath());
+        }
+
+        if (collectPackagesValue.getErrorMessage() != null) {
+          eventHandler.handle(Event.error(collectPackagesValue.getErrorMessage()));
+        }
+
+        ImmutableMap<RootedPath, Boolean> subdirectoryTransitivelyContainsPackages =
+            collectPackagesValue.getSubdirectoryTransitivelyContainsPackagesOrErrors();
+        for (RootedPath subdirectory : subdirectoryTransitivelyContainsPackages.keySet()) {
+          if (subdirectoryTransitivelyContainsPackages.get(subdirectory)) {
+            PathFragment subdirectoryRelativePath = subdirectory.getRootRelativePath();
+            ImmutableSet<PathFragment> blacklistedSubdirectoriesBeneathThisSubdirectory =
+                info.blacklistedSubdirectories
+                    .stream()
+                    .filter(pathFragment -> pathFragment.startsWith(subdirectoryRelativePath))
+                    .collect(toImmutableSet());
+            ImmutableSet<PathFragment> excludedSubdirectoriesBeneathThisSubdirectory =
+                info.excludedSubdirectories
+                    .stream()
+                    .filter(pathFragment -> pathFragment.startsWith(subdirectoryRelativePath))
+                    .collect(toImmutableSet());
+            if (!excludedSubdirectoriesBeneathThisSubdirectory.contains(subdirectoryRelativePath)) {
+              subdirTraversalBuilder.add(
+                  new TraversalInfo(
+                      subdirectory,
+                      blacklistedSubdirectoriesBeneathThisSubdirectory,
+                      excludedSubdirectoriesBeneathThisSubdirectory));
+            }
+          }
+        }
+      }
+    }
+
+    ImmutableSet<TraversalInfo> subdirTraversals = subdirTraversalBuilder.build();
+    if (!subdirTraversals.isEmpty()) {
+      collectPackagesUnder(graph, eventHandler, repository, subdirTraversals, builder);
+    }
+  }
+
+  private static final class TraversalInfo {
+    private final RootedPath rootedDir;
+    // Set of blacklisted directories. The graph is assumed to be prepopulated with
+    // CollectPackagesUnderDirectoryValue nodes whose keys have blacklisted packages embedded in
+    // them. Therefore, we need to be careful to request and use the same sort of keys here in our
+    // traversal.
+    private final ImmutableSet<PathFragment> blacklistedSubdirectories;
+    // Set of directories, targets under which should be excluded from the traversal results.
+    // Excluded directory information isn't part of the graph keys in the prepopulated graph, so we
+    // need to perform the filtering ourselves.
+    private final ImmutableSet<PathFragment> excludedSubdirectories;
+
+    private TraversalInfo(
+        RootedPath rootedDir,
+        ImmutableSet<PathFragment> blacklistedSubdirectories,
+        ImmutableSet<PathFragment> excludedSubdirectories) {
+      this.rootedDir = rootedDir;
+      this.blacklistedSubdirectories = blacklistedSubdirectories;
+      this.excludedSubdirectories = excludedSubdirectories;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hashCode(rootedDir, blacklistedSubdirectories, excludedSubdirectories);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (this == obj) {
+        return true;
+      }
+      if (obj instanceof TraversalInfo) {
+        TraversalInfo otherTraversal = (TraversalInfo) obj;
+        return Objects.equal(rootedDir, otherTraversal.rootedDir)
+            && Objects.equal(blacklistedSubdirectories, otherTraversal.blacklistedSubdirectories)
+            && Objects.equal(excludedSubdirectories, otherTraversal.excludedSubdirectories);
+      }
+      return false;
+    }
+  }
+}