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 equal(c.toArray(Object[]::new).length, 0);
367 check(c.toArray(new Object[]{42})[0] == null);
368
369 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
370 equal(c.toArray(a), a);
371 equal(a[0], null);
372 testEmptyIterator(c.iterator());
373 }
374
375 static <T> void testEmptyIterator(final Iterator<T> it) {
376 if (rnd.nextBoolean())
377 check(! it.hasNext());
378
379 THROWS(NoSuchElementException.class, () -> it.next());
380
381 try { it.remove(); }
382 catch (IllegalStateException ignored) { pass(); }
383 catch (UnsupportedOperationException ignored) { pass(); }
384 catch (Throwable t) { unexpected(t); }
385
386 if (rnd.nextBoolean())
387 check(! it.hasNext());
388 }
389
390 private static void testEmptyList(List<?> c) {
391 testEmptyCollection(c);
392 equal(c.hashCode(), 1);
393 equal2(c, Collections.<Integer>emptyList());
394 }
395
396 private static <T> void testEmptySet(Set<T> c) {
397 testEmptyCollection(c);
398 equal(c.hashCode(), 0);
399 equal2(c, Collections.<Integer>emptySet());
400 if (c instanceof NavigableSet<?>)
401 testEmptyIterator(((NavigableSet<T>)c).descendingIterator());
402 }
403
404 private static void testImmutableCollection(final Collection<Integer> c) {
405 THROWS(UnsupportedOperationException.class,
406 () -> c.add(99),
407 () -> c.addAll(singleton(99)));
408 if (! c.isEmpty()) {
409 final Integer first = c.iterator().next();
410 THROWS(UnsupportedOperationException.class,
411 () -> c.clear(),
412 () -> c.remove(first),
413 () -> c.removeAll(singleton(first)),
414 () -> c.retainAll(emptyList()));
415 }
416 }
417
418 private static void testImmutableSet(final Set<Integer> c) {
419 testImmutableCollection(c);
420 }
421
422 private static void testImmutableList(final List<Integer> c) {
423 testList(c);
424 testImmutableCollection(c);
425 THROWS(UnsupportedOperationException.class,
426 () -> c.set(0,42),
427 () -> c.add(0,42),
428 () -> c.addAll(0,singleton(86)));
429 if (! c.isEmpty())
430 THROWS(UnsupportedOperationException.class,
431 () -> { Iterator<Integer> it = c.iterator();
432 it.next();
433 it.remove(); },
434 () -> { ListIterator<Integer> it = c.listIterator();
435 it.next();
436 it.remove(); });
437 }
438
439 /**
440 * Test that calling a mutator always throws UOE, even if the mutator
441 * wouldn't actually do anything, given its arguments.
442 *
443 * @param c the collection instance to test
444 */
445 private static void testCollMutatorsAlwaysThrow(Collection<Integer> c) {
446 THROWS(UnsupportedOperationException.class,
447 () -> c.addAll(Collections.emptyList()),
448 () -> c.remove(ABSENT_VALUE),
449 () -> c.removeAll(Collections.emptyList()),
450 () -> c.removeIf(x -> false),
451 () -> c.retainAll(c));
452 }
453
454 /**
455 * Test that calling a mutator always throws UOE, even if the mutator
456 * wouldn't actually do anything on an empty collection.
457 *
458 * @param c the collection instance to test, must be empty
459 */
460 private static void testEmptyCollMutatorsAlwaysThrow(Collection<Integer> c) {
461 if (! c.isEmpty()) {
462 fail("collection is not empty");
463 }
464 THROWS(UnsupportedOperationException.class,
465 () -> c.clear());
466 }
467
468 /**
469 * As above, for a list.
470 *
471 * @param c the list instance to test
472 */
473 private static void testListMutatorsAlwaysThrow(List<Integer> c) {
474 testCollMutatorsAlwaysThrow(c);
475 THROWS(UnsupportedOperationException.class,
476 () -> c.addAll(0, Collections.emptyList()));
477 }
478
479 /**
480 * As above, for an empty list.
481 *
482 * @param c the list instance to test, must be empty
483 */
484 private static void testEmptyListMutatorsAlwaysThrow(List<Integer> c) {
485 if (! c.isEmpty()) {
486 fail("list is not empty");
487 }
488 testEmptyCollMutatorsAlwaysThrow(c);
489 THROWS(UnsupportedOperationException.class,
490 () -> c.replaceAll(x -> x),
491 () -> c.sort(null));
492 }
493
494 /**
495 * As above, for a map.
496 *
497 * @param m the map instance to test
498 */
499 private static void testMapMutatorsAlwaysThrow(Map<Integer,Integer> m) {
500 THROWS(UnsupportedOperationException.class,
501 () -> m.compute(ABSENT_VALUE, (k, v) -> null),
502 () -> m.computeIfAbsent(ABSENT_VALUE, k -> null),
503 () -> m.computeIfPresent(ABSENT_VALUE, (k, v) -> null),
504 () -> m.merge(ABSENT_VALUE, 0, (k, v) -> null),
505 () -> m.putAll(Collections.emptyMap()),
506 () -> m.remove(ABSENT_VALUE),
507 () -> m.remove(ABSENT_VALUE, 0),
508 () -> m.replace(ABSENT_VALUE, 0),
509 () -> m.replace(ABSENT_VALUE, 0, 1));
510 }
511
512 /**
513 * As above, for an empty map.
514 *
515 * @param map the map instance to test, must be empty
516 */
517 private static void testEmptyMapMutatorsAlwaysThrow(Map<Integer,Integer> m) {
518 if (! m.isEmpty()) {
519 fail("map is not empty");
520 }
521 THROWS(UnsupportedOperationException.class,
522 () -> m.clear(),
523 () -> m.replaceAll((k, v) -> v));
524 }
525
526 private static void clear(Collection<Integer> c) {
527 try { c.clear(); }
528 catch (Throwable t) { unexpected(t); }
529 testEmptyCollection(c);
530 }
531
532 private static <K,V> void testEmptyMap(final Map<K,V> m) {
533 check(m.isEmpty());
534 equal(m.size(), 0);
535 equal(m.toString(),"{}");
536 testEmptySet(m.keySet());
537 testEmptySet(m.entrySet());
538 testEmptyCollection(m.values());
539
540 try { check(! m.containsValue(null)); }
541 catch (NullPointerException ignored) { /* OK */ }
542 try { check(! m.containsKey(null)); }
543 catch (NullPointerException ignored) { /* OK */ }
544 check(! m.containsValue(1));
545 check(! m.containsKey(1));
546 }
547
548 private static void testImmutableMap(final Map<Integer,Integer> m) {
549 THROWS(UnsupportedOperationException.class,
550 () -> m.put(1,1),
551 () -> m.putAll(singletonMap(1,1)));
552 if (! m.isEmpty()) {
553 final Integer first = m.keySet().iterator().next();
554 THROWS(UnsupportedOperationException.class,
555 () -> m.remove(first),
556 () -> m.clear());
557 final Map.Entry<Integer,Integer> me
558 = m.entrySet().iterator().next();
559 Integer key = me.getKey();
560 Integer val = me.getValue();
561 THROWS(UnsupportedOperationException.class,
562 () -> me.setValue(3));
563 equal(key, me.getKey());
564 equal(val, me.getValue());
565 }
566 testImmutableSet(m.keySet());
567 testImmutableCollection(m.values());
568 //testImmutableSet(m.entrySet());
569 }
570
571 private static void clear(Map<?,?> m) {
572 try { m.clear(); }
573 catch (Throwable t) { unexpected(t); }
574 testEmptyMap(m);
575 }
576
577 private static void oneElement(Collection<Integer> c) {
578 clear(c);
579 try {
580 check(c.add(-42));
581 equal(c.toString(), "[-42]");
582 if (c instanceof Set) check(! c.add(-42));
583 } catch (Throwable t) { unexpected(t); }
584 check(! c.isEmpty()); check(c.size() == 1);
585 }
586
587 private static boolean supportsAdd(Collection<Integer> c) {
588 try { check(c.add(ABSENT_VALUE)); }
589 catch (UnsupportedOperationException t) { return false; }
590 catch (Throwable t) { unexpected(t); }
591
592 try {
593 check(c.contains(ABSENT_VALUE));
594 check(c.remove(ABSENT_VALUE));
595 } catch (Throwable t) { unexpected(t); }
596 return true;
597 }
598
599 private static boolean supportsRemove(Collection<Integer> c) {
600 try { check(! c.remove(ABSENT_VALUE)); }
601 catch (UnsupportedOperationException t) { return false; }
602 catch (Throwable t) { unexpected(t); }
603 return true;
604 }
605
606 // 6260652: (coll) Arrays.asList(x).toArray().getClass()
607 // should be Object[].class
608 // Fixed in jdk9, but not jdk8 ...
609 static final boolean needToWorkAround6260652 =
610 Arrays.asList("").toArray().getClass() != Object[].class;
611
612 private static void checkFunctionalInvariants(Collection<Integer> c) {
613 try {
614 checkContainsSelf(c);
615 checkContainsEmpty(c);
616 check(c.size() != 0 ^ c.isEmpty());
617 check(! c.contains(ABSENT_VALUE));
618
619 {
620 int size = 0;
621 for (Integer i : c) size++;
622 check(c.size() == size);
623 }
624
625 if (c instanceof Set) {
626 checkUnique((Set<Integer>)c);
627 }
628
629 check(c.toArray().length == c.size());
630 check(c.toArray().getClass() == Object[].class
631 ||
632 (needToWorkAround6260652 &&
633 c.getClass().getName().equals("java.util.Arrays$ArrayList")));
634 for (int size : new int[]{0,1,c.size(), c.size()+1}) {
635 Integer[] a = c.toArray(new Integer[size]);
636 check((size > c.size()) || a.length == c.size());
637 int i = 0; for (Integer j : c) check(a[i++] == j);
638 check((size <= c.size()) || (a[c.size()] == null));
639 check(a.getClass() == Integer[].class);
640 }
641
642 {
643 Integer[] a = c.toArray(Integer[]::new);
644 equal(c.size(), a.length);
645 check(a.getClass() == Integer[].class);
646 check(Arrays.equals(c.toArray(new Integer[0]), a));
647 }
648
649 check(c.equals(c));
650 if (c instanceof Serializable) {
651 //System.out.printf("Serializing %s%n", c.getClass().getName());
652 try {
653 Object clone = serialClone(c);
654 equal(c instanceof Serializable,
655 clone instanceof Serializable);
656 equal(c instanceof RandomAccess,
657 clone instanceof RandomAccess);
658 if ((c instanceof List) || (c instanceof Set))
659 equal(c, clone);
660 else
661 equal(new HashSet<Integer>(c),
662 new HashSet<Integer>(serialClone(c)));
663 } catch (Error xxx) {
664 if (! (xxx.getCause() instanceof NotSerializableException))
665 throw xxx;
666 }
667 }
668 }
669 catch (Throwable t) { unexpected(t); }
670 }
671
672 //----------------------------------------------------------------
673 // If add(null) succeeds, contains(null) & remove(null) should succeed
674 //----------------------------------------------------------------
675 private static void testNullElement(Collection<Integer> c) {
676
677 try {
678 check(c.add(null));
679 if (c.size() == 1)
680 equal(c.toString(), "[null]");
681 try {
682 checkFunctionalInvariants(c);
683 check(c.contains(null));
684 check(c.remove(null));
685 }
686 catch (Throwable t) { unexpected(t); }
687 }
688 catch (NullPointerException e) { /* OK */ }
689 catch (Throwable t) { unexpected(t); }
690 }
691
692 //----------------------------------------------------------------
693 // If add("x") succeeds, contains("x") & remove("x") should succeed
694 //----------------------------------------------------------------
695 @SuppressWarnings("unchecked")
696 private static void testStringElement(Collection<Integer> c) {
697 Collection x = (Collection)c; // Make type-unsafe
698 try {
699 check(x.add("x"));
700 try {
701 check(x.contains("x"));
702 check(x.remove("x"));
703 } catch (Throwable t) { unexpected(t); }
704 }
705 catch (ClassCastException e) { /* OK */ }
706 catch (Throwable t) { unexpected(t); }
707 }
708
709 private static void testConcurrentCollection(Collection<Integer> c) {
710 try {
711 c.add(1);
712 Iterator<Integer> it = c.iterator();
713 check(it.hasNext());
714 clear(c);
715 check(it.next() instanceof Integer); // No CME
716 check(c.isEmpty());
717 }
718 catch (Throwable t) { unexpected(t); }
719 }
720
721 private static void testQueue(Queue<Integer> q) {
722 q.clear();
723 for (int i = 0; i < 5; i++) {
724 testQueueAddRemove(q, null);
725 testQueueAddRemove(q, 537);
726 q.add(i);
727 }
728 equal(q.size(), 5);
729 checkFunctionalInvariants(q);
730 q.poll();
731 equal(q.size(), 4);
732 checkFunctionalInvariants(q);
733 if ((q instanceof LinkedBlockingQueue) ||
734 (q instanceof LinkedBlockingDeque) ||
735 (q instanceof ConcurrentLinkedDeque) ||
736 (q instanceof ConcurrentLinkedQueue)) {
737 testQueueIteratorRemove(q);
738 }
739 }
740
741 private static void testQueueAddRemove(final Queue<Integer> q,
742 final Integer e) {
743 final List<Integer> originalContents = new ArrayList<>(q);
744 final boolean isEmpty = q.isEmpty();
745 final boolean isList = (q instanceof List);
746 final List asList = isList ? (List) q : null;
747 check(!q.contains(e));
748 try {
749 q.add(e);
750 } catch (NullPointerException npe) {
751 check(e == null);
752 return; // Null elements not supported
753 }
754 check(q.contains(e));
755 check(q.remove(e));
756 check(!q.contains(e));
757 equal(new ArrayList<Integer>(q), originalContents);
758
759 if (q instanceof Deque<?>) {
760 final Deque<Integer> deq = (Deque<Integer>) q;
761 final List<Integer> singleton = Collections.singletonList(e);
762
763 // insert, query, remove element at head
764 if (isEmpty) {
765 THROWS(NoSuchElementException.class,
766 () -> deq.getFirst(),
767 () -> deq.element(),
768 () -> deq.iterator().next());
769 check(deq.peekFirst() == null);
770 check(deq.peek() == null);
771 } else {
772 check(deq.getFirst() != e);
773 check(deq.element() != e);
774 check(deq.iterator().next() != e);
775 check(deq.peekFirst() != e);
776 check(deq.peek() != e);
777 }
778 check(!deq.contains(e));
779 check(!deq.removeFirstOccurrence(e));
780 check(!deq.removeLastOccurrence(e));
781 if (isList) {
782 check(asList.indexOf(e) == -1);
783 check(asList.lastIndexOf(e) == -1);
784 }
785 switch (rnd.nextInt(isList ? 4 : 3)) {
786 case 0: deq.addFirst(e); break;
787 case 1: check(deq.offerFirst(e)); break;
788 case 2: deq.push(e); break;
789 case 3: asList.add(0, e); break;
790 default: throw new AssertionError();
791 }
792 check(deq.peekFirst() == e);
793 check(deq.getFirst() == e);
794 check(deq.element() == e);
795 check(deq.peek() == e);
796 check(deq.iterator().next() == e);
797 check(deq.contains(e));
798 if (isList) {
799 check(asList.get(0) == e);
800 check(asList.indexOf(e) == 0);
801 check(asList.lastIndexOf(e) == 0);
802 check(asList.subList(0, 1).equals(singleton));
803 }
804 switch (rnd.nextInt(isList ? 11 : 9)) {
805 case 0: check(deq.pollFirst() == e); break;
806 case 1: check(deq.removeFirst() == e); break;
807 case 2: check(deq.remove() == e); break;
808 case 3: check(deq.pop() == e); break;
809 case 4: check(deq.removeFirstOccurrence(e)); break;
810 case 5: check(deq.removeLastOccurrence(e)); break;
811 case 6: check(deq.remove(e)); break;
812 case 7: check(deq.removeAll(singleton)); break;
813 case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break;
814 case 9: asList.remove(0); break;
815 case 10: asList.subList(0, 1).clear(); break;
816 default: throw new AssertionError();
817 }
818 if (isEmpty) {
819 THROWS(NoSuchElementException.class,
820 () -> deq.getFirst(),
821 () -> deq.element(),
822 () -> deq.iterator().next());
823 check(deq.peekFirst() == null);
824 check(deq.peek() == null);
825 } else {
826 check(deq.getFirst() != e);
827 check(deq.element() != e);
828 check(deq.iterator().next() != e);
829 check(deq.peekFirst() != e);
830 check(deq.peek() != e);
831 }
832 check(!deq.contains(e));
833 check(!deq.removeFirstOccurrence(e));
834 check(!deq.removeLastOccurrence(e));
835 if (isList) {
836 check(isEmpty || asList.get(0) != e);
837 check(asList.indexOf(e) == -1);
838 check(asList.lastIndexOf(e) == -1);
839 }
840 equal(new ArrayList<Integer>(deq), originalContents);
841
842 // insert, query, remove element at tail
843 if (isEmpty) {
844 check(deq.peekLast() == null);
845 THROWS(NoSuchElementException.class, () -> deq.getLast());
846 } else {
847 check(deq.peekLast() != e);
848 check(deq.getLast() != e);
849 }
850 switch (rnd.nextInt(isList ? 6 : 4)) {
851 case 0: deq.addLast(e); break;
852 case 1: check(deq.offerLast(e)); break;
853 case 2: check(deq.add(e)); break;
854 case 3: deq.addAll(singleton); break;
855 case 4: asList.addAll(deq.size(), singleton); break;
856 case 5: asList.add(deq.size(), e); break;
857 default: throw new AssertionError();
858 }
859 check(deq.peekLast() == e);
860 check(deq.getLast() == e);
861 check(deq.contains(e));
862 if (isList) {
863 ListIterator it = asList.listIterator(asList.size());
864 check(it.previous() == e);
865 check(asList.get(asList.size() - 1) == e);
866 check(asList.indexOf(e) == asList.size() - 1);
867 check(asList.lastIndexOf(e) == asList.size() - 1);
868 int size = asList.size();
869 check(asList.subList(size - 1, size).equals(singleton));
870 }
871 switch (rnd.nextInt(isList ? 8 : 6)) {
872 case 0: check(deq.pollLast() == e); break;
873 case 1: check(deq.removeLast() == e); break;
874 case 2: check(deq.removeFirstOccurrence(e)); break;
875 case 3: check(deq.removeLastOccurrence(e)); break;
876 case 4: check(deq.remove(e)); break;
877 case 5: check(deq.removeAll(singleton)); break;
878 case 6: asList.remove(asList.size() - 1); break;
879 case 7:
880 ListIterator it = asList.listIterator(asList.size());
881 it.previous();
882 it.remove();
883 break;
884 default: throw new AssertionError();
885 }
886 if (isEmpty) {
887 check(deq.peekLast() == null);
888 THROWS(NoSuchElementException.class, () -> deq.getLast());
889 } else {
890 check(deq.peekLast() != e);
891 check(deq.getLast() != e);
892 }
893 check(!deq.contains(e));
894 equal(new ArrayList<Integer>(deq), originalContents);
895
896 // Test operations on empty deque
897 switch (rnd.nextInt(isList ? 4 : 2)) {
898 case 0: deq.clear(); break;
899 case 1:
900 Iterator it = deq.iterator();
901 while (it.hasNext()) {
902 it.next();
903 it.remove();
904 }
905 break;
906 case 2: asList.subList(0, asList.size()).clear(); break;
907 case 3:
908 ListIterator lit = asList.listIterator(asList.size());
909 while (lit.hasPrevious()) {
910 lit.previous();
911 lit.remove();
912 }
913 break;
914 default: throw new AssertionError();
915 }
916 testEmptyCollection(deq);
917 check(!deq.iterator().hasNext());
918 if (isList) {
919 check(!asList.listIterator().hasPrevious());
920 THROWS(NoSuchElementException.class,
921 () -> asList.listIterator().previous());
922 }
923 THROWS(NoSuchElementException.class,
924 () -> deq.iterator().next(),
925 () -> deq.element(),
926 () -> deq.getFirst(),
927 () -> deq.getLast(),
928 () -> deq.pop(),
929 () -> deq.remove(),
930 () -> deq.removeFirst(),
931 () -> deq.removeLast());
932
933 check(deq.poll() == null);
934 check(deq.pollFirst() == null);
935 check(deq.pollLast() == null);
936 check(deq.peek() == null);
937 check(deq.peekFirst() == null);
938 check(deq.peekLast() == null);
939 check(!deq.removeFirstOccurrence(e));
940 check(!deq.removeLastOccurrence(e));
941
942 check(deq.addAll(originalContents) == !isEmpty);
943 equal(new ArrayList<Integer>(deq), originalContents);
944 check(!deq.addAll(Collections.<Integer>emptyList()));
945 equal(new ArrayList<Integer>(deq), originalContents);
946 }
947 }
948
949 private static void testQueueIteratorRemove(Queue<Integer> q) {
950 System.err.printf("testQueueIteratorRemove %s%n",
951 q.getClass().getSimpleName());
952 q.clear();
953 for (int i = 0; i < 5; i++)
954 q.add(i);
955 Iterator<Integer> it = q.iterator();
956 check(it.hasNext());
957 for (int i = 3; i >= 0; i--)
958 q.remove(i);
959 equal(it.next(), 0);
960 equal(it.next(), 4);
961
962 q.clear();
963 for (int i = 0; i < 5; i++)
964 q.add(i);
965 it = q.iterator();
966 equal(it.next(), 0);
967 check(it.hasNext());
968 for (int i = 1; i < 4; i++)
969 q.remove(i);
970 equal(it.next(), 1);
971 equal(it.next(), 4);
972 }
973
974 private static void testList(final List<Integer> l) {
975 //----------------------------------------------------------------
976 // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
977 // doesn't throw IndexOutOfBoundsException
978 //----------------------------------------------------------------
979 try {
980 l.addAll(-1, Collections.<Integer>emptyList());
981 fail("Expected IndexOutOfBoundsException not thrown");
982 }
983 catch (UnsupportedOperationException ignored) {/* OK */}
984 catch (IndexOutOfBoundsException ignored) {/* OK */}
985 catch (Throwable t) { unexpected(t); }
986
987 // equal(l instanceof Serializable,
988 // l.subList(0,0) instanceof Serializable);
989 if (l.subList(0,0) instanceof Serializable)
990 check(l instanceof Serializable);
991
992 equal(l instanceof RandomAccess,
993 l.subList(0,0) instanceof RandomAccess);
994
995 l.iterator();
996 l.listIterator();
997 l.listIterator(0);
998 l.listIterator(l.size());
999 THROWS(IndexOutOfBoundsException.class,
1000 () -> l.listIterator(-1),
1001 () -> l.listIterator(l.size() + 1));
1002
1003 if (l instanceof AbstractList) {
1004 try {
1005 int size = l.size();
1006 AbstractList<Integer> abList = (AbstractList<Integer>) l;
1007 Method m = AbstractList.class.getDeclaredMethod("removeRange", new Class[] { int.class, int.class });
1008 m.setAccessible(true);
1009 m.invoke(abList, new Object[] { 0, 0 });
1010 m.invoke(abList, new Object[] { size, size });
1011 equal(size, l.size());
1012 }
1013 catch (UnsupportedOperationException ignored) {/* OK */}
1014 catch (Throwable t) { unexpected(t); }
1015 }
1016 }
1017
1018 private static void testCollection(Collection<Integer> c) {
1019 try { testCollection1(c); }
1020 catch (Throwable t) { unexpected(t); }
1021 }
1022
1023 private static void testCollection1(Collection<Integer> c) {
1024
1025 System.out.println("\n==> " + c.getClass().getName());
1026
1027 checkFunctionalInvariants(c);
1028
1029 if (! supportsAdd(c)) return;
1030 //System.out.println("add() supported");
1031
1032 if (c instanceof NavigableSet) {
1033 System.out.println("NavigableSet tests...");
1034
1035 NavigableSet<Integer> ns = (NavigableSet<Integer>)c;
1036 testNavigableSet(ns);
1037 testNavigableSet(ns.headSet(6, false));
1038 testNavigableSet(ns.headSet(5, true));
1039 testNavigableSet(ns.tailSet(0, false));
1040 testNavigableSet(ns.tailSet(1, true));
1041 testNavigableSet(ns.subSet(0, false, 5, true));
1042 testNavigableSet(ns.subSet(1, true, 6, false));
1043 }
1044
1045 if (c instanceof Queue)
1046 testQueue((Queue<Integer>)c);
1047
1048 if (c instanceof List)
1049 testList((List<Integer>)c);
1050
1051 check(supportsRemove(c));
1052
1053 try {
1054 oneElement(c);
1055 checkFunctionalInvariants(c);
1056 }
1057 catch (Throwable t) { unexpected(t); }
1058
1059 clear(c); testNullElement(c);
1060 oneElement(c); testNullElement(c);
1061
1062 clear(c); testStringElement(c);
1063 oneElement(c); testStringElement(c);
1064
1065 if (c.getClass().getName().matches(".*concurrent.*"))
1066 testConcurrentCollection(c);
1067
1068 //----------------------------------------------------------------
1069 // The "all" operations should throw NPE when passed null
1070 //----------------------------------------------------------------
1071 {
1072 clear(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 oneElement(c);
1081 try {
1082 c.removeAll(null);
1083 fail("Expected NullPointerException");
1084 }
1085 catch (NullPointerException e) { pass(); }
1086 catch (Throwable t) { unexpected(t); }
1087
1088 clear(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.retainAll(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.addAll(null);
1107 fail("Expected NullPointerException");
1108 }
1109 catch (NullPointerException e) { pass(); }
1110 catch (Throwable t) { unexpected(t); }
1111
1112 oneElement(c);
1113 try {
1114 c.containsAll(null);
1115 fail("Expected NullPointerException");
1116 }
1117 catch (NullPointerException e) { pass(); }
1118 catch (Throwable t) { unexpected(t); }
1119 }
1120 }
1121
1122 //----------------------------------------------------------------
1123 // Map
1124 //----------------------------------------------------------------
1125 private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
1126 check(m.keySet().size() == m.entrySet().size());
1127 check(m.keySet().size() == m.size());
1128 checkFunctionalInvariants(m.keySet());
1129 checkFunctionalInvariants(m.values());
1130 check(m.size() != 0 ^ m.isEmpty());
1131 check(! m.containsKey(ABSENT_VALUE));
1132
1133 if (m instanceof Serializable) {
1134 //System.out.printf("Serializing %s%n", m.getClass().getName());
1135 try {
1136 Object clone = serialClone(m);
1137 equal(m instanceof Serializable,
1138 clone instanceof Serializable);
1139 equal(m, clone);
1140 } catch (Error xxx) {
1141 if (! (xxx.getCause() instanceof NotSerializableException))
1142 throw xxx;
1143 }
1144 }
1145 }
1146
1147 private static void testMap(Map<Integer,Integer> m) {
1148 System.out.println("\n==> " + m.getClass().getName());
1149
1150 if (m instanceof ConcurrentMap)
1151 testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
1152
1153 if (m instanceof NavigableMap) {
1154 System.out.println("NavigableMap tests...");
1155
1156 NavigableMap<Integer,Integer> nm =
1157 (NavigableMap<Integer,Integer>) m;
1158 testNavigableMapRemovers(nm);
1159 testNavigableMap(nm);
1160 testNavigableMap(nm.headMap(6, false));
1161 testNavigableMap(nm.headMap(5, true));
1162 testNavigableMap(nm.tailMap(0, false));
1163 testNavigableMap(nm.tailMap(1, true));
1164 testNavigableMap(nm.subMap(1, true, 6, false));
1165 testNavigableMap(nm.subMap(0, false, 5, true));
1166 }
1167
1168 checkFunctionalInvariants(m);
1169
1170 if (supportsClear(m)) {
1171 try { clear(m); }
1172 catch (Throwable t) { unexpected(t); }
1173 }
1174
1175 if (supportsPut(m)) {
1176 try {
1177 check(m.put(3333, 77777) == null);
1178 check(m.put(9134, 74982) == null);
1179 check(m.get(9134) == 74982);
1180 check(m.put(9134, 1382) == 74982);
1181 check(m.get(9134) == 1382);
1182 check(m.size() == 2);
1183 checkFunctionalInvariants(m);
1184 checkNPEConsistency(m);
1185 }
1186 catch (Throwable t) { unexpected(t); }
1187 }
1188 }
1189
1190 private static boolean supportsPut(Map<Integer,Integer> m) {
1191 // We're asking for .equals(...) semantics
1192 if (m instanceof IdentityHashMap) return false;
1193
1194 try { check(m.put(ABSENT_VALUE,12735) == null); }
1195 catch (UnsupportedOperationException t) { return false; }
1196 catch (Throwable t) { unexpected(t); }
1197
1198 try {
1199 check(m.containsKey(ABSENT_VALUE));
1200 check(m.remove(ABSENT_VALUE) != null);
1201 } catch (Throwable t) { unexpected(t); }
1202 return true;
1203 }
1204
1205 private static boolean supportsClear(Map<?,?> m) {
1206 try { m.clear(); }
1207 catch (UnsupportedOperationException t) { return false; }
1208 catch (Throwable t) { unexpected(t); }
1209 return true;
1210 }
1211
1212 //----------------------------------------------------------------
1213 // ConcurrentMap
1214 //----------------------------------------------------------------
1215 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
1216 System.out.println("ConcurrentMap tests...");
1217
1218 try {
1219 clear(m);
1220
1221 check(m.putIfAbsent(18357,7346) == null);
1222 check(m.containsKey(18357));
1223 check(m.putIfAbsent(18357,8263) == 7346);
1224 try { m.putIfAbsent(18357,null); fail("NPE"); }
1225 catch (NullPointerException t) { }
1226 check(m.containsKey(18357));
1227
1228 check(! m.replace(18357,8888,7777));
1229 check(m.containsKey(18357));
1230 try { m.replace(18357,null,7777); fail("NPE"); }
1231 catch (NullPointerException t) { }
1232 check(m.containsKey(18357));
1233 check(m.get(18357) == 7346);
1234 check(m.replace(18357,7346,5555));
1235 check(m.replace(18357,5555,7346));
1236 check(m.get(18357) == 7346);
1237
1238 check(m.replace(92347,7834) == null);
1239 try { m.replace(18357,null); fail("NPE"); }
1240 catch (NullPointerException t) { }
1241 check(m.replace(18357,7346) == 7346);
1242 check(m.replace(18357,5555) == 7346);
1243 check(m.get(18357) == 5555);
1244 check(m.replace(18357,7346) == 5555);
1245 check(m.get(18357) == 7346);
1246
1247 check(! m.remove(18357,9999));
1248 check(m.get(18357) == 7346);
1249 check(m.containsKey(18357));
1250 check(! m.remove(18357,null)); // 6272521
1251 check(m.get(18357) == 7346);
1252 check(m.remove(18357,7346));
1253 check(m.get(18357) == null);
1254 check(! m.containsKey(18357));
1255 check(m.isEmpty());
1256
1257 m.putIfAbsent(1,2);
1258 check(m.size() == 1);
1259 check(! m.remove(1,null));
1260 check(! m.remove(1,null));
1261 check(! m.remove(1,1));
1262 check(m.remove(1,2));
1263 check(m.isEmpty());
1264
1265 testEmptyMap(m);
1266 }
1267 catch (Throwable t) { unexpected(t); }
1268 }
1269
1270 private static void throwsConsistently(Class<? extends Throwable> k,
1271 Iterable<Fun> fs) {
1272 List<Class<? extends Throwable>> threw = new ArrayList<>();
1273 for (Fun f : fs)
1274 try { f.f(); threw.add(null); }
1275 catch (Throwable t) {
1276 check(k.isAssignableFrom(t.getClass()));
1277 threw.add(t.getClass());
1278 }
1279 if (new HashSet<Object>(threw).size() != 1)
1280 fail(threw.toString());
1281 }
1282
1283 private static <T> void checkNPEConsistency(final Map<T,Integer> m) {
1284 m.clear();
1285 final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap)
1286 ? (ConcurrentMap<T,Integer>) m
1287 : null;
1288 List<Fun> fs = new ArrayList<>();
1289 fs.add(() -> check(! m.containsKey(null)));
1290 fs.add(() -> equal(m.remove(null), null));
1291 fs.add(() -> equal(m.get(null), null));
1292 if (cm != null)
1293 fs.add(() -> check(! cm.remove(null,null)));
1294 throwsConsistently(NullPointerException.class, fs);
1295
1296 fs.clear();
1297 final Map<T,Integer> sm = singletonMap(null,1);
1298 fs.add(() -> { equal(m.put(null,1), null); m.clear();});
1299 fs.add(() -> { m.putAll(sm); m.clear();});
1300 if (cm != null) {
1301 fs.add(() -> check(! cm.remove(null,null)));
1302 fs.add(() -> equal(cm.putIfAbsent(null,1), 1));
1303 fs.add(() -> equal(cm.replace(null,1), null));
1304 fs.add(() -> equal(cm.replace(null,1, 1), 1));
1305 }
1306 throwsConsistently(NullPointerException.class, fs);
1307 }
1308
1309 //----------------------------------------------------------------
1310 // NavigableMap
1311 //----------------------------------------------------------------
1312 private static void
1313 checkNavigableMapKeys(NavigableMap<Integer,Integer> m,
1314 Integer i,
1315 Integer lower,
1316 Integer floor,
1317 Integer ceiling,
1318 Integer higher) {
1319 equal(m.lowerKey(i), lower);
1320 equal(m.floorKey(i), floor);
1321 equal(m.ceilingKey(i), ceiling);
1322 equal(m.higherKey(i), higher);
1323 }
1324
1325 private static void
1326 checkNavigableSetKeys(NavigableSet<Integer> m,
1327 Integer i,
1328 Integer lower,
1329 Integer floor,
1330 Integer ceiling,
1331 Integer higher) {
1332 equal(m.lower(i), lower);
1333 equal(m.floor(i), floor);
1334 equal(m.ceiling(i), ceiling);
1335 equal(m.higher(i), higher);
1336 }
1337
1338 static final Random rnd = new Random();
1339 static void equalNext(final Iterator<?> it, Object expected) {
1340 if (rnd.nextBoolean())
1341 check(it.hasNext());
1342 equal(it.next(), expected);
1343 }
1344
1345 static void equalMaps(Map m1, Map m2) {
1346 equal(m1, m2);
1347 equal(m2, m1);
1348 equal(m1.size(), m2.size());
1349 equal(m1.isEmpty(), m2.isEmpty());
1350 equal(m1.toString(), m2.toString());
1351 check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray()));
1352 }
1353
1354 @SuppressWarnings({"unchecked", "rawtypes"})
1355 static void testNavigableMapRemovers(NavigableMap m)
1356 {
1357 final Map emptyMap = new HashMap();
1358
1359 final Map singletonMap = new HashMap();
1360 singletonMap.put(1, 2);
1361
1362 abstract class NavigableMapView {
1363 abstract NavigableMap view(NavigableMap m);
1364 }
1365
1366 NavigableMapView[] views = {
1367 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1368 return m; }},
1369 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1370 return m.headMap(99, true); }},
1371 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1372 return m.tailMap(-99, false); }},
1373 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1374 return m.subMap(-99, true, 99, false); }},
1375 };
1376
1377 abstract class Remover {
1378 abstract void remove(NavigableMap m, Object k, Object v);
1379 }
1380
1381 Remover[] removers = {
1382 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1383 equal(m.remove(k), v); }},
1384
1385 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1386 equal(m.descendingMap().remove(k), v); }},
1387 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1388 equal(m.descendingMap().headMap(-86, false).remove(k), v); }},
1389 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1390 equal(m.descendingMap().tailMap(86, true).remove(k), v); }},
1391
1392 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1393 equal(m.headMap(86, true).remove(k), v); }},
1394 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1395 equal(m.tailMap(-86, true).remove(k), v); }},
1396 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1397 equal(m.subMap(-86, false, 86, true).remove(k), v); }},
1398
1399 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1400 check(m.keySet().remove(k)); }},
1401 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1402 check(m.navigableKeySet().remove(k)); }},
1403
1404 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1405 check(m.navigableKeySet().headSet(86, true).remove(k)); }},
1406 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1407 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }},
1408 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1409 check(m.navigableKeySet().subSet(-86, true, 86, false)
1410 .remove(k)); }},
1411
1412 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1413 check(m.descendingKeySet().headSet(-86, false).remove(k)); }},
1414 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1415 check(m.descendingKeySet().tailSet(86, true).remove(k)); }},
1416 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1417 check(m.descendingKeySet().subSet(86, true, -86, false)
1418 .remove(k)); }},
1419 };
1420
1421 for (NavigableMapView view : views) {
1422 for (Remover remover : removers) {
1423 try {
1424 m.clear();
1425 equalMaps(m, emptyMap);
1426 equal(m.put(1, 2), null);
1427 equalMaps(m, singletonMap);
1428 NavigableMap v = view.view(m);
1429 remover.remove(v, 1, 2);
1430 equalMaps(m, emptyMap);
1431 } catch (Throwable t) { unexpected(t); }
1432 }
1433 }
1434 }
1435
1436 private static void testNavigableMap(NavigableMap<Integer,Integer> m)
1437 {
1438 clear(m);
1439 checkNavigableMapKeys(m, 1, null, null, null, null);
1440
1441 equal(m.put(1, 2), null);
1442 equal(m.put(3, 4), null);
1443 equal(m.put(5, 9), null);
1444
1445 equal(m.put(1, 2), 2);
1446 equal(m.put(3, 4), 4);
1447 equal(m.put(5, 6), 9);
1448
1449 checkNavigableMapKeys(m, 0, null, null, 1, 1);
1450 checkNavigableMapKeys(m, 1, null, 1, 1, 3);
1451 checkNavigableMapKeys(m, 2, 1, 1, 3, 3);
1452 checkNavigableMapKeys(m, 3, 1, 3, 3, 5);
1453 checkNavigableMapKeys(m, 5, 3, 5, 5, null);
1454 checkNavigableMapKeys(m, 6, 5, 5, null, null);
1455
1456 for (final Iterator<Integer> it :
1457 (Iterator<Integer>[])
1458 new Iterator<?>[] {
1459 m.descendingKeySet().iterator(),
1460 m.navigableKeySet().descendingIterator()}) {
1461 equalNext(it, 5);
1462 equalNext(it, 3);
1463 equalNext(it, 1);
1464 check(! it.hasNext());
1465 THROWS(NoSuchElementException.class, () -> it.next());
1466 }
1467
1468 {
1469 final Iterator<Map.Entry<Integer,Integer>> it
1470 = m.descendingMap().entrySet().iterator();
1471 check(it.hasNext()); equal(it.next().getKey(), 5);
1472 check(it.hasNext()); equal(it.next().getKey(), 3);
1473 check(it.hasNext()); equal(it.next().getKey(), 1);
1474 check(! it.hasNext());
1475 THROWS(NoSuchElementException.class, () -> it.next());
1476 }
1477
1478 prepMapForDescItrTests(m);
1479 checkDescItrRmFirst(m.keySet(), m.navigableKeySet().descendingIterator());
1480 prepMapForDescItrTests(m);
1481 checkDescItrRmMid(m.keySet(), m.navigableKeySet().descendingIterator());
1482 prepMapForDescItrTests(m);
1483 checkDescItrRmLast(m.keySet(), m.navigableKeySet().descendingIterator());
1484
1485 prepMapForDescItrTests(m);
1486 checkDescItrRmFirst(m.keySet(), m.descendingMap().keySet().iterator());
1487 prepMapForDescItrTests(m);
1488 checkDescItrRmMid(m.keySet(), m.descendingMap().keySet().iterator());
1489 prepMapForDescItrTests(m);
1490 checkDescItrRmLast(m.keySet(), m.descendingMap().keySet().iterator());
1491
1492 prepMapForDescItrTests(m);
1493 checkDescItrRmFirst(m.keySet(), m.descendingKeySet().iterator());
1494 prepMapForDescItrTests(m);
1495 checkDescItrRmMid(m.keySet(), m.descendingKeySet().iterator());
1496 prepMapForDescItrTests(m);
1497 checkDescItrRmLast(m.keySet(), m.descendingKeySet().iterator());
1498
1499 prepMapForDescItrTests(m);
1500 checkDescItrRmFirst(m.values(), m.descendingMap().values().iterator());
1501 prepMapForDescItrTests(m);
1502 checkDescItrRmMid(m.values(), m.descendingMap().values().iterator());
1503 prepMapForDescItrTests(m);
1504 checkDescItrRmLast(m.values(), m.descendingMap().values().iterator());
1505
1506 prepMapForDescItrTests(m);
1507 checkDescItrRmFirst((Collection)m.entrySet(),
1508 m.descendingMap().entrySet().iterator());
1509 prepMapForDescItrTests(m);
1510 checkDescItrRmMid((Collection)m.entrySet(),
1511 m.descendingMap().entrySet().iterator());
1512 prepMapForDescItrTests(m);
1513 checkDescItrRmLast((Collection)m.entrySet(),
1514 m.descendingMap().entrySet().iterator());
1515 }
1516
1517 private static void testNavigableSet(NavigableSet<Integer> s) {
1518 clear(s);
1519 checkNavigableSetKeys(s, 1, null, null, null, null);
1520
1521 check(s.add(1));
1522 check(s.add(3));
1523 check(s.add(5));
1524
1525 check(! s.add(1));
1526 check(! s.add(3));
1527 check(! s.add(5));
1528
1529 checkNavigableSetKeys(s, 0, null, null, 1, 1);
1530 checkNavigableSetKeys(s, 1, null, 1, 1, 3);
1531 checkNavigableSetKeys(s, 2, 1, 1, 3, 3);
1532 checkNavigableSetKeys(s, 3, 1, 3, 3, 5);
1533 checkNavigableSetKeys(s, 5, 3, 5, 5, null);
1534 checkNavigableSetKeys(s, 6, 5, 5, null, null);
1535
1536 for (final Iterator<Integer> it :
1537 (Iterator<Integer>[])
1538 new Iterator<?>[] {
1539 s.descendingIterator(),
1540 s.descendingSet().iterator()}) {
1541 equalNext(it, 5);
1542 equalNext(it, 3);
1543 equalNext(it, 1);
1544 check(! it.hasNext());
1545 THROWS(NoSuchElementException.class, () -> it.next());
1546 }
1547
1548 prepSetForDescItrTests(s);
1549 checkDescItrRmFirst(s, s.descendingIterator());
1550 prepSetForDescItrTests(s);
1551 checkDescItrRmMid(s, s.descendingIterator());
1552 prepSetForDescItrTests(s);
1553 checkDescItrRmLast(s, s.descendingIterator());
1554
1555 prepSetForDescItrTests(s);
1556 checkDescItrRmFirst(s, s.descendingSet().iterator());
1557 prepSetForDescItrTests(s);
1558 checkDescItrRmMid(s, s.descendingSet().iterator());
1559 prepSetForDescItrTests(s);
1560 checkDescItrRmLast(s, s.descendingSet().iterator());
1561 }
1562
1563 private static void prepSetForDescItrTests(Set s) {
1564 clear(s);
1565 check(s.add(1));
1566 check(s.add(3));
1567 check(s.add(5));
1568 }
1569
1570 private static void prepMapForDescItrTests(Map m) {
1571 clear(m);
1572 equal(m.put(1, 2), null);
1573 equal(m.put(3, 4), null);
1574 equal(m.put(5, 9), null);
1575 }
1576
1577 //--------------------------------------------------------------------
1578 // Check behavior of descending iterator when first element is removed
1579 //--------------------------------------------------------------------
1580 private static <T> void checkDescItrRmFirst(Collection<T> ascColl,
1581 Iterator<T> descItr) {
1582 T[] expected = (T[]) ascColl.toArray();
1583 int idx = expected.length -1;
1584
1585 equalNext(descItr, expected[idx--]);
1586 descItr.remove();
1587 while (idx >= 0 && descItr.hasNext()) {
1588 equalNext(descItr, expected[idx--]);
1589 }
1590 equal(descItr.hasNext(), false);
1591 equal(idx, -1);
1592 }
1593
1594 //-----------------------------------------------------------------------
1595 // Check behavior of descending iterator when a middle element is removed
1596 //-----------------------------------------------------------------------
1597 private static <T> void checkDescItrRmMid(Collection<T> ascColl,
1598 Iterator<T> descItr) {
1599 T[] expected = (T[]) ascColl.toArray();
1600 int idx = expected.length -1;
1601
1602 while (idx >= expected.length / 2) {
1603 equalNext(descItr, expected[idx--]);
1604 }
1605 descItr.remove();
1606 while (idx >= 0 && descItr.hasNext()) {
1607 equalNext(descItr, expected[idx--]);
1608 }
1609 equal(descItr.hasNext(), false);
1610 equal(idx, -1);
1611 }
1612
1613 //-----------------------------------------------------------------------
1614 // Check behavior of descending iterator when the last element is removed
1615 //-----------------------------------------------------------------------
1616 private static <T> void checkDescItrRmLast(Collection<T> ascColl,
1617 Iterator<T> descItr) {
1618 T[] expected = (T[]) ascColl.toArray();
1619 int idx = expected.length -1;
1620
1621 while (idx >= 0 && descItr.hasNext()) {
1622 equalNext(descItr, expected[idx--]);
1623 }
1624 equal(idx, -1);
1625 equal(descItr.hasNext(), false);
1626 descItr.remove();
1627 equal(ascColl.contains(expected[0]), false);
1628 }
1629
1630 //--------------------- Infrastructure ---------------------------
1631 static volatile int passed = 0, failed = 0;
1632 static void pass() { passed++; }
1633 static void fail() { failed++; Thread.dumpStack(); }
1634 static void fail(String msg) { System.out.println(msg); fail(); }
1635 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
1636 static void check(boolean cond) { if (cond) pass(); else fail(); }
1637 static void equal(Object x, Object y) {
1638 if (x == null ? y == null : x.equals(y)) pass();
1639 else {System.out.println(x + " not equal to " + y); fail();}}
1640 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
1641 public static void main(String[] args) throws Throwable {
1642 try { realMain(args); } catch (Throwable t) { unexpected(t); }
1643
1644 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
1645 if (failed > 0) throw new Exception("Some tests failed");
1646 }
1647 interface Fun {void f() throws Throwable;}
1648 private static void THROWS(Class<? extends Throwable> k, Fun... fs) {
1649 for (Fun f : fs)
1650 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
1651 catch (Throwable t) {
1652 if (k.isAssignableFrom(t.getClass())) pass();
1653 else unexpected(t);}}
1654 static byte[] serializedForm(Object obj) {
1655 try {
1656 ByteArrayOutputStream baos = new ByteArrayOutputStream();
1657 new ObjectOutputStream(baos).writeObject(obj);
1658 return baos.toByteArray();
1659 } catch (IOException e) { throw new Error(e); }}
1660 static Object readObject(byte[] bytes)
1661 throws IOException, ClassNotFoundException {
1662 InputStream is = new ByteArrayInputStream(bytes);
1663 return new ObjectInputStream(is).readObject();}
1664 @SuppressWarnings("unchecked")
1665 static <T> T serialClone(T obj) {
1666 try { return (T) readObject(serializedForm(obj)); }
1667 catch (Exception e) { throw new Error(e); }}
1668 private static class NewAbstractCollection<E> extends AbstractCollection<E> {
1669 ArrayList<E> list = new ArrayList<>();
1670 public boolean remove(Object obj) {
1671 return list.remove(obj);
1672 }
1673 public boolean add(E e) {
1674 return list.add(e);
1675 }
1676 public Iterator<E> iterator() {
1677 return list.iterator();
1678 }
1679 public int size() {
1680 return list.size();
1681 }
1682 }
1683 private static class NewAbstractSet<E> extends AbstractSet<E> {
1684 HashSet<E> set = new HashSet<>();
1685 public boolean remove(Object obj) {
1686 return set.remove(obj);
1687 }
1688 public boolean add(E e) {
1689 return set.add(e);
1690 }
1691 public Iterator<E> iterator() {
1692 return set.iterator();
1693 }
1694 public int size() {
1695 return set.size();
1696 }
1697 }
1698
1699 }