diff --git a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
index 95a7ca8..b20f7e8 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -57,8 +57,8 @@
    * <li>Done
    * </ol>
    *
-   * <p>The "just created" state is there to allow the {@link EvaluableGraph#createIfAbsent} and
-   * {@link NodeEntry#addReverseDepAndCheckIfDone} methods to be separate. All callers have to
+   * <p>The "just created" state is there to allow the {@link EvaluableGraph#createIfAbsentBatch}
+   * and {@link NodeEntry#addReverseDepAndCheckIfDone} methods to be separate. All callers have to
    * call both methods in that order if they want to create a node. The second method calls
    * {@link #startEvaluating}, which transitions the current node to the "evaluating" state and
    * returns true only the first time it was called. A caller that gets "true" back from that call
@@ -68,7 +68,7 @@
    * node that is never actually built (for instance, a dirty node that is verified as clean) is
    * in the "evaluating" state until it is done.
    */
-  private boolean evaluating = false;
+  boolean evaluating = false;
 
   /**
    * The state of a dirty node. A node is marked dirty in the BuildingState constructor, and goes
@@ -358,20 +358,27 @@
     return lastBuildDirectDeps.get(dirtyDirectDepIndex++);
   }
 
-  Collection<SkyKey> getAllRemainingDirtyDirectDeps() {
+  /**
+   * Returns the remaining direct deps that have not been checked. If {@code preservePosition} is
+   * true, this method is non-mutating. If {@code preservePosition} is false, the caller must
+   * process the returned set, and so subsequent calls to this method will return the empty set.
+   */
+  Set<SkyKey> getAllRemainingDirtyDirectDeps(boolean preservePosition) {
     Preconditions.checkState(isDirty(), this);
-    ImmutableList.Builder<SkyKey> result = ImmutableList.builder();
-    for (; dirtyDirectDepIndex < lastBuildDirectDeps.listSize(); dirtyDirectDepIndex++) {
-      result.addAll(lastBuildDirectDeps.get(dirtyDirectDepIndex));
+    ImmutableSet.Builder<SkyKey> result = ImmutableSet.builder();
+
+    for (int ind = dirtyDirectDepIndex; ind < lastBuildDirectDeps.listSize(); ind++) {
+      result.addAll(lastBuildDirectDeps.get(ind));
+    }
+    if (!preservePosition) {
+      dirtyDirectDepIndex = lastBuildDirectDeps.listSize();
     }
     return result.build();
   }
 
-  protected Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps() {
+  protected void markRebuilding() {
     Preconditions.checkState(dirtyState == DirtyState.NEEDS_REBUILDING, this);
-    Collection<SkyKey> result = getAllRemainingDirtyDirectDeps();
     dirtyState = DirtyState.REBUILDING;
-    return result;
   }
 
   void addDirectDeps(GroupedListHelper<SkyKey> depsThisRun) {
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 4215f0e..8e9ddb6 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -116,8 +116,13 @@
   }
 
   @Override
-  public Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps() {
-    return getDelegate().markRebuildingAndGetAllRemainingDirtyDirectDeps();
+  public Set<SkyKey> getAllRemainingDirtyDirectDeps() {
+    return getDelegate().getAllRemainingDirtyDirectDeps();
+  }
+
+  @Override
+  public void markRebuilding() {
+    getDelegate().markRebuilding();
   }
 
   @Override
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 56bcd05..414525e 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -417,15 +417,30 @@
     if (!isDirty()) {
       return Iterables.concat(getTemporaryDirectDeps());
     } else {
-      return Iterables.concat(
-          Iterables.concat(getTemporaryDirectDeps()),
-          buildingState.getAllRemainingDirtyDirectDeps());
+      // There may be duplicates here. Make sure everything is unique.
+      ImmutableSet.Builder<SkyKey> result = ImmutableSet.builder();
+      for (Iterable<SkyKey> group : getTemporaryDirectDeps()) {
+        result.addAll(group);
+      }
+      result.addAll(buildingState.getAllRemainingDirtyDirectDeps(/*preservePosition=*/ false));
+      return result.build();
     }
   }
 
   @Override
-  public synchronized Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps() {
-    return buildingState.markRebuildingAndGetAllRemainingDirtyDirectDeps();
+  public synchronized Set<SkyKey> getAllRemainingDirtyDirectDeps() {
+    if (isDirty()) {
+      Preconditions.checkState(buildingState.getDirtyState() == DirtyState.REBUILDING, this);
+      return buildingState.getAllRemainingDirtyDirectDeps(/*preservePosition=*/ true);
+    } else {
+      Preconditions.checkState(buildingState.evaluating, this);
+      return ImmutableSet.of();
+    }
+  }
+
+  @Override
+  public synchronized void markRebuilding() {
+    buildingState.markRebuilding();
   }
 
   @Override
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 924771a..0fafa86 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -159,9 +159,9 @@
   /**
    * Similar to {@link #addReverseDepAndCheckIfDone}, except that {@param reverseDep} must already
    * be a reverse dep of this entry. Should be used when reverseDep has been marked dirty and is
-   * checking its dependencies for changes. The caller must treat the return value just as they
-   * would the return value of {@link #addReverseDepAndCheckIfDone} by scheduling this node for
-   * evaluation if needed.
+   * checking its dependencies for changes or is rebuilding. The caller must treat the return value
+   * just as they would the return value of {@link #addReverseDepAndCheckIfDone} by scheduling this
+   * node for evaluation if needed.
    */
   @ThreadSafe
   DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep);
@@ -259,7 +259,8 @@
    * created, this is just any elements that were added using {@link #addTemporaryDirectDeps} (so it
    * is the same as {@link #getTemporaryDirectDeps}). If this node is marked dirty, this includes
    * all the elements that would have been returned by successive calls to
-   * {@link #getNextDirtyDirectDeps}.
+   * {@link #getNextDirtyDirectDeps} (or, equivalently, one call to
+   * {@link #getAllRemainingDirtyDirectDeps}).
    *
    * <p>This method should only be called when this node is about to be deleted after an aborted
    * evaluation. After such an evaluation, any nodes that did not finish evaluating are deleted, as
@@ -274,15 +275,28 @@
   Iterable<SkyKey> getAllDirectDepsForIncompleteNode();
 
   /**
-   * Notifies a node that it is about to be rebuilt. This method can only be called if the node
-   * {@link DirtyState#NEEDS_REBUILDING}. It returns the remaining deps of the node that had not
-   * yet been checked: all the keys that would be returned by successive calls to
-   * {@link #getNextDirtyDirectDeps}. It is the caller's responsibility to (uninterruptibly) remove
-   * the reverse deps those deps have on this node in order to keep the graph consistent. After this
-   * call, this node no longer has a dep on the nodes whose keys were returned by this call and
-   * is ready to be rebuilt (it will be in {@link DirtyState#REBUILDING}).
+   * If an entry {@link #isDirty}, returns all direct deps that were present last build, but have
+   * not yet been verified to be present during the current build. Implementations may lazily remove
+   * these deps, since in many cases they will be added back during this build, even though the node
+   * may have a changed value. However, any elements of this returned set that have not been added
+   * back by the end of evaluation <i>must</i> be removed from any done nodes, in order to preserve
+   * graph consistency.
+   *
+   * <p>Returns the empty set if an entry is not dirty. In either case, the entry must already have
+   * started evaluation.
+   *
+   * <p>This method does not mutate the entry. In particular, multiple calls to this method will
+   * always produce the same result until the entry finishes evaluation. Contrast with
+   * {@link #getAllDirectDepsForIncompleteNode}.
    */
-  Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps();
+  Set<SkyKey> getAllRemainingDirtyDirectDeps();
+
+  /**
+   * Notifies a node that it is about to be rebuilt. This method can only be called if the node
+   * {@link DirtyState#NEEDS_REBUILDING}. After this call, this node is ready to be rebuilt (it will
+   * be in {@link DirtyState#REBUILDING}).
+   */
+  void markRebuilding();
 
   /**
    * Returns the {@link GroupedList} of direct dependencies. This may only be called while the node
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 74ba24c..926a4c6 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -232,6 +232,7 @@
     private boolean building = true;
     private SkyKey depErrorKey = null;
     private final SkyKey skyKey;
+    private final Set<SkyKey> oldDeps;
     private SkyValue value = null;
     private ErrorInfo errorInfo = null;
     private final Map<SkyKey, ValueWithMetadata> bubbleErrorInfo;
@@ -270,16 +271,18 @@
         };
 
     private SkyFunctionEnvironment(
-        SkyKey skyKey, GroupedList<SkyKey> directDeps, ValueVisitor visitor) {
-      this(skyKey, directDeps, null, visitor);
+        SkyKey skyKey, GroupedList<SkyKey> directDeps, Set<SkyKey> oldDeps, ValueVisitor visitor) {
+      this(skyKey, directDeps, null, oldDeps, visitor);
     }
 
     private SkyFunctionEnvironment(
         SkyKey skyKey,
         GroupedList<SkyKey> directDeps,
         @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo,
+        Set<SkyKey> oldDeps,
         ValueVisitor visitor) {
       this.skyKey = skyKey;
+      this.oldDeps = oldDeps;
       this.directDeps = Collections.unmodifiableMap(
           batchPrefetch(directDeps, /*assertDone=*/bubbleErrorInfo == null, skyKey));
       this.bubbleErrorInfo = bubbleErrorInfo;
@@ -387,8 +390,13 @@
           "%s %s %s", skyKey, this.errorInfo, errorInfo);
 
       if (isDirectlyTransient) {
-        DependencyState triState =
-            graph.get(ErrorTransienceValue.KEY).addReverseDepAndCheckIfDone(skyKey);
+        NodeEntry errorTransienceNode = graph.get(ErrorTransienceValue.KEY);
+        DependencyState triState;
+        if (oldDeps.contains(ErrorTransienceValue.KEY)) {
+          triState = errorTransienceNode.checkIfDoneForDirtyReverseDep(skyKey);
+        } else {
+          triState = errorTransienceNode.addReverseDepAndCheckIfDone(skyKey);
+        }
         Preconditions.checkState(triState == DependencyState.DONE,
             "%s %s %s", skyKey, triState, errorInfo);
 
@@ -610,6 +618,14 @@
         Preconditions.checkState(enqueueParents, "%s %s", skyKey, primaryEntry);
         valueWithMetadata = ValueWithMetadata.normal(value, errorInfo, events);
       }
+      if (!oldDeps.isEmpty()) {
+        // Remove the rdep on this entry for each of its old deps that is no longer a direct dep.
+        Set<SkyKey> depsToRemove =
+            Sets.difference(oldDeps, primaryEntry.getTemporaryDirectDeps().toSet());
+        for (NodeEntry oldDepEntry : graph.getBatch(depsToRemove).values()) {
+          oldDepEntry.removeReverseDep(skyKey);
+        }
+      }
       // If this entry is dirty, setValue may not actually change it, if it determines that
       // the data being written now is the same as the data already present in the entry.
       // We could consider using max(childVersions) here instead of graphVersion. When full
@@ -758,29 +774,11 @@
   }
 
   /**
-   * If the entry is dirty and not already rebuilding, puts it in a state that it can rebuild, and
-   * removes it as a reverse dep from any dirty direct deps it had yet to check.
+   * If the entry is dirty and not already rebuilding, puts it in a state so that it can rebuild.
    */
-  private void maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(SkyKey key, NodeEntry entry) {
+  private static void maybeMarkRebuilding(NodeEntry entry) {
     if (entry.isDirty() && entry.getDirtyState() != DirtyState.REBUILDING) {
-      Collection<SkyKey> depsToRemove = entry.markRebuildingAndGetAllRemainingDirtyDirectDeps();
-      Map<SkyKey, NodeEntry> depsToClearFrom = graph.getBatch(depsToRemove);
-      if (depsToClearFrom.size() != depsToRemove.size()) {
-        throw new IllegalStateException(
-            "At least one dep of a dirty node wasn't present in the graph: "
-                + Sets.difference(ImmutableSet.copyOf(depsToRemove), depsToClearFrom.keySet())
-                + " for "
-                + key
-                + " with entry "
-                + entry
-                + ". Sizes: "
-                + depsToRemove.size()
-                + ", "
-                + depsToClearFrom.size());
-      }
-      for (NodeEntry depEntry : depsToClearFrom.values()) {
-        depEntry.removeReverseDep(key);
-      }
+      entry.markRebuilding();
     }
   }
 
@@ -802,11 +800,15 @@
       this.skyKey = skyKey;
     }
 
-    private void enqueueChild(SkyKey skyKey, NodeEntry entry, SkyKey child, NodeEntry childEntry,
-        boolean dirtyParent) {
+    private void enqueueChild(
+        SkyKey skyKey,
+        NodeEntry entry,
+        SkyKey child,
+        NodeEntry childEntry,
+        boolean depAlreadyExists) {
       Preconditions.checkState(!entry.isDone(), "%s %s", skyKey, entry);
       DependencyState dependencyState =
-          dirtyParent
+          depAlreadyExists
               ? childEntry.checkIfDoneForDirtyReverseDep(skyKey)
               : childEntry.addReverseDepAndCheckIfDone(skyKey);
       switch (dependencyState) {
@@ -912,7 +914,7 @@
               : graph.createIfAbsentBatch(directDepsToCheck).entrySet()) {
             SkyKey directDep = e.getKey();
             NodeEntry directDepEntry = e.getValue();
-            enqueueChild(skyKey, state, directDep, directDepEntry, /*dirtyParent=*/ true);
+            enqueueChild(skyKey, state, directDep, directDepEntry, /*depAlreadyExists=*/ true);
           }
           return DirtyOutcome.ALREADY_PROCESSED;
         case VERIFIED_CLEAN:
@@ -933,7 +935,7 @@
           signalValuesAndEnqueueIfReady(visitor, reverseDeps, state.getVersion());
           return DirtyOutcome.ALREADY_PROCESSED;
         case NEEDS_REBUILDING:
-          maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(skyKey, state);
+          maybeMarkRebuilding(state);
           // Fall through to REBUILDING case.
         case REBUILDING:
           return DirtyOutcome.NEEDS_EVALUATION;
@@ -950,9 +952,9 @@
         return;
       }
 
-      // Get the corresponding SkyFunction and call it on this value.
+      Set<SkyKey> oldDeps = state.getAllRemainingDirtyDirectDeps();
       SkyFunctionEnvironment env =
-          new SkyFunctionEnvironment(skyKey, state.getTemporaryDirectDeps(), visitor);
+          new SkyFunctionEnvironment(skyKey, state.getTemporaryDirectDeps(), oldDeps, visitor);
       SkyFunctionName functionName = skyKey.functionName();
       SkyFunction factory = skyFunctions.get(functionName);
       Preconditions.checkState(factory != null,
@@ -993,7 +995,7 @@
           }
           ErrorInfo errorInfo = ErrorInfo.fromException(reifiedBuilderException,
               isTransitivelyTransient);
-          registerNewlyDiscoveredDepsForDoneEntry(skyKey, state, newlyRequestedDeps, env);
+          registerNewlyDiscoveredDepsForDoneEntry(skyKey, state, newlyRequestedDeps, oldDeps, env);
           env.setError(errorInfo, /*isDirectlyTransient=*/ reifiedBuilderException.isTransient());
           env.commit(/*enqueueParents=*/keepGoing);
           if (!shouldFailFast) {
@@ -1032,8 +1034,8 @@
             + "but requested dependencies that weren't computed yet (one of %s), ValueEntry: %s",
             skyKey, newDirectDeps, state);
         env.setValue(value);
-        registerNewlyDiscoveredDepsForDoneEntry(skyKey, state,
-            graph.getBatch(env.newlyRequestedDeps), env);
+        registerNewlyDiscoveredDepsForDoneEntry(
+            skyKey, state, graph.getBatch(env.newlyRequestedDeps), oldDeps, env);
         env.commit(/*enqueueParents=*/true);
         return;
       }
@@ -1102,7 +1104,12 @@
       for (Map.Entry<SkyKey, NodeEntry> e : graph.createIfAbsentBatch(newDirectDeps).entrySet()) {
         SkyKey newDirectDep = e.getKey();
         NodeEntry newDirectDepEntry = e.getValue();
-        enqueueChild(skyKey, state, newDirectDep, newDirectDepEntry, /*dirtyParent=*/ false);
+        enqueueChild(
+            skyKey,
+            state,
+            newDirectDep,
+            newDirectDepEntry,
+            /*depAlreadyExists=*/ oldDeps.contains(newDirectDep));
       }
       // It is critical that there is no code below this point.
     }
@@ -1179,7 +1186,10 @@
    * enforce that condition.
    */
   private void registerNewlyDiscoveredDepsForDoneEntry(
-      SkyKey skyKey, NodeEntry entry, Map<SkyKey, NodeEntry> newlyRequestedDepMap,
+      SkyKey skyKey,
+      NodeEntry entry,
+      Map<SkyKey, NodeEntry> newlyRequestedDepMap,
+      Set<SkyKey> oldDeps,
       SkyFunctionEnvironment env) {
     Set<SkyKey> unfinishedDeps = new HashSet<>();
    for (SkyKey dep : env.newlyRequestedDeps) {
@@ -1194,7 +1204,10 @@
       // null entry, then it would have been added to unfinishedDeps and then removed from
       // env.newlyRequestedDeps just above this loop.
       NodeEntry depEntry = Preconditions.checkNotNull(newlyRequestedDepMap.get(newDep), newDep);
-      DependencyState triState = depEntry.addReverseDepAndCheckIfDone(skyKey);
+      DependencyState triState =
+          oldDeps.contains(newDep)
+              ? depEntry.checkIfDoneForDirtyReverseDep(skyKey)
+              : depEntry.addReverseDepAndCheckIfDone(skyKey);
       Preconditions.checkState(DependencyState.DONE == triState,
           "new dep %s was not already done for %s. ValueEntry: %s. DepValueEntry: %s",
           newDep, skyKey, entry, depEntry);
@@ -1489,7 +1502,7 @@
             parentEntry.signalDep();
             // Fall through to NEEDS_REBUILDING, since state is now NEEDS_REBUILDING.
           case NEEDS_REBUILDING:
-            maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(parent, parentEntry);
+            maybeMarkRebuilding(parentEntry);
             // Fall through to REBUILDING.
           case REBUILDING:
             break;
@@ -1498,7 +1511,12 @@
         }
       }
       SkyFunctionEnvironment env =
-          new SkyFunctionEnvironment(parent, new GroupedList<SkyKey>(), bubbleErrorInfo, visitor);
+          new SkyFunctionEnvironment(
+              parent,
+              new GroupedList<SkyKey>(),
+              bubbleErrorInfo,
+              ImmutableSet.<SkyKey>of(),
+              visitor);
       externalInterrupt = externalInterrupt || Thread.currentThread().isInterrupted();
       try {
         // This build is only to check if the parent node can give us a better error. We don't
@@ -1714,14 +1732,16 @@
           removeIncompleteChildrenForCycle(
               key, entry, Iterables.concat(entry.getTemporaryDirectDeps()));
         }
-        maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry);
+        maybeMarkRebuilding(entry);
         GroupedList<SkyKey> directDeps = entry.getTemporaryDirectDeps();
         // Find out which children have errors. Similar logic to that in Evaluate#run().
         List<ErrorInfo> errorDeps = getChildrenErrorsForCycle(Iterables.concat(directDeps));
         Preconditions.checkState(!errorDeps.isEmpty(),
             "Value %s was not successfully evaluated, but had no child errors. ValueEntry: %s", key,
             entry);
-        SkyFunctionEnvironment env = new SkyFunctionEnvironment(key, directDeps, visitor);
+        SkyFunctionEnvironment env =
+            new SkyFunctionEnvironment(
+                key, directDeps, entry.getAllRemainingDirtyDirectDeps(), visitor);
         env.setError(ErrorInfo.fromChildErrors(key, errorDeps), /*isDirectlyTransient=*/false);
         env.commit(/*enqueueParents=*/false);
       } else {
@@ -1750,7 +1770,7 @@
           // cycles, and this is the only missing one). Thus, it will not be removed below in
           // removeDescendantsOfCycleValue, so it is safe here to signal that it is done.
           entry.signalDep();
-          maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry);
+          maybeMarkRebuilding(entry);
         }
         if (keepGoing) {
           // Any children of this node that we haven't already visited are not worth visiting,
@@ -1763,8 +1783,12 @@
 
 
           SkyFunctionEnvironment env =
-              new SkyFunctionEnvironment(key, entry.getTemporaryDirectDeps(),
-                  ImmutableMap.of(cycleChild, dummyValue), visitor);
+              new SkyFunctionEnvironment(
+                  key,
+                  entry.getTemporaryDirectDeps(),
+                  ImmutableMap.of(cycleChild, dummyValue),
+                  entry.getAllRemainingDirtyDirectDeps(),
+                  visitor);
 
           // Construct error info for this node. Get errors from children, which are all done
           // except possibly for the cycleChild.
@@ -1891,7 +1915,7 @@
       // and was built.
       entry.signalDep();
     }
-    maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry);
+    maybeMarkRebuilding(entry);
     Preconditions.checkState(entry.isReady(), "%s %s %s", key, cycleChild, entry);
     Iterator<SkyKey> it = toVisit.iterator();
     while (it.hasNext()) {
@@ -1984,13 +2008,7 @@
         // we want to avoid, because it indicates confusion of input values and derived values.
         Preconditions.checkState(
             prevEntry.noDepsLastBuild(), "existing entry for %s has deps: %s", key, prevEntry);
-        // Put the node into a "rebuilding" state and verify that there were no dirty deps
-        // remaining.
-        Preconditions.checkState(
-            prevEntry.markRebuildingAndGetAllRemainingDirtyDirectDeps().isEmpty(),
-            "%s %s",
-            key,
-            prevEntry);
+        prevEntry.markRebuilding();
       }
       prevEntry.setValue(value, version);
       // Now that this key's injected value is set, it is no longer dirty.
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
index c10277f..26cb281 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
@@ -170,7 +170,7 @@
     // Mark the node as dirty again and check that the reverse deps have been preserved.
     sameEntry.markDirty(true);
     startEvaluation(sameEntry);
-    sameEntry.markRebuildingAndGetAllRemainingDirtyDirectDeps();
+    sameEntry.markRebuilding();
     sameEntry.setValue(new StringValue("foo2"), getNextVersion(startingVersion));
     assertEquals(new StringValue("foo2"), graph.get(key).getValue());
     assertEquals(numKeys + 1, Iterables.size(graph.get(key).getReverseDeps()));
@@ -288,7 +288,7 @@
               entry.markDirty(true);
               // Make some changes, like adding a dep and rdep.
               entry.addReverseDepAndCheckIfDone(key("rdep"));
-              entry.markRebuildingAndGetAllRemainingDirtyDirectDeps();
+              entry.markRebuilding();
               addTemporaryDirectDep(entry, key("dep"));
               entry.signalDep();
               // Move node from dirty back to done.
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index 92bed7b..080c546 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -199,7 +199,7 @@
     entry.signalDep();
     assertThatNodeEntry(entry).hasTemporaryDirectDepsThat().containsExactly(dep);
     assertTrue(entry.isReady());
-    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
+    entry.markRebuilding();
     assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
         /*graphVersion=*/1L)).containsExactly(parent);
   }
