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

1 files changed, 111 insertions, 0 deletions

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