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
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 d2f92b8..455ecda 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 @@
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 @@
*/
@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 @@
* 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 @@
}
final boolean isEvaluating() {
- return signaledDeps > -1;
+ return signaledDeps > NOT_EVALUATING_SENTINEL;
}
/**
@@ -191,34 +150,10 @@
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 f0003f7..e0b3579 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 @@
}
@Override
+ public Iterable<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
+ return getDelegate().getAllReverseDepsForNodeBeingDeleted();
+ }
+
+ @Override
public void markRebuilding() {
getDelegate().markRebuilding();
}
@@ -171,8 +176,8 @@
}
@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 76ebe75..217ebd9 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 @@
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 fefee27..7f83301 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.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 @@
*
* <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>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>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, {@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 @@
}
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 @@
@Override
public synchronized Set<SkyKey> getInProgressReverseDeps() {
Preconditions.checkState(!isDone(), this);
- return buildingState.getReverseDepsToSignal();
+ return ReverseDepsUtility.returnNewElements(this, getOpToStoreBare());
}
@Override
@@ -256,23 +247,15 @@
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 @@
: 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 @@
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 @@
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 @@
.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 @@
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 577639a..d7bb2d2 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 @@
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 @@
}
// 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 0000000..2b2572c
--- /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 d7f7fcf..57334d6 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 @@
* 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 @@
/**
* 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 @@
@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 e45f0a8..19b18cb 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 @@
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 52ad312..0000000
--- 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 6f29e39..0000000
--- 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 0000000..0f93fa6
--- /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();
+ }
+}
diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
index 49db9cd..7876d57 100644
--- a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
+++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
@@ -135,9 +135,10 @@
}
@Override
- public synchronized Collection<SkyKey> getReverseDeps() throws InterruptedException {
+ public synchronized Collection<SkyKey> getReverseDepsForDoneEntry()
+ throws InterruptedException {
TreeSet<SkyKey> result = new TreeSet<>(ALPHABETICAL_SKYKEY_COMPARATOR);
- Iterables.addAll(result, super.getReverseDeps());
+ Iterables.addAll(result, super.getReverseDepsForDoneEntry());
return result;
}
diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
index cfb656b..2ab0346 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -337,12 +337,12 @@
.setComputedValue(CONCATENATE);
eval(false, skyKey("ab_c"), skyKey("bc"));
- assertThat(graph.get(null, Reason.OTHER, skyKey("a"))
- .getReverseDeps()).containsExactly(skyKey("ab"));
- assertThat(graph.get(null, Reason.OTHER, skyKey("b"))
- .getReverseDeps()).containsExactly(skyKey("ab"), skyKey("bc"));
- assertThat(graph.get(null, Reason.OTHER, skyKey("c"))
- .getReverseDeps()).containsExactly(skyKey("ab_c"), skyKey("bc"));
+ assertThat(graph.get(null, Reason.OTHER, skyKey("a")).getReverseDepsForDoneEntry())
+ .containsExactly(skyKey("ab"));
+ assertThat(graph.get(null, Reason.OTHER, skyKey("b")).getReverseDepsForDoneEntry())
+ .containsExactly(skyKey("ab"), skyKey("bc"));
+ assertThat(graph.get(null, Reason.OTHER, skyKey("c")).getReverseDepsForDoneEntry())
+ .containsExactly(skyKey("ab_c"), skyKey("bc"));
invalidateWithoutError(new DirtyTrackingProgressReceiver(null), skyKey("ab"));
eval(false);
@@ -356,18 +356,18 @@
if (reverseDepsPresent()) {
reverseDeps.add(skyKey("ab"));
}
- assertThat(graph.get(null, Reason.OTHER, skyKey("a"))
- .getReverseDeps()).containsExactlyElementsIn(reverseDeps);
+ assertThat(graph.get(null, Reason.OTHER, skyKey("a")).getReverseDepsForDoneEntry())
+ .containsExactlyElementsIn(reverseDeps);
reverseDeps.add(skyKey("bc"));
- assertThat(graph.get(null, Reason.OTHER, skyKey("b"))
- .getReverseDeps()).containsExactlyElementsIn(reverseDeps);
+ assertThat(graph.get(null, Reason.OTHER, skyKey("b")).getReverseDepsForDoneEntry())
+ .containsExactlyElementsIn(reverseDeps);
reverseDeps.clear();
if (reverseDepsPresent()) {
reverseDeps.add(skyKey("ab_c"));
}
reverseDeps.add(skyKey("bc"));
- assertThat(graph.get(null, Reason.OTHER, skyKey("c"))
- .getReverseDeps()).containsExactlyElementsIn(reverseDeps);
+ assertThat(graph.get(null, Reason.OTHER, skyKey("c")).getReverseDepsForDoneEntry())
+ .containsExactlyElementsIn(reverseDeps);
}
@Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
index 0510523..932878f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
@@ -197,7 +197,7 @@
for (int k = chunkSize; k <= numIterations; k++) {
entry.removeReverseDep(key("rdep" + j));
entry.addReverseDepAndCheckIfDone(key("rdep" + j));
- entry.getReverseDeps();
+ entry.getReverseDepsForDoneEntry();
}
} catch (InterruptedException e) {
fail("Test failed: " + e.toString());
@@ -213,7 +213,9 @@
wrapper.waitForTasksAndMaybeThrow();
assertFalse(ExecutorUtil.interruptibleShutdown(pool));
assertEquals(new StringValue("foo1"), graph.get(null, Reason.OTHER, key).getValue());
- assertEquals(numKeys + 1, Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDeps()));
+ assertEquals(
+ numKeys + 1,
+ Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDepsForDoneEntry()));
graph = getGraph(getNextVersion(startingVersion));
NodeEntry sameEntry = Preconditions.checkNotNull(graph.get(null, Reason.OTHER, key));
@@ -223,7 +225,9 @@
sameEntry.markRebuilding();
sameEntry.setValue(new StringValue("foo2"), getNextVersion(startingVersion));
assertEquals(new StringValue("foo2"), graph.get(null, Reason.OTHER, key).getValue());
- assertEquals(numKeys + 1, Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDeps()));
+ assertEquals(
+ numKeys + 1,
+ Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDepsForDoneEntry()));
}
// Tests adding inflight nodes with a given key while an existing node with the same key
@@ -451,7 +455,7 @@
NodeEntry entry = graph.get(null, Reason.OTHER, key("foo" + i));
assertThat(entry.getValue()).isEqualTo(new StringValue("bar" + i));
assertThat(entry.getVersion()).isEqualTo(getNextVersion(startingVersion));
- for (SkyKey key : entry.getReverseDeps()) {
+ for (SkyKey key : entry.getReverseDepsForDoneEntry()) {
assertEquals(key("rdep"), key);
}
for (SkyKey key : entry.getDirectDeps()) {
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index 8b8fb81..5829329 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -101,10 +101,10 @@
assertEquals(DependencyState.ALREADY_EVALUATING, entry.addReverseDepAndCheckIfDone(father));
assertThat(setValue(entry, new SkyValue() {},
/*errorInfo=*/null, /*graphVersion=*/0L)).containsExactly(mother, father);
- assertThat(entry.getReverseDeps()).containsExactly(mother, father);
+ assertThat(entry.getReverseDepsForDoneEntry()).containsExactly(mother, father);
assertTrue(entry.isDone());
entry.removeReverseDep(mother);
- assertFalse(Iterables.contains(entry.getReverseDeps(), mother));
+ assertFalse(Iterables.contains(entry.getReverseDepsForDoneEntry(), mother));
}
@Test
@@ -337,7 +337,7 @@
try {
entry.addReverseDepAndCheckIfDone(parent);
// We only check for duplicates when we request all the reverse deps.
- entry.getReverseDeps();
+ entry.getReverseDepsForDoneEntry();
fail("Cannot add same dep twice");
} catch (IllegalStateException e) {
// Expected.
@@ -353,7 +353,7 @@
try {
entry.addReverseDepAndCheckIfDone(parent);
// We only check for duplicates when we request all the reverse deps.
- entry.getReverseDeps();
+ entry.getReverseDepsForDoneEntry();
fail("Cannot add same dep twice");
} catch (IllegalStateException e) {
// Expected.
@@ -692,9 +692,9 @@
assertThat(clone1.getDirectDeps()).containsExactly(originalChild);
assertThat(clone2.getDirectDeps()).containsExactly(newChild);
- assertThat(entry.getReverseDeps()).hasSize(0);
- assertThat(clone1.getReverseDeps()).containsExactly(key("parent1"));
- assertThat(clone2.getReverseDeps()).containsExactly(key("parent1"), key("parent2"));
+ assertThat(entry.getReverseDepsForDoneEntry()).hasSize(0);
+ assertThat(clone1.getReverseDepsForDoneEntry()).containsExactly(key("parent1"));
+ assertThat(clone2.getReverseDepsForDoneEntry()).containsExactly(key("parent1"), key("parent2"));
}
@Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java
deleted file mode 100644
index d66dc67..0000000
--- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java
+++ /dev/null
@@ -1,199 +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 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;
-import org.junit.runners.Parameterized.Parameters;
-
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.List;
-
-/**
- * Test for {@code ReverseDepsUtilImpl}.
- */
-@RunWith(Parameterized.class)
-public class ReverseDepsUtilImplTest {
-
- private static final SkyFunctionName NODE_TYPE = SkyFunctionName.create("Type");
- private final int numElements;
-
- @Parameters(name = "numElements-{0}")
- public static List<Object[]> paramenters() {
- List<Object[]> params = new ArrayList<>();
- for (int i = 0; i < 20; i++) {
- params.add(new Object[] {i});
- }
- return params;
- }
-
- public ReverseDepsUtilImplTest(int numElements) {
- this.numElements = numElements;
- }
-
- private static final ReverseDepsUtil<Example> REVERSE_DEPS_UTIL =
- new ReverseDepsUtilImpl<Example>() {
- @Override
- void setReverseDepsObject(Example container, Object object) {
- container.reverseDeps = object;
- }
-
- @Override
- void setDataToConsolidate(Example container, List<Object> dataToConsolidate) {
- container.dataToConsolidate = dataToConsolidate;
- }
-
- @Override
- Object getReverseDepsObject(Example container) {
- return container.reverseDeps;
- }
-
- @Override
- List<Object> getDataToConsolidate(Example container) {
- return container.dataToConsolidate;
- }
- };
-
- private class Example {
-
- Object reverseDeps = ImmutableList.of();
- boolean single;
- List<Object> dataToConsolidate;
-
- @Override
- public String toString() {
- return "Example: " + reverseDeps + ", " + single + ", " + dataToConsolidate;
- }
- }
-
- @Test
- public void testAddAndRemove() {
- for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) {
- Example example = new Example();
- for (int j = 0; j < numElements; j++) {
- REVERSE_DEPS_UTIL.addReverseDeps(
- example, Collections.singleton(SkyKey.create(NODE_TYPE, j)));
- }
- // Not a big test but at least check that it does not blow up.
- assertThat(REVERSE_DEPS_UTIL.toString(example)).isNotEmpty();
- assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements);
- for (int i = 0; i < numRemovals; i++) {
- REVERSE_DEPS_UTIL.removeReverseDep(example, SkyKey.create(NODE_TYPE, i));
- }
- assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals);
- assertThat(example.dataToConsolidate).isNull();
- }
- }
-
- // Same as testAdditionAndRemoval but we add all the reverse deps in one call.
- @Test
- public void testAddAllAndRemove() {
- for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) {
- Example example = new Example();
- List<SkyKey> toAdd = new ArrayList<>();
- for (int j = 0; j < numElements; j++) {
- toAdd.add(SkyKey.create(NODE_TYPE, j));
- }
- REVERSE_DEPS_UTIL.addReverseDeps(example, toAdd);
- assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements);
- for (int i = 0; i < numRemovals; i++) {
- REVERSE_DEPS_UTIL.removeReverseDep(example, SkyKey.create(NODE_TYPE, i));
- }
- assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals);
- assertThat(example.dataToConsolidate).isNull();
- }
- }
-
- @Test
- public void testDuplicateCheckOnGetReverseDeps() {
- Example example = new Example();
- for (int i = 0; i < numElements; i++) {
- REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, i)));
- }
- // Should only fail when we call getReverseDeps().
- REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, 0)));
- try {
- REVERSE_DEPS_UTIL.getReverseDeps(example);
- assertThat(numElements).isEqualTo(0);
- } catch (Exception expected) {
- }
- }
-
- @Test
- public void doubleAddThenRemove() {
- Example example = new Example();
- SkyKey key = SkyKey.create(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 = SkyKey.create(NODE_TYPE, 0);
- SkyKey key = SkyKey.create(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 = SkyKey.create(NODE_TYPE, 0);
- SkyKey key = SkyKey.create(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++) {
- REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, i)));
- // This should always succeed, since the next element is still not present.
- REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, i + 1));
- }
- try {
- REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, 0));
- // Should only fail if empty or above the checking threshold.
- assertThat(numElements == 0 || numElements >= ReverseDepsUtilImpl.MAYBE_CHECK_THRESHOLD)
- .isTrue();
- } catch (Exception expected) {
- }
- }
-}
diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
new file mode 100644
index 0000000..3001c2a
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
@@ -0,0 +1,162 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.collect.ImmutableList;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+/** Test for {@code ReverseDepsUtility}. */
+@RunWith(Parameterized.class)
+public class ReverseDepsUtilityTest {
+
+ private static final SkyFunctionName NODE_TYPE = SkyFunctionName.create("Type");
+ private final int numElements;
+
+ @Parameters(name = "numElements-{0}")
+ public static List<Object[]> paramenters() {
+ List<Object[]> params = new ArrayList<>();
+ for (int i = 0; i < 20; i++) {
+ params.add(new Object[] {i});
+ }
+ return params;
+ }
+
+ public ReverseDepsUtilityTest(int numElements) {
+ this.numElements = numElements;
+ }
+
+ @Test
+ public void testAddAndRemove() {
+ for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) {
+ InMemoryNodeEntry example = new InMemoryNodeEntry();
+ for (int j = 0; j < numElements; j++) {
+ ReverseDepsUtility.addReverseDeps(
+ example, Collections.singleton(SkyKey.create(NODE_TYPE, j)));
+ }
+ // Not a big test but at least check that it does not blow up.
+ assertThat(ReverseDepsUtility.toString(example)).isNotEmpty();
+ assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements);
+ for (int i = 0; i < numRemovals; i++) {
+ ReverseDepsUtility.removeReverseDep(example, SkyKey.create(NODE_TYPE, i));
+ }
+ assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals);
+ assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull();
+ }
+ }
+
+ // Same as testAdditionAndRemoval but we add all the reverse deps in one call.
+ @Test
+ public void testAddAllAndRemove() {
+ for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) {
+ InMemoryNodeEntry example = new InMemoryNodeEntry();
+ List<SkyKey> toAdd = new ArrayList<>();
+ for (int j = 0; j < numElements; j++) {
+ toAdd.add(SkyKey.create(NODE_TYPE, j));
+ }
+ ReverseDepsUtility.addReverseDeps(example, toAdd);
+ assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements);
+ for (int i = 0; i < numRemovals; i++) {
+ ReverseDepsUtility.removeReverseDep(example, SkyKey.create(NODE_TYPE, i));
+ }
+ assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals);
+ assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull();
+ }
+ }
+
+ @Test
+ public void testDuplicateCheckOnGetReverseDeps() {
+ InMemoryNodeEntry example = new InMemoryNodeEntry();
+ for (int i = 0; i < numElements; i++) {
+ ReverseDepsUtility.addReverseDeps(
+ example, Collections.singleton(SkyKey.create(NODE_TYPE, i)));
+ }
+ // Should only fail when we call getReverseDeps().
+ ReverseDepsUtility.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, 0)));
+ try {
+ ReverseDepsUtility.getReverseDeps(example);
+ assertThat(numElements).isEqualTo(0);
+ } catch (Exception expected) {
+ }
+ }
+
+ @Test
+ public void doubleAddThenRemove() {
+ InMemoryNodeEntry example = new InMemoryNodeEntry();
+ SkyKey key = SkyKey.create(NODE_TYPE, 0);
+ ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
+ // Should only fail when we call getReverseDeps().
+ ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
+ ReverseDepsUtility.removeReverseDep(example, key);
+ try {
+ ReverseDepsUtility.getReverseDeps(example);
+ Assert.fail();
+ } catch (IllegalStateException expected) {
+ }
+ }
+
+ @Test
+ public void doubleAddThenRemoveCheckedOnSize() {
+ InMemoryNodeEntry example = new InMemoryNodeEntry();
+ SkyKey fixedKey = SkyKey.create(NODE_TYPE, 0);
+ SkyKey key = SkyKey.create(NODE_TYPE, 1);
+ ReverseDepsUtility.addReverseDeps(example, ImmutableList.of(fixedKey, key));
+ // Should only fail when we reach the limit.
+ ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
+ ReverseDepsUtility.removeReverseDep(example, key);
+ ReverseDepsUtility.checkReverseDep(example, fixedKey);
+ try {
+ ReverseDepsUtility.checkReverseDep(example, fixedKey);
+ Assert.fail();
+ } catch (IllegalStateException expected) {
+ }
+ }
+
+ @Test
+ public void addRemoveAdd() {
+ InMemoryNodeEntry example = new InMemoryNodeEntry();
+ SkyKey fixedKey = SkyKey.create(NODE_TYPE, 0);
+ SkyKey key = SkyKey.create(NODE_TYPE, 1);
+ ReverseDepsUtility.addReverseDeps(example, ImmutableList.of(fixedKey, key));
+ ReverseDepsUtility.removeReverseDep(example, key);
+ ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
+ assertThat(ReverseDepsUtility.getReverseDeps(example)).containsExactly(fixedKey, key);
+ }
+
+ @Test
+ public void testMaybeCheck() {
+ InMemoryNodeEntry example = new InMemoryNodeEntry();
+ for (int i = 0; i < numElements; i++) {
+ ReverseDepsUtility.addReverseDeps(
+ example, Collections.singleton(SkyKey.create(NODE_TYPE, i)));
+ // This should always succeed, since the next element is still not present.
+ ReverseDepsUtility.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, i + 1));
+ }
+ try {
+ ReverseDepsUtility.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, 0));
+ // Should only fail if empty or above the checking threshold.
+ assertThat(numElements == 0 || numElements >= ReverseDepsUtility.MAYBE_CHECK_THRESHOLD)
+ .isTrue();
+ } catch (Exception expected) {
+ }
+ }
+}
