Implement `PackageFunctionWithSingleGlobsDep` so that `PackageFunction` relies on a single GLOBS node
This change adds a new `PackageFunctionWithSingleGlobsDep` class which creates a single GLOBS node to evaluate all package `BUILD` file's glob expression. Bazel adopts this new type of `PackageFunction` so that the number of nodes rdeping on PACKAGE is significantly reduced.
In order to facilitate readability, globbing strategies are renamed to `MULTIPLE_GLOB_HYBRID` (former `SKYFRAME_HYBRID`) and `SINGLE_GLOBS_HYBRID`. The heuristic node dropping logic is also refactored so that PACKAGE dep GLOBS node are removed after PACKAGE evaluation completes.
PiperOrigin-RevId: 629867325
Change-Id: I97c5aa71dc6adc155a1d32adb39c3812877768ba
diff --git a/src/main/java/com/google/devtools/build/lib/includescanning/IncludeParser.java b/src/main/java/com/google/devtools/build/lib/includescanning/IncludeParser.java
index 01a2a40..ecc678a 100644
--- a/src/main/java/com/google/devtools/build/lib/includescanning/IncludeParser.java
+++ b/src/main/java/com/google/devtools/build/lib/includescanning/IncludeParser.java
@@ -338,6 +338,7 @@
containingPackageLookupValue.getContainingPackageName().getPackageFragment();
String pattern = findFilters.get(i);
try {
+ // TODO: b/290998109#comment60 - Convert to create GLOBS node in IncludeParser.
globKeys.add(
GlobValue.key(
containingPackageLookupValue.getContainingPackageName(),
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 8f4fe44..900af32 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
@@ -144,7 +144,8 @@
// globs, but these cannot be included in load statements and so we don't traverse
// through these either.
if (!rdep.functionName().equals(SkyFunctions.PACKAGE_LOOKUP)
- && !rdep.functionName().equals(SkyFunctions.GLOB)) {
+ && !rdep.functionName().equals(SkyFunctions.GLOB)
+ && !rdep.functionName().equals(SkyFunctions.GLOBS)) {
keysToVisitNext.add(rdep);
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BUILD b/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
index 93cd47d..a1eb9d0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
@@ -48,6 +48,7 @@
"LocalRepositoryLookupFunction.java",
"PackageFunction.java",
"PackageFunctionWithMultipleGlobDeps.java",
+ "PackageFunctionWithSingleGlobsDep.java",
"PackageFunctionWithoutGlobDeps.java",
"PrepareDepsOfPatternFunction.java",
"SequencedSkyframeExecutor.java",
@@ -138,6 +139,8 @@
":glob_descriptor",
":glob_function",
":glob_value",
+ ":globs_function",
+ ":globs_value",
":ignored_package_prefixes_function",
":ignored_package_prefixes_value",
":incremental_artifact_conflict_finder",
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GlobsValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/GlobsValue.java
index a19eded..10b9ebb 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GlobsValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GlobsValue.java
@@ -30,6 +30,8 @@
/** {@link SkyValue} corresponding to the computation result of the {@link GlobsFunction}. */
public class GlobsValue implements SkyValue {
+ // TODO: b/290998109 - Storing the matches seem unnecessary except for tests. Consider only
+ // storing `matches` when testing.
private final ImmutableSet<PathFragment> matches;
public GlobsValue(ImmutableSet<PathFragment> matches) {
@@ -195,6 +197,11 @@
}
@Override
+ public boolean skipsBatchPrefetch() {
+ return true;
+ }
+
+ @Override
public SkyFunctionName functionName() {
return SkyFunctions.GLOBS;
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
index 3d88b35..d1152c5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
@@ -241,11 +241,29 @@
* Globs are resolved using {@code PackageFunctionWithMultipleGlobDeps#SkyframeHybridGlobber},
* which declares proper Skyframe dependencies.
*
+ * <p>This strategy is formerly named {@code SKYFRAME_HYBRID}.
+ *
* <p>Use when {@link PackageFunction} will be used to load packages incrementally (e.g. on both
- * clean builds and incremental builds, perhaps with cached globs). This is Bazel's normal
- * use-case.
+ * clean builds and incremental builds, perhaps with cached globs). This used to be Bazel's
+ * normal use-case and still is the preferred strategy if incremental evaluation performance
+ * requirement is strict.
*/
- SKYFRAME_HYBRID,
+ MULTIPLE_GLOB_HYBRID,
+
+ /**
+ * Globs are resolved using {@code PackageFunctionWithSingleGlobsDep#GlobsGlobber}. This
+ * strategy is similar to {@link #MULTIPLE_GLOB_HYBRID} except that there is a single GLOBS
+ * Skyframe dependency including all globs defined in the package's BUILD file.
+ *
+ * <p>The {@code GLOBS} strategy is designed to replace {@code SKYFRAME_HYBRID} as Bazel's
+ * normal use case in that it coarsens the Glob-land subgraph and saving memory without
+ * meaningfully sacrificing performance.
+ *
+ * <p>However, incremental evaluation performance might regress when switching from {@link
+ * #MULTIPLE_GLOB_HYBRID} to {@link #SINGLE_GLOBS_HYBRID}. See {@link GlobFunction} for more
+ * details.
+ */
+ SINGLE_GLOBS_HYBRID,
/**
* Globs are resolved using {@link NonSkyframeGlobber}, which does not declare Skyframe
@@ -277,6 +295,7 @@
@ForOverride
protected abstract void handleGlobDepsAndPropagateFilesystemExceptions(
PackageIdentifier packageIdentifier,
+ Root packageRoot,
LoadedPackage loadedPackage,
Environment env,
boolean packageWasInError)
@@ -516,7 +535,11 @@
try {
handleGlobDepsAndPropagateFilesystemExceptions(
- packageId, state.loadedPackage, env, pkgBuilder.containsErrors());
+ packageId,
+ packageLookupValue.getRoot(),
+ state.loadedPackage,
+ env,
+ pkgBuilder.containsErrors());
} catch (InternalInconsistentFilesystemException e) {
throw e.throwPackageFunctionException();
} catch (FileSymlinkException e) {
@@ -1261,7 +1284,7 @@
private ActionOnIOExceptionReadingBuildFile actionOnIOExceptionReadingBuildFile =
PackageFunction.ActionOnIOExceptionReadingBuildFile.UseOriginalIOException.INSTANCE;
private boolean shouldUseRepoDotBazel = true;
- @Nullable private GlobbingStrategy globbingStrategy = GlobbingStrategy.SKYFRAME_HYBRID;
+ private GlobbingStrategy globbingStrategy = GlobbingStrategy.SINGLE_GLOBS_HYBRID;
private Function<SkyKey, ThreadStateReceiver> threadStateReceiverFactoryForMetrics =
k -> ThreadStateReceiver.NULL_INSTANCE;
private AtomicReference<Semaphore> cpuBoundSemaphore = new AtomicReference<>();
@@ -1336,7 +1359,7 @@
public PackageFunction build() {
switch (globbingStrategy) {
- case SKYFRAME_HYBRID -> {
+ case MULTIPLE_GLOB_HYBRID -> {
return new PackageFunctionWithMultipleGlobDeps(
packageFactory,
pkgLocator,
@@ -1349,6 +1372,19 @@
threadStateReceiverFactoryForMetrics,
cpuBoundSemaphore);
}
+ case SINGLE_GLOBS_HYBRID -> {
+ return new PackageFunctionWithSingleGlobsDep(
+ packageFactory,
+ pkgLocator,
+ showLoadingProgress,
+ numPackagesSuccessfullyLoaded,
+ bzlLoadFunctionForInlining,
+ packageProgress,
+ actionOnIOExceptionReadingBuildFile,
+ shouldUseRepoDotBazel,
+ threadStateReceiverFactoryForMetrics,
+ cpuBoundSemaphore);
+ }
case NON_SKYFRAME -> {
return new PackageFunctionWithoutGlobDeps(
packageFactory,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithMultipleGlobDeps.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithMultipleGlobDeps.java
index e947f0b..b18243d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithMultipleGlobDeps.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithMultipleGlobDeps.java
@@ -60,7 +60,8 @@
* node in the dependency graph.
*
* <p>{@link PackageFunctionWithMultipleGlobDeps} subclass is created when the globbing strategy is
- * {@link com.google.devtools.build.lib.skyframe.PackageFunction.GlobbingStrategy#SKYFRAME_HYBRID} .
+ * {@link
+ * com.google.devtools.build.lib.skyframe.PackageFunction.GlobbingStrategy#MULTIPLE_GLOB_HYBRID}.
* Incremental evaluation adopts {@code SKYFRAME_HYBRID} globbing strategy in order to use the
* unchanged {@link GlobValue} stored in Skyframe when incrementally reloading the package.
*/
@@ -99,6 +100,7 @@
@Override
protected void handleGlobDepsAndPropagateFilesystemExceptions(
PackageIdentifier packageIdentifier,
+ Root packageRoot,
LoadedPackage loadedPackage,
Environment env,
boolean packageWasInError)
@@ -198,7 +200,7 @@
* encountering all glob calls (meaning the real pass can still have the core problem with
* Skyframe restarts).
*/
- private static class SkyframeHybridGlobber implements Globber {
+ private static final class SkyframeHybridGlobber implements Globber {
private final PackageIdentifier packageId;
private final Root packageRoot;
private final Environment env;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithSingleGlobsDep.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithSingleGlobsDep.java
new file mode 100644
index 0000000..f3d8023
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithSingleGlobsDep.java
@@ -0,0 +1,212 @@
+// Copyright 2024 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.ImmutableSet;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.actions.ThreadStateReceiver;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.io.FileSymlinkException;
+import com.google.devtools.build.lib.io.InconsistentFilesystemException;
+import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
+import com.google.devtools.build.lib.packages.CachingPackageLocator;
+import com.google.devtools.build.lib.packages.Globber;
+import com.google.devtools.build.lib.packages.GlobberUtils;
+import com.google.devtools.build.lib.packages.NonSkyframeGlobber;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.PackageFactory;
+import com.google.devtools.build.lib.skyframe.GlobsValue.GlobRequest;
+import com.google.devtools.build.lib.vfs.Root;
+import com.google.devtools.build.skyframe.SkyKey;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Set;
+import java.util.concurrent.Semaphore;
+import java.util.concurrent.atomic.AtomicBoolean;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.function.Function;
+import javax.annotation.Nullable;
+
+/**
+ * Computes the {@link PackageValue} which depends on a single GLOBS node.
+ *
+ * <p>{@link PackageFunctionWithSingleGlobsDep} subclass is created when the globbing strategy is
+ * {@link
+ * com.google.devtools.build.lib.skyframe.PackageFunction.GlobbingStrategy#SINGLE_GLOBS_HYBRID}. All
+ * globs defined in the package's {@code BUILD} file are combined into a single GLOBS node.
+ */
+final class PackageFunctionWithSingleGlobsDep extends PackageFunction {
+
+ PackageFunctionWithSingleGlobsDep(
+ PackageFactory packageFactory,
+ CachingPackageLocator pkgLocator,
+ AtomicBoolean showLoadingProgress,
+ AtomicInteger numPackagesSuccessfullyLoaded,
+ @Nullable BzlLoadFunction bzlLoadFunctionForInlining,
+ @Nullable PackageProgressReceiver packageProgress,
+ ActionOnIOExceptionReadingBuildFile actionOnIoExceptionReadingBuildFile,
+ boolean shouldUseRepoDotBazel,
+ Function<SkyKey, ThreadStateReceiver> threadStateReceiverFactoryForMetrics,
+ AtomicReference<Semaphore> cpuBoundSemaphore) {
+ super(
+ packageFactory,
+ pkgLocator,
+ showLoadingProgress,
+ numPackagesSuccessfullyLoaded,
+ bzlLoadFunctionForInlining,
+ packageProgress,
+ actionOnIoExceptionReadingBuildFile,
+ shouldUseRepoDotBazel,
+ threadStateReceiverFactoryForMetrics,
+ cpuBoundSemaphore);
+ }
+
+ private static final class LoadedPackageWithGlobRequests extends LoadedPackage {
+ private final ImmutableSet<GlobRequest> globRequests;
+
+ private LoadedPackageWithGlobRequests(
+ Package.Builder builder, long loadTimeNanos, ImmutableSet<GlobRequest> globRequests) {
+ super(builder, loadTimeNanos);
+ this.globRequests = globRequests;
+ }
+ }
+
+ /**
+ * Performs non-Skyframe globbing operations and prepares the {@link GlobRequest}s set for
+ * subsequent Skyframe-based globbing.
+ */
+ private static final class GlobsGlobber implements Globber {
+ private final NonSkyframeGlobber nonSkyframeGlobber;
+ private final Set<GlobRequest> globRequests = Sets.newConcurrentHashSet();
+
+ private GlobsGlobber(NonSkyframeGlobber nonSkyframeGlobber) {
+ this.nonSkyframeGlobber = nonSkyframeGlobber;
+ }
+
+ @Override
+ public Token runAsync(
+ List<String> includes, List<String> excludes, Operation operation, boolean allowEmpty)
+ throws BadGlobException {
+ for (String pattern : includes) {
+ try {
+ globRequests.add(GlobRequest.create(pattern, operation));
+ } catch (InvalidGlobPatternException e) {
+ throw new BadGlobException(e.getMessage());
+ }
+ }
+
+ NonSkyframeGlobber.Token nonSkyframeGlobToken =
+ nonSkyframeGlobber.runAsync(includes, excludes, operation, allowEmpty);
+ return new GlobsToken(nonSkyframeGlobToken, operation, allowEmpty);
+ }
+
+ @Override
+ public List<String> fetchUnsorted(Token token)
+ throws BadGlobException, IOException, InterruptedException {
+ Set<String> matches = Sets.newHashSet();
+ matches.addAll(
+ nonSkyframeGlobber.fetchUnsorted(((GlobsToken) token).nonSkyframeGlobberIncludesToken));
+
+ List<String> result = new ArrayList<>(matches);
+ if (!((GlobsToken) token).allowEmpty && result.isEmpty()) {
+ GlobberUtils.throwBadGlobExceptionAllExcluded(((GlobsToken) token).globberOperation);
+ }
+ return result;
+ }
+
+ @Override
+ public void onInterrupt() {
+ nonSkyframeGlobber.onInterrupt();
+ }
+
+ @Override
+ public void onCompletion() {
+ nonSkyframeGlobber.onCompletion();
+ }
+
+ /**
+ * Returns an {@link ImmutableSet} of all package's globs, which will be used to construct
+ * {@link GlobsValue.Key} to be requested in Skyframe downstream.
+ *
+ * <p>An empty {@link ImmutableSet} is returned if there is no glob is defined in the package's
+ * BUILD file. Hence, requesting GLOBS in Skyframe is skipped downstream.
+ */
+ public ImmutableSet<GlobRequest> getGlobRequests() {
+ return ImmutableSet.copyOf(globRequests);
+ }
+
+ private static class GlobsToken extends Globber.Token {
+ private final NonSkyframeGlobber.Token nonSkyframeGlobberIncludesToken;
+ private final Globber.Operation globberOperation;
+ private final boolean allowEmpty;
+
+ private GlobsToken(
+ NonSkyframeGlobber.Token nonSkyframeGlobberIncludesToken,
+ Globber.Operation globberOperation,
+ boolean allowEmpty) {
+ this.nonSkyframeGlobberIncludesToken = nonSkyframeGlobberIncludesToken;
+ this.globberOperation = globberOperation;
+ this.allowEmpty = allowEmpty;
+ }
+ }
+ }
+
+ @Override
+ protected void handleGlobDepsAndPropagateFilesystemExceptions(
+ PackageIdentifier packageIdentifier,
+ Root packageRoot,
+ LoadedPackage loadedPackage,
+ Environment env,
+ boolean packageWasInError)
+ throws InterruptedException, InternalInconsistentFilesystemException, FileSymlinkException {
+ ImmutableSet<GlobRequest> globRequests =
+ ((LoadedPackageWithGlobRequests) loadedPackage).globRequests;
+ if (globRequests.isEmpty()) {
+ return;
+ }
+
+ GlobsValue.Key globsKey = GlobsValue.key(packageIdentifier, packageRoot, globRequests);
+ try {
+ env.getValueOrThrow(globsKey, IOException.class, BuildFileNotFoundException.class);
+ } catch (InconsistentFilesystemException e) {
+ throw new InternalInconsistentFilesystemException(packageIdentifier, e);
+ } catch (FileSymlinkException e) {
+ // Please note that GlobsFunction or its deps FileFunction throws the first
+ // `FileSymlinkException` discovered, which is consistent with how
+ // PackageFunctionWithMultipleGlobDeps#handleGlobDepsAndPropagateFilesystemExceptions handles
+ // FileSymlinkException caught.
+ throw e;
+ } catch (IOException | BuildFileNotFoundException e) {
+ maybeThrowFilesystemInconsistency(packageIdentifier, e, packageWasInError);
+ }
+ }
+
+ @Override
+ protected GlobsGlobber makeGlobber(
+ NonSkyframeGlobber nonSkyframeGlobber,
+ PackageIdentifier packageId,
+ Root packageRoot,
+ Environment env) {
+ return new GlobsGlobber(nonSkyframeGlobber);
+ }
+
+ @Override
+ protected LoadedPackage newLoadedPackage(
+ Package.Builder packageBuilder, @Nullable Globber globber, long loadTimeNanos) {
+ return new LoadedPackageWithGlobRequests(
+ packageBuilder, loadTimeNanos, ((GlobsGlobber) globber).getGlobRequests());
+ }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithoutGlobDeps.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithoutGlobDeps.java
index dc4aae4..e679522 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithoutGlobDeps.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunctionWithoutGlobDeps.java
@@ -71,6 +71,7 @@
@Override
protected void handleGlobDepsAndPropagateFilesystemExceptions(
PackageIdentifier packageIdentifier,
+ Root packageRoot,
LoadedPackage loadedPackage,
Environment env,
boolean packageWasInError) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index 463dfc0..faade35 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -168,7 +168,8 @@
ActionOnIOExceptionReadingBuildFile actionOnIOExceptionReadingBuildFile,
boolean shouldUseRepoDotBazel,
SkyKeyStateReceiver skyKeyStateReceiver,
- BugReporter bugReporter) {
+ BugReporter bugReporter,
+ boolean globUnderSingleDep) {
super(
skyframeExecutorConsumerOnInit,
pkgFactory,
@@ -193,7 +194,8 @@
diffAwarenessFactories,
workspaceInfoFromDiffReceiver,
new SequencedRecordingDifferencer(),
- repositoryHelpersHolder);
+ repositoryHelpersHolder,
+ globUnderSingleDep);
}
@Override
@@ -804,6 +806,7 @@
private BugReporter bugReporter = BugReporter.defaultInstance();
private SkyKeyStateReceiver skyKeyStateReceiver = SkyKeyStateReceiver.NULL_INSTANCE;
private SyscallCache syscallCache = null;
+ private boolean globUnderSingleDep = true;
private Builder() {}
@@ -839,7 +842,8 @@
actionOnIOExceptionReadingBuildFile,
shouldUseRepoDotBazel,
skyKeyStateReceiver,
- bugReporter);
+ bugReporter,
+ globUnderSingleDep);
skyframeExecutor.init();
return skyframeExecutor;
}
@@ -964,5 +968,11 @@
this.syscallCache = syscallCache;
return this;
}
+
+ @CanIgnoreReturnValue
+ public Builder setGlobUnderSingleDep(boolean globUnderSingleDep) {
+ this.globUnderSingleDep = globUnderSingleDep;
+ return this;
+ }
}
}
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 b007535..ff01086 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
@@ -494,6 +494,13 @@
private SkyfocusState skyfocusState = SkyfocusState.DISABLED;
+ /**
+ * Determines the type of hybrid globbing strategy to use when {@link
+ * #tracksStateForIncrementality()} is {@code true}. See {@link #getGlobbingStrategy()} for more
+ * details.
+ */
+ private final boolean globUnderSingleDep;
+
// Leaf keys to be kept regardless of the working set.
private static final ImmutableSet<SkyKey> INCLUDE_KEYS_FOR_SKYFOCUS_IF_EXIST =
ImmutableSet.of(
@@ -552,7 +559,8 @@
@Nullable Iterable<? extends DiffAwareness.Factory> diffAwarenessFactories,
@Nullable WorkspaceInfoFromDiffReceiver workspaceInfoFromDiffReceiver,
@Nullable RecordingDifferencer recordingDiffer,
- @Nullable SkyframeExecutorRepositoryHelpersHolder repositoryHelpersHolder) {
+ @Nullable SkyframeExecutorRepositoryHelpersHolder repositoryHelpersHolder,
+ boolean globUnderSingleDep) {
// Strictly speaking, these arguments are not required for initialization, but all current
// callsites have them at hand, so we might as well set them during construction.
this.skyframeExecutorConsumerOnInit = skyframeExecutorConsumerOnInit;
@@ -607,6 +615,7 @@
this.workspaceInfoFromDiffReceiver = workspaceInfoFromDiffReceiver;
this.recordingDiffer = recordingDiffer;
this.repositoryHelpersHolder = repositoryHelpersHolder;
+ this.globUnderSingleDep = globUnderSingleDep;
}
private ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions() {
@@ -650,6 +659,7 @@
map.put(SkyFunctions.BZL_LOAD, newBzlLoadFunction(ruleClassProvider));
this.globFunction = newGlobFunction();
map.put(SkyFunctions.GLOB, this.globFunction);
+ map.put(SkyFunctions.GLOBS, new GlobsFunction());
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));
@@ -1009,7 +1019,6 @@
try {
memoizingEvaluator.noteEvaluationsAtSameVersionMayBeFinished(eventHandler);
} finally {
- progressReceiver.globDeps = new ConcurrentHashMap<>();
globFunction.complete();
clearSyscallCache();
// So that the supplier object can be GC-ed.
@@ -1070,9 +1079,12 @@
@ForOverride
protected GlobbingStrategy getGlobbingStrategy() {
- return tracksStateForIncrementality()
- ? GlobbingStrategy.SKYFRAME_HYBRID
- : GlobbingStrategy.NON_SKYFRAME;
+ if (tracksStateForIncrementality()) {
+ return globUnderSingleDep
+ ? GlobbingStrategy.SINGLE_GLOBS_HYBRID
+ : GlobbingStrategy.MULTIPLE_GLOB_HYBRID;
+ }
+ return GlobbingStrategy.NON_SKYFRAME;
}
/**
@@ -2947,13 +2959,6 @@
/** This receiver is only needed for execution, so it is null otherwise. */
@Nullable private EvaluationProgressReceiver executionProgressReceiver = null;
- // In non-incremental builds, we want to remove the glob subgraph after the rdep PACKAGE is
- // done. However, edges are not stored. So, we use the `globDeps` map to temporarily store the
- // relationship between GLOB and their dependent GLOBs.
- // After the rdep PACKAGE has been evaluated, all direct or transitive dependent GLOBs will be
- // recursively removed from both the in-memory graph and `globDeps` map.
- private Map<GlobDescriptor, ImmutableList<GlobDescriptor>> globDeps = new ConcurrentHashMap<>();
-
@Override
public void dirtied(SkyKey skyKey, DirtyType dirtyType) {
if (ignoreInvalidations) {
@@ -3062,30 +3067,21 @@
}
}
- if (!heuristicallyDropNodes || directDeps == null) {
+ if (!heuristicallyDropNodes
+ || directDeps == null
+ || !getGlobbingStrategy().equals(GlobbingStrategy.SINGLE_GLOBS_HYBRID)) {
+ // `--heuristically_drop_nodes` is only meaningful when this is a non-incremental build with
+ // SINGLE_GLOBS_HYBRID strategy.
return;
}
- if (skyKey.functionName().equals(SkyFunctions.GLOB)) {
- checkState(!globDeps.containsKey(skyKey), skyKey);
- ImmutableList.Builder<GlobDescriptor> directDepGlobsBuilder = ImmutableList.builder();
- for (SkyKey dep : directDeps.getAllElementsAsIterable()) {
- if (dep.functionName().equals(SkyFunctions.GLOB)) {
- checkArgument(dep instanceof GlobDescriptor, dep);
- directDepGlobsBuilder.add((GlobDescriptor) dep);
- }
- }
-
- ImmutableList<GlobDescriptor> directDepGlobs = directDepGlobsBuilder.build();
- if (!directDepGlobs.isEmpty()) {
- globDeps.put((GlobDescriptor) skyKey, directDepGlobs);
- }
- }
-
+ // With non-incremental build, edges are not stored. So GLOBS node will not be useful anymore
+ // after PACKAGE evaluation completes, making it safe to be removed.
+ // See `SequencedSkyframeExecutor#decideKeepIncrementalState()` and b/261019506#comment1.
if (skyKey.functionName().equals(SkyFunctions.PACKAGE)) {
for (SkyKey dep : directDeps.getAllElementsAsIterable()) {
- if (dep.functionName().equals(SkyFunctions.GLOB)) {
- recursivelyRemoveGlobFromGraph((GlobDescriptor) dep);
+ if (dep.functionName().equals(SkyFunctions.GLOBS)) {
+ memoizingEvaluator.getInMemoryGraph().remove(dep);
}
}
}
@@ -3117,16 +3113,6 @@
}
}
}
-
- private void recursivelyRemoveGlobFromGraph(GlobDescriptor root) {
- memoizingEvaluator.getInMemoryGraph().remove(root);
- ImmutableList<GlobDescriptor> adjacentDeps = globDeps.remove(root);
- if (adjacentDeps != null) {
- for (GlobDescriptor nextLevelDep : adjacentDeps) {
- recursivelyRemoveGlobFromGraph(nextLevelDep);
- }
- }
- }
}
public final ExecutionFinishedEvent createExecutionFinishedEvent() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkymeldInconsistencyReceiver.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkymeldInconsistencyReceiver.java
index c25984e..a45c80b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkymeldInconsistencyReceiver.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkymeldInconsistencyReceiver.java
@@ -28,6 +28,8 @@
* pre-execution nodes in Skymeld mode.
*/
public class SkymeldInconsistencyReceiver implements GraphInconsistencyReceiver {
+ // TODO: b/290998109#comment60 - After the GLOB nodes are replaced by GLOBS, the missing children
+ // below might be unexpected.
private static final ImmutableMap<SkyFunctionName, SkyFunctionName>
SKYMELD_EXPECTED_MISSING_CHILDREN =
ImmutableMap.of(
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
index 84bafd2..f1bef1e 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
@@ -253,19 +253,35 @@
}
@Before
- public final void initializeSkyframeExecutor() throws Exception {
- initializeSkyframeExecutor(/*doPackageLoadingChecks=*/ true);
+ public void initializeSkyframeExecutor() throws Exception {
+ initializeSkyframeExecutor(/* doPackageLoadingChecks= */ true);
}
public void initializeSkyframeExecutor(boolean doPackageLoadingChecks) throws Exception {
initializeSkyframeExecutor(
- /*doPackageLoadingChecks=*/ doPackageLoadingChecks,
- /*diffAwarenessFactories=*/ ImmutableList.of());
+ /* doPackageLoadingChecks= */ doPackageLoadingChecks,
+ /* diffAwarenessFactories= */ ImmutableList.of(),
+ /* globUnderSingleDep= */ true);
}
public void initializeSkyframeExecutor(
boolean doPackageLoadingChecks, ImmutableList<DiffAwareness.Factory> diffAwarenessFactories)
throws Exception {
+ initializeSkyframeExecutor(
+ doPackageLoadingChecks, diffAwarenessFactories, /* globUnderSingleDep= */ true);
+ }
+
+ /**
+ * Only {@link com.google.devtools.build.lib.skyframe.PackageFunctionTest} still covers testing
+ * Skyframe Hybrid globbing by passing in the test parameter globUnderSingleDep.
+ *
+ * <p>All other tests adopt GLOBS strategy by setting {@code globUnderSingleDep} to {@code true}.
+ */
+ public void initializeSkyframeExecutor(
+ boolean doPackageLoadingChecks,
+ ImmutableList<DiffAwareness.Factory> diffAwarenessFactories,
+ boolean globUnderSingleDep)
+ throws Exception {
analysisMock = getAnalysisMock();
directories =
new BlazeDirectories(
@@ -320,6 +336,7 @@
.setSyscallCache(SyscallCache.NO_CACHE)
.setDiffAwarenessFactories(diffAwarenessFactories)
.setRepositoryHelpersHolder(getRepositoryHelpersHolder())
+ .setGlobUnderSingleDep(globUnderSingleDep)
.build();
if (usesInliningBzlLoadFunction()) {
injectInliningBzlLoadFunction(skyframeExecutor, ruleClassProvider, directories);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/BUILD b/src/test/java/com/google/devtools/build/lib/skyframe/BUILD
index cb69c03..a79889e 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/BUILD
@@ -225,6 +225,7 @@
"//src/main/java/com/google/devtools/build/lib/skyframe:diff_awareness_manager",
"//src/main/java/com/google/devtools/build/lib/skyframe:directory_listing_function",
"//src/main/java/com/google/devtools/build/lib/skyframe:directory_listing_state_value",
+ "//src/main/java/com/google/devtools/build/lib/skyframe:directory_listing_value",
"//src/main/java/com/google/devtools/build/lib/skyframe:directory_tree_digest_function",
"//src/main/java/com/google/devtools/build/lib/skyframe:directory_tree_digest_value",
"//src/main/java/com/google/devtools/build/lib/skyframe:file_function",
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
index 4ba7856..6031135 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
@@ -29,10 +29,12 @@
import com.google.common.collect.HashMultiset;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Maps;
import com.google.common.collect.Multiset;
import com.google.common.collect.Sets;
import com.google.devtools.build.lib.actions.FileStateValue;
+import com.google.devtools.build.lib.actions.FileValue;
import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
import com.google.devtools.build.lib.clock.BlazeClock;
@@ -42,6 +44,7 @@
import com.google.devtools.build.lib.events.EventKind;
import com.google.devtools.build.lib.events.ExtendedEventHandler;
import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
+import com.google.devtools.build.lib.packages.Globber.Operation;
import com.google.devtools.build.lib.packages.NoSuchPackageException;
import com.google.devtools.build.lib.packages.NoSuchTargetException;
import com.google.devtools.build.lib.packages.Package;
@@ -55,6 +58,7 @@
import com.google.devtools.build.lib.rules.repository.RepositoryDelegatorFunction;
import com.google.devtools.build.lib.runtime.QuiescingExecutorsImpl;
import com.google.devtools.build.lib.server.FailureDetails.PackageLoading;
+import com.google.devtools.build.lib.skyframe.GlobsValue.GlobRequest;
import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
import com.google.devtools.build.lib.testutil.ManualClock;
import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
@@ -77,10 +81,14 @@
import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
import com.google.devtools.build.skyframe.Differencer.DiffWithDelta.Delta;
import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.InMemoryGraph;
+import com.google.devtools.build.skyframe.InMemoryNodeEntry;
import com.google.devtools.build.skyframe.RecordingDifferencer;
import com.google.devtools.build.skyframe.SkyKey;
import com.google.devtools.build.skyframe.SkyValue;
import com.google.devtools.common.options.Options;
+import com.google.testing.junit.testparameterinjector.TestParameter;
+import com.google.testing.junit.testparameterinjector.TestParameterInjector;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
@@ -95,6 +103,7 @@
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Stream;
import javax.annotation.Nullable;
+import org.junit.Before;
import org.junit.Rule;
import org.junit.Test;
import org.junit.runner.RunWith;
@@ -108,7 +117,7 @@
* Unit tests of specific functionality of PackageFunction. Note that it's already tested indirectly
* in several other places.
*/
-@RunWith(JUnit4.class)
+@RunWith(TestParameterInjector.class)
public class PackageFunctionTest extends BuildViewTestCase {
@Rule public final MockitoRule mockito = MockitoJUnit.rule();
@@ -117,6 +126,8 @@
@Mock private PackageOverheadEstimator mockPackageOverheadEstimator;
+ @TestParameter private boolean globUnderSingleDep;
+
private final CustomInMemoryFs fs = new CustomInMemoryFs(new ManualClock());
private void preparePackageLoading(Path... roots) {
@@ -207,6 +218,15 @@
return result.getError(skyKey).getException();
}
+ @Before
+ @Override
+ public final void initializeSkyframeExecutor() throws Exception {
+ initializeSkyframeExecutor(
+ /* doPackageLoadingChecks= */ true,
+ /* diffAwarenessFactories= */ ImmutableList.of(),
+ /* globUnderSingleDep= */ globUnderSingleDep);
+ }
+
@Test
public void testValidPackage() throws Exception {
scratch.file("pkg/BUILD");
@@ -1645,19 +1665,28 @@
// Then, when we modify the BUILD file so as to force package loading,
scratch.overwriteFile(
"foo/BUILD", "glob(['cycle/**/foo.txt']) # dummy comment to force package loading");
- // But we don't make any filesystem changes that would invalidate the GlobValues, meaning that
- // PackageFunction will observe cache hits from Skyframe globbing,
- //
- // And we also have our filesystem blow up if the directory symlink cycle is encountered (thus,
- // the absence of a crash indicates the lack of non-Skyframe globbing),
- fs.stubStatError(
- fooCyclePath,
- new IOException() {
- @Override
- public String getMessage() {
- throw new IllegalStateException("shouldn't get here!");
- }
- });
+
+ if (!globUnderSingleDep) {
+ // When globbing strategy is SKYFRAME_HYBRID (globUnderSingleDep = false), and we don't make
+ // any filesystem changes that would invalidate the GlobValues, PackageFunction will observe
+ // cache hits from Skyframe globbing.
+ //
+ // And we also have our filesystem blow up if the directory symlink cycle is encountered
+ // (thus, the absence of a crash indicates the lack of non-Skyframe globbing).
+ //
+ // However, when globbing strategy is GLOBS (globUnderSingleDep = true), and we lose Skyframe
+ // Hybrid globbing, we expect package reloading still to always do non-Skyframe globbing which
+ // calls stats for symlink `foo/cycle`.
+ fs.stubStatError(
+ fooCyclePath,
+ new IOException() {
+ @Override
+ public String getMessage() {
+ throw new IllegalStateException("shouldn't get here!");
+ }
+ });
+ }
+
// And we evaluate the PackageValue node for the Package in keepGoing mode,
getSkyframeExecutor()
.invalidateFilesUnderPathForTesting(
@@ -1682,6 +1711,106 @@
// presence of a symlink cycle encountered during glob evaluation.
}
+ @Test
+ public void testGlobbingSkyframeDependencyStructure() throws Exception {
+ reporter.removeHandler(failFastHandler);
+
+ Root pkgRoot = getSkyframeExecutor().getPathEntries().get(0);
+
+ Path fooBuildPath =
+ scratch.file("foo/BUILD", "glob(['dir/*.sh'])", "subpackages(include = ['subpkg/**'])");
+
+ Path fooDirPath = fooBuildPath.getParentDirectory().getChild("dir");
+ scratch.file("foo/dir/bar.sh");
+ scratch.file("foo/dir/baz.sh");
+
+ Path fooSubpkgPath = fooBuildPath.getParentDirectory().getChild("subpkg");
+ scratch.file("foo/subpkg/BUILD");
+
+ SkyKey pkgKey = PackageIdentifier.createInMainRepo("foo");
+ SkyframeExecutorTestUtils.evaluate(
+ getSkyframeExecutor(), pkgKey, /* keepGoing= */ true, reporter);
+
+ InMemoryGraph graph = getSkyframeExecutor().memoizingEvaluator.getInMemoryGraph();
+ InMemoryNodeEntry packageNode = graph.getIfPresent(pkgKey);
+ if (globUnderSingleDep) {
+ // The package subgraph with single Globs node looks like this:
+ // PKG["foo"]
+ // |- GLOBS[["dir/*.sh", FILES], ["subpkg/**", SUBPACKAGES]]
+ // |- FILE["foo/dir"]
+ // |- DIRECTORY_LISTING["foo/dir"]
+ // |- PACKAGE_LOOKUP["foo/dir"]
+ // |- FILE["foo/subdir"]
+ // |- PACKAGE_LOOKUP["foo/subdir"]
+ GlobsValue.Key globsKey =
+ GlobsValue.key(
+ PackageIdentifier.createInMainRepo("foo"),
+ pkgRoot,
+ ImmutableSet.of(
+ GlobRequest.create("dir/*.sh", Operation.FILES),
+ GlobRequest.create("subpkg/**", Operation.SUBPACKAGES)));
+ assertThat(packageNode.getDirectDeps()).contains(globsKey);
+
+ InMemoryNodeEntry globsNode = graph.getIfPresent(globsKey);
+ SkyValue globsValue = globsNode.getValue();
+ assertThat(globsValue).isInstanceOf(GlobsValue.class);
+ assertThat(((GlobsValue) globsValue).getMatches())
+ .containsExactly(
+ PathFragment.create("subpkg"),
+ PathFragment.create("dir/bar.sh"),
+ PathFragment.create("dir/baz.sh"));
+ ImmutableSet<SkyKey> globsDirectDeps = ImmutableSet.copyOf(globsNode.getDirectDeps());
+ assertThat(globsDirectDeps)
+ .containsAtLeast(
+ DirectoryListingValue.key(RootedPath.toRootedPath(pkgRoot, fooDirPath)),
+ FileValue.key(RootedPath.toRootedPath(pkgRoot, fooDirPath)),
+ FileValue.key(RootedPath.toRootedPath(pkgRoot, fooSubpkgPath)),
+ PackageLookupValue.key(PackageIdentifier.createInMainRepo("foo/dir")),
+ PackageLookupValue.key(PackageIdentifier.createInMainRepo("foo/subpkg")));
+ } else {
+ // The package subgraph with multiple Glob nodes looks like this:
+ // PKG["foo"]
+ // |- GLOB["dir/*.sh", FILES]
+ // |- FILE["foo/dir"]
+ // |- DIRECTORY_LISTING["foo/dir"]
+ // |- PACKAGE_LOOKUP["foo/dir"]
+ // |- GLOB["subpkg/**", SUBPACKAGES]
+ // |- FILE["foo/subdir"]
+ // |- PACKAGE_LOOKUP["foo/subdir"]
+ GlobDescriptor dirGlobDescriptor =
+ GlobValue.key(
+ PackageIdentifier.createInMainRepo("foo"),
+ pkgRoot,
+ /* pattern= */ "dir/*.sh",
+ Operation.FILES,
+ PathFragment.EMPTY_FRAGMENT);
+ GlobDescriptor subdirGlobDescriptor =
+ GlobValue.key(
+ PackageIdentifier.createInMainRepo("foo"),
+ pkgRoot,
+ /* pattern= */ "subpkg/**",
+ Operation.SUBPACKAGES,
+ PathFragment.EMPTY_FRAGMENT);
+ assertThat(packageNode.getDirectDeps())
+ .containsAtLeast(dirGlobDescriptor, subdirGlobDescriptor);
+
+ ImmutableSet<SkyKey> dirGlobNodeDeps =
+ ImmutableSet.copyOf(graph.getIfPresent(dirGlobDescriptor).getDirectDeps());
+ assertThat(dirGlobNodeDeps)
+ .containsAtLeast(
+ DirectoryListingValue.key(RootedPath.toRootedPath(pkgRoot, fooDirPath)),
+ FileValue.key(RootedPath.toRootedPath(pkgRoot, fooDirPath)),
+ PackageLookupValue.key(PackageIdentifier.createInMainRepo("foo/dir")));
+
+ ImmutableSet<SkyKey> subdirGlobNodeDeps =
+ ImmutableSet.copyOf(graph.getIfPresent(subdirGlobDescriptor).getDirectDeps());
+ assertThat(subdirGlobNodeDeps)
+ .containsAtLeast(
+ FileValue.key(RootedPath.toRootedPath(pkgRoot, fooSubpkgPath)),
+ PackageLookupValue.key(PackageIdentifier.createInMainRepo("foo/subpkg")));
+ }
+ }
+
private static void assertDetailedExitCode(
Exception exception, PackageLoading.Code expectedPackageLoadingCode, ExitCode exitCode) {
assertThat(exception).isInstanceOf(DetailedException.class);
diff --git a/src/test/shell/integration/discard_graph_edges_test.sh b/src/test/shell/integration/discard_graph_edges_test.sh
index 35868fa..ced5277 100755
--- a/src/test/shell/integration/discard_graph_edges_test.sh
+++ b/src/test/shell/integration/discard_graph_edges_test.sh
@@ -249,9 +249,9 @@
'devtools\.build\.lib\..*\.Package$')"
[[ "$package_count" -ge 9 ]] \
|| fail "package count $package_count too low: did you move/rename the class?"
- local glob_count="$(extract_histogram_count "$histo_file" "GlobValueWithImmutableSet$")"
- [[ "$glob_count" -ge 2 ]] \
- || fail "glob count $glob_count too low: did you move/rename the class?"
+ local globs_count="$(extract_histogram_count "$histo_file" "GlobsValue$")"
+ [[ "$globs_count" -ge 2 ]] \
+ || fail "globs count $globs_count too low: did you move/rename the class?"
local module_count="$(extract_histogram_count "$histo_file" 'eval.Module$')"
[[ "$module_count" -gt 25 ]] \
|| fail "Module count $module_count too low: was the class renamed/moved?" # was 74
@@ -273,9 +273,9 @@
# A few packages aren't cleared.
[[ "$package_count" -le 26 ]] \
|| fail "package count $package_count too high"
- glob_count="$(extract_histogram_count "$histo_file" "GlobValueWithImmutableSet$")"
- [[ "$glob_count" -le 1 ]] \
- || fail "glob count $glob_count too high"
+ globs_count="$(extract_histogram_count "$histo_file" "GlobsValue$")"
+ [[ "$globs_count" -le 1 ]] \
+ || fail "globs count $globs_count too high"
module_count="$(extract_histogram_count "$histo_file" 'eval.Module$')"
[[ "$module_count" -lt 190 ]] \
|| fail "Module count $module_count too high"
