1 /*
2 * Copyright (c) 2005, 2011, 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
30 * @summary Run many tests on many Collection and Map implementations
31 * @author Martin Buchholz
32 * @run main MOAT
33 * @run main/othervm -XX:+AggressiveOpts MOAT
34 */
35
36 /* Mother Of All (Collection) Tests
37 *
38 * Testing of collection classes is often spotty, because many tests
39 * need to be performed on many implementations, but the onus on
40 * writing the tests falls on the engineer introducing the new
41 * implementation.
42 *
43 * The idea of this mega-test is that:
44 *
45 * An engineer adding a new collection implementation could simply add
46 * their new implementation to a list of implementations in this
47 * test's main method. Any general purpose Collection<Integer> or
48 * Map<Integer,Integer> class is appropriate.
49 *
50 * An engineer fixing a regression could add their regression test here and
51 * simultaneously test all other implementations.
52 */
53
54 import java.io.*;
55 import java.util.*;
56 import java.util.concurrent.*;
57 import static java.util.Collections.*;
58
59 public class MOAT {
60 public static void realMain(String[] args) {
61
62 testCollection(new NewAbstractCollection<Integer>());
63 testCollection(new NewAbstractSet<Integer>());
64 testCollection(new LinkedHashSet<Integer>());
65 testCollection(new HashSet<Integer>());
66 testCollection(new Vector<Integer>());
67 testCollection(new Vector<Integer>().subList(0,0));
68 testCollection(new ArrayDeque<Integer>());
69 testCollection(new ArrayList<Integer>());
70 testCollection(new ArrayList<Integer>().subList(0,0));
71 testCollection(new LinkedList<Integer>());
72 testCollection(new LinkedList<Integer>().subList(0,0));
73 testCollection(new TreeSet<Integer>());
74
75 testCollection(new CopyOnWriteArrayList<Integer>());
76 testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0));
77 testCollection(new CopyOnWriteArraySet<Integer>());
78 testCollection(new PriorityQueue<Integer>());
79 testCollection(new PriorityBlockingQueue<Integer>());
80 testCollection(new ArrayBlockingQueue<Integer>(20));
81 testCollection(new LinkedBlockingQueue<Integer>(20));
82 testCollection(new LinkedBlockingDeque<Integer>(20));
83 testCollection(new ConcurrentLinkedDeque<Integer>());
84 testCollection(new ConcurrentLinkedQueue<Integer>());
85 testCollection(new LinkedTransferQueue<Integer>());
86 testCollection(new ConcurrentSkipListSet<Integer>());
87 testCollection(Arrays.asList(new Integer(42)));
88 testCollection(Arrays.asList(1,2,3));
89 testCollection(nCopies(25,1));
90 testImmutableList(nCopies(25,1));
91 testImmutableList(unmodifiableList(Arrays.asList(1,2,3)));
92
93 testMap(new HashMap<Integer,Integer>());
94 testMap(new LinkedHashMap<Integer,Integer>());
95 testMap(new WeakHashMap<Integer,Integer>());
96 testMap(new IdentityHashMap<Integer,Integer>());
97 testMap(new TreeMap<Integer,Integer>());
98 testMap(new Hashtable<Integer,Integer>());
99 testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f));
100 testMap(new ConcurrentSkipListMap<Integer,Integer>());
101
102 // Empty collections
103 final List<Integer> emptyArray = Arrays.asList(new Integer[]{});
104 testCollection(emptyArray);
105 testEmptyList(emptyArray);
106 THROWS(IndexOutOfBoundsException.class,
107 new Fun(){void f(){ emptyArray.set(0,1); }});
108 THROWS(UnsupportedOperationException.class,
109 new Fun(){void f(){ emptyArray.add(0,1); }});
110
111 List<Integer> noOne = nCopies(0,1);
112 testCollection(noOne);
113 testEmptyList(noOne);
114 testImmutableList(noOne);
115
116 Set<Integer> emptySet = emptySet();
117 testCollection(emptySet);
118 testEmptySet(emptySet);
119 testEmptySet(EMPTY_SET);
120 testImmutableSet(emptySet);
121
122 List<Integer> emptyList = emptyList();
123 testCollection(emptyList);
124 testEmptyList(emptyList);
125 testEmptyList(EMPTY_LIST);
126 testImmutableList(emptyList);
127
128 Map<Integer,Integer> emptyMap = emptyMap();
129 testMap(emptyMap);
130 testEmptyMap(emptyMap);
131 testEmptyMap(EMPTY_MAP);
132 testImmutableMap(emptyMap);
133
134 // Singleton collections
135 Set<Integer> singletonSet = singleton(1);
136 equal(singletonSet.size(), 1);
137 testCollection(singletonSet);
138 testImmutableSet(singletonSet);
139
140 List<Integer> singletonList = singletonList(1);
141 equal(singletonList.size(), 1);
142 testCollection(singletonList);
143 testImmutableList(singletonList);
144 testImmutableList(singletonList.subList(0,1));
145 testImmutableList(singletonList.subList(0,1).subList(0,1));
146 testEmptyList(singletonList.subList(0,0));
147 testEmptyList(singletonList.subList(0,0).subList(0,0));
148
149 Map<Integer,Integer> singletonMap = singletonMap(1,2);
150 equal(singletonMap.size(), 1);
151 testMap(singletonMap);
152 testImmutableMap(singletonMap);
153 }
154
155 private static void checkContainsSelf(Collection<Integer> c) {
156 check(c.containsAll(c));
157 check(c.containsAll(Arrays.asList(c.toArray())));
158 check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));
159 }
160
161 private static void checkContainsEmpty(Collection<Integer> c) {
162 check(c.containsAll(new ArrayList<Integer>()));
163 }
164
165 private static <T> void testEmptyCollection(Collection<T> c) {
166 check(c.isEmpty());
167 equal(c.size(), 0);
168 equal(c.toString(),"[]");
169 equal(c.toArray().length, 0);
170 equal(c.toArray(new Object[0]).length, 0);
171 check(c.toArray(new Object[]{42})[0] == null);
172
173 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
174 equal(c.toArray(a), a);
175 equal(a[0], null);
176 testEmptyIterator(c.iterator());
177 }
178
179 static <T> void testEmptyIterator(final Iterator<T> it) {
180 if (rnd.nextBoolean())
181 check(! it.hasNext());
182
183 THROWS(NoSuchElementException.class,
184 new Fun(){void f(){ it.next(); }});
185
186 try { it.remove(); }
187 catch (IllegalStateException _) { pass(); }
188 catch (UnsupportedOperationException _) { pass(); }
189 catch (Throwable t) { unexpected(t); }
190
191 if (rnd.nextBoolean())
192 check(! it.hasNext());
193 }
194
195 private static void testEmptyList(List<?> c) {
196 testEmptyCollection(c);
197 equal(c.hashCode(), 1);
198 equal2(c, Collections.<Integer>emptyList());
199 }
200
201 private static <T> void testEmptySet(Set<T> c) {
202 testEmptyCollection(c);
203 equal(c.hashCode(), 0);
204 equal2(c, Collections.<Integer>emptySet());
205 if (c instanceof NavigableSet<?>)
206 testEmptyIterator(((NavigableSet<T>)c).descendingIterator());
207 }
208
209 private static void testImmutableCollection(final Collection<Integer> c) {
210 THROWS(UnsupportedOperationException.class,
211 new Fun(){void f(){ c.add(99); }},
212 new Fun(){void f(){ c.addAll(singleton(99)); }});
213 if (! c.isEmpty()) {
214 final Integer first = c.iterator().next();
215 THROWS(UnsupportedOperationException.class,
216 new Fun(){void f(){ c.clear(); }},
217 new Fun(){void f(){ c.remove(first); }},
218 new Fun(){void f(){ c.removeAll(singleton(first)); }},
219 new Fun(){void f(){ c.retainAll(emptyList()); }}
220 );
221 }
222 }
223
224 private static void testImmutableSet(final Set<Integer> c) {
225 testImmutableCollection(c);
226 }
227
228 private static void testImmutableList(final List<Integer> c) {
229 testList(c);
230 testImmutableCollection(c);
231 THROWS(UnsupportedOperationException.class,
232 new Fun(){void f(){ c.set(0,42); }},
233 new Fun(){void f(){ c.add(0,42); }},
234 new Fun(){void f(){ c.addAll(0,singleton(86)); }});
235 if (! c.isEmpty())
236 THROWS(UnsupportedOperationException.class,
237 new Fun(){void f(){
238 Iterator<Integer> it = c.iterator();
239 it.next(); it.remove();}},
240 new Fun(){void f(){
241 ListIterator<Integer> it = c.listIterator();
242 it.next(); it.remove();}});
243 }
244
245 private static void clear(Collection<Integer> c) {
246 try { c.clear(); }
247 catch (Throwable t) { unexpected(t); }
248 testEmptyCollection(c);
249 }
250
251 private static <K,V> void testEmptyMap(final Map<K,V> m) {
252 check(m.isEmpty());
253 equal(m.size(), 0);
254 equal(m.toString(),"{}");
255 testEmptySet(m.keySet());
256 testEmptySet(m.entrySet());
257 testEmptyCollection(m.values());
258
259 try { check(! m.containsValue(null)); }
260 catch (NullPointerException _) { /* OK */ }
261 try { check(! m.containsKey(null)); }
262 catch (NullPointerException _) { /* OK */ }
263 check(! m.containsValue(1));
264 check(! m.containsKey(1));
265 }
266
267 private static void testImmutableMap(final Map<Integer,Integer> m) {
268 THROWS(UnsupportedOperationException.class,
269 new Fun(){void f(){ m.put(1,1); }},
270 new Fun(){void f(){ m.putAll(singletonMap(1,1)); }});
271 if (! m.isEmpty()) {
272 final Integer first = m.keySet().iterator().next();
273 THROWS(UnsupportedOperationException.class,
274 new Fun(){void f(){ m.remove(first); }},
275 new Fun(){void f(){ m.clear(); }});
276 final Map.Entry<Integer,Integer> me
277 = m.entrySet().iterator().next();
278 Integer key = me.getKey();
279 Integer val = me.getValue();
280 THROWS(UnsupportedOperationException.class,
281 new Fun(){void f(){ me.setValue(3); }});
282 equal(key, me.getKey());
283 equal(val, me.getValue());
284 }
285 testImmutableSet(m.keySet());
286 testImmutableCollection(m.values());
287 //testImmutableSet(m.entrySet());
288 }
289
290 private static void clear(Map<?,?> m) {
291 try { m.clear(); }
292 catch (Throwable t) { unexpected(t); }
293 testEmptyMap(m);
294 }
295
296 private static void oneElement(Collection<Integer> c) {
297 clear(c);
298 try {
299 check(c.add(-42));
300 equal(c.toString(), "[-42]");
301 if (c instanceof Set) check(! c.add(-42));
302 } catch (Throwable t) { unexpected(t); }
303 check(! c.isEmpty()); check(c.size() == 1);
304 }
305
306 private static boolean supportsAdd(Collection<Integer> c) {
307 try { check(c.add(778347983)); }
308 catch (UnsupportedOperationException t) { return false; }
309 catch (Throwable t) { unexpected(t); }
310
311 try {
312 check(c.contains(778347983));
313 check(c.remove(778347983));
314 } catch (Throwable t) { unexpected(t); }
315 return true;
316 }
317
318 private static boolean supportsRemove(Collection<Integer> c) {
319 try { check(! c.remove(19134032)); }
320 catch (UnsupportedOperationException t) { return false; }
321 catch (Throwable t) { unexpected(t); }
322 return true;
323 }
324
325 private static void checkFunctionalInvariants(Collection<Integer> c) {
326 try {
327 checkContainsSelf(c);
328 checkContainsEmpty(c);
329 check(c.size() != 0 ^ c.isEmpty());
330
331 {
332 int size = 0;
333 for (Integer i : c) size++;
334 check(c.size() == size);
335 }
336
337 check(c.toArray().length == c.size());
338 check(c.toArray().getClass() == Object[].class
339 ||
340 // !!!!
341 // 6260652: (coll) Arrays.asList(x).toArray().getClass()
342 // should be Object[].class
343 (c.getClass().getName().equals("java.util.Arrays$ArrayList"))
344 );
345 for (int size : new int[]{0,1,c.size(), c.size()+1}) {
346 Integer[] a = c.toArray(new Integer[size]);
347 check((size > c.size()) || a.length == c.size());
348 int i = 0; for (Integer j : c) check(a[i++] == j);
349 check((size <= c.size()) || (a[c.size()] == null));
350 check(a.getClass() == Integer[].class);
351 }
352
353 check(c.equals(c));
354 if (c instanceof Serializable) {
355 //System.out.printf("Serializing %s%n", c.getClass().getName());
356 try {
357 Object clone = serialClone(c);
358 equal(c instanceof Serializable,
359 clone instanceof Serializable);
360 equal(c instanceof RandomAccess,
361 clone instanceof RandomAccess);
362 if ((c instanceof List) || (c instanceof Set))
363 equal(c, clone);
364 else
365 equal(new HashSet<Integer>(c),
366 new HashSet<Integer>(serialClone(c)));
367 } catch (Error xxx) {
368 if (! (xxx.getCause() instanceof NotSerializableException))
369 throw xxx;
370 }
371 }
372 }
373 catch (Throwable t) { unexpected(t); }
374 }
375
376 //----------------------------------------------------------------
377 // If add(null) succeeds, contains(null) & remove(null) should succeed
378 //----------------------------------------------------------------
379 private static void testNullElement(Collection<Integer> c) {
380 // !!!! 5018849: (coll) TreeSet.contains(null) does not agree with Javadoc
381 if (c instanceof TreeSet) return;
382
383 try {
384 check(c.add(null));
385 if (c.size() == 1)
386 equal(c.toString(), "[null]");
387 try {
388 checkFunctionalInvariants(c);
389 check(c.contains(null));
390 check(c.remove(null));
391 }
392 catch (Throwable t) { unexpected(t); }
393 }
394 catch (NullPointerException e) { /* OK */ }
395 catch (Throwable t) { unexpected(t); }
396 }
397
398
399 //----------------------------------------------------------------
400 // If add("x") succeeds, contains("x") & remove("x") should succeed
401 //----------------------------------------------------------------
402 @SuppressWarnings("unchecked")
403 private static void testStringElement(Collection<Integer> c) {
404 Collection x = (Collection)c; // Make type-unsafe
405 try {
406 check(x.add("x"));
407 try {
408 check(x.contains("x"));
409 check(x.remove("x"));
410 } catch (Throwable t) { unexpected(t); }
411 }
412 catch (ClassCastException e) { /* OK */ }
413 catch (Throwable t) { unexpected(t); }
414 }
415
416 private static void testConcurrentCollection(Collection<Integer> c) {
417 try {
418 c.add(1);
419 Iterator<Integer> it = c.iterator();
420 check(it.hasNext());
421 clear(c);
422 check(it.next() instanceof Integer); // No CME
423 check(c.isEmpty());
424 }
425 catch (Throwable t) { unexpected(t); }
426 }
427
428 private static void testQueue(Queue<Integer> q) {
429 q.clear();
430 for (int i = 0; i < 5; i++) {
431 testQueueAddRemove(q, null);
432 testQueueAddRemove(q, 537);
433 q.add(i);
434 }
435 equal(q.size(), 5);
436 checkFunctionalInvariants(q);
437 q.poll();
438 equal(q.size(), 4);
439 checkFunctionalInvariants(q);
440 if ((q instanceof LinkedBlockingQueue) ||
441 (q instanceof LinkedBlockingDeque) ||
442 (q instanceof ConcurrentLinkedDeque) ||
443 (q instanceof ConcurrentLinkedQueue)) {
444 testQueueIteratorRemove(q);
445 }
446 }
447
448 private static void testQueueAddRemove(final Queue<Integer> q,
449 final Integer e) {
450 final List<Integer> originalContents = new ArrayList<Integer>(q);
451 final boolean isEmpty = q.isEmpty();
452 final boolean isList = (q instanceof List);
453 final List asList = isList ? (List) q : null;
454 check(!q.contains(e));
455 try {
456 q.add(e);
457 } catch (NullPointerException npe) {
458 check(e == null);
459 return; // Null elements not supported
460 }
461 check(q.contains(e));
462 check(q.remove(e));
463 check(!q.contains(e));
464 equal(new ArrayList<Integer>(q), originalContents);
465
466 if (q instanceof Deque<?>) {
467 final Deque<Integer> deq = (Deque<Integer>) q;
468 final List<Integer> singleton = Collections.singletonList(e);
469
470 // insert, query, remove element at head
471 if (isEmpty) {
472 THROWS(NoSuchElementException.class,
473 new Fun(){void f(){ deq.getFirst(); }},
474 new Fun(){void f(){ deq.element(); }},
475 new Fun(){void f(){ deq.iterator().next(); }});
476 check(deq.peekFirst() == null);
477 check(deq.peek() == null);
478 } else {
479 check(deq.getFirst() != e);
480 check(deq.element() != e);
481 check(deq.iterator().next() != e);
482 check(deq.peekFirst() != e);
483 check(deq.peek() != e);
484 }
485 check(!deq.contains(e));
486 check(!deq.removeFirstOccurrence(e));
487 check(!deq.removeLastOccurrence(e));
488 if (isList) {
489 check(asList.indexOf(e) == -1);
490 check(asList.lastIndexOf(e) == -1);
491 }
492 switch (rnd.nextInt(isList ? 4 : 3)) {
493 case 0: deq.addFirst(e); break;
494 case 1: check(deq.offerFirst(e)); break;
495 case 2: deq.push(e); break;
496 case 3: asList.add(0, e); break;
497 default: throw new AssertionError();
498 }
499 check(deq.peekFirst() == e);
500 check(deq.getFirst() == e);
501 check(deq.element() == e);
502 check(deq.peek() == e);
503 check(deq.iterator().next() == e);
504 check(deq.contains(e));
505 if (isList) {
506 check(asList.get(0) == e);
507 check(asList.indexOf(e) == 0);
508 check(asList.lastIndexOf(e) == 0);
509 check(asList.subList(0, 1).equals(singleton));
510 }
511 switch (rnd.nextInt(isList ? 11 : 9)) {
512 case 0: check(deq.pollFirst() == e); break;
513 case 1: check(deq.removeFirst() == e); break;
514 case 2: check(deq.remove() == e); break;
515 case 3: check(deq.pop() == e); break;
516 case 4: check(deq.removeFirstOccurrence(e)); break;
517 case 5: check(deq.removeLastOccurrence(e)); break;
518 case 6: check(deq.remove(e)); break;
519 case 7: check(deq.removeAll(singleton)); break;
520 case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break;
521 case 9: asList.remove(0); break;
522 case 10: asList.subList(0, 1).clear(); break;
523 default: throw new AssertionError();
524 }
525 if (isEmpty) {
526 THROWS(NoSuchElementException.class,
527 new Fun(){void f(){ deq.getFirst(); }},
528 new Fun(){void f(){ deq.element(); }},
529 new Fun(){void f(){ deq.iterator().next(); }});
530 check(deq.peekFirst() == null);
531 check(deq.peek() == null);
532 } else {
533 check(deq.getFirst() != e);
534 check(deq.element() != e);
535 check(deq.iterator().next() != e);
536 check(deq.peekFirst() != e);
537 check(deq.peek() != e);
538 }
539 check(!deq.contains(e));
540 check(!deq.removeFirstOccurrence(e));
541 check(!deq.removeLastOccurrence(e));
542 if (isList) {
543 check(isEmpty || asList.get(0) != e);
544 check(asList.indexOf(e) == -1);
545 check(asList.lastIndexOf(e) == -1);
546 }
547 equal(new ArrayList<Integer>(deq), originalContents);
548
549 // insert, query, remove element at tail
550 if (isEmpty) {
551 check(deq.peekLast() == null);
552 THROWS(NoSuchElementException.class,
553 new Fun(){void f(){ deq.getLast(); }});
554 } else {
555 check(deq.peekLast() != e);
556 check(deq.getLast() != e);
557 }
558 switch (rnd.nextInt(isList ? 6 : 4)) {
559 case 0: deq.addLast(e); break;
560 case 1: check(deq.offerLast(e)); break;
561 case 2: check(deq.add(e)); break;
562 case 3: deq.addAll(singleton); break;
563 case 4: asList.addAll(deq.size(), singleton); break;
564 case 5: asList.add(deq.size(), e); break;
565 default: throw new AssertionError();
566 }
567 check(deq.peekLast() == e);
568 check(deq.getLast() == e);
569 check(deq.contains(e));
570 if (isList) {
571 ListIterator it = asList.listIterator(asList.size());
572 check(it.previous() == e);
573 check(asList.get(asList.size() - 1) == e);
574 check(asList.indexOf(e) == asList.size() - 1);
575 check(asList.lastIndexOf(e) == asList.size() - 1);
576 int size = asList.size();
577 check(asList.subList(size - 1, size).equals(singleton));
578 }
579 switch (rnd.nextInt(isList ? 8 : 6)) {
580 case 0: check(deq.pollLast() == e); break;
581 case 1: check(deq.removeLast() == e); break;
582 case 2: check(deq.removeFirstOccurrence(e)); break;
583 case 3: check(deq.removeLastOccurrence(e)); break;
584 case 4: check(deq.remove(e)); break;
585 case 5: check(deq.removeAll(singleton)); break;
586 case 6: asList.remove(asList.size() - 1); break;
587 case 7:
588 ListIterator it = asList.listIterator(asList.size());
589 it.previous();
590 it.remove();
591 break;
592 default: throw new AssertionError();
593 }
594 if (isEmpty) {
595 check(deq.peekLast() == null);
596 THROWS(NoSuchElementException.class,
597 new Fun(){void f(){ deq.getLast(); }});
598 } else {
599 check(deq.peekLast() != e);
600 check(deq.getLast() != e);
601 }
602 check(!deq.contains(e));
603 equal(new ArrayList<Integer>(deq), originalContents);
604
605 // Test operations on empty deque
606 switch (rnd.nextInt(isList ? 4 : 2)) {
607 case 0: deq.clear(); break;
608 case 1:
609 Iterator it = deq.iterator();
610 while (it.hasNext()) {
611 it.next();
612 it.remove();
613 }
614 break;
615 case 2: asList.subList(0, asList.size()).clear(); break;
616 case 3:
617 ListIterator lit = asList.listIterator(asList.size());
618 while (lit.hasPrevious()) {
619 lit.previous();
620 lit.remove();
621 }
622 break;
623 default: throw new AssertionError();
624 }
625 testEmptyCollection(deq);
626 check(!deq.iterator().hasNext());
627 if (isList) {
628 check(!asList.listIterator().hasPrevious());
629 THROWS(NoSuchElementException.class,
630 new Fun(){void f(){ asList.listIterator().previous(); }});
631 }
632 THROWS(NoSuchElementException.class,
633 new Fun(){void f(){ deq.iterator().next(); }},
634 new Fun(){void f(){ deq.element(); }},
635 new Fun(){void f(){ deq.getFirst(); }},
636 new Fun(){void f(){ deq.getLast(); }},
637 new Fun(){void f(){ deq.pop(); }},
638 new Fun(){void f(){ deq.remove(); }},
639 new Fun(){void f(){ deq.removeFirst(); }},
640 new Fun(){void f(){ deq.removeLast(); }});
641
642 check(deq.poll() == null);
643 check(deq.pollFirst() == null);
644 check(deq.pollLast() == null);
645 check(deq.peek() == null);
646 check(deq.peekFirst() == null);
647 check(deq.peekLast() == null);
648 check(!deq.removeFirstOccurrence(e));
649 check(!deq.removeLastOccurrence(e));
650
651 check(deq.addAll(originalContents) == !isEmpty);
652 equal(new ArrayList<Integer>(deq), originalContents);
653 check(!deq.addAll(Collections.<Integer>emptyList()));
654 equal(new ArrayList<Integer>(deq), originalContents);
655 }
656 }
657
658 private static void testQueueIteratorRemove(Queue<Integer> q) {
659 System.err.printf("testQueueIteratorRemove %s%n",
660 q.getClass().getSimpleName());
661 q.clear();
662 for (int i = 0; i < 5; i++)
663 q.add(i);
664 Iterator<Integer> it = q.iterator();
665 check(it.hasNext());
666 for (int i = 3; i >= 0; i--)
667 q.remove(i);
668 equal(it.next(), 0);
669 equal(it.next(), 4);
670
671 q.clear();
672 for (int i = 0; i < 5; i++)
673 q.add(i);
674 it = q.iterator();
675 equal(it.next(), 0);
676 check(it.hasNext());
677 for (int i = 1; i < 4; i++)
678 q.remove(i);
679 equal(it.next(), 1);
680 equal(it.next(), 4);
681 }
682
683 private static void testList(final List<Integer> l) {
684 //----------------------------------------------------------------
685 // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
686 // doesn't throw IndexOutOfBoundsException
687 //----------------------------------------------------------------
688 try {
689 l.addAll(-1, Collections.<Integer>emptyList());
690 fail("Expected IndexOutOfBoundsException not thrown");
691 }
692 catch (UnsupportedOperationException _) {/* OK */}
693 catch (IndexOutOfBoundsException _) {/* OK */}
694 catch (Throwable t) { unexpected(t); }
695
696 // equal(l instanceof Serializable,
697 // l.subList(0,0) instanceof Serializable);
698 if (l.subList(0,0) instanceof Serializable)
699 check(l instanceof Serializable);
700
701 equal(l instanceof RandomAccess,
702 l.subList(0,0) instanceof RandomAccess);
703 }
704
705 private static void testCollection(Collection<Integer> c) {
706 try { testCollection1(c); }
707 catch (Throwable t) { unexpected(t); }
708 }
709
710 private static void testCollection1(Collection<Integer> c) {
711
712 System.out.println("\n==> " + c.getClass().getName());
713
714 checkFunctionalInvariants(c);
715
716 if (! supportsAdd(c)) return;
717 //System.out.println("add() supported");
718
719 if (c instanceof NavigableSet) {
720 System.out.println("NavigableSet tests...");
721
722 NavigableSet<Integer> ns = (NavigableSet<Integer>)c;
723 testNavigableSet(ns);
724 testNavigableSet(ns.headSet(6, false));
725 testNavigableSet(ns.headSet(5, true));
726 testNavigableSet(ns.tailSet(0, false));
727 testNavigableSet(ns.tailSet(1, true));
728 testNavigableSet(ns.subSet(0, false, 5, true));
729 testNavigableSet(ns.subSet(1, true, 6, false));
730 }
731
732 if (c instanceof Queue)
733 testQueue((Queue<Integer>)c);
734
735 if (c instanceof List)
736 testList((List<Integer>)c);
737
738 check(supportsRemove(c));
739
740 try {
741 oneElement(c);
742 checkFunctionalInvariants(c);
743 }
744 catch (Throwable t) { unexpected(t); }
745
746 clear(c); testNullElement(c);
747 oneElement(c); testNullElement(c);
748
749 clear(c); testStringElement(c);
750 oneElement(c); testStringElement(c);
751
752 if (c.getClass().getName().matches(".*concurrent.*"))
753 testConcurrentCollection(c);
754
755 //----------------------------------------------------------------
756 // The "all" operations should throw NPE when passed null
757 //----------------------------------------------------------------
758 {
759 clear(c);
760 try {
761 c.removeAll(null);
762 fail("Expected NullPointerException");
763 }
764 catch (NullPointerException e) { pass(); }
765 catch (Throwable t) { unexpected(t); }
766
767 oneElement(c);
768 try {
769 c.removeAll(null);
770 fail("Expected NullPointerException");
771 }
772 catch (NullPointerException e) { pass(); }
773 catch (Throwable t) { unexpected(t); }
774
775 clear(c);
776 try {
777 c.retainAll(null);
778 fail("Expected NullPointerException");
779 }
780 catch (NullPointerException e) { pass(); }
781 catch (Throwable t) { unexpected(t); }
782
783 oneElement(c);
784 try {
785 c.retainAll(null);
786 fail("Expected NullPointerException");
787 }
788 catch (NullPointerException e) { pass(); }
789 catch (Throwable t) { unexpected(t); }
790
791 oneElement(c);
792 try {
793 c.addAll(null);
794 fail("Expected NullPointerException");
795 }
796 catch (NullPointerException e) { pass(); }
797 catch (Throwable t) { unexpected(t); }
798
799 oneElement(c);
800 try {
801 c.containsAll(null);
802 fail("Expected NullPointerException");
803 }
804 catch (NullPointerException e) { pass(); }
805 catch (Throwable t) { unexpected(t); }
806 }
807 }
808
809 //----------------------------------------------------------------
810 // Map
811 //----------------------------------------------------------------
812 private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
813 check(m.keySet().size() == m.entrySet().size());
814 check(m.keySet().size() == m.size());
815 checkFunctionalInvariants(m.keySet());
816 checkFunctionalInvariants(m.values());
817 check(m.size() != 0 ^ m.isEmpty());
818 }
819
820 private static void testMap(Map<Integer,Integer> m) {
821 System.out.println("\n==> " + m.getClass().getName());
822
823 if (m instanceof ConcurrentMap)
824 testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
825
826 if (m instanceof NavigableMap) {
827 System.out.println("NavigableMap tests...");
828
829 NavigableMap<Integer,Integer> nm =
830 (NavigableMap<Integer,Integer>) m;
831 testNavigableMapRemovers(nm);
832 testNavigableMap(nm);
833 testNavigableMap(nm.headMap(6, false));
834 testNavigableMap(nm.headMap(5, true));
835 testNavigableMap(nm.tailMap(0, false));
836 testNavigableMap(nm.tailMap(1, true));
837 testNavigableMap(nm.subMap(1, true, 6, false));
838 testNavigableMap(nm.subMap(0, false, 5, true));
839 }
840
841 checkFunctionalInvariants(m);
842
843 if (supportsClear(m)) {
844 try { clear(m); }
845 catch (Throwable t) { unexpected(t); }
846 }
847
848 if (supportsPut(m)) {
849 try {
850 check(m.put(3333, 77777) == null);
851 check(m.put(9134, 74982) == null);
852 check(m.get(9134) == 74982);
853 check(m.put(9134, 1382) == 74982);
854 check(m.get(9134) == 1382);
855 check(m.size() == 2);
856 checkFunctionalInvariants(m);
857 checkNPEConsistency(m);
858 }
859 catch (Throwable t) { unexpected(t); }
860 }
861 }
862
863 private static boolean supportsPut(Map<Integer,Integer> m) {
864 // We're asking for .equals(...) semantics
865 if (m instanceof IdentityHashMap) return false;
866
867 try { check(m.put(778347983,12735) == null); }
868 catch (UnsupportedOperationException t) { return false; }
869 catch (Throwable t) { unexpected(t); }
870
871 try {
872 check(m.containsKey(778347983));
873 check(m.remove(778347983) != null);
874 } catch (Throwable t) { unexpected(t); }
875 return true;
876 }
877
878 private static boolean supportsClear(Map<?,?> m) {
879 try { m.clear(); }
880 catch (UnsupportedOperationException t) { return false; }
881 catch (Throwable t) { unexpected(t); }
882 return true;
883 }
884
885 //----------------------------------------------------------------
886 // ConcurrentMap
887 //----------------------------------------------------------------
888 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
889 System.out.println("ConcurrentMap tests...");
890
891 try {
892 clear(m);
893
894 check(m.putIfAbsent(18357,7346) == null);
895 check(m.containsKey(18357));
896 check(m.putIfAbsent(18357,8263) == 7346);
897 try { m.putIfAbsent(18357,null); fail("NPE"); }
898 catch (NullPointerException t) { }
899 check(m.containsKey(18357));
900
901 check(! m.replace(18357,8888,7777));
902 check(m.containsKey(18357));
903 try { m.replace(18357,null,7777); fail("NPE"); }
904 catch (NullPointerException t) { }
905 check(m.containsKey(18357));
906 check(m.get(18357) == 7346);
907 check(m.replace(18357,7346,5555));
908 check(m.replace(18357,5555,7346));
909 check(m.get(18357) == 7346);
910
911 check(m.replace(92347,7834) == null);
912 try { m.replace(18357,null); fail("NPE"); }
913 catch (NullPointerException t) { }
914 check(m.replace(18357,7346) == 7346);
915 check(m.replace(18357,5555) == 7346);
916 check(m.get(18357) == 5555);
917 check(m.replace(18357,7346) == 5555);
918 check(m.get(18357) == 7346);
919
920 check(! m.remove(18357,9999));
921 check(m.get(18357) == 7346);
922 check(m.containsKey(18357));
923 check(! m.remove(18357,null)); // 6272521
924 check(m.get(18357) == 7346);
925 check(m.remove(18357,7346));
926 check(m.get(18357) == null);
927 check(! m.containsKey(18357));
928 check(m.isEmpty());
929
930 m.putIfAbsent(1,2);
931 check(m.size() == 1);
932 check(! m.remove(1,null));
933 check(! m.remove(1,null));
934 check(! m.remove(1,1));
935 check(m.remove(1,2));
936 check(m.isEmpty());
937
938 testEmptyMap(m);
939 }
940 catch (Throwable t) { unexpected(t); }
941 }
942
943 private static void throwsConsistently(Class<? extends Throwable> k,
944 Iterable<Fun> fs) {
945 List<Class<? extends Throwable>> threw
946 = new ArrayList<Class<? extends Throwable>>();
947 for (Fun f : fs)
948 try { f.f(); threw.add(null); }
949 catch (Throwable t) {
950 check(k.isAssignableFrom(t.getClass()));
951 threw.add(t.getClass());
952 }
953 if (new HashSet<Object>(threw).size() != 1)
954 fail(threw.toString());
955 }
956
957 private static <T> void checkNPEConsistency(final Map<T,Integer> m) {
958 m.clear();
959 final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap)
960 ? (ConcurrentMap<T,Integer>) m
961 : null;
962 List<Fun> fs = new ArrayList<Fun>();
963 fs.add(new Fun(){void f(){ check(! m.containsKey(null));}});
964 fs.add(new Fun(){void f(){ equal(m.remove(null), null);}});
965 fs.add(new Fun(){void f(){ equal(m.get(null), null);}});
966 if (cm != null) {
967 fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});}
968 throwsConsistently(NullPointerException.class, fs);
969
970 fs.clear();
971 final Map<T,Integer> sm = singletonMap(null,1);
972 fs.add(new Fun(){void f(){ equal(m.put(null,1), null); m.clear();}});
973 fs.add(new Fun(){void f(){ m.putAll(sm); m.clear();}});
974 if (cm != null) {
975 fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});
976 fs.add(new Fun(){void f(){ equal(cm.putIfAbsent(null,1), 1);}});
977 fs.add(new Fun(){void f(){ equal(cm.replace(null,1), null);}});
978 fs.add(new Fun(){void f(){ equal(cm.replace(null,1, 1), 1);}});
979 }
980 throwsConsistently(NullPointerException.class, fs);
981 }
982
983 //----------------------------------------------------------------
984 // NavigableMap
985 //----------------------------------------------------------------
986 private static void
987 checkNavigableMapKeys(NavigableMap<Integer,Integer> m,
988 Integer i,
989 Integer lower,
990 Integer floor,
991 Integer ceiling,
992 Integer higher) {
993 equal(m.lowerKey(i), lower);
994 equal(m.floorKey(i), floor);
995 equal(m.ceilingKey(i), ceiling);
996 equal(m.higherKey(i), higher);
997 }
998
999 private static void
1000 checkNavigableSetKeys(NavigableSet<Integer> m,
1001 Integer i,
1002 Integer lower,
1003 Integer floor,
1004 Integer ceiling,
1005 Integer higher) {
1006 equal(m.lower(i), lower);
1007 equal(m.floor(i), floor);
1008 equal(m.ceiling(i), ceiling);
1009 equal(m.higher(i), higher);
1010 }
1011
1012 static final Random rnd = new Random();
1013 static void equalNext(final Iterator<?> it, Object expected) {
1014 if (rnd.nextBoolean())
1015 check(it.hasNext());
1016 equal(it.next(), expected);
1017 }
1018
1019 static void equalMaps(Map m1, Map m2) {
1020 equal(m1, m2);
1021 equal(m2, m1);
1022 equal(m1.size(), m2.size());
1023 equal(m1.isEmpty(), m2.isEmpty());
1024 equal(m1.toString(), m2.toString());
1025 check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray()));
1026 }
1027
1028 @SuppressWarnings({"unchecked", "rawtypes"})
1029 static void testNavigableMapRemovers(NavigableMap m)
1030 {
1031 final Map emptyMap = new HashMap();
1032
1033 final Map singletonMap = new HashMap();
1034 singletonMap.put(1, 2);
1035
1036 abstract class NavigableMapView {
1037 abstract NavigableMap view(NavigableMap m);
1038 }
1039
1040 NavigableMapView[] views = {
1041 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1042 return m; }},
1043 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1044 return m.headMap(99, true); }},
1045 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1046 return m.tailMap(-99, false); }},
1047 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1048 return m.subMap(-99, true, 99, false); }},
1049 };
1050
1051 abstract class Remover {
1052 abstract void remove(NavigableMap m, Object k, Object v);
1053 }
1054
1055 Remover[] removers = {
1056 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1057 equal(m.remove(k), v); }},
1058
1059 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1060 equal(m.descendingMap().remove(k), v); }},
1061 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1062 equal(m.descendingMap().headMap(-86, false).remove(k), v); }},
1063 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1064 equal(m.descendingMap().tailMap(86, true).remove(k), v); }},
1065
1066 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1067 equal(m.headMap(86, true).remove(k), v); }},
1068 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1069 equal(m.tailMap(-86, true).remove(k), v); }},
1070 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1071 equal(m.subMap(-86, false, 86, true).remove(k), v); }},
1072
1073 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1074 check(m.keySet().remove(k)); }},
1075 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1076 check(m.navigableKeySet().remove(k)); }},
1077
1078 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1079 check(m.navigableKeySet().headSet(86, true).remove(k)); }},
1080 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1081 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }},
1082 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1083 check(m.navigableKeySet().subSet(-86, true, 86, false)
1084 .remove(k)); }},
1085
1086 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1087 check(m.descendingKeySet().headSet(-86, false).remove(k)); }},
1088 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1089 check(m.descendingKeySet().tailSet(86, true).remove(k)); }},
1090 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1091 check(m.descendingKeySet().subSet(86, true, -86, false)
1092 .remove(k)); }},
1093 };
1094
1095 for (NavigableMapView view : views) {
1096 for (Remover remover : removers) {
1097 try {
1098 m.clear();
1099 equalMaps(m, emptyMap);
1100 equal(m.put(1, 2), null);
1101 equalMaps(m, singletonMap);
1102 NavigableMap v = view.view(m);
1103 remover.remove(v, 1, 2);
1104 equalMaps(m, emptyMap);
1105 } catch (Throwable t) { unexpected(t); }
1106 }
1107 }
1108 }
1109
1110 private static void testNavigableMap(NavigableMap<Integer,Integer> m)
1111 {
1112 clear(m);
1113 checkNavigableMapKeys(m, 1, null, null, null, null);
1114
1115 equal(m.put(1, 2), null);
1116 equal(m.put(3, 4), null);
1117 equal(m.put(5, 9), null);
1118
1119 equal(m.put(1, 2), 2);
1120 equal(m.put(3, 4), 4);
1121 equal(m.put(5, 6), 9);
1122
1123 checkNavigableMapKeys(m, 0, null, null, 1, 1);
1124 checkNavigableMapKeys(m, 1, null, 1, 1, 3);
1125 checkNavigableMapKeys(m, 2, 1, 1, 3, 3);
1126 checkNavigableMapKeys(m, 3, 1, 3, 3, 5);
1127 checkNavigableMapKeys(m, 5, 3, 5, 5, null);
1128 checkNavigableMapKeys(m, 6, 5, 5, null, null);
1129
1130 for (final Iterator<Integer> it :
1131 (Iterator<Integer>[])
1132 new Iterator<?>[] {
1133 m.descendingKeySet().iterator(),
1134 m.navigableKeySet().descendingIterator()}) {
1135 equalNext(it, 5);
1136 equalNext(it, 3);
1137 equalNext(it, 1);
1138 check(! it.hasNext());
1139 THROWS(NoSuchElementException.class,
1140 new Fun(){void f(){it.next();}});
1141 }
1142
1143 {
1144 final Iterator<Map.Entry<Integer,Integer>> it
1145 = m.descendingMap().entrySet().iterator();
1146 check(it.hasNext()); equal(it.next().getKey(), 5);
1147 check(it.hasNext()); equal(it.next().getKey(), 3);
1148 check(it.hasNext()); equal(it.next().getKey(), 1);
1149 check(! it.hasNext());
1150 THROWS(NoSuchElementException.class,
1151 new Fun(){void f(){it.next();}});
1152 }
1153 }
1154
1155
1156 private static void testNavigableSet(NavigableSet<Integer> s) {
1157 clear(s);
1158 checkNavigableSetKeys(s, 1, null, null, null, null);
1159
1160 check(s.add(1));
1161 check(s.add(3));
1162 check(s.add(5));
1163
1164 check(! s.add(1));
1165 check(! s.add(3));
1166 check(! s.add(5));
1167
1168 checkNavigableSetKeys(s, 0, null, null, 1, 1);
1169 checkNavigableSetKeys(s, 1, null, 1, 1, 3);
1170 checkNavigableSetKeys(s, 2, 1, 1, 3, 3);
1171 checkNavigableSetKeys(s, 3, 1, 3, 3, 5);
1172 checkNavigableSetKeys(s, 5, 3, 5, 5, null);
1173 checkNavigableSetKeys(s, 6, 5, 5, null, null);
1174
1175 for (final Iterator<Integer> it :
1176 (Iterator<Integer>[])
1177 new Iterator<?>[] {
1178 s.descendingIterator(),
1179 s.descendingSet().iterator()}) {
1180 equalNext(it, 5);
1181 equalNext(it, 3);
1182 equalNext(it, 1);
1183 check(! it.hasNext());
1184 THROWS(NoSuchElementException.class,
1185 new Fun(){void f(){it.next();}});
1186 }
1187 }
1188
1189 //--------------------- Infrastructure ---------------------------
1190 static volatile int passed = 0, failed = 0;
1191 static void pass() { passed++; }
1192 static void fail() { failed++; Thread.dumpStack(); }
1193 static void fail(String msg) { System.out.println(msg); fail(); }
1194 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
1195 static void check(boolean cond) { if (cond) pass(); else fail(); }
1196 static void equal(Object x, Object y) {
1197 if (x == null ? y == null : x.equals(y)) pass();
1198 else {System.out.println(x + " not equal to " + y); fail();}}
1199 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
1200 public static void main(String[] args) throws Throwable {
1201 try { realMain(args); } catch (Throwable t) { unexpected(t); }
1202
1203 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
1204 if (failed > 0) throw new Exception("Some tests failed");
1205 }
1206 private static abstract class Fun {abstract void f() throws Throwable;}
1207 private static void THROWS(Class<? extends Throwable> k, Fun... fs) {
1208 for (Fun f : fs)
1209 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
1210 catch (Throwable t) {
1211 if (k.isAssignableFrom(t.getClass())) pass();
1212 else unexpected(t);}}
1213 static byte[] serializedForm(Object obj) {
1214 try {
1215 ByteArrayOutputStream baos = new ByteArrayOutputStream();
1216 new ObjectOutputStream(baos).writeObject(obj);
1217 return baos.toByteArray();
1218 } catch (IOException e) { throw new Error(e); }}
1219 static Object readObject(byte[] bytes)
1220 throws IOException, ClassNotFoundException {
1221 InputStream is = new ByteArrayInputStream(bytes);
1222 return new ObjectInputStream(is).readObject();}
1223 @SuppressWarnings("unchecked")
1224 static <T> T serialClone(T obj) {
1225 try { return (T) readObject(serializedForm(obj)); }
1226 catch (Exception e) { throw new Error(e); }}
1227 private static class NewAbstractCollection<E> extends AbstractCollection<E> {
1228 ArrayList<E> list = new ArrayList<>();
1229 public boolean remove(Object obj) {
1230 return list.remove(obj);
1231 }
1232 public boolean add(E e) {
1233 return list.add(e);
1234 }
1235 public Iterator<E> iterator() {
1236 return list.iterator();
1237 }
1238 public int size() {
1239 return list.size();
1240 }
1241 }
1242 private static class NewAbstractSet<E> extends AbstractSet<E> {
1243 HashSet<E> set = new HashSet<>();
1244 public boolean remove(Object obj) {
1245 return set.remove(obj);
1246 }
1247 public boolean add(E e) {
1248 return set.add(e);
1249 }
1250 public Iterator<E> iterator() {
1251 return set.iterator();
1252 }
1253 public int size() {
1254 return set.size();
1255 }
1256 }
1257
1258 }