Teach skyframe about excluded directories, paths

RecursivePkgFunction now expects both a rooted path to load packages
beneath and a set of paths to exclude. This also augments existing
machinery to deliver this set of paths to exclude.

This leads toward more efficient processing of target patterns in
target pattern sequence evaluation.

--
MOS_MIGRATED_REVID=94020331

1 files changed, 36 insertions, 5 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java
index 11ed3be239..b814319840 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
@@ -20,6 +21,7 @@ import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.PackageIdentifier;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
 import com.google.devtools.build.lib.vfs.Dirent;
 import com.google.devtools.build.lib.vfs.Dirent.Type;
 import com.google.devtools.build.lib.vfs.Path;
@@ -31,6 +33,7 @@ import com.google.devtools.build.skyframe.SkyValue;
 
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 
 import javax.annotation.Nullable;
 
@@ -47,9 +50,11 @@ public class RecursivePkgFunction implements SkyFunction {
 
   @Override
   public SkyValue compute(SkyKey skyKey, Environment env) {
-    RootedPath rootedPath = (RootedPath) skyKey.argument();
+    RecursivePkgKey recursivePkgKey = (RecursivePkgKey) skyKey.argument();
+    RootedPath rootedPath = recursivePkgKey.getRootedPath();
     Path root = rootedPath.getRoot();
     PathFragment rootRelativePath = rootedPath.getRelativePath();
+    Set<PathFragment> excludedPaths = recursivePkgKey.getExcludedPaths();
 
     SkyKey fileKey = FileValue.key(rootedPath);
     FileValue fileValue = (FileValue) env.getValue(fileKey);
@@ -81,14 +86,13 @@ public class RecursivePkgFunction implements SkyFunction {
       if (pkgLookupValue.getRoot().equals(root)) {
         try {
           PackageValue pkgValue = (PackageValue)
-              env.getValueOrThrow(PackageValue.key(packageId),
-                  NoSuchPackageException.class);
+              env.getValueOrThrow(PackageValue.key(packageId), NoSuchPackageException.class);
           if (pkgValue == null) {
             return null;
           }
           packages.add(pkgValue.getPackage().getName());
         } catch (NoSuchPackageException e) {
-          // The package had errors, but don't fail-fast as there might subpackages below the
+          // The package had errors, but don't fail-fast as there might be subpackages below the
           // current directory.
           env.getListener().handle(Event.error(
               "package contains errors: " + rootRelativePath.getPathString()));
@@ -126,8 +130,35 @@ public class RecursivePkgFunction implements SkyFunction {
           && PathPackageLocator.DEFAULT_TOP_LEVEL_EXCLUDES.contains(basename)) {
         continue;
       }
+      PathFragment subdirectory = rootRelativePath.getRelative(basename);
+
+      // If this subdirectory is one of the excluded paths, don't do package lookups in it.
+      if (excludedPaths.contains(subdirectory)) {
+        continue;
+      }
+
+      // If we have an excluded path that isn't below this subdirectory, we shouldn't pass that
+      // excluded path to our recursive package lookup of the subdirectory, because the exclusion
+      // can't possibly match anything beneath the subdirectory.
+      //
+      // For example, if we're currently evaluating directory "a", are looking at its subdirectory
+      // "a/b", and we have an excluded path "a/c/d", there's no need to pass the excluded path
+      // "a/c/d" to our evaluation of "a/b".
+      //
+      // This strategy should help to get more skyframe sharing. Consider the example above. A
+      // subsequent request of "a/b/...", without any excluded paths, will be a cache hit.
+      //
+      // TODO(bazel-team): Replace the excludedPaths set with a trie or a SortedSet for better
+      // efficiency.
+      ImmutableSet.Builder<PathFragment> excludedSubdirectoriesBeneathThisSubdirectory =
+          ImmutableSet.builder();
+      for (PathFragment excludedPath : excludedPaths) {
+        if (excludedPath.startsWith(subdirectory)) {
+          excludedSubdirectoriesBeneathThisSubdirectory.add(excludedPath);
+        }
+      }
       SkyKey req = RecursivePkgValue.key(RootedPath.toRootedPath(root,
-          rootRelativePath.getRelative(basename)));
+          subdirectory), excludedSubdirectoriesBeneathThisSubdirectory.build());
       childDeps.add(req);
     }
     Map<SkyKey, SkyValue> childValueMap = env.getValues(childDeps);