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
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 326635d..8c1fa7f 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 @@
    * 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 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 @@
     } 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 @@
   @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 @@
 
   @Override
   public synchronized Version getVersion() {
-    return version;
+    return lastChangedVersion;
   }
 
   /**  @see BuildingState#getDirtyState() */
@@ -436,7 +449,8 @@
     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 @@
     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;