@@ -224,7 +224,7 @@
     assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
     assertTrue(entry.isReady());
     assertThat(entry.getTemporaryDirectDeps()).isEmpty();
-    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).containsExactly(dep);
+    entry.markRebuilding();
     assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
         /*graphVersion=*/1L)).containsExactly(parent);
     assertEquals(IntVersion.of(1L), entry.getVersion());
@@ -415,7 +415,7 @@
     entry.signalDep(IntVersion.of(1L));
     assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
     assertThatNodeEntry(entry).hasTemporaryDirectDepsThat().containsExactly(dep);
-    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
+    entry.markRebuilding();
     setValue(entry, new IntegerValue(5), /*errorInfo=*/null, /*graphVersion=*/1L);
     assertTrue(entry.isDone());
     assertEquals(IntVersion.of(0L), entry.getVersion());
@@ -447,7 +447,7 @@
     ReifiedSkyFunctionException exception = new ReifiedSkyFunctionException(
         new GenericFunctionException(new SomeErrorException("oops"), Transience.PERSISTENT),
         key("cause"));
-    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
+    entry.markRebuilding();
     setValue(entry, new IntegerValue(5), ErrorInfo.fromException(exception, false),
         /*graphVersion=*/1L);
     assertTrue(entry.isDone());
