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