Avoid re-evaluating a parent node when a child is found to be unchanged from an earlier version at which the child changed but the parent did not.

Concrete scenario: Parent depends on Child. We first evaluate at version v1, Child has value A1, Parent has value B1. We then evaluate at version v2, which changes a dependency of Child. Child has value A2, and Child.getVersion() returns v2. Parent re-evaluates to B1, so is unchanged. Parent.getVersion() returns v1. Now evaluate at version v3, which also changes a dependency of Child. Child re-evaluates to A2, so Child.getVersion() returns v2. If we signal Parent with v2 and Parent only knows that it is at version v1, then Parent must unnecessarily re-evaluate. To fix this, we store an additional version in the entry -- the version at which the node was last evaluated, even if the evaluation did not result in a new value. Parent can then compare that version to its children's versions. If that version is at least as recent as their versions, it knows that the result of evaluating will be the same as it was at that last evaluated version, which is its current value.

An alternative solution might be to just signal the parent with a boolean, saying whether or not the child was changed on this evaluation. However, this would be incorrect in the scenario above, with the modification that in the second evaluation, the user just requests the value of Child -- Parent is not updated. In that case, during the third evaluation, Child would report that it was not changed during this evaluation, but we must still re-evaluate Parent since it has not yet picked up the value of Child from the earlier build.

--
MOS_MIGRATED_REVID=108163443

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");