Don't expose grouped direct deps of done nodes. Callers are actually interested in the compressed form. PiperOrigin-RevId: 245827814
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 614bea8..ab2ece4 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
@@ -21,6 +21,9 @@ import com.google.common.collect.Lists; import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadHostile; +import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec; +import java.lang.annotation.ElementType; +import java.lang.annotation.Target; import java.util.ArrayList; import java.util.Iterator; import java.util.List; @@ -39,6 +42,20 @@ * treat groups as unordered. */ public class GroupedList<T> implements Iterable<List<T>> { + + /** + * Indicates that the annotated element is a compressed {@link GroupedList}, so that it can be + * safely passed to {@link #create} and friends. + */ + // TODO(jhorvitz): enforce this annotation via compile-time checks. + @Target({ + ElementType.PARAMETER, + ElementType.FIELD, + ElementType.LOCAL_VARIABLE, + ElementType.TYPE_USE + }) + public @interface Compressed {} + // 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; @@ -220,6 +237,33 @@ return 1; } + /** Returns the number of groups in a compressed {@code GroupedList}. */ + public static int numGroups(@Compressed Object compressed) { + if (compressed == EMPTY_LIST) { + return 0; + } + if (compressed.getClass().isArray()) { + return ((Object[]) compressed).length; + } + return 1; + } + + /** + * Expands a compressed {@code GroupedList} into an {@link Iterable}. Equivalent to {@link + * #getAllElementsAsIterable()} but potentially more efficient. + */ + @SuppressWarnings("unchecked") + public static <T> Iterable<T> compressedToIterable(@Compressed Object compressed) { + if (compressed == EMPTY_LIST) { + return ImmutableList.of(); + } + if (compressed.getClass().isArray()) { + return GroupedList.<T>create(compressed).getAllElementsAsIterable(); + } + Preconditions.checkState(!(compressed instanceof List), compressed); + return ImmutableList.of((T) compressed); + } + /** Returns true if this list contains no elements. */ public boolean isEmpty() { return elements.isEmpty(); @@ -242,9 +286,10 @@ return false; } - private static final Object EMPTY_LIST = new Object(); + @AutoCodec @AutoCodec.VisibleForSerialization @Compressed + static final Object EMPTY_LIST = new Object(); - public Object compress() { + public @Compressed Object compress() { switch (numElements()) { case 0: return EMPTY_LIST; @@ -272,7 +317,7 @@ return obj instanceof List ? ((List<?>) obj).size() : 1; } - public static <E> GroupedList<E> create(Object compressed) { + public static <E> GroupedList<E> create(@Compressed Object compressed) { if (compressed == EMPTY_LIST) { return new GroupedList<>(); } @@ -288,6 +333,21 @@ return new GroupedList<>(1, ImmutableList.of(compressed)); } + /** Creates an already compressed {@code GroupedList} for storage. */ + public static <E> @Compressed Object createCompressedWithTwoGroupes( + E singletonElementOfFirstGroup, List<? extends E> elementsOfSecondGroup) { + switch (elementsOfSecondGroup.size()) { + case 0: + return singletonElementOfFirstGroup; + case 1: + return new Object[] { + singletonElementOfFirstGroup, Iterables.getOnlyElement(elementsOfSecondGroup) + }; + default: + return new Object[] {singletonElementOfFirstGroup, elementsOfSecondGroup}; + } + } + @Override public int hashCode() { // Hashing requires getting an order-independent hash for each element of this.elements. That
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 1ead12f..94d6de2 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -211,17 +211,14 @@ @Override public synchronized Iterable<SkyKey> getDirectDeps() { - return getGroupedDirectDeps().getAllElementsAsIterable(); + return GroupedList.compressedToIterable(getCompressedDirectDepsForDoneEntry()); } - /** - * If {@code isDone()}, returns the ordered list of sets of grouped direct dependencies that were - * added in {@link #addTemporaryDirectDeps}. - */ - public synchronized GroupedList<SkyKey> getGroupedDirectDeps() { + /** Returns the compressed {@link GroupedList} of direct deps. Can only be called when done. */ + public synchronized @GroupedList.Compressed Object getCompressedDirectDepsForDoneEntry() { assertKeepDeps(); Preconditions.checkState(isDone(), "no deps until done. NodeEntry: %s", this); - return GroupedList.create(directDeps); + return Preconditions.checkNotNull(directDeps, "deps can't be null: %s", this); } public int getNumDirectDeps() {
diff --git a/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java b/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java index fd5938e..0a29e8b 100644 --- a/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java +++ b/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java
@@ -60,7 +60,7 @@ } Object compressedList = createAndCompress(list); assertThat(Iterables.elementsEqual(iterable(compressedList), list)).isTrue(); - assertElementsEqual(compressedList, list); + assertElementsEqual(compressedList, list, size == 0 ? 0 : 1); } @Test @@ -151,7 +151,7 @@ assertThat(groupedList.isEmpty()).isFalse(); Object compressed = groupedList.compress(); assertThat(GroupedList.numElements(compressed)).isEqualTo(groupedList.numElements()); - assertElementsEqual(compressed, allElts); + assertElementsEqual(compressed, allElts, elements.size()); assertElementsEqualInGroups(GroupedList.<String>create(compressed), elements); assertElementsEqualInGroups(groupedList, elements); assertThat(groupedList.getAllElementsAsIterable()) @@ -184,7 +184,7 @@ assertThat(groupedList.numElements()).isEqualTo(allElts.size()); assertThat(groupedList.isEmpty()).isFalse(); Object compressed = groupedList.compress(); - assertElementsEqual(compressed, allElts); + assertElementsEqual(compressed, allElts, 3); // Get rid of empty list -- it was not stored in groupedList. elements.remove(1); assertElementsEqualInGroups(GroupedList.<String>create(compressed), elements); @@ -211,6 +211,18 @@ } @Test + public void createCompressed() { + GroupedList<String> groupedList = new GroupedList<>(); + groupedList.appendGroup(ImmutableList.of("a")); + groupedList.appendGroup(ImmutableList.of("b", "c")); + assertThat(GroupedList.createCompressedWithTwoGroupes("a", ImmutableList.of("b", "c"))) + .isEqualTo(groupedList.compress()); + groupedList.remove(ImmutableSet.of("b")); + assertThat(GroupedList.createCompressedWithTwoGroupes("a", ImmutableList.of("c"))) + .isEqualTo(groupedList.compress()); + } + + @Test public void removeMakesEmpty() { GroupedList<String> groupedList = new GroupedList<>(); assertThat(groupedList.isEmpty()).isTrue(); @@ -239,7 +251,7 @@ Object compressed = groupedList.compress(); assertThat(GroupedList.numElements(compressed)).isEqualTo(groupedList.numElements()); allElts.removeAll(removed); - assertElementsEqual(compressed, allElts); + assertElementsEqual(compressed, allElts, 3); elements.get(2).remove("2a"); elements.remove(ImmutableList.of("3")); elements.remove(ImmutableList.of()); @@ -269,7 +281,7 @@ Object compressed = groupedList.compress(); assertThat(GroupedList.numElements(compressed)).isEqualTo(groupedList.numElements()); allElts.removeAll(removed); - assertElementsEqual(compressed, allElts); + assertElementsEqual(compressed, allElts, 1); elements.get(0).removeAll(removed); assertElementsEqualInGroups(GroupedList.<String>create(compressed), elements); assertElementsEqualInGroups(groupedList, elements); @@ -299,6 +311,7 @@ result.append(helper); Object compressed = result.compress(); assertThat(GroupedList.numElements(compressed)).isEqualTo(result.numElements()); + assertThat(GroupedList.numGroups(compressed)).isEqualTo(list.isEmpty() ? 0 : 1); return compressed; } @@ -321,7 +334,9 @@ assertThat(elements).hasSize(i); } - private static void assertElementsEqual(Object compressed, Iterable<String> expected) { + private static void assertElementsEqual( + @GroupedList.Compressed Object compressed, Iterable<String> expected, int numGroups) { assertThat(GroupedList.<String>create(compressed).toSet()).containsExactlyElementsIn(expected); + assertThat(GroupedList.numGroups(compressed)).isEqualTo(numGroups); } }
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 a648dba..137d8d3 100644 --- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java +++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -843,7 +843,7 @@ } @Test - public void getGroupedDirectDeps() throws InterruptedException { + public void getCompressedDirectDepsForDoneEntry() throws InterruptedException { InMemoryNodeEntry entry = new InMemoryNodeEntry(); ImmutableList<ImmutableSet<SkyKey>> groupedDirectDeps = ImmutableList.of( ImmutableSet.of(key("1A")), @@ -869,7 +869,8 @@ } entry.setValue(new IntegerValue(42), IntVersion.of(42L), null); int i = 0; - GroupedList<SkyKey> entryGroupedDirectDeps = entry.getGroupedDirectDeps(); + GroupedList<SkyKey> entryGroupedDirectDeps = + GroupedList.create(entry.getCompressedDirectDepsForDoneEntry()); assertThat(Iterables.size(entryGroupedDirectDeps)).isEqualTo(groupedDirectDeps.size()); for (Iterable<SkyKey> depGroup : entryGroupedDirectDeps) { assertThat(depGroup).containsExactlyElementsIn(groupedDirectDeps.get(i++));