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/ReverseDepsUtil.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
index 807aa8c..ed8d724 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
@@ -21,10 +21,14 @@
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
+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
@@ -46,13 +50,126 @@
abstract void setSingleReverseDep(T container, boolean singleObject);
- abstract void setReverseDepsToRemove(T container, List<SkyKey> object);
+ abstract void setDataToConsolidate(T container, Object dataToConsolidate);
abstract Object getReverseDepsObject(T container);
abstract boolean isSingleReverseDep(T container);
- abstract List<SkyKey> getReverseDepsToRemove(T container);
+ abstract Object getDataToConsolidate(T container);
+
+ private enum DataState {
+ NULL,
+ CHECK_ONLY,
+ BOTH
+ }
+
+ private static class RDepsToCheckAndRemove {
+ // reverseDepstoCheck may be null, but not toRemove, because we store a bare list if
+ // we have only toCheck.
+ @Nullable List<SkyKey> toCheck;
+ List<SkyKey> toRemove;
+
+ RDepsToCheckAndRemove(List<SkyKey> toCheck, List<SkyKey> toRemove) {
+ this.toCheck = toCheck;
+ this.toRemove = Preconditions.checkNotNull(toRemove);
+ }
+
+ static RDepsToCheckAndRemove justRemove(List<SkyKey> toRemove) {
+ return new RDepsToCheckAndRemove(null, toRemove);
+ }
+
+ static RDepsToCheckAndRemove replaceRemove(
+ RDepsToCheckAndRemove original, List<SkyKey> toRemove) {
+ return new RDepsToCheckAndRemove(original.toCheck, toRemove);
+ }
+
+ static RDepsToCheckAndRemove replaceCheck(
+ RDepsToCheckAndRemove original, List<SkyKey> toCheck) {
+ return new RDepsToCheckAndRemove(toCheck, original.toRemove);
+ }
+ }
+
+ private static DataState getDataState(Object reverseDepsToCheckAndRemove) {
+ if (reverseDepsToCheckAndRemove == null) {
+ return DataState.NULL;
+ } else if (reverseDepsToCheckAndRemove instanceof List) {
+ return DataState.CHECK_ONLY;
+ } else {
+ Preconditions.checkState(
+ reverseDepsToCheckAndRemove instanceof RDepsToCheckAndRemove,
+ reverseDepsToCheckAndRemove);
+ return DataState.BOTH;
+ }
+ }
+
+ private void setReverseDepsToRemove(T container, List<SkyKey> toRemove) {
+ Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+ switch (getDataState(reverseDepsToCheckAndRemove)) {
+ case NULL:
+ reverseDepsToCheckAndRemove = RDepsToCheckAndRemove.justRemove(toRemove);
+ break;
+ case CHECK_ONLY:
+ reverseDepsToCheckAndRemove =
+ new RDepsToCheckAndRemove(((List<SkyKey>) reverseDepsToCheckAndRemove), toRemove);
+ break;
+ case BOTH:
+ reverseDepsToCheckAndRemove =
+ RDepsToCheckAndRemove.replaceRemove(
+ (RDepsToCheckAndRemove) reverseDepsToCheckAndRemove, toRemove);
+ break;
+ default:
+ throw new IllegalStateException(container + ", " + toRemove);
+ }
+ setDataToConsolidate(container, reverseDepsToCheckAndRemove);
+ }
+
+ private void setReverseDepsToCheck(T container, List<SkyKey> toCheck) {
+ Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+ switch (getDataState(reverseDepsToCheckAndRemove)) {
+ case NULL:
+ case CHECK_ONLY:
+ reverseDepsToCheckAndRemove = toCheck;
+ break;
+ case BOTH:
+ reverseDepsToCheckAndRemove =
+ RDepsToCheckAndRemove.replaceCheck(
+ (RDepsToCheckAndRemove) reverseDepsToCheckAndRemove, toCheck);
+ break;
+ default:
+ throw new IllegalStateException(container + ", " + toCheck);
+ }
+ setDataToConsolidate(container, reverseDepsToCheckAndRemove);
+ }
+
+ @Nullable
+ private List<SkyKey> getReverseDepsToRemove(T container) {
+ Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+ switch (getDataState(reverseDepsToCheckAndRemove)) {
+ case NULL:
+ case CHECK_ONLY:
+ return null;
+ case BOTH:
+ return ((RDepsToCheckAndRemove) reverseDepsToCheckAndRemove).toRemove;
+ default:
+ throw new IllegalStateException(reverseDepsToCheckAndRemove.toString());
+ }
+ }
+
+ @Nullable
+ private List<SkyKey> getReverseDepsToCheck(T container) {
+ Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+ switch (getDataState(reverseDepsToCheckAndRemove)) {
+ case NULL:
+ return null;
+ case CHECK_ONLY:
+ return (List<SkyKey>) reverseDepsToCheckAndRemove;
+ case BOTH:
+ return ((RDepsToCheckAndRemove) reverseDepsToCheckAndRemove).toCheck;
+ default:
+ throw new IllegalStateException(reverseDepsToCheckAndRemove.toString());
+ }
+ }
/**
* We check that the reverse dependency is not already present. We only do that if reverseDeps is
@@ -60,15 +177,22 @@
*/
void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep) {
if (isSingleReverseDep(container)) {
- Preconditions.checkState(!getReverseDepsObject(container).equals(reverseDep),
- "Reverse dep %s already present", reverseDep);
+ 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", reverseDep, asList);
+ Preconditions.checkState(
+ !asList.contains(reverseDep),
+ "Reverse dep %s already present in %s for %s",
+ reverseDep,
+ asList,
+ container);
}
}
@@ -106,9 +230,29 @@
}
}
- boolean reverseDepsIsEmpty(T container) {
- return !isSingleReverseDep(container)
- && ((List<SkyKey>) getReverseDepsObject(container)).isEmpty();
+ void checkReverseDep(T container, SkyKey reverseDep) {
+ Object reverseDepsObject = getReverseDepsObject(container);
+ if (isSingleReverseDep(container)) {
+ Preconditions.checkState(
+ reverseDepsObject.equals(reverseDep),
+ "%s %s %s",
+ reverseDep,
+ reverseDepsObject,
+ container);
+ return;
+ }
+ List<SkyKey> asList = (List<SkyKey>) reverseDepsObject;
+ if (asList.size() < MAYBE_CHECK_THRESHOLD) {
+ Preconditions.checkState(
+ asList.contains(reverseDep), "%s not in %s for %s", reverseDep, asList, container);
+ } else {
+ List<SkyKey> reverseDepsToCheck = getReverseDepsToCheck(container);
+ if (reverseDepsToCheck == null) {
+ reverseDepsToCheck = new ArrayList<>();
+ setReverseDepsToCheck(container, reverseDepsToCheck);
+ }
+ reverseDepsToCheck.add(reverseDep);
+ }
}
/**
@@ -122,7 +266,7 @@
"toRemove: %s container: %s",
reverseDep,
container);
- overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
+ overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
return;
}
@SuppressWarnings("unchecked")
@@ -138,7 +282,7 @@
}
ImmutableSet<SkyKey> getReverseDeps(T container) {
- consolidateReverseDepsRemovals(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,
@@ -155,19 +299,38 @@
}
}
- void consolidateReverseDepsRemovals(T container) {
- List<SkyKey> reverseDepsToRemove = getReverseDepsToRemove(container);
+ void consolidateData(T container) {
Object reverseDeps = getReverseDepsObject(container);
- if (reverseDepsToRemove == null) {
+ List<SkyKey> reverseDepsToRemove = getReverseDepsToRemove(container);
+ List<SkyKey> reverseDepsToCheck = getReverseDepsToCheck(container);
+ if (reverseDepsToRemove == null && reverseDepsToCheck == null) {
return;
}
- Preconditions.checkState(!isSingleReverseDep(container),
- "We do not use reverseDepsToRemove for single lists: %s", container);
- // Should not happen, as we only create reverseDepsToRemove in case we have at least one
- // reverse dep to remove.
- Preconditions.checkState((!((List<?>) reverseDeps).isEmpty()),
- "Could not remove %s elements from %s.\nReverse deps to remove: %s. %s",
- reverseDepsToRemove.size(), reverseDeps, reverseDepsToRemove, container);
+ Preconditions.checkState(
+ !isSingleReverseDep(container),
+ "We do not delay removals/checks for single lists: %s %s %s",
+ container,
+ reverseDepsToRemove,
+ reverseDepsToCheck);
+ @SuppressWarnings("unchecked")
+ List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
+ // Should not happen, as we only create reverseDepsToRemove/Check in case we have at least one
+ // reverse dep to remove/check.
+ Preconditions.checkState(
+ !reverseDepsAsList.isEmpty(),
+ "Could not do delayed removal/check for %s elements from %s.\n"
+ + "Reverse deps to check: %s. Container: %s",
+ reverseDepsToRemove,
+ reverseDeps,
+ reverseDepsToCheck,
+ container);
+ if (reverseDepsToRemove == null) {
+ Set<SkyKey> reverseDepsAsSet = new HashSet<>(reverseDepsAsList);
+ Preconditions.checkState(
+ reverseDepsAsSet.containsAll(reverseDepsToCheck), "%s %s", reverseDepsToCheck, container);
+ setDataToConsolidate(container, null);
+ return;
+ }
Set<SkyKey> toRemove = Sets.newHashSet(reverseDepsToRemove);
int expectedRemovals = toRemove.size();
@@ -175,12 +338,13 @@
"A reverse dependency tried to remove itself twice: %s. %s", reverseDepsToRemove,
container);
- @SuppressWarnings("unchecked")
- List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
+ Set<SkyKey> toCheck =
+ reverseDepsToCheck == null ? new HashSet<SkyKey>() : new HashSet<>(reverseDepsToCheck);
List<SkyKey> newReverseDeps = Lists
.newArrayListWithExpectedSize(Math.max(0, reverseDepsAsList.size() - expectedRemovals));
for (SkyKey reverseDep : reverseDepsAsList) {
+ toCheck.remove(reverseDep);
if (!toRemove.contains(reverseDep)) {
newReverseDeps.add(reverseDep);
}
@@ -188,6 +352,7 @@
Preconditions.checkState(newReverseDeps.size() == reverseDepsAsList.size() - expectedRemovals,
"Could not remove some elements from %s.\nReverse deps to remove: %s. %s", reverseDeps,
toRemove, container);
+ Preconditions.checkState(toCheck.isEmpty(), "%s %s", toCheck, container);
if (newReverseDeps.isEmpty()) {
overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
@@ -196,14 +361,14 @@
} else {
overwriteReverseDepsList(container, newReverseDeps);
}
- setReverseDepsToRemove(container, null);
+ setDataToConsolidate(container, null);
}
String toString(T container) {
return MoreObjects.toStringHelper("ReverseDeps")
.add("reverseDeps", getReverseDepsObject(container))
.add("singleReverseDep", isSingleReverseDep(container))
- .add("reverseDepsToRemove", getReverseDepsToRemove(container))
+ .add("dataToConsolidate", getDataToConsolidate(container))
.toString();
}