Allow NodeEntries to prune their deps based on fingerprinting the dep group. This is useful in situations in which the deps themselves are forbidden from value-based pruning because of subtle version bugs.
PiperOrigin-RevId: 224922819
diff --git a/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java b/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java
index 71ba6bc..5dd418b 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java
@@ -26,9 +26,11 @@
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.lib.vfs.Symlinks;
+import com.google.devtools.build.skyframe.BigIntegerFingerprintUtils;
import com.google.devtools.build.skyframe.SkyValue;
import java.io.ByteArrayInputStream;
import java.io.IOException;
+import java.math.BigInteger;
import java.util.Arrays;
import java.util.Objects;
import javax.annotation.Nullable;
@@ -101,6 +103,17 @@
*/
public abstract long getModifiedTime();
+ @Nullable
+ @Override
+ public BigInteger getValueFingerprint() {
+ byte[] digest = getDigest();
+ if (digest != null) {
+ return BigIntegerFingerprintUtils.fingerprintOf(digest);
+ }
+ // TODO(janakr): return fingerprint in other cases: symlink, directory.
+ return null;
+ }
+
/**
* Index used to resolve remote files.
*
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
index c8c3aa6..56fe045 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
@@ -683,7 +683,10 @@
prevEntry.noDepsLastBuild(), "existing entry for %s has deps: %s", key, prevEntry);
prevEntry.markRebuilding();
}
- prevEntry.setValue(value, version);
+ prevEntry.setValue(
+ value,
+ version,
+ prevEntry.canPruneDepsByFingerprint() ? new DepFingerprintList.Builder(0).build() : null);
// Now that this key's injected value is set, it is no longer dirty.
progressReceiver.injected(key);
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
index 2c758fd..51731f5 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -38,6 +38,7 @@
import com.google.devtools.build.skyframe.SkyFunctionEnvironment.UndonePreviouslyRequestedDep;
import com.google.devtools.build.skyframe.SkyFunctionException.ReifiedSkyFunctionException;
import com.google.devtools.build.skyframe.ThinNodeEntry.DirtyType;
+import java.math.BigInteger;
import java.time.Duration;
import java.util.Collection;
import java.util.Iterator;
@@ -316,7 +317,21 @@
skyKey, reverseDeps, state.getVersion(), EnqueueParentBehavior.ENQUEUE);
return DirtyOutcome.ALREADY_PROCESSED;
case NEEDS_REBUILDING:
- maybeMarkRebuilding(state);
+ if (state.canPruneDepsByFingerprint()) {
+ Iterable<SkyKey> lastDirectDepsKeys =
+ state.getLastDirectDepsGroupWhenPruningDepsByFingerprint();
+ if (lastDirectDepsKeys != null) {
+ BigInteger groupFingerprint =
+ composeDepFingerprints(
+ lastDirectDepsKeys,
+ evaluatorContext.getBatchValues(
+ skyKey, Reason.DEP_REQUESTED, lastDirectDepsKeys));
+ if (state.unmarkNeedsRebuildingIfGroupUnchangedUsingFingerprint(groupFingerprint)) {
+ return maybeHandleDirtyNode(state);
+ }
+ }
+ }
+ state.markRebuilding();
return DirtyOutcome.NEEDS_EVALUATION;
case NEEDS_FORCED_REBUILDING:
state.forceRebuild();
@@ -855,6 +870,31 @@
return true;
}
+ static BigInteger composeDepFingerprints(
+ Iterable<SkyKey> directDepGroup, Map<SkyKey, ? extends NodeEntry> depEntries)
+ throws InterruptedException {
+ BigInteger groupFingerprint = BigInteger.ZERO;
+ for (SkyKey dep : directDepGroup) {
+ NodeEntry depEntry = depEntries.get(dep);
+ if (!isDoneForBuild(depEntry)) {
+ // Something weird happened: maybe something fell out of graph or was restarted?
+ return null;
+ }
+ SkyValue depValue = depEntry.getValue();
+ if (depValue == null) {
+ return null;
+ }
+ BigInteger depFingerprint = depValue.getValueFingerprint();
+ if (depFingerprint == null) {
+ // TODO(janakr): Use transitive data here.
+ return null;
+ }
+ groupFingerprint =
+ BigIntegerFingerprintUtils.composeOrdered(groupFingerprint, depFingerprint);
+ }
+ return groupFingerprint;
+ }
+
/**
* Return true if the entry does not need to be re-evaluated this build. The entry will need to be
* re-evaluated if it is not done, but also if it was not completely evaluated last build and this
diff --git a/src/main/java/com/google/devtools/build/skyframe/BUILD b/src/main/java/com/google/devtools/build/skyframe/BUILD
index e8cd3ac..7de5e27 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BUILD
+++ b/src/main/java/com/google/devtools/build/skyframe/BUILD
@@ -19,6 +19,7 @@
visibility = ["//visibility:public"],
deps = [
"//third_party:guava",
+ "//third_party:jsr305",
],
)
diff --git a/src/main/java/com/google/devtools/build/skyframe/BigIntegerFingerprintUtils.java b/src/main/java/com/google/devtools/build/skyframe/BigIntegerFingerprintUtils.java
new file mode 100644
index 0000000..337a454
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/BigIntegerFingerprintUtils.java
@@ -0,0 +1,92 @@
+// Copyright 2018 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.skyframe;
+
+import java.math.BigInteger;
+import java.util.Arrays;
+import javax.annotation.Nullable;
+
+/** Utility class for fingerprint composition. */
+public final class BigIntegerFingerprintUtils {
+ private static final int BITS = 128;
+ public static final int BYTES = BITS / 8;
+
+ private static final BigInteger UINT128_LIMIT = BigInteger.ONE.shiftLeft(BITS);
+ private static final BigInteger RELATIVE_PRIME = BigInteger.valueOf(31);
+
+ private BigIntegerFingerprintUtils() {}
+
+ public static BigInteger compose(BigInteger v1, BigInteger v2) {
+ BigInteger temp = v1.add(v2);
+ if (temp.compareTo(UINT128_LIMIT) >= 0) {
+ return temp.subtract(UINT128_LIMIT);
+ }
+ return temp;
+ }
+
+ /**
+ * Converts a byte array to a BigInteger in the fingerprint range (no more than {@link
+ * #UINT128_LIMIT}).
+ */
+ public static BigInteger fingerprintOf(byte[] bytes) {
+ int numSegments = bytes.length / BYTES;
+ if (numSegments == 0) {
+ return new BigInteger(bytes);
+ }
+ BigInteger result = new BigInteger(/*signum=*/ 1, Arrays.copyOf(bytes, BYTES));
+ for (int segment = 1; segment < numSegments; segment++) {
+ result =
+ composeOrdered(
+ result,
+ new BigInteger(
+ /*signum=*/ 1,
+ Arrays.copyOfRange(bytes, segment * BYTES, (segment + 1) * BYTES)));
+ }
+ if (numSegments * BYTES < bytes.length) {
+ result =
+ composeOrdered(
+ result,
+ new BigInteger(
+ /*signum=*/ 1, Arrays.copyOfRange(bytes, numSegments * BYTES, bytes.length)));
+ }
+ return result;
+ }
+ /**
+ * Unordered, nullable composition.
+ *
+ * <p>null is absorbing and is used to convey errors and unavailability
+ */
+ @Nullable
+ public static BigInteger composeNullable(@Nullable BigInteger v1, @Nullable BigInteger v2) {
+ if (v1 == null || v2 == null) {
+ return null;
+ }
+ return compose(v1, v2);
+ }
+
+ public static BigInteger composeOrdered(BigInteger accumulator, BigInteger v) {
+ return compose(accumulator.multiply(RELATIVE_PRIME).mod(UINT128_LIMIT), v);
+ }
+
+ @Nullable
+ public static BigInteger composeOrderedNullable(
+ @Nullable BigInteger accumulator, @Nullable BigInteger v) {
+ if (accumulator == null || v == null) {
+ return null;
+ }
+ return compose(accumulator.multiply(RELATIVE_PRIME).mod(UINT128_LIMIT), v);
+ }
+
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
index 147f681..d6c1b5e 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -15,6 +15,7 @@
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
+import java.math.BigInteger;
import java.util.Collection;
import java.util.Set;
import javax.annotation.Nullable;
@@ -54,8 +55,10 @@
}
@Override
- public Set<SkyKey> setValue(SkyValue value, Version version) throws InterruptedException {
- return getDelegate().setValue(value, version);
+ public Set<SkyKey> setValue(
+ SkyValue value, Version version, DepFingerprintList depFingerprintList)
+ throws InterruptedException {
+ return getDelegate().setValue(value, version, depFingerprintList);
}
@Override
@@ -116,6 +119,24 @@
}
@Override
+ public boolean canPruneDepsByFingerprint() {
+ return getDelegate().canPruneDepsByFingerprint();
+ }
+
+ @Nullable
+ @Override
+ public Iterable<SkyKey> getLastDirectDepsGroupWhenPruningDepsByFingerprint()
+ throws InterruptedException {
+ return getDelegate().getLastDirectDepsGroupWhenPruningDepsByFingerprint();
+ }
+
+ @Override
+ public boolean unmarkNeedsRebuildingIfGroupUnchangedUsingFingerprint(
+ BigInteger groupFingerprint) {
+ return getDelegate().unmarkNeedsRebuildingIfGroupUnchangedUsingFingerprint(groupFingerprint);
+ }
+
+ @Override
public Iterable<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
return getDelegate().getAllReverseDepsForNodeBeingDeleted();
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/DepFingerprintList.java b/src/main/java/com/google/devtools/build/skyframe/DepFingerprintList.java
new file mode 100644
index 0000000..4a7fbf4
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/DepFingerprintList.java
@@ -0,0 +1,96 @@
+// Copyright 2018 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.skyframe;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Iterators;
+import java.math.BigInteger;
+import java.util.Iterator;
+import javax.annotation.Nullable;
+
+/** List of fingerprints, each of which is a nullable {@link BigInteger}. Ordered and immutable. */
+public class DepFingerprintList implements Iterable<BigInteger> {
+ /**
+ * Marker object indicating that dep fingerprints are not being tracked, and so there should be no
+ * attempts to use this dep fingerprints object. Clients can compare their {@code
+ * DepFingerprintList} object to this one using reference equality to see if they are tracking dep
+ * fingerprints. This object should never be passed in as a valid {@code DepFingerprintList}
+ * object.
+ */
+ public static final DepFingerprintList NOT_TRACKING_MARKER = new NoDepGroupsFingerprintMarker();
+
+ private static final DepFingerprintList EMPTY_DEP_GROUPS_FINGERPRINT =
+ new DepFingerprintList(new BigInteger[0]);
+
+ private final BigInteger[] fingerprints;
+
+ private DepFingerprintList(BigInteger[] fingerprints) {
+ this.fingerprints = fingerprints;
+ }
+
+ /**
+ * Returns the {@link BigInteger} for the dep group at {@code index}. A null value indicates that
+ * a fingerprint could not be computed for this group, so that equality-by-dep-group checking
+ * cannot be performed for this group.
+ */
+ @Nullable
+ public BigInteger get(int index) {
+ return fingerprints[index];
+ }
+
+ @Override
+ public Iterator<BigInteger> iterator() {
+ return Iterators.forArray(fingerprints);
+ }
+
+ private static class NoDepGroupsFingerprintMarker extends DepFingerprintList {
+ private NoDepGroupsFingerprintMarker() {
+ super(null);
+ }
+
+ @Override
+ public BigInteger get(int index) {
+ throw new UnsupportedOperationException("No dep groups fingerprint (" + index + ")");
+ }
+
+ @Override
+ public Iterator<BigInteger> iterator() {
+ throw new UnsupportedOperationException("No dep groups fingerprint");
+ }
+ }
+
+ /** Builder for {@code DepFingerprintList}. */
+ public static class Builder {
+ private int curIndex = 0;
+ private final BigInteger[] fingerprints;
+
+ public Builder(int size) {
+ fingerprints = new BigInteger[size];
+ }
+
+ public void add(BigInteger fingerprint) {
+ fingerprints[curIndex++] = fingerprint;
+ }
+
+ public DepFingerprintList build() {
+ Preconditions.checkState(
+ curIndex == fingerprints.length, "%s %s", curIndex, fingerprints.length);
+ if (fingerprints.length == 0) {
+ return EMPTY_DEP_GROUPS_FINGERPRINT;
+ }
+ return new DepFingerprintList(fingerprints);
+ }
+ }
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
index ea5ec34..eca9fd7 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -149,6 +149,15 @@
}
}
+ public final void unmarkNeedsRebuilding() {
+ Preconditions.checkState(dirtyState == DirtyState.NEEDS_REBUILDING, this);
+ if (getNumOfGroupsInLastBuildDirectDeps() == dirtyDirectDepIndex) {
+ dirtyState = DirtyState.VERIFIED_CLEAN;
+ } else {
+ dirtyState = DirtyState.CHECK_DEPENDENCIES;
+ }
+ }
+
/**
* Returns true if {@code newValue}.equals the value from the last time this node was built.
* Should only be used by {@link NodeEntry#setValue}.
@@ -219,6 +228,10 @@
dirtyState = DirtyState.REBUILDING;
}
+ public int getLastDirtyDirectDepIndex() {
+ return dirtyDirectDepIndex - 1;
+ }
+
protected MoreObjects.ToStringHelper getStringHelper() {
return MoreObjects.toStringHelper(this)
.add("dirtyState", dirtyState)
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
index f0dadac..bd453ca3 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -22,6 +22,7 @@
import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
import com.google.devtools.build.skyframe.KeyToConsolidate.Op;
import com.google.devtools.build.skyframe.KeyToConsolidate.OpToStoreBare;
+import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
@@ -295,13 +296,21 @@
// although this method itself is synchronized, there are unsynchronized consumers of the version
// and the value.
@Override
- public synchronized Set<SkyKey> setValue(SkyValue value, Version version)
+ public synchronized Set<SkyKey> setValue(
+ SkyValue value, Version version, DepFingerprintList depFingerprintList)
throws InterruptedException {
Preconditions.checkState(isReady(), "%s %s", this, value);
+ if (depFingerprintList != null) {
+ logError(
+ new IllegalStateException(
+ String.format(
+ "Expect no depFingerprintList here: %s %s %s %s",
+ this, depFingerprintList, value, version)));
+ }
assertVersionCompatibleWhenSettingValue(version, value);
this.lastEvaluatedVersion = version;
- if (!isEligibleForChangePruning()) {
+ if (!isEligibleForChangePruningOnUnchangedValue()) {
this.lastChangedVersion = version;
this.value = value;
} else if (isDirty() && getDirtyBuildingState().unchangedFromLastBuild(value)) {
@@ -324,13 +333,13 @@
}
/**
- * Returns {@code true} if this node is eligible to be change-pruned when its value has not
+ * Returns {@code true} if this node is eligible to be change pruned when its value has not
* changed from the last build.
*
- * <p>Implementations need not check whether the value has changed - nodes will only be
- * change-pruned if the value has not changed.
+ * <p>Implementations need not check whether the value has changed - this will only be called if
+ * the value has not changed.
*/
- public boolean isEligibleForChangePruning() {
+ public boolean isEligibleForChangePruningOnUnchangedValue() {
return true;
}
@@ -624,8 +633,36 @@
}
@Override
+ public boolean canPruneDepsByFingerprint() {
+ return false;
+ }
+
+ @Nullable
+ @Override
+ public Iterable<SkyKey> getLastDirectDepsGroupWhenPruningDepsByFingerprint()
+ throws InterruptedException {
+ throw new UnsupportedOperationException(this.toString());
+ }
+
+ @Override
+ public boolean unmarkNeedsRebuildingIfGroupUnchangedUsingFingerprint(
+ BigInteger groupFingerprint) {
+ throw new UnsupportedOperationException(this.toString());
+ }
+
+ /**
+ * If this entry {@link #canPruneDepsByFingerprint} and has that data, returns a list of dep group
+ * fingerprints. Otherwise returns null.
+ */
+ @Nullable
+ public DepFingerprintList getDepFingerprintList() {
+ Preconditions.checkState(isDone(), this);
+ return null;
+ }
+
+ @Override
public synchronized void markRebuilding() {
- getDirtyBuildingState().markRebuilding(isEligibleForChangePruning());
+ getDirtyBuildingState().markRebuilding(isEligibleForChangePruningOnUnchangedValue());
}
@SuppressWarnings("unchecked")
@@ -715,8 +752,7 @@
return signaledDeps > NOT_EVALUATING_SENTINEL;
}
- @Override
- public synchronized String toString() {
+ protected synchronized MoreObjects.ToStringHelper toStringHelper() {
return MoreObjects.toStringHelper(this)
.add("identity", System.identityHashCode(this))
.add("value", value)
@@ -725,8 +761,12 @@
.add("directDeps", isDone() ? GroupedList.create(directDeps) : directDeps)
.add("signaledDeps", signaledDeps)
.add("reverseDeps", ReverseDepsUtility.toString(this))
- .add("dirtyBuildingState", dirtyBuildingState)
- .toString();
+ .add("dirtyBuildingState", dirtyBuildingState);
+ }
+
+ @Override
+ public final synchronized String toString() {
+ return toStringHelper().toString();
}
protected synchronized InMemoryNodeEntry cloneNodeEntry(InMemoryNodeEntry newEntry) {
diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
index 90b36b7..5c5797cb 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -16,6 +16,7 @@
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
+import java.math.BigInteger;
import java.util.Collection;
import java.util.Set;
import javax.annotation.Nullable;
@@ -177,9 +178,13 @@
* entry determines that the new value is equal to the previous value, the entry will keep its
* current version. Callers can query that version to see if the node considers its value to have
* changed.
+ *
+ * <p>{@code depFingerprintList} must be non-null iff {@link #canPruneDepsByFingerprint}.
*/
@ThreadSafe
- Set<SkyKey> setValue(SkyValue value, Version version) throws InterruptedException;
+ Set<SkyKey> setValue(
+ SkyValue value, Version version, @Nullable DepFingerprintList depFingerprintList)
+ throws InterruptedException;
/**
* Queries if the node is done and adds the given key as a reverse dependency. The return code
@@ -345,6 +350,42 @@
Set<SkyKey> getAllRemainingDirtyDirectDeps() throws InterruptedException;
/**
+ * Whether this entry stores fingerprints of its dep groups, which enables it to change-prune
+ * (avoid re-evaluating) if the values in a dep group haven't changed. This is normally handled by
+ * version-based change pruning, but some graph evaluation modes do not support that (see {@link
+ * InMemoryNodeEntry#isEligibleForChangePruningOnUnchangedValue}). For such evaluation modes, the
+ * downstream dependents of nodes that have not changed can avoid re-evaluation via this
+ * change-pruning mode.
+ */
+ boolean canPruneDepsByFingerprint();
+
+ /**
+ * Can only be called if {@link #canPruneDepsByFingerprint} is true, during dirtiness checking
+ * when the entry is marked as {@link DirtyState#NEEDS_REBUILDING}. Returns the last direct deps
+ * group that was checked, so that its fingerprint can be calculated.
+ *
+ * <p>Returns null if fingerprint information is not stored for this group, and so computing the
+ * new fingerprint would be useless.
+ */
+ @Nullable
+ Iterable<SkyKey> getLastDirectDepsGroupWhenPruningDepsByFingerprint() throws InterruptedException;
+
+ /**
+ * Can only be called if {@link #canPruneDepsByFingerprint} is true, during dirtiness checking
+ * when the entry is marked as {@link DirtyState#NEEDS_REBUILDING}. {@code groupFingerprint} is
+ * the fingerprint that was calculated from the deps returned by {@link
+ * #getLastDirectDepsGroupWhenPruningDepsByFingerprint}.
+ *
+ * <p>If the dep group fingerprint is the same as the stored value, modifies this entry so that
+ * the dirty state is what it would have been if the last dep group had <i>not</i> triggered a
+ * {@link DirtyState#NEEDS_REBUILDING} state: either {@link DirtyState#CHECK_DEPENDENCIES} or
+ * {@link DirtyState#VERIFIED_CLEAN} (if this was the last dep group). Returns true if the
+ * fingerprints matched.
+ */
+ @ThreadSafe
+ boolean unmarkNeedsRebuildingIfGroupUnchangedUsingFingerprint(BigInteger groupFingerprint);
+
+ /**
* Notifies a node that it is about to be rebuilt. This method can only be called if the node
* {@link DirtyState#NEEDS_REBUILDING}. After this call, this node is ready to be rebuilt (it will
* be in {@link DirtyState#REBUILDING}).
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
index fdb7c2d..c475d77 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -724,6 +724,22 @@
oldDepEntry.removeReverseDep(skyKey);
}
}
+ DepFingerprintList depFingerprintList = null;
+ if (primaryEntry.canPruneDepsByFingerprint()) {
+ DepFingerprintList.Builder depFingerprintListBuilder =
+ new DepFingerprintList.Builder(temporaryDirectDeps.listSize());
+ // TODO(janakr): in the common case, all these nodes may be locally cached. Do multi-level
+ // checking a la #getDepValuesForDoneNodeFromErrorOrDepsOrGraph to save graph lookups?
+ Map<SkyKey, ? extends NodeEntry> allDeps =
+ evaluatorContext.getBatchValues(
+ skyKey, Reason.DEP_REQUESTED, temporaryDirectDeps.getAllElementsAsIterable());
+ for (Collection<SkyKey> depGroup : temporaryDirectDeps) {
+ depFingerprintListBuilder.add(
+ AbstractParallelEvaluator.composeDepFingerprints(depGroup, allDeps));
+ }
+ depFingerprintList = depFingerprintListBuilder.build();
+ }
+
Version evaluationVersion = maxChildVersion;
if (bubbleErrorInfo != null) {
// Cycles can lead to a state where the versions of done children don't accurately reflect the
@@ -746,7 +762,8 @@
Version previousVersion = primaryEntry.getVersion();
// If this entry is dirty, setValue may not actually change it, if it determines that
// the data being written now is the same as the data already present in the entry.
- Set<SkyKey> reverseDeps = primaryEntry.setValue(valueWithMetadata, evaluationVersion);
+ Set<SkyKey> reverseDeps =
+ primaryEntry.setValue(valueWithMetadata, evaluationVersion, depFingerprintList);
// Note that if this update didn't actually change the entry, this version may not be
// evaluationVersion.
Version currentVersion = primaryEntry.getVersion();
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyValue.java b/src/main/java/com/google/devtools/build/skyframe/SkyValue.java
index 4f0e19a..fdac334 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyValue.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyValue.java
@@ -14,9 +14,20 @@
package com.google.devtools.build.skyframe;
import java.io.Serializable;
+import java.math.BigInteger;
+import javax.annotation.Nullable;
/**
* A return value of a {@code SkyFunction}.
*/
public interface SkyValue extends Serializable {
+ /**
+ * If non-null, a fingerprint for this value such that two values are equal iff they have the same
+ * fingerprint. For use during dep-fingerprint-based change pruning: see {@link
+ * NodeEntry#canPruneDepsByFingerprint}.
+ */
+ @Nullable
+ default BigInteger getValueFingerprint() {
+ return null;
+ }
}
diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
index d9e125b..9a83bde 100644
--- a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
+++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
@@ -147,9 +147,11 @@
}
@Override
- public Set<SkyKey> setValue(SkyValue value, Version version) throws InterruptedException {
+ public Set<SkyKey> setValue(
+ SkyValue value, Version version, DepFingerprintList depFingerprintList)
+ throws InterruptedException {
TreeSet<SkyKey> result = new TreeSet<>(ALPHABETICAL_SKYKEY_COMPARATOR);
- result.addAll(super.setValue(value, version));
+ result.addAll(super.setValue(value, version, depFingerprintList));
return result;
}
}
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
index 366385c..868db68 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
@@ -210,7 +210,7 @@
}
waitForStart.countDown();
waitForAddedRdep.await(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
- entry.setValue(new StringValue("foo1"), startingVersion);
+ entry.setValue(new StringValue("foo1"), startingVersion, null);
waitForSetValue.countDown();
wrapper.waitForTasksAndMaybeThrow();
assertThat(ExecutorUtil.interruptibleShutdown(pool)).isFalse();
@@ -226,7 +226,7 @@
sameEntry.markDirty(DirtyType.CHANGE);
startEvaluation(sameEntry);
sameEntry.markRebuilding();
- sameEntry.setValue(new StringValue("foo2"), getNextVersion(startingVersion));
+ sameEntry.setValue(new StringValue("foo2"), getNextVersion(startingVersion), null);
assertThat(graph.get(null, Reason.OTHER, key).getValue()).isEqualTo(new StringValue("foo2"));
if (checkRdeps()) {
assertThat(graph.get(null, Reason.OTHER, key).getReverseDepsForDoneEntry())
@@ -282,7 +282,7 @@
if (startEvaluation(entry).equals(DependencyState.NEEDS_SCHEDULING)) {
assertThat(valuesSet.add(key)).isTrue();
// Set to done.
- entry.setValue(new StringValue("bar" + keyNum), startingVersion);
+ entry.setValue(new StringValue("bar" + keyNum), startingVersion, null);
assertThat(entry.isDone()).isTrue();
}
} catch (InterruptedException e) {
@@ -332,7 +332,7 @@
for (int i = 0; i < numKeys; i++) {
NodeEntry entry = entries.get(key("foo" + i));
startEvaluation(entry);
- entry.setValue(new StringValue("bar"), startingVersion);
+ entry.setValue(new StringValue("bar"), startingVersion, null);
}
assertThat(graph.get(null, Reason.OTHER, key("foo" + 0))).isNotNull();
@@ -377,7 +377,8 @@
addTemporaryDirectDep(entry, key("dep"));
entry.signalDep();
- entry.setValue(new StringValue("bar" + keyNum), getNextVersion(startingVersion));
+ entry.setValue(
+ new StringValue("bar" + keyNum), getNextVersion(startingVersion), null);
} catch (InterruptedException e) {
throw new IllegalStateException(keyNum + ", " + entry, e);
}
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index ef26381..1dc4717 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -613,7 +613,7 @@
NodeEntry entry =
new InMemoryNodeEntry() {
@Override
- public boolean isEligibleForChangePruning() {
+ public boolean isEligibleForChangePruningOnUnchangedValue() {
return false;
}
};
@@ -756,7 +756,7 @@
.isEqualTo(DependencyState.NEEDS_SCHEDULING);
addTemporaryDirectDep(entry, originalChild);
entry.signalDep();
- entry.setValue(originalValue, version);
+ entry.setValue(originalValue, version, null);
entry.addReverseDepAndCheckIfDone(key("parent1"));
InMemoryNodeEntry clone1 = entry.cloneNodeEntry();
entry.addReverseDepAndCheckIfDone(key("parent2"));
@@ -770,7 +770,7 @@
addTemporaryDirectDep(clone2, newChild);
clone2.signalDep();
clone2.markRebuilding();
- clone2.setValue(updatedValue, version.next());
+ clone2.setValue(updatedValue, version.next(), null);
assertThat(entry.getVersion()).isEqualTo(version);
assertThat(clone1.getVersion()).isEqualTo(version);
@@ -813,7 +813,7 @@
entry.signalDep();
}
}
- entry.setValue(new IntegerValue(42), IntVersion.of(42L));
+ entry.setValue(new IntegerValue(42), IntVersion.of(42L), null);
int i = 0;
GroupedList<SkyKey> entryGroupedDirectDeps = entry.getGroupedDirectDeps();
assertThat(Iterables.size(entryGroupedDirectDeps)).isEqualTo(groupedDirectDeps.size());
@@ -827,7 +827,8 @@
throws InterruptedException {
return entry.setValue(
ValueWithMetadata.normal(value, errorInfo, NO_EVENTS, NO_POSTS),
- IntVersion.of(graphVersion));
+ IntVersion.of(graphVersion),
+ null);
}
private static void addTemporaryDirectDep(NodeEntry entry, SkyKey key) {
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
index dee4b9e..302e469 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
@@ -254,9 +254,11 @@
}
@Override
- public Set<SkyKey> setValue(SkyValue value, Version version) throws InterruptedException {
+ public Set<SkyKey> setValue(
+ SkyValue value, Version version, DepFingerprintList depFingerprintList)
+ throws InterruptedException {
graphListener.accept(myKey, EventType.SET_VALUE, Order.BEFORE, value);
- Set<SkyKey> result = super.setValue(value, version);
+ Set<SkyKey> result = super.setValue(value, version, depFingerprintList);
graphListener.accept(myKey, EventType.SET_VALUE, Order.AFTER, value);
return result;
}
