Allow SkyFunctions to return a sentinel value indicating that all of a node's in-progress data should be forgotten, and its evaluation should be restarted from scratch, as if it were freshly created/dirtied. To guard against this happening unexpectedly, any such events are passed to a GraphInconsistencyReceiver, which can verify that the SkyFunction is behaving properly.

This is the first change in a series to permit action rewinding when it is discovered that a previously generated input file is no longer available. When an action detects that one of its inputs is unusable, it can return this sentinel value, causing it to be re-evaluated from scratch. Follow-up changes will make the node corresponding to the input, and the node corresponding to the action that generated the input, dirty when this happens, causing the upstream action to be re-run, regenerating the desired input.

Currently works for builds that do not keep edges, although follow-ups may make this possible for all builds.

PiperOrigin-RevId: 194863097

18 files changed, 394 insertions, 52 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 4f192ac798..1fa364f76b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -151,6 +151,7 @@ import com.google.devtools.build.skyframe.Differencer.DiffWithDelta.Delta;
 import com.google.devtools.build.skyframe.ErrorInfo;
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver;
 import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.GraphInconsistencyReceiver;
 import com.google.devtools.build.skyframe.ImmutableDiff;
 import com.google.devtools.build.skyframe.Injectable;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
@@ -654,6 +655,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
             skyFunctions,
             evaluatorDiffer(),
             progressReceiver,
+            GraphInconsistencyReceiver.THROWING,
             emittedEventState,
             tracksStateForIncrementality());
     buildDriver = getBuildDriver();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java b/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
index 0c63193fea..d71830427d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
@@ -76,6 +76,7 @@ import com.google.devtools.build.skyframe.Differencer;
 import com.google.devtools.build.skyframe.ErrorInfo;
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver;
 import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.GraphInconsistencyReceiver;
 import com.google.devtools.build.skyframe.ImmutableDiff;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.Injectable;
@@ -333,6 +334,7 @@ public abstract class AbstractPackageLoader implements PackageLoader {
             makeFreshSkyFunctions(),
             preinjectedDifferencer,
             new EvaluationProgressReceiver.NullEvaluationProgressReceiver(),
+            GraphInconsistencyReceiver.THROWING,
             new MemoizingEvaluator.EmittedEventState(),
             /*keepEdges=*/ false));
   }
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 9526c855d9..e4a4193d57 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
@@ -86,7 +86,8 @@ public abstract class AbstractExceptionalParallelEvaluator<E extends Exception>
       ErrorInfoManager errorInfoManager,
       boolean keepGoing,
       int threadCount,
-      DirtyTrackingProgressReceiver progressReceiver) {
+      DirtyTrackingProgressReceiver progressReceiver,
+      GraphInconsistencyReceiver graphInconsistencyReceiver) {
     super(
         graph,
         graphVersion,
@@ -98,6 +99,7 @@ public abstract class AbstractExceptionalParallelEvaluator<E extends Exception>
         keepGoing,
         threadCount,
         progressReceiver,
+        graphInconsistencyReceiver,
         new SimpleCycleDetector());
   }
 
@@ -111,6 +113,7 @@ public abstract class AbstractExceptionalParallelEvaluator<E extends Exception>
       ErrorInfoManager errorInfoManager,
       boolean keepGoing,
       DirtyTrackingProgressReceiver progressReceiver,
+      GraphInconsistencyReceiver graphInconsistencyReceiver,
       ForkJoinPool forkJoinPool,
       CycleDetector cycleDetector) {
     super(
@@ -123,6 +126,7 @@ public abstract class AbstractExceptionalParallelEvaluator<E extends Exception>
         errorInfoManager,
         keepGoing,
         progressReceiver,
+        graphInconsistencyReceiver,
         forkJoinPool,
         cycleDetector);
   }
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 6ed51ad3f8..40ed157180 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -70,6 +70,7 @@ public abstract class AbstractParallelEvaluator {
       boolean keepGoing,
       int threadCount,
       DirtyTrackingProgressReceiver progressReceiver,
+      GraphInconsistencyReceiver graphInconsistencyReceiver,
       CycleDetector cycleDetector) {
     this.graph = graph;
     this.cycleDetector = cycleDetector;
@@ -85,6 +86,7 @@ public abstract class AbstractParallelEvaluator {
             storedEventFilter,
             errorInfoManager,
             Evaluate::new,
+            graphInconsistencyReceiver,
             threadCount);
   }
 
