From cfa74ac167a7f651e757224f3930e731560e293c Mon Sep 17 00:00:00 2001 From: Janak Ramakrishnan Date: Wed, 18 Nov 2015 18:10:45 +0000 Subject: 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 --- .../devtools/build/lib/util/GroupedListTest.java | 30 +++++++---- .../build/skyframe/DeterministicInMemoryGraph.java | 23 ++------ .../build/skyframe/InMemoryNodeEntryTest.java | 61 +++++++++++++++++----- 3 files changed, 72 insertions(+), 42 deletions(-) (limited to 'src/test/java') 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 list) { @@ -238,9 +238,17 @@ public class GroupedListTest { return Iterables.elementsEqual(GroupedList.create(compressed).toSet(), expected); } + private static void assertElementsEqualInGroups( + GroupedList groupedList, List> elements) { + int i = 0; + for (Iterable group : groupedList) { + assertThat(group).containsExactlyElementsIn(elements.get(i)); + i++; + } + assertThat(elements).hasSize(i); + } + private static void assertElementsEqual(Object compressed, Iterable expected) { - assertThat(GroupedList.create(compressed).toSet()) - .containsExactlyElementsIn(expected) - .inOrder(); + assertThat(GroupedList.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 helper) { - GroupedList groupedList = new GroupedList<>(); - groupedList.append(helper); - GroupedListHelper orderedHelper = new GroupedListHelper<>(); - for (Iterable group : groupedList) { - orderedHelper.startGroup(); - List 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 getTemporaryDirectDeps() { + TreeSet 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()); @@ -454,6 +453,44 @@ public class InMemoryNodeEntryTest { assertEquals("Version increments when setValue changes", new IntVersion(1), entry.getVersion()); } + @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(); @@ -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) { -- cgit v1.2.3