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
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
index 901e877..3aeda39 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.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.Iterables;
import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.events.EventHandler;
@@ -84,9 +85,11 @@
}
@Override
- public Iterable<PathFragment> getPackagesUnderDirectory(RootedPath directory)
+ public Iterable<PathFragment> getPackagesUnderDirectory(RootedPath directory,
+ ImmutableSet<PathFragment> excludedSubdirectories)
throws MissingDepException {
- RecursivePkgValue lookup = (RecursivePkgValue) env.getValue(RecursivePkgValue.key(directory));
+ RecursivePkgValue lookup = (RecursivePkgValue) env.getValue(
+ RecursivePkgValue.key(directory, excludedSubdirectories));
if (lookup == null) {
// Typically a null value from Environment.getValue(k) means that either the key k is missing
// a dependency or an exception was thrown during evaluation of k. Here, if this getValue
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 0e12f07..d36953f 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
@@ -14,6 +14,7 @@
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.events.Event;
import com.google.devtools.build.lib.events.EventHandler;
@@ -92,8 +93,9 @@
}
@Override
- public Iterable<PathFragment> getPackagesUnderDirectory(RootedPath directory) {
- SkyKey recursivePackageKey = RecursivePkgValue.key(directory);
+ public Iterable<PathFragment> getPackagesUnderDirectory(RootedPath directory,
+ ImmutableSet<PathFragment> excludedSubdirectories) {
+ SkyKey recursivePackageKey = RecursivePkgValue.key(directory, excludedSubdirectories);
if (!graph.exists(recursivePackageKey)) {
// If the recursive package key does not exist in the graph, then it must not correspond to
// any directory transitively containing packages, because the SkyQuery environment has
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
index a1b16f0..8facbe5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.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.devtools.build.lib.cmdline.LabelValidator;
import com.google.devtools.build.lib.cmdline.ResolvedTargets;
import com.google.devtools.build.lib.cmdline.TargetParsingException;
@@ -156,35 +157,32 @@
}
@Override
- public ResolvedTargets<Target> findTargetsBeneathDirectory(
- String originalPattern, String pathPrefix, boolean rulesOnly)
+ public ResolvedTargets<Target> findTargetsBeneathDirectory(String originalPattern,
+ String directory, boolean rulesOnly, ImmutableSet<String> excludedSubdirectories)
throws TargetParsingException, InterruptedException {
FilteringPolicy actualPolicy = rulesOnly
? FilteringPolicies.and(FilteringPolicies.RULES_ONLY, policy)
: policy;
- PathFragment directory = new PathFragment(pathPrefix);
- if (directory.containsUplevelReferences()) {
- throw new TargetParsingException("up-level references are not permitted: '"
- + directory.getPathString() + "'");
- }
- if (!pathPrefix.isEmpty() && (LabelValidator.validatePackageName(pathPrefix) != null)) {
- throw new TargetParsingException("'" + pathPrefix + "' is not a valid package name");
+ PathFragment pathFragment = getPathFragment(directory);
+ ImmutableSet.Builder<PathFragment> excludedPathFragments = ImmutableSet.builder();
+ for (String excludedDirectory : excludedSubdirectories) {
+ excludedPathFragments.add(getPathFragment(excludedDirectory));
}
ResolvedTargets.Builder<Target> builder = ResolvedTargets.builder();
for (Path root : pkgPath.getPathEntries()) {
- RootedPath rootedPath = RootedPath.toRootedPath(root, directory);
+ RootedPath rootedPath = RootedPath.toRootedPath(root, pathFragment);
Iterable<PathFragment> packagesUnderDirectory = recursivePackageProvider
- .getPackagesUnderDirectory(rootedPath);
+ .getPackagesUnderDirectory(rootedPath, excludedPathFragments.build());
for (PathFragment pkg : packagesUnderDirectory) {
builder.merge(getTargetsInPackage(originalPattern, pkg, FilteringPolicies.NO_FILTER));
}
}
if (builder.isEmpty()) {
- throw new TargetParsingException("no targets found beneath '" + directory + "'");
+ throw new TargetParsingException("no targets found beneath '" + pathFragment + "'");
}
// Apply the transform after the check so we only return the
@@ -202,5 +200,16 @@
return filteredBuilder.build();
}
+ private static PathFragment getPathFragment(String pathPrefix) throws TargetParsingException {
+ PathFragment directory = new PathFragment(pathPrefix);
+ if (directory.containsUplevelReferences()) {
+ throw new TargetParsingException("up-level references are not permitted: '"
+ + directory.getPathString() + "'");
+ }
+ if (!pathPrefix.isEmpty() && (LabelValidator.validatePackageName(pathPrefix) != null)) {
+ throw new TargetParsingException("'" + pathPrefix + "' is not a valid package name");
+ }
+ return directory;
+ }
}
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 11ed3be..b814319 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.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 java.util.List;
import java.util.Map;
+import java.util.Set;
import javax.annotation.Nullable;
@@ -47,9 +50,11 @@
@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 @@
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 @@
&& 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);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java
index 4013b90..56ed0e5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java
@@ -13,13 +13,19 @@
// 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.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+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.io.Serializable;
+import java.util.Objects;
+
/**
* This value represents the result of looking up all the packages under a given package path root,
* starting at a given directory.
@@ -38,11 +44,64 @@
* Create a transitive package lookup request.
*/
@ThreadSafe
- public static SkyKey key(RootedPath rootedPath) {
- return new SkyKey(SkyFunctions.RECURSIVE_PKG, rootedPath);
+ public static SkyKey key(RootedPath rootedPath, ImmutableSet<PathFragment> excludedPaths) {
+ return new SkyKey(SkyFunctions.RECURSIVE_PKG, new RecursivePkgKey(rootedPath, excludedPaths));
}
public NestedSet<String> getPackages() {
return packages;
}
+
+ /**
+ * A RecursivePkgKey is a tuple of a {@link RootedPath}, {@code rootedPath}, defining the
+ * directory to recurse beneath in search of packages, and an {@link ImmutableSet} of {@link
+ * PathFragment}s, {@code excludedPaths}, relative to {@code rootedPath.getRoot}, defining the
+ * set of subdirectories beneath {@code rootedPath} to skip.
+ *
+ * <p>Throws {@link IllegalArgumentException} if {@code excludedPaths} contains any paths that
+ * are not beneath {@code rootedPath}.
+ */
+ @ThreadSafe
+ public static final class RecursivePkgKey implements Serializable {
+ private final RootedPath rootedPath;
+ private final ImmutableSet<PathFragment> excludedPaths;
+
+ private RecursivePkgKey(RootedPath rootedPath, ImmutableSet<PathFragment> excludedPaths) {
+ this.rootedPath = Preconditions.checkNotNull(rootedPath);
+ this.excludedPaths = Preconditions.checkNotNull(excludedPaths);
+
+ PathFragment rootedPathFragment = rootedPath.getRelativePath();
+ for (PathFragment excludedPath : excludedPaths) {
+ Preconditions.checkArgument(!excludedPath.equals(rootedPathFragment)
+ && excludedPath.startsWith(rootedPathFragment), "%s is not beneath %s", excludedPath,
+ rootedPathFragment);
+ }
+ }
+
+ public RootedPath getRootedPath() {
+ return rootedPath;
+ }
+
+ public ImmutableSet<PathFragment> getExcludedPaths() {
+ return excludedPaths;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (!(o instanceof RecursivePkgKey)) {
+ return false;
+ }
+
+ RecursivePkgKey that = (RecursivePkgKey) o;
+ return excludedPaths.equals(that.excludedPaths) && rootedPath.equals(that.rootedPath);
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(rootedPath, excludedPaths);
+ }
+ }
}
