Don't remove reverse deps until node is known to be changed. This helps avoid mutating the deps of nodes that are still going to be deps after evaluation is finished.

--
MOS_MIGRATED_REVID=103659429

15 files changed, 1010 insertions, 420 deletions

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 547549e07a..41b94ad137 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -73,9 +73,10 @@ public class BuildingState {
 
   /**
    * The state of a dirty node. A node is marked dirty in the BuildingState constructor, and goes
-   * into either the state {@link DirtyState#CHECK_DEPENDENCIES} or {@link DirtyState#REBUILDING},
-   * depending on whether the caller specified that the node was itself changed or not. A non-null
-   * {@code dirtyState} indicates that the node {@link #isDirty} in some way.
+   * into either the state {@link DirtyState#CHECK_DEPENDENCIES} or
+   * {@link DirtyState#NEEDS_REBUILDING}, depending on whether the caller specified that the node
+   * was itself changed or not. A non-null {@code dirtyState} indicates that the node
+   * {@link #isDirty} in some way.
    */
   private DirtyState dirtyState = null;
 
@@ -118,41 +119,41 @@ public class BuildingState {
   // node will be removed by the time evaluation starts, so reverse deps to signal can just be
   // reverse deps in the main ValueEntry object.
   private Object reverseDepsToSignal = ImmutableList.of();
-  private List<SkyKey> reverseDepsToRemove = null;
+  private Object reverseDepsDataToConsolidate = null;
   private boolean reverseDepIsSingleObject = false;
 
   private static final ReverseDepsUtil<BuildingState> REVERSE_DEPS_UTIL =
       new ReverseDepsUtil<BuildingState>() {
-    @Override
-    void setReverseDepsObject(BuildingState container, Object object) {
-      container.reverseDepsToSignal = object;
-    }
-
-    @Override
-    void setSingleReverseDep(BuildingState container, boolean singleObject) {
-      container.reverseDepIsSingleObject = singleObject;
-    }
-
-    @Override
-    void setReverseDepsToRemove(BuildingState container, List<SkyKey> object) {
-      container.reverseDepsToRemove = object;
-    }
-
-    @Override
-    Object getReverseDepsObject(BuildingState container) {
-      return container.reverseDepsToSignal;
-    }
-
-    @Override
-    boolean isSingleReverseDep(BuildingState container) {
-      return container.reverseDepIsSingleObject;
-    }
-
-    @Override
-    List<SkyKey> getReverseDepsToRemove(BuildingState container) {
-      return container.reverseDepsToRemove;
-    }
-  };
+        @Override
+        void setReverseDepsObject(BuildingState container, Object object) {
+          container.reverseDepsToSignal = object;
+        }
+
+        @Override
+        void setSingleReverseDep(BuildingState container, boolean singleObject) {
+          container.reverseDepIsSingleObject = singleObject;
+        }
+
+        @Override
+        void setDataToConsolidate(BuildingState container, Object dataToConsolidate) {
+          container.reverseDepsDataToConsolidate = dataToConsolidate;
+        }
+
+        @Override
+        Object getReverseDepsObject(BuildingState container) {
+          return container.reverseDepsToSignal;
+        }
+
+        @Override
+        boolean isSingleReverseDep(BuildingState container) {
+          return container.reverseDepIsSingleObject;
+        }
+
+        @Override
+        Object getDataToConsolidate(BuildingState container) {
+          return container.reverseDepsDataToConsolidate;
+        }
+      };
 
   // Below are fields that are used for dirty nodes.
 
@@ -180,12 +181,10 @@ public class BuildingState {
     Preconditions.checkState(isChanged || !this.lastBuildDirectDeps.isEmpty(),
         "%s is being marked dirty, not changed, but has no children that could have dirtied it",
         this);
-    dirtyState = isChanged ? DirtyState.REBUILDING
-        : DirtyState.CHECK_DEPENDENCIES;
-    if (dirtyState == DirtyState.CHECK_DEPENDENCIES) {
-      // We need to iterate through the deps to see if they have changed. Initialize the iterator.
-      dirtyDirectDepIterator = lastBuildDirectDeps.iterator();
-    }
+    dirtyState = isChanged ? DirtyState.NEEDS_REBUILDING : DirtyState.CHECK_DEPENDENCIES;
+    // We need to iterate through the deps to see if they have changed, or to remove them if one
+    // has. Initialize the iterator.
+    dirtyDirectDepIterator = lastBuildDirectDeps.iterator();
   }
 
   static BuildingState newDirtyState(boolean isChanged,
@@ -197,7 +196,7 @@ public class BuildingState {
     Preconditions.checkState(isDirty(), this);
     Preconditions.checkState(!isChanged(), this);
     Preconditions.checkState(!evaluating, this);
-    dirtyState = DirtyState.REBUILDING;
+    dirtyState = DirtyState.NEEDS_REBUILDING;
   }
 
   void forceChanged() {
@@ -234,11 +233,7 @@ public class BuildingState {
    * @see NodeEntry#isChanged()
    */
   boolean isChanged() {
-    return dirtyState == DirtyState.REBUILDING;
-  }
-
-  private boolean rebuilding() {
-    return dirtyState == DirtyState.REBUILDING;
+    return dirtyState == DirtyState.NEEDS_REBUILDING || dirtyState == DirtyState.REBUILDING;
   }
 
   /**
@@ -246,10 +241,14 @@ public class BuildingState {
    * actually like to check that the node has been evaluated, but that is not available in
    * this context.
    */
-  private void checkNotProcessing() {
+  private void checkFinishedBuildingWhenAboutToSetValue() {
     Preconditions.checkState(evaluating, "not started building %s", this);
-    Preconditions.checkState(!isDirty() || dirtyState == DirtyState.VERIFIED_CLEAN
-        || rebuilding(), "not done building %s", this);
+    Preconditions.checkState(
+        !isDirty()
+            || dirtyState == DirtyState.VERIFIED_CLEAN
+            || dirtyState == DirtyState.REBUILDING,
+        "not done building %s",
+        this);
     Preconditions.checkState(isReady(), "not done building %s", this);
   }
 
@@ -269,7 +268,7 @@ public class BuildingState {
    * finished is equal to the number of known children.
    *
    * <p>If the node is dirty and checking its deps for changes, this also updates {@link
-   * #dirtyState} as needed -- {@link DirtyState#REBUILDING} if the child has changed,
+   * #dirtyState} as needed -- {@link DirtyState#NEEDS_REBUILDING} if the child has changed,
    * and {@link DirtyState#VERIFIED_CLEAN} if the child has not changed and this was the
    * last child to be checked (as determined by {@link #dirtyDirectDepIterator}.hasNext() and
    * isReady()).
@@ -278,15 +277,15 @@ public class BuildingState {
    */
   boolean signalDep(boolean childChanged) {
     signaledDeps++;
-    if (isDirty() && !rebuilding()) {
-      // Synchronization isn't needed here because the only caller is ValueEntry, which does it
-      // through the synchronized method signalDep(long).
+    if (isDirty() && !isChanged()) {
+      // Synchronization isn't needed here because the only caller is NodeEntry, which does it
+      // through the synchronized method signalDep(Version).
       if (childChanged) {
-        dirtyState = DirtyState.REBUILDING;
+        dirtyState = DirtyState.NEEDS_REBUILDING;
       } else if (dirtyState == DirtyState.CHECK_DEPENDENCIES
           && isReady()
           && !dirtyDirectDepIterator.hasNext()) {
-        // No other dep already marked this as REBUILDING, no deps outstanding, and this was
+        // No other dep already marked this as NEEDS_REBUILDING, no deps outstanding, and this was
         // the last block of deps to be checked.
         dirtyState = DirtyState.VERIFIED_CLEAN;
       }
@@ -300,7 +299,7 @@ public class BuildingState {
    * was built, in the same order. Should only be used by {@link NodeEntry#setValue}.
    */
   boolean unchangedFromLastBuild(SkyValue newValue) {
-    checkNotProcessing();
+    checkFinishedBuildingWhenAboutToSetValue();
     return getLastBuildValue().equals(newValue) && lastBuildDirectDeps.equals(directDeps);
   }
 
@@ -341,6 +340,22 @@ public class BuildingState {
     return nextDeps;
   }
 
+  Collection<SkyKey> getAllRemainingDirtyDirectDeps() {
+    Preconditions.checkState(isDirty(), this);
+    ImmutableList.Builder<SkyKey> result = ImmutableList.builder();
+    while (dirtyDirectDepIterator.hasNext()) {
+      result.addAll(dirtyDirectDepIterator.next());
+    }
+    return result.build();
+  }
+
+  Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps() {
+    Preconditions.checkState(dirtyState == DirtyState.NEEDS_REBUILDING, this);
+    Collection<SkyKey> result = getAllRemainingDirtyDirectDeps();
+    dirtyState = DirtyState.REBUILDING;
+    return result;
+  }
+
   void addDirectDeps(GroupedListHelper<SkyKey> depsThisRun) {
     directDeps.append(depsThisRun);
   }
@@ -380,7 +395,7 @@ public class BuildingState {
    * @see NodeEntry#addReverseDepAndCheckIfDone(SkyKey)
    */
   void addReverseDepToSignal(SkyKey newReverseDep) {
-    REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
+    REVERSE_DEPS_UTIL.consolidateData(this);
     REVERSE_DEPS_UTIL.addReverseDeps(this, Collections.singleton(newReverseDep));
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
index ad50bea196..9e346ebcb5 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
@@ -27,7 +27,6 @@ import com.google.devtools.build.skyframe.Differencer.Diff;
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DeletingInvalidationState;
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DirtyingInvalidationState;
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationState;
-import com.google.devtools.build.skyframe.NodeEntry.DependencyState;
 import com.google.devtools.build.skyframe.ParallelEvaluator.Receiver;
 
 import java.io.PrintStream;
@@ -224,29 +223,8 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator {
       return;
     }
     for (Entry<SkyKey, SkyValue> entry : valuesToInject.entrySet()) {
-      SkyKey key = entry.getKey();
-      SkyValue value = entry.getValue();
-      Preconditions.checkState(value != null, key);
-      NodeEntry prevEntry = graph.createIfAbsent(key);
-      if (prevEntry.isDirty()) {
-        // There was an existing entry for this key in the graph.
-        // Get the node in the state where it is able to accept a value.
-        Preconditions.checkState(prevEntry.getTemporaryDirectDeps().isEmpty(), key);
-
-        DependencyState newState = prevEntry.addReverseDepAndCheckIfDone(null);
-        Preconditions.checkState(newState == DependencyState.NEEDS_SCHEDULING, key);
-
-        // Check that the previous node has no dependencies. Overwriting a value with deps with an
-        // injected value (which is by definition deps-free) needs a little additional bookkeeping
-        // (removing reverse deps from the dependencies), but more importantly it's something that
-        // 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);
-      }
-      prevEntry.setValue(value, version);
-      // The evaluate method previously invalidated all keys in valuesToInject that survived the
-      // pruneInjectedValues call. Now that this key's injected value is set, it is no longer dirty.
-      dirtyKeyTracker.notDirty(key);
+      ParallelEvaluator.injectValue(
+          entry.getKey(), entry.getValue(), version, graph, dirtyKeyTracker);
     }
     // Start with a new map to avoid bloat since clear() does not downsize the map.
     valuesToInject = new HashMap<>();
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 fa8e3082a6..f3a6a8111a 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -18,11 +18,11 @@ import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
 
 import java.util.Collection;
-import java.util.List;
 import java.util.Set;
 
 import javax.annotation.Nullable;
@@ -82,49 +82,49 @@ public class InMemoryNodeEntry implements NodeEntry {
   protected boolean reverseDepIsSingleObject = false;
 
   /**
-   * During the invalidation we keep the reverse deps to be removed in this list instead of directly
-   * removing them from {@code reverseDeps}. That is because removals from reverseDeps are O(N).
+   * When reverse deps are removed or checked for presence, we store them in this object instead of
+   * directly removing/checking them. That is because removals/checks in reverseDeps are O(N).
    * Originally reverseDeps was a HashSet, but because of memory consumption we switched to a list.
    *
    * <p>This requires that any usage of reverseDeps (contains, add, the list of reverse deps) call
-   * {@code consolidateReverseDepsRemovals} first. While this operation is not free, it can be done
-   * more effectively than trying to remove each dirty reverse dependency individually (O(N) each
-   * time).
+   * {@code consolidateData} first. While this operation is not free, it can be done
+   * more effectively than trying to remove/check each dirty reverse dependency individually (O(N)
+   * each time).
    */
-  private List<SkyKey> reverseDepsToRemove = null;
+  private Object reverseDepsDataToConsolidate = null;
 
   protected static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL =
       new ReverseDepsUtil<InMemoryNodeEntry>() {
-    @Override
-    void setReverseDepsObject(InMemoryNodeEntry container, Object object) {
-      container.reverseDeps = object;
-    }
+        @Override
+        void setReverseDepsObject(InMemoryNodeEntry container, Object object) {
+          container.reverseDeps = object;
+        }
 
-    @Override
-    void setSingleReverseDep(InMemoryNodeEntry container, boolean singleObject) {
-      container.reverseDepIsSingleObject = singleObject;
-    }
+        @Override
+        void setSingleReverseDep(InMemoryNodeEntry container, boolean singleObject) {
+          container.reverseDepIsSingleObject = singleObject;
+        }
 
-    @Override
-    void setReverseDepsToRemove(InMemoryNodeEntry container, List<SkyKey> object) {
-      container.reverseDepsToRemove = object;
-    }
+        @Override
+        void setDataToConsolidate(InMemoryNodeEntry container, Object dataToConsolidate) {
+          container.reverseDepsDataToConsolidate = dataToConsolidate;
+        }
 
-    @Override
-    Object getReverseDepsObject(InMemoryNodeEntry container) {
-      return container.reverseDeps;
-    }
+        @Override
+        Object getReverseDepsObject(InMemoryNodeEntry container) {
+          return container.reverseDeps;
+        }
 
-    @Override
-    boolean isSingleReverseDep(InMemoryNodeEntry container) {
-      return container.reverseDepIsSingleObject;
-    }
+        @Override
+        boolean isSingleReverseDep(InMemoryNodeEntry container) {
+          return container.reverseDepIsSingleObject;
+        }
 
-    @Override
-    List<SkyKey> getReverseDepsToRemove(InMemoryNodeEntry container) {
-      return container.reverseDepsToRemove;
-    }
-  };
+        @Override
+        Object getDataToConsolidate(InMemoryNodeEntry container) {
+          return container.reverseDepsDataToConsolidate;
+        }
+      };
 
   /**
    * The transient state of this entry, after it has been created but before it is done. It allows
@@ -202,7 +202,7 @@ public class InMemoryNodeEntry implements NodeEntry {
   private synchronized Set<SkyKey> setStateFinishedAndReturnReverseDeps() {
     // Get reverse deps that need to be signaled.
     ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal();
-    REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
+    REVERSE_DEPS_UTIL.consolidateData(this);
     REVERSE_DEPS_UTIL.addReverseDeps(this, reverseDepsToSignal);
     this.directDeps = buildingState.getFinishedDirectDeps().compress();
 
@@ -247,7 +247,7 @@ public class InMemoryNodeEntry implements NodeEntry {
   public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
     if (reverseDep != null) {
       if (keepEdges()) {
-        REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
+        REVERSE_DEPS_UTIL.consolidateData(this);
         REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(this, reverseDep);
       }
       if (isDone()) {
@@ -263,7 +263,20 @@ public class InMemoryNodeEntry implements NodeEntry {
       return DependencyState.DONE;
     }
     return buildingState.startEvaluating() ? DependencyState.NEEDS_SCHEDULING
-                                           : DependencyState.ADDED_DEP;
+                                           : DependencyState.ALREADY_EVALUATING;
+  }
+
+  @Override
+  public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
+    Preconditions.checkNotNull(reverseDep, this);
+    Preconditions.checkState(keepEdges(), "%s %s", reverseDep, this);
+    if (!isDone()) {
+      REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
+      buildingState.addReverseDepToSignal(reverseDep);
+    } else {
+      REVERSE_DEPS_UTIL.checkReverseDep(this, reverseDep);
+    }
+    return addReverseDepAndCheckIfDone(null);
   }
 
   @Override
@@ -271,19 +284,23 @@ public class InMemoryNodeEntry implements NodeEntry {
     if (!keepEdges()) {
       return;
     }
-    if (REVERSE_DEPS_UTIL.reverseDepsIsEmpty(this)) {
-      // If an entry has no existing reverse deps, all its reverse deps are to signal, and vice
-      // versa.
-      buildingState.removeReverseDepToSignal(reverseDep);
-    } else {
-      REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
-    }
+    REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
+  }
+
+  @Override
+  public synchronized void removeInProgressReverseDep(SkyKey reverseDep) {
+    buildingState.removeReverseDepToSignal(reverseDep);
   }
 
   @Override
-  public synchronized Collection<SkyKey> getReverseDeps() {
+  public synchronized Iterable<SkyKey> getReverseDeps() {
     assertKeepEdges();
-    return REVERSE_DEPS_UTIL.getReverseDeps(this);
+    Iterable<SkyKey> reverseDeps = REVERSE_DEPS_UTIL.getReverseDeps(this);
+    if (isDone()) {
+      return reverseDeps;
+    } else {
+      return Iterables.concat(reverseDeps, buildingState.getReverseDepsToSignal());
+    }
   }
 
   @Override
@@ -313,15 +330,13 @@ public class InMemoryNodeEntry implements NodeEntry {
   }
 
   @Override
-  @Nullable
-  public synchronized Iterable<SkyKey> markDirty(boolean isChanged) {
+  public synchronized boolean markDirty(boolean isChanged) {
     assertKeepEdges();
     if (isDone()) {
-      GroupedList<SkyKey> lastDirectDeps = GroupedList.create(directDeps);
-      buildingState = BuildingState.newDirtyState(isChanged, lastDirectDeps, value);
+      buildingState =
+          BuildingState.newDirtyState(isChanged, GroupedList.<SkyKey>create(directDeps), value);
       value = null;
-      directDeps = null;
-      return lastDirectDeps.toSet();
+      return true;
     }
     // The caller may be simultaneously trying to mark this node dirty and changed, and the dirty
     // thread may have lost the race, but it is the caller's responsibility not to try to mark
@@ -330,13 +345,12 @@ public class InMemoryNodeEntry implements NodeEntry {
     Preconditions.checkState(isChanged != isChanged(),
         "Cannot mark node dirty twice or changed twice: %s", this);
     Preconditions.checkState(value == null, "Value should have been reset already %s", this);
-    Preconditions.checkState(directDeps == null, "direct deps not already reset %s", this);
     if (isChanged) {
       // If the changed marker lost the race, we just need to mark changed in this method -- all
       // other work was done by the dirty marker.
       buildingState.markChanged();
     }
-    return null;
+    return false;
   }
 
   @Override
@@ -371,10 +385,27 @@ public class InMemoryNodeEntry implements NodeEntry {
   /**  @see BuildingState#getNextDirtyDirectDeps() */
   @Override
   public synchronized Collection<SkyKey> getNextDirtyDirectDeps() {
+    Preconditions.checkState(isReady(), this);
     return buildingState.getNextDirtyDirectDeps();
   }
 
   @Override
+  public synchronized Iterable<SkyKey> getAllDirectDepsForIncompleteNode() {
+    Preconditions.checkState(!isDone(), this);
+    if (!isDirty()) {
+      return getTemporaryDirectDeps();
+    } else {
+      return Iterables.concat(
+          getTemporaryDirectDeps(), buildingState.getAllRemainingDirtyDirectDeps());
+    }
+  }
+
+  @Override
+  public synchronized Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps() {
+    return buildingState.markRebuildingAndGetAllRemainingDirtyDirectDeps();
+  }
+
+  @Override
   public synchronized Set<SkyKey> getTemporaryDirectDeps() {
     Preconditions.checkState(!isDone(), "temporary shouldn't be done: %s", this);
     return buildingState.getDirectDepsForBuild();
@@ -403,13 +434,15 @@ public class InMemoryNodeEntry implements NodeEntry {
   }
 
   @Override
-  public String toString() {
+  public synchronized String toString() {
     return MoreObjects.toStringHelper(this)
+        .add("identity", System.identityHashCode(this))
         .add("value", value)
         .add("version", version)
         .add("directDeps", directDeps == null ? null : GroupedList.create(directDeps))
         .add("reverseDeps", REVERSE_DEPS_UTIL.toString(this))
-        .add("buildingState", buildingState).toString();
+        .add("buildingState", buildingState)
+        .toString();
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
index 791155a7dd..659f8f6665 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -239,17 +239,39 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
                 for (SkyKey reverseDep : entry.getReverseDeps()) {
                   visit(reverseDep, InvalidationType.DELETED, !MUST_EXIST);
                 }
+
+                // Unregister this node as an rdep from its direct deps, since reverse dep edges
+                // cannot point to non-existent nodes. To know whether the child has this node as an
+                // "in-progress" rdep to be signaled, or just as a known rdep, we look at the deps
+                // that this node declared during its last (presumably interrupted) evaluation. If a
+                // dep is in this set, then it was notified to signal this node, and so the rdep
+                // will be an in-progress rdep, if the dep itself isn't done. Otherwise it will be a
+                // normal rdep. That information is used to remove this node as an rdep from the
+                // correct list of rdeps in the child -- because of our compact storage of rdeps,
+                // checking which list contains this parent could be expensive.
+                Set<SkyKey> signalingDeps =
+                    entry.isDone() ? ImmutableSet.<SkyKey>of() : entry.getTemporaryDirectDeps();
                 Iterable<SkyKey> directDeps =
-                    entry.isDone() ? entry.getDirectDeps() : entry.getTemporaryDirectDeps();
-                // Unregister this node from direct deps, since reverse dep edges cannot point to
-                // non-existent nodes.
-                for (SkyKey directDep : directDeps) {
-                  NodeEntry dep = graph.get(directDep);
+                    entry.isDone()
+                        ? entry.getDirectDeps()
+                        : entry.getAllDirectDepsForIncompleteNode();
+                Map<SkyKey, NodeEntry> depMap = graph.getBatch(directDeps);
+                for (Map.Entry<SkyKey, NodeEntry> directDepEntry : depMap.entrySet()) {
+                  NodeEntry dep = directDepEntry.getValue();
                   if (dep != null) {
-                    dep.removeReverseDep(key);
+                    if (dep.isDone() || !signalingDeps.contains(directDepEntry.getKey())) {
+                      dep.removeReverseDep(key);
+                    } else {
+                      // This step is not strictly necessary, since all in-progress nodes are
+                      // deleted during graph cleaning, which happens in a single
+                      // DeletingNodeVisitor visitation, aka the one right now. We leave this here
+                      // in case the logic changes.
+                      dep.removeInProgressReverseDep(key);
+                    }
                   }
                 }
               }
+
               // Allow custom key-specific logic to update dirtiness status.
               informInvalidationReceiver(key, EvaluationProgressReceiver.InvalidationState.DELETED);
               // Actually remove the node.
@@ -343,40 +365,20 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
                 return;
               }
 
-              // This entry remains in the graph in this dirty state until it is re-evaluated.
-              Iterable<SkyKey> deps = entry.markDirty(isChanged);
               // It is not safe to interrupt the logic from this point until the end of the method.
               // Any exception thrown should be unrecoverable.
-              if (deps == null) {
+              // This entry remains in the graph in this dirty state until it is re-evaluated.
+              if (!entry.markDirty(isChanged)) {
                 // Another thread has already dirtied this node. Don't do anything in this thread.
                 pendingVisitations.remove(invalidationPair);
                 return;
               }
-              // Propagate dirtiness upwards and mark this node dirty/changed. Reverse deps
-              // should only be marked dirty (because only a dependency of theirs has changed).
+              // Propagate dirtiness upwards and mark this node dirty/changed. Reverse deps should
+              // only be marked dirty (because only a dependency of theirs has changed).
               for (SkyKey reverseDep : entry.getReverseDeps()) {
                 visit(reverseDep, InvalidationType.DIRTIED, MUST_EXIST);
               }
 
-              // Remove this node as a reverse dep from its children, since we have reset it and
-              // it no longer lists its children as direct deps.
-              Map<SkyKey, ? extends ThinNodeEntry> children = graph.getBatch(deps);
-              if (children.size() != Iterables.size(deps)) {
-                Set<SkyKey> depsSet = ImmutableSet.copyOf(deps);
-                throw new IllegalStateException(
-                    "Mismatch in getBatch: "
-                        + key
-                        + ", "
-                        + entry
-                        + "\n"
-                        + Sets.difference(depsSet, children.keySet())
-                        + "\n"
-                        + Sets.difference(children.keySet(), depsSet));
-              }
-              for (ThinNodeEntry child : children.values()) {
-                child.removeReverseDep(key);
-              }
-
               informInvalidationReceiver(key, EvaluationProgressReceiver.InvalidationState.DIRTY);
               dirtyKeyTracker.dirty(key);
               // Remove the node from the set as the last operation.
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 56f89978ae..9f45ad4ede 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -29,15 +29,17 @@ import javax.annotation.Nullable;
  */
 public interface NodeEntry extends ThinNodeEntry {
   /**
-   * Return code for {@link #addReverseDepAndCheckIfDone(SkyKey)}.
+   * Return code for {@link #addReverseDepAndCheckIfDone} and
+   * {@link #checkIfDoneForDirtyReverseDep}.
    */
   enum DependencyState {
     /** The node is done. */
     DONE,
 
     /**
-     * The node was just created and needs to be scheduled for its first evaluation pass. The
-     * evaluator is responsible for signaling the reverse dependency node.
+     * The node has not started evaluating, and needs to be scheduled for its first evaluation pass.
+     * The caller getting this return value is responsible for scheduling its evaluation and
+     * signaling the reverse dependency node when this node is done.
      */
     NEEDS_SCHEDULING,
 
@@ -45,7 +47,7 @@ public interface NodeEntry extends ThinNodeEntry {
      * The node was already created, but isn't done yet. The evaluator is responsible for
      * signaling the reverse dependency node.
      */
-    ADDED_DEP;
+    ALREADY_EVALUATING;
   }
 
   /**
@@ -63,9 +65,11 @@ public interface NodeEntry extends ThinNodeEntry {
      */
     VERIFIED_CLEAN,
     /**
-     * A rebuilding is required or in progress, because either the node itself changed or one of
-     * its dependencies did.
+     * A rebuilding is required, because either the node itself changed or one of its dependencies
+     * did.
      */
+    NEEDS_REBUILDING,
+    /** A rebuilding is in progress. */
     REBUILDING
   }
 
@@ -149,7 +153,17 @@ public interface NodeEntry extends ThinNodeEntry {
    * if the node needs to be scheduled.
    */
   @ThreadSafe
-  DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep);
+  DependencyState addReverseDepAndCheckIfDone(@Nullable SkyKey reverseDep);
+
+  /**
+   * 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.
+   */
+  @ThreadSafe
+  DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep);
 
   /**
    * Tell this node that one of its dependencies is now done. Callers must check the return value,
@@ -169,7 +183,7 @@ public interface NodeEntry extends ThinNodeEntry {
    * {@link #getVersion()}, then this entry records that one of its children has changed since it
    * was last evaluated (namely, it was last evaluated at version {@link #getVersion()} and the
    * child was last evaluated at {@code childVersion}. Thus, the next call to
-   * {@link #getDirtyState()} will return {@link DirtyState#REBUILDING}.
+   * {@link #getDirtyState()} will return {@link DirtyState#NEEDS_REBUILDING}.
    */
   @ThreadSafe
   boolean signalDep(Version childVersion);
@@ -230,6 +244,37 @@ public interface NodeEntry extends ThinNodeEntry {
   Collection<SkyKey> getNextDirtyDirectDeps();
 
   /**
+   * Returns all deps of a node that has not yet finished evaluating. In other words, if a node has
+   * a reverse dep on this node, its key will be in the returned set here. If this node was freshly
+   * 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}.
+   *
+   * <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
+   * are any nodes that depend on them, which are necessarily also not done. If this node is to be
+   * deleted because of this, we must delete it as a reverse dep from other nodes. This method
+   * returns that list of other nodes. This method may not be called on done nodes, since they do
+   * not need to be deleted after aborted evaluations.
+   *
+   * <p>This method must not be called twice: the next thing done to this node after this method is
+   * called should be the removal of the node from the graph.
+   */
+  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}).
+   */
+  Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps();
+
+  /**
    * Returns the set of direct dependencies. This may only be called while the node is being
    * evaluated, that is, before {@link #setValue} and after {@link #markDirty}.
    */
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 12cc1dd0cb..a2df93a2ed 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -40,6 +40,7 @@ import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationState;
 import com.google.devtools.build.skyframe.MemoizingEvaluator.EmittedEventState;
 import com.google.devtools.build.skyframe.NodeEntry.DependencyState;
+import com.google.devtools.build.skyframe.NodeEntry.DirtyState;
 import com.google.devtools.build.skyframe.Scheduler.SchedulerException;
 import com.google.devtools.build.skyframe.SkyFunctionException.ReifiedSkyFunctionException;
 
@@ -582,6 +583,32 @@ public final class ParallelEvaluator implements Evaluator {
   }
 
   /**
+   * 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.
+   */
+  private void maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(SkyKey key, NodeEntry entry) {
+    if (entry.isDirty() && entry.getDirtyState() != DirtyState.REBUILDING) {
+      Collection<SkyKey> depsToRemove = entry.markRebuildingAndGetAllRemainingDirtyDirectDeps();
+      Map<SkyKey, NodeEntry> depsToClearFrom = graph.getBatch(depsToRemove);
+      Preconditions.checkState(
+          depsToRemove.size() == depsToClearFrom.size(),
+          "%s %s: %s %s",
+          key,
+          entry,
+          depsToRemove,
+          depsToClearFrom);
+      for (NodeEntry depEntry : depsToClearFrom.values()) {
+        depEntry.removeReverseDep(key);
+      }
+    }
+  }
+
+  private enum DirtyOutcome {
+    ALREADY_PROCESSED,
+    NEEDS_EVALUATION
+  }
+
+  /**
    * An action that evaluates a value.
    */
   private class Evaluate implements Runnable {
@@ -594,20 +621,24 @@ public final class ParallelEvaluator implements Evaluator {
       this.skyKey = skyKey;
     }
 
-    private void enqueueChild(SkyKey skyKey, NodeEntry entry, SkyKey child) {
+    private void enqueueChild(SkyKey skyKey, NodeEntry entry, SkyKey child, boolean dirtyParent) {
       Preconditions.checkState(!entry.isDone(), "%s %s", skyKey, entry);
 
       NodeEntry depEntry = graph.createIfAbsent(child);
-      switch (depEntry.addReverseDepAndCheckIfDone(skyKey)) {
-        case DONE :
+      DependencyState dependencyState =
+          dirtyParent
+              ? depEntry.checkIfDoneForDirtyReverseDep(skyKey)
+              : depEntry.addReverseDepAndCheckIfDone(skyKey);
+      switch (dependencyState) {
+        case DONE:
           if (entry.signalDep(depEntry.getVersion())) {
             // This can only happen if there are no more children to be added.
             visitor.enqueueEvaluation(skyKey);
           }
           break;
-        case ADDED_DEP :
+        case ALREADY_EVALUATING:
           break;
-        case NEEDS_SCHEDULING :
+        case NEEDS_SCHEDULING:
           visitor.enqueueEvaluation(child);
           break;
       }
@@ -623,97 +654,116 @@ public final class ParallelEvaluator implements Evaluator {
           && !graph.get(ErrorTransienceValue.key()).getVersion().atMost(entry.getVersion());
     }
 
-    @Override
-    public void run() {
-      NodeEntry state = Preconditions.checkNotNull(graph.get(skyKey), skyKey);
-      Preconditions.checkState(state.isReady(), "%s %s", skyKey, state);
-
-      if (state.isDirty()) {
-        switch (state.getDirtyState()) {
-          case CHECK_DEPENDENCIES:
-            // Evaluating a dirty node for the first time, and checking its children to see if any
-            // of them have changed. Note that there must be dirty children for this to happen.
-
-            // Check the children group by group -- we don't want to evaluate a value that is no
-            // longer needed because an earlier dependency changed. For example, //foo:foo depends
-            // on target //bar:bar and is built. Then foo/BUILD is modified to remove the dependence
-            // on bar, and bar/BUILD is deleted. Reloading //bar:bar would incorrectly throw an
-            // exception. To avoid this, we must reload foo/BUILD first, at which point we will
-            // discover that it has changed, and re-evaluate target //foo:foo from scratch.
-            // On the other hand, when an action requests all of its inputs, we can safely check all
-            // of them in parallel on a subsequent build. So we allow checking an entire group in
-            // parallel here, if the node builder requested a group last build.
-            Collection<SkyKey> directDepsToCheck = state.getNextDirtyDirectDeps();
-
-            if (invalidatedByErrorTransience(directDepsToCheck, state)) {
-              // If this dep is the ErrorTransienceValue and the ErrorTransienceValue has been
-              // updated then we need to force a rebuild. We would like to just signal the entry as
-              // usual, but we can't, because then the ErrorTransienceValue would remain as a dep,
-              // which would be incorrect if, for instance, the value re-evaluated to a non-error.
-              state.forceRebuild();
-              break; // Fall through to re-evaluation.
-            }
-            if (!keepGoing) {
-              // This check ensures that we maintain the invariant that if a node with an error is
-              // reached during a no-keep-going build, none of its currently building parents
-              // finishes building. If the child isn't done building yet, it will detect on its own
-              // that it has an error (see the VERIFIED_CLEAN case below). On the other hand, if it
-              // is done, then it is the parent's responsibility to notice that, which we do here.
-              // We check the deps for errors so that we don't continue building this node if it has
-              // a child error.
-              for (Map.Entry<SkyKey, NodeEntry> entry :
-                  graph.getBatch(directDepsToCheck).entrySet()) {
-                if (entry.getValue().isDone() && entry.getValue().getErrorInfo() != null) {
-                  // If any child has an error, we arbitrarily add a dep on the first one (needed
-                  // for error bubbling) and throw an exception coming from it.
-                  if (!visitor.preventNewEvaluations()) {
-                    // An error was already thrown in the evaluator. Don't do anything here.
-                    return;
+    private DirtyOutcome maybeHandleDirtyNode(NodeEntry state) {
+      if (!state.isDirty()) {
+        return DirtyOutcome.NEEDS_EVALUATION;
+      }
+      switch (state.getDirtyState()) {
+        case CHECK_DEPENDENCIES:
+          // Evaluating a dirty node for the first time, and checking its children to see if any
+          // of them have changed. Note that there must be dirty children for this to happen.
+
+          // Check the children group by group -- we don't want to evaluate a value that is no
+          // longer needed because an earlier dependency changed. For example, //foo:foo depends
+          // on target //bar:bar and is built. Then foo/BUILD is modified to remove the dependence
+          // on bar, and bar/BUILD is deleted. Reloading //bar:bar would incorrectly throw an
+          // exception. To avoid this, we must reload foo/BUILD first, at which point we will
+          // discover that it has changed, and re-evaluate target //foo:foo from scratch.
+          // On the other hand, when an action requests all of its inputs, we can safely check all
+          // of them in parallel on a subsequent build. So we allow checking an entire group in
+          // parallel here, if the node builder requested a group last build.
+          // Note: every dep returned here must either have this node re-registered for it (using
+          // checkIfDoneForDirtyReverseDep) and be registered as a direct dep of this node, or have
+          // its reverse dep on this node removed. Failing to do either one of these would result in
+          // a graph inconsistency, where the child had a reverse dep on this node, but this node
+          // had no kind of dependency on the child.
+          Collection<SkyKey> directDepsToCheck = state.getNextDirtyDirectDeps();
+
+          if (invalidatedByErrorTransience(directDepsToCheck, state)) {
+            // If this dep is the ErrorTransienceValue and the ErrorTransienceValue has been
+            // updated then we need to force a rebuild. We would like to just signal the entry as
+            // usual, but we can't, because then the ErrorTransienceValue would remain as a dep,
+            // which would be incorrect if, for instance, the value re-evaluated to a non-error.
+            state.forceRebuild();
+            graph.get(ErrorTransienceValue.key()).removeReverseDep(skyKey);
+            return DirtyOutcome.NEEDS_EVALUATION;
+          }
+          if (!keepGoing) {
+            // This check ensures that we maintain the invariant that if a node with an error is
+            // reached during a no-keep-going build, none of its currently building parents
+            // finishes building. If the child isn't done building yet, it will detect on its own
+            // that it has an error (see the VERIFIED_CLEAN case below). On the other hand, if it
+            // is done, then it is the parent's responsibility to notice that, which we do here.
+            // We check the deps for errors so that we don't continue building this node if it has
+            // a child error.
+            Map<SkyKey, NodeEntry> entriesToCheck = graph.getBatch(directDepsToCheck);
+            for (Map.Entry<SkyKey, NodeEntry> entry : entriesToCheck.entrySet()) {
+              if (entry.getValue().isDone() && entry.getValue().getErrorInfo() != null) {
+                // If any child has an error, we arbitrarily add a dep on the first one (needed
+                // for error bubbling) and throw an exception coming from it.
+                SkyKey errorKey = entry.getKey();
+                NodeEntry errorEntry = entry.getValue();
+                state.addTemporaryDirectDeps(GroupedListHelper.create(ImmutableList.of(errorKey)));
+                errorEntry.checkIfDoneForDirtyReverseDep(skyKey);
+                // Perform the necessary bookkeeping for any deps that are not being used.
+                for (Map.Entry<SkyKey, NodeEntry> depEntry : entriesToCheck.entrySet()) {
+                  if (!depEntry.getKey().equals(errorKey)) {
+                    depEntry.getValue().removeReverseDep(skyKey);
                   }
-                  SkyKey errorKey = entry.getKey();
-                  NodeEntry errorEntry = entry.getValue();
-                  state.addTemporaryDirectDeps(
-                      GroupedListHelper.create(ImmutableList.of(errorKey)));
-                  DependencyState errorState = entry.getValue().addReverseDepAndCheckIfDone(skyKey);
-                  Preconditions.checkState(errorState == DependencyState.DONE, "%s %s %s %s",
-                      skyKey, state, errorKey, errorEntry);
-                  throw SchedulerException.ofError(errorEntry.getErrorInfo(), entry.getKey());
                 }
+                if (!visitor.preventNewEvaluations()) {
+                  // An error was already thrown in the evaluator. Don't do anything here.
+                  return DirtyOutcome.ALREADY_PROCESSED;
+                }
+                throw SchedulerException.ofError(errorEntry.getErrorInfo(), entry.getKey());
               }
             }
-            // It is safe to add these deps back to the node -- even if one of them has changed, the
-            // contract of pruning is that the node will request these deps again when it rebuilds.
-            // We must add these deps before enqueuing them, so that the node knows that it depends
-            // on them. If one of these deps is the error transience node, the check we did above
-            // in #invalidatedByErrorTransience means that the error transience node is not newer
-            // than this node, so we are going to mark it clean (since the error transience node is
-            // always the last dep).
-            state.addTemporaryDirectDeps(GroupedListHelper.create(directDepsToCheck));
-            for (SkyKey directDep : directDepsToCheck) {
-              enqueueChild(skyKey, state, directDep);
-            }
-            return;
-          case VERIFIED_CLEAN:
-            // No child has a changed value. This node can be marked done and its parents signaled
-            // without any re-evaluation.
-            visitor.notifyDone(skyKey);
-            Set<SkyKey> reverseDeps = state.markClean();
-            if (progressReceiver != null) {
-              // Tell the receiver that the value was not actually changed this run.
-              progressReceiver.evaluated(skyKey, new SkyValueSupplier(state),
-                  EvaluationState.CLEAN);
-            }
-            if (!keepGoing && state.getErrorInfo() != null) {
-              if (!visitor.preventNewEvaluations()) {
-                return;
-              }
-              throw SchedulerException.ofError(state.getErrorInfo(), skyKey);
+          }
+          // It is safe to add these deps back to the node -- even if one of them has changed, the
+          // contract of pruning is that the node will request these deps again when it rebuilds.
+          // We must add these deps before enqueuing them, so that the node knows that it depends
+          // on them. If one of these deps is the error transience node, the check we did above
+          // in #invalidatedByErrorTransience means that the error transience node is not newer
+          // than this node, so we are going to mark it clean (since the error transience node is
+          // always the last dep).
+          state.addTemporaryDirectDeps(GroupedListHelper.create(directDepsToCheck));
+          for (SkyKey directDep : directDepsToCheck) {
+            enqueueChild(skyKey, state, directDep, /*dirtyParent=*/ true);
+          }
+          return DirtyOutcome.ALREADY_PROCESSED;
+        case VERIFIED_CLEAN:
+          // No child has a changed value. This node can be marked done and its parents signaled
+          // without any re-evaluation.
+          visitor.notifyDone(skyKey);
+          Set<SkyKey> reverseDeps = state.markClean();
+          if (progressReceiver != null) {
+            // Tell the receiver that the value was not actually changed this run.
+            progressReceiver.evaluated(skyKey, new SkyValueSupplier(state), EvaluationState.CLEAN);
+          }
+          if (!keepGoing && state.getErrorInfo() != null) {
+            if (!visitor.preventNewEvaluations()) {
+              return DirtyOutcome.ALREADY_PROCESSED;
             }
-            signalValuesAndEnqueueIfReady(visitor, reverseDeps, state.getVersion());
-            return;
-          case REBUILDING:
-            // Nothing to be done if we are already rebuilding.
-        }
+            throw SchedulerException.ofError(state.getErrorInfo(), skyKey);
+          }
+          signalValuesAndEnqueueIfReady(visitor, reverseDeps, state.getVersion());
+          return DirtyOutcome.ALREADY_PROCESSED;
+        case NEEDS_REBUILDING:
+          maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(skyKey, state);
+          // Fall through to REBUILDING case.
+        case REBUILDING:
+          return DirtyOutcome.NEEDS_EVALUATION;
+        default:
+          throw new IllegalStateException("key: " + skyKey + ", entry: " + state);
+      }
+    }
+
+    @Override
+    public void run() {
+      NodeEntry state = Preconditions.checkNotNull(graph.get(skyKey), skyKey);
+      Preconditions.checkState(state.isReady(), "%s %s", skyKey, state);
+      if (maybeHandleDirtyNode(state) == DirtyOutcome.ALREADY_PROCESSED) {
+        return;
       }
 
       // TODO(bazel-team): Once deps are requested in a deterministic order within a group, or the
@@ -850,7 +900,7 @@ public final class ParallelEvaluator implements Evaluator {
       }
 
       for (SkyKey newDirectDep : newDirectDeps) {
-        enqueueChild(skyKey, state, newDirectDep);
+        enqueueChild(skyKey, state, newDirectDep, /*dirtyParent=*/ false);
       }
       // It is critical that there is no code below this point.
     }
@@ -904,13 +954,13 @@ public final class ParallelEvaluator implements Evaluator {
   }
 
   /**
-   * If child is not done, removes key from child's reverse deps. Returns whether child should be
-   * removed from key's entry's direct deps.
+   * If child is not done, removes {@param inProgressParent} from {@param child}'s reverse deps.
+   * Returns whether child should be removed from inProgressParent's entry's direct deps.
    */
-  private boolean removeIncompleteChild(SkyKey key, SkyKey child) {
+  private boolean removeIncompleteChild(SkyKey inProgressParent, SkyKey child) {
     NodeEntry childEntry = graph.get(child);
     if (!isDoneForBuild(childEntry)) {
-      childEntry.removeReverseDep(key);
+      childEntry.removeInProgressReverseDep(inProgressParent);
       return true;
     }
     return false;
@@ -1021,18 +1071,13 @@ public final class ParallelEvaluator implements Evaluator {
     // in the graph, by the time that it is needed. Creating it on demand in a parallel context sets
     // up a race condition, because there is no way to atomically create a node and set its value.
     NodeEntry errorTransienceEntry = graph.createIfAbsent(ErrorTransienceValue.key());
-    DependencyState triState = errorTransienceEntry.addReverseDepAndCheckIfDone(null);
-    Preconditions.checkState(triState != DependencyState.ADDED_DEP,
-        "%s %s", errorTransienceEntry, triState);
-    if (triState != DependencyState.DONE) {
-      errorTransienceEntry.setValue(new ErrorTransienceValue(), graphVersion);
-      // The error transience entry is always invalidated by the RecordingDifferencer.
-      // Now that the entry's value is set, it is no longer dirty.
-      dirtyKeyTracker.notDirty(ErrorTransienceValue.key());
-
-      Preconditions.checkState(
-          errorTransienceEntry.addReverseDepAndCheckIfDone(null) != DependencyState.ADDED_DEP,
-          errorTransienceEntry);
+    if (!errorTransienceEntry.isDone()) {
+      injectValue(
+          ErrorTransienceValue.key(),
+          new ErrorTransienceValue(),
+          graphVersion,
+          graph,
+          dirtyKeyTracker);
     }
     for (SkyKey skyKey : skyKeys) {
       NodeEntry entry = graph.createIfAbsent(skyKey);
@@ -1044,7 +1089,7 @@ public final class ParallelEvaluator implements Evaluator {
         case DONE:
           informProgressReceiverThatValueIsDone(skyKey);
           break;
-        case ADDED_DEP:
+        case ALREADY_EVALUATING:
           break;
         default:
           throw new IllegalStateException(entry + " for " + skyKey + " in unknown state");
@@ -1135,7 +1180,7 @@ public final class ParallelEvaluator implements Evaluator {
     Map<SkyKey, ValueWithMetadata> bubbleErrorInfo = new HashMap<>();
     boolean externalInterrupt = false;
     while (true) {
-      NodeEntry errorEntry = graph.get(errorKey);
+      NodeEntry errorEntry = Preconditions.checkNotNull(graph.get(errorKey), errorKey);
       Iterable<SkyKey> reverseDeps = errorEntry.isDone()
           ? errorEntry.getReverseDeps()
           : errorEntry.getInProgressReverseDeps();
@@ -1178,15 +1223,27 @@ public final class ParallelEvaluator implements Evaluator {
               bubbleParent, bubbleParentEntry, parentVersion, graphVersion);
           continue;
         }
-        // Arbitrarily pick the first in-flight parent.
-        Preconditions.checkState(visitor.isInflight(bubbleParent),
-            "errorKey: %s, errorEntry: %s, bubbleParent: %s, bubbleParentEntry: %s", errorKey,
-            errorEntry, bubbleParent, bubbleParentEntry);
-        parent = bubbleParent;
-        parentEntry = bubbleParentEntry;
+        if (visitor.isInflight(bubbleParent)
+            && bubbleParentEntry.getTemporaryDirectDeps().contains(errorKey)) {
+          // Only bubble up to parent if it's part of this build. If this node was dirtied and
+          // re-evaluated, but in a build without this parent, we may try to bubble up to that
+          // parent. Don't -- it's not part of the build.
+          // Similarly, the parent may not yet have requested this dep in its dirtiness-checking
+          // process. Don't bubble up to it in that case either.
+          parent = bubbleParent;
+          parentEntry = bubbleParentEntry;
+          break;
+        }
+      }
+      if (parent == null) {
+        Preconditions.checkState(
+            rootValues.contains(errorKey),
+            "Current key %s has to be a top-level key: %s, %s",
+            errorKey,
+            rootValues,
+            errorEntry);
         break;
       }
-      Preconditions.checkNotNull(parent, "%s %s", errorKey, bubbleErrorInfo);
       errorKey = parent;
       SkyFunction factory = skyFunctions.get(parent.functionName());
       if (parentEntry.isDirty()) {
@@ -1195,9 +1252,11 @@ public final class ParallelEvaluator implements Evaluator {
             // If this value's child was bubbled up to, it did not signal this value, and so we must
             // manually make it ready to build.
             parentEntry.signalDep();
-            // Fall through to REBUILDING, since state is now REBUILDING.
+            // Fall through to NEEDS_REBUILDING, since state is now NEEDS_REBUILDING.
+          case NEEDS_REBUILDING:
+            maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(parent, parentEntry);
+            // Fall through to REBUILDING.
           case REBUILDING:
-            // Nothing to be done.
             break;
           default:
             throw new AssertionError(parent + " not in valid dirty state: " + parentEntry);
@@ -1392,6 +1451,7 @@ public final class ParallelEvaluator implements Evaluator {
         } else if (!entry.isReady()) {
           removeIncompleteChildrenForCycle(key, entry, entry.getTemporaryDirectDeps());
         }
+        maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry);
         Set<SkyKey> directDeps = entry.getTemporaryDirectDeps();
         // Find out which children have errors. Similar logic to that in Evaluate#run().
         List<ErrorInfo> errorDeps = getChildrenErrorsForCycle(directDeps);
@@ -1425,6 +1485,7 @@ public final class ParallelEvaluator implements Evaluator {
           // 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);
         }
         if (keepGoing) {
           // Any children of this node that we haven't already visited are not worth visiting,
@@ -1560,6 +1621,7 @@ public final class ParallelEvaluator implements Evaluator {
       // that the entry can conceivably be ready if its cycleChild already found a different cycle
       // and was built.
       entry.signalDep();
+      maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry);
     }
     Preconditions.checkState(entry.isReady(), "%s %s %s", key, cycleChild, entry);
     Iterator<SkyKey> it = toVisit.iterator();
@@ -1645,4 +1707,39 @@ public final class ParallelEvaluator implements Evaluator {
   private boolean isDoneForBuild(@Nullable NodeEntry entry) {
     return entry != null && entry.isDone();
   }
+
+  static void injectValue(
+      SkyKey key,
+      SkyValue value,
+      Version version,
+      EvaluableGraph graph,
+      DirtyKeyTracker dirtyKeyTracker) {
+    Preconditions.checkNotNull(value, key);
+    NodeEntry prevEntry = graph.createIfAbsent(key);
+    DependencyState newState = prevEntry.addReverseDepAndCheckIfDone(null);
+    Preconditions.checkState(
+        newState != DependencyState.ALREADY_EVALUATING, "%s %s", key, prevEntry);
+    if (prevEntry.isDirty()) {
+      Preconditions.checkState(
+          newState == DependencyState.NEEDS_SCHEDULING, "%s %s", key, prevEntry);
+      // There was an existing entry for this key in the graph.
+      // Get the node in the state where it is able to accept a value.
+
+      // Check that the previous node has no dependencies. Overwriting a value with deps with an
+      // injected value (which is by definition deps-free) needs a little additional bookkeeping
+      // (removing reverse deps from the dependencies), but more importantly it's something that
+      // 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.setValue(value, version);
+    // Now that this key's injected value is set, it is no longer dirty.
+    dirtyKeyTracker.notDirty(key);
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
index 807aa8c440..ed8d724af9 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
@@ -21,10 +21,14 @@ import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 
+import java.util.ArrayList;
 import java.util.Collection;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 
+import javax.annotation.Nullable;
+
 /**
  * A utility class that allows us to keep the reverse dependencies as an array list instead of a
  * set. This is more memory-efficient. At the same time it allows us to group the removals and
@@ -46,13 +50,126 @@ public abstract class ReverseDepsUtil<T> {
 
   abstract void setSingleReverseDep(T container, boolean singleObject);
 
-  abstract void setReverseDepsToRemove(T container, List<SkyKey> object);
+  abstract void setDataToConsolidate(T container, Object dataToConsolidate);
 
   abstract Object getReverseDepsObject(T container);
 
   abstract boolean isSingleReverseDep(T container);
 
-  abstract List<SkyKey> getReverseDepsToRemove(T container);
+  abstract Object getDataToConsolidate(T container);
+
+  private enum DataState {
+    NULL,
+    CHECK_ONLY,
+    BOTH
+  }
+
+  private static class RDepsToCheckAndRemove {
+    // reverseDepstoCheck may be null, but not toRemove, because we store a bare list if
+    // we have only toCheck.
+    @Nullable List<SkyKey> toCheck;
+    List<SkyKey> toRemove;
+
+    RDepsToCheckAndRemove(List<SkyKey> toCheck, List<SkyKey> toRemove) {
+      this.toCheck = toCheck;
+      this.toRemove = Preconditions.checkNotNull(toRemove);
+    }
+
+    static RDepsToCheckAndRemove justRemove(List<SkyKey> toRemove) {
+      return new RDepsToCheckAndRemove(null, toRemove);
+    }
+
+    static RDepsToCheckAndRemove replaceRemove(
+        RDepsToCheckAndRemove original, List<SkyKey> toRemove) {
+      return new RDepsToCheckAndRemove(original.toCheck, toRemove);
+    }
+
+    static RDepsToCheckAndRemove replaceCheck(
+        RDepsToCheckAndRemove original, List<SkyKey> toCheck) {
+      return new RDepsToCheckAndRemove(toCheck, original.toRemove);
+    }
+  }
+
+  private static DataState getDataState(Object reverseDepsToCheckAndRemove) {
+    if (reverseDepsToCheckAndRemove == null) {
+      return DataState.NULL;
+    } else if (reverseDepsToCheckAndRemove instanceof List) {
+      return DataState.CHECK_ONLY;
+    } else {
+      Preconditions.checkState(
+          reverseDepsToCheckAndRemove instanceof RDepsToCheckAndRemove,
+          reverseDepsToCheckAndRemove);
+      return DataState.BOTH;
+    }
+  }
+
+  private void setReverseDepsToRemove(T container, List<SkyKey> toRemove) {
+    Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+    switch (getDataState(reverseDepsToCheckAndRemove)) {
+      case NULL:
+        reverseDepsToCheckAndRemove = RDepsToCheckAndRemove.justRemove(toRemove);
+        break;
+      case CHECK_ONLY:
+        reverseDepsToCheckAndRemove =
+            new RDepsToCheckAndRemove(((List<SkyKey>) reverseDepsToCheckAndRemove), toRemove);
+        break;
+      case BOTH:
+        reverseDepsToCheckAndRemove =
+            RDepsToCheckAndRemove.replaceRemove(
+                (RDepsToCheckAndRemove) reverseDepsToCheckAndRemove, toRemove);
+        break;
+      default:
+        throw new IllegalStateException(container + ", " + toRemove);
+    }
+    setDataToConsolidate(container, reverseDepsToCheckAndRemove);
+  }
+
+  private void setReverseDepsToCheck(T container, List<SkyKey> toCheck) {
+    Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+    switch (getDataState(reverseDepsToCheckAndRemove)) {
+      case NULL:
+      case CHECK_ONLY:
+        reverseDepsToCheckAndRemove = toCheck;
+        break;
+      case BOTH:
+        reverseDepsToCheckAndRemove =
+            RDepsToCheckAndRemove.replaceCheck(
+                (RDepsToCheckAndRemove) reverseDepsToCheckAndRemove, toCheck);
+        break;
+      default:
+        throw new IllegalStateException(container + ", " + toCheck);
+    }
+    setDataToConsolidate(container, reverseDepsToCheckAndRemove);
+  }
+
+  @Nullable
+  private List<SkyKey> getReverseDepsToRemove(T container) {
+    Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+    switch (getDataState(reverseDepsToCheckAndRemove)) {
+      case NULL:
+      case CHECK_ONLY:
+        return null;
+      case BOTH:
+        return ((RDepsToCheckAndRemove) reverseDepsToCheckAndRemove).toRemove;
+      default:
+        throw new IllegalStateException(reverseDepsToCheckAndRemove.toString());
+    }
+  }
+
+  @Nullable
+  private List<SkyKey> getReverseDepsToCheck(T container) {
+    Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+    switch (getDataState(reverseDepsToCheckAndRemove)) {
+      case NULL:
+        return null;
+      case CHECK_ONLY:
+        return (List<SkyKey>) reverseDepsToCheckAndRemove;
+      case BOTH:
+        return ((RDepsToCheckAndRemove) reverseDepsToCheckAndRemove).toCheck;
+      default:
+        throw new IllegalStateException(reverseDepsToCheckAndRemove.toString());
+    }
+  }
 
   /**
    * We check that the reverse dependency is not already present. We only do that if reverseDeps is
@@ -60,15 +177,22 @@ public abstract class ReverseDepsUtil<T> {
    */
   void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep) {
     if (isSingleReverseDep(container)) {
-      Preconditions.checkState(!getReverseDepsObject(container).equals(reverseDep),
-          "Reverse dep %s already present", reverseDep);
+      Preconditions.checkState(
+          !getReverseDepsObject(container).equals(reverseDep),
+          "Reverse dep %s already present in %s",
+          reverseDep,
+          container);
       return;
     }
     @SuppressWarnings("unchecked")
     List<SkyKey> asList = (List<SkyKey>) getReverseDepsObject(container);
     if (asList.size() < MAYBE_CHECK_THRESHOLD) {
-      Preconditions.checkState(!asList.contains(reverseDep), "Reverse dep %s already present"
-          + " in %s", reverseDep, asList);
+      Preconditions.checkState(
+          !asList.contains(reverseDep),
+          "Reverse dep %s already present in %s for %s",
+          reverseDep,
+          asList,
+          container);
     }
   }
 
@@ -106,9 +230,29 @@ public abstract class ReverseDepsUtil<T> {
     }
   }
 
-  boolean reverseDepsIsEmpty(T container) {
-    return !isSingleReverseDep(container)
-        && ((List<SkyKey>) getReverseDepsObject(container)).isEmpty();
+  void checkReverseDep(T container, SkyKey reverseDep) {
+    Object reverseDepsObject = getReverseDepsObject(container);
+    if (isSingleReverseDep(container)) {
+      Preconditions.checkState(
+          reverseDepsObject.equals(reverseDep),
+          "%s %s %s",
+          reverseDep,
+          reverseDepsObject,
+          container);
+      return;
+    }
+    List<SkyKey> asList = (List<SkyKey>) reverseDepsObject;
+    if (asList.size() < MAYBE_CHECK_THRESHOLD) {
+      Preconditions.checkState(
+          asList.contains(reverseDep), "%s not in %s for %s", reverseDep, asList, container);
+    } else {
+      List<SkyKey> reverseDepsToCheck = getReverseDepsToCheck(container);
+      if (reverseDepsToCheck == null) {
+        reverseDepsToCheck = new ArrayList<>();
+        setReverseDepsToCheck(container, reverseDepsToCheck);
+      }
+      reverseDepsToCheck.add(reverseDep);
+    }
   }
 
   /**
@@ -122,7 +266,7 @@ public abstract class ReverseDepsUtil<T> {
           "toRemove: %s container: %s",
           reverseDep,
           container);
-        overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
+      overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
       return;
     }
     @SuppressWarnings("unchecked")
@@ -138,7 +282,7 @@ public abstract class ReverseDepsUtil<T> {
   }
 
   ImmutableSet<SkyKey> getReverseDeps(T container) {
-    consolidateReverseDepsRemovals(container);
+    consolidateData(container);
 
     // TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side
     // wrt. thread-safety. The parents of a node get modified when any of the parents is deleted,
@@ -155,19 +299,38 @@ public abstract class ReverseDepsUtil<T> {
     }
   }
 
-  void consolidateReverseDepsRemovals(T container) {
-    List<SkyKey> reverseDepsToRemove = getReverseDepsToRemove(container);
+  void consolidateData(T container) {
     Object reverseDeps = getReverseDepsObject(container);
+    List<SkyKey> reverseDepsToRemove = getReverseDepsToRemove(container);
+    List<SkyKey> reverseDepsToCheck = getReverseDepsToCheck(container);
+    if (reverseDepsToRemove == null && reverseDepsToCheck == null) {
+      return;
+    }
+    Preconditions.checkState(
+        !isSingleReverseDep(container),
+        "We do not delay removals/checks for single lists: %s %s %s",
+        container,
+        reverseDepsToRemove,
+        reverseDepsToCheck);
+    @SuppressWarnings("unchecked")
+    List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
+    // Should not happen, as we only create reverseDepsToRemove/Check in case we have at least one
+    // reverse dep to remove/check.
+    Preconditions.checkState(
+        !reverseDepsAsList.isEmpty(),
+        "Could not do delayed removal/check for %s elements from %s.\n"
+            + "Reverse deps to check: %s. Container: %s",
+        reverseDepsToRemove,
+        reverseDeps,
+        reverseDepsToCheck,
+        container);
     if (reverseDepsToRemove == null) {
+      Set<SkyKey> reverseDepsAsSet = new HashSet<>(reverseDepsAsList);
+      Preconditions.checkState(
+          reverseDepsAsSet.containsAll(reverseDepsToCheck), "%s %s", reverseDepsToCheck, container);
+      setDataToConsolidate(container, null);
       return;
     }
-    Preconditions.checkState(!isSingleReverseDep(container),
-        "We do not use reverseDepsToRemove for single lists: %s", container);
-    // Should not happen, as we only create reverseDepsToRemove in case we have at least one
-    // reverse dep to remove.
-    Preconditions.checkState((!((List<?>) reverseDeps).isEmpty()),
-        "Could not remove %s elements from %s.\nReverse deps to remove: %s. %s",
-        reverseDepsToRemove.size(), reverseDeps, reverseDepsToRemove, container);
 
     Set<SkyKey> toRemove = Sets.newHashSet(reverseDepsToRemove);
     int expectedRemovals = toRemove.size();
@@ -175,12 +338,13 @@ public abstract class ReverseDepsUtil<T> {
         "A reverse dependency tried to remove itself twice: %s. %s", reverseDepsToRemove,
         container);
 
-    @SuppressWarnings("unchecked")
-    List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
+    Set<SkyKey> toCheck =
+        reverseDepsToCheck == null ? new HashSet<SkyKey>() : new HashSet<>(reverseDepsToCheck);
     List<SkyKey> newReverseDeps = Lists
         .newArrayListWithExpectedSize(Math.max(0, reverseDepsAsList.size() - expectedRemovals));
 
     for (SkyKey reverseDep : reverseDepsAsList) {
+      toCheck.remove(reverseDep);
       if (!toRemove.contains(reverseDep)) {
         newReverseDeps.add(reverseDep);
       }
@@ -188,6 +352,7 @@ public abstract class ReverseDepsUtil<T> {
     Preconditions.checkState(newReverseDeps.size() == reverseDepsAsList.size() - expectedRemovals,
         "Could not remove some elements from %s.\nReverse deps to remove: %s. %s", reverseDeps,
         toRemove, container);
+    Preconditions.checkState(toCheck.isEmpty(), "%s %s", toCheck, container);
 
     if (newReverseDeps.isEmpty()) {
       overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
@@ -196,14 +361,14 @@ public abstract class ReverseDepsUtil<T> {
     } else {
       overwriteReverseDepsList(container, newReverseDeps);
     }
-    setReverseDepsToRemove(container, null);
+    setDataToConsolidate(container, null);
   }
 
   String toString(T container) {
     return MoreObjects.toStringHelper("ReverseDeps")
         .add("reverseDeps", getReverseDepsObject(container))
         .add("singleReverseDep", isSingleReverseDep(container))
-        .add("reverseDepsToRemove", getReverseDepsToRemove(container))
+        .add("dataToConsolidate", getDataToConsolidate(container))
         .toString();
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
index 661b52141d..8cd16f0695 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
@@ -49,6 +49,15 @@ public interface ThinNodeEntry {
   void removeReverseDep(SkyKey reverseDep);
 
   /**
+   * Removes a reverse dependency.
+   *
+   * <p>May only be called if this entry is not done (i.e. {@link #isDone} is false) and
+   * {@param reverseDep} is present in {@link #getReverseDeps}
+   */
+  @ThreadSafe
+  void removeInProgressReverseDep(SkyKey reverseDep);
+
+  /**
    * Returns a copy of the set of reverse dependencies. Note that this introduces a potential
    * check-then-act race; {@link #removeReverseDep} may fail for a key that is returned here.
    */
@@ -80,11 +89,11 @@ public interface ThinNodeEntry {
    * the caller will only ever want to call {@code markDirty()} a second time if a transition from a
    * dirty-unchanged state to a dirty-changed state is required.
    *
-   * @return The direct deps of this entry, or null if the entry has already been marked
-   * dirty. In the latter case, the caller should abort its handling of this node, since another
-   * thread is already dealing with it.
+   * @return true if the node was previously clean, and false if it was already dirty. If it was
+   * already dirty, the caller should abort its handling of this node, since another thread is
+   * already dealing with it.
    */
   @Nullable
   @ThreadSafe
-  Iterable<SkyKey> markDirty(boolean isChanged);
+  boolean markDirty(boolean isChanged);
 }
diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
index 2c4e861d75..b8c46b6537 100644
--- a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
@@ -69,7 +70,7 @@ public class DeterministicInMemoryGraph extends NotifyingInMemoryGraph {
     @Override
     public synchronized Collection<SkyKey> getReverseDeps() {
       TreeSet<SkyKey> result = new TreeSet<>(ALPHABETICAL_SKYKEY_COMPARATOR);
-      result.addAll(super.getReverseDeps());
+      Iterables.addAll(result, super.getReverseDeps());
       return result;
     }
 
diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
index 623e08874c..5b5790fdee 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -126,6 +126,10 @@ public class EagerInvalidatorTest {
     throw new UnsupportedOperationException("Sublcasses must override");
   }
 
+  protected boolean reverseDepsPresent() {
+    throw new UnsupportedOperationException("Subclasses must override");
+  }
+
   // Convenience method for eval-ing a single value.
   protected SkyValue eval(boolean keepGoing, SkyKey key) throws InterruptedException {
     SkyKey[] keys = { key };
@@ -349,10 +353,20 @@ public class EagerInvalidatorTest {
     assertTrue(isInvalidated(skyKey("ab")));
     assertTrue(isInvalidated(skyKey("abc")));
 
-    // The reverse deps to ab and ab_c should have been removed.
-    assertThat(graph.get(skyKey("a")).getReverseDeps()).isEmpty();
-    assertThat(graph.get(skyKey("b")).getReverseDeps()).containsExactly(skyKey("bc"));
-    assertThat(graph.get(skyKey("c")).getReverseDeps()).containsExactly(skyKey("bc"));
+    // The reverse deps to ab and ab_c should have been removed if reverse deps are cleared.
+    Set<SkyKey> reverseDeps = new HashSet<>();
+    if (reverseDepsPresent()) {
+      reverseDeps.add(skyKey("ab"));
+    }
+    assertThat(graph.get(skyKey("a")).getReverseDeps()).containsExactlyElementsIn(reverseDeps);
+    reverseDeps.add(skyKey("bc"));
+    assertThat(graph.get(skyKey("b")).getReverseDeps()).containsExactlyElementsIn(reverseDeps);
+    reverseDeps.clear();
+    if (reverseDepsPresent()) {
+      reverseDeps.add(skyKey("ab_c"));
+    }
+    reverseDeps.add(skyKey("bc"));
+    assertThat(graph.get(skyKey("c")).getReverseDeps()).containsExactlyElementsIn(reverseDeps);
   }
 
   @Test
@@ -612,6 +626,11 @@ public class EagerInvalidatorTest {
       return InvalidationType.DELETED;
     }
 
+    @Override
+    protected boolean reverseDepsPresent() {
+      return false;
+    }
+
     @Test
     public void dirtyKeyTrackerWorksWithDeletingInvalidator() throws Exception {
       setupInvalidatableGraph();
@@ -628,7 +647,7 @@ public class EagerInvalidatorTest {
       Iterable<SkyKey> diff = ImmutableList.of(skyKey("a"));
       Preconditions.checkNotNull(EagerInvalidator.createDeletingVisitorIfNeeded(graph, diff,
           receiver, state, true, dirtyKeyTracker)).run();
-      assertThat(dirtyKeyTracker.getDirtyKeys()).containsExactly(skyKey("ab"));
+      assertThat(dirtyKeyTracker.getDirtyKeys()).isEmpty();
     }
   }
 
@@ -670,6 +689,11 @@ public class EagerInvalidatorTest {
       return InvalidationType.CHANGED;
     }
 
+    @Override
+    protected boolean reverseDepsPresent() {
+      return true;
+    }
+
     @Test
     public void dirtyKeyTrackerWorksWithDirtyingInvalidator() throws Exception {
       setupInvalidatableGraph();
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 cf28aa81d9..9ad015922a 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
@@ -43,6 +43,7 @@ import java.util.Set;
 import java.util.concurrent.CountDownLatch;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
+import java.util.concurrent.TimeUnit;
 
 /** Base class for concurrency sanity tests on {@link EvaluableGraph} implementations. */
 public abstract class GraphConcurrencyTest {
@@ -85,58 +86,59 @@ public abstract class GraphConcurrencyTest {
     final NodeEntry entry = graph.createIfAbsent(key);
     // These numbers are arbitrary.
     int numThreads = 50;
-    int numKeys = 100;
+    int numKeys = numThreads;
     // One chunk will be used to add and remove rdeps before setting the node value.  The second
     // chunk of work will have the node value set and the last chunk will be to add and remove
     // rdeps after the value has been set.
     final int chunkSize = 40;
-    final int numIterations = chunkSize * 3;
+    final int numIterations = chunkSize * 2;
     // This latch is used to signal that the runnables have been submitted to the executor.
-    final CountDownLatch countDownLatch1 = new CountDownLatch(1);
+    final CountDownLatch waitForStart = new CountDownLatch(1);
     // This latch is used to signal to the main thread that we have begun the second chunk
     // for sufficiently many keys.  The minimum of numThreads and numKeys is used to prevent
     // thread starvation from causing a delay here.
-    final CountDownLatch countDownLatch2 = new CountDownLatch(Math.min(numThreads, numKeys));
+    final CountDownLatch waitForAddedRdep = new CountDownLatch(numThreads);
     // This latch is used to guarantee that we set the node's value before we enter the third
     // chunk for any key.
-    final CountDownLatch countDownLatch3 = new CountDownLatch(1);
+    final CountDownLatch waitForSetValue = new CountDownLatch(1);
     ExecutorService pool = Executors.newFixedThreadPool(numThreads);
     // Add single rdep before transition to done.
     assertEquals(DependencyState.NEEDS_SCHEDULING, entry.addReverseDepAndCheckIfDone(key("rdep")));
     for (int i = 0; i < numKeys; i++) {
       final int j = i;
-      Runnable r = new Runnable() {
-        @Override
-        public void run() {
-          try {
-            countDownLatch1.await();
-            // Add and remove the rdep a bunch of times to test interleaving.
-            for (int k = 1; k <= numIterations; k++) {
-              if (k == chunkSize) {
-                countDownLatch2.countDown();
+      Runnable r =
+          new Runnable() {
+            @Override
+            public void run() {
+              try {
+                // Add and remove the rdep a bunch of times to test interleaving.
+                waitForStart.await(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
+                for (int k = 1; k < chunkSize; k++) {
+                  assertThat(entry.addReverseDepAndCheckIfDone(key("rdep" + j)))
+                      .isNotEqualTo(DependencyState.DONE);
+                  entry.removeInProgressReverseDep(key("rdep" + j));
+                  assertThat(entry.getInProgressReverseDeps()).doesNotContain(key("rdep" + j));
+                }
+                assertThat(entry.addReverseDepAndCheckIfDone(key("rdep" + j)))
+                    .isNotEqualTo(DependencyState.DONE);
+                waitForAddedRdep.countDown();
+                waitForSetValue.await(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
+              } catch (InterruptedException e) {
+                fail("Test failed: " + e.toString());
               }
-              entry.addReverseDepAndCheckIfDone(key("rdep" + j));
-              entry.removeReverseDep(key("rdep" + j));
-              if (k == chunkSize * 2) {
-                countDownLatch3.await();
+              for (int k = chunkSize; k <= numIterations; k++) {
+                entry.removeReverseDep(key("rdep" + j));
+                entry.addReverseDepAndCheckIfDone(key("rdep" + j));
+                entry.getReverseDeps();
               }
             }
-            entry.addReverseDepAndCheckIfDone(key("rdep" + j));
-          } catch (InterruptedException e) {
-            fail("Test failed: " + e.toString());
-          }
-        }
-      };
+          };
       pool.execute(wrapper.wrap(r));
     }
-    countDownLatch1.countDown();
-    try {
-      countDownLatch2.await();
-    } catch (InterruptedException e) {
-      fail("Test failed: " + e.toString());
-    }
+    waitForStart.countDown();
+    waitForAddedRdep.await(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
     entry.setValue(new StringValue("foo1"), startingVersion);
-    countDownLatch3.countDown();
+    waitForSetValue.countDown();
     entry.removeReverseDep(key("rdep"));
     wrapper.waitForTasksAndMaybeThrow();
     assertFalse(ExecutorUtil.interruptibleShutdown(pool));
@@ -148,6 +150,7 @@ public abstract class GraphConcurrencyTest {
     // Mark the node as dirty again and check that the reverse deps have been preserved.
     sameEntry.markDirty(true);
     startEvaluation(sameEntry);
+    sameEntry.markRebuildingAndGetAllRemainingDirtyDirectDeps();
     sameEntry.setValue(new StringValue("foo2"), startingVersion.next());
     assertEquals(new StringValue("foo2"), graph.get(key).getValue());
     assertEquals(numKeys, Iterables.size(graph.get(key).getReverseDeps()));
@@ -253,6 +256,7 @@ public abstract class GraphConcurrencyTest {
               entry.markDirty(true);
               // Make some changes, like adding a dep and rdep.
               entry.addReverseDepAndCheckIfDone(key("rdep"));
+              entry.markRebuildingAndGetAllRemainingDirtyDirectDeps();
               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 1976766719..b598bf8f19 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -98,8 +98,8 @@ public class InMemoryNodeEntryTest {
     SkyKey mother = key("mother");
     SkyKey father = key("father");
     assertEquals(DependencyState.NEEDS_SCHEDULING, entry.addReverseDepAndCheckIfDone(mother));
-    assertEquals(DependencyState.ADDED_DEP, entry.addReverseDepAndCheckIfDone(null));
-    assertEquals(DependencyState.ADDED_DEP, entry.addReverseDepAndCheckIfDone(father));
+    assertEquals(DependencyState.ALREADY_EVALUATING, entry.addReverseDepAndCheckIfDone(null));
+    assertEquals(DependencyState.ALREADY_EVALUATING, entry.addReverseDepAndCheckIfDone(father));
     assertThat(setValue(entry, new SkyValue() {},
         /*errorInfo=*/null, /*graphVersion=*/0L)).containsExactly(mother, father);
     assertThat(entry.getReverseDeps()).containsExactly(mother, father);
@@ -197,6 +197,7 @@ public class InMemoryNodeEntryTest {
     entry.signalDep();
     assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
     assertTrue(entry.isReady());
+    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
     assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
         /*graphVersion=*/1L)).containsExactly(parent);
   }
@@ -218,9 +219,10 @@ public class InMemoryNodeEntryTest {
     assertTrue(entry.isReady());
     SkyKey parent = key("parent");
     entry.addReverseDepAndCheckIfDone(parent);
-    assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+    assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
     assertTrue(entry.isReady());
     assertThat(entry.getTemporaryDirectDeps()).isEmpty();
+    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).containsExactly(dep);
     assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
         /*graphVersion=*/1L)).containsExactly(parent);
     assertEquals(new IntVersion(1L), entry.getVersion());
@@ -409,8 +411,9 @@ public class InMemoryNodeEntryTest {
     assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(new IntVersion(1L));
-    assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+    assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
     assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
+    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
     setValue(entry, new IntegerValue(5), /*errorInfo=*/null, /*graphVersion=*/1L);
     assertTrue(entry.isDone());
     assertEquals(new IntVersion(0L), entry.getVersion());
@@ -438,11 +441,12 @@ public class InMemoryNodeEntryTest {
     assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(new IntVersion(1L));
-    assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+    assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
     assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
     ReifiedSkyFunctionException exception = new ReifiedSkyFunctionException(
         new GenericFunctionException(new SomeErrorException("oops"), Transience.PERSISTENT),
         key("cause"));
+    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
     setValue(entry, new IntegerValue(5), new ErrorInfo(exception),
         /*graphVersion=*/1L);
     assertTrue(entry.isDone());
@@ -467,8 +471,9 @@ public class InMemoryNodeEntryTest {
     assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(new IntVersion(1L));
-    assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+    assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
     assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
+    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
     setValue(entry, /*value=*/null, errorInfo, /*graphVersion=*/1L);
     assertTrue(entry.isDone());
     assertEquals(new IntVersion(0L), entry.getVersion());
@@ -542,8 +547,9 @@ public class InMemoryNodeEntryTest {
     assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
     addTemporaryDirectDep(entry, dep);
     assertTrue(entry.signalDep(new IntVersion(1L)));
-    assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+    assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
     assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
+    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
     addTemporaryDirectDep(entry, key("dep2"));
     assertTrue(entry.signalDep(new IntVersion(1L)));
     setValue(entry, new IntegerValue(5), /*errorInfo=*/null, /*graphVersion=*/1L);
@@ -586,7 +592,8 @@ public class InMemoryNodeEntryTest {
     entry.markDirty(/*isChanged=*/true);
     SkyKey newParent = key("new parent");
     entry.addReverseDepAndCheckIfDone(newParent);
-    assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+    assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
+    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
     assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
         /*graphVersion=*/1L)).containsExactly(newParent);
   }
@@ -612,6 +619,8 @@ public class InMemoryNodeEntryTest {
     SkyKey newChild = key("newchild");
     addTemporaryDirectDep(clone2, newChild);
     clone2.signalDep();
+    assertThat(clone2.markRebuildingAndGetAllRemainingDirtyDirectDeps())
+        .containsExactly(originalChild);
     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 ffb5bf8b62..348f5c0d59 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -840,6 +840,43 @@ public class MemoizingEvaluatorTest {
     assertThat(cycleInfo.getPathToCycle()).containsExactly(cycleKey2).inOrder();
   }
 
+  @Test
+  public void cycleAndSelfEdgeWithDirtyValueInSameGroup() throws Exception {
+    setGraphForTesting(new DeterministicInMemoryGraph());
+    final SkyKey cycleKey1 = GraphTester.toSkyKey("zcycleKey1");
+    final SkyKey cycleKey2 = GraphTester.toSkyKey("acycleKey2");
+    tester.getOrCreate(cycleKey2).addDependency(cycleKey2).setComputedValue(CONCATENATE);
+    tester
+        .getOrCreate(cycleKey1)
+        .setBuilder(
+            new SkyFunction() {
+              @Nullable
+              @Override
+              public SkyValue compute(SkyKey skyKey, Environment env)
+                  throws SkyFunctionException, InterruptedException {
+                Map<SkyKey, SkyValue> result =
+                    env.getValues(ImmutableList.of(cycleKey1, cycleKey2));
+                Preconditions.checkState(env.valuesMissing(), result);
+                return null;
+              }
+
+              @Nullable
+              @Override
+              public String extractTag(SkyKey skyKey) {
+                return null;
+              }
+            });
+    // Evaluate twice to make sure nothing strange happens with invalidation the second time.
+    for (int i = 0; i < 2; i++) {
+      EvaluationResult<SkyValue> result = tester.eval(/*keepGoing=*/ true, cycleKey1);
+      assertEquals(null, result.get(cycleKey1));
+      ErrorInfo errorInfo = result.getError(cycleKey1);
+      CycleInfo cycleInfo = Iterables.getOnlyElement(errorInfo.getCycleInfo());
+      assertThat(cycleInfo.getCycle()).containsExactly(cycleKey1).inOrder();
+      assertThat(cycleInfo.getPathToCycle()).isEmpty();
+    }
+  }
+
   /** Regression test: "crash in cycle checker with dirty values". */
   @Test
   public void cycleWithDirtyValue() throws Exception {
@@ -1587,6 +1624,70 @@ public class MemoizingEvaluatorTest {
   }
 
   @Test
+  public void removeReverseDepFromRebuildingNode() throws Exception {
+    SkyKey topKey = GraphTester.skyKey("top");
+    final SkyKey midKey = GraphTester.skyKey("mid");
+    final SkyKey changedKey = GraphTester.skyKey("changed");
+    tester.getOrCreate(changedKey).setConstantValue(new StringValue("first"));
+    // When top depends on mid,
+    tester.getOrCreate(topKey).addDependency(midKey).setComputedValue(CONCATENATE);
+    // And mid depends on changed,
+    tester.getOrCreate(midKey).addDependency(changedKey).setComputedValue(CONCATENATE);
+    final CountDownLatch changedKeyStarted = new CountDownLatch(1);
+    final CountDownLatch changedKeyCanFinish = new CountDownLatch(1);
+    final AtomicBoolean controlTiming = new AtomicBoolean(false);
+    setGraphForTesting(
+        new NotifyingInMemoryGraph(
+            new Listener() {
+              @Override
+              public void accept(SkyKey key, EventType type, Order order, Object context) {
+                if (!controlTiming.get()) {
+                  return;
+                }
+                if (key.equals(midKey)
+                    && type == EventType.CHECK_IF_DONE
+                    && order == Order.BEFORE) {
+                  TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions(
+                      changedKeyStarted, "changed key didn't start");
+                } else if (key.equals(changedKey)
+                    && type == EventType.REMOVE_REVERSE_DEP
+                    && order == Order.AFTER
+                    && midKey.equals(context)) {
+                  changedKeyCanFinish.countDown();
+                }
+              }
+            }));
+    // Then top builds as expected.
+    assertThat(tester.evalAndGet(/*keepGoing=*/ false, topKey)).isEqualTo(new StringValue("first"));
+    // When changed is modified,
+    tester
+        .getOrCreate(changedKey, /*markAsModified=*/ true)
+        .setConstantValue(null)
+        .setBuilder(
+            // And changed is not allowed to finish building until it is released,
+            new ChainedFunction(
+                changedKeyStarted,
+                changedKeyCanFinish,
+                null,
+                false,
+                new StringValue("second"),
+                ImmutableList.<SkyKey>of()));
+    // And mid is independently marked as modified,
+    tester.getOrCreate(midKey, /*markAsModified=*/ true);
+    tester.invalidate();
+    SkyKey newTopKey = GraphTester.skyKey("newTop");
+    // And changed will start rebuilding independently of midKey, because it's requested directly by
+    // newTop
+    tester.getOrCreate(newTopKey).addDependency(changedKey).setComputedValue(CONCATENATE);
+    // And we control the timing using the graph listener above to make sure that:
+    // (1) before we do anything with mid, changed has already started, and
+    // (2) changed key can't finish until mid tries to remove its reverse dep from changed,
+    controlTiming.set(true);
+    // Then this evaluation completes without crashing.
+    tester.eval(/*keepGoing=*/ false, newTopKey, topKey);
+  }
+
+  @Test
   public void dirtyThenDeleted() throws Exception {
     initializeTester();
     SkyKey topKey = GraphTester.skyKey("top");
@@ -1616,15 +1717,24 @@ public class MemoizingEvaluatorTest {
     // leaf4 should not built in the second build.
     final SkyKey leaf4 = GraphTester.toSkyKey("leaf4");
     final AtomicBoolean shouldNotBuildLeaf4 = new AtomicBoolean(false);
-    setGraphForTesting(new NotifyingInMemoryGraph(new Listener() {
-      @Override
-      public void accept(SkyKey key, EventType type, Order order, Object context) {
-        if (shouldNotBuildLeaf4.get() && key.equals(leaf4)) {
-          throw new IllegalStateException("leaf4 should not have been considered this build: "
-              + type + ", " + order + ", " + context);
-        }
-      }
-    }));
+    setGraphForTesting(
+        new NotifyingInMemoryGraph(
+            new Listener() {
+              @Override
+              public void accept(SkyKey key, EventType type, Order order, Object context) {
+                if (shouldNotBuildLeaf4.get()
+                    && key.equals(leaf4)
+                    && type != EventType.REMOVE_REVERSE_DEP) {
+                  throw new IllegalStateException(
+                      "leaf4 should not have been considered this build: "
+                          + type
+                          + ", "
+                          + order
+                          + ", "
+                          + context);
+                }
+              }
+            }));
     tester.set(leaf4, new StringValue("leaf4"));
 
     // Create leaf0, leaf1 and leaf2 values with values "leaf2", "leaf3", "leaf4" respectively.
@@ -2548,10 +2658,10 @@ public class MemoizingEvaluatorTest {
     tester.getOrCreate(topKey).addDependency(midKey).setComputedValue(CONCATENATE);
     tester.getOrCreate(midKey).addDependency(badKey).setComputedValue(CONCATENATE);
     tester.getOrCreate(badKey).setHasError(true);
-    EvaluationResult<SkyValue> result = tester.eval(/*keepGoing=*/false, topKey, midKey);
+    EvaluationResult<SkyValue> result = tester.eval(/*keepGoing=*/ false, topKey, midKey);
     assertThat(result.getError(midKey).getRootCauses()).containsExactly(badKey);
     // Do it again with keepGoing.  We should also see an error for the top key this time.
-    result = tester.eval(/*keepGoing=*/true, topKey, midKey);
+    result = tester.eval(/*keepGoing=*/ true, topKey, midKey);
     assertThat(result.getError(midKey).getRootCauses()).containsExactly(badKey);
     assertThat(result.getError(topKey).getRootCauses()).containsExactly(badKey);
   }
@@ -2566,13 +2676,13 @@ public class MemoizingEvaluatorTest {
         .addErrorDependency(errorKey, new StringValue("recovered"))
         .setComputedValue(CONCATENATE);
     // When the error value throws, the propagation will cause an interrupted exception in parent.
-    EvaluationResult<StringValue> result = tester.eval(/*keepGoing=*/false, parentKey);
+    EvaluationResult<StringValue> result = tester.eval(/*keepGoing=*/ false, parentKey);
     assertThat(result.keyNames()).isEmpty();
     Map.Entry<SkyKey, ErrorInfo> error = Iterables.getOnlyElement(result.errorMap().entrySet());
     assertEquals(parentKey, error.getKey());
     assertThat(error.getValue().getRootCauses()).containsExactly(errorKey);
     assertFalse(Thread.interrupted());
-    result = tester.eval(/*keepGoing=*/true, parentKey);
+    result = tester.eval(/*keepGoing=*/ true, parentKey);
     assertThat(result.errorMap()).isEmpty();
     assertEquals("recovered", result.get(parentKey).getValue());
   }
@@ -2624,10 +2734,10 @@ public class MemoizingEvaluatorTest {
     tester.getOrCreate(topKey).addDependency(midKey).setComputedValue(CONCATENATE);
     tester.getOrCreate(midKey).addDependency(badKey).setComputedValue(CONCATENATE);
     tester.getOrCreate(badKey).setHasError(true);
-    EvaluationResult<SkyValue> result = tester.eval(/*keepGoing=*/false, topKey, midKey);
+    EvaluationResult<SkyValue> result = tester.eval(/*keepGoing=*/ false, topKey, midKey);
     assertThat(result.getError(midKey).getRootCauses()).containsExactly(badKey);
     waitForSecondCall.set(true);
-    result = tester.eval(/*keepGoing=*/true, topKey, midKey);
+    result = tester.eval(/*keepGoing=*/ true, topKey, midKey);
     assertNotNull(firstThread.get());
     assertEquals(0, otherThreadWinning.getCount());
     assertThat(result.getError(midKey).getRootCauses()).containsExactly(badKey);
@@ -2645,12 +2755,12 @@ public class MemoizingEvaluatorTest {
         .addErrorDependency(errorKey, new StringValue("recovered"))
         .setComputedValue(CONCATENATE)
         .addDependency("after");
-    EvaluationResult<StringValue> result = tester.eval(/*keepGoing=*/false, parentKey);
+    EvaluationResult<StringValue> result = tester.eval(/*keepGoing=*/ false, parentKey);
     assertThat(result.keyNames()).isEmpty();
     Map.Entry<SkyKey, ErrorInfo> error = Iterables.getOnlyElement(result.errorMap().entrySet());
     assertEquals(parentKey, error.getKey());
     assertThat(error.getValue().getRootCauses()).containsExactly(errorKey);
-    result = tester.eval(/*keepGoing=*/true, parentKey);
+    result = tester.eval(/*keepGoing=*/ true, parentKey);
     assertThat(result.errorMap()).isEmpty();
     assertEquals("recoveredafter", result.get(parentKey).getValue());
   }
@@ -2741,7 +2851,7 @@ public class MemoizingEvaluatorTest {
 
     // When the graph is evaluated in noKeepGoing mode,
     EvaluationResult<StringValue> result =
-        tester.eval(/*keepGoing=*/false, errorKey, otherErrorKey);
+        tester.eval(/*keepGoing=*/ false, errorKey, otherErrorKey);
 
     // Then the result reports that an error occurred because of errorKey,
     assertTrue(result.hasError());
@@ -3398,6 +3508,68 @@ public class MemoizingEvaluatorTest {
     }
   }
 
+  @Test
+  public void cleanReverseDepFromDirtyNodeNotInBuild() throws Exception {
+    final SkyKey topKey = GraphTester.skyKey("top");
+    SkyKey inactiveKey = GraphTester.skyKey("inactive");
+    final Thread mainThread = Thread.currentThread();
+    final AtomicBoolean shouldInterrupt = new AtomicBoolean(false);
+    NotifyingInMemoryGraph graph =
+        new NotifyingInMemoryGraph(
+            new Listener() {
+              @Override
+              public void accept(SkyKey key, EventType type, Order order, Object context) {
+                if (shouldInterrupt.get()
+                    && key.equals(topKey)
+                    && type == EventType.IS_READY
+                    && order == Order.BEFORE) {
+                  mainThread.interrupt();
+                  shouldInterrupt.set(false);
+                  try {
+                    // Make sure threadpool propagates interrupt.
+                    Thread.sleep(TestUtils.WAIT_TIMEOUT_MILLISECONDS);
+                  } catch (InterruptedException e) {
+                    Thread.currentThread().interrupt();
+                  }
+                }
+              }
+            });
+    setGraphForTesting(graph);
+    // When top depends on inactive,
+    tester.getOrCreate(topKey).addDependency(inactiveKey).setComputedValue(COPY);
+    StringValue val = new StringValue("inactive");
+    // And inactive is constant,
+    tester.set(inactiveKey, val);
+    // Then top evaluates normally.
+    assertThat(tester.evalAndGet(/*keepGoing=*/ true, topKey)).isEqualTo(val);
+    // When evaluation will be interrupted as soon as top starts evaluating,
+    shouldInterrupt.set(true);
+    // And inactive is dirty,
+    tester.getOrCreate(inactiveKey, /*markAsModified=*/ true);
+    // And so is top,
+    tester.getOrCreate(topKey, /*markAsModified=*/ true);
+    tester.invalidate();
+    try {
+      // Then evaluation is interrupted,
+      tester.eval(/*keepGoing=*/ false, topKey);
+      fail();
+    } catch (InterruptedException e) {
+      // Expected.
+    }
+    // But inactive is still present,
+    assertThat(graph.get(inactiveKey)).isNotNull();
+    // And still dirty,
+    assertThat(graph.get(inactiveKey).isDirty()).isTrue();
+    // And re-evaluates successfully,
+    assertThat(tester.evalAndGet(/*keepGoing=*/ true, inactiveKey)).isEqualTo(val);
+    // But top is gone from the graph,
+    assertThat(graph.get(topKey)).isNull();
+    // And we can successfully invalidate and re-evaluate inactive again.
+    tester.getOrCreate(inactiveKey, /*markAsModified=*/ true);
+    tester.invalidate();
+    assertThat(tester.evalAndGet(/*keepGoing=*/ true, inactiveKey)).isEqualTo(val);
+  }
+
   /**
    * A graph tester that is specific to the memoizing evaluator, with some convenience methods.
    */
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
index 53f6ebffa5..bbed5ba756 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
@@ -89,13 +89,17 @@ public class NotifyingInMemoryGraph extends InMemoryGraph {
   public enum EventType {
     CREATE_IF_ABSENT,
     ADD_REVERSE_DEP,
+    REMOVE_REVERSE_DEP,
     SIGNAL,
     SET_VALUE,
     MARK_DIRTY,
     MARK_CLEAN,
     IS_CHANGED,
     GET_VALUE_WITH_METADATA,
-    IS_DIRTY
+    IS_DIRTY,
+    IS_READY,
+    CHECK_IF_DONE,
+    GET_ALL_DIRECT_DEPS_FOR_INCOMPLETE_NODE
   }
 
   public enum Order {
@@ -121,6 +125,13 @@ public class NotifyingInMemoryGraph extends InMemoryGraph {
     }
 
     @Override
+    public synchronized void removeReverseDep(SkyKey reverseDep) {
+      graphListener.accept(myKey, EventType.REMOVE_REVERSE_DEP, Order.BEFORE, reverseDep);
+      super.removeReverseDep(reverseDep);
+      graphListener.accept(myKey, EventType.REMOVE_REVERSE_DEP, Order.AFTER, reverseDep);
+    }
+
+    @Override
     public boolean signalDep(Version childVersion) {
       graphListener.accept(myKey, EventType.SIGNAL, Order.BEFORE, childVersion);
       boolean result = super.signalDep(childVersion);
@@ -137,9 +148,9 @@ public class NotifyingInMemoryGraph extends InMemoryGraph {
     }
 
     @Override
-    public Iterable<SkyKey> markDirty(boolean isChanged) {
+    public boolean markDirty(boolean isChanged) {
       graphListener.accept(myKey, EventType.MARK_DIRTY, Order.BEFORE, isChanged);
-      Iterable<SkyKey> result = super.markDirty(isChanged);
+      boolean result = super.markDirty(isChanged);
       graphListener.accept(myKey, EventType.MARK_DIRTY, Order.AFTER, isChanged);
       return result;
     }
@@ -165,9 +176,28 @@ public class NotifyingInMemoryGraph extends InMemoryGraph {
     }
 
     @Override
+    public synchronized boolean isReady() {
+      graphListener.accept(myKey, EventType.IS_READY, Order.BEFORE, this);
+      return super.isReady();
+    }
+
+    @Override
     public SkyValue getValueMaybeWithMetadata() {
       graphListener.accept(myKey, EventType.GET_VALUE_WITH_METADATA, Order.BEFORE, this);
       return super.getValueMaybeWithMetadata();
     }
+
+    @Override
+    public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
+      graphListener.accept(myKey, EventType.CHECK_IF_DONE, Order.BEFORE, reverseDep);
+      return super.checkIfDoneForDirtyReverseDep(reverseDep);
+    }
+
+    @Override
+    public synchronized Iterable<SkyKey> getAllDirectDepsForIncompleteNode() {
+      graphListener.accept(
+          myKey, EventType.GET_ALL_DIRECT_DEPS_FOR_INCOMPLETE_NODE, Order.BEFORE, this);
+      return super.getAllDirectDepsForIncompleteNode();
+    }
   }
 }
diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilTest.java
index efcbbec28c..526666fef8 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilTest.java
@@ -48,43 +48,49 @@ public class ReverseDepsUtilTest {
     this.numElements = numElements;
   }
 
-  private static final ReverseDepsUtil<Example> REVERSE_DEPS_UTIL = new ReverseDepsUtil<Example>() {
-    @Override
-    void setReverseDepsObject(Example container, Object object) {
-      container.reverseDeps = object;
-    }
-
-    @Override
-    void setSingleReverseDep(Example container, boolean singleObject) {
-      container.single = singleObject;
-    }
-
-    @Override
-    void setReverseDepsToRemove(Example container, List<SkyKey> object) {
-      container.reverseDepsToRemove = object;
-    }
-
-    @Override
-    Object getReverseDepsObject(Example container) {
-      return container.reverseDeps;
-    }
-
-    @Override
-    boolean isSingleReverseDep(Example container) {
-      return container.single;
-    }
-
-    @Override
-    List<SkyKey> getReverseDepsToRemove(Example container) {
-      return container.reverseDepsToRemove;
-    }
-  };
+  private static final ReverseDepsUtil<Example> REVERSE_DEPS_UTIL =
+      new ReverseDepsUtil<Example>() {
+        @Override
+        void setReverseDepsObject(Example container, Object object) {
+          container.reverseDeps = object;
+        }
+
+        @Override
+        void setSingleReverseDep(Example container, boolean singleObject) {
+          container.single = singleObject;
+        }
+
+        @Override
+        void setDataToConsolidate(Example container, Object dataToConsolidate) {
+          container.dataToConsolidate = dataToConsolidate;
+        }
+
+        @Override
+        Object getReverseDepsObject(Example container) {
+          return container.reverseDeps;
+        }
+
+        @Override
+        boolean isSingleReverseDep(Example container) {
+          return container.single;
+        }
+
+        @Override
+        Object getDataToConsolidate(Example container) {
+          return container.dataToConsolidate;
+        }
+      };
 
   private class Example {
 
     Object reverseDeps = ImmutableList.of();
     boolean single;
-    List<SkyKey> reverseDepsToRemove;
+    Object dataToConsolidate;
+
+    @Override
+    public String toString() {
+      return "Example: " + reverseDeps + ", " + single + ", " + dataToConsolidate;
+    }
   }
 
   @Test
@@ -101,7 +107,7 @@ public class ReverseDepsUtilTest {
         REVERSE_DEPS_UTIL.removeReverseDep(example, new SkyKey(NODE_TYPE, i));
       }
       assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals);
-      assertThat(example.reverseDepsToRemove).isNull();
+      assertThat(example.dataToConsolidate).isNull();
     }
   }
 
@@ -120,7 +126,7 @@ public class ReverseDepsUtilTest {
         REVERSE_DEPS_UTIL.removeReverseDep(example, new SkyKey(NODE_TYPE, i));
       }
       assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals);
-      assertThat(example.reverseDepsToRemove).isNull();
+      assertThat(example.dataToConsolidate).isNull();
     }
   }