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