@@ -98,6 +100,7 @@ public abstract class AbstractParallelEvaluator {
       ErrorInfoManager errorInfoManager,
       boolean keepGoing,
       DirtyTrackingProgressReceiver progressReceiver,
+      GraphInconsistencyReceiver graphInconsistencyReceiver,
       ForkJoinPool forkJoinPool,
       CycleDetector cycleDetector) {
     this.graph = graph;
@@ -114,6 +117,7 @@ public abstract class AbstractParallelEvaluator {
             storedEventFilter,
             errorInfoManager,
             Evaluate::new,
+            graphInconsistencyReceiver,
             Preconditions.checkNotNull(forkJoinPool));
   }
 
@@ -442,6 +446,11 @@ public abstract class AbstractParallelEvaluator {
           env.doneBuilding();
         }
 
+        if (maybeEraseNodeToRestartFromScratch(skyKey, state, value)) {
+          evaluatorContext.getVisitor().enqueueEvaluation(skyKey);
+          return;
+        }
+
         // Helper objects for all the newly requested deps that weren't known to the environment,
         // and may contain duplicate elements.
         GroupedListHelper<SkyKey> newDirectDeps = env.getNewlyRequestedDeps();
@@ -601,6 +610,25 @@ public abstract class AbstractParallelEvaluator {
     private static final int MAX_REVERSEDEP_DUMP_LENGTH = 1000;
   }
 
