1 /* 2 * Copyright (c) 2005, 2017, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 /* 25 * @test 26 * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464 27 * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753 28 * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215 29 * 4802647 7123424 8024709 30 * @summary Run many tests on many Collection and Map implementations 31 * @author Martin Buchholz 32 * @modules java.base/java.util:open 33 * @run main MOAT 34 * @key randomness 35 */ 36 37 /* Mother Of All (Collection) Tests 38 * 39 * Testing of collection classes is often spotty, because many tests 40 * need to be performed on many implementations, but the onus on 41 * writing the tests falls on the engineer introducing the new 42 * implementation. 43 * 44 * The idea of this mega-test is that: 45 * 46 * An engineer adding a new collection implementation could simply add 47 * their new implementation to a list of implementations in this 48 * test's main method. Any general purpose Collection<Integer> or 49 * Map<Integer,Integer> class is appropriate. 50 * 51 * An engineer fixing a regression could add their regression test here and 52 * simultaneously test all other implementations. 53 */ 54 55 import java.io.*; 56 import java.util.*; 57 import java.util.concurrent.*; 58 import static java.util.Collections.*; 59 import java.lang.reflect.*; 60 import java.util.stream.Collectors; 61 import java.util.stream.Stream; 62 63 public class MOAT { 64 // Collections under test must not be initialized to contain this value, 65 // and maps under test must not contain this value as a key. 66 // It's used as a sentinel for absent-element testing. 67 static final int ABSENT_VALUE = 778347983; 68 69 static final Integer[] integerArray; 70 static { 71 Integer[] ia = new Integer[20]; 72 // fill with 1..20 inclusive 73 for (int i = 0; i < ia.length; i++) { 74 ia[i] = i + 1; 75 } 76 integerArray = ia; 77 } 78 79 public static void realMain(String[] args) { 80 81 testCollection(new NewAbstractCollection<Integer>()); 82 testCollection(new NewAbstractSet<Integer>()); 83 testCollection(new LinkedHashSet<Integer>()); 84 testCollection(new HashSet<Integer>()); 85 testCollection(new Vector<Integer>()); 86 testCollection(new Vector<Integer>().subList(0,0)); 87 testCollection(new ArrayDeque<Integer>()); 88 testCollection(new ArrayList<Integer>()); 89 testCollection(new ArrayList<Integer>().subList(0,0)); 90 testCollection(new LinkedList<Integer>()); 91 testCollection(new LinkedList<Integer>().subList(0,0)); 92 testCollection(new TreeSet<Integer>()); 93 testCollection(Collections.checkedList(new ArrayList<Integer>(), Integer.class)); 94 testCollection(Collections.synchronizedList(new ArrayList<Integer>())); 95 testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class)); 96 testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class)); 97 testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class)); 98 testCollection(Collections.synchronizedSet(new HashSet<Integer>())); 99 testCollection(Collections.synchronizedSortedSet(new TreeSet<Integer>())); 100 testCollection(Collections.synchronizedNavigableSet(new TreeSet<Integer>())); 101 102 testCollection(new CopyOnWriteArrayList<Integer>()); 103 testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0)); 104 testCollection(new CopyOnWriteArraySet<Integer>()); 105 testCollection(new PriorityQueue<Integer>()); 106 testCollection(new PriorityBlockingQueue<Integer>()); 107 testCollection(new ArrayBlockingQueue<Integer>(20)); 108 testCollection(new LinkedBlockingQueue<Integer>(20)); 109 testCollection(new LinkedBlockingDeque<Integer>(20)); 110 testCollection(new ConcurrentLinkedDeque<Integer>()); 111 testCollection(new ConcurrentLinkedQueue<Integer>()); 112 testCollection(new LinkedTransferQueue<Integer>()); 113 testCollection(new ConcurrentSkipListSet<Integer>()); 114 testCollection(Arrays.asList(new Integer(42))); 115 testCollection(Arrays.asList(1,2,3)); 116 testCollection(nCopies(25,1)); 117 testImmutableList(nCopies(25,1)); 118 119 testMap(new HashMap<Integer,Integer>()); 120 testMap(new LinkedHashMap<Integer,Integer>()); 121 122 // TODO: Add reliable support for WeakHashMap. 123 // This test is subject to very rare failures because the GC 124 // may remove unreferenced-keys from the map at any time. 125 // testMap(new WeakHashMap<Integer,Integer>()); 126 127 testMap(new IdentityHashMap<Integer,Integer>()); 128 testMap(new TreeMap<Integer,Integer>()); 129 testMap(new Hashtable<Integer,Integer>()); 130 testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f)); 131 testMap(new ConcurrentSkipListMap<Integer,Integer>()); 132 testMap(Collections.checkedMap(new HashMap<Integer,Integer>(), Integer.class, Integer.class)); 133 testMap(Collections.checkedSortedMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class)); 134 testMap(Collections.checkedNavigableMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class)); 135 testMap(Collections.synchronizedMap(new HashMap<Integer,Integer>())); 136 testMap(Collections.synchronizedSortedMap(new TreeMap<Integer,Integer>())); 137 testMap(Collections.synchronizedNavigableMap(new TreeMap<Integer,Integer>())); 138 139 // Unmodifiable wrappers 140 testImmutableSet(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3)))); 141 testImmutableList(unmodifiableList(Arrays.asList(1,2,3))); 142 testImmutableMap(unmodifiableMap(Collections.singletonMap(1,2))); 143 testCollMutatorsAlwaysThrow(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3)))); 144 testCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet())); 145 testEmptyCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet())); 146 testListMutatorsAlwaysThrow(unmodifiableList(Arrays.asList(1,2,3))); 147 testListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList())); 148 testEmptyListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList())); 149 testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.singletonMap(1,2))); 150 testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap())); 151 testEmptyMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap())); 152 153 // Empty collections 154 final List<Integer> emptyArray = Arrays.asList(new Integer[]{}); 155 testCollection(emptyArray); 156 testEmptyList(emptyArray); 157 THROWS(IndexOutOfBoundsException.class, () -> emptyArray.set(0,1)); 158 THROWS(UnsupportedOperationException.class, () -> emptyArray.add(0,1)); 159 160 List<Integer> noOne = nCopies(0,1); 161 testCollection(noOne); 162 testEmptyList(noOne); 163 testImmutableList(noOne); 164 165 Set<Integer> emptySet = emptySet(); 166 testCollection(emptySet); 167 testEmptySet(emptySet); 168 testEmptySet(EMPTY_SET); 169 testEmptySet(Collections.emptySet()); 170 testEmptySet(Collections.emptySortedSet()); 171 testEmptySet(Collections.emptyNavigableSet()); 172 testImmutableSet(emptySet); 173 174 List<Integer> emptyList = emptyList(); 175 testCollection(emptyList); 176 testEmptyList(emptyList); 177 testEmptyList(EMPTY_LIST); 178 testEmptyList(Collections.emptyList()); 179 testImmutableList(emptyList); 180 181 Map<Integer,Integer> emptyMap = emptyMap(); 182 testMap(emptyMap); 183 testEmptyMap(emptyMap); 184 testEmptyMap(EMPTY_MAP); 185 testEmptyMap(Collections.emptyMap()); 186 testEmptyMap(Collections.emptySortedMap()); 187 testEmptyMap(Collections.emptyNavigableMap()); 188 testImmutableMap(emptyMap); 189 testImmutableMap(Collections.emptyMap()); 190 testImmutableMap(Collections.emptySortedMap()); 191 testImmutableMap(Collections.emptyNavigableMap()); 192 193 // Singleton collections 194 Set<Integer> singletonSet = singleton(1); 195 equal(singletonSet.size(), 1); 196 testCollection(singletonSet); 197 testImmutableSet(singletonSet); 198 199 List<Integer> singletonList = singletonList(1); 200 equal(singletonList.size(), 1); 201 testCollection(singletonList); 202 testImmutableList(singletonList); 203 testImmutableList(singletonList.subList(0,1)); 204 testImmutableList(singletonList.subList(0,1).subList(0,1)); 205 testEmptyList(singletonList.subList(0,0)); 206 testEmptyList(singletonList.subList(0,0).subList(0,0)); 207 208 Map<Integer,Integer> singletonMap = singletonMap(1,2); 209 equal(singletonMap.size(), 1); 210 testMap(singletonMap); 211 testImmutableMap(singletonMap); 212 213 // Immutable List 214 testEmptyList(List.of()); 215 testListMutatorsAlwaysThrow(List.of()); 216 testEmptyListMutatorsAlwaysThrow(List.of()); 217 for (List<Integer> list : Arrays.asList( 218 List.<Integer>of(), 219 List.of(1), 220 List.of(1, 2), 221 List.of(1, 2, 3), 222 List.of(1, 2, 3, 4), 223 List.of(1, 2, 3, 4, 5), 224 List.of(1, 2, 3, 4, 5, 6), 225 List.of(1, 2, 3, 4, 5, 6, 7), 226 List.of(1, 2, 3, 4, 5, 6, 7, 8), 227 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9), 228 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 229 List.of(integerArray))) { 230 testCollection(list); 231 testImmutableList(list); 232 testListMutatorsAlwaysThrow(list); 233 } 234 235 List<Integer> listCopy = List.copyOf(Arrays.asList(1, 2, 3)); 236 testCollection(listCopy); 237 testImmutableList(listCopy); 238 testListMutatorsAlwaysThrow(listCopy); 239 240 List<Integer> listCollected = Stream.of(1, 2, 3).collect(Collectors.toUnmodifiableList()); 241 equal(listCollected, List.of(1, 2, 3)); 242 testCollection(listCollected); 243 testImmutableList(listCollected); 244 testListMutatorsAlwaysThrow(listCollected); 245 246 // Immutable Set 247 testEmptySet(Set.of()); 248 testCollMutatorsAlwaysThrow(Set.of()); 249 testEmptyCollMutatorsAlwaysThrow(Set.of()); 250 for (Set<Integer> set : Arrays.asList( 251 Set.<Integer>of(), 252 Set.of(1), 253 Set.of(1, 2), 254 Set.of(1, 2, 3), 255 Set.of(1, 2, 3, 4), 256 Set.of(1, 2, 3, 4, 5), 257 Set.of(1, 2, 3, 4, 5, 6), 258 Set.of(1, 2, 3, 4, 5, 6, 7), 259 Set.of(1, 2, 3, 4, 5, 6, 7, 8), 260 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9), 261 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 262 Set.of(integerArray))) { 263 testCollection(set); 264 testImmutableSet(set); 265 testCollMutatorsAlwaysThrow(set); 266 } 267 268 Set<Integer> setCopy = Set.copyOf(Arrays.asList(1, 2, 3)); 269 testCollection(setCopy); 270 testImmutableSet(setCopy); 271 testCollMutatorsAlwaysThrow(setCopy); 272 273 Set<Integer> setCollected = Stream.of(1, 1, 2, 3, 2, 3) 274 .collect(Collectors.toUnmodifiableSet()); 275 equal(setCollected, Set.of(1, 2, 3)); 276 testCollection(setCollected); 277 testImmutableSet(setCollected); 278 testCollMutatorsAlwaysThrow(setCollected); 279 280 // Immutable Map 281 282 @SuppressWarnings("unchecked") 283 Map.Entry<Integer,Integer>[] ea = (Map.Entry<Integer,Integer>[])new Map.Entry<?,?>[20]; 284 for (int i = 0; i < ea.length; i++) { 285 ea[i] = Map.entry(i+1, i+101); 286 } 287 288 testEmptyMap(Map.of()); 289 testMapMutatorsAlwaysThrow(Map.of()); 290 testEmptyMapMutatorsAlwaysThrow(Map.of()); 291 for (Map<Integer,Integer> map : Arrays.asList( 292 Map.<Integer,Integer>of(), 293 Map.of(1, 101), 294 Map.of(1, 101, 2, 202), 295 Map.of(1, 101, 2, 202, 3, 303), 296 Map.of(1, 101, 2, 202, 3, 303, 4, 404), 297 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505), 298 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606), 299 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707), 300 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808), 301 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909), 302 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909, 10, 1010), 303 Map.ofEntries(ea))) { 304 testMap(map); 305 testImmutableMap(map); 306 testMapMutatorsAlwaysThrow(map); 307 } 308 309 Map<Integer,Integer> mapCopy = Map.copyOf(new HashMap<>(Map.of(1, 101, 2, 202, 3, 303))); 310 testMap(mapCopy); 311 testImmutableMap(mapCopy); 312 testMapMutatorsAlwaysThrow(mapCopy); 313 314 Map<Integer,Integer> mapCollected1 = 315 Stream.of(1, 2, 3) 316 .collect(Collectors.toUnmodifiableMap(i -> i, i -> 101 * i)); 317 equal(mapCollected1, Map.of(1, 101, 2, 202, 3, 303)); 318 testMap(mapCollected1); 319 testImmutableMap(mapCollected1); 320 testMapMutatorsAlwaysThrow(mapCollected1); 321 322 try { 323 Stream.of(1, 1, 2, 3, 2, 3) 324 .collect(Collectors.toUnmodifiableMap(i -> i, i -> 101 * i)); 325 fail("duplicates should have thrown an exception"); 326 } catch (IllegalStateException ise) { 327 pass(); 328 } 329 330 Map<Integer,Integer> mapCollected2 = 331 Stream.of(1, 1, 2, 3, 2, 3) 332 .collect(Collectors.toUnmodifiableMap(i -> i, i -> 101 * i, Integer::sum)); 333 equal(mapCollected2, Map.of(1, 202, 2, 404, 3, 606)); 334 testMap(mapCollected2); 335 testImmutableMap(mapCollected2); 336 testMapMutatorsAlwaysThrow(mapCollected2); 337 } 338 339 private static void checkContainsSelf(Collection<Integer> c) { 340 check(c.containsAll(c)); 341 check(c.containsAll(Arrays.asList(c.toArray()))); 342 check(c.containsAll(Arrays.asList(c.toArray(new Integer[0])))); 343 } 344 345 private static void checkContainsEmpty(Collection<Integer> c) { 346 check(c.containsAll(new ArrayList<Integer>())); 347 } 348 349 private static void checkUnique(Set<Integer> s) { 350 for (Integer i : s) { 351 int count = 0; 352 for (Integer j : s) { 353 if (Objects.equals(i,j)) 354 ++count; 355 } 356 check(count == 1); 357 } 358 } 359 360 private static <T> void testEmptyCollection(Collection<T> c) { 361 check(c.isEmpty()); 362 equal(c.size(), 0); 363 equal(c.toString(),"[]"); 364 equal(c.toArray().length, 0); 365 equal(c.toArray(new Object[0]).length, 0); 366 check(c.toArray(new Object[]{42})[0] == null); 367 368 Object[] a = new Object[1]; a[0] = Boolean.TRUE; 369 equal(c.toArray(a), a); 370 equal(a[0], null); 371 testEmptyIterator(c.iterator()); 372 } 373 374 static <T> void testEmptyIterator(final Iterator<T> it) { 375 if (rnd.nextBoolean()) 376 check(! it.hasNext()); 377 378 THROWS(NoSuchElementException.class, () -> it.next()); 379 380 try { it.remove(); } 381 catch (IllegalStateException ignored) { pass(); } 382 catch (UnsupportedOperationException ignored) { pass(); } 383 catch (Throwable t) { unexpected(t); } 384 385 if (rnd.nextBoolean()) 386 check(! it.hasNext()); 387 } 388 389 private static void testEmptyList(List<?> c) { 390 testEmptyCollection(c); 391 equal(c.hashCode(), 1); 392 equal2(c, Collections.<Integer>emptyList()); 393 } 394 395 private static <T> void testEmptySet(Set<T> c) { 396 testEmptyCollection(c); 397 equal(c.hashCode(), 0); 398 equal2(c, Collections.<Integer>emptySet()); 399 if (c instanceof NavigableSet<?>) 400 testEmptyIterator(((NavigableSet<T>)c).descendingIterator()); 401 } 402 403 private static void testImmutableCollection(final Collection<Integer> c) { 404 THROWS(UnsupportedOperationException.class, 405 () -> c.add(99), 406 () -> c.addAll(singleton(99))); 407 if (! c.isEmpty()) { 408 final Integer first = c.iterator().next(); 409 THROWS(UnsupportedOperationException.class, 410 () -> c.clear(), 411 () -> c.remove(first), 412 () -> c.removeAll(singleton(first)), 413 () -> c.retainAll(emptyList())); 414 } 415 } 416 417 private static void testImmutableSet(final Set<Integer> c) { 418 testImmutableCollection(c); 419 } 420 421 private static void testImmutableList(final List<Integer> c) { 422 testList(c); 423 testImmutableCollection(c); 424 THROWS(UnsupportedOperationException.class, 425 () -> c.set(0,42), 426 () -> c.add(0,42), 427 () -> c.addAll(0,singleton(86))); 428 if (! c.isEmpty()) 429 THROWS(UnsupportedOperationException.class, 430 () -> { Iterator<Integer> it = c.iterator(); 431 it.next(); 432 it.remove(); }, 433 () -> { ListIterator<Integer> it = c.listIterator(); 434 it.next(); 435 it.remove(); }); 436 } 437 438 /** 439 * Test that calling a mutator always throws UOE, even if the mutator 440 * wouldn't actually do anything, given its arguments. 441 * 442 * @param c the collection instance to test 443 */ 444 private static void testCollMutatorsAlwaysThrow(Collection<Integer> c) { 445 THROWS(UnsupportedOperationException.class, 446 () -> c.addAll(Collections.emptyList()), 447 () -> c.remove(ABSENT_VALUE), 448 () -> c.removeAll(Collections.emptyList()), 449 () -> c.removeIf(x -> false), 450 () -> c.retainAll(c)); 451 } 452 453 /** 454 * Test that calling a mutator always throws UOE, even if the mutator 455 * wouldn't actually do anything on an empty collection. 456 * 457 * @param c the collection instance to test, must be empty 458 */ 459 private static void testEmptyCollMutatorsAlwaysThrow(Collection<Integer> c) { 460 if (! c.isEmpty()) { 461 fail("collection is not empty"); 462 } 463 THROWS(UnsupportedOperationException.class, 464 () -> c.clear()); 465 } 466 467 /** 468 * As above, for a list. 469 * 470 * @param c the list instance to test 471 */ 472 private static void testListMutatorsAlwaysThrow(List<Integer> c) { 473 testCollMutatorsAlwaysThrow(c); 474 THROWS(UnsupportedOperationException.class, 475 () -> c.addAll(0, Collections.emptyList())); 476 } 477 478 /** 479 * As above, for an empty list. 480 * 481 * @param c the list instance to test, must be empty 482 */ 483 private static void testEmptyListMutatorsAlwaysThrow(List<Integer> c) { 484 if (! c.isEmpty()) { 485 fail("list is not empty"); 486 } 487 testEmptyCollMutatorsAlwaysThrow(c); 488 THROWS(UnsupportedOperationException.class, 489 () -> c.replaceAll(x -> x), 490 () -> c.sort(null)); 491 } 492 493 /** 494 * As above, for a map. 495 * 496 * @param m the map instance to test 497 */ 498 private static void testMapMutatorsAlwaysThrow(Map<Integer,Integer> m) { 499 THROWS(UnsupportedOperationException.class, 500 () -> m.compute(ABSENT_VALUE, (k, v) -> null), 501 () -> m.computeIfAbsent(ABSENT_VALUE, k -> null), 502 () -> m.computeIfPresent(ABSENT_VALUE, (k, v) -> null), 503 () -> m.merge(ABSENT_VALUE, 0, (k, v) -> null), 504 () -> m.putAll(Collections.emptyMap()), 505 () -> m.remove(ABSENT_VALUE), 506 () -> m.remove(ABSENT_VALUE, 0), 507 () -> m.replace(ABSENT_VALUE, 0), 508 () -> m.replace(ABSENT_VALUE, 0, 1)); 509 } 510 511 /** 512 * As above, for an empty map. 513 * 514 * @param map the map instance to test, must be empty 515 */ 516 private static void testEmptyMapMutatorsAlwaysThrow(Map<Integer,Integer> m) { 517 if (! m.isEmpty()) { 518 fail("map is not empty"); 519 } 520 THROWS(UnsupportedOperationException.class, 521 () -> m.clear(), 522 () -> m.replaceAll((k, v) -> v)); 523 } 524 525 private static void clear(Collection<Integer> c) { 526 try { c.clear(); } 527 catch (Throwable t) { unexpected(t); } 528 testEmptyCollection(c); 529 } 530 531 private static <K,V> void testEmptyMap(final Map<K,V> m) { 532 check(m.isEmpty()); 533 equal(m.size(), 0); 534 equal(m.toString(),"{}"); 535 testEmptySet(m.keySet()); 536 testEmptySet(m.entrySet()); 537 testEmptyCollection(m.values()); 538 539 try { check(! m.containsValue(null)); } 540 catch (NullPointerException ignored) { /* OK */ } 541 try { check(! m.containsKey(null)); } 542 catch (NullPointerException ignored) { /* OK */ } 543 check(! m.containsValue(1)); 544 check(! m.containsKey(1)); 545 } 546 547 private static void testImmutableMap(final Map<Integer,Integer> m) { 548 THROWS(UnsupportedOperationException.class, 549 () -> m.put(1,1), 550 () -> m.putAll(singletonMap(1,1))); 551 if (! m.isEmpty()) { 552 final Integer first = m.keySet().iterator().next(); 553 THROWS(UnsupportedOperationException.class, 554 () -> m.remove(first), 555 () -> m.clear()); 556 final Map.Entry<Integer,Integer> me 557 = m.entrySet().iterator().next(); 558 Integer key = me.getKey(); 559 Integer val = me.getValue(); 560 THROWS(UnsupportedOperationException.class, 561 () -> me.setValue(3)); 562 equal(key, me.getKey()); 563 equal(val, me.getValue()); 564 } 565 testImmutableSet(m.keySet()); 566 testImmutableCollection(m.values()); 567 //testImmutableSet(m.entrySet()); 568 } 569 570 private static void clear(Map<?,?> m) { 571 try { m.clear(); } 572 catch (Throwable t) { unexpected(t); } 573 testEmptyMap(m); 574 } 575 576 private static void oneElement(Collection<Integer> c) { 577 clear(c); 578 try { 579 check(c.add(-42)); 580 equal(c.toString(), "[-42]"); 581 if (c instanceof Set) check(! c.add(-42)); 582 } catch (Throwable t) { unexpected(t); } 583 check(! c.isEmpty()); check(c.size() == 1); 584 } 585 586 private static boolean supportsAdd(Collection<Integer> c) { 587 try { check(c.add(ABSENT_VALUE)); } 588 catch (UnsupportedOperationException t) { return false; } 589 catch (Throwable t) { unexpected(t); } 590 591 try { 592 check(c.contains(ABSENT_VALUE)); 593 check(c.remove(ABSENT_VALUE)); 594 } catch (Throwable t) { unexpected(t); } 595 return true; 596 } 597 598 private static boolean supportsRemove(Collection<Integer> c) { 599 try { check(! c.remove(ABSENT_VALUE)); } 600 catch (UnsupportedOperationException t) { return false; } 601 catch (Throwable t) { unexpected(t); } 602 return true; 603 } 604 605 // 6260652: (coll) Arrays.asList(x).toArray().getClass() 606 // should be Object[].class 607 // Fixed in jdk9, but not jdk8 ... 608 static final boolean needToWorkAround6260652 = 609 Arrays.asList("").toArray().getClass() != Object[].class; 610 611 private static void checkFunctionalInvariants(Collection<Integer> c) { 612 try { 613 checkContainsSelf(c); 614 checkContainsEmpty(c); 615 check(c.size() != 0 ^ c.isEmpty()); 616 check(! c.contains(ABSENT_VALUE)); 617 618 { 619 int size = 0; 620 for (Integer i : c) size++; 621 check(c.size() == size); 622 } 623 624 if (c instanceof Set) { 625 checkUnique((Set<Integer>)c); 626 } 627 628 check(c.toArray().length == c.size()); 629 check(c.toArray().getClass() == Object[].class 630 || 631 (needToWorkAround6260652 && 632 c.getClass().getName().equals("java.util.Arrays$ArrayList"))); 633 for (int size : new int[]{0,1,c.size(), c.size()+1}) { 634 Integer[] a = c.toArray(new Integer[size]); 635 check((size > c.size()) || a.length == c.size()); 636 int i = 0; for (Integer j : c) check(a[i++] == j); 637 check((size <= c.size()) || (a[c.size()] == null)); 638 check(a.getClass() == Integer[].class); 639 } 640 641 check(c.equals(c)); 642 if (c instanceof Serializable) { 643 //System.out.printf("Serializing %s%n", c.getClass().getName()); 644 try { 645 Object clone = serialClone(c); 646 equal(c instanceof Serializable, 647 clone instanceof Serializable); 648 equal(c instanceof RandomAccess, 649 clone instanceof RandomAccess); 650 if ((c instanceof List) || (c instanceof Set)) 651 equal(c, clone); 652 else 653 equal(new HashSet<Integer>(c), 654 new HashSet<Integer>(serialClone(c))); 655 } catch (Error xxx) { 656 if (! (xxx.getCause() instanceof NotSerializableException)) 657 throw xxx; 658 } 659 } 660 } 661 catch (Throwable t) { unexpected(t); } 662 } 663 664 //---------------------------------------------------------------- 665 // If add(null) succeeds, contains(null) & remove(null) should succeed 666 //---------------------------------------------------------------- 667 private static void testNullElement(Collection<Integer> c) { 668 669 try { 670 check(c.add(null)); 671 if (c.size() == 1) 672 equal(c.toString(), "[null]"); 673 try { 674 checkFunctionalInvariants(c); 675 check(c.contains(null)); 676 check(c.remove(null)); 677 } 678 catch (Throwable t) { unexpected(t); } 679 } 680 catch (NullPointerException e) { /* OK */ } 681 catch (Throwable t) { unexpected(t); } 682 } 683 684 //---------------------------------------------------------------- 685 // If add("x") succeeds, contains("x") & remove("x") should succeed 686 //---------------------------------------------------------------- 687 @SuppressWarnings("unchecked") 688 private static void testStringElement(Collection<Integer> c) { 689 Collection x = (Collection)c; // Make type-unsafe 690 try { 691 check(x.add("x")); 692 try { 693 check(x.contains("x")); 694 check(x.remove("x")); 695 } catch (Throwable t) { unexpected(t); } 696 } 697 catch (ClassCastException e) { /* OK */ } 698 catch (Throwable t) { unexpected(t); } 699 } 700 701 private static void testConcurrentCollection(Collection<Integer> c) { 702 try { 703 c.add(1); 704 Iterator<Integer> it = c.iterator(); 705 check(it.hasNext()); 706 clear(c); 707 check(it.next() instanceof Integer); // No CME 708 check(c.isEmpty()); 709 } 710 catch (Throwable t) { unexpected(t); } 711 } 712 713 private static void testQueue(Queue<Integer> q) { 714 q.clear(); 715 for (int i = 0; i < 5; i++) { 716 testQueueAddRemove(q, null); 717 testQueueAddRemove(q, 537); 718 q.add(i); 719 } 720 equal(q.size(), 5); 721 checkFunctionalInvariants(q); 722 q.poll(); 723 equal(q.size(), 4); 724 checkFunctionalInvariants(q); 725 if ((q instanceof LinkedBlockingQueue) || 726 (q instanceof LinkedBlockingDeque) || 727 (q instanceof ConcurrentLinkedDeque) || 728 (q instanceof ConcurrentLinkedQueue)) { 729 testQueueIteratorRemove(q); 730 } 731 } 732 733 private static void testQueueAddRemove(final Queue<Integer> q, 734 final Integer e) { 735 final List<Integer> originalContents = new ArrayList<>(q); 736 final boolean isEmpty = q.isEmpty(); 737 final boolean isList = (q instanceof List); 738 final List asList = isList ? (List) q : null; 739 check(!q.contains(e)); 740 try { 741 q.add(e); 742 } catch (NullPointerException npe) { 743 check(e == null); 744 return; // Null elements not supported 745 } 746 check(q.contains(e)); 747 check(q.remove(e)); 748 check(!q.contains(e)); 749 equal(new ArrayList<Integer>(q), originalContents); 750 751 if (q instanceof Deque<?>) { 752 final Deque<Integer> deq = (Deque<Integer>) q; 753 final List<Integer> singleton = Collections.singletonList(e); 754 755 // insert, query, remove element at head 756 if (isEmpty) { 757 THROWS(NoSuchElementException.class, 758 () -> deq.getFirst(), 759 () -> deq.element(), 760 () -> deq.iterator().next()); 761 check(deq.peekFirst() == null); 762 check(deq.peek() == null); 763 } else { 764 check(deq.getFirst() != e); 765 check(deq.element() != e); 766 check(deq.iterator().next() != e); 767 check(deq.peekFirst() != e); 768 check(deq.peek() != e); 769 } 770 check(!deq.contains(e)); 771 check(!deq.removeFirstOccurrence(e)); 772 check(!deq.removeLastOccurrence(e)); 773 if (isList) { 774 check(asList.indexOf(e) == -1); 775 check(asList.lastIndexOf(e) == -1); 776 } 777 switch (rnd.nextInt(isList ? 4 : 3)) { 778 case 0: deq.addFirst(e); break; 779 case 1: check(deq.offerFirst(e)); break; 780 case 2: deq.push(e); break; 781 case 3: asList.add(0, e); break; 782 default: throw new AssertionError(); 783 } 784 check(deq.peekFirst() == e); 785 check(deq.getFirst() == e); 786 check(deq.element() == e); 787 check(deq.peek() == e); 788 check(deq.iterator().next() == e); 789 check(deq.contains(e)); 790 if (isList) { 791 check(asList.get(0) == e); 792 check(asList.indexOf(e) == 0); 793 check(asList.lastIndexOf(e) == 0); 794 check(asList.subList(0, 1).equals(singleton)); 795 } 796 switch (rnd.nextInt(isList ? 11 : 9)) { 797 case 0: check(deq.pollFirst() == e); break; 798 case 1: check(deq.removeFirst() == e); break; 799 case 2: check(deq.remove() == e); break; 800 case 3: check(deq.pop() == e); break; 801 case 4: check(deq.removeFirstOccurrence(e)); break; 802 case 5: check(deq.removeLastOccurrence(e)); break; 803 case 6: check(deq.remove(e)); break; 804 case 7: check(deq.removeAll(singleton)); break; 805 case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break; 806 case 9: asList.remove(0); break; 807 case 10: asList.subList(0, 1).clear(); break; 808 default: throw new AssertionError(); 809 } 810 if (isEmpty) { 811 THROWS(NoSuchElementException.class, 812 () -> deq.getFirst(), 813 () -> deq.element(), 814 () -> deq.iterator().next()); 815 check(deq.peekFirst() == null); 816 check(deq.peek() == null); 817 } else { 818 check(deq.getFirst() != e); 819 check(deq.element() != e); 820 check(deq.iterator().next() != e); 821 check(deq.peekFirst() != e); 822 check(deq.peek() != e); 823 } 824 check(!deq.contains(e)); 825 check(!deq.removeFirstOccurrence(e)); 826 check(!deq.removeLastOccurrence(e)); 827 if (isList) { 828 check(isEmpty || asList.get(0) != e); 829 check(asList.indexOf(e) == -1); 830 check(asList.lastIndexOf(e) == -1); 831 } 832 equal(new ArrayList<Integer>(deq), originalContents); 833 834 // insert, query, remove element at tail 835 if (isEmpty) { 836 check(deq.peekLast() == null); 837 THROWS(NoSuchElementException.class, () -> deq.getLast()); 838 } else { 839 check(deq.peekLast() != e); 840 check(deq.getLast() != e); 841 } 842 switch (rnd.nextInt(isList ? 6 : 4)) { 843 case 0: deq.addLast(e); break; 844 case 1: check(deq.offerLast(e)); break; 845 case 2: check(deq.add(e)); break; 846 case 3: deq.addAll(singleton); break; 847 case 4: asList.addAll(deq.size(), singleton); break; 848 case 5: asList.add(deq.size(), e); break; 849 default: throw new AssertionError(); 850 } 851 check(deq.peekLast() == e); 852 check(deq.getLast() == e); 853 check(deq.contains(e)); 854 if (isList) { 855 ListIterator it = asList.listIterator(asList.size()); 856 check(it.previous() == e); 857 check(asList.get(asList.size() - 1) == e); 858 check(asList.indexOf(e) == asList.size() - 1); 859 check(asList.lastIndexOf(e) == asList.size() - 1); 860 int size = asList.size(); 861 check(asList.subList(size - 1, size).equals(singleton)); 862 } 863 switch (rnd.nextInt(isList ? 8 : 6)) { 864 case 0: check(deq.pollLast() == e); break; 865 case 1: check(deq.removeLast() == e); break; 866 case 2: check(deq.removeFirstOccurrence(e)); break; 867 case 3: check(deq.removeLastOccurrence(e)); break; 868 case 4: check(deq.remove(e)); break; 869 case 5: check(deq.removeAll(singleton)); break; 870 case 6: asList.remove(asList.size() - 1); break; 871 case 7: 872 ListIterator it = asList.listIterator(asList.size()); 873 it.previous(); 874 it.remove(); 875 break; 876 default: throw new AssertionError(); 877 } 878 if (isEmpty) { 879 check(deq.peekLast() == null); 880 THROWS(NoSuchElementException.class, () -> deq.getLast()); 881 } else { 882 check(deq.peekLast() != e); 883 check(deq.getLast() != e); 884 } 885 check(!deq.contains(e)); 886 equal(new ArrayList<Integer>(deq), originalContents); 887 888 // Test operations on empty deque 889 switch (rnd.nextInt(isList ? 4 : 2)) { 890 case 0: deq.clear(); break; 891 case 1: 892 Iterator it = deq.iterator(); 893 while (it.hasNext()) { 894 it.next(); 895 it.remove(); 896 } 897 break; 898 case 2: asList.subList(0, asList.size()).clear(); break; 899 case 3: 900 ListIterator lit = asList.listIterator(asList.size()); 901 while (lit.hasPrevious()) { 902 lit.previous(); 903 lit.remove(); 904 } 905 break; 906 default: throw new AssertionError(); 907 } 908 testEmptyCollection(deq); 909 check(!deq.iterator().hasNext()); 910 if (isList) { 911 check(!asList.listIterator().hasPrevious()); 912 THROWS(NoSuchElementException.class, 913 () -> asList.listIterator().previous()); 914 } 915 THROWS(NoSuchElementException.class, 916 () -> deq.iterator().next(), 917 () -> deq.element(), 918 () -> deq.getFirst(), 919 () -> deq.getLast(), 920 () -> deq.pop(), 921 () -> deq.remove(), 922 () -> deq.removeFirst(), 923 () -> deq.removeLast()); 924 925 check(deq.poll() == null); 926 check(deq.pollFirst() == null); 927 check(deq.pollLast() == null); 928 check(deq.peek() == null); 929 check(deq.peekFirst() == null); 930 check(deq.peekLast() == null); 931 check(!deq.removeFirstOccurrence(e)); 932 check(!deq.removeLastOccurrence(e)); 933 934 check(deq.addAll(originalContents) == !isEmpty); 935 equal(new ArrayList<Integer>(deq), originalContents); 936 check(!deq.addAll(Collections.<Integer>emptyList())); 937 equal(new ArrayList<Integer>(deq), originalContents); 938 } 939 } 940 941 private static void testQueueIteratorRemove(Queue<Integer> q) { 942 System.err.printf("testQueueIteratorRemove %s%n", 943 q.getClass().getSimpleName()); 944 q.clear(); 945 for (int i = 0; i < 5; i++) 946 q.add(i); 947 Iterator<Integer> it = q.iterator(); 948 check(it.hasNext()); 949 for (int i = 3; i >= 0; i--) 950 q.remove(i); 951 equal(it.next(), 0); 952 equal(it.next(), 4); 953 954 q.clear(); 955 for (int i = 0; i < 5; i++) 956 q.add(i); 957 it = q.iterator(); 958 equal(it.next(), 0); 959 check(it.hasNext()); 960 for (int i = 1; i < 4; i++) 961 q.remove(i); 962 equal(it.next(), 1); 963 equal(it.next(), 4); 964 } 965 966 private static void testList(final List<Integer> l) { 967 //---------------------------------------------------------------- 968 // 4802633: (coll) AbstractList.addAll(-1,emptyCollection) 969 // doesn't throw IndexOutOfBoundsException 970 //---------------------------------------------------------------- 971 try { 972 l.addAll(-1, Collections.<Integer>emptyList()); 973 fail("Expected IndexOutOfBoundsException not thrown"); 974 } 975 catch (UnsupportedOperationException ignored) {/* OK */} 976 catch (IndexOutOfBoundsException ignored) {/* OK */} 977 catch (Throwable t) { unexpected(t); } 978 979 // equal(l instanceof Serializable, 980 // l.subList(0,0) instanceof Serializable); 981 if (l.subList(0,0) instanceof Serializable) 982 check(l instanceof Serializable); 983 984 equal(l instanceof RandomAccess, 985 l.subList(0,0) instanceof RandomAccess); 986 987 l.iterator(); 988 l.listIterator(); 989 l.listIterator(0); 990 l.listIterator(l.size()); 991 THROWS(IndexOutOfBoundsException.class, 992 () -> l.listIterator(-1), 993 () -> l.listIterator(l.size() + 1)); 994 995 if (l instanceof AbstractList) { 996 try { 997 int size = l.size(); 998 AbstractList<Integer> abList = (AbstractList<Integer>) l; 999 Method m = AbstractList.class.getDeclaredMethod("removeRange", new Class[] { int.class, int.class }); 1000 m.setAccessible(true); 1001 m.invoke(abList, new Object[] { 0, 0 }); 1002 m.invoke(abList, new Object[] { size, size }); 1003 equal(size, l.size()); 1004 } 1005 catch (UnsupportedOperationException ignored) {/* OK */} 1006 catch (Throwable t) { unexpected(t); } 1007 } 1008 } 1009 1010 private static void testCollection(Collection<Integer> c) { 1011 try { testCollection1(c); } 1012 catch (Throwable t) { unexpected(t); } 1013 } 1014 1015 private static void testCollection1(Collection<Integer> c) { 1016 1017 System.out.println("\n==> " + c.getClass().getName()); 1018 1019 checkFunctionalInvariants(c); 1020 1021 if (! supportsAdd(c)) return; 1022 //System.out.println("add() supported"); 1023 1024 if (c instanceof NavigableSet) { 1025 System.out.println("NavigableSet tests..."); 1026 1027 NavigableSet<Integer> ns = (NavigableSet<Integer>)c; 1028 testNavigableSet(ns); 1029 testNavigableSet(ns.headSet(6, false)); 1030 testNavigableSet(ns.headSet(5, true)); 1031 testNavigableSet(ns.tailSet(0, false)); 1032 testNavigableSet(ns.tailSet(1, true)); 1033 testNavigableSet(ns.subSet(0, false, 5, true)); 1034 testNavigableSet(ns.subSet(1, true, 6, false)); 1035 } 1036 1037 if (c instanceof Queue) 1038 testQueue((Queue<Integer>)c); 1039 1040 if (c instanceof List) 1041 testList((List<Integer>)c); 1042 1043 check(supportsRemove(c)); 1044 1045 try { 1046 oneElement(c); 1047 checkFunctionalInvariants(c); 1048 } 1049 catch (Throwable t) { unexpected(t); } 1050 1051 clear(c); testNullElement(c); 1052 oneElement(c); testNullElement(c); 1053 1054 clear(c); testStringElement(c); 1055 oneElement(c); testStringElement(c); 1056 1057 if (c.getClass().getName().matches(".*concurrent.*")) 1058 testConcurrentCollection(c); 1059 1060 //---------------------------------------------------------------- 1061 // The "all" operations should throw NPE when passed null 1062 //---------------------------------------------------------------- 1063 { 1064 clear(c); 1065 try { 1066 c.removeAll(null); 1067 fail("Expected NullPointerException"); 1068 } 1069 catch (NullPointerException e) { pass(); } 1070 catch (Throwable t) { unexpected(t); } 1071 1072 oneElement(c); 1073 try { 1074 c.removeAll(null); 1075 fail("Expected NullPointerException"); 1076 } 1077 catch (NullPointerException e) { pass(); } 1078 catch (Throwable t) { unexpected(t); } 1079 1080 clear(c); 1081 try { 1082 c.retainAll(null); 1083 fail("Expected NullPointerException"); 1084 } 1085 catch (NullPointerException e) { pass(); } 1086 catch (Throwable t) { unexpected(t); } 1087 1088 oneElement(c); 1089 try { 1090 c.retainAll(null); 1091 fail("Expected NullPointerException"); 1092 } 1093 catch (NullPointerException e) { pass(); } 1094 catch (Throwable t) { unexpected(t); } 1095 1096 oneElement(c); 1097 try { 1098 c.addAll(null); 1099 fail("Expected NullPointerException"); 1100 } 1101 catch (NullPointerException e) { pass(); } 1102 catch (Throwable t) { unexpected(t); } 1103 1104 oneElement(c); 1105 try { 1106 c.containsAll(null); 1107 fail("Expected NullPointerException"); 1108 } 1109 catch (NullPointerException e) { pass(); } 1110 catch (Throwable t) { unexpected(t); } 1111 } 1112 } 1113 1114 //---------------------------------------------------------------- 1115 // Map 1116 //---------------------------------------------------------------- 1117 private static void checkFunctionalInvariants(Map<Integer,Integer> m) { 1118 check(m.keySet().size() == m.entrySet().size()); 1119 check(m.keySet().size() == m.size()); 1120 checkFunctionalInvariants(m.keySet()); 1121 checkFunctionalInvariants(m.values()); 1122 check(m.size() != 0 ^ m.isEmpty()); 1123 check(! m.containsKey(ABSENT_VALUE)); 1124 1125 if (m instanceof Serializable) { 1126 //System.out.printf("Serializing %s%n", m.getClass().getName()); 1127 try { 1128 Object clone = serialClone(m); 1129 equal(m instanceof Serializable, 1130 clone instanceof Serializable); 1131 equal(m, clone); 1132 } catch (Error xxx) { 1133 if (! (xxx.getCause() instanceof NotSerializableException)) 1134 throw xxx; 1135 } 1136 } 1137 } 1138 1139 private static void testMap(Map<Integer,Integer> m) { 1140 System.out.println("\n==> " + m.getClass().getName()); 1141 1142 if (m instanceof ConcurrentMap) 1143 testConcurrentMap((ConcurrentMap<Integer,Integer>) m); 1144 1145 if (m instanceof NavigableMap) { 1146 System.out.println("NavigableMap tests..."); 1147 1148 NavigableMap<Integer,Integer> nm = 1149 (NavigableMap<Integer,Integer>) m; 1150 testNavigableMapRemovers(nm); 1151 testNavigableMap(nm); 1152 testNavigableMap(nm.headMap(6, false)); 1153 testNavigableMap(nm.headMap(5, true)); 1154 testNavigableMap(nm.tailMap(0, false)); 1155 testNavigableMap(nm.tailMap(1, true)); 1156 testNavigableMap(nm.subMap(1, true, 6, false)); 1157 testNavigableMap(nm.subMap(0, false, 5, true)); 1158 } 1159 1160 checkFunctionalInvariants(m); 1161 1162 if (supportsClear(m)) { 1163 try { clear(m); } 1164 catch (Throwable t) { unexpected(t); } 1165 } 1166 1167 if (supportsPut(m)) { 1168 try { 1169 check(m.put(3333, 77777) == null); 1170 check(m.put(9134, 74982) == null); 1171 check(m.get(9134) == 74982); 1172 check(m.put(9134, 1382) == 74982); 1173 check(m.get(9134) == 1382); 1174 check(m.size() == 2); 1175 checkFunctionalInvariants(m); 1176 checkNPEConsistency(m); 1177 } 1178 catch (Throwable t) { unexpected(t); } 1179 } 1180 } 1181 1182 private static boolean supportsPut(Map<Integer,Integer> m) { 1183 // We're asking for .equals(...) semantics 1184 if (m instanceof IdentityHashMap) return false; 1185 1186 try { check(m.put(ABSENT_VALUE,12735) == null); } 1187 catch (UnsupportedOperationException t) { return false; } 1188 catch (Throwable t) { unexpected(t); } 1189 1190 try { 1191 check(m.containsKey(ABSENT_VALUE)); 1192 check(m.remove(ABSENT_VALUE) != null); 1193 } catch (Throwable t) { unexpected(t); } 1194 return true; 1195 } 1196 1197 private static boolean supportsClear(Map<?,?> m) { 1198 try { m.clear(); } 1199 catch (UnsupportedOperationException t) { return false; } 1200 catch (Throwable t) { unexpected(t); } 1201 return true; 1202 } 1203 1204 //---------------------------------------------------------------- 1205 // ConcurrentMap 1206 //---------------------------------------------------------------- 1207 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) { 1208 System.out.println("ConcurrentMap tests..."); 1209 1210 try { 1211 clear(m); 1212 1213 check(m.putIfAbsent(18357,7346) == null); 1214 check(m.containsKey(18357)); 1215 check(m.putIfAbsent(18357,8263) == 7346); 1216 try { m.putIfAbsent(18357,null); fail("NPE"); } 1217 catch (NullPointerException t) { } 1218 check(m.containsKey(18357)); 1219 1220 check(! m.replace(18357,8888,7777)); 1221 check(m.containsKey(18357)); 1222 try { m.replace(18357,null,7777); fail("NPE"); } 1223 catch (NullPointerException t) { } 1224 check(m.containsKey(18357)); 1225 check(m.get(18357) == 7346); 1226 check(m.replace(18357,7346,5555)); 1227 check(m.replace(18357,5555,7346)); 1228 check(m.get(18357) == 7346); 1229 1230 check(m.replace(92347,7834) == null); 1231 try { m.replace(18357,null); fail("NPE"); } 1232 catch (NullPointerException t) { } 1233 check(m.replace(18357,7346) == 7346); 1234 check(m.replace(18357,5555) == 7346); 1235 check(m.get(18357) == 5555); 1236 check(m.replace(18357,7346) == 5555); 1237 check(m.get(18357) == 7346); 1238 1239 check(! m.remove(18357,9999)); 1240 check(m.get(18357) == 7346); 1241 check(m.containsKey(18357)); 1242 check(! m.remove(18357,null)); // 6272521 1243 check(m.get(18357) == 7346); 1244 check(m.remove(18357,7346)); 1245 check(m.get(18357) == null); 1246 check(! m.containsKey(18357)); 1247 check(m.isEmpty()); 1248 1249 m.putIfAbsent(1,2); 1250 check(m.size() == 1); 1251 check(! m.remove(1,null)); 1252 check(! m.remove(1,null)); 1253 check(! m.remove(1,1)); 1254 check(m.remove(1,2)); 1255 check(m.isEmpty()); 1256 1257 testEmptyMap(m); 1258 } 1259 catch (Throwable t) { unexpected(t); } 1260 } 1261 1262 private static void throwsConsistently(Class<? extends Throwable> k, 1263 Iterable<Fun> fs) { 1264 List<Class<? extends Throwable>> threw = new ArrayList<>(); 1265 for (Fun f : fs) 1266 try { f.f(); threw.add(null); } 1267 catch (Throwable t) { 1268 check(k.isAssignableFrom(t.getClass())); 1269 threw.add(t.getClass()); 1270 } 1271 if (new HashSet<Object>(threw).size() != 1) 1272 fail(threw.toString()); 1273 } 1274 1275 private static <T> void checkNPEConsistency(final Map<T,Integer> m) { 1276 m.clear(); 1277 final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap) 1278 ? (ConcurrentMap<T,Integer>) m 1279 : null; 1280 List<Fun> fs = new ArrayList<>(); 1281 fs.add(() -> check(! m.containsKey(null))); 1282 fs.add(() -> equal(m.remove(null), null)); 1283 fs.add(() -> equal(m.get(null), null)); 1284 if (cm != null) 1285 fs.add(() -> check(! cm.remove(null,null))); 1286 throwsConsistently(NullPointerException.class, fs); 1287 1288 fs.clear(); 1289 final Map<T,Integer> sm = singletonMap(null,1); 1290 fs.add(() -> { equal(m.put(null,1), null); m.clear();}); 1291 fs.add(() -> { m.putAll(sm); m.clear();}); 1292 if (cm != null) { 1293 fs.add(() -> check(! cm.remove(null,null))); 1294 fs.add(() -> equal(cm.putIfAbsent(null,1), 1)); 1295 fs.add(() -> equal(cm.replace(null,1), null)); 1296 fs.add(() -> equal(cm.replace(null,1, 1), 1)); 1297 } 1298 throwsConsistently(NullPointerException.class, fs); 1299 } 1300 1301 //---------------------------------------------------------------- 1302 // NavigableMap 1303 //---------------------------------------------------------------- 1304 private static void 1305 checkNavigableMapKeys(NavigableMap<Integer,Integer> m, 1306 Integer i, 1307 Integer lower, 1308 Integer floor, 1309 Integer ceiling, 1310 Integer higher) { 1311 equal(m.lowerKey(i), lower); 1312 equal(m.floorKey(i), floor); 1313 equal(m.ceilingKey(i), ceiling); 1314 equal(m.higherKey(i), higher); 1315 } 1316 1317 private static void 1318 checkNavigableSetKeys(NavigableSet<Integer> m, 1319 Integer i, 1320 Integer lower, 1321 Integer floor, 1322 Integer ceiling, 1323 Integer higher) { 1324 equal(m.lower(i), lower); 1325 equal(m.floor(i), floor); 1326 equal(m.ceiling(i), ceiling); 1327 equal(m.higher(i), higher); 1328 } 1329 1330 static final Random rnd = new Random(); 1331 static void equalNext(final Iterator<?> it, Object expected) { 1332 if (rnd.nextBoolean()) 1333 check(it.hasNext()); 1334 equal(it.next(), expected); 1335 } 1336 1337 static void equalMaps(Map m1, Map m2) { 1338 equal(m1, m2); 1339 equal(m2, m1); 1340 equal(m1.size(), m2.size()); 1341 equal(m1.isEmpty(), m2.isEmpty()); 1342 equal(m1.toString(), m2.toString()); 1343 check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray())); 1344 } 1345 1346 @SuppressWarnings({"unchecked", "rawtypes"}) 1347 static void testNavigableMapRemovers(NavigableMap m) 1348 { 1349 final Map emptyMap = new HashMap(); 1350 1351 final Map singletonMap = new HashMap(); 1352 singletonMap.put(1, 2); 1353 1354 abstract class NavigableMapView { 1355 abstract NavigableMap view(NavigableMap m); 1356 } 1357 1358 NavigableMapView[] views = { 1359 new NavigableMapView() { NavigableMap view(NavigableMap m) { 1360 return m; }}, 1361 new NavigableMapView() { NavigableMap view(NavigableMap m) { 1362 return m.headMap(99, true); }}, 1363 new NavigableMapView() { NavigableMap view(NavigableMap m) { 1364 return m.tailMap(-99, false); }}, 1365 new NavigableMapView() { NavigableMap view(NavigableMap m) { 1366 return m.subMap(-99, true, 99, false); }}, 1367 }; 1368 1369 abstract class Remover { 1370 abstract void remove(NavigableMap m, Object k, Object v); 1371 } 1372 1373 Remover[] removers = { 1374 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1375 equal(m.remove(k), v); }}, 1376 1377 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1378 equal(m.descendingMap().remove(k), v); }}, 1379 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1380 equal(m.descendingMap().headMap(-86, false).remove(k), v); }}, 1381 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1382 equal(m.descendingMap().tailMap(86, true).remove(k), v); }}, 1383 1384 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1385 equal(m.headMap(86, true).remove(k), v); }}, 1386 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1387 equal(m.tailMap(-86, true).remove(k), v); }}, 1388 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1389 equal(m.subMap(-86, false, 86, true).remove(k), v); }}, 1390 1391 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1392 check(m.keySet().remove(k)); }}, 1393 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1394 check(m.navigableKeySet().remove(k)); }}, 1395 1396 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1397 check(m.navigableKeySet().headSet(86, true).remove(k)); }}, 1398 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1399 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }}, 1400 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1401 check(m.navigableKeySet().subSet(-86, true, 86, false) 1402 .remove(k)); }}, 1403 1404 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1405 check(m.descendingKeySet().headSet(-86, false).remove(k)); }}, 1406 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1407 check(m.descendingKeySet().tailSet(86, true).remove(k)); }}, 1408 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1409 check(m.descendingKeySet().subSet(86, true, -86, false) 1410 .remove(k)); }}, 1411 }; 1412 1413 for (NavigableMapView view : views) { 1414 for (Remover remover : removers) { 1415 try { 1416 m.clear(); 1417 equalMaps(m, emptyMap); 1418 equal(m.put(1, 2), null); 1419 equalMaps(m, singletonMap); 1420 NavigableMap v = view.view(m); 1421 remover.remove(v, 1, 2); 1422 equalMaps(m, emptyMap); 1423 } catch (Throwable t) { unexpected(t); } 1424 } 1425 } 1426 } 1427 1428 private static void testNavigableMap(NavigableMap<Integer,Integer> m) 1429 { 1430 clear(m); 1431 checkNavigableMapKeys(m, 1, null, null, null, null); 1432 1433 equal(m.put(1, 2), null); 1434 equal(m.put(3, 4), null); 1435 equal(m.put(5, 9), null); 1436 1437 equal(m.put(1, 2), 2); 1438 equal(m.put(3, 4), 4); 1439 equal(m.put(5, 6), 9); 1440 1441 checkNavigableMapKeys(m, 0, null, null, 1, 1); 1442 checkNavigableMapKeys(m, 1, null, 1, 1, 3); 1443 checkNavigableMapKeys(m, 2, 1, 1, 3, 3); 1444 checkNavigableMapKeys(m, 3, 1, 3, 3, 5); 1445 checkNavigableMapKeys(m, 5, 3, 5, 5, null); 1446 checkNavigableMapKeys(m, 6, 5, 5, null, null); 1447 1448 for (final Iterator<Integer> it : 1449 (Iterator<Integer>[]) 1450 new Iterator<?>[] { 1451 m.descendingKeySet().iterator(), 1452 m.navigableKeySet().descendingIterator()}) { 1453 equalNext(it, 5); 1454 equalNext(it, 3); 1455 equalNext(it, 1); 1456 check(! it.hasNext()); 1457 THROWS(NoSuchElementException.class, () -> it.next()); 1458 } 1459 1460 { 1461 final Iterator<Map.Entry<Integer,Integer>> it 1462 = m.descendingMap().entrySet().iterator(); 1463 check(it.hasNext()); equal(it.next().getKey(), 5); 1464 check(it.hasNext()); equal(it.next().getKey(), 3); 1465 check(it.hasNext()); equal(it.next().getKey(), 1); 1466 check(! it.hasNext()); 1467 THROWS(NoSuchElementException.class, () -> it.next()); 1468 } 1469 1470 prepMapForDescItrTests(m); 1471 checkDescItrRmFirst(m.keySet(), m.navigableKeySet().descendingIterator()); 1472 prepMapForDescItrTests(m); 1473 checkDescItrRmMid(m.keySet(), m.navigableKeySet().descendingIterator()); 1474 prepMapForDescItrTests(m); 1475 checkDescItrRmLast(m.keySet(), m.navigableKeySet().descendingIterator()); 1476 1477 prepMapForDescItrTests(m); 1478 checkDescItrRmFirst(m.keySet(), m.descendingMap().keySet().iterator()); 1479 prepMapForDescItrTests(m); 1480 checkDescItrRmMid(m.keySet(), m.descendingMap().keySet().iterator()); 1481 prepMapForDescItrTests(m); 1482 checkDescItrRmLast(m.keySet(), m.descendingMap().keySet().iterator()); 1483 1484 prepMapForDescItrTests(m); 1485 checkDescItrRmFirst(m.keySet(), m.descendingKeySet().iterator()); 1486 prepMapForDescItrTests(m); 1487 checkDescItrRmMid(m.keySet(), m.descendingKeySet().iterator()); 1488 prepMapForDescItrTests(m); 1489 checkDescItrRmLast(m.keySet(), m.descendingKeySet().iterator()); 1490 1491 prepMapForDescItrTests(m); 1492 checkDescItrRmFirst(m.values(), m.descendingMap().values().iterator()); 1493 prepMapForDescItrTests(m); 1494 checkDescItrRmMid(m.values(), m.descendingMap().values().iterator()); 1495 prepMapForDescItrTests(m); 1496 checkDescItrRmLast(m.values(), m.descendingMap().values().iterator()); 1497 1498 prepMapForDescItrTests(m); 1499 checkDescItrRmFirst((Collection)m.entrySet(), 1500 m.descendingMap().entrySet().iterator()); 1501 prepMapForDescItrTests(m); 1502 checkDescItrRmMid((Collection)m.entrySet(), 1503 m.descendingMap().entrySet().iterator()); 1504 prepMapForDescItrTests(m); 1505 checkDescItrRmLast((Collection)m.entrySet(), 1506 m.descendingMap().entrySet().iterator()); 1507 } 1508 1509 private static void testNavigableSet(NavigableSet<Integer> s) { 1510 clear(s); 1511 checkNavigableSetKeys(s, 1, null, null, null, null); 1512 1513 check(s.add(1)); 1514 check(s.add(3)); 1515 check(s.add(5)); 1516 1517 check(! s.add(1)); 1518 check(! s.add(3)); 1519 check(! s.add(5)); 1520 1521 checkNavigableSetKeys(s, 0, null, null, 1, 1); 1522 checkNavigableSetKeys(s, 1, null, 1, 1, 3); 1523 checkNavigableSetKeys(s, 2, 1, 1, 3, 3); 1524 checkNavigableSetKeys(s, 3, 1, 3, 3, 5); 1525 checkNavigableSetKeys(s, 5, 3, 5, 5, null); 1526 checkNavigableSetKeys(s, 6, 5, 5, null, null); 1527 1528 for (final Iterator<Integer> it : 1529 (Iterator<Integer>[]) 1530 new Iterator<?>[] { 1531 s.descendingIterator(), 1532 s.descendingSet().iterator()}) { 1533 equalNext(it, 5); 1534 equalNext(it, 3); 1535 equalNext(it, 1); 1536 check(! it.hasNext()); 1537 THROWS(NoSuchElementException.class, () -> it.next()); 1538 } 1539 1540 prepSetForDescItrTests(s); 1541 checkDescItrRmFirst(s, s.descendingIterator()); 1542 prepSetForDescItrTests(s); 1543 checkDescItrRmMid(s, s.descendingIterator()); 1544 prepSetForDescItrTests(s); 1545 checkDescItrRmLast(s, s.descendingIterator()); 1546 1547 prepSetForDescItrTests(s); 1548 checkDescItrRmFirst(s, s.descendingSet().iterator()); 1549 prepSetForDescItrTests(s); 1550 checkDescItrRmMid(s, s.descendingSet().iterator()); 1551 prepSetForDescItrTests(s); 1552 checkDescItrRmLast(s, s.descendingSet().iterator()); 1553 } 1554 1555 private static void prepSetForDescItrTests(Set s) { 1556 clear(s); 1557 check(s.add(1)); 1558 check(s.add(3)); 1559 check(s.add(5)); 1560 } 1561 1562 private static void prepMapForDescItrTests(Map m) { 1563 clear(m); 1564 equal(m.put(1, 2), null); 1565 equal(m.put(3, 4), null); 1566 equal(m.put(5, 9), null); 1567 } 1568 1569 //-------------------------------------------------------------------- 1570 // Check behavior of descending iterator when first element is removed 1571 //-------------------------------------------------------------------- 1572 private static <T> void checkDescItrRmFirst(Collection<T> ascColl, 1573 Iterator<T> descItr) { 1574 T[] expected = (T[]) ascColl.toArray(); 1575 int idx = expected.length -1; 1576 1577 equalNext(descItr, expected[idx--]); 1578 descItr.remove(); 1579 while (idx >= 0 && descItr.hasNext()) { 1580 equalNext(descItr, expected[idx--]); 1581 } 1582 equal(descItr.hasNext(), false); 1583 equal(idx, -1); 1584 } 1585 1586 //----------------------------------------------------------------------- 1587 // Check behavior of descending iterator when a middle element is removed 1588 //----------------------------------------------------------------------- 1589 private static <T> void checkDescItrRmMid(Collection<T> ascColl, 1590 Iterator<T> descItr) { 1591 T[] expected = (T[]) ascColl.toArray(); 1592 int idx = expected.length -1; 1593 1594 while (idx >= expected.length / 2) { 1595 equalNext(descItr, expected[idx--]); 1596 } 1597 descItr.remove(); 1598 while (idx >= 0 && descItr.hasNext()) { 1599 equalNext(descItr, expected[idx--]); 1600 } 1601 equal(descItr.hasNext(), false); 1602 equal(idx, -1); 1603 } 1604 1605 //----------------------------------------------------------------------- 1606 // Check behavior of descending iterator when the last element is removed 1607 //----------------------------------------------------------------------- 1608 private static <T> void checkDescItrRmLast(Collection<T> ascColl, 1609 Iterator<T> descItr) { 1610 T[] expected = (T[]) ascColl.toArray(); 1611 int idx = expected.length -1; 1612 1613 while (idx >= 0 && descItr.hasNext()) { 1614 equalNext(descItr, expected[idx--]); 1615 } 1616 equal(idx, -1); 1617 equal(descItr.hasNext(), false); 1618 descItr.remove(); 1619 equal(ascColl.contains(expected[0]), false); 1620 } 1621 1622 //--------------------- Infrastructure --------------------------- 1623 static volatile int passed = 0, failed = 0; 1624 static void pass() { passed++; } 1625 static void fail() { failed++; Thread.dumpStack(); } 1626 static void fail(String msg) { System.out.println(msg); fail(); } 1627 static void unexpected(Throwable t) { failed++; t.printStackTrace(); } 1628 static void check(boolean cond) { if (cond) pass(); else fail(); } 1629 static void equal(Object x, Object y) { 1630 if (x == null ? y == null : x.equals(y)) pass(); 1631 else {System.out.println(x + " not equal to " + y); fail();}} 1632 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);} 1633 public static void main(String[] args) throws Throwable { 1634 try { realMain(args); } catch (Throwable t) { unexpected(t); } 1635 1636 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 1637 if (failed > 0) throw new Exception("Some tests failed"); 1638 } 1639 interface Fun {void f() throws Throwable;} 1640 private static void THROWS(Class<? extends Throwable> k, Fun... fs) { 1641 for (Fun f : fs) 1642 try { f.f(); fail("Expected " + k.getName() + " not thrown"); } 1643 catch (Throwable t) { 1644 if (k.isAssignableFrom(t.getClass())) pass(); 1645 else unexpected(t);}} 1646 static byte[] serializedForm(Object obj) { 1647 try { 1648 ByteArrayOutputStream baos = new ByteArrayOutputStream(); 1649 new ObjectOutputStream(baos).writeObject(obj); 1650 return baos.toByteArray(); 1651 } catch (IOException e) { throw new Error(e); }} 1652 static Object readObject(byte[] bytes) 1653 throws IOException, ClassNotFoundException { 1654 InputStream is = new ByteArrayInputStream(bytes); 1655 return new ObjectInputStream(is).readObject();} 1656 @SuppressWarnings("unchecked") 1657 static <T> T serialClone(T obj) { 1658 try { return (T) readObject(serializedForm(obj)); } 1659 catch (Exception e) { throw new Error(e); }} 1660 private static class NewAbstractCollection<E> extends AbstractCollection<E> { 1661 ArrayList<E> list = new ArrayList<>(); 1662 public boolean remove(Object obj) { 1663 return list.remove(obj); 1664 } 1665 public boolean add(E e) { 1666 return list.add(e); 1667 } 1668 public Iterator<E> iterator() { 1669 return list.iterator(); 1670 } 1671 public int size() { 1672 return list.size(); 1673 } 1674 } 1675 private static class NewAbstractSet<E> extends AbstractSet<E> { 1676 HashSet<E> set = new HashSet<>(); 1677 public boolean remove(Object obj) { 1678 return set.remove(obj); 1679 } 1680 public boolean add(E e) { 1681 return set.add(e); 1682 } 1683 public Iterator<E> iterator() { 1684 return set.iterator(); 1685 } 1686 public int size() { 1687 return set.size(); 1688 } 1689 } 1690 1691 }