Use WorkspaceNameValue.key() to seed RBuildFile traversals under WORKSPACE file modifications.
Move some RBuildFilesVisitor-specific logic out to that file for better organization and to remove some clutter from SkyQueryEnvironment
PiperOrigin-RevId: 296281889
diff --git a/src/main/java/com/google/devtools/build/lib/query2/ParallelSkyQueryUtils.java b/src/main/java/com/google/devtools/build/lib/query2/ParallelSkyQueryUtils.java
index 9e81dbd..1034dc9 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/ParallelSkyQueryUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/ParallelSkyQueryUtils.java
@@ -154,7 +154,7 @@
/*resultUniquifier=*/ env.createSkyKeyUniquifier(),
context,
callback);
- visitor.visitAndWaitForCompletion(env.getSkyKeysForFileFragments(fileIdentifiers));
+ visitor.visitFileIdentifiersAndWaitForCompletion(env.graph, fileIdentifiers);
}
static QueryTaskFuture<Void> getDepsUnboundedParallel(
diff --git a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java
index 73b638c..819b081 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java
@@ -13,9 +13,15 @@
// limitations under the License.
package com.google.devtools.build.lib.query2;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
+import com.google.common.collect.Multimap;
+import com.google.devtools.build.lib.actions.FileStateValue;
import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.LabelConstants;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
import com.google.devtools.build.lib.packages.Target;
@@ -24,10 +30,21 @@
import com.google.devtools.build.lib.query2.engine.QueryException;
import com.google.devtools.build.lib.query2.engine.QueryExpressionContext;
import com.google.devtools.build.lib.query2.engine.Uniquifier;
+import com.google.devtools.build.lib.rules.repository.WorkspaceFileHelper;
+import com.google.devtools.build.lib.skyframe.ContainingPackageLookupFunction;
+import com.google.devtools.build.lib.skyframe.PackageLookupValue;
+import com.google.devtools.build.lib.skyframe.PackageValue;
import com.google.devtools.build.lib.skyframe.SkyFunctions;
+import com.google.devtools.build.lib.skyframe.WorkspaceNameValue;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.RootedPath;
import com.google.devtools.build.skyframe.SkyFunctionName;
import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+import com.google.devtools.build.skyframe.WalkableGraph;
import java.util.Collection;
+import java.util.HashSet;
+import java.util.Map;
import java.util.Set;
/** A helper class that computes 'rbuildfiles(<blah>)' via BFS. */
@@ -52,6 +69,8 @@
SkyFunctions.PREPARE_DEPS_OF_PATTERN,
SkyFunctions.PREPARE_DEPS_OF_PATTERNS);
+ private static final SkyKey EXTERNAL_PACKAGE_KEY =
+ PackageValue.key(LabelConstants.EXTERNAL_PACKAGE_IDENTIFIER);
private final SkyQueryEnvironment env;
private final QueryExpressionContext<Target> context;
private final Uniquifier<SkyKey> visitUniquifier;
@@ -85,6 +104,13 @@
if (resultUniquifier.unique(rdep)) {
keysToUseForResult.add((PackageIdentifier) rdep.argument());
}
+ // PackageValue(//p) has a transitive dep on the PackageValue(//external), so we need to
+ // make sure these dep paths are traversed. These dep paths go through the singleton
+ // WorkspaceNameValue(), and that node has a direct dep on PackageValue(//external), so it
+ // suffices to ensure we visit PackageValue(//external).
+ if (rdep.equals(EXTERNAL_PACKAGE_KEY)) {
+ keysToVisitNext.add(rdep);
+ }
} else if (!NODES_TO_PRUNE_TRAVERSAL.contains(rdep.functionName())) {
processNonPackageRdepAndDetermineVisitations(rdep, keysToVisitNext, keysToUseForResult);
}
@@ -121,4 +147,102 @@
Iterable<SkyKey> prospectiveVisitationKeys) throws QueryException {
return visitUniquifier.unique(prospectiveVisitationKeys);
}
+
+ /** Initiates the graph visitation algorithm seeded by a set of file paths. */
+ public void visitFileIdentifiersAndWaitForCompletion(
+ WalkableGraph graph, Iterable<PathFragment> fileKeys)
+ throws QueryException, InterruptedException {
+ visitAndWaitForCompletion(getSkyKeysForFileFragments(graph, fileKeys));
+ }
+
+ /**
+ * The passed in {@link PathFragment}s can be associated uniquely to a {@link FileStateValue} with
+ * the following logic (the same logic that's in {@link ContainingPackageLookupFunction}): For
+ * each given file path, we look for the nearest ancestor directory (starting with its parent
+ * directory), if any, that has a package. The {@link PackageLookupValue} for this package tells
+ * us the package root that we should use for the {@link RootedPath} for the {@link
+ * FileStateValue} key.
+ *
+ * <p>For the reverse graph traversal, we are looking for all packages that are transitively
+ * reverse dependencies of those {@link FileStateValue} keys. This function returns a collection
+ * of SkyKeys whose transitive reverse dependencies must contain the exact same set of packages.
+ *
+ * <p>Note that there may not be nodes in the graph corresponding to the returned SkyKeys.
+ */
+ private static Collection<SkyKey> getSkyKeysForFileFragments(
+ WalkableGraph graph, Iterable<PathFragment> pathFragments) throws InterruptedException {
+ Set<SkyKey> result = new HashSet<>();
+ Multimap<PathFragment, PathFragment> currentToOriginal = ArrayListMultimap.create();
+ for (PathFragment pathFragment : pathFragments) {
+ currentToOriginal.put(pathFragment, pathFragment);
+ }
+ while (!currentToOriginal.isEmpty()) {
+ Multimap<SkyKey, PathFragment> packageLookupKeysToOriginal = ArrayListMultimap.create();
+ Multimap<SkyKey, PathFragment> packageLookupKeysToCurrent = ArrayListMultimap.create();
+ for (Map.Entry<PathFragment, PathFragment> entry : currentToOriginal.entries()) {
+ PathFragment current = entry.getKey();
+ PathFragment original = entry.getValue();
+ for (SkyKey packageLookupKey : getPkgLookupKeysForFile(current)) {
+ packageLookupKeysToOriginal.put(packageLookupKey, original);
+ packageLookupKeysToCurrent.put(packageLookupKey, current);
+ }
+
+ // The WORKSPACE file is a transitive dependency of every package. Unfortunately, there is
+ // no specific SkyValue that we can use to figure out under which package path entries it
+ // lives so we add a dependency on the WorkspaceNameValue key.
+ if (original.equals(current) && WorkspaceFileHelper.matchWorkspaceFileName(original)) {
+ // TODO(mschaller): this should not be checked at runtime. These are constants!
+ Preconditions.checkState(
+ LabelConstants.WORKSPACE_FILE_NAME
+ .getParentDirectory()
+ .equals(PathFragment.EMPTY_FRAGMENT),
+ LabelConstants.WORKSPACE_FILE_NAME);
+ result.add(WorkspaceNameValue.key());
+ }
+ }
+ Map<SkyKey, SkyValue> lookupValues =
+ graph.getSuccessfulValues(packageLookupKeysToOriginal.keySet());
+ for (Map.Entry<SkyKey, SkyValue> entry : lookupValues.entrySet()) {
+ SkyKey packageLookupKey = entry.getKey();
+ PackageLookupValue packageLookupValue = (PackageLookupValue) entry.getValue();
+ if (packageLookupValue.packageExists()) {
+ Collection<PathFragment> originalFiles =
+ packageLookupKeysToOriginal.get(packageLookupKey);
+ Preconditions.checkState(!originalFiles.isEmpty(), entry);
+ for (PathFragment fileName : originalFiles) {
+ result.add(
+ FileStateValue.key(
+ RootedPath.toRootedPath(packageLookupValue.getRoot(), fileName)));
+ }
+ for (PathFragment current : packageLookupKeysToCurrent.get(packageLookupKey)) {
+ currentToOriginal.removeAll(current);
+ }
+ }
+ }
+ Multimap<PathFragment, PathFragment> newCurrentToOriginal = ArrayListMultimap.create();
+ for (PathFragment pathFragment : currentToOriginal.keySet()) {
+ PathFragment parent = pathFragment.getParentDirectory();
+ if (parent != null) {
+ newCurrentToOriginal.putAll(parent, currentToOriginal.get(pathFragment));
+ }
+ }
+ currentToOriginal = newCurrentToOriginal;
+ }
+ return result;
+ }
+
+ /**
+ * Returns package lookup keys for looking up the package root for which there may be a relevant
+ * {@link FileStateValue} node in the graph for {@code originalFileFragment}, which is assumed to
+ * be a file path.
+ *
+ * <p>This is a helper function for {@link #getSkyKeysForFileFragments}.
+ */
+ private static Iterable<SkyKey> getPkgLookupKeysForFile(PathFragment currentPathFragment) {
+ PathFragment parentPathFragment = currentPathFragment.getParentDirectory();
+ return parentPathFragment == null
+ ? ImmutableList.of()
+ : ImmutableList.of(
+ PackageLookupValue.key(PackageIdentifier.createInMainRepo(parentPathFragment)));
+ }
}
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 6f5e062..e0ae25c 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
@@ -38,9 +38,7 @@
import com.google.common.util.concurrent.ListeningExecutorService;
import com.google.common.util.concurrent.MoreExecutors;
import com.google.common.util.concurrent.ThreadFactoryBuilder;
-import com.google.devtools.build.lib.actions.FileStateValue;
import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.cmdline.LabelConstants;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.cmdline.TargetParsingException;
import com.google.devtools.build.lib.cmdline.TargetPattern;
@@ -85,11 +83,8 @@
import com.google.devtools.build.lib.query2.engine.ThreadSafeOutputFormatterCallback;
import com.google.devtools.build.lib.query2.engine.Uniquifier;
import com.google.devtools.build.lib.query2.query.BlazeTargetAccessor;
-import com.google.devtools.build.lib.rules.repository.WorkspaceFileHelper;
import com.google.devtools.build.lib.skyframe.BlacklistedPackagePrefixesValue;
-import com.google.devtools.build.lib.skyframe.ContainingPackageLookupFunction;
import com.google.devtools.build.lib.skyframe.GraphBackedRecursivePackageProvider;
-import com.google.devtools.build.lib.skyframe.PackageLookupValue;
import com.google.devtools.build.lib.skyframe.PackageValue;
import com.google.devtools.build.lib.skyframe.PrepareDepsOfPatternsFunction;
import com.google.devtools.build.lib.skyframe.RecursivePackageProviderBackedTargetPatternResolver;
@@ -101,7 +96,6 @@
import com.google.devtools.build.lib.supplier.MemoizingInterruptibleSupplier;
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.PathFragment;
-import com.google.devtools.build.lib.vfs.RootedPath;
import com.google.devtools.build.skyframe.EvaluationContext;
import com.google.devtools.build.skyframe.EvaluationResult;
import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -1211,115 +1205,6 @@
return target;
}
- private static ImmutableList<SkyKey> getDependenciesForWorkspaceFile(
- PathFragment originalFileFragment, PathFragment currentPathFragment) {
- if (originalFileFragment.equals(currentPathFragment)
- && WorkspaceFileHelper.matchWorkspaceFileName(originalFileFragment)) {
- // TODO(mschaller): this should not be checked at runtime. These are constants!
- Preconditions.checkState(
- LabelConstants.WORKSPACE_FILE_NAME
- .getParentDirectory()
- .equals(PathFragment.EMPTY_FRAGMENT),
- LabelConstants.WORKSPACE_FILE_NAME);
- // The WORKSPACE file is a transitive dependency of every package. Unfortunately, there is no
- // specific SkyValue that we can use to figure out under which package path entries it lives,
- // so we add another dependency that's a transitive dependency of every package.
- //
- // The PackageLookupValue for //external is not a good choice, because it's not requested when
- // that package is built so that we can have a directory called external/ in the workspace
- // (this is special-cased in PackageFunction). The principled solution would be to not rely
- // on external/ and introduce a SkyValue for the concept of "the WORKSPACE file of the main
- // repository", but we don't have that yet, so we improvise.
- return ImmutableList.of(PackageValue.key(LabelConstants.EXTERNAL_PACKAGE_IDENTIFIER));
- }
-
- return ImmutableList.of();
- }
-
- /**
- * Returns package lookup keys for looking up the package root for which there may be a relevant
- * (from the perspective of {@link #getRBuildFiles}) {@link FileStateValue} node in the graph for
- * {@code originalFileFragment}, which is assumed to be a file path.
- *
- * <p>This is a helper function for {@link #getSkyKeysForFileFragments}.
- */
- private static Iterable<SkyKey> getPkgLookupKeysForFile(PathFragment currentPathFragment) {
- PathFragment parentPathFragment = currentPathFragment.getParentDirectory();
- return parentPathFragment == null
- ? ImmutableList.of()
- : ImmutableList.of(
- PackageLookupValue.key(PackageIdentifier.createInMainRepo(parentPathFragment)));
- }
-
- /**
- * Returns SkyKeys for which there may be relevant (from the perspective of {@link
- * #getRBuildFiles}) FileStateValues in the graph corresponding to the given {@code
- * pathFragments}, which are assumed to be file paths.
- *
- * <p>The passed in {@link PathFragment}s can be associated uniquely to a {@link FileStateValue}
- * with the following logic (the same logic that's in {@link ContainingPackageLookupFunction}):
- * For each given file path, we look for the nearest ancestor directory (starting with its parent
- * directory), if any, that has a package. The {@link PackageLookupValue} for this package tells
- * us the package root that we should use for the {@link RootedPath} for the {@link
- * FileStateValue} key.
- *
- * <p>For the reverse graph traversal in {@link #getRBuildFiles}, we are looking for all packages
- * that are transitively reverse dependencies of those {@link FileStateValue} keys. This function
- * returns a collection of SkyKeys whose transitive reverse dependencies must contain the exact
- * same set of packages.
- *
- * <p>Note that there may not be nodes in the graph corresponding to the returned SkyKeys.
- */
- protected Collection<SkyKey> getSkyKeysForFileFragments(Iterable<PathFragment> pathFragments)
- throws InterruptedException {
- Set<SkyKey> result = new HashSet<>();
- Multimap<PathFragment, PathFragment> currentToOriginal = ArrayListMultimap.create();
- for (PathFragment pathFragment : pathFragments) {
- currentToOriginal.put(pathFragment, pathFragment);
- }
- while (!currentToOriginal.isEmpty()) {
- Multimap<SkyKey, PathFragment> packageLookupKeysToOriginal = ArrayListMultimap.create();
- Multimap<SkyKey, PathFragment> packageLookupKeysToCurrent = ArrayListMultimap.create();
- for (Map.Entry<PathFragment, PathFragment> entry : currentToOriginal.entries()) {
- PathFragment current = entry.getKey();
- PathFragment original = entry.getValue();
- for (SkyKey packageLookupKey : getPkgLookupKeysForFile(current)) {
- packageLookupKeysToOriginal.put(packageLookupKey, original);
- packageLookupKeysToCurrent.put(packageLookupKey, current);
- }
-
- result.addAll(getDependenciesForWorkspaceFile(original, current));
- }
- Map<SkyKey, SkyValue> lookupValues =
- graph.getSuccessfulValues(packageLookupKeysToOriginal.keySet());
- for (Map.Entry<SkyKey, SkyValue> entry : lookupValues.entrySet()) {
- SkyKey packageLookupKey = entry.getKey();
- PackageLookupValue packageLookupValue = (PackageLookupValue) entry.getValue();
- if (packageLookupValue.packageExists()) {
- Collection<PathFragment> originalFiles =
- packageLookupKeysToOriginal.get(packageLookupKey);
- Preconditions.checkState(!originalFiles.isEmpty(), entry);
- for (PathFragment fileName : originalFiles) {
- result.add(FileStateValue.key(
- RootedPath.toRootedPath(packageLookupValue.getRoot(), fileName)));
- }
- for (PathFragment current : packageLookupKeysToCurrent.get(packageLookupKey)) {
- currentToOriginal.removeAll(current);
- }
- }
- }
- Multimap<PathFragment, PathFragment> newCurrentToOriginal = ArrayListMultimap.create();
- for (PathFragment pathFragment : currentToOriginal.keySet()) {
- PathFragment parent = pathFragment.getParentDirectory();
- if (parent != null) {
- newCurrentToOriginal.putAll(parent, currentToOriginal.get(pathFragment));
- }
- }
- currentToOriginal = newCurrentToOriginal;
- }
- return result;
- }
-
protected Iterable<Target> getBuildFileTargetsForPackageKeys(
Set<PackageIdentifier> pkgIds, QueryExpressionContext<Target> context)
throws QueryException, InterruptedException {
