Compare GroupedLists without regard to the order within a given group. Also make sure that we don't store duplicate elements within a given group (although that is currently taken care of by the callers).

--
MOS_MIGRATED_REVID=108155105

3 files changed, 72 insertions, 42 deletions

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 5a029a69ce..e317adc837 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
@@ -125,8 +125,8 @@ public class GroupedListTest {
     assertFalse(groupedList.isEmpty());
     Object compressed = groupedList.compress();
     assertElementsEqual(compressed, allElts);
-    assertThat(GroupedList.create(compressed)).containsExactlyElementsIn(elements).inOrder();
-    assertThat(groupedList).containsExactlyElementsIn(elements).inOrder();
+    assertElementsEqualInGroups(GroupedList.create(compressed), elements);
+    assertElementsEqualInGroups(groupedList, elements);
   }
 
   @Test
@@ -157,8 +157,8 @@ public class GroupedListTest {
     assertElementsEqual(compressed, allElts);
     // Get rid of empty list -- it was not stored in groupedList.
     elements.remove(1);
-    assertThat(GroupedList.create(compressed)).containsExactlyElementsIn(elements).inOrder();
-    assertThat(groupedList).containsExactlyElementsIn(elements).inOrder();
+    assertElementsEqualInGroups(GroupedList.create(compressed), elements);
+    assertElementsEqualInGroups(groupedList, elements);
   }
 
   @Test
@@ -194,8 +194,8 @@ public class GroupedListTest {
     elements.remove(ImmutableList.of("3"));
     elements.remove(ImmutableList.of());
     elements.remove(ImmutableList.of("removedGroup1", "removedGroup2"));
-    assertThat(GroupedList.create(compressed)).containsExactlyElementsIn(elements).inOrder();
-    assertThat(groupedList).containsExactlyElementsIn(elements).inOrder();
+    assertElementsEqualInGroups(GroupedList.create(compressed), elements);
+    assertElementsEqualInGroups(groupedList, elements);
   }
 
   @Test
@@ -220,8 +220,8 @@ public class GroupedListTest {
     allElts.removeAll(removed);
     assertElementsEqual(compressed, allElts);
     elements.get(0).removeAll(removed);
-    assertThat(GroupedList.create(compressed)).containsExactlyElementsIn(elements).inOrder();
-    assertThat(groupedList).containsExactlyElementsIn(elements).inOrder();
+    assertElementsEqualInGroups(GroupedList.create(compressed), elements);
+    assertElementsEqualInGroups(groupedList, elements);
   }
 
   private static Object createAndCompress(Collection<String> list) {
@@ -238,9 +238,17 @@ public class GroupedListTest {
     return Iterables.elementsEqual(GroupedList.<String>create(compressed).toSet(), expected);
   }
 
+  private static void assertElementsEqualInGroups(
+      GroupedList<String> groupedList, List<? extends List<String>> elements) {
+    int i = 0;
+    for (Iterable<String> group : groupedList) {
+      assertThat(group).containsExactlyElementsIn(elements.get(i));
+      i++;
+    }
+    assertThat(elements).hasSize(i);
+  }
+
   private static void assertElementsEqual(Object compressed, Iterable<String> expected) {
-    assertThat(GroupedList.<String>create(compressed).toSet())
-        .containsExactlyElementsIn(expected)
-        .inOrder();
+    assertThat(GroupedList.<String>create(compressed).toSet()).containsExactlyElementsIn(expected);
   }
 }
diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
index c55abf23e1..f427b2c0e2 100644
--- a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
@@ -14,14 +14,9 @@
 package com.google.devtools.build.skyframe;
 
 import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
-import com.google.devtools.build.lib.util.GroupedList;
-import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
 
 import java.util.Collection;
-import java.util.Collections;
 import java.util.Comparator;
-import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.TreeMap;
@@ -82,20 +77,10 @@ public class DeterministicInMemoryGraph extends NotifyingInMemoryGraph {
     }
 
     @Override
-    public synchronized void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
-      GroupedList<SkyKey> groupedList = new GroupedList<>();
-      groupedList.append(helper);
-      GroupedListHelper<SkyKey> orderedHelper = new GroupedListHelper<>();
-      for (Iterable<SkyKey> group : groupedList) {
-        orderedHelper.startGroup();
-        List<SkyKey> orderedGroup = Lists.newArrayList(group);
-        Collections.sort(orderedGroup, ALPHABETICAL_SKYKEY_COMPARATOR);
-        for (SkyKey dep : orderedGroup) {
-          orderedHelper.add(dep);
-        }
-        orderedHelper.endGroup();
-      }
-      super.addTemporaryDirectDeps(orderedHelper);
+    public synchronized Set<SkyKey> getTemporaryDirectDeps() {
+      TreeSet<SkyKey> result = new TreeSet<>(ALPHABETICAL_SKYKEY_COMPARATOR);
+      result.addAll(super.getTemporaryDirectDeps());
+      return result;
     }
   }
 }
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 23843fd83f..8b7c0d2c8c 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -193,7 +193,7 @@ public class InMemoryNodeEntryTest {
     SkyKey parent = key("parent");
     entry.addReverseDepAndCheckIfDone(parent);
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
-    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep);
     addTemporaryDirectDep(entry, dep);
     entry.signalDep();
     assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
