Don't remove reverse deps until node is known to be changed. This helps avoid mutating the deps of nodes that are still going to be deps after evaluation is finished.
--
MOS_MIGRATED_REVID=103659429
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 fa8e308..f3a6a81 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -18,11 +18,11 @@
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
import java.util.Collection;
-import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;
@@ -82,49 +82,49 @@
protected boolean reverseDepIsSingleObject = false;
/**
- * During the invalidation we keep the reverse deps to be removed in this list instead of directly
- * removing them from {@code reverseDeps}. That is because removals from reverseDeps are O(N).
+ * When reverse deps are removed or checked for presence, we store them in this object instead of
+ * directly removing/checking them. That is because removals/checks in reverseDeps are O(N).
* Originally reverseDeps was a HashSet, but because of memory consumption we switched to a list.
*
* <p>This requires that any usage of reverseDeps (contains, add, the list of reverse deps) call
- * {@code consolidateReverseDepsRemovals} first. While this operation is not free, it can be done
- * more effectively than trying to remove each dirty reverse dependency individually (O(N) each
- * time).
+ * {@code consolidateData} first. While this operation is not free, it can be done
+ * more effectively than trying to remove/check each dirty reverse dependency individually (O(N)
+ * each time).
*/
- private List<SkyKey> reverseDepsToRemove = null;
+ private Object reverseDepsDataToConsolidate = null;
protected static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL =
new ReverseDepsUtil<InMemoryNodeEntry>() {
- @Override
- void setReverseDepsObject(InMemoryNodeEntry container, Object object) {
- container.reverseDeps = object;
- }
+ @Override
+ void setReverseDepsObject(InMemoryNodeEntry container, Object object) {
+ container.reverseDeps = object;
+ }
- @Override
- void setSingleReverseDep(InMemoryNodeEntry container, boolean singleObject) {
- container.reverseDepIsSingleObject = singleObject;
- }
+ @Override
+ void setSingleReverseDep(InMemoryNodeEntry container, boolean singleObject) {
+ container.reverseDepIsSingleObject = singleObject;
+ }
- @Override
- void setReverseDepsToRemove(InMemoryNodeEntry container, List<SkyKey> object) {
- container.reverseDepsToRemove = object;
- }
+ @Override
+ void setDataToConsolidate(InMemoryNodeEntry container, Object dataToConsolidate) {
+ container.reverseDepsDataToConsolidate = dataToConsolidate;
+ }
- @Override
- Object getReverseDepsObject(InMemoryNodeEntry container) {
- return container.reverseDeps;
- }
+ @Override
+ Object getReverseDepsObject(InMemoryNodeEntry container) {
+ return container.reverseDeps;
+ }
- @Override
- boolean isSingleReverseDep(InMemoryNodeEntry container) {
- return container.reverseDepIsSingleObject;
- }
+ @Override
+ boolean isSingleReverseDep(InMemoryNodeEntry container) {
+ return container.reverseDepIsSingleObject;
+ }
- @Override
- List<SkyKey> getReverseDepsToRemove(InMemoryNodeEntry container) {
- return container.reverseDepsToRemove;
- }
- };
+ @Override
+ 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
@@ -202,7 +202,7 @@
private synchronized Set<SkyKey> setStateFinishedAndReturnReverseDeps() {
// Get reverse deps that need to be signaled.
ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal();
- REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
+ REVERSE_DEPS_UTIL.consolidateData(this);
REVERSE_DEPS_UTIL.addReverseDeps(this, reverseDepsToSignal);
this.directDeps = buildingState.getFinishedDirectDeps().compress();
@@ -247,7 +247,7 @@
public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
if (reverseDep != null) {
if (keepEdges()) {
- REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
+ REVERSE_DEPS_UTIL.consolidateData(this);
REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(this, reverseDep);
}
if (isDone()) {
@@ -263,7 +263,20 @@
return DependencyState.DONE;
}
return buildingState.startEvaluating() ? DependencyState.NEEDS_SCHEDULING
- : DependencyState.ADDED_DEP;
+ : DependencyState.ALREADY_EVALUATING;
+ }
+
+ @Override
+ public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
+ Preconditions.checkNotNull(reverseDep, this);
+ Preconditions.checkState(keepEdges(), "%s %s", reverseDep, this);
+ if (!isDone()) {
+ REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
+ buildingState.addReverseDepToSignal(reverseDep);
+ } else {
+ REVERSE_DEPS_UTIL.checkReverseDep(this, reverseDep);
+ }
+ return addReverseDepAndCheckIfDone(null);
}
@Override
@@ -271,19 +284,23 @@
if (!keepEdges()) {
return;
}
- if (REVERSE_DEPS_UTIL.reverseDepsIsEmpty(this)) {
- // If an entry has no existing reverse deps, all its reverse deps are to signal, and vice
- // versa.
- buildingState.removeReverseDepToSignal(reverseDep);
- } else {
- REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
- }
+ REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
}
@Override
- public synchronized Collection<SkyKey> getReverseDeps() {
+ public synchronized void removeInProgressReverseDep(SkyKey reverseDep) {
+ buildingState.removeReverseDepToSignal(reverseDep);
+ }
+
+ @Override
+ public synchronized Iterable<SkyKey> getReverseDeps() {
assertKeepEdges();
- return REVERSE_DEPS_UTIL.getReverseDeps(this);
+ Iterable<SkyKey> reverseDeps = REVERSE_DEPS_UTIL.getReverseDeps(this);
+ if (isDone()) {
+ return reverseDeps;
+ } else {
+ return Iterables.concat(reverseDeps, buildingState.getReverseDepsToSignal());
+ }
}
@Override
@@ -313,15 +330,13 @@
}
@Override
- @Nullable
- public synchronized Iterable<SkyKey> markDirty(boolean isChanged) {
+ public synchronized boolean markDirty(boolean isChanged) {
assertKeepEdges();
if (isDone()) {
- GroupedList<SkyKey> lastDirectDeps = GroupedList.create(directDeps);
- buildingState = BuildingState.newDirtyState(isChanged, lastDirectDeps, value);
+ buildingState =
+ BuildingState.newDirtyState(isChanged, GroupedList.<SkyKey>create(directDeps), value);
value = null;
- directDeps = null;
- return lastDirectDeps.toSet();
+ return true;
}
// 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
@@ -330,13 +345,12 @@
Preconditions.checkState(isChanged != isChanged(),
"Cannot mark node dirty twice or changed twice: %s", this);
Preconditions.checkState(value == null, "Value should have been reset already %s", this);
- Preconditions.checkState(directDeps == null, "direct deps not already reset %s", this);
if (isChanged) {
// If the changed marker lost the race, we just need to mark changed in this method -- all
// other work was done by the dirty marker.
buildingState.markChanged();
}
- return null;
+ return false;
}
@Override
@@ -371,10 +385,27 @@
/** @see BuildingState#getNextDirtyDirectDeps() */
@Override
public synchronized Collection<SkyKey> getNextDirtyDirectDeps() {
+ Preconditions.checkState(isReady(), this);
return buildingState.getNextDirtyDirectDeps();
}
@Override
+ public synchronized Iterable<SkyKey> getAllDirectDepsForIncompleteNode() {
+ Preconditions.checkState(!isDone(), this);
+ if (!isDirty()) {
+ return getTemporaryDirectDeps();
+ } else {
+ return Iterables.concat(
+ getTemporaryDirectDeps(), buildingState.getAllRemainingDirtyDirectDeps());
+ }
+ }
+
+ @Override
+ public synchronized Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps() {
+ return buildingState.markRebuildingAndGetAllRemainingDirtyDirectDeps();
+ }
+
+ @Override
public synchronized Set<SkyKey> getTemporaryDirectDeps() {
Preconditions.checkState(!isDone(), "temporary shouldn't be done: %s", this);
return buildingState.getDirectDepsForBuild();
@@ -403,13 +434,15 @@
}
@Override
- public String toString() {
+ public synchronized String toString() {
return MoreObjects.toStringHelper(this)
+ .add("identity", System.identityHashCode(this))
.add("value", value)
.add("version", version)
.add("directDeps", directDeps == null ? null : GroupedList.create(directDeps))
.add("reverseDeps", REVERSE_DEPS_UTIL.toString(this))
- .add("buildingState", buildingState).toString();
+ .add("buildingState", buildingState)
+ .toString();
}
/**
