Delay additions as well as removals of reverse deps. Now that removals are not all done during invalidation, repeated adding/removing means that we are consolidating more often, negating the benefit of delayed removals. To work around this, delay adds as well until we consolidate and verify the integrity of our data.

Since there is no well-defined point that a consolidation should trigger for a done node, we delay until our pending list is as large as the done list. We can tweak this if necessary for a memory/performance tradeoff.

The alternative to this that I could think of is giving up our strong integrity checks, which I'm not a fan of.

--
MOS_MIGRATED_REVID=105095886

4 files changed, 226 insertions, 206 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 59c18b833b..0969d1782a 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -119,7 +119,7 @@ public class BuildingState {
   // node will be removed by the time evaluation starts, so reverse deps to signal can just be
   // reverse deps in the main ValueEntry object.
   private Object reverseDepsToSignal = ImmutableList.of();
-  private Object reverseDepsDataToConsolidate = null;
+  private List<Object> reverseDepsDataToConsolidate = null;
   private boolean reverseDepIsSingleObject = false;
 
   private static final ReverseDepsUtil<BuildingState> REVERSE_DEPS_UTIL =
@@ -135,7 +135,7 @@ public class BuildingState {
         }
 
         @Override
-        void setDataToConsolidate(BuildingState container, Object dataToConsolidate) {
+        void setDataToConsolidate(BuildingState container, List<Object> dataToConsolidate) {
           container.reverseDepsDataToConsolidate = dataToConsolidate;
         }
 
@@ -150,7 +150,7 @@ public class BuildingState {
         }
 
         @Override
-        Object getDataToConsolidate(BuildingState container) {
+        List<Object> getDataToConsolidate(BuildingState container) {
           return container.reverseDepsDataToConsolidate;
         }
       };
@@ -404,7 +404,6 @@ public class BuildingState {
    * @see NodeEntry#addReverseDepAndCheckIfDone(SkyKey)
    */
   void addReverseDepToSignal(SkyKey newReverseDep) {
-    REVERSE_DEPS_UTIL.consolidateData(this);
     REVERSE_DEPS_UTIL.addReverseDeps(this, Collections.singleton(newReverseDep));
   }
 
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 6dcd93650f..637787a12d 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -23,6 +23,7 @@ import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
 
 import java.util.Collection;
+import java.util.List;
 import java.util.Set;
 
 import javax.annotation.Nullable;
@@ -82,16 +83,16 @@ public class InMemoryNodeEntry implements NodeEntry {
   protected boolean reverseDepIsSingleObject = false;
 
   /**
-   * When reverse deps are removed or checked for presence, we store them in this object instead of
-   * directly removing/checking them. That is because removals/checks in reverseDeps are O(N).
-   * Originally reverseDeps was a HashSet, but because of memory consumption we switched to a list.
+   * 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.
    *
-   * <p>This requires that any usage of reverseDeps (contains, add, the list of reverse deps) call
-   * {@code consolidateData} first. While this operation is not free, it can be done
-   * more effectively than trying to remove/check each dirty reverse dependency individually (O(N)
-   * each time).
+   * <p>Internally, ReverseDepsUtil 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).
    */
-  private Object reverseDepsDataToConsolidate = null;
+  private List<Object> reverseDepsDataToConsolidate = null;
 
   protected static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL =
       new ReverseDepsUtil<InMemoryNodeEntry>() {
@@ -106,7 +107,7 @@ public class InMemoryNodeEntry implements NodeEntry {
         }
 
         @Override
-        void setDataToConsolidate(InMemoryNodeEntry container, Object dataToConsolidate) {
+        void setDataToConsolidate(InMemoryNodeEntry container, List<Object> dataToConsolidate) {
           container.reverseDepsDataToConsolidate = dataToConsolidate;
         }
 
@@ -121,7 +122,7 @@ public class InMemoryNodeEntry implements NodeEntry {
         }
 
         @Override
-        Object getDataToConsolidate(InMemoryNodeEntry container) {
+        List<Object> getDataToConsolidate(InMemoryNodeEntry container) {
           return container.reverseDepsDataToConsolidate;
         }
       };
@@ -201,8 +202,9 @@ public class InMemoryNodeEntry implements NodeEntry {
   protected synchronized Set<SkyKey> setStateFinishedAndReturnReverseDeps() {
     // Get reverse deps that need to be signaled.
     ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal();
-    REVERSE_DEPS_UTIL.consolidateData(this);
     REVERSE_DEPS_UTIL.addReverseDeps(this, reverseDepsToSignal);
+    // Force consistency check.
+    REVERSE_DEPS_UTIL.getReverseDeps(this);
     this.directDeps = buildingState.getFinishedDirectDeps().compress();
 
     // Set state of entry to done.
@@ -246,7 +248,6 @@ public class InMemoryNodeEntry implements NodeEntry {
   public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
     if (reverseDep != null) {
       if (keepEdges()) {
-        REVERSE_DEPS_UTIL.consolidateData(this);
         REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(this, reverseDep);
       }
       if (isDone()) {
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
index af8e965602..d0f6d4ac82 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
@@ -19,7 +19,7 @@ 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.common.collect.Sets;
+import com.google.devtools.build.lib.collect.CompactHashSet;
 
 import java.util.ArrayList;
 import java.util.Collection;
@@ -50,132 +50,112 @@ public abstract class ReverseDepsUtil<T> {
 
   abstract void setSingleReverseDep(T container, boolean singleObject);
 
-  abstract void setDataToConsolidate(T container, Object dataToConsolidate);
+  abstract void setDataToConsolidate(T container, @Nullable List<Object> dataToConsolidate);
 
   abstract Object getReverseDepsObject(T container);
 
   abstract boolean isSingleReverseDep(T container);
 
-  abstract Object getDataToConsolidate(T container);
+  abstract List<Object> getDataToConsolidate(T container);
 
-  private enum DataState {
-    NULL,
-    CHECK_ONLY,
-    BOTH
+  private enum ConsolidateOp {
+    CHECK,
+    ADD,
+    REMOVE
   }
 
-  private static class RDepsToCheckAndRemove {
-    // reverseDepstoCheck may be null, but not toRemove, because we store a bare list if
-    // we have only toCheck.
-    @Nullable List<SkyKey> toCheck;
-    List<SkyKey> toRemove;
+  /**
+   * 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.
+    private final SkyKey key;
 
-    RDepsToCheckAndRemove(List<SkyKey> toCheck, List<SkyKey> toRemove) {
-      this.toCheck = toCheck;
-      this.toRemove = Preconditions.checkNotNull(toRemove);
+    /** Do not call directly -- use the {@link #create} static method instead. */
+    private KeyToConsolidate(SkyKey key) {
+      this.key = key;
     }
 
-    static RDepsToCheckAndRemove justRemove(List<SkyKey> toRemove) {
-      return new RDepsToCheckAndRemove(null, toRemove);
+    @Override
+    public String toString() {
+      return MoreObjects.toStringHelper(this).add("key", key).toString();
     }
 
-    static RDepsToCheckAndRemove replaceRemove(
-        RDepsToCheckAndRemove original, List<SkyKey> toRemove) {
-      return new RDepsToCheckAndRemove(original.toCheck, toRemove);
+    /** 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;
     }
 
-    static RDepsToCheckAndRemove replaceCheck(
-        RDepsToCheckAndRemove original, List<SkyKey> toCheck) {
-      return new RDepsToCheckAndRemove(toCheck, original.toRemove);
+    /** 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;
     }
-  }
 
-  private static DataState getDataState(Object reverseDepsToCheckAndRemove) {
-    if (reverseDepsToCheckAndRemove == null) {
-      return DataState.NULL;
-    } else if (reverseDepsToCheckAndRemove instanceof List) {
-      return DataState.CHECK_ONLY;
-    } else {
-      Preconditions.checkState(
-          reverseDepsToCheckAndRemove instanceof RDepsToCheckAndRemove,
-          reverseDepsToCheckAndRemove);
-      return DataState.BOTH;
+    static Object create(SkyKey key, ConsolidateOp op) {
+      switch (op) {
+        case CHECK:
+          return key;
+        case REMOVE:
+          return new KeyToRemove(key);
+        case ADD:
+          return new KeyToAdd(key);
+        default:
+          throw new IllegalStateException(op + ", " + key);
+      }
     }
   }
 
-  private void setReverseDepsToRemove(T container, List<SkyKey> toRemove) {
-    Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
-    switch (getDataState(reverseDepsToCheckAndRemove)) {
-      case NULL:
-        reverseDepsToCheckAndRemove = RDepsToCheckAndRemove.justRemove(toRemove);
-        break;
-      case CHECK_ONLY:
-        reverseDepsToCheckAndRemove =
-            new RDepsToCheckAndRemove(((List<SkyKey>) reverseDepsToCheckAndRemove), toRemove);
-        break;
-      case BOTH:
-        reverseDepsToCheckAndRemove =
-            RDepsToCheckAndRemove.replaceRemove(
-                (RDepsToCheckAndRemove) reverseDepsToCheckAndRemove, toRemove);
-        break;
-      default:
-        throw new IllegalStateException(container + ", " + toRemove);
+  private static final class KeyToAdd extends KeyToConsolidate {
+    KeyToAdd(SkyKey key) {
+      super(key);
     }
-    setDataToConsolidate(container, reverseDepsToCheckAndRemove);
   }
 
-  private void setReverseDepsToCheck(T container, List<SkyKey> toCheck) {
-    Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
-    switch (getDataState(reverseDepsToCheckAndRemove)) {
-      case NULL:
-      case CHECK_ONLY:
-        reverseDepsToCheckAndRemove = toCheck;
-        break;
-      case BOTH:
-        reverseDepsToCheckAndRemove =
-            RDepsToCheckAndRemove.replaceCheck(
-                (RDepsToCheckAndRemove) reverseDepsToCheckAndRemove, toCheck);
-        break;
-      default:
-        throw new IllegalStateException(container + ", " + toCheck);
+  private static final class KeyToRemove extends KeyToConsolidate {
+    KeyToRemove(SkyKey key) {
+      super(key);
     }
-    setDataToConsolidate(container, reverseDepsToCheckAndRemove);
   }
 
-  @Nullable
-  private List<SkyKey> getReverseDepsToRemove(T container) {
-    Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
-    switch (getDataState(reverseDepsToCheckAndRemove)) {
-      case NULL:
-      case CHECK_ONLY:
-        return null;
-      case BOTH:
-        return ((RDepsToCheckAndRemove) reverseDepsToCheckAndRemove).toRemove;
-      default:
-        throw new IllegalStateException(reverseDepsToCheckAndRemove.toString());
+  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);
     }
-  }
-
-  @Nullable
-  private List<SkyKey> getReverseDepsToCheck(T container) {
-    Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
-    switch (getDataState(reverseDepsToCheckAndRemove)) {
-      case NULL:
-        return null;
-      case CHECK_ONLY:
-        return (List<SkyKey>) reverseDepsToCheckAndRemove;
-      case BOTH:
-        return ((RDepsToCheckAndRemove) reverseDepsToCheckAndRemove).toCheck;
-      default:
-        throw new IllegalStateException(reverseDepsToCheckAndRemove.toString());
+    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);
     }
   }
 
   /**
    * We check that the reverse dependency is not already present. We only do that if reverseDeps is
-   * small, so that it does not impact performance.
+   * small, so that it does not impact performance. We do not check if there are delayed data to
+   * consolidate, since then presence or absence is not known.
    */
   void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep) {
+    if (getDataToConsolidate(container) != null) {
+      return;
+    }
     if (isSingleReverseDep(container)) {
       Preconditions.checkState(
           !getReverseDepsObject(container).equals(reverseDep),
@@ -196,6 +176,12 @@ public abstract class ReverseDepsUtil<T> {
     }
   }
 
+  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.
@@ -213,6 +199,11 @@ public abstract class ReverseDepsUtil<T> {
     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();
@@ -231,54 +222,14 @@ public abstract class ReverseDepsUtil<T> {
   }
 
   void checkReverseDep(T container, SkyKey reverseDep) {
-    Object reverseDepsObject = getReverseDepsObject(container);
-    if (isSingleReverseDep(container)) {
-      Preconditions.checkState(
-          reverseDepsObject.equals(reverseDep),
-          "%s %s %s",
-          reverseDep,
-          reverseDepsObject,
-          container);
-      return;
-    }
-    List<SkyKey> asList = (List<SkyKey>) reverseDepsObject;
-    if (asList.size() < MAYBE_CHECK_THRESHOLD) {
-      Preconditions.checkState(
-          asList.contains(reverseDep), "%s not in %s for %s", reverseDep, asList, container);
-    } else {
-      List<SkyKey> reverseDepsToCheck = getReverseDepsToCheck(container);
-      if (reverseDepsToCheck == null) {
-        reverseDepsToCheck = new ArrayList<>();
-        setReverseDepsToCheck(container, reverseDepsToCheck);
-      }
-      reverseDepsToCheck.add(reverseDep);
-    }
+    maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.CHECK);
   }
 
   /**
    * See {@code addReverseDeps} method.
    */
   void removeReverseDep(T container, SkyKey reverseDep) {
-    if (isSingleReverseDep(container)) {
-      // This removal is cheap so let's do it and not keep it in reverseDepsToRemove.
-      Preconditions.checkState(
-          getReverseDepsObject(container).equals(reverseDep),
-          "toRemove: %s container: %s",
-          reverseDep,
-          container);
-      overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
-      return;
-    }
-    @SuppressWarnings("unchecked")
-    List<SkyKey> reverseDepsAsList = (List<SkyKey>) getReverseDepsObject(container);
-    Preconditions.checkState(
-        !reverseDepsAsList.isEmpty(), "toRemove: %s container: %s", reverseDep, container);
-    List<SkyKey> reverseDepsToRemove = getReverseDepsToRemove(container);
-    if (reverseDepsToRemove == null) {
-      reverseDepsToRemove = Lists.newArrayListWithExpectedSize(1);
-      setReverseDepsToRemove(container, reverseDepsToRemove);
-    }
-    reverseDepsToRemove.add(reverseDep);
+    maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.REMOVE);
   }
 
   ImmutableSet<SkyKey> getReverseDeps(T container) {
@@ -299,69 +250,94 @@ public abstract class ReverseDepsUtil<T> {
     }
   }
 
-  void consolidateData(T container) {
-    Object reverseDeps = getReverseDepsObject(container);
-    List<SkyKey> reverseDepsToRemove = getReverseDepsToRemove(container);
-    List<SkyKey> reverseDepsToCheck = getReverseDepsToCheck(container);
-    if (reverseDepsToRemove == null && reverseDepsToCheck == null) {
+  private void consolidateData(T container) {
+    List<Object> dataToConsolidate = getDataToConsolidate(container);
+    if (dataToConsolidate == null) {
       return;
     }
-    Preconditions.checkState(
-        !isSingleReverseDep(container),
-        "We do not delay removals/checks for single lists: %s %s %s",
-        container,
-        reverseDepsToRemove,
-        reverseDepsToCheck);
-    @SuppressWarnings("unchecked")
-    List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
-    // Should not happen, as we only create reverseDepsToRemove/Check in case we have at least one
-    // reverse dep to remove/check.
-    Preconditions.checkState(
-        !reverseDepsAsList.isEmpty(),
-        "Could not do delayed removal/check for %s elements from %s.\n"
-            + "Reverse deps to check: %s. Container: %s",
-        reverseDepsToRemove,
-        reverseDeps,
-        reverseDepsToCheck,
-        container);
-    if (reverseDepsToRemove == null) {
-      Set<SkyKey> reverseDepsAsSet = new HashSet<>(reverseDepsAsList);
+    setDataToConsolidate(container, null);
+    Object reverseDeps = getReverseDepsObject(container);
+    if (isSingleReverseDep(container)) {
       Preconditions.checkState(
-          reverseDepsAsSet.containsAll(reverseDepsToCheck), "%s %s", reverseDepsToCheck, container);
-      setDataToConsolidate(container, null);
+          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;
     }
-
-    Set<SkyKey> toRemove = Sets.newHashSet(reverseDepsToRemove);
-    int expectedRemovals = toRemove.size();
-    Preconditions.checkState(expectedRemovals == reverseDepsToRemove.size(),
-        "A reverse dependency tried to remove itself twice: %s. %s", reverseDepsToRemove,
-        container);
-
-    Set<SkyKey> toCheck =
-        reverseDepsToCheck == null ? new HashSet<SkyKey>() : new HashSet<>(reverseDepsToCheck);
-    List<SkyKey> newReverseDeps = Lists
-        .newArrayListWithExpectedSize(Math.max(0, reverseDepsAsList.size() - expectedRemovals));
-
-    for (SkyKey reverseDep : reverseDepsAsList) {
-      toCheck.remove(reverseDep);
-      if (!toRemove.contains(reverseDep)) {
-        newReverseDeps.add(reverseDep);
+    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",
+              keyToConsolidate,
+              reverseDepsAsSet,
+              container);
+          break;
+        case REMOVE:
+          Preconditions.checkState(
+              reverseDepsAsSet.remove(key), "%s %s %s", keyToConsolidate, reverseDeps, container);
+          break;
+        case ADD:
+          Preconditions.checkState(
+              reverseDepsAsSet.add(key), "%s %s %s", keyToConsolidate, reverseDeps, container);
+          break;
+        default:
+          throw new IllegalStateException(
+              keyToConsolidate + ", " + reverseDepsAsSet + ", " + container);
       }
     }
-    Preconditions.checkState(newReverseDeps.size() == reverseDepsAsList.size() - expectedRemovals,
-        "Could not remove some elements from %s.\nReverse deps to remove: %s. %s", reverseDeps,
-        toRemove, container);
-    Preconditions.checkState(toCheck.isEmpty(), "%s %s", toCheck, container);
 
-    if (newReverseDeps.isEmpty()) {
+    if (reverseDepsAsSet.isEmpty()) {
       overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
-    } else if (newReverseDeps.size() == 1) {
-      overwriteReverseDepsWithObject(container, newReverseDeps.get(0));
+    } else if (reverseDepsAsSet.size() == 1) {
+      overwriteReverseDepsWithObject(container, Iterables.getOnlyElement(reverseDepsAsSet));
     } else {
-      overwriteReverseDepsList(container, newReverseDeps);
+      overwriteReverseDepsList(container, new ArrayList<>(reverseDepsAsSet));
     }
-    setDataToConsolidate(container, null);
   }
 
   String toString(T container) {
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 bf0f6681df..9d743f5f65 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilTest.java
@@ -17,6 +17,7 @@ import static com.google.common.truth.Truth.assertThat;
 
 import com.google.common.collect.ImmutableList;
 
+import org.junit.Assert;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -61,7 +62,7 @@ public class ReverseDepsUtilTest {
         }
 
         @Override
-        void setDataToConsolidate(Example container, Object dataToConsolidate) {
+        void setDataToConsolidate(Example container, List<Object> dataToConsolidate) {
           container.dataToConsolidate = dataToConsolidate;
         }
 
@@ -76,7 +77,7 @@ public class ReverseDepsUtilTest {
         }
 
         @Override
-        Object getDataToConsolidate(Example container) {
+        List<Object> getDataToConsolidate(Example container) {
           return container.dataToConsolidate;
         }
       };
@@ -85,7 +86,7 @@ public class ReverseDepsUtilTest {
 
     Object reverseDeps = ImmutableList.of();
     boolean single;
-    Object dataToConsolidate;
+    List<Object> dataToConsolidate;
 
     @Override
     public String toString() {
@@ -145,6 +146,49 @@ public class ReverseDepsUtilTest {
   }
 
   @Test
+  public void doubleAddThenRemove() {
+    Example example = new Example();
+    SkyKey key = new SkyKey(NODE_TYPE, 0);
+    REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
+    // Should only fail when we call getReverseDeps().
+    REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
+    REVERSE_DEPS_UTIL.removeReverseDep(example, key);
+    try {
+      REVERSE_DEPS_UTIL.getReverseDeps(example);
+      Assert.fail();
+    } catch (IllegalStateException expected) {
+    }
+  }
+
+  @Test
+  public void doubleAddThenRemoveCheckedOnSize() {
+    Example example = new Example();
+    SkyKey fixedKey = new SkyKey(NODE_TYPE, 0);
+    SkyKey key = new SkyKey(NODE_TYPE, 1);
+    REVERSE_DEPS_UTIL.addReverseDeps(example, ImmutableList.of(fixedKey, key));
+    // Should only fail when we reach the limit.
+    REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
+    REVERSE_DEPS_UTIL.removeReverseDep(example, key);
+    REVERSE_DEPS_UTIL.checkReverseDep(example, fixedKey);
+    try {
+      REVERSE_DEPS_UTIL.checkReverseDep(example, fixedKey);
+      Assert.fail();
+    } catch (IllegalStateException expected) {
+    }
+  }
+
+  @Test
+  public void addRemoveAdd() {
+    Example example = new Example();
+    SkyKey fixedKey = new SkyKey(NODE_TYPE, 0);
+    SkyKey key = new SkyKey(NODE_TYPE, 1);
+    REVERSE_DEPS_UTIL.addReverseDeps(example, ImmutableList.of(fixedKey, key));
+    REVERSE_DEPS_UTIL.removeReverseDep(example, key);
+    REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
+    assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).containsExactly(fixedKey, key);
+  }
+
+  @Test
   public void testMaybeCheck() {
     Example example = new Example();
     for (int i = 0; i < numElements; i++) {