diff options
Diffstat (limited to 'guava-tests/test/com/google/common/collect/ImmutableSetTest.java')
| -rw-r--r-- | guava-tests/test/com/google/common/collect/ImmutableSetTest.java | 483 |
1 files changed, 66 insertions, 417 deletions
diff --git a/guava-tests/test/com/google/common/collect/ImmutableSetTest.java b/guava-tests/test/com/google/common/collect/ImmutableSetTest.java index 6a38fcdb5..43a935221 100644 --- a/guava-tests/test/com/google/common/collect/ImmutableSetTest.java +++ b/guava-tests/test/com/google/common/collect/ImmutableSetTest.java @@ -20,35 +20,24 @@ import static com.google.common.truth.Truth.assertThat; import com.google.common.annotations.GwtCompatible; import com.google.common.annotations.GwtIncompatible; -import com.google.common.base.Equivalence; import com.google.common.collect.ImmutableSet.Builder; import com.google.common.collect.testing.ListTestSuiteBuilder; import com.google.common.collect.testing.SetTestSuiteBuilder; -import com.google.common.collect.testing.TestStringSetGenerator; import com.google.common.collect.testing.features.CollectionFeature; import com.google.common.collect.testing.features.CollectionSize; import com.google.common.collect.testing.google.SetGenerators.DegeneratedImmutableSetGenerator; import com.google.common.collect.testing.google.SetGenerators.ImmutableSetAsListGenerator; import com.google.common.collect.testing.google.SetGenerators.ImmutableSetCopyOfGenerator; -import com.google.common.collect.testing.google.SetGenerators.ImmutableSetSizedBuilderGenerator; -import com.google.common.collect.testing.google.SetGenerators.ImmutableSetTooBigBuilderGenerator; -import com.google.common.collect.testing.google.SetGenerators.ImmutableSetTooSmallBuilderGenerator; -import com.google.common.collect.testing.google.SetGenerators.ImmutableSetUnsizedBuilderGenerator; import com.google.common.collect.testing.google.SetGenerators.ImmutableSetWithBadHashesGenerator; -import com.google.common.testing.CollectorTester; import com.google.common.testing.EqualsTester; -import com.google.errorprone.annotations.CanIgnoreReturnValue; -import java.util.Arrays; + +import junit.framework.Test; +import junit.framework.TestSuite; + import java.util.Collection; import java.util.Collections; import java.util.Iterator; -import java.util.List; import java.util.Set; -import java.util.function.BiPredicate; -import java.util.stream.Collector; -import junit.framework.Test; -import junit.framework.TestSuite; -import org.checkerframework.checker.nullness.qual.Nullable; /** * Unit test for {@link ImmutableSet}. @@ -60,166 +49,88 @@ import org.checkerframework.checker.nullness.qual.Nullable; @GwtCompatible(emulated = true) public class ImmutableSetTest extends AbstractImmutableSetTest { - @GwtIncompatible // suite + @GwtIncompatible("suite") public static Test suite() { TestSuite suite = new TestSuite(); - suite.addTest( - SetTestSuiteBuilder.using(new ImmutableSetCopyOfGenerator()) - .named(ImmutableSetTest.class.getName()) - .withFeatures( - CollectionSize.ANY, - CollectionFeature.KNOWN_ORDER, - CollectionFeature.SERIALIZABLE, - CollectionFeature.ALLOWS_NULL_QUERIES) - .createTestSuite()); - - suite.addTest( - SetTestSuiteBuilder.using(new ImmutableSetUnsizedBuilderGenerator()) - .named(ImmutableSetTest.class.getName() + ", with unsized builder") - .withFeatures( - CollectionSize.ANY, - CollectionFeature.KNOWN_ORDER, - CollectionFeature.SERIALIZABLE, - CollectionFeature.ALLOWS_NULL_QUERIES) - .createTestSuite()); - - suite.addTest( - SetTestSuiteBuilder.using( - new TestStringSetGenerator() { - @Override - protected Set<String> create(String[] elements) { - ImmutableSet.Builder<String> builder = ImmutableSet.builder(); - builder.forceJdk(); - builder.add(elements); - return builder.build(); - } - }) - .named(ImmutableSetTest.class.getName() + ", with JDK builder") - .withFeatures( - CollectionSize.ANY, - CollectionFeature.KNOWN_ORDER, - CollectionFeature.SERIALIZABLE, - CollectionFeature.ALLOWS_NULL_QUERIES) - .createTestSuite()); - - suite.addTest( - SetTestSuiteBuilder.using(new ImmutableSetSizedBuilderGenerator()) - .named(ImmutableSetTest.class.getName() + ", with exactly sized builder") - .withFeatures( - CollectionSize.ANY, - CollectionFeature.KNOWN_ORDER, - CollectionFeature.SERIALIZABLE, - CollectionFeature.ALLOWS_NULL_QUERIES) - .createTestSuite()); - - suite.addTest( - SetTestSuiteBuilder.using(new ImmutableSetTooBigBuilderGenerator()) - .named(ImmutableSetTest.class.getName() + ", with oversized builder") - .withFeatures( - CollectionSize.ANY, - CollectionFeature.KNOWN_ORDER, - CollectionFeature.SERIALIZABLE, - CollectionFeature.ALLOWS_NULL_QUERIES) - .createTestSuite()); - - suite.addTest( - SetTestSuiteBuilder.using(new ImmutableSetTooSmallBuilderGenerator()) - .named(ImmutableSetTest.class.getName() + ", with undersized builder") - .withFeatures( - CollectionSize.ANY, - CollectionFeature.KNOWN_ORDER, - CollectionFeature.SERIALIZABLE, - CollectionFeature.ALLOWS_NULL_QUERIES) - .createTestSuite()); - - suite.addTest( - SetTestSuiteBuilder.using(new ImmutableSetWithBadHashesGenerator()) - .named(ImmutableSetTest.class.getName() + ", with bad hashes") - .withFeatures( - CollectionSize.ANY, - CollectionFeature.KNOWN_ORDER, - CollectionFeature.ALLOWS_NULL_QUERIES) - .createTestSuite()); - - suite.addTest( - SetTestSuiteBuilder.using(new DegeneratedImmutableSetGenerator()) - .named(ImmutableSetTest.class.getName() + ", degenerate") - .withFeatures( - CollectionSize.ONE, - CollectionFeature.KNOWN_ORDER, - CollectionFeature.ALLOWS_NULL_QUERIES) - .createTestSuite()); - - suite.addTest( - ListTestSuiteBuilder.using(new ImmutableSetAsListGenerator()) - .named("ImmutableSet.asList") - .withFeatures( - CollectionSize.ANY, - CollectionFeature.REJECTS_DUPLICATES_AT_CREATION, - CollectionFeature.SERIALIZABLE, - CollectionFeature.ALLOWS_NULL_QUERIES) - .createTestSuite()); + suite.addTest(SetTestSuiteBuilder.using(new ImmutableSetCopyOfGenerator()) + .named(ImmutableSetTest.class.getName()) + .withFeatures(CollectionSize.ANY, CollectionFeature.KNOWN_ORDER, + CollectionFeature.SERIALIZABLE, + CollectionFeature.ALLOWS_NULL_QUERIES) + .createTestSuite()); + + suite.addTest(SetTestSuiteBuilder.using( + new ImmutableSetWithBadHashesGenerator()) + .named(ImmutableSetTest.class.getName() + ", with bad hashes") + .withFeatures(CollectionSize.ANY, CollectionFeature.KNOWN_ORDER, + CollectionFeature.ALLOWS_NULL_QUERIES) + .createTestSuite()); + + suite.addTest(SetTestSuiteBuilder.using( + new DegeneratedImmutableSetGenerator()) + .named(ImmutableSetTest.class.getName() + ", degenerate") + .withFeatures(CollectionSize.ONE, CollectionFeature.KNOWN_ORDER, + CollectionFeature.ALLOWS_NULL_QUERIES) + .createTestSuite()); + + suite.addTest(ListTestSuiteBuilder.using(new ImmutableSetAsListGenerator()) + .named("ImmutableSet.asList") + .withFeatures(CollectionSize.ANY, + CollectionFeature.REJECTS_DUPLICATES_AT_CREATION, + CollectionFeature.SERIALIZABLE, + CollectionFeature.ALLOWS_NULL_QUERIES) + .createTestSuite()); suite.addTestSuite(ImmutableSetTest.class); return suite; } - @Override - protected <E extends Comparable<? super E>> Set<E> of() { + @Override protected Set<String> of() { return ImmutableSet.of(); } - @Override - protected <E extends Comparable<? super E>> Set<E> of(E e) { + @Override protected Set<String> of(String e) { return ImmutableSet.of(e); } - @Override - protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2) { + @Override protected Set<String> of(String e1, String e2) { return ImmutableSet.of(e1, e2); } - @Override - protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2, E e3) { + @Override protected Set<String> of(String e1, String e2, String e3) { return ImmutableSet.of(e1, e2, e3); } - @Override - protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2, E e3, E e4) { + @Override protected Set<String> of( + String e1, String e2, String e3, String e4) { return ImmutableSet.of(e1, e2, e3, e4); } - @Override - protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2, E e3, E e4, E e5) { + @Override protected Set<String> of( + String e1, String e2, String e3, String e4, String e5) { return ImmutableSet.of(e1, e2, e3, e4, e5); } - @SuppressWarnings("unchecked") - @Override - protected <E extends Comparable<? super E>> Set<E> of( - E e1, E e2, E e3, E e4, E e5, E e6, E... rest) { + @Override protected Set<String> of(String e1, String e2, String e3, + String e4, String e5, String e6, String... rest) { return ImmutableSet.of(e1, e2, e3, e4, e5, e6, rest); } - @Override - protected <E extends Comparable<? super E>> Set<E> copyOf(E[] elements) { + @Override protected Set<String> copyOf(String[] elements) { return ImmutableSet.copyOf(elements); } - @Override - protected <E extends Comparable<? super E>> Set<E> copyOf(Collection<? extends E> elements) { + @Override protected Set<String> copyOf(Collection<String> elements) { return ImmutableSet.copyOf(elements); } - @Override - protected <E extends Comparable<? super E>> Set<E> copyOf(Iterable<? extends E> elements) { + @Override protected Set<String> copyOf(Iterable<String> elements) { return ImmutableSet.copyOf(elements); } - @Override - protected <E extends Comparable<? super E>> Set<E> copyOf(Iterator<? extends E> elements) { + @Override protected Set<String> copyOf(Iterator<String> elements) { return ImmutableSet.copyOf(elements); } @@ -231,37 +142,37 @@ public class ImmutableSetTest extends AbstractImmutableSetTest { public void testCreation_oneDuplicate() { // now we'll get the varargs overload - ImmutableSet<String> set = - ImmutableSet.of("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "a"); - assertEquals( - Lists.newArrayList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m"), + ImmutableSet<String> set = ImmutableSet.of( + "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "a"); + assertEquals(Lists.newArrayList( + "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m"), Lists.newArrayList(set)); } public void testCreation_manyDuplicates() { // now we'll get the varargs overload - ImmutableSet<String> set = - ImmutableSet.of("a", "b", "c", "c", "c", "c", "b", "b", "a", "a", "c", "c", "c", "a"); - assertThat(set).containsExactly("a", "b", "c").inOrder(); + ImmutableSet<String> set = ImmutableSet.of( + "a", "b", "c", "c", "c", "c", "b", "b", "a", "a", "c", "c", "c", "a"); + assertThat(set).has().exactly("a", "b", "c").inOrder(); } public void testCreation_arrayOfArray() { - String[] array = new String[] {"a"}; + String[] array = new String[] { "a" }; Set<String[]> set = ImmutableSet.<String[]>of(array); assertEquals(Collections.singleton(array), set); } - @GwtIncompatible // ImmutableSet.chooseTableSize + @GwtIncompatible("ImmutableSet.chooseTableSize") public void testChooseTableSize() { assertEquals(8, ImmutableSet.chooseTableSize(3)); assertEquals(8, ImmutableSet.chooseTableSize(4)); assertEquals(1 << 29, ImmutableSet.chooseTableSize(1 << 28)); - assertEquals(1 << 29, ImmutableSet.chooseTableSize((1 << 29) * 3 / 5)); + assertEquals(1 << 29, ImmutableSet.chooseTableSize(1 << 29 - 1)); // Now we hit the cap assertEquals(1 << 30, ImmutableSet.chooseTableSize(1 << 29)); - assertEquals(1 << 30, ImmutableSet.chooseTableSize((1 << 30) - 1)); + assertEquals(1 << 30, ImmutableSet.chooseTableSize(1 << 30 - 1)); // Now we've gone too far try { @@ -271,9 +182,9 @@ public class ImmutableSetTest extends AbstractImmutableSetTest { } } - @GwtIncompatible // RegularImmutableSet.table not in emulation + @GwtIncompatible("RegularImmutableSet.table not in emulation") public void testResizeTable() { - verifyTableSize(100, 2, 8); + verifyTableSize(100, 2, 4); verifyTableSize(100, 5, 8); verifyTableSize(100, 33, 64); verifyTableSize(17, 17, 32); @@ -281,7 +192,7 @@ public class ImmutableSetTest extends AbstractImmutableSetTest { verifyTableSize(17, 15, 32); } - @GwtIncompatible // RegularImmutableSet.table not in emulation + @GwtIncompatible("RegularImmutableSet.table not in emulation") private void verifyTableSize(int inputSize, int setSize, int tableSize) { Builder<Integer> builder = ImmutableSet.builder(); for (int i = 0; i < inputSize; i++) { @@ -289,10 +200,8 @@ public class ImmutableSetTest extends AbstractImmutableSetTest { } ImmutableSet<Integer> set = builder.build(); assertTrue(set instanceof RegularImmutableSet); - assertEquals( - "Input size " + inputSize + " and set size " + setSize, - tableSize, - ((RegularImmutableSet<Integer>) set).table.length); + assertEquals("Input size " + inputSize + " and set size " + setSize, + tableSize, ((RegularImmutableSet<Integer>) set).table.length); } public void testCopyOf_copiesImmutableSortedSet() { @@ -301,73 +210,16 @@ public class ImmutableSetTest extends AbstractImmutableSetTest { assertNotSame(sortedSet, copy); } - public void testToImmutableSet() { - Collector<String, ?, ImmutableSet<String>> collector = ImmutableSet.toImmutableSet(); - Equivalence<ImmutableSet<String>> equivalence = - Equivalence.equals().onResultOf(ImmutableSet::asList); - CollectorTester.of(collector, equivalence) - .expectCollects(ImmutableSet.of("a", "b", "c", "d"), "a", "b", "a", "c", "b", "b", "d"); - } - - public void testToImmutableSet_duplicates() { - class TypeWithDuplicates { - final int a; - final int b; - - TypeWithDuplicates(int a, int b) { - this.a = a; - this.b = b; - } - - @Override - public int hashCode() { - return a; - } - - @Override - public boolean equals(Object obj) { - return obj instanceof TypeWithDuplicates && ((TypeWithDuplicates) obj).a == a; - } - - public boolean fullEquals(TypeWithDuplicates other) { - return other != null && a == other.a && b == other.b; - } - } - - Collector<TypeWithDuplicates, ?, ImmutableSet<TypeWithDuplicates>> collector = - ImmutableSet.toImmutableSet(); - BiPredicate<ImmutableSet<TypeWithDuplicates>, ImmutableSet<TypeWithDuplicates>> equivalence = - (set1, set2) -> { - if (!set1.equals(set2)) { - return false; - } - for (int i = 0; i < set1.size(); i++) { - if (!set1.asList().get(i).fullEquals(set2.asList().get(i))) { - return false; - } - } - return true; - }; - TypeWithDuplicates a = new TypeWithDuplicates(1, 1); - TypeWithDuplicates b1 = new TypeWithDuplicates(2, 1); - TypeWithDuplicates b2 = new TypeWithDuplicates(2, 2); - TypeWithDuplicates c = new TypeWithDuplicates(3, 1); - CollectorTester.of(collector, equivalence) - .expectCollects(ImmutableSet.of(a, b1, c), a, b1, c, b2); - } - - @GwtIncompatible // GWT is single threaded + @GwtIncompatible("GWT is single threaded") public void testCopyOf_threadSafe() { verifyThreadSafe(); } - @Override - <E extends Comparable<E>> Builder<E> builder() { + @Override <E extends Comparable<E>> Builder<E> builder() { return ImmutableSet.builder(); } - @Override - int getComplexBuilderSetLastElement() { + @Override int getComplexBuilderSetLastElement() { return LAST_COLOR_ADDED; } @@ -378,207 +230,4 @@ public class ImmutableSetTest extends AbstractImmutableSetTest { .addEqualityGroup(ImmutableSet.of(1, 2, 1), ImmutableSet.of(2, 1, 1)) .testEquals(); } - - /** - * A Comparable wrapper around a String which executes callbacks on calls to hashCode, equals, and - * compareTo. - */ - private static class CountsHashCodeAndEquals implements Comparable<CountsHashCodeAndEquals> { - private final String delegateString; - private final Runnable onHashCode; - private final Runnable onEquals; - private final Runnable onCompareTo; - - CountsHashCodeAndEquals( - String delegateString, Runnable onHashCode, Runnable onEquals, Runnable onCompareTo) { - this.delegateString = delegateString; - this.onHashCode = onHashCode; - this.onEquals = onEquals; - this.onCompareTo = onCompareTo; - } - - @Override - public int hashCode() { - onHashCode.run(); - return delegateString.hashCode(); - } - - @Override - public boolean equals(@Nullable Object other) { - onEquals.run(); - return other instanceof CountsHashCodeAndEquals - && delegateString.equals(((CountsHashCodeAndEquals) other).delegateString); - } - - @Override - public int compareTo(CountsHashCodeAndEquals o) { - onCompareTo.run(); - return delegateString.compareTo(o.delegateString); - } - } - - /** A holder of counters for calls to hashCode, equals, and compareTo. */ - private static final class CallsCounter { - long hashCode; - long equals; - long compareTo; - - long total() { - return hashCode + equals + compareTo; - } - - void zero() { - hashCode = 0; - equals = 0; - compareTo = 0; - } - } - - /** All the ways to construct an ImmutableSet. */ - enum ConstructionPathway { - OF { - @Override - ImmutableSet<?> create(List<?> list) { - Object o1 = list.get(0); - Object o2 = list.get(1); - Object o3 = list.get(2); - Object o4 = list.get(3); - Object o5 = list.get(4); - Object o6 = list.get(5); - Object[] rest = list.subList(6, list.size()).toArray(); - return ImmutableSet.of(o1, o2, o3, o4, o5, o6, rest); - } - }, - COPY_OF_ARRAY { - @Override - ImmutableSet<?> create(List<?> list) { - return ImmutableSet.copyOf(list.toArray()); - } - }, - COPY_OF_LIST { - @Override - ImmutableSet<?> create(List<?> list) { - return ImmutableSet.copyOf(list); - } - }, - BUILDER_ADD_ONE_BY_ONE { - @Override - ImmutableSet<?> create(List<?> list) { - ImmutableSet.Builder<Object> builder = ImmutableSet.builder(); - for (Object o : list) { - builder.add(o); - } - return builder.build(); - } - }, - BUILDER_ADD_ARRAY { - @Override - ImmutableSet<?> create(List<?> list) { - ImmutableSet.Builder<Object> builder = ImmutableSet.builder(); - builder.add(list.toArray()); - return builder.build(); - } - }, - BUILDER_ADD_LIST { - @Override - ImmutableSet<?> create(List<?> list) { - ImmutableSet.Builder<Object> builder = ImmutableSet.builder(); - builder.addAll(list); - return builder.build(); - } - }; - - @CanIgnoreReturnValue - abstract ImmutableSet<?> create(List<?> list); - } - - /** - * Returns a list of objects with the same hash code, of size 2^power, counting calls to equals, - * hashCode, and compareTo in counter. - */ - static List<CountsHashCodeAndEquals> createAdversarialInput(int power, CallsCounter counter) { - String str1 = "Aa"; - String str2 = "BB"; - assertEquals(str1.hashCode(), str2.hashCode()); - List<String> haveSameHashes2 = Arrays.asList(str1, str2); - List<CountsHashCodeAndEquals> result = - Lists.newArrayList( - Lists.transform( - Lists.cartesianProduct(Collections.nCopies(power, haveSameHashes2)), - strs -> - new CountsHashCodeAndEquals( - String.join("", strs), - () -> counter.hashCode++, - () -> counter.equals++, - () -> counter.compareTo++))); - assertEquals( - result.get(0).delegateString.hashCode(), - result.get(result.size() - 1).delegateString.hashCode()); - return result; - } - - @GwtIncompatible - public void testResistsHashFloodingInConstruction() { - CallsCounter smallCounter = new CallsCounter(); - List<CountsHashCodeAndEquals> haveSameHashesSmall = createAdversarialInput(10, smallCounter); - int smallSize = haveSameHashesSmall.size(); - - CallsCounter largeCounter = new CallsCounter(); - List<CountsHashCodeAndEquals> haveSameHashesLarge = createAdversarialInput(15, largeCounter); - int largeSize = haveSameHashesLarge.size(); - - for (ConstructionPathway pathway : ConstructionPathway.values()) { - smallCounter.zero(); - pathway.create(haveSameHashesSmall); - - largeCounter.zero(); - pathway.create(haveSameHashesLarge); - - double ratio = (double) largeCounter.total() / smallCounter.total(); - - assertThat(ratio) - .named( - "ratio of equals/hashCode/compareTo operations to build an ImmutableSet via pathway " - + "%s of size %s versus size %s", - pathway, haveSameHashesLarge.size(), haveSameHashesSmall.size()) - .isAtMost(2.0 * (largeSize * Math.log(largeSize)) / (smallSize * Math.log(smallSize))); - // We allow up to 2x wobble in the constant factors. - } - } - - @GwtIncompatible - public void testResistsHashFloodingOnContains() { - CallsCounter smallCounter = new CallsCounter(); - List<CountsHashCodeAndEquals> haveSameHashesSmall = createAdversarialInput(10, smallCounter); - ImmutableSet<?> smallSet = ConstructionPathway.COPY_OF_LIST.create(haveSameHashesSmall); - long worstCaseOpsSmall = worstCaseQueryOperations(smallSet, smallCounter); - - CallsCounter largeCounter = new CallsCounter(); - List<CountsHashCodeAndEquals> haveSameHashesLarge = createAdversarialInput(15, largeCounter); - ImmutableSet<?> largeSet = ConstructionPathway.COPY_OF_LIST.create(haveSameHashesLarge); - long worstCaseOpsLarge = worstCaseQueryOperations(largeSet, largeCounter); - - double ratio = (double) worstCaseOpsLarge / worstCaseOpsSmall; - int smallSize = haveSameHashesSmall.size(); - int largeSize = haveSameHashesLarge.size(); - - assertThat(ratio) - .named( - "ratio of equals/hashCode/compareTo operations to worst-case query an ImmutableSet " - + "of size %s versus size %s", - haveSameHashesLarge.size(), haveSameHashesSmall.size()) - .isAtMost(2 * Math.log(largeSize) / Math.log(smallSize)); - // We allow up to 2x wobble in the constant factors. - } - - private static long worstCaseQueryOperations(Set<?> set, CallsCounter counter) { - long worstCalls = 0; - for (Object k : set) { - counter.zero(); - if (set.contains(k)) { - worstCalls = Math.max(worstCalls, counter.total()); - } - } - return worstCalls; - } } |