@@ -481,8 +481,7 @@
     entry.signalDep(IntVersion.of(1L));
     assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
     assertThatNodeEntry(entry).hasTemporaryDirectDepsThat().containsExactly(dep);
-    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps())
-        .containsExactly(dep1InGroup, dep2InGroup);
+    entry.markRebuilding();
     addTemporaryDirectDeps(entry, dep2InGroup, dep1InGroup);
     assertFalse(entry.signalDep());
     assertTrue(entry.signalDep());
@@ -512,7 +511,7 @@
     entry.signalDep(IntVersion.of(1L));
     assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
     assertThatNodeEntry(entry).hasTemporaryDirectDepsThat().containsExactly(dep);
-    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
+    entry.markRebuilding();
     setValue(entry, /*value=*/null, errorInfo, /*graphVersion=*/1L);
     assertTrue(entry.isDone());
     // ErrorInfo is treated as a NotComparableSkyValue, so it is not pruned.
@@ -589,7 +588,7 @@
     assertTrue(entry.signalDep(IntVersion.of(1L)));
     assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
     assertThatNodeEntry(entry).hasTemporaryDirectDepsThat().containsExactly(dep);
-    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
+    entry.markRebuilding();
     addTemporaryDirectDep(entry, key("dep2"));
     assertTrue(entry.signalDep(IntVersion.of(1L)));
     setValue(entry, new IntegerValue(5), /*errorInfo=*/null, /*graphVersion=*/1L);
