Stop storing reverse deps to signal in BuildingState. Instead, re-use the reverseDepsToConsolidate field in InMemoryNodeEntry. As part of that, revamp our logic of how we store pending operations: store adds bare on initial evaluations, and checks bare on incremental evaluations and operations on done nodes.

This should improve performance in two ways: BuildingState loses two fields, saving working memory intra-build. Storing pending reverse dep operations bare also saves memory intra-build. Note that neither of these changes helps resting memory state, only while a node is still evaluating.

Because of this, we can simplify ReverseDepsUtil a bit, making ReverseDepsUtilImpl a static class, which it always wanted to be (what it really wants to be is a superclass of InMemoryNodeEntry, but I don't want to spend the object alignment bits).

Finally, this makes it pretty tempting to get rid of BuildingState altogether on initial evaluations. We'd still keep DirtyBuildingState, but we could save another ~24 bytes by storing BuildingState's one remaining field, signaledDeps, directly inside InMemoryNodeEntry.

--
PiperOrigin-RevId: 151048879
MOS_MIGRATED_REVID=151048879

11 files changed, 764 insertions, 610 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 d2f92b864e..455ecda809 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -15,14 +15,9 @@ package com.google.devtools.build.skyframe;
 
 import com.google.common.base.MoreObjects;
 import com.google.common.base.MoreObjects.ToStringHelper;
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
 import com.google.devtools.build.lib.util.Preconditions;
 
-import java.util.Collections;
-import java.util.List;
-
 /**
  * Data the NodeEntry uses to maintain its state before it is done building. It allows the {@link
  * NodeEntry} to keep the current state of the entry across invalidation and successive evaluations.
@@ -60,6 +55,8 @@ import java.util.List;
  */
 @ThreadCompatible
 class BuildingState {
+  protected static final int NOT_EVALUATING_SENTINEL = -1;
+
   /**
    * The number of dependencies that are known to be done in a {@link NodeEntry} if it is already
    * evaluating, and a sentinel (-1) indicating that it has not yet started evaluating otherwise.
@@ -81,45 +78,7 @@ class BuildingState {
    * thread is not working on the node anymore. Note that this requires that there is no code after
    * the loop in {@code ParallelEvaluator.Evaluate#run}.
    */
-  int signaledDeps = -1;
-
-  /**
-   * The set of reverse dependencies that are registered before the node has finished building. Upon
-   * building, these reverse deps will be signaled and then stored in the permanent {@link
-   * InMemoryNodeEntry#reverseDeps}. This field is marked volatile for subclasses that may change
-   * its value and require volatile reads.
-   */
-  protected volatile Object reverseDepsToSignal = ImmutableList.of();
-  private List<Object> reverseDepsDataToConsolidate = null;
-
-  private static final ReverseDepsUtil<BuildingState> REVERSE_DEPS_UTIL =
-      new ReverseDepsUtilImpl<BuildingState>() {
-        @Override
-        void setReverseDepsObject(BuildingState container, Object object) {
-          container.reverseDepsToSignal = object;
-        }
-
-        @Override
-        void setDataToConsolidate(BuildingState container, List<Object> dataToConsolidate) {
-          container.reverseDepsDataToConsolidate = dataToConsolidate;
-        }
-
-        @Override
-        Object getReverseDepsObject(BuildingState container) {
-          return container.reverseDepsToSignal;
-        }
-
-        @Override
-        List<Object> getDataToConsolidate(BuildingState container) {
-          return container.reverseDepsDataToConsolidate;
-        }
-
-        @Override
-        public void consolidateReverseDeps(BuildingState container) {
-          // #consolidateReverseDeps is only supported for node entries, not building states.
-          throw new UnsupportedOperationException();
-        }
-      };
+  protected int signaledDeps = NOT_EVALUATING_SENTINEL;
 
   /** Returns whether all known children of this node have signaled that they are done. */
   final boolean isReady(int numDirectDeps) {
@@ -170,7 +129,7 @@ class BuildingState {
   }
 
   final boolean isEvaluating() {
-    return signaledDeps > -1;
+    return signaledDeps > NOT_EVALUATING_SENTINEL;
   }
 
   /**
@@ -191,34 +150,10 @@ class BuildingState {
 
   void signalDepInternal(boolean childChanged, int numDirectDeps) {}
 
-  /**
-   * Returns reverse deps to signal that have been registered this build.
-   *
-   * @see NodeEntry#getReverseDeps()
-   */
-  final ImmutableSet<SkyKey> getReverseDepsToSignal() {
-    return REVERSE_DEPS_UTIL.getReverseDeps(this);
-  }
-
-  /**
-   * Adds a reverse dependency that should be notified when this entry is done.
-   *
-   * @see NodeEntry#addReverseDepAndCheckIfDone(SkyKey)
-   */
-  final void addReverseDepToSignal(SkyKey newReverseDep) {
-    REVERSE_DEPS_UTIL.addReverseDeps(this, Collections.singleton(newReverseDep));
-  }
-
-  /** @see NodeEntry#removeReverseDep(SkyKey) */
-  final void removeReverseDepToSignal(SkyKey reverseDep) {
-    REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
-  }
-
   protected ToStringHelper getStringHelper() {
     return MoreObjects.toStringHelper(this)
         .add("hash", System.identityHashCode(this))
-        .add("signaledDeps/evaluating state", signaledDeps)
-        .add("reverseDepsToSignal", REVERSE_DEPS_UTIL.toString(this));
+        .add("signaledDeps/evaluating state", signaledDeps);
   }
   @Override
   public final String toString() {
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
index f0003f7be2..e0b3579d09 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -121,6 +121,11 @@ public abstract class DelegatingNodeEntry implements NodeEntry {
   }
 
   @Override
+  public Iterable<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
+    return getDelegate().getAllReverseDepsForNodeBeingDeleted();
+  }
+
+  @Override
   public void markRebuilding() {
     getDelegate().markRebuilding();
   }
@@ -171,8 +176,8 @@ public abstract class DelegatingNodeEntry implements NodeEntry {
   }
 
   @Override
-  public Iterable<SkyKey> getReverseDeps() throws InterruptedException {
-    return getDelegate().getReverseDeps();
+  public Iterable<SkyKey> getReverseDepsForDoneEntry() throws InterruptedException {
+    return getDelegate().getReverseDepsForDoneEntry();
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
index 76ebe75db5..217ebd9310 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
@@ -128,7 +128,7 @@ public class DelegatingWalkableGraph implements WalkableGraph {
     Map<SkyKey, Iterable<SkyKey>> result = new HashMap<>(entries.size());
     for (Entry<SkyKey, ? extends NodeEntry> entry : entries.entrySet()) {
       Preconditions.checkState(entry.getValue().isDone(), entry);
-      result.put(entry.getKey(), entry.getValue().getReverseDeps());
+      result.put(entry.getKey(), entry.getValue().getReverseDepsForDoneEntry());
     }
     return result;
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
index fefee27763..7f8330195b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -21,6 +21,9 @@ import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
 import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.skyframe.KeyToConsolidate.Op;
+import com.google.devtools.build.skyframe.KeyToConsolidate.OpToStoreBare;
+import java.util.ArrayList;
 import java.util.Collection;
 import java.util.List;
 import java.util.Set;
@@ -84,44 +87,35 @@ public class InMemoryNodeEntry implements NodeEntry {
    *
    * <p>In case of a single object we store the object unwrapped, without the list, for
    * memory-efficiency.
+   *
+   * <p>When an entry is being re-evaluated, this object stores the reverse deps from the previous
+   * evaluation. At the end of evaluation, the changed reverse dep operations from {@link
+   * #reverseDepsDataToConsolidate} are merged in here.
    */
   protected Object reverseDeps = ImmutableList.of();
 
   /**
-   * When reverse deps are removed, checked for presence, or possibly added, we store them in this
-   * object instead of directly doing the operation. 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.
+   * This list stores objects returned by {@link KeyToConsolidate#create}. Morally they are {@link
+   * KeyToConsolidate} objects, but since some operations are stored bare, we can only declare that
+   * this list holds {@link Object} references. Created lazily to save memory.
+   *
+   * <p>This list serves double duty. For a done node, when a reverse dep is removed, checked for
+   * presence, or possibly added, we store the mutation in this object instead of immediately doing
+   * the operation. 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>Internally, ReverseDepsUtilImpl consolidates this data periodically, and when the set of
-   * reverse deps is requested. While this operation is not free, it can be done more effectively
+   * <p>Internally, {@link ReverseDepsUtility} consolidates this data periodically, and when the set
+   * of reverse deps is requested. 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).
+   *
+   * <p>When the node entry is evaluating, this list serves to declare the reverse dep operations
+   * that have taken place on it during this evaluation. When evaluation finishes, this list will be
+   * merged into the existing reverse deps if any, but furthermore, this list will also be used to
+   * calculate the set of reverse deps to signal when this entry finishes evaluation. That is done
+   * by {@link ReverseDepsUtility#consolidateDataAndReturnNewElements}.
    */
   private List<Object> reverseDepsDataToConsolidate = null;
 
-  private static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL =
-      new ReverseDepsUtilImpl<InMemoryNodeEntry>() {
-        @Override
-        void setReverseDepsObject(InMemoryNodeEntry container, Object object) {
-          container.reverseDeps = object;
-        }
-
-        @Override
-        void setDataToConsolidate(InMemoryNodeEntry container, List<Object> dataToConsolidate) {
-          container.reverseDepsDataToConsolidate = dataToConsolidate;
-        }
-
-        @Override
-        Object getReverseDepsObject(InMemoryNodeEntry container) {
-          return container.reverseDeps;
-        }
-
-        @Override
-        List<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
    * us to keep the current state of the entry across invalidation and successive evaluations.
@@ -209,11 +203,8 @@ public class InMemoryNodeEntry implements NodeEntry {
   }
 
   protected synchronized Set<SkyKey> setStateFinishedAndReturnReverseDepsToSignal() {
-    // Get reverse deps that need to be signaled.
-    ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal();
-    getReverseDepsUtil().addReverseDeps(this, reverseDepsToSignal);
-    // Force consistency check and consolidate rdeps changes.
-    getReverseDepsUtil().consolidateReverseDeps(this);
+    Set<SkyKey> reverseDepsToSignal =
+        ReverseDepsUtility.consolidateDataAndReturnNewElements(this, getOpToStoreBare());
     this.directDeps = getTemporaryDirectDeps().compress();
 
     markDone();
@@ -228,7 +219,7 @@ public class InMemoryNodeEntry implements NodeEntry {
   @Override
   public synchronized Set<SkyKey> getInProgressReverseDeps() {
     Preconditions.checkState(!isDone(), this);
-    return buildingState.getReverseDepsToSignal();
+    return ReverseDepsUtility.returnNewElements(this, getOpToStoreBare());
   }
 
   @Override
@@ -256,23 +247,15 @@ public class InMemoryNodeEntry implements NodeEntry {
     return setStateFinishedAndReturnReverseDepsToSignal();
   }
 
-  protected ReverseDepsUtil<InMemoryNodeEntry> getReverseDepsUtil() {
-    return REVERSE_DEPS_UTIL;
-  }
-
   @Override
   public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
     if (reverseDep != null) {
-      if (keepEdges()) {
-        getReverseDepsUtil().maybeCheckReverseDepNotPresent(this, reverseDep);
-      }
       if (isDone()) {
         if (keepEdges()) {
-          getReverseDepsUtil().addReverseDeps(this, ImmutableList.of(reverseDep));
+          ReverseDepsUtility.addReverseDeps(this, ImmutableList.of(reverseDep));
         }
       } else {
-        // Parent should never register itself twice in the same build.
-        buildingState.addReverseDepToSignal(reverseDep);
+        appendToReverseDepOperations(reverseDep, Op.ADD);
       }
     }
     if (isDone()) {
@@ -282,15 +265,52 @@ public class InMemoryNodeEntry implements NodeEntry {
                                            : DependencyState.ALREADY_EVALUATING;
   }
 
+  /** Sets {@link #reverseDeps}. Does not alter {@link #reverseDepsDataToConsolidate}. */
+  synchronized void setSingleReverseDepForReverseDepsUtil(SkyKey reverseDep) {
+    this.reverseDeps = reverseDep;
+  }
+
+  /** Sets {@link #reverseDeps}. Does not alter {@link #reverseDepsDataToConsolidate}. */
+  synchronized void setReverseDepsForReverseDepsUtil(List<SkyKey> reverseDeps) {
+    this.reverseDeps = reverseDeps;
+  }
+
+  /** Sets {@link #reverseDepsDataToConsolidate}. Does not alter {@link #reverseDeps}. */
+  synchronized void setReverseDepsDataToConsolidateForReverseDepsUtil(
+      List<Object> dataToConsolidate) {
+    this.reverseDepsDataToConsolidate = dataToConsolidate;
+  }
+
+  synchronized Object getReverseDepsRawForReverseDepsUtil() {
+    return this.reverseDeps;
+  }
+
+  synchronized List<Object> getReverseDepsDataToConsolidateForReverseDepsUtil() {
+    return this.reverseDepsDataToConsolidate;
+  }
+
+  private synchronized void appendToReverseDepOperations(SkyKey reverseDep, Op op) {
+    Preconditions.checkState(!isDone(), "Don't append to done %s %s %s", this, reverseDep, op);
+    if (reverseDepsDataToConsolidate == null) {
+      reverseDepsDataToConsolidate = new ArrayList<>();
+    }
+    Preconditions.checkState(
+        isDirty() || op != Op.CHECK, "Not dirty check %s %s", this, reverseDep);
+    reverseDepsDataToConsolidate.add(KeyToConsolidate.create(reverseDep, op, getOpToStoreBare()));
+  }
+
+  private OpToStoreBare getOpToStoreBare() {
+    return isDirty() ? OpToStoreBare.CHECK : OpToStoreBare.ADD;
+  }
+
   @Override
   public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
     Preconditions.checkNotNull(reverseDep, this);
     Preconditions.checkState(keepEdges(), "%s %s", reverseDep, this);
-    if (!isDone()) {
-      getReverseDepsUtil().removeReverseDep(this, reverseDep);
-      buildingState.addReverseDepToSignal(reverseDep);
+    if (isDone()) {
+      ReverseDepsUtility.checkReverseDep(this, reverseDep);
     } else {
-      getReverseDepsUtil().checkReverseDep(this, reverseDep);
+      appendToReverseDepOperations(reverseDep, Op.CHECK);
     }
     return addReverseDepAndCheckIfDone(null);
   }
@@ -300,23 +320,36 @@ public class InMemoryNodeEntry implements NodeEntry {
     if (!keepEdges()) {
       return;
     }
-    getReverseDepsUtil().removeReverseDep(this, reverseDep);
+    if (isDone()) {
+      ReverseDepsUtility.removeReverseDep(this, reverseDep);
+    } else {
+      // Removing a reverse dep from an in-flight node is rare -- it should only happen when this
+      // node is about to be cleaned from the graph.
+      appendToReverseDepOperations(reverseDep, Op.REMOVE_OLD);
+    }
   }
 
   @Override
   public synchronized void removeInProgressReverseDep(SkyKey reverseDep) {
-    buildingState.removeReverseDepToSignal(reverseDep);
+    appendToReverseDepOperations(reverseDep, Op.REMOVE);
   }
 
   @Override
-  public synchronized Iterable<SkyKey> getReverseDeps() {
+  public synchronized Iterable<SkyKey> getReverseDepsForDoneEntry() {
     assertKeepEdges();
-    Iterable<SkyKey> reverseDeps = getReverseDepsUtil().getReverseDeps(this);
-    if (isDone()) {
-      return reverseDeps;
-    } else {
-      return Iterables.concat(reverseDeps, buildingState.getReverseDepsToSignal());
+    Preconditions.checkState(isDone(), "Called on not done %s", this);
+    return ReverseDepsUtility.getReverseDeps(this);
+  }
+
+  @Override
+  public synchronized Iterable<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
+    assertKeepEdges();
+    if (!isDone()) {
+      // This consolidation loses information about pending reverse deps to signal, but that is
+      // unimportant since this node is being deleted.
+      ReverseDepsUtility.consolidateDataAndReturnNewElements(this, getOpToStoreBare());
     }
+    return ReverseDepsUtility.getReverseDeps(this);
   }
 
   @Override
@@ -355,7 +388,7 @@ public class InMemoryNodeEntry implements NodeEntry {
           DirtyBuildingState.create(isChanged, GroupedList.<SkyKey>create(directDeps), value);
       value = null;
       directDeps = null;
-      return new MarkedDirtyResult(getReverseDepsUtil().getReverseDeps(this));
+      return new MarkedDirtyResult(ReverseDepsUtility.getReverseDeps(this));
     }
     // 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
@@ -499,7 +532,7 @@ public class InMemoryNodeEntry implements NodeEntry {
         .add("lastChangedVersion", lastChangedVersion)
         .add("lastEvaluatedVersion", lastEvaluatedVersion)
         .add("directDeps", isDone() ? GroupedList.create(directDeps) : directDeps)
-        .add("reverseDeps", getReverseDepsUtil().toString(this))
+        .add("reverseDeps", ReverseDepsUtility.toString(this))
         .add("buildingState", buildingState)
         .toString();
   }
@@ -516,7 +549,7 @@ public class InMemoryNodeEntry implements NodeEntry {
     nodeEntry.value = value;
     nodeEntry.lastChangedVersion = this.lastChangedVersion;
     nodeEntry.lastEvaluatedVersion = this.lastEvaluatedVersion;
-    getReverseDepsUtil().addReverseDeps(nodeEntry, getReverseDepsUtil().getReverseDeps(this));
+    ReverseDepsUtility.addReverseDeps(nodeEntry, ReverseDepsUtility.getReverseDeps(this));
     nodeEntry.directDeps = directDeps;
     nodeEntry.buildingState = null;
     return nodeEntry;
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 577639a618..d7bb2d2cab 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -271,16 +271,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends QueryableGraph> {
 
                 if (traverseGraph) {
                   // Propagate deletion upwards.
-                  try {
-                    visit(entry.getReverseDeps(), InvalidationType.DELETED);
-                  } catch (InterruptedException e) {
-                    throw new IllegalStateException(
-                        "Deletion cannot happen on a graph that may have blocking operations: "
-                            + key
-                            + ", "
-                            + entry,
-                        e);
-                  }
+                  visit(entry.getAllReverseDepsForNodeBeingDeleted(), InvalidationType.DELETED);
 
                   // 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
@@ -339,8 +330,8 @@ public abstract class InvalidatingNodeVisitor<TGraph extends QueryableGraph> {
                 }
 
                 // Allow custom key-specific logic to update dirtiness status.
-                progressReceiver.invalidated(key,
-                    EvaluationProgressReceiver.InvalidationState.DELETED);
+                progressReceiver.invalidated(
+                    key, EvaluationProgressReceiver.InvalidationState.DELETED);
                 // Actually remove the node.
                 graph.remove(key);
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/KeyToConsolidate.java b/src/main/java/com/google/devtools/build/skyframe/KeyToConsolidate.java
new file mode 100644
index 0000000000..2b2572c727
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/KeyToConsolidate.java
@@ -0,0 +1,206 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.skyframe;
+
+import com.google.common.base.MoreObjects;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.util.Preconditions;
+
+/**
+ * Container for a pending operation on the reverse deps set. We use subclasses to save 8 bytes of
+ * memory instead of keeping a field in this class, and we store {@link Op#CHECK} or {@link Op#ADD}
+ * operations as the bare {@link SkyKey} in order to save the wrapper object in that case.
+ *
+ * <p>When a list of {@link KeyToConsolidate} operations is processed, each operation is performed
+ * in order. Operations on a done or freshly evaluating node entry are straightforward: they apply
+ * to the entry's reverse deps. Operations on a re-evaluating node entry have a double meaning: they
+ * will eventually be applied to the node entry's existing reverse deps, just as for a done node
+ * entry, but they are also used to track the entries that declared/redeclared a reverse dep on this
+ * entry during this evaluation (and will thus need to be signaled when this entry finishes
+ * evaluating).
+ */
+abstract class KeyToConsolidate {
+  enum Op {
+    /**
+     * Assert that the reverse dep is already present in the set of reverse deps. If the entry is
+     * re-evaluating, add this reverse dep to the set of reverse deps to signal when this entry is
+     * done.
+     */
+    CHECK,
+    /**
+     * Add the reverse dep to the set of reverse deps and assert it was not already present. If the
+     * entry is re-evaluating, add this reverse dep to the set of reverse deps to signal when this
+     * entry is done.
+     */
+    ADD,
+    /**
+     * Remove the reverse dep from the set of reverse deps and assert it was present. If the entry
+     * is re-evaluating, also remove the reverse dep from the set of reverse deps to signal when
+     * this entry is done, and assert that it was present.
+     */
+    REMOVE,
+    /**
+     * The same as {@link #REMOVE}, except that if the entry is re-evaluating, we assert that the
+     * set of reverse deps to signal did <i>not</i> contain this reverse dep.
+     */
+    REMOVE_OLD
+  }
+
+  enum OpToStoreBare {
+    ADD(Op.ADD),
+    CHECK(Op.CHECK);
+
+    private final Op op;
+
+    OpToStoreBare(Op op) {
+      this.op = op;
+    }
+  }
+
+  private static final Interner<KeyToConsolidate> consolidateInterner =
+      BlazeInterners.newWeakInterner();
+
+  private final SkyKey key;
+
+  /** Do not call directly -- use the {@link #create} static method instead. */
+  private KeyToConsolidate(SkyKey key) {
+    this.key = key;
+  }
+
+  @Override
+  public String toString() {
+    return MoreObjects.toStringHelper(this).add("key", key).toString();
+  }
+
+  /**
+   * Gets which operation was delayed for the given object, created using {@link #create}. The same
+   * {@code opToStoreBare} passed in to {@link #create} should be passed in here.
+   */
+  static Op op(Object obj, OpToStoreBare opToStoreBare) {
+    if (obj instanceof SkyKey) {
+      return opToStoreBare.op;
+    }
+    if (obj instanceof KeyToAdd) {
+      return Op.ADD;
+    }
+    if (obj instanceof KeyToCheck) {
+      return Op.CHECK;
+    }
+    if (obj instanceof KeyToRemove) {
+      return Op.REMOVE;
+    }
+    if (obj instanceof KeyToRemoveOld) {
+      return Op.REMOVE_OLD;
+    }
+    throw new IllegalStateException(
+        "Unknown object type: " + obj + ", " + opToStoreBare + ", " + obj.getClass());
+  }
+
+  /** Gets the key whose operation was delayed for the given object. */
+  static SkyKey key(Object obj) {
+    if (obj instanceof SkyKey) {
+      return (SkyKey) obj;
+    }
+    Preconditions.checkState(obj instanceof KeyToConsolidate, obj);
+    return ((KeyToConsolidate) obj).key;
+  }
+
+  /**
+   * Creates a new operation, encoding the operation {@code op} with reverse dep {@code key}. To
+   * save memory, the caller should specify the most common operation expected as {@code
+   * opToStoreBare}. That operation will be encoded as the raw {@code key}, saving the memory of an
+   * object wrapper. Whatever {@code opToStoreBare} is set to here, the same value must be passed in
+   * to {@link #op} when decoding an operation emitted by this method.
+   */
+  static Object create(SkyKey key, Op op, OpToStoreBare opToStoreBare) {
+    if (op == opToStoreBare.op) {
+      return key;
+    }
+    switch (op) {
+      case CHECK:
+        return consolidateInterner.intern(new KeyToCheck(key));
+      case REMOVE:
+        return consolidateInterner.intern(new KeyToRemove(key));
+      case REMOVE_OLD:
+        return consolidateInterner.intern(new KeyToRemoveOld(key));
+      case ADD:
+        return consolidateInterner.intern(new KeyToAdd(key));
+      default:
+        throw new IllegalStateException(op + ", " + key);
+    }
+  }
+
+  @Override
+  public boolean equals(Object obj) {
+    if (obj == null) {
+      return false;
+    }
+    return this.getClass() == obj.getClass() && this.key.equals(((KeyToConsolidate) obj).key);
+  }
+
+  protected int keyHashCode() {
+    return key.hashCode();
+  }
+
+  @Override
+  public int hashCode() {
+    // Overridden in subclasses.
+    throw new UnsupportedOperationException(key.toString());
+  }
+
+  private static final class KeyToAdd extends KeyToConsolidate {
+    KeyToAdd(SkyKey key) {
+      super(key);
+    }
+
+    @Override
+    public int hashCode() {
+      return keyHashCode();
+    }
+  }
+
+  private static final class KeyToCheck extends KeyToConsolidate {
+    KeyToCheck(SkyKey key) {
+      super(key);
+    }
+
+    @Override
+    public int hashCode() {
+      return 31 + 43 * keyHashCode();
+    }
+  }
+
+  private static final class KeyToRemove extends KeyToConsolidate {
+    KeyToRemove(SkyKey key) {
+      super(key);
+    }
+
+    @Override
+    public int hashCode() {
+      return 42 + 37 * keyHashCode();
+    }
+  }
+
+  private static final class KeyToRemoveOld extends KeyToConsolidate {
+    KeyToRemoveOld(SkyKey key) {
+      super(key);
+    }
+
+    @Override
+    public int hashCode() {
+      return 93 + 37 * keyHashCode();
+    }
+  }
+}
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 d7f7fcfc89..57334d6384 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -104,7 +104,8 @@ public interface NodeEntry extends ThinNodeEntry {
    * 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}
+   * reverseDep} was added/confirmed during this evaluation (by {@link #addReverseDepAndCheckIfDone}
+   * or {@link #checkIfDoneForDirtyReverseDep}).
    */
   @ThreadSafe
   void removeInProgressReverseDep(SkyKey reverseDep);
@@ -112,9 +113,11 @@ public interface NodeEntry extends ThinNodeEntry {
   /**
    * 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.
+   *
+   * <p>May only be called on a done node entry.
    */
   @ThreadSafe
-  Iterable<SkyKey> getReverseDeps() throws InterruptedException;
+  Iterable<SkyKey> getReverseDepsForDoneEntry() throws InterruptedException;
 
   /**
    * Returns raw {@link SkyValue} stored in this entry, which may include metadata associated with
@@ -199,6 +202,8 @@ public interface NodeEntry extends ThinNodeEntry {
   @ThreadSafe
   DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) throws InterruptedException;
 
+  Iterable<SkyKey> getAllReverseDepsForNodeBeingDeleted();
+
   /**
    * Tell this node that one of its dependencies is now done. Callers must check the return value,
    * and if true, they must re-schedule this node for evaluation. Equivalent to
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 e45f0a8927..19b18cb8cf 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -870,9 +870,10 @@ public final class ParallelEvaluator implements Evaluator {
       NodeEntry errorEntry = Preconditions.checkNotNull(
           graph.get(null, Reason.ERROR_BUBBLING, errorKey),
           errorKey);
-      Iterable<SkyKey> reverseDeps = errorEntry.isDone()
-          ? errorEntry.getReverseDeps()
-          : errorEntry.getInProgressReverseDeps();
+      Iterable<SkyKey> reverseDeps =
+          errorEntry.isDone()
+              ? errorEntry.getReverseDepsForDoneEntry()
+              : errorEntry.getInProgressReverseDeps();
       // We should break from loop only when node doesn't have any parents.
       if (Iterables.isEmpty(reverseDeps)) {
         Preconditions.checkState(rootValues.contains(errorKey),
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
deleted file mode 100644
index 52ad31229c..0000000000
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
+++ /dev/null
@@ -1,47 +0,0 @@
-// Copyright 2015 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.skyframe;
-
-import com.google.common.collect.ImmutableSet;
-
-import java.util.Collection;
-
-/**
- * A utility interface for dealing with reverse deps in NodeEntry and BuildingState implementations.
- *
- * <p>The reason for this interface is to abstract out dealing with reverse deps, which is subject
- * to various non-trivial and fairly ugly memory/performance optimizations.
- *
- * <p>This interface is public only for the benefit of alternative graph implementations outside of
- * the package.
- */
-public interface ReverseDepsUtil<T> {
-  void addReverseDeps(T container, Collection<SkyKey> reverseDeps);
-  /**
-   * Checks that the reverse dependency is not already present. Implementations may choose not to
-   * perform this check, or only to do it if reverseDeps is small, so that it does not impact
-   * performance.
-   */
-  void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep);
-
-  void checkReverseDep(T container, SkyKey reverseDep);
-
-  void removeReverseDep(T container, SkyKey reverseDep);
-
-  void consolidateReverseDeps(T container);
-
-  ImmutableSet<SkyKey> getReverseDeps(T container);
-
-  String toString(T container);
-}
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtilImpl.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtilImpl.java
deleted file mode 100644
index 6f29e39b59..0000000000
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtilImpl.java
+++ /dev/null
@@ -1,413 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.skyframe;
-
-import com.google.common.base.MoreObjects;
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Interner;
-import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
-import com.google.devtools.build.lib.collect.CompactHashSet;
-import com.google.devtools.build.lib.concurrent.BlazeInterners;
-import com.google.devtools.build.lib.util.Preconditions;
-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
- * uniqueness checks so that it also performs well.
- *
- * <p>The reason for making this a separate class is to share non-trivial code between BuildingState
- * and NodeEntry. We could simply make those two classes extend this class instead, but we would be
- * less memory-efficient since object memory alignment does not cross classes (you would have two
- * memory alignments, one for the base class and one for the extended one).
- *
- */
-public abstract class ReverseDepsUtilImpl<T> implements ReverseDepsUtil<T> {
-
-  static final int MAYBE_CHECK_THRESHOLD = 10;
-
-  private static final Interner<KeyToConsolidate> consolidateInterner =
-      BlazeInterners.newWeakInterner();
-
-  abstract void setReverseDepsObject(T container, Object object);
-
-  abstract void setDataToConsolidate(T container, @Nullable List<Object> dataToConsolidate);
-
-  abstract Object getReverseDepsObject(T container);
-
-  abstract List<Object> getDataToConsolidate(T container);
-
-  private enum ConsolidateOp {
-    CHECK,
-    ADD,
-    REMOVE
-  }
-
-  /**
-   * Opaque container for a pending operation on the reverse deps set. We use subclasses to save
-   * 8 bytes of memory instead of keeping a field in this class, and we store
-   * {@link ConsolidateOp#CHECK} operations as the bare {@link SkyKey} in order to save the wrapper
-   * object in that case.
-   */
-  private abstract static class KeyToConsolidate {
-    // Do not access directly -- use the {@link #key} static accessor instead.
-    protected final SkyKey key;
-
-    /** Do not call directly -- use the {@link #create} static method instead. */
-    private KeyToConsolidate(SkyKey key) {
-      this.key = key;
-    }
-
-    @Override
-    public String toString() {
-      return MoreObjects.toStringHelper(this).add("key", key).toString();
-    }
-
-    /** Gets which operation was delayed for the given object. */
-    static ConsolidateOp op(Object obj) {
-      if (obj instanceof SkyKey) {
-        return ConsolidateOp.CHECK;
-      }
-      if (obj instanceof KeyToRemove) {
-        return ConsolidateOp.REMOVE;
-      }
-      Preconditions.checkState(obj instanceof KeyToAdd, obj);
-      return ConsolidateOp.ADD;
-    }
-
-    /** Gets the key whose operation was delayed for the given object. */
-    static SkyKey key(Object obj) {
-      if (obj instanceof SkyKey) {
-        return (SkyKey) obj;
-      }
-      Preconditions.checkState(obj instanceof KeyToConsolidate, obj);
-      return ((KeyToConsolidate) obj).key;
-    }
-
-    static Object create(SkyKey key, ConsolidateOp op) {
-      switch (op) {
-        case CHECK:
-          return key;
-        case REMOVE:
-          return consolidateInterner.intern(new KeyToRemove(key));
-        case ADD:
-          return consolidateInterner.intern(new KeyToAdd(key));
-        default:
-          throw new IllegalStateException(op + ", " + key);
-      }
-    }
-
-    @Override
-    public boolean equals(Object obj) {
-      if (obj == null) {
-        return false;
-      }
-      return this.getClass() == obj.getClass() && this.key.equals(((KeyToConsolidate) obj).key);
-    }
-
-    @Override
-    public int hashCode() {
-      // Overridden in subclasses.
-      throw new UnsupportedOperationException(key.toString());
-    }
-  }
-
-  private static final class KeyToAdd extends KeyToConsolidate {
-    KeyToAdd(SkyKey key) {
-      super(key);
-    }
-
-    @Override
-    public int hashCode() {
-      return key.hashCode();
-    }
-  }
-
-  private static final class KeyToRemove extends KeyToConsolidate {
-    KeyToRemove(SkyKey key) {
-      super(key);
-    }
-
-    @Override
-    public int hashCode() {
-      return 42 + 37 * key.hashCode();
-    }
-  }
-
-  private void maybeDelayReverseDepOp(T container, Iterable<SkyKey> reverseDeps, ConsolidateOp op) {
-    List<Object> consolidations = getDataToConsolidate(container);
-    int currentReverseDepSize = getCurrentReverseDepSize(container);
-    if (consolidations == null) {
-      consolidations = new ArrayList<>(currentReverseDepSize);
-      setDataToConsolidate(container, consolidations);
-    }
-    for (SkyKey reverseDep : reverseDeps) {
-      consolidations.add(KeyToConsolidate.create(reverseDep, op));
-    }
-    // TODO(janakr): Should we consolidate more aggressively? This threshold can be customized.
-    if (consolidations.size() == currentReverseDepSize) {
-      consolidateData(container);
-    }
-  }
-
-  private boolean isSingleReverseDep(T container) {
-    return !(getReverseDepsObject(container) instanceof List);
-  }
-
-  /**
-   *  We only check if reverse deps is small and there are no delayed data to consolidate, since
-   *  then presence or absence would not be known.
-   */
-  @Override
-  public void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep) {
-    if (getDataToConsolidate(container) != null) {
-      return;
-    }
-    if (isSingleReverseDep(container)) {
-      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 for %s",
-          reverseDep,
-          asList,
-          container);
-    }
-  }
-
-  private int getCurrentReverseDepSize(T container) {
-    return isSingleReverseDep(container)
-        ? 1
-        : ((List<SkyKey>) getReverseDepsObject(container)).size();
-  }
-
-  /**
-   * We use a memory-efficient trick to keep reverseDeps memory usage low. Edges in Bazel are
-   * dominant over the number of nodes.
-   *
-   * <p>Most of the nodes have zero or one reverse dep. That is why we use immutable versions of the
-   * lists for those cases. In case of the size being > 1 we switch to an ArrayList. That is because
-   * we also have a decent number of nodes for which the reverseDeps are huge (for example almost
-   * everything depends on BuildInfo node).
-   *
-   * <p>We also optimize for the case where we have only one dependency. In that case we keep the
-   * object directly instead of a wrapper list.
-   */
-  @SuppressWarnings("unchecked")
-  public void addReverseDeps(T container, Collection<SkyKey> newReverseDeps) {
-    if (newReverseDeps.isEmpty()) {
-      return;
-    }
-    List<Object> dataToConsolidate = getDataToConsolidate(container);
-    if (dataToConsolidate != null) {
-      maybeDelayReverseDepOp(container, newReverseDeps, ConsolidateOp.ADD);
-      return;
-    }
-    Object reverseDeps = getReverseDepsObject(container);
-    int reverseDepsSize = isSingleReverseDep(container) ? 1 : ((List<SkyKey>) reverseDeps).size();
-    int newSize = reverseDepsSize + newReverseDeps.size();
-    if (newSize == 1) {
-      overwriteReverseDepsWithObject(container, Iterables.getOnlyElement(newReverseDeps));
-    } else if (reverseDepsSize == 0) {
-      overwriteReverseDepsList(container, Lists.newArrayList(newReverseDeps));
-    } else if (reverseDepsSize == 1) {
-      List<SkyKey> newList = Lists.newArrayListWithExpectedSize(newSize);
-      newList.add((SkyKey) reverseDeps);
-      newList.addAll(newReverseDeps);
-      overwriteReverseDepsList(container, newList);
-    } else {
-      ((List<SkyKey>) reverseDeps).addAll(newReverseDeps);
-    }
-  }
-
-  @Override
-  public void checkReverseDep(T container, SkyKey reverseDep) {
-    maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.CHECK);
-  }
-
-  /**
-   * See {@code addReverseDeps} method.
-   */
-  @Override
-  public void removeReverseDep(T container, SkyKey reverseDep) {
-    maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.REMOVE);
-  }
-
-  @Override
-  public ImmutableSet<SkyKey> getReverseDeps(T 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,
-    // and we can't handle that right now.
-    if (isSingleReverseDep(container)) {
-      return ImmutableSet.of((SkyKey) getReverseDepsObject(container));
-    } else {
-      @SuppressWarnings("unchecked")
-      List<SkyKey> reverseDeps = (List<SkyKey>) getReverseDepsObject(container);
-      ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps);
-      Preconditions.checkState(
-          set.size() == reverseDeps.size(),
-          "Duplicate reverse deps present in %s: %s. %s",
-          this,
-          reverseDeps,
-          container);
-      return set;
-    }
-  }
-
-  @Override
-  public void consolidateReverseDeps(T container) {
-    consolidateData(container);
-  }
-
-  private void consolidateData(T container) {
-    List<Object> dataToConsolidate = getDataToConsolidate(container);
-    if (dataToConsolidate == null) {
-      return;
-    }
-    setDataToConsolidate(container, null);
-    Object reverseDeps = getReverseDepsObject(container);
-    if (isSingleReverseDep(container)) {
-      Preconditions.checkState(
-          dataToConsolidate.size() == 1,
-          "dataToConsolidate not size 1 even though only one rdep: %s %s %s",
-          dataToConsolidate,
-          reverseDeps,
-          container);
-      Object keyToConsolidate = Iterables.getOnlyElement(dataToConsolidate);
-      SkyKey key = KeyToConsolidate.key(keyToConsolidate);
-      switch (KeyToConsolidate.op(keyToConsolidate)) {
-        case REMOVE:
-          overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
-          // Fall through to check.
-        case CHECK:
-          Preconditions.checkState(
-              key.equals(reverseDeps), "%s %s %s", keyToConsolidate, reverseDeps, container);
-          break;
-        case ADD:
-          throw new IllegalStateException(
-              "Shouldn't delay add if only one element: "
-                  + keyToConsolidate
-                  + ", "
-                  + reverseDeps
-                  + ", "
-                  + container);
-        default:
-          throw new IllegalStateException(keyToConsolidate + ", " + reverseDeps + ", " + container);
-      }
-      return;
-    }
-    List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
-    Set<SkyKey> reverseDepsAsSet = CompactHashSet.create(reverseDepsAsList);
-
-    if (reverseDepsAsSet.size() != reverseDepsAsList.size()) {
-      // We're about to crash. Try to print an informative error message.
-      Set<SkyKey> seen = new HashSet<>();
-      List<SkyKey> duplicates = new ArrayList<>();
-      for (SkyKey key : reverseDepsAsList) {
-        if (!seen.add(key)) {
-          duplicates.add(key);
-        }
-      }
-      throw new IllegalStateException(
-          (reverseDepsAsList.size() - reverseDepsAsSet.size())
-              + " duplicates: "
-              + duplicates
-              + " for "
-              + container);
-    }
-    for (Object keyToConsolidate : dataToConsolidate) {
-      SkyKey key = KeyToConsolidate.key(keyToConsolidate);
-      switch (KeyToConsolidate.op(keyToConsolidate)) {
-        case CHECK:
-          Preconditions.checkState(
-              reverseDepsAsSet.contains(key),
-              "%s %s %s %s",
-              keyToConsolidate,
-              reverseDepsAsSet,
-              dataToConsolidate,
-              container);
-          break;
-        case REMOVE:
-          Preconditions.checkState(
-              reverseDepsAsSet.remove(key),
-              "%s %s %s %s",
-              keyToConsolidate,
-              reverseDeps,
-              dataToConsolidate,
-              container);
-          break;
-        case ADD:
-          Preconditions.checkState(
-              reverseDepsAsSet.add(key),
-              "%s %s %s %s",
-              keyToConsolidate,
-              reverseDeps,
-              dataToConsolidate,
-              container);
-          break;
-        default:
-          throw new IllegalStateException(
-              keyToConsolidate
-                  + ", "
-                  + reverseDepsAsSet
-                  + ", "
-                  + dataToConsolidate
-                  + ", "
-                  + container);
-      }
-    }
-
-    if (reverseDepsAsSet.isEmpty()) {
-      overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
-    } else if (reverseDepsAsSet.size() == 1) {
-      overwriteReverseDepsWithObject(container, Iterables.getOnlyElement(reverseDepsAsSet));
-    } else {
-      overwriteReverseDepsList(container, new ArrayList<>(reverseDepsAsSet));
-    }
-  }
-
-  @Override
-  public String toString(T container) {
-    return MoreObjects.toStringHelper("ReverseDeps")
-        .add("reverseDeps", getReverseDepsObject(container))
-        .add("singleReverseDep", isSingleReverseDep(container))
-        .add("dataToConsolidate", getDataToConsolidate(container))
-        .toString();
-  }
-
-  private void overwriteReverseDepsWithObject(T container, SkyKey newObject) {
-    setReverseDepsObject(container, newObject);
-  }
-
-  private void overwriteReverseDepsList(T container, List<SkyKey> list) {
-    setReverseDepsObject(container, list);
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
new file mode 100644
index 0000000000..0f93fa6a21
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
@@ -0,0 +1,438 @@
+// Copyright 2014 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.skyframe;
+
+import com.google.common.base.MoreObjects;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.collect.CompactHashSet;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.skyframe.KeyToConsolidate.Op;
+import com.google.devtools.build.skyframe.KeyToConsolidate.OpToStoreBare;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * 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
+ * uniqueness checks so that it also performs well.
+ *
+ * <p>We could simply make {@link InMemoryNodeEntry} extend this class, but we would be less
+ * memory-efficient since object memory alignment does not cross classes (you would have two memory
+ * alignments, one for the base class and one for the extended one). We could also merge this
+ * functionality directly into {@link InMemoryNodeEntry} at the cost of increasing its size and
+ * complexity even more.
+ *
+ * <p>The operations {@link #addReverseDeps}, {@link #checkReverseDep}, and {@link
+ * #removeReverseDep} here are optimized for a done entry. Done entries rarely have rdeps added and
+ * removed, but do have {@link Op#CHECK} operations performed frequently. As well, done node entries
+ * may never have their data forcibly consolidated, since their reverse deps will only be retrieved
+ * as a whole if they are marked dirty. Thus, we consolidate periodically.
+ *
+ * <p>{@link InMemoryNodeEntry} manages pending reverse dep operations on a marked-dirty or initally
+ * evaluating node itself, using similar logic tuned to those cases, and calls into {@link
+ * #consolidateDataAndReturnNewElements(InMemoryNodeEntry, OpToStoreBare)} when transitioning to
+ * done.
+ */
+abstract class ReverseDepsUtility {
+  private ReverseDepsUtility() {}
+
+  static final int MAYBE_CHECK_THRESHOLD = 10;
+
+  /**
+   * We can store one type of operation bare in order to save memory. For done nodes, most
+   * operations are CHECKS.
+   */
+  private static final OpToStoreBare DEFAULT_OP_TO_STORE_BARE = OpToStoreBare.CHECK;
+
+  private static void maybeDelayReverseDepOp(
+      InMemoryNodeEntry entry, Iterable<SkyKey> reverseDeps, Op op) {
+    List<Object> consolidations = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
+    int currentReverseDepSize = getCurrentReverseDepSize(entry);
+    if (consolidations == null) {
+      consolidations = new ArrayList<>(currentReverseDepSize);
+      entry.setReverseDepsDataToConsolidateForReverseDepsUtil(consolidations);
+    }
+    for (SkyKey reverseDep : reverseDeps) {
+      consolidations.add(KeyToConsolidate.create(reverseDep, op, DEFAULT_OP_TO_STORE_BARE));
+    }
+    // TODO(janakr): Should we consolidate more aggressively? This threshold can be customized.
+    if (consolidations.size() >= currentReverseDepSize) {
+      consolidateData(entry);
+    }
+  }
+
+  private static boolean isSingleReverseDep(InMemoryNodeEntry entry) {
+    return !(entry.getReverseDepsRawForReverseDepsUtil() instanceof List);
+  }
+
+  /**
+   * We only check if reverse deps is small and there are no delayed data to consolidate, since then
+   * presence or absence would not be known.
+   */
+  static void maybeCheckReverseDepNotPresent(InMemoryNodeEntry entry, SkyKey reverseDep) {
+    if (entry.getReverseDepsDataToConsolidateForReverseDepsUtil() != null) {
+      return;
+    }
+    if (isSingleReverseDep(entry)) {
+      Preconditions.checkState(
+          !entry.getReverseDepsRawForReverseDepsUtil().equals(reverseDep),
+          "Reverse dep %s already present in %s",
+          reverseDep,
+          entry);
+      return;
+    }
+    @SuppressWarnings("unchecked")
+    List<SkyKey> asList = (List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil();
+    if (asList.size() < MAYBE_CHECK_THRESHOLD) {
+      Preconditions.checkState(
+          !asList.contains(reverseDep),
+          "Reverse dep %s already present in %s for %s",
+          reverseDep,
+          asList,
+          entry);
+    }
+  }
+
+  @SuppressWarnings("unchecked") // Cast to list.
+  private static int getCurrentReverseDepSize(InMemoryNodeEntry entry) {
+    return isSingleReverseDep(entry)
+        ? 1
+        : ((List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil()).size();
+  }
+
+  /**
+   * We use a memory-efficient trick to keep reverseDeps memory usage low. Edges in Bazel are
+   * dominant over the number of nodes.
+   *
+   * <p>Most of the nodes have zero or one reverse dep. That is why we use immutable versions of the
+   * lists for those cases. In case of the size being > 1 we switch to an ArrayList. That is because
+   * we also have a decent number of nodes for which the reverseDeps are huge (for example almost
+   * everything depends on BuildInfo node).
+   *
+   * <p>We also optimize for the case where we have only one dependency. In that case we keep the
+   * object directly instead of a wrapper list.
+   */
+  @SuppressWarnings("unchecked") // Cast to SkyKey and List.
+  static void addReverseDeps(InMemoryNodeEntry entry, Collection<SkyKey> newReverseDeps) {
+    if (newReverseDeps.isEmpty()) {
+      return;
+    }
+    List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
+    if (dataToConsolidate != null) {
+      maybeDelayReverseDepOp(entry, newReverseDeps, Op.ADD);
+      return;
+    }
+    Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil();
+    int reverseDepsSize = isSingleReverseDep(entry) ? 1 : ((List<SkyKey>) reverseDeps).size();
+    int newSize = reverseDepsSize + newReverseDeps.size();
+    if (newSize == 1) {
+      entry.setSingleReverseDepForReverseDepsUtil(Iterables.getOnlyElement(newReverseDeps));
+    } else if (reverseDepsSize == 0) {
+      entry.setReverseDepsForReverseDepsUtil(Lists.newArrayList(newReverseDeps));
+    } else if (reverseDepsSize == 1) {
+      List<SkyKey> newList = Lists.newArrayListWithExpectedSize(newSize);
+      newList.add((SkyKey) reverseDeps);
+      newList.addAll(newReverseDeps);
+      entry.setReverseDepsForReverseDepsUtil(newList);
+    } else {
+      ((List<SkyKey>) reverseDeps).addAll(newReverseDeps);
+    }
+  }
+
+  static void checkReverseDep(InMemoryNodeEntry entry, SkyKey reverseDep) {
+    maybeDelayReverseDepOp(entry, ImmutableList.of(reverseDep), Op.CHECK);
+  }
+
+  /** See {@code addReverseDeps} method. */
+  static void removeReverseDep(InMemoryNodeEntry entry, SkyKey reverseDep) {
+    maybeDelayReverseDepOp(entry, ImmutableList.of(reverseDep), Op.REMOVE);
+  }
+
+  static ImmutableSet<SkyKey> getReverseDeps(InMemoryNodeEntry entry) {
+    consolidateData(entry);
+
+    // 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,
+    // and we can't handle that right now.
+    if (isSingleReverseDep(entry)) {
+      return ImmutableSet.of((SkyKey) entry.getReverseDepsRawForReverseDepsUtil());
+    } else {
+      @SuppressWarnings("unchecked")
+      List<SkyKey> reverseDeps = (List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil();
+      ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps);
+      Preconditions.checkState(
+          set.size() == reverseDeps.size(),
+          "Duplicate reverse deps present in %s: %s",
+          reverseDeps,
+          entry);
+      return set;
+    }
+  }
+
+  static Set<SkyKey> returnNewElements(InMemoryNodeEntry entry, OpToStoreBare opToStoreBare) {
+    return consolidateDataAndReturnNewElements(entry, false, opToStoreBare);
+  }
+
+  @SuppressWarnings("unchecked") // List and bare SkyKey casts.
+  private static Set<SkyKey> consolidateDataAndReturnNewElements(
+      InMemoryNodeEntry entry, boolean mutateObject, OpToStoreBare opToStoreBare) {
+    List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
+    if (dataToConsolidate == null) {
+      return ImmutableSet.of();
+    }
+    Set<SkyKey> reverseDepsAsSet;
+    Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil();
+    if (isSingleReverseDep(entry)) {
+      reverseDepsAsSet = CompactHashSet.create((SkyKey) reverseDeps);
+    } else {
+      List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
+      reverseDepsAsSet = getReverseDepsSet(entry, reverseDepsAsList);
+    }
+    Set<SkyKey> newData = CompactHashSet.create();
+    for (Object keyToConsolidate : dataToConsolidate) {
+      SkyKey key = KeyToConsolidate.key(keyToConsolidate);
+      switch (KeyToConsolidate.op(keyToConsolidate, opToStoreBare)) {
+        case CHECK:
+          Preconditions.checkState(
+              reverseDepsAsSet.contains(key),
+              "Reverse dep not present: %s %s %s %s %s",
+              keyToConsolidate,
+              reverseDepsAsSet,
+              newData,
+              dataToConsolidate,
+              entry);
+          Preconditions.checkState(
+              newData.add(key),
+              "Duplicate new reverse dep: %s %s %s %s %s",
+              keyToConsolidate,
+              reverseDepsAsSet,
+              newData,
+              dataToConsolidate,
+              entry);
+          break;
+        case REMOVE:
+          Preconditions.checkState(
+              reverseDepsAsSet.remove(key),
+              "Reverse dep to be removed not present: %s %s %s %s %s",
+              keyToConsolidate,
+              reverseDepsAsSet,
+              newData,
+              dataToConsolidate,
+              entry);
+          Preconditions.checkState(
+              newData.remove(key),
+              "Reverse dep to be removed not present: %s %s %s %s %s",
+              keyToConsolidate,
+              reverseDepsAsSet,
+              newData,
+              dataToConsolidate,
+              entry);
+          break;
+        case REMOVE_OLD:
+          Preconditions.checkState(
+              reverseDepsAsSet.remove(key),
+              "Reverse dep to be removed not present: %s %s %s %s %s",
+              keyToConsolidate,
+              reverseDepsAsSet,
+              newData,
+              dataToConsolidate,
+              entry);
+          Preconditions.checkState(
+              !newData.contains(key),
+              "Reverse dep shouldn't have been added to new: %s %s %s %s %s",
+              keyToConsolidate,
+              reverseDepsAsSet,
+              newData,
+              dataToConsolidate,
+              entry);
+          break;
+        case ADD:
+          Preconditions.checkState(
+              reverseDepsAsSet.add(key),
+              "Duplicate reverse deps: %s %s %s %s %s",
+              keyToConsolidate,
+              reverseDeps,
+              newData,
+              dataToConsolidate,
+              entry);
+          Preconditions.checkState(
+              newData.add(key),
+              "Duplicate new reverse deps: %s %s %s %s %s",
+              keyToConsolidate,
+              reverseDeps,
+              newData,
+              dataToConsolidate,
+              entry);
+          break;
+        default:
+          throw new IllegalStateException(
+              keyToConsolidate + ", " + reverseDepsAsSet + ", " + dataToConsolidate + ", " + entry);
+      }
+    }
+    if (mutateObject) {
+      entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null);
+      writeReverseDepsSet(entry, reverseDepsAsSet);
+    }
+    return newData;
+  }
+
+  static Set<SkyKey> consolidateDataAndReturnNewElements(
+      InMemoryNodeEntry entry, OpToStoreBare opToStoreBare) {
+    return consolidateDataAndReturnNewElements(entry, true, opToStoreBare);
+  }
+
+  @SuppressWarnings("unchecked") // Casts to SkyKey and List.
+  private static void consolidateData(InMemoryNodeEntry entry) {
+    List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
+    if (dataToConsolidate == null) {
+      return;
+    }
+    entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null);
+    Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil();
+    if (isSingleReverseDep(entry)) {
+      Preconditions.checkState(
+          dataToConsolidate.size() == 1,
+          "dataToConsolidate not size 1 even though only one rdep: %s %s %s",
+          dataToConsolidate,
+          reverseDeps,
+          entry);
+      Object keyToConsolidate = Iterables.getOnlyElement(dataToConsolidate);
+      SkyKey key = KeyToConsolidate.key(keyToConsolidate);
+      switch (KeyToConsolidate.op(keyToConsolidate, DEFAULT_OP_TO_STORE_BARE)) {
+        case REMOVE:
+          entry.setReverseDepsForReverseDepsUtil(ImmutableList.<SkyKey>of());
+          // Fall through to check.
+        case CHECK:
+          Preconditions.checkState(
+              key.equals(reverseDeps), "%s %s %s", keyToConsolidate, reverseDeps, entry);
+          break;
+        case ADD:
+          throw new IllegalStateException(
+              "Shouldn't delay add if only one element: "
+                  + keyToConsolidate
+                  + ", "
+                  + reverseDeps
+                  + ", "
+                  + entry);
+        case REMOVE_OLD:
+          throw new IllegalStateException(
+              "Shouldn't be removing old deps if node already done: "
+                  + keyToConsolidate
+                  + ", "
+                  + reverseDeps
+                  + ", "
+                  + entry);
+        default:
+          throw new IllegalStateException(keyToConsolidate + ", " + reverseDeps + ", " + entry);
+      }
+      return;
+    }
+    List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
+    Set<SkyKey> reverseDepsAsSet = getReverseDepsSet(entry, reverseDepsAsList);
+
+    for (Object keyToConsolidate : dataToConsolidate) {
+      SkyKey key = KeyToConsolidate.key(keyToConsolidate);
+      switch (KeyToConsolidate.op(keyToConsolidate, DEFAULT_OP_TO_STORE_BARE)) {
+        case CHECK:
+          Preconditions.checkState(
+              reverseDepsAsSet.contains(key),
+              "%s %s %s %s",
+              keyToConsolidate,
+              reverseDepsAsSet,
+              dataToConsolidate,
+              entry);
+          break;
+        case REMOVE:
+          Preconditions.checkState(
+              reverseDepsAsSet.remove(key),
+              "%s %s %s %s",
+              keyToConsolidate,
+              reverseDeps,
+              dataToConsolidate,
+              entry);
+          break;
+        case ADD:
+          Preconditions.checkState(
+              reverseDepsAsSet.add(key),
+              "%s %s %s %s",
+              keyToConsolidate,
+              reverseDeps,
+              dataToConsolidate,
+              entry);
+          break;
+        case REMOVE_OLD:
+          throw new IllegalStateException(
+              "Shouldn't be removing old deps if node already done: "
+                  + keyToConsolidate
+                  + ", "
+                  + reverseDeps
+                  + ", "
+                  + dataToConsolidate
+                  + ", "
+                  + entry);
+        default:
+          throw new IllegalStateException(
+              keyToConsolidate + ", " + reverseDepsAsSet + ", " + dataToConsolidate + ", " + entry);
+      }
+    }
+    writeReverseDepsSet(entry, reverseDepsAsSet);
+  }
+
+  private static void writeReverseDepsSet(InMemoryNodeEntry entry, Set<SkyKey> reverseDepsAsSet) {
+    if (reverseDepsAsSet.isEmpty()) {
+      entry.setReverseDepsForReverseDepsUtil(ImmutableList.<SkyKey>of());
+    } else if (reverseDepsAsSet.size() == 1) {
+      entry.setSingleReverseDepForReverseDepsUtil(Iterables.getOnlyElement(reverseDepsAsSet));
+    } else {
+      entry.setReverseDepsForReverseDepsUtil(new ArrayList<>(reverseDepsAsSet));
+    }
+  }
+
+  private static Set<SkyKey> getReverseDepsSet(
+      InMemoryNodeEntry entry, List<SkyKey> reverseDepsAsList) {
+    Set<SkyKey> reverseDepsAsSet = CompactHashSet.create(reverseDepsAsList);
+
+    if (reverseDepsAsSet.size() != reverseDepsAsList.size()) {
+      // We're about to crash. Try to print an informative error message.
+      Set<SkyKey> seen = new HashSet<>();
+      List<SkyKey> duplicates = new ArrayList<>();
+      for (SkyKey key : reverseDepsAsList) {
+        if (!seen.add(key)) {
+          duplicates.add(key);
+        }
+      }
+      throw new IllegalStateException(
+          (reverseDepsAsList.size() - reverseDepsAsSet.size())
+              + " duplicates: "
+              + duplicates
+              + " for "
+              + entry);
+    }
+    return reverseDepsAsSet;
+  }
+
+  static String toString(InMemoryNodeEntry entry) {
+    return MoreObjects.toStringHelper("ReverseDeps")
+        .add("reverseDeps", entry.getReverseDepsRawForReverseDepsUtil())
+        .add("singleReverseDep", isSingleReverseDep(entry))
+        .add("dataToConsolidate", entry.getReverseDepsDataToConsolidateForReverseDepsUtil())
+        .toString();
+  }
+}