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