Correctly handle missing data in FileDependencyDeserializer.
This change introduces explicit representations for missing data for the
different FileSystemsDependencies implementations. It adds a corresponding
type, AlwaysMatch to serve as a match type when there is missing data.
PiperOrigin-RevId: 775236289
Change-Id: Id20011c1971eee789b3817537c2d7569583e4107
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/AlwaysMatch.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/AlwaysMatch.java
new file mode 100644
index 0000000..11f3bdf
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/AlwaysMatch.java
@@ -0,0 +1,37 @@
+// Copyright 2025 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.serialization.analysis;
+
+import com.google.devtools.build.lib.skyframe.serialization.analysis.FileOpMatchResultTypes.FileOpMatchResult;
+import com.google.devtools.build.lib.skyframe.serialization.analysis.NestedMatchResultTypes.NestedMatchResult;
+
+/**
+ * The delta matches any set of dependencies, meaning a <b>cache miss</b>.
+ *
+ * <p>This occurs when there is missing data, and thus no guarantee can be made about the cache
+ * entry's validity.
+ */
+enum AlwaysMatch implements FileOpMatchResult, NestedMatchResult, MatchIndicator {
+ ALWAYS_MATCH_RESULT;
+
+ @Override
+ public boolean isMatch() {
+ return true;
+ }
+
+ @Override
+ public final int version() {
+ return VersionedChanges.ALWAYS_MATCH;
+ }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/BUILD b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/BUILD
index 0b3968c..9d4d902 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/BUILD
@@ -165,8 +165,10 @@
java_library(
name = "versioned_changes_validator",
srcs = [
+ "AlwaysMatch.java",
"FileOpMatchMemoizingLookup.java",
"FileOpMatchResultTypes.java",
+ "MatchIndicator.java",
"NestedMatchMemoizingLookup.java",
"NestedMatchResultTypes.java",
"NoMatch.java",
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencies.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencies.java
index c7595c2..c8c41e9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencies.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencies.java
@@ -74,6 +74,10 @@
return new Builder(firstResolvedPath);
}
+ static FileDependencies newMissingInstance() {
+ return new MissingFileDependencies();
+ }
+
static final class Builder {
private final ArrayList<String> paths = new ArrayList<>();
private final ArrayList<FileDependencies> dependencies = new ArrayList<>();
@@ -124,6 +128,11 @@
}
@Override
+ public boolean isMissingData() {
+ return false;
+ }
+
+ @Override
int findEarliestMatch(VersionedChanges changes, int validityHorizon) {
return changes.matchFileChange(resolvedPath, validityHorizon);
}
@@ -164,6 +173,11 @@
}
@Override
+ public boolean isMissingData() {
+ return false;
+ }
+
+ @Override
int findEarliestMatch(VersionedChanges changes, int validityHorizon) {
return changes.matchFileChange(resolvedPath, validityHorizon);
}
@@ -211,6 +225,11 @@
}
@Override
+ public boolean isMissingData() {
+ return false;
+ }
+
+ @Override
int findEarliestMatch(VersionedChanges changes, int validityHorizon) {
int minMatch = VersionedChanges.NO_MATCH;
for (String element : resolvedPaths) {
@@ -250,4 +269,44 @@
.toString();
}
}
+
+ /**
+ * Signals missing data in the nested set of dependencies.
+ *
+ * <p>This is deliberately not a singleton to avoid a memory leak in the weak-value caches in
+ * {@link FileDependencyDeserializer}.
+ */
+ private static final class MissingFileDependencies extends FileDependencies {
+ private MissingFileDependencies() {}
+
+ @Override
+ public boolean isMissingData() {
+ return true;
+ }
+
+ @Override
+ int findEarliestMatch(VersionedChanges changes, int validityHorizon) {
+ return VersionedChanges.ALWAYS_MATCH;
+ }
+
+ @Override
+ int getDependencyCount() {
+ return 0;
+ }
+
+ @Override
+ FileDependencies getDependency(int index) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ String resolvedPath() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ ImmutableList<String> getAllResolvedPathsForTesting() {
+ throw new UnsupportedOperationException();
+ }
+ }
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencyDeserializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencyDeserializer.java
index cb1fd26..1aa3f42 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencyDeserializer.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileDependencyDeserializer.java
@@ -261,6 +261,10 @@
@Override
public ListenableFuture<FileDependencies> apply(byte[] bytes)
throws InvalidProtocolBufferException {
+ if (bytes == null) {
+ return immediateFuture(FileDependencies.newMissingInstance());
+ }
+
var data = FileInvalidationData.parseFrom(bytes, getEmptyRegistry());
if (data.hasOverflowKey() && !data.getOverflowKey().equals(key)) {
return immediateFailedFuture(
@@ -485,6 +489,10 @@
@Override
public ListenableFuture<ListingDependencies> apply(byte[] bytes)
throws InvalidProtocolBufferException {
+ if (bytes == null) {
+ return immediateFuture(ListingDependencies.newMissingInstance());
+ }
+
var data = DirectoryListingInvalidationData.parseFrom(bytes, getEmptyRegistry());
if (data.hasOverflowKey() && !data.getOverflowKey().equals(key)) {
return immediateFailedFuture(
@@ -499,7 +507,7 @@
String path = key.substring(pathBegin);
if (path.isEmpty()) {
- return immediateFuture(new ListingDependencies(ROOT_FILE));
+ return immediateFuture(ListingDependencies.from(ROOT_FILE));
}
String fileKey =
@@ -509,9 +517,9 @@
FILE_KEY_DELIMITER);
switch (getFileDependencies(fileKey)) {
case FileDependencies dependencies:
- return immediateFuture(new ListingDependencies(dependencies));
+ return immediateFuture(ListingDependencies.from(dependencies));
case FutureFileDependencies future:
- return Futures.transform(future, ListingDependencies::new, directExecutor());
+ return Futures.transform(future, ListingDependencies::from, directExecutor());
}
}
}
@@ -529,6 +537,10 @@
*/
@Override
public ListenableFuture<NestedDependencies> apply(byte[] bytes) {
+ if (bytes == null) {
+ return immediateFuture(NestedDependencies.newMissingInstance());
+ }
+
try {
boolean usesZstdCompression = MagicBytes.hasMagicBytes(bytes);
CodedInputStream codedIn;
@@ -649,7 +661,7 @@
@Override
protected NestedDependencies getValue() {
- return new NestedDependencies(elements, sources);
+ return NestedDependencies.from(elements, sources);
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchMemoizingLookup.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchMemoizingLookup.java
index bc8a216..f6914a2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchMemoizingLookup.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchMemoizingLookup.java
@@ -14,6 +14,7 @@
package com.google.devtools.build.lib.skyframe.serialization.analysis;
import static com.google.common.util.concurrent.MoreExecutors.directExecutor;
+import static com.google.devtools.build.lib.skyframe.serialization.analysis.AlwaysMatch.ALWAYS_MATCH_RESULT;
import static java.lang.Math.min;
import com.google.common.util.concurrent.FutureCallback;
@@ -64,21 +65,23 @@
private FileOpMatchResultOrFuture populateFutureFileOpMatchResult(
int validityHorizon, FutureFileOpMatchResult ownedFuture) {
- switch (ownedFuture.key()) {
- case FileDependencies file:
- return aggregateAnyAdditionalFileDependencies(
- file.findEarliestMatch(changes, validityHorizon), file, validityHorizon, ownedFuture);
- case ListingDependencies listing:
+ return switch (ownedFuture.key()) {
+ case FileDependencies file ->
+ aggregateAnyAdditionalFileDependencies(
+ file.findEarliestMatch(changes, validityHorizon), file, validityHorizon, ownedFuture);
+ case ListingDependencies.AvailableListingDependencies listing -> {
// Matches the listing (files inside the directory changed).
int version = listing.findEarliestMatch(changes, validityHorizon);
// Then matches the directory itself.
FileDependencies realDirectory = listing.realDirectory();
- return aggregateAnyAdditionalFileDependencies(
+ yield aggregateAnyAdditionalFileDependencies(
min(version, realDirectory.findEarliestMatch(changes, validityHorizon)),
realDirectory,
validityHorizon,
ownedFuture);
- }
+ }
+ case ListingDependencies.MissingListingDependencies missingListing -> ALWAYS_MATCH_RESULT;
+ };
}
private FileOpMatchResultOrFuture aggregateAnyAdditionalFileDependencies(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchResultTypes.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchResultTypes.java
index e1d0f22..1816b67 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchResultTypes.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchResultTypes.java
@@ -13,6 +13,7 @@
// limitations under the License.
package com.google.devtools.build.lib.skyframe.serialization.analysis;
+import static com.google.devtools.build.lib.skyframe.serialization.analysis.AlwaysMatch.ALWAYS_MATCH_RESULT;
import static com.google.devtools.build.lib.skyframe.serialization.analysis.NoMatch.NO_MATCH_RESULT;
import com.google.devtools.build.lib.concurrent.SettableFutureKeyedValue;
@@ -26,17 +27,26 @@
sealed interface FileOpMatchResultOrFuture permits FileOpMatchResult, FutureFileOpMatchResult {}
/** An immediate result. */
- sealed interface FileOpMatchResult extends FileOpMatchResultOrFuture
- permits NoMatch, FileOpMatch {
+ sealed interface FileOpMatchResult extends FileOpMatchResultOrFuture, MatchIndicator
+ permits FileOpMatch, NoMatch, AlwaysMatch {
static FileOpMatchResult create(int version) {
- return version == VersionedChanges.NO_MATCH ? NO_MATCH_RESULT : new FileOpMatch(version);
+ return switch (version) {
+ case VersionedChanges.NO_MATCH -> NO_MATCH_RESULT;
+ case VersionedChanges.ALWAYS_MATCH -> ALWAYS_MATCH_RESULT;
+ default -> new FileOpMatch(version);
+ };
}
int version();
}
- /** A result signalling a match. */
- record FileOpMatch(int version) implements FileOpMatchResult {}
+ /** A result signaling a match. */
+ record FileOpMatch(int version) implements FileOpMatchResult {
+ @Override
+ public boolean isMatch() {
+ return true;
+ }
+ }
/** A future result. */
static final class FutureFileOpMatchResult
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependencies.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependencies.java
index f806051..27f88fc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependencies.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependencies.java
@@ -28,4 +28,14 @@
/** Dependencies, excluding nested dependencies. */
sealed interface FileOpDependency extends FileSystemDependencies
permits FileDependencies, ListingDependencies {}
+
+ /**
+ * True if data was missing for this dependency.
+ *
+ * <p>Dependencies are fetched from a remote cache without durability guarantees. It's possible
+ * for the corresponding data to be missing. Any missing data induces missing data on anything
+ * that references it. From an invalidation perspective, if {@link isMissingData} is true, the
+ * dependency should never allow a cache hit and always signal matching everything.
+ */
+ boolean isMissingData();
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/ListingDependencies.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/ListingDependencies.java
index d53a7a6..d930bf8 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/ListingDependencies.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/ListingDependencies.java
@@ -16,41 +16,77 @@
import static com.google.common.base.MoreObjects.toStringHelper;
/** Type representing a directory listing operation. */
-final class ListingDependencies
+abstract sealed class ListingDependencies
implements FileSystemDependencies.FileOpDependency,
- FileDependencyDeserializer.ListingDependenciesOrFuture {
- private final FileDependencies realDirectory;
+ FileDependencyDeserializer.ListingDependenciesOrFuture
+ permits ListingDependencies.AvailableListingDependencies,
+ ListingDependencies.MissingListingDependencies {
- ListingDependencies(FileDependencies realDirectory) {
- this.realDirectory = realDirectory;
+ static ListingDependencies from(FileDependencies realDirectory) {
+ if (realDirectory.isMissingData()) {
+ return newMissingInstance();
+ }
+ return new AvailableListingDependencies(realDirectory);
+ }
+
+ static ListingDependencies newMissingInstance() {
+ return new MissingListingDependencies();
+ }
+
+ static final class AvailableListingDependencies extends ListingDependencies {
+ private final FileDependencies realDirectory;
+
+ private AvailableListingDependencies(FileDependencies realDirectory) {
+ this.realDirectory = realDirectory;
+ }
+
+ @Override
+ public boolean isMissingData() {
+ return false;
+ }
+
+ /**
+ * Determines if this listing is invalidated by anything in {@code changes}.
+ *
+ * <p>The caller should ensure the following.
+ *
+ * <ul>
+ * <li>This listing is known to be valid at {@code validityHorizon} (VH).
+ * <li>All changes over the range {@code (VH, VC])} are registered with {@code changes} before
+ * calling this method. (VC is the synced version of the cache reader.)
+ * </ul>
+ *
+ * <p>See description of {@link VersionedChanges} for more details.
+ *
+ * @return the earliest version where a matching (invalidating) change is identified, otherwise
+ * {@link VersionedChanges#NO_MATCH}.
+ */
+ int findEarliestMatch(VersionedChanges changes, int validityHorizon) {
+ return changes.matchListingChange(realDirectory.resolvedPath(), validityHorizon);
+ }
+
+ FileDependencies realDirectory() {
+ return realDirectory;
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this).add("realDirectory", realDirectory).toString();
+ }
}
/**
- * Determines if this listing is invalidated by anything in {@code changes}.
+ * Signals missing listing data.
*
- * <p>The caller should ensure the following.
- *
- * <ul>
- * <li>This listing is known to be valid at {@code validityHorizon} (VH).
- * <li>All changes over the range {@code (VH, VC])} are registered with {@code changes} before
- * calling this method. (VC is the synced version of the cache reader.)
- * </ul>
- *
- * <p>See description of {@link VersionedChanges} for more details.
- *
- * @return the earliest version where a matching (invalidating) change is identified, otherwise
- * {@link VersionedChanges#NO_MATCH}.
+ * <p>This is deliberately not a singleton to avoid a memory leak in the weak-value caches in
+ * {@link FileDependencyDeserializer}.
*/
- int findEarliestMatch(VersionedChanges changes, int validityHorizon) {
- return changes.matchListingChange(realDirectory.resolvedPath(), validityHorizon);
- }
+ static final class MissingListingDependencies extends ListingDependencies {
+ private MissingListingDependencies() {}
- FileDependencies realDirectory() {
- return realDirectory;
- }
-
- @Override
- public String toString() {
- return toStringHelper(this).add("realDirectory", realDirectory).toString();
+ @Override
+ public boolean isMissingData() {
+ return true;
+ }
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/MatchIndicator.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/MatchIndicator.java
new file mode 100644
index 0000000..4f2d18b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/MatchIndicator.java
@@ -0,0 +1,19 @@
+// Copyright 2025 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.serialization.analysis;
+
+/** Specifies whether a certain match result indicates a match or not. */
+interface MatchIndicator {
+ boolean isMatch();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedDependencies.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedDependencies.java
index affd209..1f5bf15 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedDependencies.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedDependencies.java
@@ -16,6 +16,7 @@
import static com.google.common.base.MoreObjects.toStringHelper;
import static com.google.common.base.Preconditions.checkArgument;
+import com.google.common.annotations.VisibleForTesting;
import java.util.Arrays;
import java.util.Collection;
@@ -26,52 +27,97 @@
* com.google.devtools.build.lib.skyframe.AbstractNestedFileOpNodes} instance, but this
* implementation is mostly decoupled from Bazel code.
*/
-final class NestedDependencies
- implements FileSystemDependencies, FileDependencyDeserializer.NestedDependenciesOrFuture {
- // While formally possible, we don't anticipate analysisDependencies being empty often. `sources`
- // could be frequently empty.
+abstract sealed class NestedDependencies
+ implements FileSystemDependencies, FileDependencyDeserializer.NestedDependenciesOrFuture
+ permits NestedDependencies.AvailableNestedDependencies,
+ NestedDependencies.MissingNestedDependencies {
+ // While formally possible, we don't anticipate analysisDependencies being empty often.
+ // `sources` could be frequently empty.
static final FileDependencies[] EMPTY_SOURCES = new FileDependencies[0];
- private final FileSystemDependencies[] analysisDependencies;
- private final FileDependencies[] sources;
-
- NestedDependencies(FileSystemDependencies[] analysisDependencies, FileDependencies[] sources) {
- checkArgument(
- analysisDependencies.length >= 1 || sources.length >= 1,
- "analysisDependencies and sources both empty");
- this.analysisDependencies = analysisDependencies;
- this.sources = sources;
+ static NestedDependencies from(
+ FileSystemDependencies[] analysisDependencies, FileDependencies[] sources) {
+ for (FileSystemDependencies dep : analysisDependencies) {
+ if (dep.isMissingData()) {
+ return new MissingNestedDependencies();
+ }
+ }
+ for (FileDependencies dep : sources) {
+ if (dep.isMissingData()) {
+ return new MissingNestedDependencies();
+ }
+ }
+ return new AvailableNestedDependencies(analysisDependencies, sources);
}
- NestedDependencies(
+ @VisibleForTesting
+ static NestedDependencies from(
Collection<? extends FileSystemDependencies> analysisDependencies,
Collection<FileDependencies> sources) {
- this(
+ return from(
analysisDependencies.toArray(FileSystemDependencies[]::new),
sources.toArray(FileDependencies[]::new));
}
- int analysisDependenciesCount() {
- return analysisDependencies.length;
+ static NestedDependencies newMissingInstance() {
+ return new MissingNestedDependencies();
}
- FileSystemDependencies getAnalysisDependency(int index) {
- return analysisDependencies[index];
+ static final class AvailableNestedDependencies extends NestedDependencies {
+ private final FileSystemDependencies[] analysisDependencies;
+ private final FileDependencies[] sources;
+
+ AvailableNestedDependencies(
+ FileSystemDependencies[] analysisDependencies, FileDependencies[] sources) {
+ checkArgument(
+ analysisDependencies.length >= 1 || sources.length >= 1,
+ "analysisDependencies and sources both empty");
+ this.analysisDependencies = analysisDependencies;
+ this.sources = sources;
+ }
+
+ @Override
+ public boolean isMissingData() {
+ return false;
+ }
+
+ int analysisDependenciesCount() {
+ return analysisDependencies.length;
+ }
+
+ FileSystemDependencies getAnalysisDependency(int index) {
+ return analysisDependencies[index];
+ }
+
+ int sourcesCount() {
+ return sources.length;
+ }
+
+ FileDependencies getSource(int index) {
+ return sources[index];
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this)
+ .add("analysisDependencies", Arrays.asList(analysisDependencies))
+ .add("sources", Arrays.asList(sources))
+ .toString();
+ }
}
- int sourcesCount() {
- return sources.length;
- }
+ /**
+ * Signals missing data in the nested set of dependencies.
+ *
+ * <p>This is deliberately not a singleton to avoid a memory leak in the weak-value caches in
+ * {@link FileDependencyDeserializer}.
+ */
+ static final class MissingNestedDependencies extends NestedDependencies {
+ private MissingNestedDependencies() {}
- FileDependencies getSource(int index) {
- return sources[index];
- }
-
- @Override
- public String toString() {
- return toStringHelper(this)
- .add("analysisDependencies", Arrays.asList(analysisDependencies))
- .add("sources", Arrays.asList(sources))
- .toString();
+ @Override
+ public boolean isMissingData() {
+ return true;
+ }
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchMemoizingLookup.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchMemoizingLookup.java
index 14133fa..1f187aa 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchMemoizingLookup.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchMemoizingLookup.java
@@ -14,6 +14,7 @@
package com.google.devtools.build.lib.skyframe.serialization.analysis;
import static com.google.common.util.concurrent.MoreExecutors.directExecutor;
+import static com.google.devtools.build.lib.skyframe.serialization.analysis.AlwaysMatch.ALWAYS_MATCH_RESULT;
import static com.google.devtools.build.lib.skyframe.serialization.analysis.NestedMatchResultTypes.createNestedMatchResult;
import static com.google.devtools.build.lib.skyframe.serialization.analysis.NoMatch.NO_MATCH_RESULT;
@@ -74,41 +75,46 @@
private NestedMatchResultOrFuture populateFutureNestedMatchResult(
int validityHorizon, FutureNestedMatchResult ownedFuture) {
- NestedDependencies nested = ownedFuture.key();
- var aggregator = new NestedFutureResultAggregator();
- for (int i = 0; i < nested.analysisDependenciesCount(); i++) {
- switch (nested.getAnalysisDependency(i)) {
- case FileOpDependency dependency:
- aggregator.addAnalysisResultOrFuture(
- fileOpMatches.getValueOrFuture(dependency, validityHorizon));
- break;
- case NestedDependencies child:
- // In a common case, the cache reader sends a single top-level request that traverses the
- // full set of dependencies and waits for that request to complete. Parallelizes
- // recursive traversal of child nodes to avoid being singly-threaded in this scenario.
- aggregator.signalNestedTaskAdded();
- executor.execute(
- () -> {
- switch (getValueOrFuture(child, validityHorizon)) {
- case NestedMatchResult result:
- aggregator.addNestedResult(result);
- aggregator.signalNestedTaskComplete();
- break;
- case FutureNestedMatchResult future:
- // The aggregator decrements when the future completes.
- aggregator.addFutureNestedMatchResult(future);
- break;
- }
- });
- break;
+ return switch (ownedFuture.key()) {
+ case NestedDependencies.AvailableNestedDependencies nested -> {
+ var aggregator = new NestedFutureResultAggregator();
+ for (int i = 0; i < nested.analysisDependenciesCount(); i++) {
+ switch (nested.getAnalysisDependency(i)) {
+ case FileOpDependency dependency:
+ aggregator.addAnalysisResultOrFuture(
+ fileOpMatches.getValueOrFuture(dependency, validityHorizon));
+ break;
+ case NestedDependencies child:
+ // In a common case, the cache reader sends a single top-level request that traverses
+ // the full set of dependencies and waits for that request to complete. Parallelizes
+ // recursive traversal of child nodes to avoid being singly-threaded in this scenario.
+ aggregator.signalNestedTaskAdded();
+ executor.execute(
+ () -> {
+ switch (getValueOrFuture(child, validityHorizon)) {
+ case NestedMatchResult result:
+ aggregator.addNestedResult(result);
+ aggregator.signalNestedTaskComplete();
+ break;
+ case FutureNestedMatchResult future:
+ // The aggregator decrements when the future completes.
+ aggregator.addFutureNestedMatchResult(future);
+ break;
+ }
+ });
+ break;
+ }
+ }
+ for (int i = 0; i < nested.sourcesCount(); i++) {
+ aggregator.addSourceResultOrFuture(
+ fileOpMatches.getValueOrFuture(nested.getSource(i), validityHorizon));
+ }
+ aggregator.notifyAllDependenciesAdded();
+ yield ownedFuture.completeWith(aggregator);
}
- }
- for (int i = 0; i < nested.sourcesCount(); i++) {
- aggregator.addSourceResultOrFuture(
- fileOpMatches.getValueOrFuture(nested.getSource(i), validityHorizon));
- }
- aggregator.notifyAllDependenciesAdded();
- return ownedFuture.completeWith(aggregator);
+ case NestedDependencies.MissingNestedDependencies missing ->
+ ownedFuture.completeWith(ALWAYS_MATCH_RESULT);
+ };
}
private static final class NestedFutureResultAggregator
@@ -160,6 +166,9 @@
switch (result) {
case NO_MATCH_RESULT:
break;
+ case ALWAYS_MATCH_RESULT:
+ earliestAnalysisMatch = VersionedChanges.ALWAYS_MATCH;
+ break;
case AnalysisMatch(int version):
updateAnalysisVersionIfEarlier(version);
break;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchResultTypes.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchResultTypes.java
index 229e813..c9ae5e5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchResultTypes.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchResultTypes.java
@@ -26,7 +26,7 @@
/** An immediate match result. */
sealed interface NestedMatchResult extends NestedMatchResultOrFuture
- permits AnalysisMatch, SourceMatch, AnalysisAndSourceMatch, NoMatch {}
+ permits AnalysisMatch, SourceMatch, AnalysisAndSourceMatch, NoMatch, AlwaysMatch {}
static NestedMatchResult createNestedMatchResult(int analysisVersion, int sourceVersion) {
if (analysisVersion <= sourceVersion) {
@@ -47,7 +47,12 @@
*
* @param version the minimum version where the analysis match was observed
*/
- static record AnalysisMatch(int version) implements NestedMatchResult {}
+ static record AnalysisMatch(int version) implements NestedMatchResult, MatchIndicator {
+ @Override
+ public boolean isMatch() {
+ return true;
+ }
+ }
/**
* The delta didn't match analysis dependencies, but matched source dependencies, indicating a
@@ -68,7 +73,7 @@
* @param sourceVersion the minimum version where the source match was observed.
*/
record AnalysisAndSourceMatch(int analysisVersion, int sourceVersion)
- implements NestedMatchResult {
+ implements NestedMatchResult, MatchIndicator {
public AnalysisAndSourceMatch {
checkArgument(
sourceVersion < analysisVersion,
@@ -76,6 +81,11 @@
sourceVersion,
analysisVersion);
}
+
+ @Override
+ public boolean isMatch() {
+ return true;
+ }
}
/** A future match result. */
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NoMatch.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NoMatch.java
index 979adda..67de8a7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NoMatch.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NoMatch.java
@@ -17,10 +17,15 @@
import com.google.devtools.build.lib.skyframe.serialization.analysis.NestedMatchResultTypes.NestedMatchResult;
/** The delta didn't match the set of dependencies, meaning a <b>cache hit</b>. */
-enum NoMatch implements FileOpMatchResult, NestedMatchResult {
+enum NoMatch implements FileOpMatchResult, NestedMatchResult, MatchIndicator {
NO_MATCH_RESULT;
@Override
+ public boolean isMatch() {
+ return false;
+ }
+
+ @Override
public final int version() {
return VersionedChanges.NO_MATCH;
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/VersionedChanges.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/VersionedChanges.java
index 1de695c..8f3c756 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/VersionedChanges.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/analysis/VersionedChanges.java
@@ -79,6 +79,13 @@
*/
static final int CLIENT_CHANGE = Integer.MAX_VALUE - 1;
+ /**
+ * Version indicating a match at any change.
+ *
+ * <p>Used when there is missing data and correct invalidation is impossible.
+ */
+ static final int ALWAYS_MATCH = -1;
+
// TODO: b/364831651 - if sorted int[] does not scale, it can be replaced with TreeSet<Integer>
// but we expect the number of changes per entry to be small.
private final ConcurrentHashMap<String, int[]> fileChanges = new ConcurrentHashMap<>();
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/ControllableFileDependencies.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/ControllableFileDependencies.java
index 8c487f9..e921fb9 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/ControllableFileDependencies.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/ControllableFileDependencies.java
@@ -36,6 +36,11 @@
this.dependencies = dependencies;
}
+ @Override
+ public boolean isMissingData() {
+ return false;
+ }
+
void awaitEarliestMatchEntered() throws InterruptedException {
findEarliestMatchEntered.await();
}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchMemoizingLookupTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchMemoizingLookupTest.java
index c043dda..92166cb 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchMemoizingLookupTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileOpMatchMemoizingLookupTest.java
@@ -14,6 +14,7 @@
package com.google.devtools.build.lib.skyframe.serialization.analysis;
import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.lib.skyframe.serialization.analysis.AlwaysMatch.ALWAYS_MATCH_RESULT;
import static com.google.devtools.build.lib.skyframe.serialization.analysis.NoMatch.NO_MATCH_RESULT;
import com.google.common.collect.ImmutableList;
@@ -143,7 +144,7 @@
public void matchingListing_matchesContainedFileChange() {
changes.registerFileChange("dir/a", 100);
- var key = new ListingDependencies(FileDependencies.builder("dir").build());
+ var key = ListingDependencies.from(FileDependencies.builder("dir").build());
assertThat(getLookupResult(key, 99)).isEqualTo(new FileOpMatch(100));
}
@@ -151,7 +152,7 @@
public void matchListingChange_matchesDirectoryChange() {
changes.registerFileChange("dir", 100);
- var key = new ListingDependencies(FileDependencies.builder("dir").build());
+ var key = ListingDependencies.from(FileDependencies.builder("dir").build());
assertThat(getLookupResult(key, 99)).isEqualTo(new FileOpMatch(100));
}
@@ -160,7 +161,7 @@
changes.registerFileChange("dep/a", 100);
var key =
- new ListingDependencies(
+ ListingDependencies.from(
FileDependencies.builder("dir")
.addDependency(FileDependencies.builder("dep/a").build())
.build());
@@ -168,6 +169,24 @@
assertThat(getLookupResult(key, 99)).isEqualTo(new FileOpMatch(100));
}
+ @Test
+ public void invalidation_missingFile() {
+ FileDependencies missingFile = FileDependencies.newMissingInstance();
+
+ var result = lookup.getValueOrFuture(missingFile, 99);
+
+ assertThat(result).isEqualTo(ALWAYS_MATCH_RESULT);
+ }
+
+ @Test
+ public void invalidation_missingListing() {
+ ListingDependencies missingListing = ListingDependencies.newMissingInstance();
+
+ var result = lookup.getValueOrFuture(missingListing, 99);
+
+ assertThat(result).isEqualTo(ALWAYS_MATCH_RESULT);
+ }
+
private FileOpMatchResult getLookupResult(FileOpDependency key, int validityHorizon) {
try {
switch (lookup.getValueOrFuture(key, validityHorizon)) {
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependenciesTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependenciesTest.java
index 76798b5..6c39933 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependenciesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/FileSystemDependenciesTest.java
@@ -18,6 +18,7 @@
import static com.google.devtools.build.lib.skyframe.serialization.analysis.VersionedChanges.NO_MATCH;
import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.skyframe.serialization.analysis.ListingDependencies.AvailableListingDependencies;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;
@@ -60,7 +61,9 @@
@Test
public void listingDependencies_findEarliestMatch_matchesClientChange() {
var changes = new VersionedChanges(ImmutableList.of("abc/def"));
- var dependencies = new ListingDependencies(FileDependencies.builder("abc").build());
+ var dependencies =
+ (AvailableListingDependencies)
+ ListingDependencies.from(FileDependencies.builder("abc").build());
assertThat(dependencies.findEarliestMatch(changes, 0)).isEqualTo(CLIENT_CHANGE);
}
@@ -71,7 +74,9 @@
changes.registerFileChange("abc/def", 99);
changes.registerFileChange("abc/ghi", 100);
- var dependencies = new ListingDependencies(FileDependencies.builder("abc").build());
+ var dependencies =
+ (AvailableListingDependencies)
+ ListingDependencies.from(FileDependencies.builder("abc").build());
assertThat(dependencies.findEarliestMatch(changes, 100)).isEqualTo(NO_MATCH);
assertThat(dependencies.findEarliestMatch(changes, 99)).isEqualTo(100);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchMemoizingLookupTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchMemoizingLookupTest.java
index 9e3f9cf..ce787e1 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchMemoizingLookupTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/NestedMatchMemoizingLookupTest.java
@@ -14,6 +14,7 @@
package com.google.devtools.build.lib.skyframe.serialization.analysis;
import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.lib.skyframe.serialization.analysis.AlwaysMatch.ALWAYS_MATCH_RESULT;
import static com.google.devtools.build.lib.skyframe.serialization.analysis.NestedMatchResultTypes.createNestedMatchResult;
import static com.google.devtools.build.lib.skyframe.serialization.analysis.NoMatch.NO_MATCH_RESULT;
import static com.google.devtools.build.lib.skyframe.serialization.analysis.VersionedChanges.NO_MATCH;
@@ -80,7 +81,7 @@
changes.registerFileChange("src/a", 98);
var key =
- new NestedDependencies(
+ NestedDependencies.from(
ImmutableList.of(
FileDependencies.builder("dep/a").build(),
FileDependencies.builder("dep/b").build(),
@@ -115,7 +116,7 @@
var depB = new ControllableFileDependencies(ImmutableList.of("dep/b"), ImmutableList.of());
var depC = new ControllableFileDependencies(ImmutableList.of("dep/c"), ImmutableList.of());
var srcA = new ControllableFileDependencies(ImmutableList.of("src/a"), ImmutableList.of());
- var key = new NestedDependencies(ImmutableList.of(depA, depB, depC), ImmutableList.of(srcA));
+ var key = NestedDependencies.from(ImmutableList.of(depA, depB, depC), ImmutableList.of(srcA));
var pool = new ForkJoinPool(4); // one for each dependency and source
pool.execute(
@@ -173,14 +174,14 @@
changes.registerFileChange("src/a", 102);
var nestedDep =
- new NestedDependencies(
+ NestedDependencies.from(
ImmutableList.of(
FileDependencies.builder("dep/b").build(),
FileDependencies.builder("dep/c").build()),
ImmutableList.of(FileDependencies.builder("src/a").build()));
var key =
- new NestedDependencies(
+ NestedDependencies.from(
ImmutableList.of(FileDependencies.builder("dep/a").build(), nestedDep),
ImmutableList.of());
@@ -208,14 +209,14 @@
changes.registerFileChange("src/a", 102);
var nestedDep =
- new NestedDependencies(
+ NestedDependencies.from(
ImmutableList.of(
FileDependencies.builder("dep/b").build(),
FileDependencies.builder("dep/c").build()),
ImmutableList.of(FileDependencies.builder("src/a").build()));
var key =
- new NestedDependencies(
+ NestedDependencies.from(
ImmutableList.of(FileDependencies.builder("dep/a").build(), nestedDep),
ImmutableList.of());
@@ -284,6 +285,15 @@
assertThat(result).isEqualTo(NO_MATCH_RESULT);
}
+ @Test
+ public void invalidation_missingNested() throws Exception {
+ NestedDependencies missingNested = NestedDependencies.newMissingInstance();
+
+ var lookupResult = lookup.getValueOrFuture(missingNested, 99);
+
+ assertThat(lookupResult).isEqualTo(ALWAYS_MATCH_RESULT);
+ }
+
private NestedMatchResult getLookupResult(NestedDependencies key, int validityHorizon) {
try {
switch (lookup.getValueOrFuture(key, validityHorizon)) {
@@ -317,7 +327,7 @@
}
private static NestedDependencies createNestedDependencies(FileDependencies fileDependency) {
- return new NestedDependencies(
+ return NestedDependencies.from(
new FileSystemDependencies[] {fileDependency}, NestedDependencies.EMPTY_SOURCES);
}
}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/VersionedChangesValidatorTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/VersionedChangesValidatorTest.java
index 879ac25..770b4fb 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/VersionedChangesValidatorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/analysis/VersionedChangesValidatorTest.java
@@ -70,7 +70,7 @@
changes.registerFileChange("src/a", 98);
var key =
- new NestedDependencies(
+ NestedDependencies.from(
ImmutableList.of(
FileDependencies.builder("dep/a").build(),
FileDependencies.builder("dep/b").build(),
@@ -91,14 +91,14 @@
changes.registerFileChange("dep/b", 102);
var keyA =
- new NestedDependencies(
+ NestedDependencies.from(
ImmutableList.of(
FileDependencies.builder("shared").build(),
FileDependencies.builder("dep/a").build()),
ImmutableList.of());
var keyB =
- new NestedDependencies(
+ NestedDependencies.from(
ImmutableList.of(
FileDependencies.builder("shared").build(),
FileDependencies.builder("dep/b").build()),
