diff options
Diffstat (limited to 'src')
3 files changed, 149 insertions, 14 deletions
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 326635dc37..8c1fa7f119 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java @@ -59,7 +59,17 @@ public class InMemoryNodeEntry implements NodeEntry { * the already-stored data. In that case, the version will remain the same. The version can be * thought of as the latest timestamp at which this entry was changed. */ - protected Version version = MinimalVersion.INSTANCE; + protected Version lastChangedVersion = MinimalVersion.INSTANCE; + + /** + * Returns the last version this entry was evaluated at, even if it re-evaluated to the same + * value. When a child signals this entry with the last version it was changed at in + * {@link #signalDep}, this entry need not re-evaluate if the child's version is at most this + * version, even if the {@link #lastChangedVersion} is less than this one. + * + * @see #signalDep(Version) + */ + protected Version lastEvaluatedVersion = MinimalVersion.INSTANCE; /** * This object represents a {@link GroupedList}<SkyKey> in a memory-efficient way. It stores the @@ -227,8 +237,11 @@ public class InMemoryNodeEntry implements NodeEntry { public synchronized Set<SkyKey> setValue(SkyValue value, Version version) { Preconditions.checkState(isReady(), "%s %s", this, value); // This check may need to be removed when we move to a non-linear versioning sequence. - Preconditions.checkState(this.version.atMost(version), - "%s %s %s", this, version, value); + Preconditions.checkState( + this.lastChangedVersion.atMost(version), "%s %s %s", this, version, value); + Preconditions.checkState( + this.lastEvaluatedVersion.atMost(version), "%s %s %s", this, version, value); + this.lastEvaluatedVersion = version; if (isDirty() && buildingState.unchangedFromLastBuild(value)) { // If the value is the same as before, just use the old value. Note that we don't use the new @@ -237,7 +250,7 @@ public class InMemoryNodeEntry implements NodeEntry { } else { // If this is a new value, or it has changed since the last build, set the version to the // current graph version. - this.version = version; + this.lastChangedVersion = version; this.value = value; } @@ -311,7 +324,7 @@ public class InMemoryNodeEntry implements NodeEntry { @Override public synchronized boolean signalDep(Version childVersion) { Preconditions.checkState(!isDone(), "Value must not be done in signalDep %s", this); - return buildingState.signalDep(/*childChanged=*/!childVersion.atMost(getVersion())); + return buildingState.signalDep(/*childChanged=*/ !childVersion.atMost(lastEvaluatedVersion)); } @Override @@ -371,7 +384,7 @@ public class InMemoryNodeEntry implements NodeEntry { @Override public synchronized Version getVersion() { - return version; + return lastChangedVersion; } /** @see BuildingState#getDirtyState() */ @@ -436,7 +449,8 @@ public class InMemoryNodeEntry implements NodeEntry { return MoreObjects.toStringHelper(this) .add("identity", System.identityHashCode(this)) .add("value", value) - .add("version", version) + .add("lastChangedVersion", lastChangedVersion) + .add("lastEvaluatedVersion", lastEvaluatedVersion) .add("directDeps", directDeps == null ? null : GroupedList.create(directDeps)) .add("reverseDeps", REVERSE_DEPS_UTIL.toString(this)) .add("buildingState", buildingState) @@ -453,7 +467,8 @@ public class InMemoryNodeEntry implements NodeEntry { Preconditions.checkState(isDone(), "Only done nodes can be copied: %s", this); InMemoryNodeEntry nodeEntry = new InMemoryNodeEntry(); nodeEntry.value = value; - nodeEntry.version = this.version; + nodeEntry.lastChangedVersion = this.lastChangedVersion; + nodeEntry.lastEvaluatedVersion = this.lastEvaluatedVersion; REVERSE_DEPS_UTIL.addReverseDeps(nodeEntry, REVERSE_DEPS_UTIL.getReverseDeps(this)); nodeEntry.directDeps = directDeps; nodeEntry.buildingState = null; 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 bf157b29bd..8d9b51db5f 100644 --- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java @@ -168,7 +168,7 @@ public interface NodeEntry extends ThinNodeEntry { /** * Tell this node that one of its dependencies is now done. Callers must check the return value, * and if true, they must re-schedule this node for evaluation. Equivalent to - * {@code #signalDep(Long.MAX_VALUE)}. Since this entry's version is less than + * {@code #signalDep(Long.MAX_VALUE)}. Since this entry was last evaluated at a version less than * {@link Long#MAX_VALUE}, informing this entry that a child of it has version * {@link Long#MAX_VALUE} will force it to re-evaluate. */ @@ -179,11 +179,20 @@ public interface NodeEntry extends ThinNodeEntry { * Tell this entry that one of its dependencies is now done. Callers must check the return value, * and if true, they must re-schedule this node for evaluation. * - * @param childVersion If this entry {@link #isDirty()} and {@code childVersion} is not at most - * {@link #getVersion()}, then this entry records that one of its children has changed since it - * was last evaluated (namely, it was last evaluated at version {@link #getVersion()} and the - * child was last evaluated at {@code childVersion}. Thus, the next call to - * {@link #getDirtyState()} will return {@link DirtyState#NEEDS_REBUILDING}. + * <p>Even if {@code childVersion} is not at most {@link #getVersion}, this entry may not rebuild, + * in the case that the entry already rebuilt at {@code childVersion} and discovered that it had + * the same value as at an earlier version. For instance, after evaluating at version v1, at + * version v2, child has a new value, but parent re-evaluates and finds it has the same value, + * child.getVersion() will return v2 and parent.getVersion() will return v1. At v3 parent is + * dirtied and checks its dep on child. child signals parent with version v2. That should not in + * and of itself trigger a rebuild, since parent has already rebuilt with child at v2. + * + * + * @param childVersion If this entry {@link #isDirty()} and the last version at which this entry + * was evaluated did not include the changes at version {@code childVersion} (for instance, if + * {@code childVersion} is after the last version at which this entry was evaluated), then this + * entry records that one of its children has changed since it was last evaluated. Thus, the next + * call to {@link #getDirtyState()} will return {@link DirtyState#NEEDS_REBUILDING}. */ @ThreadSafe boolean signalDep(Version childVersion); diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java index cea62e2276..fdae6b25c0 100644 --- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java +++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java @@ -2334,6 +2334,117 @@ public class MemoizingEvaluatorTest { } @Test + public void changePruningAfterParentPrunes() throws Exception { + initializeTester(); + final SkyKey leaf = GraphTester.toSkyKey("leaf"); + SkyKey top = GraphTester.toSkyKey("top"); + tester.set(leaf, new StringValue("leafy")); + // When top depends on leaf, but always returns the same value, + final StringValue fixedTopValue = new StringValue("top"); + final AtomicBoolean topEvaluated = new AtomicBoolean(false); + tester + .getOrCreate(top) + .setBuilder( + new SkyFunction() { + @Override + public SkyValue compute(SkyKey skyKey, Environment env) { + topEvaluated.set(true); + return env.getValue(leaf) == null ? null : fixedTopValue; + } + + @Nullable + @Override + public String extractTag(SkyKey skyKey) { + return null; + } + }); + // And top is evaluated, + StringValue topValue = (StringValue) tester.evalAndGet("top"); + // Then top's value is as expected, + assertEquals(fixedTopValue, topValue); + // And top was actually evaluated. + assertThat(topEvaluated.get()).isTrue(); + // When leaf is changed, + tester.set(leaf, new StringValue("crunchy")); + tester.invalidate(); + topEvaluated.set(false); + // And top is evaluated, + StringValue topValue2 = (StringValue) tester.evalAndGet("top"); + // Then top's value is as expected, + assertEquals(fixedTopValue, topValue2); + // And top was actually evaluated. + assertThat(topEvaluated.get()).isTrue(); + // When leaf is invalidated but not actually changed, + tester.getOrCreate(leaf, /*markAsModified=*/ true); + tester.invalidate(); + topEvaluated.set(false); + // And top is evaluated, + StringValue topValue3 = (StringValue) tester.evalAndGet("top"); + // Then top's value is as expected, + assertEquals(fixedTopValue, topValue3); + // And top was *not* actually evaluated, because change pruning cut off evaluation. + assertThat(topEvaluated.get()).isFalse(); + } + + @Test + public void changePruningFromOtherNodeAfterParentPrunes() throws Exception { + initializeTester(); + final SkyKey leaf = GraphTester.toSkyKey("leaf"); + final SkyKey other = GraphTester.toSkyKey("other"); + SkyKey top = GraphTester.toSkyKey("top"); + tester.set(leaf, new StringValue("leafy")); + tester.set(other, new StringValue("other")); + // When top depends on leaf and other, but always returns the same value, + final StringValue fixedTopValue = new StringValue("top"); + final AtomicBoolean topEvaluated = new AtomicBoolean(false); + tester + .getOrCreate(top) + .setBuilder( + new SkyFunction() { + @Override + public SkyValue compute(SkyKey skyKey, Environment env) { + topEvaluated.set(true); + + return env.getValue(other) == null || env.getValue(leaf) == null + ? null + : fixedTopValue; + } + + @Nullable + @Override + public String extractTag(SkyKey skyKey) { + return null; + } + }); + // And top is evaluated, + StringValue topValue = (StringValue) tester.evalAndGet("top"); + // Then top's value is as expected, + assertEquals(fixedTopValue, topValue); + // And top was actually evaluated. + assertThat(topEvaluated.get()).isTrue(); + // When leaf is changed, + tester.set(leaf, new StringValue("crunchy")); + tester.invalidate(); + topEvaluated.set(false); + // And top is evaluated, + StringValue topValue2 = (StringValue) tester.evalAndGet("top"); + // Then top's value is as expected, + assertEquals(fixedTopValue, topValue2); + // And top was actually evaluated. + assertThat(topEvaluated.get()).isTrue(); + // When other is invalidated but not actually changed, + tester.getOrCreate(other, /*markAsModified=*/ true); + tester.invalidate(); + topEvaluated.set(false); + // And top is evaluated, + StringValue topValue3 = (StringValue) tester.evalAndGet("top"); + // Then top's value is as expected, + assertEquals(fixedTopValue, topValue3); + // And top was *not* actually evaluated, because change pruning cut off evaluation. + assertThat(topEvaluated.get()).isFalse(); + } + + @Test public void changedChildChangesDepOfParent() throws Exception { initializeTester(); final SkyKey buildFile = GraphTester.toSkyKey("buildFile"); |