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 import java.lang.reflect.*;
59
60 public class MOAT {
61 public static void realMain(String[] args) {
62
63 testCollection(new NewAbstractCollection<Integer>());
64 testCollection(new NewAbstractSet<Integer>());
65 testCollection(new LinkedHashSet<Integer>());
66 testCollection(new HashSet<Integer>());
67 testCollection(new Vector<Integer>());
68 testCollection(new Vector<Integer>().subList(0,0));
69 testCollection(new ArrayDeque<Integer>());
70 testCollection(new ArrayList<Integer>());
71 testCollection(new ArrayList<Integer>().subList(0,0));
72 testCollection(new LinkedList<Integer>());
73 testCollection(new LinkedList<Integer>().subList(0,0));
74 testCollection(new TreeSet<Integer>());
75 testCollection(Collections.checkedList(new ArrayList<Integer>(), Integer.class));
76 testCollection(Collections.synchronizedList(new ArrayList<Integer>()));
77 testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class));
78 testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class));
79 testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class));
80 testCollection(Collections.synchronizedSet(new HashSet<Integer>()));
161
162 // Singleton collections
163 Set<Integer> singletonSet = singleton(1);
164 equal(singletonSet.size(), 1);
165 testCollection(singletonSet);
166 testImmutableSet(singletonSet);
167
168 List<Integer> singletonList = singletonList(1);
169 equal(singletonList.size(), 1);
170 testCollection(singletonList);
171 testImmutableList(singletonList);
172 testImmutableList(singletonList.subList(0,1));
173 testImmutableList(singletonList.subList(0,1).subList(0,1));
174 testEmptyList(singletonList.subList(0,0));
175 testEmptyList(singletonList.subList(0,0).subList(0,0));
176
177 Map<Integer,Integer> singletonMap = singletonMap(1,2);
178 equal(singletonMap.size(), 1);
179 testMap(singletonMap);
180 testImmutableMap(singletonMap);
181 }
182
183 private static void checkContainsSelf(Collection<Integer> c) {
184 check(c.containsAll(c));
185 check(c.containsAll(Arrays.asList(c.toArray())));
186 check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));
187 }
188
189 private static void checkContainsEmpty(Collection<Integer> c) {
190 check(c.containsAll(new ArrayList<Integer>()));
191 }
192
193 private static <T> void testEmptyCollection(Collection<T> c) {
194 check(c.isEmpty());
195 equal(c.size(), 0);
196 equal(c.toString(),"[]");
197 equal(c.toArray().length, 0);
198 equal(c.toArray(new Object[0]).length, 0);
199 check(c.toArray(new Object[]{42})[0] == null);
200
201 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
202 equal(c.toArray(a), a);
203 equal(a[0], null);
204 testEmptyIterator(c.iterator());
205 }
206
207 static <T> void testEmptyIterator(final Iterator<T> it) {
208 if (rnd.nextBoolean())
209 check(! it.hasNext());
210
211 THROWS(NoSuchElementException.class, () -> it.next());
212
313 //testImmutableSet(m.entrySet());
314 }
315
316 private static void clear(Map<?,?> m) {
317 try { m.clear(); }
318 catch (Throwable t) { unexpected(t); }
319 testEmptyMap(m);
320 }
321
322 private static void oneElement(Collection<Integer> c) {
323 clear(c);
324 try {
325 check(c.add(-42));
326 equal(c.toString(), "[-42]");
327 if (c instanceof Set) check(! c.add(-42));
328 } catch (Throwable t) { unexpected(t); }
329 check(! c.isEmpty()); check(c.size() == 1);
330 }
331
332 private static boolean supportsAdd(Collection<Integer> c) {
333 try { check(c.add(778347983)); }
334 catch (UnsupportedOperationException t) { return false; }
335 catch (Throwable t) { unexpected(t); }
336
337 try {
338 check(c.contains(778347983));
339 check(c.remove(778347983));
340 } catch (Throwable t) { unexpected(t); }
341 return true;
342 }
343
344 private static boolean supportsRemove(Collection<Integer> c) {
345 try { check(! c.remove(19134032)); }
346 catch (UnsupportedOperationException t) { return false; }
347 catch (Throwable t) { unexpected(t); }
348 return true;
349 }
350
351 // 6260652: (coll) Arrays.asList(x).toArray().getClass()
352 // should be Object[].class
353 // Fixed in jdk9, but not jdk8 ...
354 static final boolean needToWorkAround6260652 =
355 Arrays.asList("").toArray().getClass() != Object[].class;
356
357 private static void checkFunctionalInvariants(Collection<Integer> c) {
358 try {
359 checkContainsSelf(c);
360 checkContainsEmpty(c);
361 check(c.size() != 0 ^ c.isEmpty());
362
363 {
364 int size = 0;
365 for (Integer i : c) size++;
366 check(c.size() == size);
367 }
368
369 check(c.toArray().length == c.size());
370 check(c.toArray().getClass() == Object[].class
371 ||
372 (needToWorkAround6260652 &&
373 c.getClass().getName().equals("java.util.Arrays$ArrayList")));
374 for (int size : new int[]{0,1,c.size(), c.size()+1}) {
375 Integer[] a = c.toArray(new Integer[size]);
376 check((size > c.size()) || a.length == c.size());
377 int i = 0; for (Integer j : c) check(a[i++] == j);
378 check((size <= c.size()) || (a[c.size()] == null));
379 check(a.getClass() == Integer[].class);
380 }
381
382 check(c.equals(c));
383 if (c instanceof Serializable) {
384 //System.out.printf("Serializing %s%n", c.getClass().getName());
385 try {
386 Object clone = serialClone(c);
387 equal(c instanceof Serializable,
388 clone instanceof Serializable);
844
845 oneElement(c);
846 try {
847 c.containsAll(null);
848 fail("Expected NullPointerException");
849 }
850 catch (NullPointerException e) { pass(); }
851 catch (Throwable t) { unexpected(t); }
852 }
853 }
854
855 //----------------------------------------------------------------
856 // Map
857 //----------------------------------------------------------------
858 private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
859 check(m.keySet().size() == m.entrySet().size());
860 check(m.keySet().size() == m.size());
861 checkFunctionalInvariants(m.keySet());
862 checkFunctionalInvariants(m.values());
863 check(m.size() != 0 ^ m.isEmpty());
864 }
865
866 private static void testMap(Map<Integer,Integer> m) {
867 System.out.println("\n==> " + m.getClass().getName());
868
869 if (m instanceof ConcurrentMap)
870 testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
871
872 if (m instanceof NavigableMap) {
873 System.out.println("NavigableMap tests...");
874
875 NavigableMap<Integer,Integer> nm =
876 (NavigableMap<Integer,Integer>) m;
877 testNavigableMapRemovers(nm);
878 testNavigableMap(nm);
879 testNavigableMap(nm.headMap(6, false));
880 testNavigableMap(nm.headMap(5, true));
881 testNavigableMap(nm.tailMap(0, false));
882 testNavigableMap(nm.tailMap(1, true));
883 testNavigableMap(nm.subMap(1, true, 6, false));
893
894 if (supportsPut(m)) {
895 try {
896 check(m.put(3333, 77777) == null);
897 check(m.put(9134, 74982) == null);
898 check(m.get(9134) == 74982);
899 check(m.put(9134, 1382) == 74982);
900 check(m.get(9134) == 1382);
901 check(m.size() == 2);
902 checkFunctionalInvariants(m);
903 checkNPEConsistency(m);
904 }
905 catch (Throwable t) { unexpected(t); }
906 }
907 }
908
909 private static boolean supportsPut(Map<Integer,Integer> m) {
910 // We're asking for .equals(...) semantics
911 if (m instanceof IdentityHashMap) return false;
912
913 try { check(m.put(778347983,12735) == null); }
914 catch (UnsupportedOperationException t) { return false; }
915 catch (Throwable t) { unexpected(t); }
916
917 try {
918 check(m.containsKey(778347983));
919 check(m.remove(778347983) != null);
920 } catch (Throwable t) { unexpected(t); }
921 return true;
922 }
923
924 private static boolean supportsClear(Map<?,?> m) {
925 try { m.clear(); }
926 catch (UnsupportedOperationException t) { return false; }
927 catch (Throwable t) { unexpected(t); }
928 return true;
929 }
930
931 //----------------------------------------------------------------
932 // ConcurrentMap
933 //----------------------------------------------------------------
934 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
935 System.out.println("ConcurrentMap tests...");
936
937 try {
938 clear(m);
939
|
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 import java.lang.reflect.*;
59
60 public class MOAT {
61 // Collections under test must not be initialized to contain this value,
62 // and maps under test must not contain this value as a key.
63 // It's used as a sentinel for absent-element testing.
64 static final int ABSENT_VALUE = 778347983;
65
66 static final Integer[] integerArray;
67 static {
68 Integer[] ia = new Integer[20];
69 // fill with 1..20 inclusive
70 for (int i = 0; i < ia.length; i++) {
71 ia[i] = i + 1;
72 }
73 integerArray = ia;
74 }
75
76 public static void realMain(String[] args) {
77
78 testCollection(new NewAbstractCollection<Integer>());
79 testCollection(new NewAbstractSet<Integer>());
80 testCollection(new LinkedHashSet<Integer>());
81 testCollection(new HashSet<Integer>());
82 testCollection(new Vector<Integer>());
83 testCollection(new Vector<Integer>().subList(0,0));
84 testCollection(new ArrayDeque<Integer>());
85 testCollection(new ArrayList<Integer>());
86 testCollection(new ArrayList<Integer>().subList(0,0));
87 testCollection(new LinkedList<Integer>());
88 testCollection(new LinkedList<Integer>().subList(0,0));
89 testCollection(new TreeSet<Integer>());
90 testCollection(Collections.checkedList(new ArrayList<Integer>(), Integer.class));
91 testCollection(Collections.synchronizedList(new ArrayList<Integer>()));
92 testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class));
93 testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class));
94 testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class));
95 testCollection(Collections.synchronizedSet(new HashSet<Integer>()));
176
177 // Singleton collections
178 Set<Integer> singletonSet = singleton(1);
179 equal(singletonSet.size(), 1);
180 testCollection(singletonSet);
181 testImmutableSet(singletonSet);
182
183 List<Integer> singletonList = singletonList(1);
184 equal(singletonList.size(), 1);
185 testCollection(singletonList);
186 testImmutableList(singletonList);
187 testImmutableList(singletonList.subList(0,1));
188 testImmutableList(singletonList.subList(0,1).subList(0,1));
189 testEmptyList(singletonList.subList(0,0));
190 testEmptyList(singletonList.subList(0,0).subList(0,0));
191
192 Map<Integer,Integer> singletonMap = singletonMap(1,2);
193 equal(singletonMap.size(), 1);
194 testMap(singletonMap);
195 testImmutableMap(singletonMap);
196
197 // Unmodifiable List
198 testEmptyList(List.of());
199 for (List<Integer> list : Arrays.asList(
200 List.<Integer>of(),
201 List.of(1),
202 List.of(1, 2),
203 List.of(1, 2, 3),
204 List.of(1, 2, 3, 4),
205 List.of(1, 2, 3, 4, 5),
206 List.of(1, 2, 3, 4, 5, 6),
207 List.of(1, 2, 3, 4, 5, 6, 7),
208 List.of(1, 2, 3, 4, 5, 6, 7, 8),
209 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9),
210 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),
211 List.of(integerArray))) {
212 testCollection(list);
213 testImmutableList(list);
214 }
215
216 // Unmodifiable Set
217 testEmptySet(Set.of());
218 for (Set<Integer> set : Arrays.asList(
219 Set.<Integer>of(),
220 Set.of(1),
221 Set.of(1, 2),
222 Set.of(1, 2, 3),
223 Set.of(1, 2, 3, 4),
224 Set.of(1, 2, 3, 4, 5),
225 Set.of(1, 2, 3, 4, 5, 6),
226 Set.of(1, 2, 3, 4, 5, 6, 7),
227 Set.of(1, 2, 3, 4, 5, 6, 7, 8),
228 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9),
229 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),
230 Set.of(integerArray))) {
231 testCollection(set);
232 testImmutableSet(set);
233 }
234
235 // Unmodifiable Map
236
237 @SuppressWarnings("unchecked")
238 Map.Entry<Integer,Integer>[] ea = (Map.Entry<Integer,Integer>[])new Map.Entry<?,?>[20];
239 for (int i = 0; i < ea.length; i++) {
240 ea[i] = Map.entry(i+1, i+101);
241 }
242
243 testEmptyMap(Map.of());
244 for (Map<Integer,Integer> map : Arrays.asList(
245 Map.<Integer,Integer>of(),
246 Map.of(1, 101),
247 Map.of(1, 101, 2, 202),
248 Map.of(1, 101, 2, 202, 3, 303),
249 Map.of(1, 101, 2, 202, 3, 303, 4, 404),
250 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505),
251 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606),
252 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707),
253 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808),
254 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909),
255 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909, 10, 1010),
256 Map.ofEntries(ea))) {
257 testMap(map);
258 testImmutableMap(map);
259 }
260 }
261
262 private static void checkContainsSelf(Collection<Integer> c) {
263 check(c.containsAll(c));
264 check(c.containsAll(Arrays.asList(c.toArray())));
265 check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));
266 }
267
268 private static void checkContainsEmpty(Collection<Integer> c) {
269 check(c.containsAll(new ArrayList<Integer>()));
270 }
271
272 private static void checkUnique(Set<Integer> s) {
273 for (Integer i : s) {
274 int count = 0;
275 for (Integer j : s) {
276 if (Objects.equals(i,j))
277 ++count;
278 }
279 check(count == 1);
280 }
281 }
282
283 private static <T> void testEmptyCollection(Collection<T> c) {
284 check(c.isEmpty());
285 equal(c.size(), 0);
286 equal(c.toString(),"[]");
287 equal(c.toArray().length, 0);
288 equal(c.toArray(new Object[0]).length, 0);
289 check(c.toArray(new Object[]{42})[0] == null);
290
291 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
292 equal(c.toArray(a), a);
293 equal(a[0], null);
294 testEmptyIterator(c.iterator());
295 }
296
297 static <T> void testEmptyIterator(final Iterator<T> it) {
298 if (rnd.nextBoolean())
299 check(! it.hasNext());
300
301 THROWS(NoSuchElementException.class, () -> it.next());
302
403 //testImmutableSet(m.entrySet());
404 }
405
406 private static void clear(Map<?,?> m) {
407 try { m.clear(); }
408 catch (Throwable t) { unexpected(t); }
409 testEmptyMap(m);
410 }
411
412 private static void oneElement(Collection<Integer> c) {
413 clear(c);
414 try {
415 check(c.add(-42));
416 equal(c.toString(), "[-42]");
417 if (c instanceof Set) check(! c.add(-42));
418 } catch (Throwable t) { unexpected(t); }
419 check(! c.isEmpty()); check(c.size() == 1);
420 }
421
422 private static boolean supportsAdd(Collection<Integer> c) {
423 try { check(c.add(ABSENT_VALUE)); }
424 catch (UnsupportedOperationException t) { return false; }
425 catch (Throwable t) { unexpected(t); }
426
427 try {
428 check(c.contains(ABSENT_VALUE));
429 check(c.remove(ABSENT_VALUE));
430 } catch (Throwable t) { unexpected(t); }
431 return true;
432 }
433
434 private static boolean supportsRemove(Collection<Integer> c) {
435 try { check(! c.remove(ABSENT_VALUE)); }
436 catch (UnsupportedOperationException t) { return false; }
437 catch (Throwable t) { unexpected(t); }
438 return true;
439 }
440
441 // 6260652: (coll) Arrays.asList(x).toArray().getClass()
442 // should be Object[].class
443 // Fixed in jdk9, but not jdk8 ...
444 static final boolean needToWorkAround6260652 =
445 Arrays.asList("").toArray().getClass() != Object[].class;
446
447 private static void checkFunctionalInvariants(Collection<Integer> c) {
448 try {
449 checkContainsSelf(c);
450 checkContainsEmpty(c);
451 check(c.size() != 0 ^ c.isEmpty());
452 check(! c.contains(ABSENT_VALUE));
453
454 {
455 int size = 0;
456 for (Integer i : c) size++;
457 check(c.size() == size);
458 }
459
460 if (c instanceof Set) {
461 checkUnique((Set<Integer>)c);
462 }
463
464 check(c.toArray().length == c.size());
465 check(c.toArray().getClass() == Object[].class
466 ||
467 (needToWorkAround6260652 &&
468 c.getClass().getName().equals("java.util.Arrays$ArrayList")));
469 for (int size : new int[]{0,1,c.size(), c.size()+1}) {
470 Integer[] a = c.toArray(new Integer[size]);
471 check((size > c.size()) || a.length == c.size());
472 int i = 0; for (Integer j : c) check(a[i++] == j);
473 check((size <= c.size()) || (a[c.size()] == null));
474 check(a.getClass() == Integer[].class);
475 }
476
477 check(c.equals(c));
478 if (c instanceof Serializable) {
479 //System.out.printf("Serializing %s%n", c.getClass().getName());
480 try {
481 Object clone = serialClone(c);
482 equal(c instanceof Serializable,
483 clone instanceof Serializable);
939
940 oneElement(c);
941 try {
942 c.containsAll(null);
943 fail("Expected NullPointerException");
944 }
945 catch (NullPointerException e) { pass(); }
946 catch (Throwable t) { unexpected(t); }
947 }
948 }
949
950 //----------------------------------------------------------------
951 // Map
952 //----------------------------------------------------------------
953 private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
954 check(m.keySet().size() == m.entrySet().size());
955 check(m.keySet().size() == m.size());
956 checkFunctionalInvariants(m.keySet());
957 checkFunctionalInvariants(m.values());
958 check(m.size() != 0 ^ m.isEmpty());
959 check(! m.containsKey(ABSENT_VALUE));
960
961 if (m instanceof Serializable) {
962 //System.out.printf("Serializing %s%n", m.getClass().getName());
963 try {
964 Object clone = serialClone(m);
965 equal(m instanceof Serializable,
966 clone instanceof Serializable);
967 equal(m, clone);
968 } catch (Error xxx) {
969 if (! (xxx.getCause() instanceof NotSerializableException))
970 throw xxx;
971 }
972 }
973 }
974
975 private static void testMap(Map<Integer,Integer> m) {
976 System.out.println("\n==> " + m.getClass().getName());
977
978 if (m instanceof ConcurrentMap)
979 testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
980
981 if (m instanceof NavigableMap) {
982 System.out.println("NavigableMap tests...");
983
984 NavigableMap<Integer,Integer> nm =
985 (NavigableMap<Integer,Integer>) m;
986 testNavigableMapRemovers(nm);
987 testNavigableMap(nm);
988 testNavigableMap(nm.headMap(6, false));
989 testNavigableMap(nm.headMap(5, true));
990 testNavigableMap(nm.tailMap(0, false));
991 testNavigableMap(nm.tailMap(1, true));
992 testNavigableMap(nm.subMap(1, true, 6, false));
1002
1003 if (supportsPut(m)) {
1004 try {
1005 check(m.put(3333, 77777) == null);
1006 check(m.put(9134, 74982) == null);
1007 check(m.get(9134) == 74982);
1008 check(m.put(9134, 1382) == 74982);
1009 check(m.get(9134) == 1382);
1010 check(m.size() == 2);
1011 checkFunctionalInvariants(m);
1012 checkNPEConsistency(m);
1013 }
1014 catch (Throwable t) { unexpected(t); }
1015 }
1016 }
1017
1018 private static boolean supportsPut(Map<Integer,Integer> m) {
1019 // We're asking for .equals(...) semantics
1020 if (m instanceof IdentityHashMap) return false;
1021
1022 try { check(m.put(ABSENT_VALUE,12735) == null); }
1023 catch (UnsupportedOperationException t) { return false; }
1024 catch (Throwable t) { unexpected(t); }
1025
1026 try {
1027 check(m.containsKey(ABSENT_VALUE));
1028 check(m.remove(ABSENT_VALUE) != null);
1029 } catch (Throwable t) { unexpected(t); }
1030 return true;
1031 }
1032
1033 private static boolean supportsClear(Map<?,?> m) {
1034 try { m.clear(); }
1035 catch (UnsupportedOperationException t) { return false; }
1036 catch (Throwable t) { unexpected(t); }
1037 return true;
1038 }
1039
1040 //----------------------------------------------------------------
1041 // ConcurrentMap
1042 //----------------------------------------------------------------
1043 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
1044 System.out.println("ConcurrentMap tests...");
1045
1046 try {
1047 clear(m);
1048
|