Set the version of a computed node to the max of its child versions rather than the graph version when that is feasible.

  * It's not feasible when the computation accesses outside state, i.e. is non-hermetic, so see below.
  * It's also more complicated (and not worth the trouble) when the computation is taking place just for the error status.

Have SkyFunctionName declare whether the function it corresponds to is hermetic or non-hermetic. Only non-hermetically-generated SkyValues can be directly marked changed, and non-hermetic SkyFunctions have their values saved at the graph version, not the max of the child versions. All SkyFunctions are hermetic except for the ones that can be explicitly dirtied.

A marked-hermetic SkyFunction that has a transient error due to filesystem access can be re-evaluated and get the correct version: if it throws an IOException at version 1 and then, when re-evaluated at version 2 with unchanged dependencies, has a value, the version will be version 1.

All Skyframe unit tests that were doing non-hermetic things to nodes need to declare that those nodes are non-hermetic. I tried to make the minimal set of changes there, so that we had good incidental coverage of hermetic+non-hermetic nodes. Also did some drive-by clean-ups around that code.

Artifacts are a weird case, since they're doing untracked filesystem access (for source directories). Using max(child versions) for them gives rise to the following correctness bug: 1. do a build at v1 that creates a FileStateValue for dir/ at v1. Then at v2, add a file to dir/ and do a build that consumes dir/ as a source artifact. Now the artifact for dir/ will (incorrectly) have v1. Then at v1, do that build again. We'll consume the "artifact from the future". However, this can only have an effect when using the local action cache, since the incorrect value of the artifact (the mtime) is only consumed by the action cache. Bazel is already broken in this way (incremental builds don't invalidate directories), so this change doesn't make things worse.

PiperOrigin-RevId: 204210719

14 files changed, 217 insertions, 52 deletions

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 a82d1158df..af658f32d5 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
@@ -114,7 +114,8 @@ public abstract class AbstractExceptionalParallelEvaluator<E extends Exception>
       DirtyTrackingProgressReceiver progressReceiver,
       GraphInconsistencyReceiver graphInconsistencyReceiver,
       ForkJoinPool forkJoinPool,
-      CycleDetector cycleDetector) {
+      CycleDetector cycleDetector,
+      EvaluationVersionBehavior evaluationVersionBehavior) {
     super(
         graph,
         graphVersion,
@@ -127,7 +128,8 @@ public abstract class AbstractExceptionalParallelEvaluator<E extends Exception>
         progressReceiver,
         graphInconsistencyReceiver,
         forkJoinPool,
-        cycleDetector);
+        cycleDetector,
+        evaluationVersionBehavior);
   }
 
   private void informProgressReceiverThatValueIsDone(SkyKey key, NodeEntry entry)
@@ -469,6 +471,7 @@ public abstract class AbstractExceptionalParallelEvaluator<E extends Exception>
             maybeMarkRebuilding(parentEntry);
             // Fall through to REBUILDING.
           case REBUILDING:
