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