+  private boolean maybeEraseNodeToRestartFromScratch(
+      SkyKey key, NodeEntry entry, SkyValue returnedValue) {
+    if (!SkyFunction.SENTINEL_FOR_RESTART_FROM_SCRATCH.equals(returnedValue)) {
+      return false;
+    }
+    evaluatorContext
+        .getGraphInconsistencyReceiver()
+        .noteInconsistencyAndMaybeThrow(
+            key, /*otherKey=*/ null, GraphInconsistencyReceiver.Inconsistency.RESET_REQUESTED);
+    entry.resetForRestartFromScratch();
+    // TODO(mschaller): rdeps of children have to be handled here. If the graph does not keep edges,
+    // nothing has to be done, since there are no reverse deps to keep consistent. If the graph
+    // keeps edges, it's a harder problem. The reverse deps could just be removed, but in the case
+    // that this node is dirty, the deps shouldn't be removed, they should just be transformed back
+    // to "known reverse deps" from "reverse deps declared during this evaluation" (the inverse of
+    // NodeEntry#checkIfDoneForDirtyReverseDep). Such a method doesn't currently exist, but could.
+    return true;
+  }
+
   void propagateEvaluatorContextCrashIfAny() {
     if (!evaluatorContext.getVisitor().getCrashes().isEmpty()) {
       evaluatorContext
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
index 689b1cd9db..95124ecb58 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -141,6 +141,11 @@ public abstract class DelegatingNodeEntry implements NodeEntry {
   }
 
   @Override
+  public void resetForRestartFromScratch() {
+    getDelegate().resetForRestartFromScratch();
+  }
+
+  @Override
   public Set<SkyKey> addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
     return getDelegate().addTemporaryDirectDeps(helper);
   }
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 d802c3d673..59a2e13db3 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -193,6 +193,11 @@ public abstract class DirtyBuildingState {
     return result.build();
   }
 
+  final void resetForRestartFromScratch() {
+    Preconditions.checkState(dirtyState == DirtyState.REBUILDING, this);
+    dirtyDirectDepIndex = 0;
+  }
+
   protected void markRebuilding() {
     Preconditions.checkState(dirtyState == DirtyState.NEEDS_REBUILDING, this);
     dirtyState = DirtyState.REBUILDING;
diff --git a/src/main/java/com/google/devtools/build/skyframe/GraphInconsistencyReceiver.java b/src/main/java/com/google/devtools/build/skyframe/GraphInconsistencyReceiver.java
new file mode 100644
index 0000000000..bba9264dac
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/GraphInconsistencyReceiver.java
@@ -0,0 +1,41 @@
+// 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;
+
+import javax.annotation.Nullable;
+
+/**
+ * A receiver that can be informed of inconsistencies detected in Skyframe. Such inconsistencies are
+ * usually the result of external data loss (such as nodes in the graph, or the results of external
+ * computations stored in a remote execution service).
+ *
+ * <p>The receiver can tolerate such inconsistencies, or throw hard if they are unexpected.
+ */
+public interface GraphInconsistencyReceiver {
+  void noteInconsistencyAndMaybeThrow(
+      SkyKey key, @Nullable SkyKey otherKey, Inconsistency inconsistency);
+
+  /** The type of inconsistency detected. */
+  enum Inconsistency {
+    RESET_REQUESTED
+  }
+
+  /** A {@link GraphInconsistencyReceiver} that crashes on any inconsistency. */
+  GraphInconsistencyReceiver THROWING =
+      (key, otherKey, inconsistency) -> {
+        throw new IllegalStateException(
+            "Unexpected inconsistency: " + key + ", " + otherKey + ", " + inconsistency);
+      };
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
index 5d29b82758..923c71242a 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
@@ -61,6 +61,7 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator {
   private Map<SkyKey, SkyValue> valuesToInject = new HashMap<>();
   private final InvalidationState deleterState = new DeletingInvalidationState();
   private final Differencer differencer;
+  private final GraphInconsistencyReceiver graphInconsistencyReceiver;
 
   // Keep edges in graph. Can be false to save memory, in which case incremental builds are
   // not possible.
@@ -83,18 +84,26 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator {
       Map<SkyFunctionName, ? extends SkyFunction> skyFunctions,
       Differencer differencer,
       @Nullable EvaluationProgressReceiver progressReceiver) {
-    this(skyFunctions, differencer, progressReceiver, new EmittedEventState(), true);
+    this(
+        skyFunctions,
+        differencer,
+        progressReceiver,
+        GraphInconsistencyReceiver.THROWING,
+        new EmittedEventState(),
+        true);
   }
 
   public InMemoryMemoizingEvaluator(
       Map<SkyFunctionName, ? extends SkyFunction> skyFunctions,
       Differencer differencer,
       @Nullable EvaluationProgressReceiver progressReceiver,
+      GraphInconsistencyReceiver graphInconsistencyReceiver,
       EmittedEventState emittedEventState,
       boolean keepEdges) {
     this.skyFunctions = ImmutableMap.copyOf(skyFunctions);
     this.differencer = Preconditions.checkNotNull(differencer);
     this.progressReceiver = new DirtyTrackingProgressReceiver(progressReceiver);
+    this.graphInconsistencyReceiver = Preconditions.checkNotNull(graphInconsistencyReceiver);
     this.graph = new InMemoryGraphImpl(keepEdges);
     this.emittedEventState = emittedEventState;
     this.keepEdges = keepEdges;
@@ -179,7 +188,8 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator {
               ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE,
               keepGoing,
               numThreads,
-              progressReceiver);
+              progressReceiver,
+              graphInconsistencyReceiver);
       EvaluationResult<T> result = evaluator.eval(roots);
       return EvaluationResult.<T>builder()
           .mergeFrom(result)
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 7b48275cbe..5a13c57ce0 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -582,6 +582,16 @@ public class InMemoryNodeEntry implements NodeEntry {
   }
 
   @Override
+  public synchronized void resetForRestartFromScratch() {
+    Preconditions.checkState(!isDone(), "Reset entry can't be done: %s", this);
+    directDeps = null;
+    signaledDeps = 0;
+    if (dirtyBuildingState != null) {
+      dirtyBuildingState.resetForRestartFromScratch();
+    }
+  }
+
+  @Override
   public synchronized Set<SkyKey> addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
     Preconditions.checkState(!isDone(), "add temp shouldn't be done: %s %s", helper, this);
     return getTemporaryDirectDeps().append(helper);
diff --git a/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java
index dac0927ca0..adff0d0589 100644
--- a/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java
@@ -165,6 +165,7 @@ public interface MemoizingEvaluator {
         ImmutableMap<SkyFunctionName, ? extends SkyFunction> skyFunctions,
         Differencer differencer,
         EvaluationProgressReceiver progressReceiver,
+        GraphInconsistencyReceiver graphInconsistencyReceiver,
         EmittedEventState emittedEventState,
         boolean keepEdges);
   }
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 02796390ef..aee68b3b91 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -355,6 +355,15 @@ public interface NodeEntry extends ThinNodeEntry {
   void removeUnfinishedDeps(Set<SkyKey> unfinishedDeps);
 
   /**
+   * Erases all stored work during this evaluation from this entry, namely all temporary direct
+   * deps. The entry will be as if it had never evaluated at this version. Called after the {@link
+   * SkyFunction} for this entry returns {@link SkyFunction#SENTINEL_FOR_RESTART_FROM_SCRATCH},
+   * indicating that something went wrong in external state and the evaluation has to be restarted.
+   */
+  @ThreadSafe
+  void resetForRestartFromScratch();
+
+  /**
    * Adds the temporary direct deps given in {@code helper} and returns the set of unique deps
    * added. It is the users responsibility to ensure that there are no elements in common between
    * helper and the already existing temporary direct deps.
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 cdcec829a9..afd0279e5f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -42,7 +42,8 @@ public class ParallelEvaluator extends AbstractExceptionalParallelEvaluator<Runt
       ErrorInfoManager errorInfoManager,
       boolean keepGoing,
       int threadCount,
-      DirtyTrackingProgressReceiver progressReceiver) {
+      DirtyTrackingProgressReceiver progressReceiver,
+      GraphInconsistencyReceiver graphInconsistencyReceiver) {
     super(
         graph,
         graphVersion,
@@ -53,7 +54,8 @@ public class ParallelEvaluator extends AbstractExceptionalParallelEvaluator<Runt
         errorInfoManager,
         keepGoing,
         threadCount,
-        progressReceiver);
+        progressReceiver,
+        graphInconsistencyReceiver);
   }
 
   public ParallelEvaluator(
@@ -66,6 +68,7 @@ public class ParallelEvaluator extends AbstractExceptionalParallelEvaluator<Runt
       ErrorInfoManager errorInfoManager,
       boolean keepGoing,
       DirtyTrackingProgressReceiver progressReceiver,
+      GraphInconsistencyReceiver graphInconsistencyReceiver,
       ForkJoinPool forkJoinPool,
       CycleDetector cycleDetector) {
     super(
@@ -78,6 +81,7 @@ public class ParallelEvaluator extends AbstractExceptionalParallelEvaluator<Runt
         errorInfoManager,
         keepGoing,
         progressReceiver,
+        graphInconsistencyReceiver,
         forkJoinPool,
         cycleDetector);
   }
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 6860433c01..14306d484b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
@@ -52,6 +52,7 @@ class ParallelEvaluatorContext {
   private final DirtyTrackingProgressReceiver progressReceiver;
   private final EventFilter storedEventFilter;
   private final ErrorInfoManager errorInfoManager;
+  private final GraphInconsistencyReceiver graphInconsistencyReceiver;
 
   /**
    * The visitor managing the thread pool. Used to enqueue parents when an entry is finished, and,
@@ -72,29 +73,20 @@ class ParallelEvaluatorContext {
       EventFilter storedEventFilter,
       ErrorInfoManager errorInfoManager,
       final Function<SkyKey, Runnable> runnableMaker,
+      GraphInconsistencyReceiver graphInconsistencyReceiver,
       final int threadCount) {
-    this.graph = graph;
-    this.graphVersion = graphVersion;
-    this.skyFunctions = skyFunctions;
-    this.reporter = reporter;
-    this.replayingNestedSetEventVisitor =
-        new NestedSetVisitor<>(new NestedSetEventReceiver(reporter), emittedEventState.eventState);
-    this.replayingNestedSetPostableVisitor =
-        new NestedSetVisitor<>(
-            new NestedSetPostableReceiver(reporter), emittedEventState.postableState);
-    this.keepGoing = keepGoing;
-    this.progressReceiver = Preconditions.checkNotNull(progressReceiver);
-    this.storedEventFilter = storedEventFilter;
-    this.errorInfoManager = errorInfoManager;
-    visitorSupplier =
-        Suppliers.memoize(
-            new Supplier<NodeEntryVisitor>() {
-              @Override
-              public NodeEntryVisitor get() {
-                return new NodeEntryVisitor(
-                    threadCount, progressReceiver, runnableMaker);
-              }
-            });
+    this(
+        graph,
+        graphVersion,
+        skyFunctions,
+        reporter,
+        emittedEventState,
+        keepGoing,
+        progressReceiver,
+        storedEventFilter,
+        errorInfoManager,
+        graphInconsistencyReceiver,
+        () -> new NodeEntryVisitor(threadCount, progressReceiver, runnableMaker));
   }
 
   ParallelEvaluatorContext(
@@ -108,11 +100,39 @@ class ParallelEvaluatorContext {
       EventFilter storedEventFilter,
       ErrorInfoManager errorInfoManager,
       final Function<SkyKey, Runnable> runnableMaker,
+      GraphInconsistencyReceiver graphInconsistencyReceiver,
       final ForkJoinPool forkJoinPool) {
+    this(
+        graph,
+        graphVersion,
+        skyFunctions,
+        reporter,
+        emittedEventState,
+        keepGoing,
+        progressReceiver,
+        storedEventFilter,
+        errorInfoManager,
+        graphInconsistencyReceiver,
+        () -> new NodeEntryVisitor(forkJoinPool, progressReceiver, runnableMaker));
+  }
+
+  private ParallelEvaluatorContext(
+      QueryableGraph graph,
+      Version graphVersion,
+      ImmutableMap<SkyFunctionName, ? extends SkyFunction> skyFunctions,
+      ExtendedEventHandler reporter,
+      EmittedEventState emittedEventState,
+      boolean keepGoing,
+      final DirtyTrackingProgressReceiver progressReceiver,
+      EventFilter storedEventFilter,
+      ErrorInfoManager errorInfoManager,
+      GraphInconsistencyReceiver graphInconsistencyReceiver,
+      Supplier<NodeEntryVisitor> visitorSupplier) {
     this.graph = graph;
     this.graphVersion = graphVersion;
     this.skyFunctions = skyFunctions;
     this.reporter = reporter;
+    this.graphInconsistencyReceiver = graphInconsistencyReceiver;
     this.replayingNestedSetEventVisitor =
         new NestedSetVisitor<>(new NestedSetEventReceiver(reporter), emittedEventState.eventState);
     this.replayingNestedSetPostableVisitor =
@@ -122,15 +142,7 @@ class ParallelEvaluatorContext {
     this.progressReceiver = Preconditions.checkNotNull(progressReceiver);
     this.storedEventFilter = storedEventFilter;
     this.errorInfoManager = errorInfoManager;
-    visitorSupplier =
-        Suppliers.memoize(
-            new Supplier<NodeEntryVisitor>() {
-              @Override
-              public NodeEntryVisitor get() {
-                return new NodeEntryVisitor(
-                    forkJoinPool, progressReceiver, runnableMaker);
-              }
-            });
+    this.visitorSupplier = Suppliers.memoize(visitorSupplier);
   }
 
   Map<SkyKey, ? extends NodeEntry> getBatchValues(
@@ -196,6 +208,10 @@ class ParallelEvaluatorContext {
     return progressReceiver;
   }
 
+  GraphInconsistencyReceiver getGraphInconsistencyReceiver() {
+    return graphInconsistencyReceiver;
+  }
+
   NestedSetVisitor<TaggedEvents> getReplayingNestedSetEventVisitor() {
     return replayingNestedSetEventVisitor;
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
index e1d16bb9ec..5eea55a17b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
+import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
@@ -53,7 +54,7 @@ import java.util.Set;
 abstract class ReverseDepsUtility {
   private ReverseDepsUtility() {}
 
-  static final int MAYBE_CHECK_THRESHOLD = 10;
+  @VisibleForTesting static final int MAYBE_CHECK_THRESHOLD = 10;
 
   /**
    * We can store one type of operation bare in order to save memory. For done nodes, most
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java
index 9975996af5..1ae29160b8 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java
@@ -36,15 +36,18 @@ public interface SkyFunction {
    * When a value is requested, this method is called with the name of the value and a
    * dependency-tracking environment.
    *
-   * <p>This method should return a non-{@code null} value, or {@code null} if any dependencies
-   * were missing ({@link Environment#valuesMissing} was true before returning). In that case the
-   * missing dependencies will be computed and the {@code compute} method called again.
+   * <p>This method should return a non-{@code null} value, or {@code null} if any dependencies were
+   * missing ({@link Environment#valuesMissing} was true before returning). In that case the missing
+   * dependencies will be computed and the {@code compute} method called again.
    *
-   * <p>This method should throw if it fails, or if one of its dependencies fails with an
-   * exception and this method cannot recover. If one of its dependencies fails and this method can
-   * enrich the exception with additional context, then this method should catch that exception and
-   * throw another containing that additional context. If it has no such additional context, then
-   * it should allow its dependency's exception to be thrown through it.
+   * <p>This method should throw if it fails, or if one of its dependencies fails with an exception
+   * and this method cannot recover. If one of its dependencies fails and this method can enrich the
+   * exception with additional context, then this method should catch that exception and throw
+   * another containing that additional context. If it has no such additional context, then it
+   * should allow its dependency's exception to be thrown through it.
+   *
+   * <p>This method may return {@link #SENTINEL_FOR_RESTART_FROM_SCRATCH} in rare circumstances. See
+   * its docs. Do not return this value unless you know exactly what you are doing.
    *
    * @throws SkyFunctionException on failure
    * @throws InterruptedException if interrupted
@@ -66,6 +69,17 @@ public interface SkyFunction {
   String extractTag(SkyKey skyKey);
 
   /**
+   * Sentinel value for {@link #compute} to return, indicating that something went wrong in external
+   * state and the evaluation has to be restarted from scratch, ignoring any deps that the {@link
+   * #compute} function may have declared during evaluation at this version (including deps declared
+   * during previous calls that returned null). Common causes for returning this would be data loss,
+   * if a dep's data is not actually available externally. In this case, the {@link SkyFunction}
+   * will likely dirty the unusable dep to force its re-evalution when re-requested by the restarted
+   * entry's computation.
+   */
+  SkyValue SENTINEL_FOR_RESTART_FROM_SCRATCH = new SkyValue() {};
+
+  /**
    * The services provided to the {@link SkyFunction#compute} implementation by the Skyframe
    * evaluation framework.
    */
diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
index 0f243c7aac..d9ebca5ebc 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -143,7 +143,8 @@ public class EagerInvalidatorTest {
             ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE,
             keepGoing,
             200,
-            new DirtyTrackingProgressReceiver(null));
+            new DirtyTrackingProgressReceiver(null),
+            GraphInconsistencyReceiver.THROWING);
     graphVersion = graphVersion.next();
     return evaluator.eval(ImmutableList.copyOf(keys));
   }
diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
index d2a5bfc6a6..807563a1eb 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -100,7 +100,7 @@ public class MemoizingEvaluatorTest {
     if (customProgressReceiver != null) {
       tester.setProgressReceiver(customProgressReceiver);
     }
-    tester.initialize();
+    tester.initialize(true);
   }
 
   protected RecordingDifferencer getRecordingDifferencer() {
@@ -110,9 +110,16 @@ public class MemoizingEvaluatorTest {
   protected MemoizingEvaluator getMemoizingEvaluator(
       Map<SkyFunctionName, ? extends SkyFunction> functions,
       Differencer differencer,
-      EvaluationProgressReceiver progressReceiver) {
+      EvaluationProgressReceiver progressReceiver,
+      GraphInconsistencyReceiver graphInconsistencyReceiver,
+      boolean keepEdges) {
     return new InMemoryMemoizingEvaluator(
-        functions, differencer, progressReceiver, emittedEventState, true);
+        functions,
+        differencer,
+        progressReceiver,
+        graphInconsistencyReceiver,
+        emittedEventState,
+        true);
   }
 
   protected BuildDriver getBuildDriver(MemoizingEvaluator evaluator) {
@@ -2252,6 +2259,171 @@ public class MemoizingEvaluatorTest {
         .isEqualTo(new StringValue("leafy"));
   }
 
+  @Test
+  public void resetNodeOnRequest_smoke() throws Exception {
+    SkyKey restartingKey = GraphTester.skyKey("restart");
+    StringValue expectedValue = new StringValue("done");
+    AtomicInteger numInconsistencyCalls = new AtomicInteger(0);
+    tester.setGraphInconsistencyReceiver(
+        (key, otherKey, inconsistency) -> {
+          Preconditions.checkState(otherKey == null, otherKey);
+          Preconditions.checkState(
+              inconsistency == GraphInconsistencyReceiver.Inconsistency.RESET_REQUESTED,
+              inconsistency);
+          Preconditions.checkState(restartingKey.equals(key), key);
+          numInconsistencyCalls.incrementAndGet();
+        });
+    tester.initialize(/*keepEdges=*/ true);
+    AtomicInteger numFunctionCalls = new AtomicInteger(0);
+    tester
+        .getOrCreate(restartingKey)
+        .setBuilder(
+            new SkyFunction() {
+
+              @Override
+              public SkyValue compute(SkyKey skyKey, Environment env) {
+                if (numFunctionCalls.getAndIncrement() < 2) {
+                  return SkyFunction.SENTINEL_FOR_RESTART_FROM_SCRATCH;
+                }
+                return expectedValue;
+              }
+
+              @Nullable
+              @Override
+              public String extractTag(SkyKey skyKey) {
+                return null;
+              }
+            });
+    assertThat(tester.evalAndGet(/*keepGoing=*/ false, restartingKey)).isEqualTo(expectedValue);
+    assertThat(numInconsistencyCalls.get()).isEqualTo(2);
+    assertThat(numFunctionCalls.get()).isEqualTo(3);
+    tester.getOrCreate(restartingKey, /*markAsModified=*/ true);
+    tester.invalidate();
+    numInconsistencyCalls.set(0);
+    numFunctionCalls.set(0);
+    assertThat(tester.evalAndGet(/*keepGoing=*/ false, restartingKey)).isEqualTo(expectedValue);
+    assertThat(numInconsistencyCalls.get()).isEqualTo(2);
+    assertThat(numFunctionCalls.get()).isEqualTo(3);
+  }
+
+  /** Mode in which to run {@link #runResetNodeOnRequest_withDeps}. */
+  protected enum RunResetNodeOnRequestWithDepsMode {
+    /** Do a second evaluation of the top node. */
+    REEVALUATE_TOP_NODE,
+    /**
+     * On the second evaluation, only evaluate a leaf node. This will detect reverse dep
+     * inconsistencies in that node from the clean evaluation, but does not require handling
+     * resetting dirty nodes.
+     */
+    REEVALUATE_LEAF_NODE_TO_FORCE_DIRTY,
+    /** Run the clean build without keeping edges. Incremental builds are therefore not possible. */
+    NO_KEEP_EDGES_SO_NO_REEVALUATION
+  }
+
+  protected void runResetNodeOnRequest_withDeps(RunResetNodeOnRequestWithDepsMode mode)
+      throws Exception {
+    SkyKey restartingKey = GraphTester.skyKey("restart");
+    AtomicInteger numInconsistencyCalls = new AtomicInteger(0);
+    tester.setGraphInconsistencyReceiver(
+        (key, otherKey, inconsistency) -> {
+          Preconditions.checkState(otherKey == null, otherKey);
+          Preconditions.checkState(
+              inconsistency == GraphInconsistencyReceiver.Inconsistency.RESET_REQUESTED,
+              inconsistency);
+          Preconditions.checkState(restartingKey.equals(key), key);
+          numInconsistencyCalls.incrementAndGet();
+        });
+    tester.initialize(mode != RunResetNodeOnRequestWithDepsMode.NO_KEEP_EDGES_SO_NO_REEVALUATION);
+    StringValue expectedValue = new StringValue("done");
+    SkyKey alreadyRequestedDep = GraphTester.skyKey("alreadyRequested");
+    SkyKey newlyRequestedNotDoneDep = GraphTester.skyKey("newlyRequestedNotDone");
+    SkyKey newlyRequestedDoneDep = GraphTester.skyKey("newlyRequestedDone");
+    tester
+        .getOrCreate(newlyRequestedDoneDep)
+        .setConstantValue(new StringValue("newlyRequestedDone"));
+    tester
+        .getOrCreate(alreadyRequestedDep)
+        .addDependency(newlyRequestedDoneDep)
+        .setConstantValue(new StringValue("alreadyRequested"));
+    tester
+        .getOrCreate(newlyRequestedNotDoneDep)
+        .setConstantValue(new StringValue("newlyRequestedNotDone"));
+    AtomicInteger numFunctionCalls = new AtomicInteger(0);
+    AtomicBoolean cleanBuild = new AtomicBoolean(true);
+    tester
+        .getOrCreate(restartingKey)
+        .setBuilder(
+            new SkyFunction() {
+              @Override
+              public SkyValue compute(SkyKey skyKey, Environment env) throws InterruptedException {
+                numFunctionCalls.getAndIncrement();
+                SkyValue dep1 = env.getValue(alreadyRequestedDep);
+                if (dep1 == null) {
+                  return null;
+                }
+                env.getValues(ImmutableList.of(newlyRequestedDoneDep, newlyRequestedNotDoneDep));
+                if (numFunctionCalls.get() < 4) {
+                  return SkyFunction.SENTINEL_FOR_RESTART_FROM_SCRATCH;
+                } else if (numFunctionCalls.get() == 4) {
+                  if (cleanBuild.get()) {
+                    Preconditions.checkState(
+                        env.valuesMissing(), "Not done dep should never have been enqueued");
+                  }
+                  return null;
+                }
+                return expectedValue;
+              }
+
+              @Nullable
+              @Override
+              public String extractTag(SkyKey skyKey) {
+                return null;
+              }
+            });
+    assertThat(tester.evalAndGet(/*keepGoing=*/ false, restartingKey)).isEqualTo(expectedValue);
+    assertThat(numInconsistencyCalls.get()).isEqualTo(2);
+    assertThat(numFunctionCalls.get()).isEqualTo(5);
+    switch (mode) {
+      case REEVALUATE_TOP_NODE:
+        tester
+            .getOrCreate(newlyRequestedDoneDep, /*markAsModified=*/ true)
+            .setConstantValue(new StringValue("new value"));
+        tester.invalidate();
+        numInconsistencyCalls.set(0);
+        // The dirty restartingKey's deps are checked for a changed dep before it is actually
+        // evaluated. It picks up dep1 as a dep during that checking phase, so to keep the
+        // SkyFunction in sync, we start numFunctionCalls at 1 instead of 0.
+        numFunctionCalls.set(1);
+        cleanBuild.set(false);
+        assertThat(tester.evalAndGet(/*keepGoing=*/ false, restartingKey)).isEqualTo(expectedValue);
+        assertThat(numInconsistencyCalls.get()).isEqualTo(2);
+        assertThat(numFunctionCalls.get()).isEqualTo(5);
+        return;
+      case REEVALUATE_LEAF_NODE_TO_FORCE_DIRTY:
+        // Confirm that when a node is marked dirty and its reverse deps are consolidated, we don't
+        // crash due to inconsistencies.
+        tester.getOrCreate(alreadyRequestedDep, /*markAsModified=*/ true);
+        tester.invalidate();
+        assertThat(tester.evalAndGet(/*keepGoing=*/ false, alreadyRequestedDep))
+            .isEqualTo(new StringValue("alreadyRequested"));
+        return;
+      case NO_KEEP_EDGES_SO_NO_REEVALUATION:
+        return;
+    }
+    throw new IllegalStateException("Unknown mode " + mode);
+  }
+
+  // TODO(mschaller): Enable test with other modes.
+  // TODO(janakr): Test would actually pass if there was no invalidation/subsequent re-evaluation
+  // because duplicate reverse deps aren't detected until the child is dirtied, which isn't awesome.
+  // REEVALUATE_LEAF_NODE_TO_FORCE_DIRTY allows us to check that even clean evaluations with
+  // keepEdges are still poisoned.
+  @Test
+  public void resetNodeOnRequest_withDeps() throws Exception {
+    runResetNodeOnRequest_withDeps(
+        RunResetNodeOnRequestWithDepsMode.NO_KEEP_EDGES_SO_NO_REEVALUATION);
+  }
+
   /**
    * The same dep is requested in two groups, but its value determines what the other dep in the
    * second group is. When it changes, the other dep in the second group should not be requested.
@@ -4631,11 +4803,18 @@ public class MemoizingEvaluatorTest {
     private MemoizingEvaluator evaluator;
     private BuildDriver driver;
     private TrackingProgressReceiver progressReceiver = new TrackingProgressReceiver();
+    private GraphInconsistencyReceiver graphInconsistencyReceiver =
+        GraphInconsistencyReceiver.THROWING;
 
-    public void initialize() {
+    public void initialize(boolean keepEdges) {
       this.differencer = getRecordingDifferencer();
       this.evaluator =
-          getMemoizingEvaluator(getSkyFunctionMap(), differencer, progressReceiver);
+          getMemoizingEvaluator(
+              getSkyFunctionMap(),
+              differencer,
+              progressReceiver,
+              graphInconsistencyReceiver,
+              keepEdges);
       this.driver = getBuildDriver(evaluator);
     }
 
@@ -4644,6 +4823,15 @@ public class MemoizingEvaluatorTest {
       progressReceiver = customProgressReceiver;
     }
 
+    /**
+     * Sets the {@link #graphInconsistencyReceiver}. {@link #initialize} must be called after this
+     * to have any effect/
+     */
+    public void setGraphInconsistencyReceiver(
+        GraphInconsistencyReceiver graphInconsistencyReceiver) {
+      this.graphInconsistencyReceiver = graphInconsistencyReceiver;
+    }
+
     public void invalidate() {
       differencer.invalidate(getModifiedValues());
       clearModifiedValues();
diff --git a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
index 19c78138f4..f2b5043a77 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -106,7 +106,8 @@ public class ParallelEvaluatorTest {
         ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE,
         keepGoing,
         150,
-        revalidationReceiver);
+        revalidationReceiver,
+        GraphInconsistencyReceiver.THROWING);
   }
 
   private ParallelEvaluator makeEvaluator(ProcessableGraph graph,