Fix theoretical bug pointed out by jhorvitz@, that GroupedList assumes its elements are either raw or Lists, but #appendGroup(Collection) might add a Set or other Collection, which we wouldn't handle correctly.
The original motivation was to stress that the deps in a group were unordered with respect to each other, but that's not a good enough reason.
PiperOrigin-RevId: 233121648
diff --git a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
index 0054a3f..614bea8 100644
--- a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
+++ b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
@@ -22,7 +22,6 @@
import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadHostile;
import java.util.ArrayList;
-import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
@@ -36,10 +35,10 @@
* <p>Despite the "list" name, it is an error for the same element to appear multiple times in the
* list. Users are responsible for not trying to add the same element to a GroupedList twice.
*
- * <p>Groups are implemented as lists to minimize memory use. However, {@link #equals} is defined
- * to treat groups as unordered.
+ * <p>Groups are implemented as lists to minimize memory use. However, {@link #equals} is defined to
+ * treat groups as unordered.
*/
-public class GroupedList<T> implements Iterable<Collection<T>> {
+public class GroupedList<T> implements Iterable<List<T>> {
// Total number of items in the list. At least elements.size(), but might be larger if there are
// any nested lists.
private int size = 0;
@@ -110,11 +109,9 @@
// Use with caution as there are no checks in place for the integrity of the resulting object
// (no de-duping).
- public void appendGroup(Collection<? extends T> group) {
+ public void appendGroup(List<? extends T> group) {
// Do a check to make sure we don't have lists here. Note that if group is empty,
// Iterables.getFirst will return null, and null is not instanceof List.
- Preconditions.checkState(!(Iterables.getFirst(group, null) instanceof List),
- "Cannot make grouped list of lists: %s", group);
switch (group.size()) {
case 0:
return;
@@ -125,6 +122,8 @@
elements.add(group);
break;
}
+ Preconditions.checkState(
+ !(group.get(0) instanceof List), "Cannot make grouped list of lists: %s", group);
size += group.size();
}
@@ -393,7 +392,7 @@
* iterator is needed here because, to optimize memory, we store single-element lists as elements
* internally, and so they must be wrapped before they're returned.
*/
- private class GroupedIterator implements Iterator<Collection<T>> {
+ private class GroupedIterator implements Iterator<List<T>> {
private final Iterator<Object> iter = elements.iterator();
@Override
@@ -403,7 +402,7 @@
@SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
@Override
- public Collection<T> next() {
+ public List<T> next() {
Object obj = iter.next();
if (obj instanceof List) {
return (List<T>) obj;
@@ -413,7 +412,7 @@
}
@Override
- public Iterator<Collection<T>> iterator() {
+ public Iterator<List<T>> iterator() {
return new GroupedIterator();
}
@@ -474,7 +473,7 @@
* goes in a group of its own.
*/
public void add(E elt) {
- elements.add(Preconditions.checkNotNull(elt, "%s %s", elt, this));
+ elements.add(Preconditions.checkNotNull(elt, "Null add of elt: %s", this));
if (currentGroup == null) {
groupedList.add(elt);
} else {
@@ -502,16 +501,6 @@
currentGroup = new ArrayList<>();
}
- /**
- * Starts a group with an initial capacity. All elements added until {@link #endGroup} will be
- * in the same group. Each call of startGroup must be paired with a following {@link #endGroup}
- * call. Any duplicate elements added to this group will be silently deduplicated.
- */
- public void startGroup(int expectedGroupSize) {
- Preconditions.checkState(currentGroup == null, this);
- currentGroup = new ArrayList<>(expectedGroupSize);
- }
-
/** Ends a group started with {@link #startGroup}. */
public void endGroup() {
Preconditions.checkNotNull(currentGroup);
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
index 85aa3e8..84e5ff7 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -44,6 +44,7 @@
import java.time.Duration;
import java.util.Collection;
import java.util.Iterator;
+import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ExecutorService;
@@ -219,7 +220,7 @@
// its reverse dep on this node removed. Failing to do either one of these would result in
// a graph inconsistency, where the child had a reverse dep on this node, but this node
// had no kind of dependency on the child.
- Collection<SkyKey> directDepsToCheck = state.getNextDirtyDirectDeps();
+ List<SkyKey> directDepsToCheck = state.getNextDirtyDirectDeps();
if (invalidatedByErrorTransience(directDepsToCheck, state)) {
// If this dep is the ErrorTransienceValue and the ErrorTransienceValue has been
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 c9d202e..823c127 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -16,7 +16,7 @@
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
import java.math.BigInteger;
-import java.util.Collection;
+import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;
@@ -99,7 +99,7 @@
}
@Override
- public Collection<SkyKey> getNextDirtyDirectDeps() throws InterruptedException {
+ public List<SkyKey> getNextDirtyDirectDeps() throws InterruptedException {
return getDelegate().getNextDirtyDirectDeps();
}
@@ -213,7 +213,7 @@
}
@Override
- public void addTemporaryDirectDepsGroupToDirtyEntry(Collection<SkyKey> group) {
+ public void addTemporaryDirectDepsGroupToDirtyEntry(List<SkyKey> group) {
getDelegate().addTemporaryDirectDepsGroupToDirtyEntry(group);
}
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
index 7d16bb2..b110ab0 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -19,7 +19,7 @@
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.skyframe.NodeEntry.DirtyState;
import com.google.devtools.build.skyframe.ThinNodeEntry.DirtyType;
-import java.util.Collection;
+import java.util.List;
import java.util.Set;
/**
@@ -194,7 +194,7 @@
*
* <p>See {@link NodeEntry#getNextDirtyDirectDeps}.
*/
- final Collection<SkyKey> getNextDirtyDirectDeps() throws InterruptedException {
+ final List<SkyKey> getNextDirtyDirectDeps() throws InterruptedException {
Preconditions.checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this);
Preconditions.checkState(dirtyDirectDepIndex < getNumOfGroupsInLastBuildDirectDeps(), this);
return getLastBuildDirectDeps().get(dirtyDirectDepIndex++);
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 e350a3d..f72d069 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -23,7 +23,6 @@
import com.google.devtools.build.skyframe.KeyToConsolidate.OpToStoreBare;
import java.math.BigInteger;
import java.util.ArrayList;
-import java.util.Collection;
import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;
@@ -589,7 +588,7 @@
/** @see DirtyBuildingState#getNextDirtyDirectDeps() */
@Override
- public synchronized Collection<SkyKey> getNextDirtyDirectDeps() throws InterruptedException {
+ public synchronized List<SkyKey> getNextDirtyDirectDeps() throws InterruptedException {
Preconditions.checkState(isReady(), this);
Preconditions.checkState(isEvaluating(), "Not evaluating during getNextDirty? %s", this);
return getDirtyBuildingState().getNextDirtyDirectDeps();
@@ -708,7 +707,7 @@
}
@Override
- public synchronized void addTemporaryDirectDepsGroupToDirtyEntry(Collection<SkyKey> group) {
+ public synchronized void addTemporaryDirectDepsGroupToDirtyEntry(List<SkyKey> group) {
Preconditions.checkState(!isDone(), "add group temp shouldn't be done: %s %s", group, this);
getTemporaryDirectDeps().appendGroup(group);
}
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 78fb6ca..61bbc24 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -18,6 +18,7 @@
import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
import java.math.BigInteger;
import java.util.Collection;
+import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;
@@ -299,7 +300,7 @@
* @see DirtyBuildingState#getNextDirtyDirectDeps()
*/
@ThreadSafe
- Collection<SkyKey> getNextDirtyDirectDeps() throws InterruptedException;
+ List<SkyKey> getNextDirtyDirectDeps() throws InterruptedException;
/**
* Returns all deps of a node that has not yet finished evaluating. In other words, if a node has
@@ -425,7 +426,7 @@
* checking.
*/
@ThreadSafe
- void addTemporaryDirectDepsGroupToDirtyEntry(Collection<SkyKey> group);
+ void addTemporaryDirectDepsGroupToDirtyEntry(List<SkyKey> group);
/**
* Returns true if the node is ready to be evaluated, i.e., it has been signaled exactly as many
