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