@@ -633,7 +632,7 @@
     SkyKey newParent = key("new parent");
     entry.addReverseDepAndCheckIfDone(newParent);
     assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
-    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
+    entry.markRebuilding();
     assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
         /*graphVersion=*/1L)).containsExactly(newParent);
   }
@@ -659,8 +658,7 @@
     SkyKey newChild = key("newchild");
     addTemporaryDirectDep(clone2, newChild);
     clone2.signalDep();
-    assertThat(clone2.markRebuildingAndGetAllRemainingDirtyDirectDeps())
-        .containsExactly(originalChild);
+    clone2.markRebuilding();
     clone2.setValue(updatedValue, version.next());
 
     assertThat(entry.getVersion()).isEqualTo(version);
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 c18f076..c4f0047 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -1936,7 +1936,11 @@
                 new StringValue("second"),
                 ImmutableList.<SkyKey>of()));
     // And mid is independently marked as modified,
-    tester.getOrCreate(midKey, /*markAsModified=*/ true);
+    tester
+        .getOrCreate(midKey, /*markAsModified=*/ true)
+        .removeDependency(changedKey)
+        .setComputedValue(null)
+        .setConstantValue(new StringValue("mid"));
     tester.invalidate();
     SkyKey newTopKey = GraphTester.skyKey("newTop");
     // And changed will start rebuilding independently of midKey, because it's requested directly by
