Split PrepareDepsOfTargetsUnderDirectory into two parts, one which does the directory traversal and package loading, and the other which requests deps on all the transitive targets. We need values from the first half, but the second half can fail to evaluate because of a target cycle. By splitting them, we ensure that there will be values in the graph, so we can get the targets below a directory even if there are cycles present.

--
MOS_MIGRATED_REVID=111609889

7 files changed, 348 insertions, 199 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java
new file mode 100644
index 0000000000..bfa8c1c2ee
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java
@@ -0,0 +1,126 @@
+// Copyright 2016 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.ImmutableCollection;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.analysis.BlazeDirectories;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier.RepositoryName;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+import java.util.Map;
+
+import javax.annotation.Nullable;
+
+/**
+ * <p>Computes {@link CollectPackagesUnderDirectoryValue} which describes whether the directory is a
+ * package and whether non-excluded packages exist below each of the directory's subdirectories. As
+ * a side effect, loads all of these packages, in order to interleave the disk-bound work of
+ * checking for directories and the CPU-bound work of package loading.
+ */
+public class CollectPackagesUnderDirectoryFunction implements SkyFunction {
+  private final BlazeDirectories directories;
+
+  public CollectPackagesUnderDirectoryFunction(BlazeDirectories directories) {
+    this.directories = directories;
+  }
+
+  @Override
+  public SkyValue compute(SkyKey skyKey, Environment env) {
+    return new MyTraversalFunction().visitDirectory((RecursivePkgKey) skyKey.argument(), env);
+  }
+
+  private class MyTraversalFunction
+      extends RecursiveDirectoryTraversalFunction<MyVisitor, CollectPackagesUnderDirectoryValue> {
+
+    private MyTraversalFunction() {
+      super(directories);
+    }
+
+    @Override
+    protected CollectPackagesUnderDirectoryValue getEmptyReturn() {
+      return CollectPackagesUnderDirectoryValue.EMPTY;
+    }
+
+    @Override
+    protected MyVisitor getInitialVisitor() {
+      return new MyVisitor();
+    }
+
+    @Override
+    protected SkyKey getSkyKeyForSubdirectory(
+        RepositoryName repository,
+        RootedPath subdirectory,
+        ImmutableSet<PathFragment> excludedSubdirectoriesBeneathSubdirectory) {
+      return CollectPackagesUnderDirectoryValue.key(
+          repository, subdirectory, excludedSubdirectoriesBeneathSubdirectory);
+    }
+
+    @Override
+    protected CollectPackagesUnderDirectoryValue aggregateWithSubdirectorySkyValues(
+        MyVisitor visitor, Map<SkyKey, SkyValue> subdirectorySkyValues) {
+      // Aggregate the child subdirectory package state.
+      ImmutableMap.Builder<RootedPath, Boolean> builder = ImmutableMap.builder();
+      for (SkyKey key : subdirectorySkyValues.keySet()) {
+        RecursivePkgKey recursivePkgKey = (RecursivePkgKey) key.argument();
+        CollectPackagesUnderDirectoryValue collectPackagesValue =
+            (CollectPackagesUnderDirectoryValue) subdirectorySkyValues.get(key);
+        boolean packagesInSubdirectory = collectPackagesValue.isDirectoryPackage();
+        // If the subdirectory isn't a package, check to see if any of its subdirectories
+        // transitively contain packages.
+        if (!packagesInSubdirectory) {
+          ImmutableCollection<Boolean> subdirectoryValues =
+              collectPackagesValue.getSubdirectoryTransitivelyContainsPackages().values();
+          for (Boolean pkgsInSubSub : subdirectoryValues) {
+            if (pkgsInSubSub) {
+              packagesInSubdirectory = true;
+              break;
+            }
+          }
+        }
+        builder.put(recursivePkgKey.getRootedPath(), packagesInSubdirectory);
+      }
+      return CollectPackagesUnderDirectoryValue.of(visitor.isDirectoryPackage(), builder.build());
+    }
+  }
+
+  private static class MyVisitor implements RecursiveDirectoryTraversalFunction.Visitor {
+
+    private boolean isDirectoryPackage;
+
+    private MyVisitor() {}
+
+    @Override
+    public void visitPackageValue(Package pkg, Environment env) {
+      isDirectoryPackage = true;
+    }
+
+    boolean isDirectoryPackage() {
+      return isDirectoryPackage;
+    }
+  }
+
+  @Nullable
+  @Override
+  public String extractTag(SkyKey skyKey) {
+    return null;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java
new file mode 100644
index 0000000000..3d0b5b6ccd
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java
@@ -0,0 +1,120 @@
+// Copyright 2016 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.MoreObjects;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier.RepositoryName;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+import java.util.Objects;
+
+/**
+ * The value computed by {@link CollectPackagesUnderDirectoryFunction}. Contains a mapping for all
+ * its non-excluded directories to whether there are packages beneath them.
+ *
+ * <p>This value is used by {@link GraphBackedRecursivePackageProvider#getPackagesUnderDirectory}
+ * to help it traverse the graph and find the set of packages under a directory, recursively by
+ * {@link CollectPackagesUnderDirectoryFunction} which computes a value for a directory by
+ * aggregating results calculated from its subdirectories, and by
+ * {@link PrepareDepsOfTargetsUnderDirectoryFunction} which uses this value to find transitive
+ * targets to load.
+ *
+ * <p>Note that even though the {@link CollectPackagesUnderDirectoryFunction} is evaluated in
+ * part because of its side-effects (i.e. loading transitive dependencies of targets), this value
+ * interacts safely with change pruning, despite the fact that this value is a lossy representation
+ * of the packages beneath a directory (i.e. it doesn't care <b>which</b> packages are under a
+ * directory, just whether there are any). When the targets in a package change, the
+ * {@link PackageValue} that {@link CollectPackagesUnderDirectoryFunction} depends on will be
+ * invalidated, and the PrepareDeps function for that package's directory will be reevaluated,
+ * loading any new transitive dependencies. Change pruning may prevent the reevaluation of
+ * PrepareDeps for directories above that one, but they don't need to be re-run.
+ */
+public class CollectPackagesUnderDirectoryValue implements SkyValue {
+  public static final CollectPackagesUnderDirectoryValue EMPTY =
+      new CollectPackagesUnderDirectoryValue(false, ImmutableMap.<RootedPath, Boolean>of());
+
+  private final boolean isDirectoryPackage;
+  private final ImmutableMap<RootedPath, Boolean> subdirectoryTransitivelyContainsPackages;
+
+  private CollectPackagesUnderDirectoryValue(
+      boolean isDirectoryPackage,
+      ImmutableMap<RootedPath, Boolean> subdirectoryTransitivelyContainsPackages) {
+    this.subdirectoryTransitivelyContainsPackages = subdirectoryTransitivelyContainsPackages;
+    this.isDirectoryPackage = isDirectoryPackage;
+  }
+
+  public static CollectPackagesUnderDirectoryValue of(
+      boolean isDirectoryPackage,
+      ImmutableMap<RootedPath, Boolean> subdirectoryTransitivelyContainsPackages) {
+    if (!isDirectoryPackage && subdirectoryTransitivelyContainsPackages.isEmpty()) {
+      return EMPTY;
+    }
+    return new CollectPackagesUnderDirectoryValue(
+        isDirectoryPackage, subdirectoryTransitivelyContainsPackages);
+  }
+
+  public boolean isDirectoryPackage() {
+    return isDirectoryPackage;
+  }
+
+  public ImmutableMap<RootedPath, Boolean> getSubdirectoryTransitivelyContainsPackages() {
+    return subdirectoryTransitivelyContainsPackages;
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(isDirectoryPackage, subdirectoryTransitivelyContainsPackages);
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (!(o instanceof CollectPackagesUnderDirectoryValue)) {
+      return false;
+    }
+    CollectPackagesUnderDirectoryValue that = (CollectPackagesUnderDirectoryValue) o;
+    return this.isDirectoryPackage == that.isDirectoryPackage
+        && this
+            .subdirectoryTransitivelyContainsPackages.equals(
+                that.subdirectoryTransitivelyContainsPackages);
+  }
+
+  @Override
+  public String toString() {
+    return MoreObjects.toStringHelper(this)
+        .add("isDirectoryPackage", isDirectoryPackage)
+        .add("subdirectoryTransitivelyContainsPackages", subdirectoryTransitivelyContainsPackages)
+        .toString();
+  }
+
+  /** Create a collect packages under directory request. */
+  @ThreadSafe
+  static SkyKey key(
+      RepositoryName repository, RootedPath rootedPath, ImmutableSet<PathFragment> excludedPaths) {
+    return key(new RecursivePkgKey(repository, rootedPath, excludedPaths));
+  }
+
+  static SkyKey key(RecursivePkgKey recursivePkgKey) {
+    return new SkyKey(SkyFunctions.COLLECT_PACKAGES_UNDER_DIRECTORY, recursivePkgKey);
+  }
+}
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 f8761ba152..c099dcb88b 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
@@ -34,8 +34,6 @@ import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.packages.Target;
-import com.google.devtools.build.lib.pkgcache.FilteringPolicies;
-import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.pkgcache.RecursivePackageProvider;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
@@ -151,21 +149,23 @@ public final class GraphBackedRecursivePackageProvider implements RecursivePacka
       ImmutableSet<PathFragment> excludedSubdirectories) {
     PathFragment.checkAllPathsAreUnder(excludedSubdirectories, directory);
 
-    // Find the filtering policy of a TargetsBelowDirectory pattern, if any, in the universe that
-    // contains this directory.
-    FilteringPolicy filteringPolicy = null;
+    // Check that this package is covered by at least one of our universe patterns.
+    boolean inUniverse = false;
     for (TargetPatternKey patternKey : universeTargetPatternKeys) {
       TargetPattern pattern = patternKey.getParsedPattern();
       boolean isTBD = pattern.getType().equals(Type.TARGETS_BELOW_DIRECTORY);
       PackageIdentifier packageIdentifier = PackageIdentifier.create(
           repository, directory);
       if (isTBD && pattern.containsBelowDirectory(packageIdentifier)) {
-        filteringPolicy =
-            pattern.getRulesOnly() ? FilteringPolicies.RULES_ONLY : FilteringPolicies.NO_FILTER;
+        inUniverse = true;
         break;
       }
     }
 
+    if (!inUniverse) {
+      return ImmutableList.of();
+    }
+
     List<Path> roots = new ArrayList<>();
     if (repository.isDefault()) {
       roots.addAll(pkgPath.getPathEntries());
@@ -184,27 +184,28 @@ public final class GraphBackedRecursivePackageProvider implements RecursivePacka
     // 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();
-    if (filteringPolicy != null) {
-      for (Path root : roots) {
-        RootedPath rootedDir = RootedPath.toRootedPath(root, directory);
-        TraversalInfo info = new TraversalInfo(rootedDir, excludedSubdirectories);
-        collectPackagesUnder(repository, ImmutableSet.of(info), builder, filteringPolicy);
-      }
+    for (Path root : roots) {
+      RootedPath rootedDir = RootedPath.toRootedPath(root, directory);
+      TraversalInfo info = new TraversalInfo(rootedDir, excludedSubdirectories);
+      collectPackagesUnder(repository, ImmutableSet.of(info), builder);
     }
     return builder.build();
   }
 
-  private void collectPackagesUnder(final RepositoryName repository,
-      Set<TraversalInfo> traversals, ImmutableList.Builder<PathFragment> builder,
-      final FilteringPolicy policy) {
+  private void collectPackagesUnder(
+      final RepositoryName repository,
+      Set<TraversalInfo> traversals,
+      ImmutableList.Builder<PathFragment> builder) {
     Map<TraversalInfo, SkyKey> traversalToKeyMap =
-        Maps.asMap(traversals, new Function<TraversalInfo, SkyKey>() {
-          @Override
-          public SkyKey apply(TraversalInfo traversalInfo) {
-            return PrepareDepsOfTargetsUnderDirectoryValue.key(
-                repository, traversalInfo.rootedDir, traversalInfo.excludedSubdirectories, policy);
-          }
-        });
+        Maps.asMap(
+            traversals,
+            new Function<TraversalInfo, SkyKey>() {
+              @Override
+              public SkyKey apply(TraversalInfo traversalInfo) {
+                return CollectPackagesUnderDirectoryValue.key(
+                    repository, traversalInfo.rootedDir, traversalInfo.excludedSubdirectories);
+              }
+            });
     Map<SkyKey, SkyValue> values = graph.getSuccessfulValues(traversalToKeyMap.values());
 
     ImmutableSet.Builder<TraversalInfo> subdirTraversalBuilder = ImmutableSet.builder();
@@ -212,15 +213,15 @@ public final class GraphBackedRecursivePackageProvider implements RecursivePacka
       TraversalInfo info = entry.getKey();
       SkyKey key = entry.getValue();
       SkyValue val = values.get(key);
-      PrepareDepsOfTargetsUnderDirectoryValue prepDepsValue =
-          (PrepareDepsOfTargetsUnderDirectoryValue) val;
-      if (prepDepsValue != null) {
-        if (prepDepsValue.isDirectoryPackage()) {
+      CollectPackagesUnderDirectoryValue collectPackagesValue =
+          (CollectPackagesUnderDirectoryValue) val;
+      if (collectPackagesValue != null) {
+        if (collectPackagesValue.isDirectoryPackage()) {
           builder.add(info.rootedDir.getRelativePath());
         }
 
         ImmutableMap<RootedPath, Boolean> subdirectoryTransitivelyContainsPackages =
-            prepDepsValue.getSubdirectoryTransitivelyContainsPackages();
+            collectPackagesValue.getSubdirectoryTransitivelyContainsPackages();
         for (RootedPath subdirectory : subdirectoryTransitivelyContainsPackages.keySet()) {
           if (subdirectoryTransitivelyContainsPackages.get(subdirectory)) {
             PathFragment subdirectoryRelativePath = subdirectory.getRelativePath();
@@ -236,7 +237,7 @@ public final class GraphBackedRecursivePackageProvider implements RecursivePacka
 
     ImmutableSet<TraversalInfo> subdirTraversals = subdirTraversalBuilder.build();
     if (!subdirTraversals.isEmpty()) {
-      collectPackagesUnder(repository, subdirTraversals, builder, policy);
+      collectPackagesUnder(repository, subdirTraversals, builder);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java
index ea210047df..e21ce8b2d2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java
@@ -13,11 +13,9 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
-import com.google.devtools.build.lib.analysis.BlazeDirectories;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier.RepositoryName;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
@@ -27,7 +25,6 @@ import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
 import com.google.devtools.build.lib.pkgcache.TargetPatternResolverUtil;
 import com.google.devtools.build.lib.skyframe.PrepareDepsOfTargetsUnderDirectoryValue.PrepareDepsOfTargetsUnderDirectoryKey;
-import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
@@ -35,6 +32,8 @@ import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
+import java.util.ArrayList;
+import java.util.List;
 import java.util.Map;
 
 import javax.annotation.Nullable;
@@ -43,113 +42,74 @@ import javax.annotation.Nullable;
  * Ensures the graph contains the targets in the directory's package, if any, and in the
  * non-excluded packages in its subdirectories, and all those targets' transitive dependencies,
  * after a successful evaluation.
- *
- * <p>Computes {@link PrepareDepsOfTargetsUnderDirectoryValue} which describes whether the
- * directory is a package and how many non-excluded packages exist below each of the directory's
- * subdirectories.
  */
 public class PrepareDepsOfTargetsUnderDirectoryFunction implements SkyFunction {
-  private final BlazeDirectories directories;
-
-  public PrepareDepsOfTargetsUnderDirectoryFunction(BlazeDirectories directories) {
-    this.directories = directories;
-  }
-
   @Override
   public SkyValue compute(SkyKey skyKey, Environment env) {
     PrepareDepsOfTargetsUnderDirectoryKey argument =
         (PrepareDepsOfTargetsUnderDirectoryKey) skyKey.argument();
     FilteringPolicy filteringPolicy = argument.getFilteringPolicy();
-    RecursivePkgKey recursivePkgKey = argument.getRecursivePkgKey();
-    return new MyTraversalFunction(filteringPolicy).visitDirectory(recursivePkgKey, env);
-  }
-
-  private class MyTraversalFunction
-      extends RecursiveDirectoryTraversalFunction<MyVisitor,
-      PrepareDepsOfTargetsUnderDirectoryValue> {
-
-    private final FilteringPolicy filteringPolicy;
-
-    private MyTraversalFunction(FilteringPolicy filteringPolicy) {
-      super(directories);
-      this.filteringPolicy = filteringPolicy;
-    }
-
-    @Override
-    protected PrepareDepsOfTargetsUnderDirectoryValue getEmptyReturn() {
-      return PrepareDepsOfTargetsUnderDirectoryValue.EMPTY;
-    }
-
-    @Override
-    protected MyVisitor getInitialVisitor() {
-      return new MyVisitor(filteringPolicy);
+    CollectPackagesUnderDirectoryValue collectPackagesUnderDirectoryValue =
+        (CollectPackagesUnderDirectoryValue)
+            env.getValue(CollectPackagesUnderDirectoryValue.key(argument.getRecursivePkgKey()));
+    if (env.valuesMissing()) {
+      return null;
     }
-
-    @Override
-    protected SkyKey getSkyKeyForSubdirectory(RepositoryName repository, RootedPath subdirectory,
-        ImmutableSet<PathFragment> excludedSubdirectoriesBeneathSubdirectory) {
-      return PrepareDepsOfTargetsUnderDirectoryValue.key(repository, subdirectory,
-          excludedSubdirectoriesBeneathSubdirectory, filteringPolicy);
-    }
-
-    @Override
-    protected PrepareDepsOfTargetsUnderDirectoryValue aggregateWithSubdirectorySkyValues(
-        MyVisitor visitor, Map<SkyKey, SkyValue> subdirectorySkyValues) {
-      // Aggregate the child subdirectory package state.
-      ImmutableMap.Builder<RootedPath, Boolean> builder = ImmutableMap.builder();
-      for (SkyKey key : subdirectorySkyValues.keySet()) {
-        PrepareDepsOfTargetsUnderDirectoryKey prepDepsKey =
-            (PrepareDepsOfTargetsUnderDirectoryKey) key.argument();
-        PrepareDepsOfTargetsUnderDirectoryValue prepDepsValue =
-            (PrepareDepsOfTargetsUnderDirectoryValue) subdirectorySkyValues.get(key);
-        boolean packagesInSubdirectory = prepDepsValue.isDirectoryPackage();
-        // If the subdirectory isn't a package, check to see if any of its subdirectories
-        // transitively contain packages.
-        if (!packagesInSubdirectory) {
-          ImmutableCollection<Boolean> subdirectoryValues =
-              prepDepsValue.getSubdirectoryTransitivelyContainsPackages().values();
-          for (Boolean pkgsInSubSub : subdirectoryValues) {
-            if (pkgsInSubSub) {
-              packagesInSubdirectory = true;
-              break;
-            }
-          }
-        }
-        builder.put(prepDepsKey.getRecursivePkgKey().getRootedPath(), packagesInSubdirectory);
+    Map<RootedPath, Boolean> subdirMap =
+        collectPackagesUnderDirectoryValue.getSubdirectoryTransitivelyContainsPackages();
+    List<SkyKey> subdirKeys = new ArrayList<>(subdirMap.size());
+    RepositoryName repositoryName = argument.getRecursivePkgKey().getRepository();
+    ImmutableSet<PathFragment> excludedPaths = argument.getRecursivePkgKey().getExcludedPaths();
+
+    PathFragment baseDir = argument.getRecursivePkgKey().getRootedPath().getRelativePath();
+    for (Map.Entry<RootedPath, Boolean> subdirEntry : subdirMap.entrySet()) {
+      if (subdirEntry.getValue()) {
+        // Keep in rough sync with the logic in RecursiveDirectoryTraversalFunction#visitDirectory.
+        RootedPath subdir = subdirEntry.getKey();
+        PathFragment subdirRelativePath = subdir.getRelativePath().relativeTo(baseDir);
+        ImmutableSet<PathFragment> excludedSubdirectoriesBeneathThisSubdirectory =
+            PathFragment.filterPathsStartingWith(excludedPaths, subdirRelativePath);
+
+        subdirKeys.add(
+            PrepareDepsOfTargetsUnderDirectoryValue.key(
+                repositoryName,
+                subdir,
+                excludedSubdirectoriesBeneathThisSubdirectory,
+                filteringPolicy));
       }
-      return PrepareDepsOfTargetsUnderDirectoryValue.of(visitor.isDirectoryPackage(),
-          builder.build());
     }
-  }
-
-  private static class MyVisitor implements RecursiveDirectoryTraversalFunction.Visitor {
-
-    private final FilteringPolicy filteringPolicy;
-    private boolean isDirectoryPackage;
-
-    private MyVisitor(FilteringPolicy filteringPolicy) {
-      this.filteringPolicy = Preconditions.checkNotNull(filteringPolicy);
-    }
-
-    @Override
-    public void visitPackageValue(Package pkg, Environment env) {
-      isDirectoryPackage = true;
-      loadTransitiveTargets(env, pkg, filteringPolicy);
-    }
-
-    public boolean isDirectoryPackage() {
-      return isDirectoryPackage;
+    if (collectPackagesUnderDirectoryValue.isDirectoryPackage()) {
+      PackageIdentifier packageIdentifier =
+          PackageIdentifier.create(
+              argument.getRecursivePkgKey().getRepository(),
+              argument.getRecursivePkgKey().getRootedPath().getRelativePath());
+      PackageValue pkgValue =
+          (PackageValue)
+              Preconditions.checkNotNull(
+                  env.getValue(PackageValue.key(packageIdentifier)),
+                  collectPackagesUnderDirectoryValue);
+      loadTransitiveTargets(env, pkgValue.getPackage(), filteringPolicy, subdirKeys);
+    } else {
+      env.getValues(subdirKeys);
     }
+    return env.valuesMissing() ? null : PrepareDepsOfTargetsUnderDirectoryValue.INSTANCE;
   }
 
-  private static void loadTransitiveTargets(Environment env, Package pkg,
-      FilteringPolicy filteringPolicy) {
+  // The additionalKeysToRequest argument allows us to batch skyframe dependencies a little more
+  // aggressively. Since the keys computed in this method are independent from any other keys, we
+  // can request our keys together with any other keys that are needed, possibly avoiding a restart.
+  private static void loadTransitiveTargets(
+      Environment env,
+      Package pkg,
+      FilteringPolicy filteringPolicy,
+      Iterable<SkyKey> additionalKeysToRequest) {
     ResolvedTargets<Target> packageTargets =
         TargetPatternResolverUtil.resolvePackageTargets(pkg, filteringPolicy);
     ImmutableList.Builder<SkyKey> builder = ImmutableList.builder();
     for (Target target : packageTargets.getTargets()) {
       builder.add(TransitiveTraversalValue.key(target.getLabel()));
     }
+    builder.addAll(additionalKeysToRequest);
     ImmutableList<SkyKey> skyKeys = builder.build();
     env.getValuesOrThrow(skyKeys, NoSuchPackageException.class, NoSuchTargetException.class);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java
index 63064f3827..9b726c3279 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.MoreObjects;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier.RepositoryName;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
@@ -31,85 +30,22 @@ import java.io.Serializable;
 import java.util.Objects;
 
 /**
- * The value computed by {@link PrepareDepsOfTargetsUnderDirectoryFunction}. Contains a mapping for
- * all its non-excluded directories to whether there are packages beneath them.
+ * Dummy value that is the result of {@link PrepareDepsOfTargetsUnderDirectoryFunction}.
  *
- * <p>This value is used by {@link GraphBackedRecursivePackageProvider#getPackagesUnderDirectory}
- * to help it traverse the graph and find the set of packages under a directory, and recursively by
- * {@link PrepareDepsOfTargetsUnderDirectoryFunction} which computes a value for a directory by
- * aggregating results calculated from its subdirectories.
- *
- * <p>Note that even though the {@link PrepareDepsOfTargetsUnderDirectoryFunction} is evaluated in
- * part because of its side-effects (i.e. loading transitive dependencies of targets), this value
- * interacts safely with change pruning, despite the fact that this value is a lossy representation
- * of the packages beneath a directory (i.e. it doesn't care <b>which</b> packages are under a
- * directory, just whether there are any). When the targets in a package change, the
- * {@link PackageValue} that {@link PrepareDepsOfTargetsUnderDirectoryFunction} depends on will be
- * invalidated, and the PrepareDeps function for that package's directory will be reevaluated,
- * loading any new transitive dependencies. Change pruning may prevent the reevaluation of
- * PrepareDeps for directories above that one, but they don't need to be re-run.
+ * <p>Note that even though the {@link PrepareDepsOfTargetsUnderDirectoryFunction} is evaluated
+ * entirely because of its side effects (i.e. loading transitive dependencies of targets), this
+ * value interacts safely with change pruning, despite the fact that this value is a singleton. When
+ * the targets in a package change, the {@link PackageValue} that
+ * {@link PrepareDepsOfTargetsUnderDirectoryFunction} depends on will be invalidated, and the
+ * PrepareDeps function for that package's directory will be re-evaluated, loading any new
+ * transitive dependencies. Change pruning may prevent the re-evaluation of PrepareDeps for
+ * directories above that one, but they don't need to be re-run.
  */
 public final class PrepareDepsOfTargetsUnderDirectoryValue implements SkyValue {
-  public static final PrepareDepsOfTargetsUnderDirectoryValue EMPTY =
-      new PrepareDepsOfTargetsUnderDirectoryValue(false, ImmutableMap.<RootedPath, Boolean>of());
-  public static final PrepareDepsOfTargetsUnderDirectoryValue EMPTY_DIRECTORY_PACKAGE =
-      new PrepareDepsOfTargetsUnderDirectoryValue(true, ImmutableMap.<RootedPath, Boolean>of());
-
-  public static final PrepareDepsOfTargetsUnderDirectoryValue of(boolean isDirectoryPackage,
-      ImmutableMap<RootedPath, Boolean> subdirectoryTransitivelyContainsPackages) {
-    if (subdirectoryTransitivelyContainsPackages.isEmpty()) {
-      if (isDirectoryPackage) {
-        return EMPTY_DIRECTORY_PACKAGE;
-      } else {
-        return EMPTY;
-      }
-    } else {
-      return new PrepareDepsOfTargetsUnderDirectoryValue(
-          isDirectoryPackage, subdirectoryTransitivelyContainsPackages);
-    }
-  }
-
-  private final boolean isDirectoryPackage;
-  private final ImmutableMap<RootedPath, Boolean> subdirectoryTransitivelyContainsPackages;
-
-  private PrepareDepsOfTargetsUnderDirectoryValue(boolean isDirectoryPackage,
-      ImmutableMap<RootedPath, Boolean> subdirectoryTransitivelyContainsPackages) {
-    this.isDirectoryPackage = isDirectoryPackage;
-    this.subdirectoryTransitivelyContainsPackages = Preconditions.checkNotNull(
-        subdirectoryTransitivelyContainsPackages);
-  }
-
-  /** Whether the directory is a package (i.e. contains a BUILD file). */
-  public boolean isDirectoryPackage() {
-    return isDirectoryPackage;
-  }
+  public static final PrepareDepsOfTargetsUnderDirectoryValue INSTANCE =
+      new PrepareDepsOfTargetsUnderDirectoryValue();
 
-  /**
-   * Returns a map from non-excluded immediate subdirectories of this directory to whether there
-   * are non-excluded packages under them.
-   */
-  public ImmutableMap<RootedPath, Boolean> getSubdirectoryTransitivelyContainsPackages() {
-    return subdirectoryTransitivelyContainsPackages;
-  }
-
-  @Override
-  public boolean equals(Object o) {
-    if (this == o) {
-      return true;
-    }
-    if (!(o instanceof PrepareDepsOfTargetsUnderDirectoryValue)) {
-      return false;
-    }
-    PrepareDepsOfTargetsUnderDirectoryValue that = (PrepareDepsOfTargetsUnderDirectoryValue) o;
-    return isDirectoryPackage == that.isDirectoryPackage
-        && Objects.equals(subdirectoryTransitivelyContainsPackages,
-        that.subdirectoryTransitivelyContainsPackages);
-  }
-
-  @Override
-  public int hashCode() {
-    return Objects.hash(isDirectoryPackage, subdirectoryTransitivelyContainsPackages);
-  }
+  private PrepareDepsOfTargetsUnderDirectoryValue() {}
 
   /** Create a prepare deps of targets under directory request. */
   @ThreadSafe
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
index 3ed5488d04..fcccc85791 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
@@ -51,6 +51,8 @@ public final class SkyFunctions {
       SkyFunctionName.create("PREPARE_DEPS_OF_PATTERN");
   public static final SkyFunctionName PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY =
       SkyFunctionName.create("PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY");
+  public static final SkyFunctionName COLLECT_PACKAGES_UNDER_DIRECTORY =
+      SkyFunctionName.create("COLLECT_PACKAGES_UNDER_DIRECTORY");
   public static final SkyFunctionName BLACKLISTED_PACKAGE_PREFIXES =
       SkyFunctionName.create("BLACKLISTED_PACKAGE_PREFIXES");
   public static final SkyFunctionName TEST_SUITE_EXPANSION =
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index d72094201c..f142e75863 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -339,8 +339,12 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
     map.put(SkyFunctions.TARGET_PATTERN, new TargetPatternFunction());
     map.put(SkyFunctions.PREPARE_DEPS_OF_PATTERNS, new PrepareDepsOfPatternsFunction());
     map.put(SkyFunctions.PREPARE_DEPS_OF_PATTERN, new PrepareDepsOfPatternFunction(pkgLocator));
-    map.put(SkyFunctions.PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY,
-        new PrepareDepsOfTargetsUnderDirectoryFunction(directories));
+    map.put(
+        SkyFunctions.PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY,
+        new PrepareDepsOfTargetsUnderDirectoryFunction());
+    map.put(
+        SkyFunctions.COLLECT_PACKAGES_UNDER_DIRECTORY,
+        new CollectPackagesUnderDirectoryFunction(directories));
     map.put(SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES, new BlacklistedPackagePrefixesFunction());
     map.put(SkyFunctions.TESTS_IN_SUITE, new TestsInSuiteFunction());
     map.put(SkyFunctions.TEST_SUITE_EXPANSION, new TestSuiteExpansionFunction());