1 /* 2 * Copyright (C) 2007 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import static com.google.common.truth.Truth.assertThat; 20 import static org.junit.Assert.assertThrows; 21 22 import com.google.common.annotations.GwtCompatible; 23 import com.google.common.annotations.GwtIncompatible; 24 import com.google.common.base.Equivalence; 25 import com.google.common.collect.ImmutableSet.Builder; 26 import com.google.common.collect.testing.ListTestSuiteBuilder; 27 import com.google.common.collect.testing.SetTestSuiteBuilder; 28 import com.google.common.collect.testing.TestStringSetGenerator; 29 import com.google.common.collect.testing.features.CollectionFeature; 30 import com.google.common.collect.testing.features.CollectionSize; 31 import com.google.common.collect.testing.google.SetGenerators.DegeneratedImmutableSetGenerator; 32 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetAsListGenerator; 33 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetCopyOfGenerator; 34 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetSizedBuilderGenerator; 35 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetTooBigBuilderGenerator; 36 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetTooSmallBuilderGenerator; 37 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetUnsizedBuilderGenerator; 38 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetWithBadHashesGenerator; 39 import com.google.common.testing.CollectorTester; 40 import com.google.common.testing.EqualsTester; 41 import java.util.Collection; 42 import java.util.Collections; 43 import java.util.Iterator; 44 import java.util.Set; 45 import java.util.function.BiPredicate; 46 import java.util.stream.Collector; 47 import junit.framework.Test; 48 import junit.framework.TestSuite; 49 import org.checkerframework.checker.nullness.qual.Nullable; 50 51 /** 52 * Unit test for {@link ImmutableSet}. 53 * 54 * @author Kevin Bourrillion 55 * @author Jared Levy 56 * @author Nick Kralevich 57 */ 58 @GwtCompatible(emulated = true) 59 public class ImmutableSetTest extends AbstractImmutableSetTest { 60 61 @GwtIncompatible // suite suite()62 public static Test suite() { 63 TestSuite suite = new TestSuite(); 64 65 suite.addTest( 66 SetTestSuiteBuilder.using(new ImmutableSetCopyOfGenerator()) 67 .named(ImmutableSetTest.class.getName()) 68 .withFeatures( 69 CollectionSize.ANY, 70 CollectionFeature.KNOWN_ORDER, 71 CollectionFeature.SERIALIZABLE, 72 CollectionFeature.ALLOWS_NULL_QUERIES) 73 .createTestSuite()); 74 75 suite.addTest( 76 SetTestSuiteBuilder.using(new ImmutableSetUnsizedBuilderGenerator()) 77 .named(ImmutableSetTest.class.getName() + ", with unsized builder") 78 .withFeatures( 79 CollectionSize.ANY, 80 CollectionFeature.KNOWN_ORDER, 81 CollectionFeature.SERIALIZABLE, 82 CollectionFeature.ALLOWS_NULL_QUERIES) 83 .createTestSuite()); 84 85 suite.addTest( 86 SetTestSuiteBuilder.using( 87 new TestStringSetGenerator() { 88 @Override 89 protected Set<String> create(String[] elements) { 90 ImmutableSet.Builder<String> builder = ImmutableSet.builder(); 91 builder.forceJdk(); 92 builder.add(elements); 93 return builder.build(); 94 } 95 }) 96 .named(ImmutableSetTest.class.getName() + ", with JDK builder") 97 .withFeatures( 98 CollectionSize.ANY, 99 CollectionFeature.KNOWN_ORDER, 100 CollectionFeature.SERIALIZABLE, 101 CollectionFeature.ALLOWS_NULL_QUERIES) 102 .createTestSuite()); 103 104 suite.addTest( 105 SetTestSuiteBuilder.using(new ImmutableSetSizedBuilderGenerator()) 106 .named(ImmutableSetTest.class.getName() + ", with exactly sized builder") 107 .withFeatures( 108 CollectionSize.ANY, 109 CollectionFeature.KNOWN_ORDER, 110 CollectionFeature.SERIALIZABLE, 111 CollectionFeature.ALLOWS_NULL_QUERIES) 112 .createTestSuite()); 113 114 suite.addTest( 115 SetTestSuiteBuilder.using(new ImmutableSetTooBigBuilderGenerator()) 116 .named(ImmutableSetTest.class.getName() + ", with oversized builder") 117 .withFeatures( 118 CollectionSize.ANY, 119 CollectionFeature.KNOWN_ORDER, 120 CollectionFeature.SERIALIZABLE, 121 CollectionFeature.ALLOWS_NULL_QUERIES) 122 .createTestSuite()); 123 124 suite.addTest( 125 SetTestSuiteBuilder.using(new ImmutableSetTooSmallBuilderGenerator()) 126 .named(ImmutableSetTest.class.getName() + ", with undersized builder") 127 .withFeatures( 128 CollectionSize.ANY, 129 CollectionFeature.KNOWN_ORDER, 130 CollectionFeature.SERIALIZABLE, 131 CollectionFeature.ALLOWS_NULL_QUERIES) 132 .createTestSuite()); 133 134 suite.addTest( 135 SetTestSuiteBuilder.using(new ImmutableSetWithBadHashesGenerator()) 136 .named(ImmutableSetTest.class.getName() + ", with bad hashes") 137 .withFeatures( 138 CollectionSize.ANY, 139 CollectionFeature.KNOWN_ORDER, 140 CollectionFeature.ALLOWS_NULL_QUERIES) 141 .createTestSuite()); 142 143 suite.addTest( 144 SetTestSuiteBuilder.using(new DegeneratedImmutableSetGenerator()) 145 .named(ImmutableSetTest.class.getName() + ", degenerate") 146 .withFeatures( 147 CollectionSize.ONE, 148 CollectionFeature.KNOWN_ORDER, 149 CollectionFeature.ALLOWS_NULL_QUERIES) 150 .createTestSuite()); 151 152 suite.addTest( 153 ListTestSuiteBuilder.using(new ImmutableSetAsListGenerator()) 154 .named("ImmutableSet.asList") 155 .withFeatures( 156 CollectionSize.ANY, 157 CollectionFeature.REJECTS_DUPLICATES_AT_CREATION, 158 CollectionFeature.SERIALIZABLE, 159 CollectionFeature.ALLOWS_NULL_QUERIES) 160 .createTestSuite()); 161 162 suite.addTestSuite(ImmutableSetTest.class); 163 164 return suite; 165 } 166 167 @Override of()168 protected <E extends Comparable<? super E>> Set<E> of() { 169 return ImmutableSet.of(); 170 } 171 172 @Override of(E e)173 protected <E extends Comparable<? super E>> Set<E> of(E e) { 174 return ImmutableSet.of(e); 175 } 176 177 @Override of(E e1, E e2)178 protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2) { 179 return ImmutableSet.of(e1, e2); 180 } 181 182 @Override of(E e1, E e2, E e3)183 protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2, E e3) { 184 return ImmutableSet.of(e1, e2, e3); 185 } 186 187 @Override of(E e1, E e2, E e3, E e4)188 protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2, E e3, E e4) { 189 return ImmutableSet.of(e1, e2, e3, e4); 190 } 191 192 @Override of(E e1, E e2, E e3, E e4, E e5)193 protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2, E e3, E e4, E e5) { 194 return ImmutableSet.of(e1, e2, e3, e4, e5); 195 } 196 197 @SuppressWarnings("unchecked") 198 @Override of( E e1, E e2, E e3, E e4, E e5, E e6, E... rest)199 protected <E extends Comparable<? super E>> Set<E> of( 200 E e1, E e2, E e3, E e4, E e5, E e6, E... rest) { 201 return ImmutableSet.of(e1, e2, e3, e4, e5, e6, rest); 202 } 203 204 @Override copyOf(E[] elements)205 protected <E extends Comparable<? super E>> Set<E> copyOf(E[] elements) { 206 return ImmutableSet.copyOf(elements); 207 } 208 209 @Override copyOf(Collection<? extends E> elements)210 protected <E extends Comparable<? super E>> Set<E> copyOf(Collection<? extends E> elements) { 211 return ImmutableSet.copyOf(elements); 212 } 213 214 @Override copyOf(Iterable<? extends E> elements)215 protected <E extends Comparable<? super E>> Set<E> copyOf(Iterable<? extends E> elements) { 216 return ImmutableSet.copyOf(elements); 217 } 218 219 @Override copyOf(Iterator<? extends E> elements)220 protected <E extends Comparable<? super E>> Set<E> copyOf(Iterator<? extends E> elements) { 221 return ImmutableSet.copyOf(elements); 222 } 223 testCreation_allDuplicates()224 public void testCreation_allDuplicates() { 225 ImmutableSet<String> set = ImmutableSet.copyOf(Lists.newArrayList("a", "a")); 226 assertTrue(set instanceof SingletonImmutableSet); 227 assertEquals(Lists.newArrayList("a"), Lists.newArrayList(set)); 228 } 229 testCreation_oneDuplicate()230 public void testCreation_oneDuplicate() { 231 // now we'll get the varargs overload 232 ImmutableSet<String> set = 233 ImmutableSet.of("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "a"); 234 assertEquals( 235 Lists.newArrayList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m"), 236 Lists.newArrayList(set)); 237 } 238 testCreation_manyDuplicates()239 public void testCreation_manyDuplicates() { 240 // now we'll get the varargs overload 241 ImmutableSet<String> set = 242 ImmutableSet.of("a", "b", "c", "c", "c", "c", "b", "b", "a", "a", "c", "c", "c", "a"); 243 assertThat(set).containsExactly("a", "b", "c").inOrder(); 244 } 245 testCreation_arrayOfArray()246 public void testCreation_arrayOfArray() { 247 String[] array = new String[] {"a"}; 248 Set<String[]> set = ImmutableSet.<String[]>of(array); 249 assertEquals(Collections.singleton(array), set); 250 } 251 252 @GwtIncompatible // ImmutableSet.chooseTableSize testChooseTableSize()253 public void testChooseTableSize() { 254 assertEquals(8, ImmutableSet.chooseTableSize(3)); 255 assertEquals(8, ImmutableSet.chooseTableSize(4)); 256 257 assertEquals(1 << 29, ImmutableSet.chooseTableSize(1 << 28)); 258 assertEquals(1 << 29, ImmutableSet.chooseTableSize((1 << 29) * 3 / 5)); 259 260 // Now we hit the cap 261 assertEquals(1 << 30, ImmutableSet.chooseTableSize(1 << 29)); 262 assertEquals(1 << 30, ImmutableSet.chooseTableSize((1 << 30) - 1)); 263 264 // Now we've gone too far 265 assertThrows(IllegalArgumentException.class, () -> ImmutableSet.chooseTableSize(1 << 30)); 266 } 267 268 @GwtIncompatible // RegularImmutableSet.table not in emulation testResizeTable()269 public void testResizeTable() { 270 verifyTableSize(100, 2, 8); 271 verifyTableSize(100, 5, 8); 272 verifyTableSize(100, 33, 64); 273 verifyTableSize(17, 17, 32); 274 verifyTableSize(17, 16, 32); 275 verifyTableSize(17, 15, 32); 276 } 277 278 @GwtIncompatible // RegularImmutableSet.table not in emulation verifyTableSize(int inputSize, int setSize, int tableSize)279 private void verifyTableSize(int inputSize, int setSize, int tableSize) { 280 Builder<Integer> builder = ImmutableSet.builder(); 281 for (int i = 0; i < inputSize; i++) { 282 builder.add(i % setSize); 283 } 284 ImmutableSet<Integer> set = builder.build(); 285 assertTrue(set instanceof RegularImmutableSet); 286 assertEquals( 287 "Input size " + inputSize + " and set size " + setSize, 288 tableSize, 289 ((RegularImmutableSet<Integer>) set).table.length); 290 } 291 testCopyOf_copiesImmutableSortedSet()292 public void testCopyOf_copiesImmutableSortedSet() { 293 ImmutableSortedSet<String> sortedSet = ImmutableSortedSet.of("a"); 294 ImmutableSet<String> copy = ImmutableSet.copyOf(sortedSet); 295 assertNotSame(sortedSet, copy); 296 } 297 testToImmutableSet()298 public void testToImmutableSet() { 299 Collector<String, ?, ImmutableSet<String>> collector = ImmutableSet.toImmutableSet(); 300 Equivalence<ImmutableSet<String>> equivalence = 301 Equivalence.equals().onResultOf(ImmutableSet::asList); 302 CollectorTester.of(collector, equivalence) 303 .expectCollects(ImmutableSet.of("a", "b", "c", "d"), "a", "b", "a", "c", "b", "b", "d"); 304 } 305 testToImmutableSet_duplicates()306 public void testToImmutableSet_duplicates() { 307 class TypeWithDuplicates { 308 final int a; 309 final int b; 310 311 TypeWithDuplicates(int a, int b) { 312 this.a = a; 313 this.b = b; 314 } 315 316 @Override 317 public int hashCode() { 318 return a; 319 } 320 321 @Override 322 public boolean equals(@Nullable Object obj) { 323 return obj instanceof TypeWithDuplicates && ((TypeWithDuplicates) obj).a == a; 324 } 325 326 public boolean fullEquals(@Nullable TypeWithDuplicates other) { 327 return other != null && a == other.a && b == other.b; 328 } 329 } 330 331 Collector<TypeWithDuplicates, ?, ImmutableSet<TypeWithDuplicates>> collector = 332 ImmutableSet.toImmutableSet(); 333 BiPredicate<ImmutableSet<TypeWithDuplicates>, ImmutableSet<TypeWithDuplicates>> equivalence = 334 (set1, set2) -> { 335 if (!set1.equals(set2)) { 336 return false; 337 } 338 for (int i = 0; i < set1.size(); i++) { 339 if (!set1.asList().get(i).fullEquals(set2.asList().get(i))) { 340 return false; 341 } 342 } 343 return true; 344 }; 345 TypeWithDuplicates a = new TypeWithDuplicates(1, 1); 346 TypeWithDuplicates b1 = new TypeWithDuplicates(2, 1); 347 TypeWithDuplicates b2 = new TypeWithDuplicates(2, 2); 348 TypeWithDuplicates c = new TypeWithDuplicates(3, 1); 349 CollectorTester.of(collector, equivalence) 350 .expectCollects(ImmutableSet.of(a, b1, c), a, b1, c, b2); 351 } 352 353 @GwtIncompatible // GWT is single threaded testCopyOf_threadSafe()354 public void testCopyOf_threadSafe() { 355 verifyThreadSafe(); 356 } 357 358 @Override builder()359 <E extends Comparable<E>> Builder<E> builder() { 360 return ImmutableSet.builder(); 361 } 362 363 @Override getComplexBuilderSetLastElement()364 int getComplexBuilderSetLastElement() { 365 return LAST_COLOR_ADDED; 366 } 367 testEquals()368 public void testEquals() { 369 new EqualsTester() 370 .addEqualityGroup(ImmutableSet.of(), ImmutableSet.of()) 371 .addEqualityGroup(ImmutableSet.of(1), ImmutableSet.of(1), ImmutableSet.of(1, 1)) 372 .addEqualityGroup(ImmutableSet.of(1, 2, 1), ImmutableSet.of(2, 1, 1)) 373 .testEquals(); 374 } 375 376 /** 377 * The maximum allowed probability of falsely detecting a hash flooding attack if the input is 378 * randomly generated. 379 */ 380 private static final double HASH_FLOODING_FPP = 0.001; 381 testReuseBuilderReducingHashTableSizeWithPowerOfTwoTotalElements()382 public void testReuseBuilderReducingHashTableSizeWithPowerOfTwoTotalElements() { 383 ImmutableSet.Builder<Object> builder = ImmutableSet.builderWithExpectedSize(6); 384 builder.add(0); 385 ImmutableSet<Object> unused = builder.build(); 386 ImmutableSet<Object> subject = builder.add(1).add(2).add(3).build(); 387 assertFalse(subject.contains(4)); 388 } 389 } 390