@@ -4127,6 +4131,16 @@
     assertThat(tester.evalAndGet(/*keepGoing=*/ true, inactiveKey)).isEqualTo(val);
   }
 
+  @Test
+  public void errorChanged() throws Exception {
+    SkyKey error = GraphTester.skyKey("error");
+    tester.getOrCreate(error).setHasTransientError(true);
+    assertThatErrorInfo(tester.evalAndGetError(error)).hasExceptionThat().isNotNull();
+    tester.getOrCreate(error, /*markAsModified=*/ true);
+    tester.invalidate();
+    assertThatErrorInfo(tester.evalAndGetError(error)).hasExceptionThat().isNotNull();
+  }
+
   /** A graph tester that is specific to the memoizing evaluator, with some convenience methods. */
   protected class MemoizingEvaluatorTester extends GraphTester {
     private RecordingDifferencer differencer = new RecordingDifferencer();
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingGraph.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingGraph.java
index 7e76b8f..bf3ab1b 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingGraph.java
@@ -18,6 +18,7 @@
 import com.google.common.collect.Maps;
 import com.google.common.collect.Maps.EntryTransformer;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.util.GroupedList;
 
 import java.util.Map;
 import java.util.Set;
@@ -115,6 +116,7 @@
     CREATE_IF_ABSENT,
     ADD_REVERSE_DEP,
     REMOVE_REVERSE_DEP,
+    GET_TEMPORARY_DIRECT_DEPS,
     SIGNAL,
     SET_VALUE,
     MARK_DIRTY,
@@ -204,6 +206,12 @@
     }
 
     @Override
+    public GroupedList<SkyKey> getTemporaryDirectDeps() {
+      graphListener.accept(myKey, EventType.GET_TEMPORARY_DIRECT_DEPS, Order.BEFORE, null);
+      return super.getTemporaryDirectDeps();
+    }
+
+    @Override
     public boolean signalDep(Version childVersion) {
       graphListener.accept(myKey, EventType.SIGNAL, Order.BEFORE, childVersion);
       boolean result = super.signalDep(childVersion);