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