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/cmdline/TargetPattern.java b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
index ead03af..deeec79 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
@@ -19,6 +19,7 @@
import com.google.common.base.Preconditions;
import com.google.common.base.Splitter;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import com.google.devtools.build.lib.cmdline.LabelValidator.BadLabelException;
import com.google.devtools.build.lib.cmdline.LabelValidator.PackageAndTarget;
@@ -119,7 +120,20 @@
/**
* Evaluates the current target pattern and returns the result.
*/
- public abstract <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver)
+ public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver)
+ throws TargetParsingException, InterruptedException {
+ return eval(resolver, ImmutableSet.<String>of());
+ }
+
+ /**
+ * Evaluates the current target pattern, excluding targets under directories in
+ * {@code excludedSubdirectories}, and returns the result.
+ *
+ * @throws IllegalArgumentException if {@code excludedSubdirectories} is nonempty and this
+ * pattern does not have type {@code Type.TARGETS_BELOW_DIRECTORY}.
+ */
+ public abstract <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver,
+ ImmutableSet<String> excludedSubdirectories)
throws TargetParsingException, InterruptedException;
/**
@@ -153,8 +167,12 @@
}
@Override
- public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver)
+ public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver,
+ ImmutableSet<String> excludedSubdirectories)
throws TargetParsingException, InterruptedException {
+ Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
+ "Target pattern \"%s\" of type %s cannot be evaluated with excluded subdirectories: %s.",
+ targetName, getType(), excludedSubdirectories);
return resolver.getExplicitTarget(targetName);
}
@@ -196,8 +214,12 @@
}
@Override
- public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver)
+ public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver,
+ ImmutableSet<String> excludedSubdirectories)
throws TargetParsingException, InterruptedException {
+ Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
+ "Target pattern \"%s\" of type %s cannot be evaluated with excluded subdirectories: %s.",
+ path, getType(), excludedSubdirectories);
if (resolver.isPackage(path)) {
// User has specified a package name. lookout for default target.
return resolver.getExplicitTarget("//" + path);
@@ -268,8 +290,12 @@
}
@Override
- public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver)
+ public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver,
+ ImmutableSet<String> excludedSubdirectories)
throws TargetParsingException, InterruptedException {
+ Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
+ "Target pattern \"%s\" of type %s cannot be evaluated with excluded subdirectories: %s.",
+ originalPattern, getType(), excludedSubdirectories);
if (checkWildcardConflict) {
ResolvedTargets<T> targets = getWildcardConflict(resolver);
if (targets != null) {
@@ -359,9 +385,11 @@
}
@Override
- public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver)
+ public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver,
+ ImmutableSet<String> excludedSubdirectories)
throws TargetParsingException, InterruptedException {
- return resolver.findTargetsBeneathDirectory(originalPattern, directory, rulesOnly);
+ return resolver.findTargetsBeneathDirectory(originalPattern, directory, rulesOnly,
+ excludedSubdirectories);
}
@Override
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
index ae91caa..3566b23 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
@@ -14,6 +14,8 @@
package com.google.devtools.build.lib.cmdline;
+import com.google.common.collect.ImmutableSet;
+
/**
* A callback interface that is used during the process of converting target patterns (such as
* <code>//foo:all</code>) into one or more lists of targets (such as <code>//foo:foo,
@@ -53,25 +55,30 @@
boolean rulesOnly) throws TargetParsingException, InterruptedException;
/**
- * Returns the set containing the targets found below the given {@code pathPrefix}. Conceptually,
- * this method should look for all packages that start with the {@code pathPrefix} (as a proper
+ * Returns the set containing the targets found below the given {@code directory}. Conceptually,
+ * this method should look for all packages that start with the {@code directory} (as a proper
* prefix directory, i.e., "foo/ba" is not a proper prefix of "foo/bar/"), and then collect all
* targets in each such package (subject to {@code rulesOnly}) as if calling {@link
* #getTargetsInPackage}. The specified directory is not necessarily a valid package name.
*
- * <p>Note that the {@code pathPrefix} can be empty, which corresponds to the "//..." pattern.
- * Implementations may choose not to support this case and throw an exception instead, or may
- * restrict the set of directories that are considered by default.
+ * <p>Note that the {@code directory} can be empty, which corresponds to the "//..." pattern.
+ * Implementations may choose not to support this case and throw an {@link
+ * IllegalArgumentException} exception instead, or may restrict the set of directories that are
+ * considered by default.
*
- * <p>If the {@code pathPrefix} points to a package, then that package should also be part of the
+ * <p>If the {@code directory} points to a package, then that package should also be part of the
* result.
*
* @param originalPattern the original target pattern for error reporting purposes
- * @param pathPrefix the directory in which to look for packages
+ * @param directory the directory in which to look for packages
* @param rulesOnly whether to return rules only
+ * @param excludedSubdirectories a set of transitive subdirectories beneath {@code directory}
+ * to ignore
+ * @throws TargetParsingException under implementation-specific failure conditions
*/
- ResolvedTargets<T> findTargetsBeneathDirectory(String originalPattern, String pathPrefix,
- boolean rulesOnly) throws TargetParsingException, InterruptedException;
+ ResolvedTargets<T> findTargetsBeneathDirectory(String originalPattern, String directory,
+ boolean rulesOnly, ImmutableSet<String> excludedSubdirectories)
+ throws TargetParsingException, InterruptedException;
/**
* Returns true, if and only if the given name corresponds to a package, i.e., a file with the
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
index 5c17e92..96526cc 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
@@ -13,6 +13,7 @@
// limitations under the License.
package com.google.devtools.build.lib.pkgcache;
+import com.google.common.collect.ImmutableSet;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.lib.vfs.RootedPath;
@@ -23,8 +24,10 @@
/**
* Returns the names of all the packages under a given directory.
-
* @param directory a {@link RootedPath} specifying the directory to search
+ * @param excludedSubdirectories a set of {@link PathFragment}s specifying transitive
+ * subdirectories beneath {@code directory} to exclude
*/
- Iterable<PathFragment> getPackagesUnderDirectory(RootedPath directory);
+ Iterable<PathFragment> getPackagesUnderDirectory(RootedPath directory,
+ ImmutableSet<PathFragment> excludedSubdirectories);
}
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);
+ }
+ }
}
