Extract ReverseDepsUtil interface so that InMemoryNodeEntry can be partially isolated from implementation details.

--
MOS_MIGRATED_REVID=108523104

4 files changed, 439 insertions, 377 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 d0d2573af7..ad16c38a88 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -123,7 +123,7 @@ public class BuildingState {
   private boolean reverseDepIsSingleObject = false;
 
   private static final ReverseDepsUtil<BuildingState> REVERSE_DEPS_UTIL =
-      new ReverseDepsUtil<BuildingState>() {
+      new ReverseDepsUtilImpl<BuildingState>() {
         @Override
         void setReverseDepsObject(BuildingState container, Object object) {
           container.reverseDepsToSignal = object;
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 8c1fa7f119..261c836344 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -98,14 +98,14 @@ public class InMemoryNodeEntry implements NodeEntry {
    * are O(N). Originally reverseDeps was a HashSet, but because of memory consumption we switched
    * to a list.
    *
-   * <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).
+   * <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
+   * than trying to remove/check each dirty reverse dependency individually (O(N) each time).
    */
   private List<Object> reverseDepsDataToConsolidate = null;
 
   protected static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL =
-      new ReverseDepsUtil<InMemoryNodeEntry>() {
+      new ReverseDepsUtilImpl<InMemoryNodeEntry>() {
         @Override
         void setReverseDepsObject(InMemoryNodeEntry container, Object object) {
           container.reverseDeps = object;
@@ -209,16 +209,23 @@ public class InMemoryNodeEntry implements NodeEntry {
     return ValueWithMetadata.getMaybeErrorInfo(value);
   }
 
+  /**
+   * Puts entry in "done" state, as checked by {@link #isDone}. Subclasses that override one should
+   * override the other.
+   */
+  protected void markDone() {
+    buildingState = null;
+  }
+
   protected synchronized Set<SkyKey> setStateFinishedAndReturnReverseDeps() {
     // Get reverse deps that need to be signaled.
     ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal();
-    REVERSE_DEPS_UTIL.addReverseDeps(this, reverseDepsToSignal);
+    getReverseDepsUtil().addReverseDeps(this, reverseDepsToSignal);
     // Force consistency check.
-    REVERSE_DEPS_UTIL.getReverseDeps(this);
+    getReverseDepsUtil().getReverseDeps(this);
     this.directDeps = buildingState.getFinishedDirectDeps().compress();
 
-    // Set state of entry to done.
-    buildingState = null;
+    markDone();
 
     if (!keepEdges()) {
       this.directDeps = null;
@@ -257,15 +264,19 @@ public class InMemoryNodeEntry implements NodeEntry {
     return setStateFinishedAndReturnReverseDeps();
   }
 
+  protected ReverseDepsUtil<InMemoryNodeEntry> getReverseDepsUtil() {
+    return REVERSE_DEPS_UTIL;
+  }
+
   @Override
   public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
     if (reverseDep != null) {
       if (keepEdges()) {
-        REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(this, reverseDep);
+        getReverseDepsUtil().maybeCheckReverseDepNotPresent(this, reverseDep);
       }
       if (isDone()) {
         if (keepEdges()) {
-          REVERSE_DEPS_UTIL.addReverseDeps(this, ImmutableList.of(reverseDep));
+          getReverseDepsUtil().addReverseDeps(this, ImmutableList.of(reverseDep));
         }
       } else {
         // Parent should never register itself twice in the same build.
@@ -284,10 +295,10 @@ public class InMemoryNodeEntry implements NodeEntry {
     Preconditions.checkNotNull(reverseDep, this);
     Preconditions.checkState(keepEdges(), "%s %s", reverseDep, this);
     if (!isDone()) {
-      REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
+      getReverseDepsUtil().removeReverseDep(this, reverseDep);
       buildingState.addReverseDepToSignal(reverseDep);
     } else {
-      REVERSE_DEPS_UTIL.checkReverseDep(this, reverseDep);
+      getReverseDepsUtil().checkReverseDep(this, reverseDep);
     }
     return addReverseDepAndCheckIfDone(null);
   }
@@ -297,7 +308,7 @@ public class InMemoryNodeEntry implements NodeEntry {
     if (!keepEdges()) {
       return;
     }
-    REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
+    getReverseDepsUtil().removeReverseDep(this, reverseDep);
   }
 
   @Override
@@ -308,7 +319,7 @@ public class InMemoryNodeEntry implements NodeEntry {
   @Override
   public synchronized Iterable<SkyKey> getReverseDeps() {
     assertKeepEdges();
-    Iterable<SkyKey> reverseDeps = REVERSE_DEPS_UTIL.getReverseDeps(this);
+    Iterable<SkyKey> reverseDeps = getReverseDepsUtil().getReverseDeps(this);
     if (isDone()) {
       return reverseDeps;
     } else {
@@ -349,7 +360,7 @@ public class InMemoryNodeEntry implements NodeEntry {
       buildingState =
           BuildingState.newDirtyState(isChanged, GroupedList.<SkyKey>create(directDeps), value);
       value = null;
-      return new MarkedDirtyResult(REVERSE_DEPS_UTIL.getReverseDeps(this));
+      return new MarkedDirtyResult(getReverseDepsUtil().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
@@ -452,7 +463,7 @@ public class InMemoryNodeEntry implements NodeEntry {
         .add("lastChangedVersion", lastChangedVersion)
         .add("lastEvaluatedVersion", lastEvaluatedVersion)
         .add("directDeps", directDeps == null ? null : GroupedList.create(directDeps))
-        .add("reverseDeps", REVERSE_DEPS_UTIL.toString(this))
+        .add("reverseDeps", getReverseDepsUtil().toString(this))
         .add("buildingState", buildingState)
         .toString();
   }
@@ -469,7 +480,7 @@ public class InMemoryNodeEntry implements NodeEntry {
     nodeEntry.value = value;
     nodeEntry.lastChangedVersion = this.lastChangedVersion;
     nodeEntry.lastEvaluatedVersion = this.lastEvaluatedVersion;
-    REVERSE_DEPS_UTIL.addReverseDeps(nodeEntry, REVERSE_DEPS_UTIL.getReverseDeps(this));
+    getReverseDepsUtil().addReverseDeps(nodeEntry, getReverseDepsUtil().getReverseDeps(this));
     nodeEntry.directDeps = directDeps;
     nodeEntry.buildingState = null;
     return nodeEntry;
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 86c39ab2e5..219758b30d 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
@@ -1,4 +1,4 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
+// 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.
@@ -13,376 +13,33 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
-import com.google.common.base.MoreObjects;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Interner;
-import com.google.common.collect.Interners;
-import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
-import com.google.devtools.build.lib.collect.CompactHashSet;
 
-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.
+ * A utility interface for dealing with reverse deps in NodeEntry and BuildingState implementations.
  *
- * <p>The reason of this class it 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).
+ * <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 class is public only for the benefit of alternative graph implementations outside of the
- * package.
+ * <p>This interface is public only for the benefit of alternative graph implementations outside of
+ * the package.
  */
-public abstract class ReverseDepsUtil<T> {
-
-  static final int MAYBE_CHECK_THRESHOLD = 10;
-
-  private static final Interner<KeyToConsolidate> consolidateInterner = Interners.newWeakInterner();
-
-  abstract void setReverseDepsObject(T container, Object object);
-
-  abstract void setSingleReverseDep(T container, boolean singleObject);
-
-  abstract void setDataToConsolidate(T container, @Nullable List<Object> dataToConsolidate);
-
-  abstract Object getReverseDepsObject(T container);
-
-  abstract boolean isSingleReverseDep(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);
-    }
-  }
-
+public interface ReverseDepsUtil<T> {
+  void addReverseDeps(T container, Collection<SkyKey> reverseDeps);
   /**
-   * 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. We do not check if there are delayed data to
-   * consolidate, since then presence or absence is not known.
+   * 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) {
-    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);
-    }
-  }
-
-  void checkReverseDep(T container, SkyKey reverseDep) {
-    maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.CHECK);
-  }
-
-  /**
-   * See {@code addReverseDeps} method.
-   */
-  void removeReverseDep(T container, SkyKey reverseDep) {
-    maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.REMOVE);
-  }
-
-  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;
-    }
-  }
-
-  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",
-              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);
-      }
-    }
+  void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep);
 
-    if (reverseDepsAsSet.isEmpty()) {
-      overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
-    } else if (reverseDepsAsSet.size() == 1) {
-      overwriteReverseDepsWithObject(container, Iterables.getOnlyElement(reverseDepsAsSet));
-    } else {
-      overwriteReverseDepsList(container, new ArrayList<>(reverseDepsAsSet));
-    }
-  }
+  void checkReverseDep(T container, SkyKey reverseDep);
 
-  String toString(T container) {
-    return MoreObjects.toStringHelper("ReverseDeps")
-        .add("reverseDeps", getReverseDepsObject(container))
-        .add("singleReverseDep", isSingleReverseDep(container))
-        .add("dataToConsolidate", getDataToConsolidate(container))
-        .toString();
-  }
+  void removeReverseDep(T container, SkyKey reverseDep);
 
-  private void overwriteReverseDepsWithObject(T container, SkyKey newObject) {
-    setReverseDepsObject(container, newObject);
-    setSingleReverseDep(container, true);
-  }
+  ImmutableSet<SkyKey> getReverseDeps(T container);
 
-  private void overwriteReverseDepsList(T container, List<SkyKey> list) {
-    setReverseDepsObject(container, list);
-    setSingleReverseDep(container, false);
-  }
+  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
new file mode 100644
index 0000000000..11af1005a7
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtilImpl.java
@@ -0,0 +1,394 @@
+// 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.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Interner;
+import com.google.common.collect.Interners;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.collect.CompactHashSet;
+
+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 = Interners.newWeakInterner();
+
+  abstract void setReverseDepsObject(T container, Object object);
+
+  abstract void setSingleReverseDep(T container, boolean singleObject);
+
+  abstract void setDataToConsolidate(T container, @Nullable List<Object> dataToConsolidate);
+
+  abstract Object getReverseDepsObject(T container);
+
+  abstract boolean isSingleReverseDep(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);
+    }
+  }
+
+  /**
+   *  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;
+    }
+  }
+
+  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",
+              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);
+      }
+    }
+
+    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);
+    setSingleReverseDep(container, true);
+  }
+
+  private void overwriteReverseDepsList(T container, List<SkyKey> list) {
+    setReverseDepsObject(container, list);
+    setSingleReverseDep(container, false);
+  }
+}