1 files changed, 0 insertions, 413 deletions
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);
-  }
-}