+          case FORCED_REBUILDING:
             break;
           default:
             throw new AssertionError(parent + " not in valid dirty state: " + parentEntry);
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 c2f8561c32..04fcdeae91 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -104,7 +104,8 @@ public abstract class AbstractParallelEvaluator {
       DirtyTrackingProgressReceiver progressReceiver,
       GraphInconsistencyReceiver graphInconsistencyReceiver,
       ForkJoinPool forkJoinPool,
-      CycleDetector cycleDetector) {
+      CycleDetector cycleDetector,
+      EvaluationVersionBehavior evaluationVersionBehavior) {
     this.graph = graph;
     this.cycleDetector = cycleDetector;
     evaluatorContext =
@@ -120,14 +121,17 @@ public abstract class AbstractParallelEvaluator {
             errorInfoManager,
             Evaluate::new,
             graphInconsistencyReceiver,
-            Preconditions.checkNotNull(forkJoinPool));
+            Preconditions.checkNotNull(forkJoinPool),
+            evaluationVersionBehavior);
   }
 
   /**
    * If the entry is dirty and not already rebuilding, puts it in a state so that it can rebuild.
    */
   static void maybeMarkRebuilding(NodeEntry entry) {
-    if (entry.isDirty() && entry.getDirtyState() != DirtyState.REBUILDING) {
+    if (entry.isDirty()
+        && entry.getDirtyState() != DirtyState.REBUILDING
+        && entry.getDirtyState() != DirtyState.FORCED_REBUILDING) {
       entry.markRebuilding();
     }
   }
@@ -310,6 +314,7 @@ public abstract class AbstractParallelEvaluator {
           maybeMarkRebuilding(state);
           // Fall through to REBUILDING case.
         case REBUILDING:
+        case FORCED_REBUILDING:
           return DirtyOutcome.NEEDS_EVALUATION;
         default:
           throw new IllegalStateException("key: " + skyKey + ", entry: " + state);
diff --git a/src/main/java/com/google/devtools/build/skyframe/BUILD b/src/main/java/com/google/devtools/build/skyframe/BUILD
index 8a57fd0d35..c75206db4d 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BUILD
+++ b/src/main/java/com/google/devtools/build/skyframe/BUILD
@@ -6,6 +6,7 @@ package(
 
 SKYFRAME_OBJECT_SRCS = [
     "AbstractSkyKey.java",
+    "FunctionHermeticity.java",
     "ShareabilityOfValue.java",
     "SkyFunctionName.java",
     "SkyKey.java",
@@ -38,7 +39,6 @@ java_library(
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/profiler",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
-        "//src/main/java/com/google/devtools/build/lib/vfs",
         "//src/main/java/com/google/devtools/common/options",
         "//third_party:error_prone",
         "//third_party:guava",
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 59a2e13db3..2732fc4fe5 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -93,16 +93,20 @@ public abstract class DirtyBuildingState {
   final void forceChanged() {
     Preconditions.checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this);
     Preconditions.checkState(getNumOfGroupsInLastBuildDirectDeps() == dirtyDirectDepIndex, this);
-    dirtyState = DirtyState.REBUILDING;
+    dirtyState = DirtyState.FORCED_REBUILDING;
   }
 
   final boolean isChanged() {
-    return dirtyState == DirtyState.NEEDS_REBUILDING || dirtyState == DirtyState.REBUILDING;
+    return dirtyState == DirtyState.NEEDS_REBUILDING
+        || dirtyState == DirtyState.REBUILDING
+        || dirtyState == DirtyState.FORCED_REBUILDING;
   }
 
   private void checkFinishedBuildingWhenAboutToSetValue() {
     Preconditions.checkState(
-        dirtyState == DirtyState.VERIFIED_CLEAN || dirtyState == DirtyState.REBUILDING,
+        dirtyState == DirtyState.VERIFIED_CLEAN
+            || dirtyState == DirtyState.REBUILDING
+            || dirtyState == DirtyState.FORCED_REBUILDING,
         "not done building %s",
         this);
   }
@@ -194,7 +198,8 @@ public abstract class DirtyBuildingState {
   }
 
   final void resetForRestartFromScratch() {
-    Preconditions.checkState(dirtyState == DirtyState.REBUILDING, this);
+    Preconditions.checkState(
+        dirtyState == DirtyState.REBUILDING || dirtyState == DirtyState.FORCED_REBUILDING, this);
     dirtyDirectDepIndex = 0;
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java b/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java
index babf90208c..bd9ce9c746 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java
@@ -22,7 +22,8 @@ import java.io.ObjectOutputStream;
  * failure. Is not equal to anything, including itself, in order to force re-evaluation.
  */
 public final class ErrorTransienceValue implements SkyValue {
-  public static final SkyFunctionName FUNCTION_NAME = SkyFunctionName.create("ERROR_TRANSIENCE");
+  public static final SkyFunctionName FUNCTION_NAME =
+      SkyFunctionName.createNonHermetic("ERROR_TRANSIENCE");
   @AutoCodec public static final SkyKey KEY = () -> FUNCTION_NAME;
   @AutoCodec public static final ErrorTransienceValue INSTANCE = new ErrorTransienceValue();
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/EvaluationVersionBehavior.java b/src/main/java/com/google/devtools/build/skyframe/EvaluationVersionBehavior.java
new file mode 100644
index 0000000000..a4cc37165e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/EvaluationVersionBehavior.java
@@ -0,0 +1,29 @@
+// 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;
+
+/**
+ * What version to give an evaluated node: the max of its child versions or the graph version. Even
+ * for {@link #MAX_CHILD_VERSIONS} the version may still be the graph version depending on
+ * properties of the {@link SkyFunction} (if it is {@link FunctionHermeticity#NONHERMETIC}) or the
+ * error state of the node.
+ *
+ * <p>Should be set to {@link #MAX_CHILD_VERSIONS} unless the evaluation framework is being very
+ * sneaky.
+ */
+public enum EvaluationVersionBehavior {
+  MAX_CHILD_VERSIONS,
+  GRAPH_VERSION
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/FunctionHermeticity.java b/src/main/java/com/google/devtools/build/skyframe/FunctionHermeticity.java
new file mode 100644
index 0000000000..fd19b757b7
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/FunctionHermeticity.java
@@ -0,0 +1,31 @@
+// 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;
+
+/**
+ * Hermeticity of a {@link SkyFunction}, meaning whether it accesses external state untracked by
+ * Skyframe during its evaluation. A classic example is a {@link SkyFunction} that consumes a file
+ * on a filesystem: that state is untracked by Skyframe. Skyframe must be more conservative when
+ * using values generated by a non-hermetic function: for instance, a non-hermetic function may need
+ * to be re-run even if all its Skyframe dependencies are unchanged: such a node may be explicitly
+ * dirtied due to outside changes.
+ *
+ * <p>Note that Skyframe does <i>not</i> explicitly re-evaluate non-hermetic functions on every
+ * build: it just relaxes some of its graph-pruning logic to be more conservative with such nodes.
+ */
+public enum FunctionHermeticity {
+  HERMETIC,
+  NONHERMETIC
+}
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 859f531666..12e3a2357f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -307,8 +307,16 @@ public class InMemoryNodeEntry implements NodeEntry {
       // value, because preserving == equality is even better than .equals() equality.
       this.value = getDirtyBuildingState().getLastBuildValue();
     } else {
+      boolean forcedRebuild =
+          isDirty() && getDirtyBuildingState().getDirtyState() == DirtyState.FORCED_REBUILDING;
       // If this is a new value, or it has changed since the last build, set the version to the
       // current graph version.
+      Preconditions.checkState(
+          forcedRebuild || !this.lastChangedVersion.equals(version),
+          "Changed value but with the same version? %s %s %s",
+          this.lastChangedVersion,
+          version,
+          this);
       this.lastChangedVersion = version;
       this.value = value;
     }
@@ -550,8 +558,9 @@ public class InMemoryNodeEntry implements NodeEntry {
   public synchronized Set<SkyKey> getAllRemainingDirtyDirectDeps() throws InterruptedException {
     Preconditions.checkState(isEvaluating(), "Not evaluating for remaining dirty? %s", this);
     if (isDirty()) {
+      DirtyState dirtyState = getDirtyBuildingState().getDirtyState();
       Preconditions.checkState(
-          getDirtyBuildingState().getDirtyState() == DirtyState.REBUILDING, this);
+          dirtyState == DirtyState.REBUILDING || dirtyState == DirtyState.FORCED_REBUILDING, this);
       return getDirtyBuildingState().getAllRemainingDirtyDirectDeps(/*preservePosition=*/ true);
     } else {
       return ImmutableSet.of();
diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
index 9d2d811594..168ad23b95 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -425,6 +425,9 @@ public abstract class InvalidatingNodeVisitor<TGraph extends QueryableGraph> {
       ArrayList<SkyKey> keysToGet = new ArrayList<>(size);
       for (SkyKey key : keys) {
         if (setToCheck.add(key)) {
+          Preconditions.checkState(
+              !isChanged || key.functionName().getHermeticity() == FunctionHermeticity.NONHERMETIC,
+              key);
           keysToGet.add(key);
         }
       }
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 1e6169496b..e74fb1ed16 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -72,7 +72,13 @@ public interface NodeEntry extends ThinNodeEntry {
      */
     NEEDS_REBUILDING,
     /** A rebuilding is in progress. */
-    REBUILDING
+    REBUILDING,
+    /**
+     * A forced rebuilding is in progress, likely because of a transient error on the previous
+     * build. The distinction between this and {@link #REBUILDING} is only needed for internal
+     * sanity checks.
+     */
+    FORCED_REBUILDING
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
index afd0279e5f..5b847c5c5a 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -70,7 +70,8 @@ public class ParallelEvaluator extends AbstractExceptionalParallelEvaluator<Runt
       DirtyTrackingProgressReceiver progressReceiver,
       GraphInconsistencyReceiver graphInconsistencyReceiver,
       ForkJoinPool forkJoinPool,
-      CycleDetector cycleDetector) {
+      CycleDetector cycleDetector,
+      EvaluationVersionBehavior evaluationVersionBehavior) {
     super(
         graph,
         graphVersion,
@@ -83,7 +84,8 @@ public class ParallelEvaluator extends AbstractExceptionalParallelEvaluator<Runt
         progressReceiver,
         graphInconsistencyReceiver,
         forkJoinPool,
-        cycleDetector);
+        cycleDetector,
+        evaluationVersionBehavior);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
index 14306d484b..60987ac7f2 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
@@ -53,6 +53,7 @@ class ParallelEvaluatorContext {
   private final EventFilter storedEventFilter;
   private final ErrorInfoManager errorInfoManager;
   private final GraphInconsistencyReceiver graphInconsistencyReceiver;
+  private final EvaluationVersionBehavior evaluationVersionBehavior;
 
   /**
    * The visitor managing the thread pool. Used to enqueue parents when an entry is finished, and,
@@ -86,7 +87,8 @@ class ParallelEvaluatorContext {
         storedEventFilter,
         errorInfoManager,
         graphInconsistencyReceiver,
-        () -> new NodeEntryVisitor(threadCount, progressReceiver, runnableMaker));
+        () -> new NodeEntryVisitor(threadCount, progressReceiver, runnableMaker),
+        EvaluationVersionBehavior.MAX_CHILD_VERSIONS);
   }
 
   ParallelEvaluatorContext(
@@ -101,7 +103,8 @@ class ParallelEvaluatorContext {
       ErrorInfoManager errorInfoManager,
       final Function<SkyKey, Runnable> runnableMaker,
       GraphInconsistencyReceiver graphInconsistencyReceiver,
-      final ForkJoinPool forkJoinPool) {
+      final ForkJoinPool forkJoinPool,
+      EvaluationVersionBehavior evaluationVersionBehavior) {
     this(
         graph,
         graphVersion,
@@ -113,7 +116,8 @@ class ParallelEvaluatorContext {
         storedEventFilter,
         errorInfoManager,
         graphInconsistencyReceiver,
-        () -> new NodeEntryVisitor(forkJoinPool, progressReceiver, runnableMaker));
+        () -> new NodeEntryVisitor(forkJoinPool, progressReceiver, runnableMaker),
+        evaluationVersionBehavior);
   }
 
   private ParallelEvaluatorContext(
@@ -127,12 +131,14 @@ class ParallelEvaluatorContext {
       EventFilter storedEventFilter,
       ErrorInfoManager errorInfoManager,
       GraphInconsistencyReceiver graphInconsistencyReceiver,
-      Supplier<NodeEntryVisitor> visitorSupplier) {
+      Supplier<NodeEntryVisitor> visitorSupplier,
+      EvaluationVersionBehavior evaluationVersionBehavior) {
     this.graph = graph;
     this.graphVersion = graphVersion;
     this.skyFunctions = skyFunctions;
     this.reporter = reporter;
     this.graphInconsistencyReceiver = graphInconsistencyReceiver;
+    this.evaluationVersionBehavior = evaluationVersionBehavior;
     this.replayingNestedSetEventVisitor =
         new NestedSetVisitor<>(new NestedSetEventReceiver(reporter), emittedEventState.eventState);
     this.replayingNestedSetPostableVisitor =
@@ -236,6 +242,10 @@ class ParallelEvaluatorContext {
     return errorInfoManager;
   }
 
+  EvaluationVersionBehavior getEvaluationVersionBehavior() {
+    return evaluationVersionBehavior;
+  }
+
   /** Receives the events from the NestedSet and delegates to the reporter. */
   private static class NestedSetEventReceiver implements NestedSetVisitor.Receiver<TaggedEvents> {
 
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 4b2fc51cdf..fc6e3c88c8 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -71,6 +71,9 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
   private SkyValue value = null;
   private ErrorInfo errorInfo = null;
 
+  private final FunctionHermeticity hermeticity;
+  @Nullable private Version maxChildVersion = null;
+
   /**
    * This is not {@code null} only during cycle detection and error bubbling. The nullness of this
    * field is used to detect whether evaluation is in one of those special states.
@@ -156,6 +159,7 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     this.oldDeps = oldDeps;
     this.evaluatorContext = evaluatorContext;
     this.bubbleErrorInfo = null;
+    this.hermeticity = skyKey.functionName().getHermeticity();
     this.previouslyRequestedDepsValues =
         batchPrefetch(skyKey, directDeps, oldDeps, /*assertDone=*/ true, skyKey);
     Preconditions.checkState(
@@ -176,6 +180,7 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     this.oldDeps = oldDeps;
     this.evaluatorContext = evaluatorContext;
     this.bubbleErrorInfo = Preconditions.checkNotNull(bubbleErrorInfo);
+    this.hermeticity = skyKey.functionName().getHermeticity();
     try {
       this.previouslyRequestedDepsValues =
           batchPrefetch(skyKey, directDeps, oldDeps, /*assertDone=*/ false, skyKey);
@@ -227,7 +232,8 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
         ImmutableMap.builderWithExpectedSize(batchMap.size());
     for (Entry<SkyKey, ? extends NodeEntry> entry : batchMap.entrySet()) {
       SkyValue valueMaybeWithMetadata = entry.getValue().getValueMaybeWithMetadata();
-      if (assertDone && valueMaybeWithMetadata == null) {
+      boolean depDone = valueMaybeWithMetadata != null;
+      if (assertDone && !depDone) {
         // A previously requested dep may have transitioned from done to dirty between when the node
         // was read during a previous attempt to build this node and now. Notify the graph
         // inconsistency receiver so that we can crash if that's unexpected.
@@ -237,8 +243,10 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
                 skyKey, entry.getKey(), Inconsistency.CHILD_UNDONE_FOR_BUILDING_NODE);
         throw new UndonePreviouslyRequestedDep(entry.getKey());
       }
-      depValuesBuilder.put(
-          entry.getKey(), valueMaybeWithMetadata == null ? NULL_MARKER : valueMaybeWithMetadata);
+      depValuesBuilder.put(entry.getKey(), !depDone ? NULL_MARKER : valueMaybeWithMetadata);
+      if (depDone) {
+        maybeUpdateMaxChildVersion(entry.getValue());
+      }
     }
     return depValuesBuilder.build();
   }
@@ -323,6 +331,7 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
           triState == DependencyState.DONE, "%s %s %s", skyKey, triState, errorInfo);
       state.addTemporaryDirectDeps(GroupedListHelper.create(ErrorTransienceValue.KEY));
       state.signalDep();
+      maxChildVersion = evaluatorContext.getGraphVersion();
     }
 
     this.errorInfo = Preconditions.checkNotNull(errorInfo, skyKey);
@@ -367,9 +376,13 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     Map<SkyKey, ? extends NodeEntry> missingEntries =
         evaluatorContext.getBatchValues(skyKey, Reason.DEP_REQUESTED, missingKeys);
     for (SkyKey key : missingKeys) {
-      SkyValue valueOrNullMarker = getValueOrNullMarker(missingEntries.get(key));
+      NodeEntry depEntry = missingEntries.get(key);
+      SkyValue valueOrNullMarker = getValueOrNullMarker(depEntry);
       result.put(key, valueOrNullMarker);
       newlyRequestedDepsValues.put(key, valueOrNullMarker);
+      if (valueOrNullMarker != NULL_MARKER) {
+        maybeUpdateMaxChildVersion(depEntry);
+      }
     }
     return result;
   }
@@ -425,7 +438,8 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     Map<SkyKey, ? extends NodeEntry> missingEntries =
         evaluatorContext.getBatchValues(skyKey, Reason.DEP_REQUESTED, missingKeys);
     for (SkyKey key : missingKeys) {
-      SkyValue valueOrNullMarker = getValueOrNullMarker(missingEntries.get(key));
+      NodeEntry depEntry = missingEntries.get(key);
+      SkyValue valueOrNullMarker = getValueOrNullMarker(depEntry);
       newlyRequestedDepsValues.put(key, valueOrNullMarker);
       if (valueOrNullMarker == NULL_MARKER) {
         // TODO(mschaller): handle registered deps that transitioned from done to dirty during eval
@@ -435,6 +449,7 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
         Preconditions.checkState(!assertDone, "%s had not done: %s", skyKey, key);
         continue;
       }
+      maybeUpdateMaxChildVersion(depEntry);
       result.add(valueOrNullMarker);
     }
     return result;
@@ -686,7 +701,6 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     NestedSet<Postable> posts = buildPosts(primaryEntry, /*expectDoneDeps=*/ true);
     NestedSet<TaggedEvents> events = buildEvents(primaryEntry, /*expectDoneDeps=*/ true);
 
-    Version valueVersion;
     SkyValue valueWithMetadata;
     if (value == null) {
       Preconditions.checkNotNull(errorInfo, "%s %s", skyKey, primaryEntry);
@@ -697,42 +711,54 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
           enqueueParents == EnqueueParentBehavior.ENQUEUE, "%s %s", skyKey, primaryEntry);
       valueWithMetadata = ValueWithMetadata.normal(value, errorInfo, events, posts);
     }
+    GroupedList<SkyKey> temporaryDirectDeps = primaryEntry.getTemporaryDirectDeps();
     if (!oldDeps.isEmpty()) {
       // Remove the rdep on this entry for each of its old deps that is no longer a direct dep.
-      Set<SkyKey> depsToRemove =
-          Sets.difference(oldDeps, primaryEntry.getTemporaryDirectDeps().toSet());
+      Set<SkyKey> depsToRemove = Sets.difference(oldDeps, temporaryDirectDeps.toSet());
       Collection<? extends NodeEntry> oldDepEntries =
           evaluatorContext.getGraph().getBatch(skyKey, Reason.RDEP_REMOVAL, depsToRemove).values();
       for (NodeEntry oldDepEntry : oldDepEntries) {
         oldDepEntry.removeReverseDep(skyKey);
       }
     }
+    Version evaluationVersion = maxChildVersion;
+    if (evaluatorContext.getEvaluationVersionBehavior() == EvaluationVersionBehavior.GRAPH_VERSION
+        || hermeticity == FunctionHermeticity.NONHERMETIC) {
+      evaluationVersion = evaluatorContext.getGraphVersion();
+    } else if (bubbleErrorInfo != null) {
+      // Cycles can lead to a state where the versions of done children don't accurately reflect the
+      // state that led to this node's value. Be conservative then.
+      evaluationVersion = evaluatorContext.getGraphVersion();
+    } else if (evaluationVersion == null) {
+      Preconditions.checkState(
+          temporaryDirectDeps.isEmpty(),
+          "No max child version found, but have direct deps: %s %s",
+          skyKey,
+          primaryEntry);
+      evaluationVersion = evaluatorContext.getGraphVersion();
+    }
+    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.
-    // We could consider using max(childVersions) here instead of graphVersion. When full
-    // versioning is implemented, this would allow evaluation at a version between
-    // max(childVersions) and graphVersion to re-use this result.
-    Set<SkyKey> reverseDeps =
-        primaryEntry.setValue(valueWithMetadata, evaluatorContext.getGraphVersion());
-    // Note that if this update didn't actually change the value entry, this version may not
-    // be the graph version.
-    valueVersion = primaryEntry.getVersion();
+    Set<SkyKey> reverseDeps = primaryEntry.setValue(valueWithMetadata, evaluationVersion);
+    // Note that if this update didn't actually change the entry, this version may not be
+    // evaluationVersion.
+    Version currentVersion = primaryEntry.getVersion();
     Preconditions.checkState(
-        valueVersion.atMost(evaluatorContext.getGraphVersion()),
-        "%s should be at most %s in the version partial ordering",
-        valueVersion,
+        currentVersion.atMost(evaluationVersion),
+        "%s should be at most %s in the version partial ordering (graph version %s)",
+        currentVersion,
+        evaluationVersion,
         evaluatorContext.getGraphVersion());
 
-    // Tell the receiver that this value was built. If valueVersion.equals(graphVersion), it was
-    // evaluated this run, and so was changed. Otherwise, it is less than graphVersion, by the
-    // Preconditions check above, and was not actually changed this run -- when it was written
+    // Tell the receiver that this value was built. If currentVersion.equals(evaluationVersion), it
+    // was evaluated this run, and so was changed. Otherwise, it is less than evaluationVersion, by
+    // the Preconditions check above, and was not actually changed this run -- when it was written
     // above, its version stayed below this update's version, so its value remains the same.
     // We use a SkyValueSupplier here because it keeps a reference to the entry, allowing for
     // the receiver to be confident that the entry is readily accessible in memory.
     EvaluationState evaluationState =
-        valueVersion.equals(evaluatorContext.getGraphVersion())
-            ? EvaluationState.BUILT
-            : EvaluationState.CLEAN;
+        currentVersion.equals(previousVersion) ? EvaluationState.CLEAN : EvaluationState.BUILT;
     evaluatorContext
         .getProgressReceiver()
         .evaluated(
@@ -742,7 +768,7 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
             evaluationState);
 
     evaluatorContext.signalValuesAndEnqueueIfReady(
-        skyKey, reverseDeps, valueVersion, enqueueParents);
+        skyKey, reverseDeps, currentVersion, enqueueParents);
 
     evaluatorContext.getReplayingNestedSetPostableVisitor().visit(posts);
     evaluatorContext.getReplayingNestedSetEventVisitor().visit(events);
@@ -777,11 +803,25 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
       if (!previouslyRequestedDepsValues.containsKey(key)) {
         newlyRequestedDeps.add(key);
         newlyRegisteredDeps.add(key);
+        // Be conservative with these value-not-retrieved deps: assume they have the highest
+        // possible version.
+        maxChildVersion = evaluatorContext.getGraphVersion();
       }
     }
     newlyRequestedDeps.endGroup();
   }
 
+  private void maybeUpdateMaxChildVersion(NodeEntry depEntry) {
+    if (hermeticity == FunctionHermeticity.HERMETIC
+        && evaluatorContext.getEvaluationVersionBehavior()
+            == EvaluationVersionBehavior.MAX_CHILD_VERSIONS) {
+      Version depVersion = depEntry.getVersion();
+      if (maxChildVersion == null || maxChildVersion.atMost(depVersion)) {
+        maxChildVersion = depVersion;
+      }
+    }
+  }
+
   /** Thrown during environment construction if a previously requested dep is no longer done. */
   static class UndonePreviouslyRequestedDep extends Exception {
     private final SkyKey depKey;
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionName.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionName.java
index 3d6ece1975..107181ed1d 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionName.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionName.java
@@ -31,15 +31,29 @@ public final class SkyFunctionName implements Serializable {
    * argument.
    */
   // Needs to be after the cache is initialized.
-  public static final SkyFunctionName FOR_TESTING = SkyFunctionName.create("FOR_TESTING");
+  public static final SkyFunctionName FOR_TESTING = SkyFunctionName.createHermetic("FOR_TESTING");
 
-  /** Create a SkyFunctionName identified by {@code name}. */
-  public static SkyFunctionName create(String name) {
-    return create(name, ShareabilityOfValue.ALWAYS);
+  /**
+   * Create a SkyFunctionName identified by {@code name} whose evaluation is non-hermetic (its value
+   * may not be a pure function of its dependencies. Only use this if the evaluation explicitly
+   * consumes data outside of Skyframe, or if the node can be directly invalidated (as opposed to
+   * transitively invalidated).
+   */
+  public static SkyFunctionName createNonHermetic(String name) {
+    return create(name, ShareabilityOfValue.ALWAYS, FunctionHermeticity.NONHERMETIC);
+  }
+
+  /**
+   * Creates a SkyFunctionName identified by {@code name} whose evaluation is hermetic (guaranteed
+   * to be a deterministic function of its dependencies, not doing any external operations).
+   */
+  public static SkyFunctionName createHermetic(String name) {
+    return create(name, ShareabilityOfValue.ALWAYS, FunctionHermeticity.HERMETIC);
   }
 
-  public static SkyFunctionName create(String name, ShareabilityOfValue shareabilityOfValue) {
-    SkyFunctionName result = new SkyFunctionName(name, shareabilityOfValue);
+  public static SkyFunctionName create(
+      String name, ShareabilityOfValue shareabilityOfValue, FunctionHermeticity hermeticity) {
+    SkyFunctionName result = new SkyFunctionName(name, shareabilityOfValue, hermeticity);
     SkyFunctionName cached;
     try {
       cached = interner.get(new NameOnlyWrapper(result), () -> result);
@@ -56,10 +70,13 @@ public final class SkyFunctionName implements Serializable {
 
   private final String name;
   private final ShareabilityOfValue shareabilityOfValue;
+  private final FunctionHermeticity hermeticity;
 
-  private SkyFunctionName(String name, ShareabilityOfValue shareabilityOfValue) {
+  private SkyFunctionName(
+      String name, ShareabilityOfValue shareabilityOfValue, FunctionHermeticity hermeticity) {
     this.name = name;
     this.shareabilityOfValue = shareabilityOfValue;
+    this.hermeticity = hermeticity;
   }
 
   public String getName() {
@@ -70,6 +87,10 @@ public final class SkyFunctionName implements Serializable {
     return shareabilityOfValue;
   }
 
+  public FunctionHermeticity getHermeticity() {
+    return hermeticity;
+  }
+
   @Override
   public String toString() {
     return name