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

24 files changed, 338 insertions, 130 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java
index b456de9be5..d287d77a55 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java
@@ -19,6 +19,7 @@ import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.skyframe.FunctionHermeticity;
 import com.google.devtools.build.skyframe.ShareabilityOfValue;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -28,8 +29,10 @@ import com.google.devtools.build.skyframe.SkyKey;
 public class ActionLookupData implements SkyKey {
   private static final Interner<ActionLookupData> INTERNER = BlazeInterners.newWeakInterner();
   // Test actions are not shareable.
+  // Action execution writes to disk and can be invalidated by disk state, so is non-hermetic.
   public static final SkyFunctionName NAME =
-      SkyFunctionName.create("ACTION_EXECUTION", ShareabilityOfValue.SOMETIMES);
+      SkyFunctionName.create(
+          "ACTION_EXECUTION", ShareabilityOfValue.SOMETIMES, FunctionHermeticity.NONHERMETIC);
 
   private final ActionLookupKey actionLookupKey;
   private final int actionIndex;
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
index a27756e259..f21d579aed 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
@@ -127,7 +127,19 @@ public class Artifact
         }
       };
 
-  public static final SkyFunctionName ARTIFACT = SkyFunctionName.create("ARTIFACT");
+  /**
+   * {@link com.google.devtools.build.lib.skyframe.ArtifactFunction} does direct filesystem access
+   * without declaring Skyframe dependencies if the artifact is a source directory. However, that
+   * filesystem access is not invalidated on incremental builds, and we have no plans to fix it,
+   * since general consumption of source directories in this way is unsound. Therefore no new bugs
+   * are created by declaring {@link com.google.devtools.build.lib.skyframe.ArtifactFunction} to be
+   * hermetic.
+   *
+   * <p>TODO(janakr): Avoid this issue entirely by giving {@link SourceArtifact} its own {@code
+   * SkyFunction}. Then we can just declare that function to be non-hermetic. That will also save
+   * memory since we can make mandatory source artifacts their own SkyKeys!
+   */
+  public static final SkyFunctionName ARTIFACT = SkyFunctionName.createHermetic("ARTIFACT");
 
   @Override
   public int compareTo(Object o) {
diff --git a/src/main/java/com/google/devtools/build/lib/actions/FileStateValue.java b/src/main/java/com/google/devtools/build/lib/actions/FileStateValue.java
index bc4b51ad71..1a5cceb1d0 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FileStateValue.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FileStateValue.java
@@ -56,7 +56,7 @@ import javax.annotation.Nullable;
  */
 @VisibleForTesting
 public abstract class FileStateValue implements SkyValue {
-  public static final SkyFunctionName FILE_STATE = SkyFunctionName.create("FILE_STATE");
+  public static final SkyFunctionName FILE_STATE = SkyFunctionName.createNonHermetic("FILE_STATE");
 
   @AutoCodec
   public static final DirectoryFileStateValue DIRECTORY_FILE_STATE_NODE =
diff --git a/src/main/java/com/google/devtools/build/lib/actions/FileValue.java b/src/main/java/com/google/devtools/build/lib/actions/FileValue.java
index d862881b2c..89450d2f62 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FileValue.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FileValue.java
@@ -49,7 +49,8 @@ import javax.annotation.Nullable;
 @Immutable
 @ThreadSafe
 public abstract class FileValue implements SkyValue {
-  public static final SkyFunctionName FILE = SkyFunctionName.create("FILE");
+  // Depends non-hermetically on package path.
+  public static final SkyFunctionName FILE = SkyFunctionName.createNonHermetic("FILE");
 
   /**
    * Exists to accommodate the control flow of {@link ActionMetadataHandler#getMetadata}.
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerFunction.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerFunction.java
index 6e0a8b0fd8..24c24ba356 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerFunction.java
@@ -53,7 +53,8 @@ import org.apache.maven.settings.building.SettingsBuildingResult;
  * Implementation of maven_repository.
  */
 public class MavenServerFunction implements SkyFunction {
-  public static final SkyFunctionName NAME = SkyFunctionName.create("MAVEN_SERVER_FUNCTION");
+  public static final SkyFunctionName NAME =
+      SkyFunctionName.createHermetic("MAVEN_SERVER_FUNCTION");
 
   private static final String USER_KEY = "user";
   private static final String SYSTEM_KEY = "system";
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/Label.java b/src/main/java/com/google/devtools/build/lib/cmdline/Label.java
index 831c408e2d..43d984628b 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/Label.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/Label.java
@@ -82,7 +82,7 @@ public final class Label
 
   public static final PathFragment EXTERNAL_PATH_PREFIX = PathFragment.create("external");
   public static final SkyFunctionName TRANSITIVE_TRAVERSAL =
-      SkyFunctionName.create("TRANSITIVE_TRAVERSAL");
+      SkyFunctionName.createHermetic("TRANSITIVE_TRAVERSAL");
 
   private static final Interner<Label> LABEL_INTERNER = BlazeInterners.newWeakInterner();
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoSupportValue.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoSupportValue.java
index 5d2192b889..b6d0d9e576 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoSupportValue.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoSupportValue.java
@@ -36,7 +36,7 @@ import java.util.Objects;
 @AutoCodec
 @Immutable
 public class FdoSupportValue implements SkyValue {
-  public static final SkyFunctionName SKYFUNCTION = SkyFunctionName.create("FDO_SUPPORT");
+  public static final SkyFunctionName SKYFUNCTION = SkyFunctionName.createHermetic("FDO_SUPPORT");
 
   /** {@link SkyKey} for {@link FdoSupportValue}. */
   @Immutable
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java b/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
index c99898028a..b501f3abce 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
@@ -43,6 +43,7 @@ import com.google.devtools.build.lib.vfs.ModifiedFileSet;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.Differencer;
+import com.google.devtools.build.skyframe.FunctionHermeticity;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
@@ -506,6 +507,10 @@ public class FilesystemValueChecker {
         if (!checker.applies(key)) {
           continue;
         }
+        Preconditions.checkState(
+            key.functionName().getHermeticity() == FunctionHermeticity.NONHERMETIC,
+            "Only non-hermetic keys can be dirty roots: %s",
+            key);
         executor.execute(
             wrapper.wrap(
                 () -> {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
index aed4d5dbc1..be40e0619f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
@@ -15,6 +15,7 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Predicate;
 import com.google.devtools.build.lib.actions.ActionLookupData;
+import com.google.devtools.build.skyframe.FunctionHermeticity;
 import com.google.devtools.build.skyframe.ShareabilityOfValue;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -23,98 +24,116 @@ import com.google.devtools.build.skyframe.SkyKey;
  * Value types in Skyframe.
  */
 public final class SkyFunctions {
-  public static final SkyFunctionName PRECOMPUTED = SkyFunctionName.create("PRECOMPUTED");
+  public static final SkyFunctionName PRECOMPUTED =
+      SkyFunctionName.createNonHermetic("PRECOMPUTED");
   public static final SkyFunctionName CLIENT_ENVIRONMENT_VARIABLE =
-      SkyFunctionName.create("CLIENT_ENVIRONMENT_VARIABLE");
+      SkyFunctionName.createNonHermetic("CLIENT_ENVIRONMENT_VARIABLE");
   public static final SkyFunctionName ACTION_ENVIRONMENT_VARIABLE =
-      SkyFunctionName.create("ACTION_ENVIRONMENT_VARIABLE");
+      SkyFunctionName.createHermetic("ACTION_ENVIRONMENT_VARIABLE");
   public static final SkyFunctionName DIRECTORY_LISTING_STATE =
-      SkyFunctionName.create("DIRECTORY_LISTING_STATE");
+      SkyFunctionName.createNonHermetic("DIRECTORY_LISTING_STATE");
   public static final SkyFunctionName FILE_SYMLINK_CYCLE_UNIQUENESS =
-      SkyFunctionName.create("FILE_SYMLINK_CYCLE_UNIQUENESS");
+      SkyFunctionName.createHermetic("FILE_SYMLINK_CYCLE_UNIQUENESS");
   public static final SkyFunctionName FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS =
-      SkyFunctionName.create("FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS");
+      SkyFunctionName.createHermetic("FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS");
   public static final SkyFunctionName DIRECTORY_LISTING =
-      SkyFunctionName.create("DIRECTORY_LISTING");
-  public static final SkyFunctionName PACKAGE_LOOKUP = SkyFunctionName.create("PACKAGE_LOOKUP");
+      SkyFunctionName.createHermetic("DIRECTORY_LISTING");
+  // Non-hermetic because unfortunately package lookups secretly access the set of deleted packages.
+  public static final SkyFunctionName PACKAGE_LOOKUP =
+      SkyFunctionName.createNonHermetic("PACKAGE_LOOKUP");
   public static final SkyFunctionName CONTAINING_PACKAGE_LOOKUP =
-      SkyFunctionName.create("CONTAINING_PACKAGE_LOOKUP");
-  public static final SkyFunctionName AST_FILE_LOOKUP = SkyFunctionName.create("AST_FILE_LOOKUP");
+      SkyFunctionName.createHermetic("CONTAINING_PACKAGE_LOOKUP");
+  // Non-hermetic because accesses the package locator. Also does disk access.
+  public static final SkyFunctionName AST_FILE_LOOKUP =
+      SkyFunctionName.createNonHermetic("AST_FILE_LOOKUP");
   public static final SkyFunctionName SKYLARK_IMPORTS_LOOKUP =
-      SkyFunctionName.create("SKYLARK_IMPORTS_LOOKUP");
-  public static final SkyFunctionName GLOB = SkyFunctionName.create("GLOB");
-  public static final SkyFunctionName PACKAGE = SkyFunctionName.create("PACKAGE");
-  public static final SkyFunctionName PACKAGE_ERROR = SkyFunctionName.create("PACKAGE_ERROR");
-  public static final SkyFunctionName PACKAGE_ERROR_MESSAGE =
-      SkyFunctionName.create("PACKAGE_ERROR_MESSAGE");
-  public static final SkyFunctionName TARGET_MARKER = SkyFunctionName.create("TARGET_MARKER");
-  public static final SkyFunctionName TARGET_PATTERN = SkyFunctionName.create("TARGET_PATTERN");
-  public static final SkyFunctionName TARGET_PATTERN_ERROR =
-      SkyFunctionName.create("TARGET_PATTERN_ERROR");
+      SkyFunctionName.createHermetic("SKYLARK_IMPORTS_LOOKUP");
+  public static final SkyFunctionName GLOB = SkyFunctionName.createHermetic("GLOB");
+  public static final SkyFunctionName PACKAGE = SkyFunctionName.createHermetic("PACKAGE");
+  static final SkyFunctionName PACKAGE_ERROR = SkyFunctionName.createHermetic("PACKAGE_ERROR");
+  static final SkyFunctionName PACKAGE_ERROR_MESSAGE =
+      SkyFunctionName.createHermetic("PACKAGE_ERROR_MESSAGE");
+  public static final SkyFunctionName TARGET_MARKER =
+      SkyFunctionName.createHermetic("TARGET_MARKER");
+  // Non-hermetic because accesses package locator
+  public static final SkyFunctionName TARGET_PATTERN =
+      SkyFunctionName.createNonHermetic("TARGET_PATTERN");
+  static final SkyFunctionName TARGET_PATTERN_ERROR =
+      SkyFunctionName.createHermetic("TARGET_PATTERN_ERROR");
   public static final SkyFunctionName PREPARE_DEPS_OF_PATTERNS =
-      SkyFunctionName.create("PREPARE_DEPS_OF_PATTERNS");
+      SkyFunctionName.createHermetic("PREPARE_DEPS_OF_PATTERNS");
+  // Non-hermetic because accesses package locator
   public static final SkyFunctionName PREPARE_DEPS_OF_PATTERN =
-      SkyFunctionName.create("PREPARE_DEPS_OF_PATTERN");
+      SkyFunctionName.createNonHermetic("PREPARE_DEPS_OF_PATTERN");
   public static final SkyFunctionName PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY =
-      SkyFunctionName.create("PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY");
+      SkyFunctionName.createHermetic("PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY");
   public static final SkyFunctionName COLLECT_TARGETS_IN_PACKAGE =
-      SkyFunctionName.create("COLLECT_TARGETS_IN_PACKAGE");
+      SkyFunctionName.createHermetic("COLLECT_TARGETS_IN_PACKAGE");
   public static final SkyFunctionName COLLECT_PACKAGES_UNDER_DIRECTORY =
-      SkyFunctionName.create("COLLECT_PACKAGES_UNDER_DIRECTORY");
+      SkyFunctionName.createHermetic("COLLECT_PACKAGES_UNDER_DIRECTORY");
   public static final SkyFunctionName BLACKLISTED_PACKAGE_PREFIXES =
-      SkyFunctionName.create("BLACKLISTED_PACKAGE_PREFIXES");
-  public static final SkyFunctionName TEST_SUITE_EXPANSION =
-      SkyFunctionName.create("TEST_SUITE_EXPANSION");
-  public static final SkyFunctionName TESTS_IN_SUITE = SkyFunctionName.create("TESTS_IN_SUITE");
-  public static final SkyFunctionName TARGET_PATTERN_PHASE =
-      SkyFunctionName.create("TARGET_PATTERN_PHASE");
-  public static final SkyFunctionName RECURSIVE_PKG = SkyFunctionName.create("RECURSIVE_PKG");
-  public static final SkyFunctionName TRANSITIVE_TARGET =
-      SkyFunctionName.create("TRANSITIVE_TARGET");
+      SkyFunctionName.createHermetic("BLACKLISTED_PACKAGE_PREFIXES");
+  static final SkyFunctionName TEST_SUITE_EXPANSION =
+      SkyFunctionName.createHermetic("TEST_SUITE_EXPANSION");
+  static final SkyFunctionName TESTS_IN_SUITE = SkyFunctionName.createHermetic("TESTS_IN_SUITE");
+  // Non-hermetic because accesses package locator
+  static final SkyFunctionName TARGET_PATTERN_PHASE =
+      SkyFunctionName.createNonHermetic("TARGET_PATTERN_PHASE");
+  static final SkyFunctionName RECURSIVE_PKG = SkyFunctionName.createHermetic("RECURSIVE_PKG");
+  static final SkyFunctionName TRANSITIVE_TARGET =
+      SkyFunctionName.createHermetic("TRANSITIVE_TARGET");
   public static final SkyFunctionName CONFIGURED_TARGET =
-      SkyFunctionName.create("CONFIGURED_TARGET");
+      SkyFunctionName.createHermetic("CONFIGURED_TARGET");
   public static final SkyFunctionName POST_CONFIGURED_TARGET =
-      SkyFunctionName.create("POST_CONFIGURED_TARGET");
-  public static final SkyFunctionName ASPECT = SkyFunctionName.create("ASPECT");
-  public static final SkyFunctionName LOAD_SKYLARK_ASPECT =
-      SkyFunctionName.create("LOAD_SKYLARK_ASPECT");
+      SkyFunctionName.createHermetic("POST_CONFIGURED_TARGET");
+  public static final SkyFunctionName ASPECT = SkyFunctionName.createHermetic("ASPECT");
+  static final SkyFunctionName LOAD_SKYLARK_ASPECT =
+      SkyFunctionName.createHermetic("LOAD_SKYLARK_ASPECT");
   public static final SkyFunctionName TARGET_COMPLETION =
-      SkyFunctionName.create("TARGET_COMPLETION");
+      SkyFunctionName.createHermetic("TARGET_COMPLETION");
   public static final SkyFunctionName ASPECT_COMPLETION =
-      SkyFunctionName.create("ASPECT_COMPLETION");
-  public static final SkyFunctionName TEST_COMPLETION =
-      SkyFunctionName.create("TEST_COMPLETION", ShareabilityOfValue.NEVER);
-  public static final SkyFunctionName BUILD_CONFIGURATION =
-      SkyFunctionName.create("BUILD_CONFIGURATION");
+      SkyFunctionName.createHermetic("ASPECT_COMPLETION");
+  static final SkyFunctionName TEST_COMPLETION =
+      SkyFunctionName.create(
+          "TEST_COMPLETION", ShareabilityOfValue.NEVER, FunctionHermeticity.HERMETIC);
+  static final SkyFunctionName BUILD_CONFIGURATION =
+      SkyFunctionName.createHermetic("BUILD_CONFIGURATION");
   public static final SkyFunctionName CONFIGURATION_FRAGMENT =
-      SkyFunctionName.create("CONFIGURATION_FRAGMENT");
+      SkyFunctionName.createHermetic("CONFIGURATION_FRAGMENT");
   public static final SkyFunctionName ACTION_EXECUTION = ActionLookupData.NAME;
-  public static final SkyFunctionName RECURSIVE_FILESYSTEM_TRAVERSAL =
-      SkyFunctionName.create("RECURSIVE_DIRECTORY_TRAVERSAL");
-  public static final SkyFunctionName FILESET_ENTRY = SkyFunctionName.create("FILESET_ENTRY");
-  public static final SkyFunctionName BUILD_INFO_COLLECTION =
-      SkyFunctionName.create("BUILD_INFO_COLLECTION");
-  public static final SkyFunctionName BUILD_INFO = SkyFunctionName.create("BUILD_INFO");
-  public static final SkyFunctionName WORKSPACE_NAME = SkyFunctionName.create("WORKSPACE_NAME");
-  public static final SkyFunctionName WORKSPACE_FILE = SkyFunctionName.create("WORKSPACE_FILE");
-  public static final SkyFunctionName COVERAGE_REPORT = SkyFunctionName.create("COVERAGE_REPORT");
-  public static final SkyFunctionName REPOSITORY = SkyFunctionName.create("REPOSITORY");
+  static final SkyFunctionName RECURSIVE_FILESYSTEM_TRAVERSAL =
+      SkyFunctionName.createHermetic("RECURSIVE_DIRECTORY_TRAVERSAL");
+  public static final SkyFunctionName FILESET_ENTRY =
+      SkyFunctionName.createHermetic("FILESET_ENTRY");
+  static final SkyFunctionName BUILD_INFO_COLLECTION =
+      SkyFunctionName.createHermetic("BUILD_INFO_COLLECTION");
+  public static final SkyFunctionName BUILD_INFO = SkyFunctionName.createHermetic("BUILD_INFO");
+  public static final SkyFunctionName WORKSPACE_NAME =
+      SkyFunctionName.createHermetic("WORKSPACE_NAME");
+  // Non-hermetic because accesses package locator
+  public static final SkyFunctionName WORKSPACE_FILE =
+      SkyFunctionName.createNonHermetic("WORKSPACE_FILE");
+  static final SkyFunctionName COVERAGE_REPORT = SkyFunctionName.createHermetic("COVERAGE_REPORT");
+  public static final SkyFunctionName REPOSITORY = SkyFunctionName.createHermetic("REPOSITORY");
   public static final SkyFunctionName REPOSITORY_DIRECTORY =
-      SkyFunctionName.create("REPOSITORY_DIRECTORY");
-  public static final SkyFunctionName WORKSPACE_AST = SkyFunctionName.create("WORKSPACE_AST");
-  public static final SkyFunctionName EXTERNAL_PACKAGE = SkyFunctionName.create("EXTERNAL_PACKAGE");
-  public static final SkyFunctionName ACTION_TEMPLATE_EXPANSION =
-      SkyFunctionName.create("ACTION_TEMPLATE_EXPANSION");
+      SkyFunctionName.createNonHermetic("REPOSITORY_DIRECTORY");
+  public static final SkyFunctionName WORKSPACE_AST =
+      SkyFunctionName.createHermetic("WORKSPACE_AST");
+  // Non-hermetic because accesses package locator
+  public static final SkyFunctionName EXTERNAL_PACKAGE =
+      SkyFunctionName.createNonHermetic("EXTERNAL_PACKAGE");
+  static final SkyFunctionName ACTION_TEMPLATE_EXPANSION =
+      SkyFunctionName.createHermetic("ACTION_TEMPLATE_EXPANSION");
   public static final SkyFunctionName LOCAL_REPOSITORY_LOOKUP =
-      SkyFunctionName.create("LOCAL_REPOSITORY_LOOKUP");
-  public static final SkyFunctionName REGISTERED_EXECUTION_PLATFORMS =
-      SkyFunctionName.create("REGISTERED_EXECUTION_PLATFORMS");
-  public static final SkyFunctionName REGISTERED_TOOLCHAINS =
-      SkyFunctionName.create("REGISTERED_TOOLCHAINS");
-  public static final SkyFunctionName TOOLCHAIN_RESOLUTION =
-      SkyFunctionName.create("TOOLCHAIN_RESOLUTION");
+      SkyFunctionName.createHermetic("LOCAL_REPOSITORY_LOOKUP");
+  static final SkyFunctionName REGISTERED_EXECUTION_PLATFORMS =
+      SkyFunctionName.createHermetic("REGISTERED_EXECUTION_PLATFORMS");
+  static final SkyFunctionName REGISTERED_TOOLCHAINS =
+      SkyFunctionName.createHermetic("REGISTERED_TOOLCHAINS");
+  static final SkyFunctionName TOOLCHAIN_RESOLUTION =
+      SkyFunctionName.createHermetic("TOOLCHAIN_RESOLUTION");
   public static final SkyFunctionName REPOSITORY_MAPPING =
-      SkyFunctionName.create("REPOSITORY_MAPPING");
+      SkyFunctionName.createHermetic("REPOSITORY_MAPPING");
 
   public static Predicate<SkyKey> isSkyFunction(final SkyFunctionName functionName) {
     return new Predicate<SkyKey>() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyValueDirtinessChecker.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyValueDirtinessChecker.java
index 2a41a4740f..ad852d6268 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyValueDirtinessChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyValueDirtinessChecker.java
@@ -24,8 +24,10 @@ import javax.annotation.Nullable;
  * up to date.
  */
 public abstract class SkyValueDirtinessChecker {
-
-  /** Returns {@code true} iff the checker can handle {@code key}. */
+  /**
+   * Returns {@code true} iff the checker can handle {@code key}. Can only be true if {@code
+   * key.functionName().getHermeticity() == FunctionHermeticity.NONHERMETIC}.
+   */
   public abstract boolean applies(SkyKey key);
 
   /**
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