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

7 files changed, 346 insertions, 100 deletions

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();
     }
   }