@@ -370,7 +370,7 @@ public class InMemoryNodeEntryTest {
     SkyKey parent = key("parent");
     entry.addReverseDepAndCheckIfDone(parent);
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
-    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep);
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(new IntVersion(0L));
     assertEquals(NodeEntry.DirtyState.VERIFIED_CLEAN, entry.getDirtyState());
@@ -409,7 +409,7 @@ public class InMemoryNodeEntryTest {
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
-    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep);
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(new IntVersion(1L));
     assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
@@ -420,7 +420,6 @@ public class InMemoryNodeEntryTest {
     assertEquals(new IntVersion(0L), entry.getVersion());
   }
 
-
   @Test
   public void noPruneWhenDetailsChange() {
     NodeEntry entry = new InMemoryNodeEntry();
@@ -439,7 +438,7 @@ public class InMemoryNodeEntryTest {
     SkyKey parent = key("parent");
     entry.addReverseDepAndCheckIfDone(parent);
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
-    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep);
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(new IntVersion(1L));
     assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
@@ -455,6 +454,44 @@ public class InMemoryNodeEntryTest {
   }
 
   @Test
+  public void pruneWhenDepGroupReordered() {
+    NodeEntry entry = new InMemoryNodeEntry();
+    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    SkyKey dep = key("dep");
+    SkyKey dep1InGroup = key("dep1InGroup");
+    SkyKey dep2InGroup = key("dep2InGroup");
+    addTemporaryDirectDep(entry, dep);
+    addTemporaryDirectDeps(entry, dep1InGroup, dep2InGroup);
+    entry.signalDep();
+    entry.signalDep();
+    entry.signalDep();
+    setValue(entry, new IntegerValue(5), /*errorInfo=*/ null, /*graphVersion=*/ 0L);
+    assertFalse(entry.isDirty());
+    assertTrue(entry.isDone());
+    entry.markDirty(/*isChanged=*/ false);
+    assertTrue(entry.isDirty());
+    assertFalse(entry.isChanged());
+    assertFalse(entry.isDone());
+    assertTrue(entry.isReady());
+    entry.addReverseDepAndCheckIfDone(null);
+    assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep);
+    addTemporaryDirectDep(entry, dep);
+    entry.signalDep(new IntVersion(1L));
+    assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
+    assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
+    assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps())
+        .containsExactly(dep1InGroup, dep2InGroup);
+    addTemporaryDirectDeps(entry, dep2InGroup, dep1InGroup);
+    assertFalse(entry.signalDep());
+    assertTrue(entry.signalDep());
+    setValue(entry, new IntegerValue(5), /*errorInfo=*/ null, /*graphVersion=*/ 1L);
+    assertTrue(entry.isDone());
+    assertEquals(
+        "Version does not change when dep group reordered", new IntVersion(0), entry.getVersion());
+  }
+
+  @Test
   public void pruneErrorValue() {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
@@ -469,7 +506,7 @@ public class InMemoryNodeEntryTest {
     entry.markDirty(/*isChanged=*/false);
     entry.addReverseDepAndCheckIfDone(null); // Restart evaluation.
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
-    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep);
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(new IntVersion(1L));
     assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
@@ -496,12 +533,12 @@ public class InMemoryNodeEntryTest {
     entry.markDirty(/*isChanged=*/false);
     entry.addReverseDepAndCheckIfDone(null); // Restart evaluation.
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
-    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep, dep2).inOrder();
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep, dep2);
     addTemporaryDirectDeps(entry, dep, dep2);
     entry.signalDep(new IntVersion(0L));
     entry.signalDep(new IntVersion(0L));
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
-    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep3).inOrder();
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep3);
   }
 
   @Test
@@ -527,11 +564,11 @@ public class InMemoryNodeEntryTest {
     entry.markDirty(/*isChanged=*/false);
     entry.addReverseDepAndCheckIfDone(null); // Restart evaluation.
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
-    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep);
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(new IntVersion(0L));
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
-    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep4).inOrder();
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep4);
   }
 
   @Test
@@ -545,7 +582,7 @@ public class InMemoryNodeEntryTest {
     entry.markDirty(/*isChanged=*/false);
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
-    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
+    assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep);
     addTemporaryDirectDep(entry, dep);
     assertTrue(entry.signalDep(new IntVersion(1L)));
     assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
@@ -574,7 +611,7 @@ public class InMemoryNodeEntryTest {
     entry.addReverseDepAndCheckIfDone(null); // Start new evaluation.
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
     for (int ii = 0; ii < 10; ii++) {
-      assertThat(entry.getNextDirtyDirectDeps()).containsExactly(deps.get(ii)).inOrder();
+      assertThat(entry.getNextDirtyDirectDeps()).containsExactly(deps.get(ii));
       addTemporaryDirectDep(entry, deps.get(ii));
       assertTrue(entry.signalDep(new IntVersion(0L)));
       if (ii < 9) {