Allow NodeEntry implementations to keep just deps, as opposed to all edges or no edges. Also add option to disable checks in MemoizingEvaluatorTest that don't make sense for implementations that don't keep track of dirty nodes. Also extract RecordingDifferencer to an interface. And add a test for the situation that a node changes during a build that it's not requested, and which fails, necessitating cleanup.

PiperOrigin-RevId: 171616817

31 files changed, 298 insertions, 154 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index 61dd9f199c..02a6dfd684 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
@@ -322,7 +322,7 @@ public class BuildView {
   }
 
   @VisibleForTesting
-  WorkspaceStatusAction getLastWorkspaceBuildInfoActionForTesting() {
+  WorkspaceStatusAction getLastWorkspaceBuildInfoActionForTesting() throws InterruptedException {
     return skyframeExecutor.getLastWorkspaceStatusAction();
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index 1f4f8039a2..406de7850d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -66,6 +66,7 @@ import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.MemoizingEvaluator.EvaluatorSupplier;
 import com.google.devtools.build.skyframe.NodeEntry;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -184,7 +185,7 @@ public final class SequencedSkyframeExecutor extends SkyframeExecutor {
   protected void init() {
     // Note that we need to set recordingDiffer first since SkyframeExecutor#init calls
     // SkyframeExecutor#evaluatorDiffer.
-    recordingDiffer = new RecordingDifferencer();
+    recordingDiffer = new SequencedRecordingDifferencer();
     super.init();
   }
 
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 273ab775e1..0891d0602d 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
@@ -677,7 +677,8 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
     PrecomputedValue.DEFAULTS_PACKAGE_CONTENTS.set(injectable(), defaultsPackageContents);
   }
 
-  public void maybeInvalidateWorkspaceStatusValue(String workspaceName) {
+  public void maybeInvalidateWorkspaceStatusValue(String workspaceName)
+      throws InterruptedException {
     WorkspaceStatusAction newWorkspaceStatusAction = makeWorkspaceStatusAction(workspaceName);
     WorkspaceStatusAction oldWorkspaceStatusAction = getLastWorkspaceStatusAction();
     if (oldWorkspaceStatusAction != null
@@ -696,7 +697,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
 
   @VisibleForTesting
   @Nullable
-  public WorkspaceStatusAction getLastWorkspaceStatusAction() {
+  public WorkspaceStatusAction getLastWorkspaceStatusAction() throws InterruptedException {
     WorkspaceStatusValue workspaceStatusValue =
         (WorkspaceStatusValue) memoizingEvaluator.getExistingValue(WorkspaceStatusValue.SKY_KEY);
     return workspaceStatusValue == null
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 e0b3579d09..e884954845 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -28,7 +28,7 @@ public abstract class DelegatingNodeEntry implements NodeEntry {
   }
 
   @Override
-  public boolean keepEdges() {
+  public KeepEdgesPolicy keepEdges() {
     return getDelegate().keepEdges();
   }
 
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 2b8dc9aef6..30884fcbe5 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -43,8 +43,10 @@ public abstract class DirtyBuildingState {
    * build to check whether this node has changed in {@link NodeEntry#setValue}. If they are null,
    * it means that this node is being built for the first time. See {@link
    * InMemoryNodeEntry#directDeps} for more on dependency group storage.
+   *
+   * <p>Public only for the use of alternative graph implementations.
    */
-  protected abstract GroupedList<SkyKey> getLastBuildDirectDeps() throws InterruptedException;
+  public abstract GroupedList<SkyKey> getLastBuildDirectDeps() throws InterruptedException;
 
   /**
    * The number of groups of the dependencies requested last time when the node was built.
@@ -53,8 +55,12 @@ public abstract class DirtyBuildingState {
    */
   protected abstract int getNumOfGroupsInLastBuildDirectDeps();
 
-  /** The value of the node the last time it was built. */
-  protected abstract SkyValue getLastBuildValue() throws InterruptedException;
+  /**
+   * The value of the node the last time it was built.
+   *
+   * <p>Public only for the use of alternative graph implementations.
+   */
+  public abstract SkyValue getLastBuildValue() throws InterruptedException;
 
   /**
    * Group of children to be checked next in the process of determining if this entry needs to be
@@ -216,12 +222,12 @@ public abstract class DirtyBuildingState {
     }
 
     @Override
-    protected SkyValue getLastBuildValue() {
+    public SkyValue getLastBuildValue() {
       return lastBuildValue;
     }
 
     @Override
-    protected GroupedList<SkyKey> getLastBuildDirectDeps() throws InterruptedException {
+    public GroupedList<SkyKey> getLastBuildDirectDeps() throws InterruptedException {
       return lastBuildDirectDeps;
     }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/EdgelessInMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/EdgelessInMemoryNodeEntry.java
index daa24ac64d..b0c2b2e714 100644
--- a/src/main/java/com/google/devtools/build/skyframe/EdgelessInMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/EdgelessInMemoryNodeEntry.java
@@ -26,7 +26,13 @@ package com.google.devtools.build.skyframe;
  */
 class EdgelessInMemoryNodeEntry extends InMemoryNodeEntry {
   @Override
-  public boolean keepEdges() {
-    return false;
+  public KeepEdgesPolicy keepEdges() {
+    return KeepEdgesPolicy.NONE;
+  }
+
+  @Override
+  protected void postProcessAfterDone() {
+    this.directDeps = null;
+    this.reverseDeps = null;
   }
 }
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 007cfefa12..67e1867b7f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -73,7 +73,7 @@ import javax.annotation.Nullable;
 public class InMemoryNodeEntry implements NodeEntry {
 
   /** Actual data stored in this entry when it is done. */
-  private SkyValue value = null;
+  protected SkyValue value = null;
 
   /**
    * The last version of the graph at which this node's value was changed. In {@link #setValue} it
@@ -95,13 +95,13 @@ public class InMemoryNodeEntry implements NodeEntry {
 
   /**
    * This object represents the direct deps of the node, in groups if the {@code SkyFunction}
-   * requested them that way. It contains either the in-progress direct deps, stored as a
-   * {@code GroupedList<SkyKey>} before the node is finished building, or the full direct deps,
-   * compressed in a memory-efficient way (via {@link GroupedList#compress}, after the node is done.
+   * requested them that way. It contains either the in-progress direct deps, stored as a {@code
+   * GroupedList<SkyKey>} before the node is finished building, or the full direct deps, compressed
+   * in a memory-efficient way (via {@link GroupedList#compress}, after the node is done.
    *
    * <p>It is initialized lazily in getTemporaryDirectDeps() to save a little bit more memory.
    */
-  private Object directDeps = null;
+  protected Object directDeps = null;
 
   /**
    * This list stores the reverse dependencies of this node that have been declared so far.
@@ -175,8 +175,12 @@ public class InMemoryNodeEntry implements NodeEntry {
   }
 
   @Override
-  public boolean keepEdges() {
-    return true;
+  public KeepEdgesPolicy keepEdges() {
+    return KeepEdgesPolicy.ALL;
+  }
+
+  private boolean keepReverseDeps() {
+    return keepEdges() == KeepEdgesPolicy.ALL;
   }
 
   @Override
@@ -224,7 +228,7 @@ public class InMemoryNodeEntry implements NodeEntry {
    * added in {@link #addTemporaryDirectDeps}.
    */
   public synchronized GroupedList<SkyKey> getGroupedDirectDeps() {
-    assertKeepEdges();
+    assertKeepDeps();
     Preconditions.checkState(isDone(), "no deps until done. NodeEntry: %s", this);
     return GroupedList.create(directDeps);
   }
@@ -236,7 +240,7 @@ public class InMemoryNodeEntry implements NodeEntry {
     return ValueWithMetadata.getMaybeErrorInfo(value);
   }
 
-  private DirtyBuildingState getDirtyBuildingState() {
+  protected DirtyBuildingState getDirtyBuildingState() {
     return Preconditions.checkNotNull(dirtyBuildingState, "Didn't have state: %s", this);
   }
 
@@ -249,20 +253,18 @@ public class InMemoryNodeEntry implements NodeEntry {
     signaledDeps = NOT_EVALUATING_SENTINEL;
   }
 
-  protected synchronized Set<SkyKey> setStateFinishedAndReturnReverseDepsToSignal() {
+  protected final synchronized Set<SkyKey> setStateFinishedAndReturnReverseDepsToSignal() {
     Set<SkyKey> reverseDepsToSignal =
         ReverseDepsUtility.consolidateDataAndReturnNewElements(this, getOpToStoreBare());
     this.directDeps = getTemporaryDirectDeps().compress();
 
     markDone();
-
-    if (!keepEdges()) {
-      this.directDeps = null;
-      this.reverseDeps = null;
-    }
+    postProcessAfterDone();
     return reverseDepsToSignal;
   }
 
+  protected void postProcessAfterDone() {}
+
   @Override
   public synchronized Set<SkyKey> getInProgressReverseDeps() {
     Preconditions.checkState(!isDone(), this);
@@ -298,7 +300,7 @@ public class InMemoryNodeEntry implements NodeEntry {
   public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
     if (reverseDep != null) {
       if (isDone()) {
-        if (keepEdges()) {
+        if (keepReverseDeps()) {
           ReverseDepsUtility.addReverseDeps(this, ImmutableList.of(reverseDep));
         }
       } else {
@@ -356,7 +358,13 @@ public class InMemoryNodeEntry implements NodeEntry {
   @Override
   public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
     Preconditions.checkNotNull(reverseDep, this);
-    Preconditions.checkState(keepEdges(), "%s %s", reverseDep, this);
+    // Note that implementations of InMemoryNodeEntry that have
+    // #keepEdges == KeepEdgesPolicy.JUST_DEPS may override this entire method.
+    Preconditions.checkState(
+        keepEdges() == KeepEdgesPolicy.ALL,
+        "Incremental means keeping edges %s %s",
+        reverseDep,
+        this);
     if (isDone()) {
       ReverseDepsUtility.checkReverseDep(this, reverseDep);
     } else {
@@ -367,7 +375,7 @@ public class InMemoryNodeEntry implements NodeEntry {
 
   @Override
   public synchronized void removeReverseDep(SkyKey reverseDep) {
-    if (!keepEdges()) {
+    if (!keepReverseDeps()) {
       return;
     }
     if (isDone()) {
@@ -386,14 +394,14 @@ public class InMemoryNodeEntry implements NodeEntry {
 
   @Override
   public synchronized Set<SkyKey> getReverseDepsForDoneEntry() {
-    assertKeepEdges();
+    assertKeepRdeps();
     Preconditions.checkState(isDone(), "Called on not done %s", this);
     return ReverseDepsUtility.getReverseDeps(this);
   }
 
   @Override
   public synchronized Set<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
-    assertKeepEdges();
+    assertKeepRdeps();
     if (!isDone()) {
       // This consolidation loses information about pending reverse deps to signal, but that is
       // unimportant since this node is being deleted.
@@ -429,13 +437,19 @@ public class InMemoryNodeEntry implements NodeEntry {
   }
 
   /** Checks that a caller is not trying to access not-stored graph edges. */
-  private void assertKeepEdges() {
-    Preconditions.checkState(keepEdges(), "Graph edges not stored. %s", this);
+  private void assertKeepDeps() {
+    Preconditions.checkState(keepEdges() != KeepEdgesPolicy.NONE, "Not keeping deps: %s", this);
+  }
+
+  /** Checks that a caller is not trying to access not-stored graph edges. */
+  private void assertKeepRdeps() {
+    Preconditions.checkState(keepEdges() == KeepEdgesPolicy.ALL, "Not keeping rdeps: %s", this);
   }
 
   @Override
   public synchronized MarkedDirtyResult markDirty(boolean isChanged) {
-    assertKeepEdges();
+    // Can't process a dirty node without its deps.
+    assertKeepDeps();
     if (isDone()) {
       dirtyBuildingState =
           DirtyBuildingState.create(isChanged, GroupedList.<SkyKey>create(directDeps), value);
@@ -601,21 +615,24 @@ public class InMemoryNodeEntry implements NodeEntry {
         .toString();
   }
 
+  protected synchronized InMemoryNodeEntry cloneNodeEntry(InMemoryNodeEntry newEntry) {
+    // As this is temporary, for now let's limit to done nodes.
+    Preconditions.checkState(isDone(), "Only done nodes can be copied: %s", this);
+    newEntry.value = value;
+    newEntry.lastChangedVersion = this.lastChangedVersion;
+    newEntry.lastEvaluatedVersion = this.lastEvaluatedVersion;
+    ReverseDepsUtility.addReverseDeps(newEntry, ReverseDepsUtility.getReverseDeps(this));
+    newEntry.directDeps = directDeps;
+    newEntry.dirtyBuildingState = null;
+    return newEntry;
+  }
+
   /**
    * Do not use except in custom evaluator implementations! Added only temporarily.
    *
    * <p>Clones a InMemoryMutableNodeEntry iff it is a done node. Otherwise it fails.
    */
   public synchronized InMemoryNodeEntry cloneNodeEntry() {
-    // As this is temporary, for now let's limit to done nodes.
-    Preconditions.checkState(isDone(), "Only done nodes can be copied: %s", this);
-    InMemoryNodeEntry nodeEntry = new InMemoryNodeEntry();
-    nodeEntry.value = value;
-    nodeEntry.lastChangedVersion = this.lastChangedVersion;
-    nodeEntry.lastEvaluatedVersion = this.lastEvaluatedVersion;
-    ReverseDepsUtility.addReverseDeps(nodeEntry, ReverseDepsUtility.getReverseDeps(this));
-    nodeEntry.directDeps = directDeps;
-    nodeEntry.dirtyBuildingState = null;
-    return nodeEntry;
+    return cloneNodeEntry(new InMemoryNodeEntry());
   }
 }
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 889c9df7b8..562c2eaebc 100644
--- a/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java
@@ -113,7 +113,7 @@ public interface MemoizingEvaluator {
    */
   @VisibleForTesting
   @Nullable
-  SkyValue getExistingValue(SkyKey key);
+  SkyValue getExistingValue(SkyKey key) throws InterruptedException;
 
   /**
    * Returns an error if and only if an earlier call to {@link #evaluate} created it; null
@@ -127,7 +127,7 @@ public interface MemoizingEvaluator {
   ErrorInfo getExistingErrorForTesting(SkyKey key) throws InterruptedException;
 
   @Nullable
-  NodeEntry getExistingEntryForTesting(SkyKey key);
+  NodeEntry getExistingEntryForTesting(SkyKey key) throws InterruptedException;
 
   /**
    * Tests that want finer control over the graph being used may provide a {@code transformer} here.
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 57334d6384..7857915fa2 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -75,7 +75,7 @@ public interface NodeEntry extends ThinNodeEntry {
     REBUILDING
   }
 
-  boolean keepEdges();
+  KeepEdgesPolicy keepEdges();
 
   /**
    * Returns the value stored in this entry. This method may only be called after the evaluation of
@@ -378,4 +378,17 @@ public interface NodeEntry extends ThinNodeEntry {
    */
   @ThreadSafe
   boolean isReady();
+
+  /** Which edges a done NodeEntry stores (dependencies and/or reverse dependencies. */
+  enum KeepEdgesPolicy {
+    /** Both deps and rdeps are stored. Incremental builds and sanity checks are possible. */
+    ALL,
+    /**
+     * Only deps are stored. Incremental builds may be possible with a "top-down" evaluation
+     * framework. Sanity checking of reverse deps is not possible.
+     */
+    JUST_DEPS,
+    /** Neither deps nor rdeps are stored. Incremental builds and sanity checking are disabled. */
+    NONE
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/RecordingDifferencer.java b/src/main/java/com/google/devtools/build/skyframe/RecordingDifferencer.java
index a4d768d043..d92f93b4eb 100644
--- a/src/main/java/com/google/devtools/build/skyframe/RecordingDifferencer.java
+++ b/src/main/java/com/google/devtools/build/skyframe/RecordingDifferencer.java
@@ -1,4 +1,4 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
+// Copyright 2017 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.
@@ -11,47 +11,18 @@
 // 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 com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterables;
-import com.google.devtools.build.lib.concurrent.ThreadSafety;
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-/**
- * A simple Differencer which just records the invalidated values it's been given.
- */
-@ThreadSafety.ThreadCompatible
-public class RecordingDifferencer implements Differencer, Injectable {
-
-  private List<SkyKey> valuesToInvalidate;
-  private Map<SkyKey, SkyValue> valuesToInject;
-
-  public RecordingDifferencer() {
-    clear();
-  }
-
-  private void clear() {
-    valuesToInvalidate = new ArrayList<>();
-    valuesToInject = new HashMap<>();
-  }
 
+/** A simple {@link Differencer} that is manually informed of invalid/injected nodes. */
+public interface RecordingDifferencer extends Differencer, Injectable {
   @Override
-  public Diff getDiff(WalkableGraph fromGraph, Version fromVersion, Version toVersion) {
-    Diff diff = new ImmutableDiff(valuesToInvalidate, valuesToInject);
-    clear();
-    return diff;
-  }
+  Diff getDiff(WalkableGraph fromGraph, Version fromVersion, Version toVersion);
 
-  /**
-   * Store the given values for invalidation.
-   */
-  public void invalidate(Iterable<SkyKey> values) {
-    Iterables.addAll(valuesToInvalidate, values);
-  }
+  /** Stores the given values for invalidation. */
+  void invalidate(Iterable<SkyKey> values);
 
   /**
    * Invalidates the cached values of any values in error transiently.
@@ -59,22 +30,9 @@ public class RecordingDifferencer implements Differencer, Injectable {
    * <p>If a future call to {@link MemoizingEvaluator#evaluate} requests a value that transitively
    * depends on any value that was in an error state (or is one of these), they will be re-computed.
    */
-  public void invalidateTransientErrors() {
+  default void invalidateTransientErrors() {
     // All transient error values have a dependency on the single global ERROR_TRANSIENCE value,
     // so we only have to invalidate that one value to catch everything.
     invalidate(ImmutableList.of(ErrorTransienceValue.KEY));
   }
-
-  /**
-   * Store the given values for injection.
-   */
-  @Override
-  public void inject(Map<SkyKey, ? extends SkyValue> values) {
-    valuesToInject.putAll(values);
-  }
-
-  @Override
-  public void inject(SkyKey key, SkyValue value) {
-    valuesToInject.put(key, value);
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/SequencedRecordingDifferencer.java b/src/main/java/com/google/devtools/build/skyframe/SequencedRecordingDifferencer.java
new file mode 100644
index 0000000000..80aad4ec58
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/SequencedRecordingDifferencer.java
@@ -0,0 +1,60 @@
+// Copyright 2014 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 com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.concurrent.ThreadSafety;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/** A simple Differencer which just records the invalidated values it's been given. */
+@ThreadSafety.ThreadCompatible
+public class SequencedRecordingDifferencer implements RecordingDifferencer {
+
+  private List<SkyKey> valuesToInvalidate;
+  private Map<SkyKey, SkyValue> valuesToInject;
+
+  public SequencedRecordingDifferencer() {
+    clear();
+  }
+
+  private void clear() {
+    valuesToInvalidate = new ArrayList<>();
+    valuesToInject = new HashMap<>();
+  }
+
+  @Override
+  public Diff getDiff(WalkableGraph fromGraph, Version fromVersion, Version toVersion) {
+    Diff diff = new ImmutableDiff(valuesToInvalidate, valuesToInject);
+    clear();
+    return diff;
+  }
+
+  @Override
+  public void invalidate(Iterable<SkyKey> values) {
+    Iterables.addAll(valuesToInvalidate, values);
+  }
+
+  @Override
+  public void inject(Map<SkyKey, ? extends SkyValue> values) {
+    valuesToInject.putAll(values);
+  }
+
+  @Override
+  public void inject(SkyKey key, SkyValue value) {
+    valuesToInject.put(key, value);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/SequentialBuildDriver.java b/src/main/java/com/google/devtools/build/skyframe/SequentialBuildDriver.java
index 82b4ecbb75..c4430db939 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SequentialBuildDriver.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SequentialBuildDriver.java
@@ -59,7 +59,7 @@ public class SequentialBuildDriver implements BuildDriver {
 
   @Nullable
   @Override
-  public SkyValue getExistingValueForTesting(SkyKey key) {
+  public SkyValue getExistingValueForTesting(SkyKey key) throws InterruptedException {
     return memoizingEvaluator.getExistingValue(key);
   }
 
@@ -71,7 +71,7 @@ public class SequentialBuildDriver implements BuildDriver {
 
   @Nullable
   @Override
-  public NodeEntry getEntryForTesting(SkyKey key) {
+  public NodeEntry getEntryForTesting(SkyKey key) throws InterruptedException {
     return memoizingEvaluator.getExistingEntryForTesting(key);
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
index eb3296cfb0..405e401950 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
@@ -357,7 +357,7 @@ public abstract class AnalysisTestCase extends FoundationTestCase {
     return update(new EventBus(), defaultFlags(), aspects, labels);
   }
 
-  protected Target getTarget(String label) {
+  protected Target getTarget(String label) throws InterruptedException {
     try {
       return SkyframeExecutorTestUtils.getExistingTarget(skyframeExecutor,
           Label.parseAbsolute(label));
diff --git a/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java b/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java
index 488b554d68..aa537287a9 100644
--- a/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java
+++ b/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java
@@ -54,6 +54,7 @@ import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -128,7 +129,7 @@ public class ExternalPackageUtilTest extends BuildViewTestCase {
     skyFunctions.put(GET_RULE_BY_NAME_FUNCTION, new GetRuleByNameFunction());
     skyFunctions.put(GET_REGISTERED_TOOLCHAINS_FUNCTION, new GetRegisteredToolchainsFunction());
 
-    RecordingDifferencer differencer = new RecordingDifferencer();
+    RecordingDifferencer differencer = new SequencedRecordingDifferencer();
     MemoizingEvaluator evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
     driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
diff --git a/src/test/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorTest.java b/src/test/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorTest.java
index 7229e25810..57e517e4d2 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorTest.java
@@ -47,6 +47,7 @@ import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -82,7 +83,7 @@ public class RepositoryDelegatorTest extends FoundationTestCase {
         pkgLocator,
         ExternalFileAction.DEPEND_ON_EXTERNAL_PKG_FOR_EXTERNAL_REPO_PATHS,
         directories);
-    RecordingDifferencer differencer = new RecordingDifferencer();
+    RecordingDifferencer differencer = new SequencedRecordingDifferencer();
     MemoizingEvaluator evaluator =
         new InMemoryMemoizingEvaluator(
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
index 954a3d5cdb..991959096a 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
@@ -45,6 +45,7 @@ import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -71,7 +72,7 @@ public final class ActionTemplateExpansionFunctionTest extends FoundationTestCas
     artifactValueMap = new LinkedHashMap<>();
     AtomicReference<PathPackageLocator> pkgLocator = new AtomicReference<>(new PathPackageLocator(
         rootDirectory.getFileSystem().getPath("/outputbase"), ImmutableList.of(rootDirectory)));
-    RecordingDifferencer differencer = new RecordingDifferencer();
+    RecordingDifferencer differencer = new SequencedRecordingDifferencer();
     MemoizingEvaluator evaluator =
         new InMemoryMemoizingEvaluator(
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
index 673fcfb2b8..c33f14f3ea 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
@@ -459,7 +459,7 @@ public class ArtifactFunctionTest extends ArtifactFunctionTestCase {
     return result.get(key);
   }
 
-  private void setGeneratingActions() {
+  private void setGeneratingActions() throws InterruptedException {
     if (evaluator.getExistingValue(OWNER_KEY) == null) {
       differencer.inject(
           ImmutableMap.of(
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
index 127261d16a..9408db89c8 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
@@ -38,6 +38,7 @@ import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -59,7 +60,7 @@ abstract class ArtifactFunctionTestCase {
 
   protected Set<ActionAnalysisMetadata> actions;
   protected boolean fastDigest = false;
-  protected RecordingDifferencer differencer = new RecordingDifferencer();
+  protected RecordingDifferencer differencer = new SequencedRecordingDifferencer();
   protected SequentialBuildDriver driver;
   protected MemoizingEvaluator evaluator;
   protected Path root;
@@ -82,7 +83,7 @@ abstract class ArtifactFunctionTestCase {
         pkgLocator,
         ExternalFileAction.DEPEND_ON_EXTERNAL_PKG_FOR_EXTERNAL_REPO_PATHS,
         directories);
-    differencer = new RecordingDifferencer();
+    differencer = new SequencedRecordingDifferencer();
     evaluator =
         new InMemoryMemoizingEvaluator(
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
index bbfb0f8aba..3c662db805 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
@@ -43,6 +43,7 @@ import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -132,7 +133,7 @@ public class ContainingPackageLookupFunctionTest extends FoundationTestCase {
             repositoryHandlers, null, new AtomicBoolean(true), ImmutableMap::of, directories));
     skyFunctions.put(SkyFunctions.REPOSITORY, new RepositoryLoaderFunction());
 
-    differencer = new RecordingDifferencer();
+    differencer = new SequencedRecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
     driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
index df5ed51efb..93bb5aeccc 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
@@ -64,6 +64,7 @@ import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -126,7 +127,7 @@ public class FileFunctionTest {
             new ServerDirectories(pkgRoot, outputBase), pkgRoot, TestConstants.PRODUCT_NAME);
     ExternalFilesHelper externalFilesHelper =
         new ExternalFilesHelper(pkgLocatorRef, externalFileAction, directories);
-    differencer = new RecordingDifferencer();
+    differencer = new SequencedRecordingDifferencer();
     MemoizingEvaluator evaluator =
         new InMemoryMemoizingEvaluator(
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
index 66c4d16eaf..1ee69a3c46 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
@@ -51,6 +51,7 @@ import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -115,7 +116,7 @@ public final class FilesetEntryFunctionTest extends FoundationTestCase {
     skyFunctions.put(SkyFunctions.FILESET_ENTRY, new FilesetEntryFunction());
     skyFunctions.put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction());
 
-    differencer = new RecordingDifferencer();
+    differencer = new SequencedRecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
     driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
index 80e3bdef61..f1b8b407bf 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
@@ -60,6 +60,7 @@ import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -133,7 +134,7 @@ public class FilesystemValueCheckerTest {
             directories));
     skyFunctions.put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction());
 
-    differencer = new RecordingDifferencer();
+    differencer = new SequencedRecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions.build(), differencer);
     driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
index bfa4e9d292..811c962997 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
@@ -49,6 +49,7 @@ import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -109,7 +110,7 @@ public abstract class GlobFunctionTest {
         new AtomicReference<>(
             new PathPackageLocator(outputBase, ImmutableList.of(writableRoot, root)));
 
-    differencer = new RecordingDifferencer();
+    differencer = new SequencedRecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(createFunctionMap(), differencer);
     driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java
index eacefdcf0d..ca81506a63 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java
@@ -41,6 +41,7 @@ import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -109,7 +110,7 @@ public class LocalRepositoryLookupFunctionTest extends FoundationTestCase {
     skyFunctions.put(
         SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS, new FileSymlinkCycleUniquenessFunction());
 
-    differencer = new RecordingDifferencer();
+    differencer = new SequencedRecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
     driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
index 51642f370c..990e5935b7 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
@@ -52,6 +52,7 @@ import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -139,7 +140,7 @@ public abstract class PackageLookupFunctionTest extends FoundationTestCase {
             repositoryHandlers, null, new AtomicBoolean(true), ImmutableMap::of, directories));
     skyFunctions.put(SkyFunctions.REPOSITORY, new RepositoryLoaderFunction());
 
-    differencer = new RecordingDifferencer();
+    differencer = new SequencedRecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
     driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
index a926a75101..c3cb04f282 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
@@ -54,6 +54,7 @@ import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -136,7 +137,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
         SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS, new FileSymlinkCycleUniquenessFunction());
 
     progressReceiver = new RecordingEvaluationProgressReceiver();
-    differencer = new RecordingDifferencer();
+    differencer = new SequencedRecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer, progressReceiver);
     driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
index d39d857f05..3ecc85b596 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
@@ -82,6 +82,7 @@ import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -116,7 +117,7 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
 
   protected Clock clock = BlazeClock.instance();
   protected TimestampGranularityMonitor tsgm;
-  protected RecordingDifferencer differencer = new RecordingDifferencer();
+  protected RecordingDifferencer differencer = new SequencedRecordingDifferencer();
   private Set<ActionAnalysisMetadata> actions;
 
   protected AtomicReference<EventBus> eventBusRef = new AtomicReference<>();
@@ -170,7 +171,7 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
         pkgLocator,
         ExternalFileAction.DEPEND_ON_EXTERNAL_PKG_FOR_EXTERNAL_REPO_PATHS,
         directories);
-    differencer = new RecordingDifferencer();
+    differencer = new SequencedRecordingDifferencer();
 
     ActionExecutionStatusReporter statusReporter =
         ActionExecutionStatusReporter.create(new StoredEventHandler());
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
index 6b53a00383..54b4e483d0 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
@@ -223,7 +223,7 @@ public class TreeArtifactMetadataTest extends ArtifactFunctionTestCase {
     return result.get(key);
   }
 
-  private void setGeneratingActions() {
+  private void setGeneratingActions() throws InterruptedException {
     if (evaluator.getExistingValue(OWNER_KEY) == null) {
       differencer.inject(
           ImmutableMap.of(
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/util/SkyframeExecutorTestUtils.java b/src/test/java/com/google/devtools/build/lib/skyframe/util/SkyframeExecutorTestUtils.java
index 30b0076010..9f8e1d09eb 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/util/SkyframeExecutorTestUtils.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/util/SkyframeExecutorTestUtils.java
@@ -45,11 +45,10 @@ public class SkyframeExecutorTestUtils {
   private SkyframeExecutorTestUtils() {
   }
 
-  /**
-   * Returns an existing value, or {@code null} if the given key is not currently in the graph.
-   */
+  /** Returns an existing value, or {@code null} if the given key is not currently in the graph. */
   @Nullable
-  public static SkyValue getExistingValue(SkyframeExecutor skyframeExecutor, SkyKey key) {
+  public static SkyValue getExistingValue(SkyframeExecutor skyframeExecutor, SkyKey key)
+      throws InterruptedException {
     return skyframeExecutor.getEvaluatorForTesting().getExistingValue(key);
   }
 
@@ -77,11 +76,12 @@ public class SkyframeExecutorTestUtils {
    * Returns an existing configured target value, or {@code null} if there is not an appropriate
    * configured target value key in the graph.
    *
-   * This helper is provided so legacy tests don't need to know about details of skyframe keys.
+   * <p>This helper is provided so legacy tests don't need to know about details of skyframe keys.
    */
   @Nullable
   public static ConfiguredTargetValue getExistingConfiguredTargetValue(
-      SkyframeExecutor skyframeExecutor, Label label, BuildConfiguration config) {
+      SkyframeExecutor skyframeExecutor, Label label, BuildConfiguration config)
+      throws InterruptedException {
     SkyKey key = ConfiguredTargetValue.key(label, config);
     return (ConfiguredTargetValue) getExistingValue(skyframeExecutor, key);
   }
@@ -90,12 +90,12 @@ public class SkyframeExecutorTestUtils {
    * Returns the configured target for an existing configured target value, or {@code null} if there
    * is not an appropriate configured target value key in the graph.
    *
-   * This helper is provided so legacy tests don't need to know about details of skyframe keys.
+   * <p>This helper is provided so legacy tests don't need to know about details of skyframe keys.
    */
   @Nullable
   public static ConfiguredTarget getExistingConfiguredTarget(
-      SkyframeExecutor skyframeExecutor,
-      Label label, BuildConfiguration config) {
+      SkyframeExecutor skyframeExecutor, Label label, BuildConfiguration config)
+      throws InterruptedException {
     ConfiguredTargetValue value = getExistingConfiguredTargetValue(skyframeExecutor, label, config);
     if (value == null) {
       return null;
@@ -141,11 +141,11 @@ public class SkyframeExecutorTestUtils {
    * Returns the target for an existing target value, or {@code null} if there is not an appropriate
    * target value key in the graph.
    *
-   * This helper is provided so legacy tests don't need to know about details of skyframe keys.
+   * <p>This helper is provided so legacy tests don't need to know about details of skyframe keys.
    */
   @Nullable
-  public static Target getExistingTarget(SkyframeExecutor skyframeExecutor,
-      Label label) {
+  public static Target getExistingTarget(SkyframeExecutor skyframeExecutor, Label label)
+      throws InterruptedException {
     PackageValue value = (PackageValue) getExistingValue(skyframeExecutor,
         PackageValue.key(label.getPackageIdentifier()));
     if (value == null) {
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 1a70c2e70a..5a6ca8313a 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -102,6 +102,10 @@ public class MemoizingEvaluatorTest {
     tester.initialize();
   }
 
+  protected RecordingDifferencer getRecordingDifferencer() {
+    return new SequencedRecordingDifferencer();
+  }
+
   protected MemoizingEvaluator getMemoizingEvaluator(
       Map<SkyFunctionName, ? extends SkyFunction> functions,
       Differencer differencer,
@@ -126,6 +130,10 @@ public class MemoizingEvaluatorTest {
     return true;
   }
 
+  protected boolean preciseEvaluationStatusStored() {
+    return true;
+  }
+
   private void initializeReporter() {
     eventCollector = new EventCollector();
     reporter = new Reporter(new EventBus(), eventCollector);
@@ -749,7 +757,9 @@ public class MemoizingEvaluatorTest {
     tester.getOrCreate(leaf, /*markAsModified=*/true);
     tester.invalidate();
     tester.eval(/*keepGoing=*/true, top);
-    assertThat(tester.progressReceiver.evaluated).containsExactly(leaf, top);
+    if (preciseEvaluationStatusStored()) {
+      assertThat(tester.progressReceiver.evaluated).containsExactly(leaf, top);
+    }
   }
 
   @Test
@@ -1488,6 +1498,51 @@ public class MemoizingEvaluatorTest {
     assertThat(maxValue[0]).isEqualTo(5);
   }
 
+  @Test
+  public void nodeIsChangedWithoutBeingEvaluated() throws Exception {
+    SkyKey buildFile = GraphTester.skyKey("buildfile");
+    SkyKey top = GraphTester.skyKey("top");
+    SkyKey dep = GraphTester.skyKey("dep");
+    tester.set(buildFile, new StringValue("depend on dep"));
+    StringValue depVal = new StringValue("this is dep");
+    tester.set(dep, depVal);
+    tester
+        .getOrCreate(top)
+        .setBuilder(
+            new SkyFunction() {
+              @Nullable
+              @Override
+              public SkyValue compute(SkyKey skyKey, Environment env)
+                  throws SkyFunctionException, InterruptedException {
+                StringValue val = (StringValue) env.getValue(buildFile);
+                if (env.valuesMissing()) {
+                  return null;
+                }
+                if (val.getValue().equals("depend on dep")) {
+                  StringValue result = (StringValue) env.getValue(dep);
+                  return env.valuesMissing() ? null : result;
+                }
+                throw new GenericFunctionException(
+                    new SomeErrorException("bork"), Transience.PERSISTENT);
+              }
+
+              @Nullable
+              @Override
+              public String extractTag(SkyKey skyKey) {
+                return null;
+              }
+            });
+    assertThat(tester.evalAndGet("top")).isEqualTo(depVal);
+    StringValue newDepVal = new StringValue("this is new dep");
+    tester.set(dep, newDepVal);
+    tester.set(buildFile, new StringValue("don't depend on dep"));
+    tester.invalidate();
+    tester.eval(/*keepGoing=*/ false, top);
+    tester.set(buildFile, new StringValue("depend on dep"));
+    tester.invalidate();
+    assertThat(tester.evalAndGet("top")).isEqualTo(newDepVal);
+  }
+
   /**
    * Regression test: error on clearMaybeDirtyValue. We do an evaluation of topKey, which registers
    * dependencies on midKey and errorKey. midKey enqueues slowKey, and waits. errorKey throws an
@@ -2819,8 +2874,10 @@ public class MemoizingEvaluatorTest {
     tester.invalidate();
     topValue = (StringValue) tester.evalAndGet("top");
     assertThat(topValue.getValue()).isEqualTo("joyce drank whiskey");
-    assertThat(tester.getDirtyKeys()).containsExactly(buildFile, top);
-    assertThat(tester.getDeletedKeys()).isEmpty();
+    if (preciseEvaluationStatusStored()) {
+      assertThat(tester.getDirtyKeys()).containsExactly(buildFile, top);
+      assertThat(tester.getDeletedKeys()).isEmpty();
+    }
   }
 
   @Test
@@ -2842,14 +2899,18 @@ public class MemoizingEvaluatorTest {
     tester.invalidate();
     topValue = (StringValue) tester.evalAndGet("top");
     assertThat(topValue.getValue()).isEqualTo("ignore");
-    assertThat(tester.getDirtyKeys()).containsExactly(leaf);
-    assertThat(tester.getDeletedKeys()).isEmpty();
+    if (preciseEvaluationStatusStored()) {
+      assertThat(tester.getDirtyKeys()).containsExactly(leaf);
+      assertThat(tester.getDeletedKeys()).isEmpty();
+    }
     tester.set(leaf, new StringValue("smushy"));
     tester.invalidate();
     topValue = (StringValue) tester.evalAndGet("top");
     assertThat(topValue.getValue()).isEqualTo("ignore");
-    assertThat(tester.getDirtyKeys()).containsExactly(leaf);
-    assertThat(tester.getDeletedKeys()).isEmpty();
+    if (preciseEvaluationStatusStored()) {
+      assertThat(tester.getDirtyKeys()).containsExactly(leaf);
+      assertThat(tester.getDeletedKeys()).isEmpty();
+    }
   }
 
   private static final SkyFunction INTERRUPT_BUILDER = new SkyFunction() {
@@ -4275,12 +4336,14 @@ public class MemoizingEvaluatorTest {
     // Then when top is evaluated, its value is as expected,
     tester.invalidate();
     assertThat(tester.evalAndGet(/*keepGoing=*/ true, top)).isEqualTo(topValue);
-    // And there is no value for mid in the graph,
-    assertThat(tester.driver.getExistingValueForTesting(mid)).isNull();
-    assertThat(tester.driver.getExistingErrorForTesting(mid)).isNull();
-    // Or for leaf.
-    assertThat(tester.driver.getExistingValueForTesting(leaf)).isNull();
-    assertThat(tester.driver.getExistingErrorForTesting(leaf)).isNull();
+    if (preciseEvaluationStatusStored()) {
+      // And there is no value for mid in the graph,
+      assertThat(tester.driver.getExistingValueForTesting(mid)).isNull();
+      assertThat(tester.driver.getExistingErrorForTesting(mid)).isNull();
+      // Or for leaf.
+      assertThat(tester.driver.getExistingValueForTesting(leaf)).isNull();
+      assertThat(tester.driver.getExistingErrorForTesting(leaf)).isNull();
+    }
 
     // When top is changed to depend directly on leaf,
     tester
@@ -4291,9 +4354,11 @@ public class MemoizingEvaluatorTest {
     // Then when top is evaluated, its value is as expected,
     tester.invalidate();
     assertThat(tester.evalAndGet(/*keepGoing=*/ true, top)).isEqualTo(leafValue);
-    // and there is no value for mid in the graph,
-    assertThat(tester.driver.getExistingValueForTesting(mid)).isNull();
-    assertThat(tester.driver.getExistingErrorForTesting(mid)).isNull();
+    if (preciseEvaluationStatusStored()) {
+      // and there is no value for mid in the graph,
+      assertThat(tester.driver.getExistingValueForTesting(mid)).isNull();
+      assertThat(tester.driver.getExistingErrorForTesting(mid)).isNull();
+    }
   }
 
   // Tests that a removed and then reinstated node doesn't try to invalidate its erstwhile parent
@@ -4346,10 +4411,11 @@ public class MemoizingEvaluatorTest {
     // Then when top is evaluated, its value is as expected,
     tester.invalidate();
     assertThat(tester.evalAndGet(/*keepGoing=*/ true, top)).isEqualTo(topValue);
-    // And there is no value for leaf in the graph.
-    assertThat(tester.driver.getExistingValueForTesting(leaf)).isNull();
-    assertThat(tester.driver.getExistingErrorForTesting(leaf)).isNull();
-
+    if (preciseEvaluationStatusStored()) {
+      // And there is no value for leaf in the graph.
+      assertThat(tester.driver.getExistingValueForTesting(leaf)).isNull();
+      assertThat(tester.driver.getExistingErrorForTesting(leaf)).isNull();
+    }
     // When leaf is evaluated, so that it is present in the graph again,
     assertThat(tester.evalAndGet(/*keepGoing=*/ true, leaf)).isEqualTo(leafValue);
     // And top is changed to depend on leaf again,
@@ -4437,12 +4503,13 @@ public class MemoizingEvaluatorTest {
 
   /** A graph tester that is specific to the memoizing evaluator, with some convenience methods. */
   protected class MemoizingEvaluatorTester extends GraphTester {
-    private RecordingDifferencer differencer = new RecordingDifferencer();
+    private RecordingDifferencer differencer;
     private MemoizingEvaluator evaluator;
     private BuildDriver driver;
     private TrackingProgressReceiver progressReceiver = new TrackingProgressReceiver();
 
     public void initialize() {
+      this.differencer = getRecordingDifferencer();
       this.evaluator =
           getMemoizingEvaluator(getSkyFunctionMap(), differencer, progressReceiver);
       this.driver = getBuildDriver(evaluator);
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 2053ce4503..af09fcd1ea 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -1856,9 +1856,11 @@ public class ParallelEvaluatorTest {
               }
             });
 
-    MemoizingEvaluator aug = new InMemoryMemoizingEvaluator(
-        ImmutableMap.of(GraphTester.NODE_TYPE, tester.getFunction()), new RecordingDifferencer(),
-        progressReceiver);
+    MemoizingEvaluator aug =
+        new InMemoryMemoizingEvaluator(
+            ImmutableMap.of(GraphTester.NODE_TYPE, tester.getFunction()),
+            new SequencedRecordingDifferencer(),
+            progressReceiver);
     SequentialBuildDriver driver = new SequentialBuildDriver(aug);
 
     tester.getOrCreate("top1").setComputedValue(CONCATENATE)