29 * @run main/othervm -XX:+IgnoreUnrecognizedVMOptions -XX:+EliminateAutoBox -XX:AutoBoxCacheMax=20000 LockStep
30 * @run main/othervm -XX:+IgnoreUnrecognizedVMOptions -XX:+EliminateAutoBox -XX:AutoBoxCacheMax=20000 -Dthorough=true LockStep
31 * @author Martin Buchholz
32 * @key randomness
33 */
34
35 import java.io.ByteArrayInputStream;
36 import java.io.ByteArrayOutputStream;
37 import java.io.IOException;
38 import java.io.InputStream;
39 import java.io.NotSerializableException;
40 import java.io.ObjectInputStream;
41 import java.io.ObjectOutputStream;
42 import java.io.Serializable;
43 import java.util.Arrays;
44 import java.util.Collection;
45 import java.util.Collections;
46 import java.util.Comparator;
47 import java.util.HashSet;
48 import java.util.Iterator;
49 import java.util.List;
50 import java.util.Map;
51 import java.util.NavigableMap;
52 import java.util.NavigableSet;
53 import java.util.NoSuchElementException;
54 import java.util.Random;
55 import java.util.Set;
56 import java.util.TreeMap;
57 import java.util.TreeSet;
58 import java.util.concurrent.ConcurrentSkipListMap;
59 import java.util.concurrent.ConcurrentSkipListSet;
60
61 import static java.util.Collections.reverseOrder;
62 import static java.util.Collections.singleton;
63 import static java.util.Collections.singletonMap;
64
65 @SuppressWarnings("unchecked")
66 public class LockStep {
67 static final int DEFAULT_SIZE = 5;
68 static int size; // Running time is O(size**2)
69
70 static int intArg(String[] args, int i, int defaultValue) {
71 return args.length > i ? Integer.parseInt(args[i]) : defaultValue;
72 }
73
74 // Pass -Dthorough=true for more exhaustive testing
75 static final boolean thorough = Boolean.getBoolean("thorough");
76
77 static boolean maybe(int n) { return rnd.nextInt(n) == 0; }
78
79 static void realMain(String[] args) {
80 size = intArg(args, 0, DEFAULT_SIZE);
81
82 lockSteps(new TreeMap(),
83 new ConcurrentSkipListMap());
84 lockSteps(new TreeMap(),
85 Collections.checkedNavigableMap(new TreeMap(), Integer.class, Integer.class));
86 lockSteps(new TreeMap(),
87 Collections.synchronizedNavigableMap(new TreeMap()));
88 lockSteps(new TreeMap(reverseOrder()),
89 new ConcurrentSkipListMap(reverseOrder()));
90
91 lockSteps(new TreeSet(),
92 new ConcurrentSkipListSet());
93 lockSteps(new TreeSet(),
94 Collections.checkedNavigableSet(new TreeSet(), Integer.class));
95 lockSteps(new TreeSet(),
96 Collections.synchronizedNavigableSet(new TreeSet()));
97 lockSteps(new TreeSet(reverseOrder()),
98 new ConcurrentSkipListSet(reverseOrder()));
99 }
100
101 static void lockSteps(NavigableMap m1, NavigableMap m2) {
102 if (maybe(4)) m1 = serialClone(m1);
103 if (maybe(4)) m2 = serialClone(m2);
104 lockStep(m1,
105 m2);
106 lockStep(m1.descendingMap(),
107 m2.descendingMap());
108 lockStep(fullSubMap(m1),
109 fullSubMap(m2));
110 lockStep(fullSubMap(m1.descendingMap()),
111 fullSubMap(m2.descendingMap()));
112 lockStep(fullHeadMap(m1),
113 fullHeadMap(m2));
114 lockStep(fullHeadMap(m1.descendingMap()),
115 fullHeadMap(m2.descendingMap()));
116 lockStep(fullTailMap(m1),
117 fullTailMap(m2));
118 lockStep(fullTailMap(m1.descendingMap()),
119 fullTailMap(m2.descendingMap()));
120 }
121
122 static void lockSteps(NavigableSet s1, NavigableSet s2) {
123 if (maybe(4)) s1 = serialClone(s1);
124 if (maybe(4)) s2 = serialClone(s2);
125 lockStep(s1,
126 s2);
127 lockStep(s1.descendingSet(),
128 s2.descendingSet());
129 lockStep(fullSubSet(s1),
130 fullSubSet(s2));
131 lockStep(fullSubSet(s1.descendingSet()),
132 fullSubSet(s2.descendingSet()));
133 lockStep(fullHeadSet(s1),
134 fullHeadSet(s2));
135 lockStep(fullHeadSet(s1.descendingSet()),
136 fullHeadSet(s2.descendingSet()));
137 lockStep(fullTailSet(s1),
138 fullTailSet(s2));
139 lockStep(fullTailSet(s1.descendingSet()),
140 fullTailSet(s2.descendingSet()));
141 }
142
143 static boolean isAscending(NavigableMap m) {
144 Comparator cmp = m.comparator();
145 return (cmp == null || cmp.compare(1, 2) < 0);
146 }
147
148 static NavigableMap fullSubMap(NavigableMap m) {
149 return isAscending(m)
150 ? m.subMap(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)
151 : m.subMap(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);
152 }
153
154 static NavigableMap fullHeadMap(NavigableMap m) {
155 return isAscending(m)
156 ? m.headMap(Integer.MAX_VALUE, true)
157 : m.headMap(Integer.MIN_VALUE, true);
158 }
159
160 static NavigableMap fullTailMap(NavigableMap m) {
161 return isAscending(m)
162 ? m.tailMap(Integer.MIN_VALUE, true)
163 : m.tailMap(Integer.MAX_VALUE, true);
164 }
165
166 static boolean isAscending(NavigableSet s) {
167 Comparator cmp = s.comparator();
168 return (cmp == null || cmp.compare(1, 2) < 0);
169 }
170
171 static NavigableSet fullSubSet(NavigableSet s) {
172 return isAscending(s)
173 ? s.subSet(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)
174 : s.subSet(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);
175 }
176
177 static NavigableSet fullHeadSet(NavigableSet s) {
178 return isAscending(s)
179 ? s.headSet(Integer.MAX_VALUE, true)
180 : s.headSet(Integer.MIN_VALUE, true);
181 }
182
183 static NavigableSet fullTailSet(NavigableSet s) {
184 return isAscending(s)
185 ? s.tailSet(Integer.MIN_VALUE, true)
186 : s.tailSet(Integer.MAX_VALUE, true);
187 }
188
189 static void testEmptyCollection(Collection<?> c) {
190 check(c.isEmpty());
191 equal(c.size(), 0);
192 equal(c.toString(),"[]");
193 equal(c.toArray().length, 0);
194 equal(c.toArray(new Object[0]).length, 0);
195
196 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
197 equal(c.toArray(a), a);
198 equal(a[0], null);
199 check(! c.iterator().hasNext());
200 }
201
202 static void testEmptySet(Set<?> c) {
203 testEmptyCollection(c);
214 testEmptySet(m.entrySet());
215 testEmptyCollection(m.values());
216 }
217
218 static final Random rnd;
219
220 static {
221 // sufficiently random for this test
222 long seed = System.nanoTime();
223 System.out.println(LockStep.class.getCanonicalName() + ": Trial random seed: " + seed );
224
225 rnd = new Random(seed);
226 }
227
228 static void equalNext(final Iterator<?> it, Object expected) {
229 if (maybe(2))
230 check(it.hasNext());
231 equal(it.next(), expected);
232 }
233
234 static Comparator comparator(NavigableSet s) {
235 Comparator cmp = s.comparator();
236 return cmp != null ? cmp : new Comparator() {
237 public int compare(Object o1, Object o2) {
238 return ((Comparable) o1).compareTo(o2); }};
239 }
240
241 static Comparator comparator(NavigableMap m) {
242 Comparator cmp = m.comparator();
243 return cmp != null ? cmp : new Comparator() {
244 public int compare(Object o1, Object o2) {
245 return ((Comparable) o1).compareTo(o2); }};
246 }
247
248 static void checkNavigableSet(final NavigableSet s) {
249 if (s.comparator() == null)
250 check(s.descendingSet().descendingSet().comparator() == null);
251 equal(s.isEmpty(), s.size() == 0);
252 equal2(s, s.descendingSet());
253 if (maybe(4) && s instanceof Serializable) {
254 try {
255 equal2(s, serialClone(s));
256 } catch (RuntimeException uhoh) {
257 if (!(uhoh.getCause() instanceof NotSerializableException)) {
258 throw uhoh;
259 }
260 }
261 }
262 Comparator cmp = comparator(s);
263 if (s.isEmpty()) {
264 THROWS(NoSuchElementException.class,
265 () -> s.first(),
266 () -> s.last());
267 equal(null, s.lower(1));
268 equal(null, s.floor(1));
269 equal(null, s.ceiling(1));
270 equal(null, s.higher(1));
271 } else {
272 Object a = s.first();
273 Object z = s.last();
274 equal(s.lower(a), null);
275 equal(s.higher(z), null);
276 equal2(s, s.tailSet(a));
277 equal2(s, s.headSet(z, true));
278 equal2(s, s.subSet(a, true, z, true));
279
280 testEmptySet(s.subSet(a, true, a, false));
281 testEmptySet(s.subSet(z, true, z, false));
282 testEmptySet(s.headSet(a, false));
283 testEmptySet(s.tailSet(z, false));
284
285 equal2(s.headSet(a, true), singleton(a));
286 equal2(s.tailSet(z, true), singleton(z));
287 }
288 Iterator[] its = new Iterator[] {
289 s.iterator(),
290 s.descendingSet().descendingSet().iterator(),
291 };
292 for (final Iterator it : its)
293 if (maybe(4))
294 THROWS(IllegalStateException.class, () -> it.remove());
295 Object prev = null;
296 for (Object e : s) {
297 check(s.contains(e));
298 for (Iterator it : its) equalNext(it, e);
299 equal(e, s.ceiling(e));
300 equal(e, s.floor(e));
301 check(s.higher(e) == null || cmp.compare(e, s.higher(e)) < 0);
302 equal(s.lower(e), prev);
303 if (prev == null) {
304 } else {
305 check(cmp.compare(prev, e) < 0);
306 }
307 prev = e;
308 }
309 for (final Iterator it : its) {
310 if (maybe(2))
311 check(! it.hasNext());
312 Fun fun = () -> it.next();
313 THROWS(NoSuchElementException.class, fun, fun, fun);
314 }
315 }
316
317 static void equalIterators(final Iterator<?> it1,
318 final Iterator<?> it2) {
319 while (it1.hasNext()) {
320 if (maybe(2))
321 check(it2.hasNext());
322 equal(it1.next(), it2.next());
323 }
324 check(! it2.hasNext());
325 }
326
327 static void equalSetsLeaf(final Set s1, final Set s2) {
328 equal2(s1, s2);
329 equal( s1.size(), s2.size());
330 equal( s1.isEmpty(), s2.isEmpty());
331 equal( s1.hashCode(), s2.hashCode());
332 equal( s1.toString(), s2.toString());
333 equal( s1.containsAll(s2), s2.containsAll(s1));
334 }
335
336 static void equalNavigableSetsLeaf(final NavigableSet s1,
337 final NavigableSet s2) {
338 equal2(s1, s2);
339 equal( s1.size(), s2.size());
340 equal( s1.isEmpty(), s2.isEmpty());
341 equal( s1.hashCode(), s2.hashCode());
342 equal( s1.toString(), s2.toString());
343 if (! s1.isEmpty()) {
344 equal(s1.first(), s2.first());
345 equal(s1.last(), s2.last());
346 }
347 equalIterators(s1.iterator(), s2.iterator());
348 equalIterators(s1.descendingIterator(), s2.descendingIterator());
349 checkNavigableSet(s1);
350 checkNavigableSet(s2);
351 }
352
353 static void equalNavigableSets(final NavigableSet s1,
354 final NavigableSet s2) {
355 equalNavigableSetsLeaf(s1, s2);
356 equalNavigableSetsLeaf(s1.descendingSet(), s2.descendingSet());
357 equalNavigableSetsLeaf(s1.descendingSet().descendingSet(), s2);
358 Object min = s1.isEmpty() ? Integer.MIN_VALUE : s1.first();
359 Object max = s2.isEmpty() ? Integer.MAX_VALUE : s2.last();
360 if (s1.comparator() != null &&
361 s1.comparator().compare(min, max) > 0) {
362 Object tmp = min; min = max; max = tmp;
363 }
364
365 equalNavigableSetsLeaf(s1.subSet(min, true, max, true),
366 s2.subSet(min, true, max, true));
367 equalNavigableSetsLeaf(s1.tailSet(min, true),
368 s2.tailSet(min, true));
369 equalNavigableSetsLeaf(s1.headSet(max, true),
370 s2.headSet(max, true));
371 equalNavigableSetsLeaf((NavigableSet) s1.subSet(min, max),
372 (NavigableSet) s2.subSet(min, max));
373 equalNavigableSetsLeaf((NavigableSet) s1.tailSet(min),
374 (NavigableSet) s2.tailSet(min));
375 equalNavigableSetsLeaf((NavigableSet) s1.headSet(max),
376 (NavigableSet) s2.headSet(max));
377 }
378
379 // Destined for a Collections.java near you?
380 static <T> T[] concat(T[]... arrays) {
381 int len = 0;
382 for (int i = 0; i < arrays.length; i++)
383 len += arrays[i].length;
384 T[] a = (T[])java.lang.reflect.Array
385 .newInstance(arrays[0].getClass().getComponentType(), len);
386 int k = 0;
387 for (int i = 0; i < arrays.length; i++) {
388 T[] array = arrays[i];
389 System.arraycopy(array, 0, a, k, array.length);
390 k += array.length;
391 }
392 return a;
393 }
394
395 static void checkNavigableMap(final NavigableMap m) {
396 if (m.comparator() == null) {
397 check(m.descendingMap().descendingMap().comparator() == null);
398 check(m.descendingKeySet().descendingSet().comparator() == null);
399 }
400 equal(m.isEmpty(), m.size() == 0);
401 equal2(m, m.descendingMap());
402 if (maybe(4))
403 equal2(m, serialClone(m));
404 equal2(m.keySet(), m.descendingKeySet());
405 Comparator cmp = comparator(m);
406 if (m.isEmpty()) {
407 THROWS(NoSuchElementException.class,
408 () -> m.firstKey(),
409 () -> m.lastKey());
410 equal(null, m.firstEntry());
411 equal(null, m.lastEntry());
412 equal(null, m.pollFirstEntry());
413 equal(null, m.pollLastEntry());
414 equal(null, m.lowerKey(1));
415 equal(null, m.floorKey(1));
416 equal(null, m.ceilingKey(1));
417 equal(null, m.higherKey(1));
418 equal(null, m.lowerEntry(1));
419 equal(null, m.floorEntry(1));
420 equal(null, m.ceilingEntry(1));
421 equal(null, m.higherEntry(1));
422 } else {
423 Object a = m.firstKey();
424 Object z = m.lastKey();
425 equal(m.lowerKey(a), null);
426 equal(m.higherKey(z), null);
427 equal(a, m.firstEntry().getKey());
428 equal(z, m.lastEntry().getKey());
429 equal2(m, m.tailMap(a));
430 equal2(m, m.headMap(z, true));
431 equal2(m, m.subMap(a, true, z, true));
432
433 testEmptyMap(m.subMap(a, true, a, false));
434 testEmptyMap(m.subMap(z, true, z, false));
435 testEmptyMap(m.headMap(a, false));
436 testEmptyMap(m.tailMap(z, false));
437
438 equal2(m.headMap(a, true), singletonMap(a, m.get(a)));
439 equal2(m.tailMap(z, true), singletonMap(z, m.get(z)));
440 }
441
442 Iterator[] kits = new Iterator[] {
443 m.keySet().iterator(),
444 m.descendingMap().descendingKeySet().iterator(),
445 m.descendingKeySet().descendingSet().iterator(),
446 };
447 Iterator[] vits = new Iterator[] {
448 m.values().iterator(),
449 m.descendingMap().descendingMap().values().iterator(),
450 };
451 Iterator[] eits = new Iterator[] {
452 m.entrySet().iterator(),
453 m.descendingMap().descendingMap().entrySet().iterator(),
454 };
455 Iterator[] its = concat(kits, vits, eits);
456 for (final Iterator it : its)
457 if (maybe(4))
458 THROWS(IllegalStateException.class, () -> it.remove());
459 Map.Entry prev = null;
460 for (Map.Entry e : (Set<Map.Entry>) m.entrySet()) {
461 Object k = e.getKey();
462 Object v = e.getValue();
463 check(m.containsKey(k));
464 check(m.containsValue(v));
465 for (Iterator kit : kits) equalNext(kit, k);
466 for (Iterator vit : vits) equalNext(vit, v);
467 for (Iterator eit : eits) equalNext(eit, e);
468 equal(k, m.ceilingKey(k));
469 equal(k, m.ceilingEntry(k).getKey());
470 equal(k, m.floorKey(k));
471 equal(k, m.floorEntry(k).getKey());
472 check(m.higherKey(k) == null || cmp.compare(k, m.higherKey(k)) < 0);
473 check(m.lowerKey(k) == null || cmp.compare(k, m.lowerKey(k)) > 0);
474 equal(m.lowerEntry(k), prev);
475 if (prev == null) {
476 equal(m.lowerKey(k), null);
477 } else {
478 equal(m.lowerKey(k), prev.getKey());
479 check(cmp.compare(prev.getKey(), e.getKey()) < 0);
480 }
481 prev = e;
482 }
483 for (final Iterator it : its) {
484 if (maybe(2))
485 check(! it.hasNext());
486 Fun fun = () -> it.next();
487 THROWS(NoSuchElementException.class, fun, fun, fun);
488 }
489 }
490
491 static void equalNavigableMapsLeaf(final NavigableMap m1,
492 final NavigableMap m2) {
493 equal2(m1, m2);
494 equal( m1.size(), m2.size());
495 equal( m1.isEmpty(), m2.isEmpty());
496 equal( m1.hashCode(), m2.hashCode());
497 equal( m1.toString(), m2.toString());
498 equal2(m1.firstEntry(), m2.firstEntry());
499 equal2(m1.lastEntry(), m2.lastEntry());
500 checkNavigableMap(m1);
501 checkNavigableMap(m2);
502 }
503
504 static void equalNavigableMaps(NavigableMap m1,
505 NavigableMap m2) {
506 equalNavigableMapsLeaf(m1, m2);
507 equalSetsLeaf(m1.keySet(), m2.keySet());
508 equalNavigableSets(m1.navigableKeySet(),
509 m2.navigableKeySet());
510 equalNavigableSets(m1.descendingKeySet(),
511 m2.descendingKeySet());
512 equal2(m1.entrySet(),
513 m2.entrySet());
514 equalNavigableMapsLeaf(m1.descendingMap(),
515 m2.descendingMap());
516 equalNavigableMapsLeaf(m1.descendingMap().descendingMap(),
517 m2);
518 equalNavigableSetsLeaf((NavigableSet) m1.descendingMap().keySet(),
519 (NavigableSet) m2.descendingMap().keySet());
520 equalNavigableSetsLeaf(m1.descendingMap().descendingKeySet(),
521 m2.descendingMap().descendingKeySet());
522 equal2(m1.descendingMap().entrySet(),
523 m2.descendingMap().entrySet());
524
525 //----------------------------------------------------------------
526 // submaps
527 //----------------------------------------------------------------
528 Object min = Integer.MIN_VALUE;
529 Object max = Integer.MAX_VALUE;
530 if (m1.comparator() != null
531 && m1.comparator().compare(min, max) > 0) {
532 Object tmp = min; min = max; max = tmp;
533 }
534 switch (rnd.nextInt(6)) {
535 case 0:
536 equalNavigableMapsLeaf(m1.subMap(min, true, max, true),
537 m2.subMap(min, true, max, true));
538 break;
539 case 1:
540 equalNavigableMapsLeaf(m1.tailMap(min, true),
541 m2.tailMap(min, true));
542 break;
543 case 2:
544 equalNavigableMapsLeaf(m1.headMap(max, true),
545 m2.headMap(max, true));
546 break;
547 case 3:
548 equalNavigableMapsLeaf((NavigableMap) m1.subMap(min, max),
549 (NavigableMap) m2.subMap(min, max));
550 break;
551 case 4:
552 equalNavigableMapsLeaf((NavigableMap) m1.tailMap(min),
553 (NavigableMap) m2.tailMap(min));
554 break;
555 case 5:
556 equalNavigableMapsLeaf((NavigableMap) m1.headMap(max),
557 (NavigableMap) m2.headMap(max));
558 break;
559 }
560 }
561
562 abstract static class MapFrobber { abstract void frob(NavigableMap m); }
563 abstract static class SetFrobber { abstract void frob(NavigableSet m); }
564
565 static MapFrobber randomAdder(NavigableMap m) {
566 final Integer k = unusedKey(m);
567 final MapFrobber[] randomAdders = {
568 new MapFrobber() {void frob(NavigableMap m) {
569 equal(m.put(k, k+1), null);
570 equal(m.get(k), k+1);
571 if (maybe(4)) {
572 equal(m.put(k, k+1), k+1);
573 equal(m.get(k), k+1);}}},
574 new MapFrobber() {void frob(NavigableMap m) {
575 m.descendingMap().put(k, k+1);
576 equal(m.get(k), k+1);}},
577 new MapFrobber() {void frob(NavigableMap m) {
578 m.tailMap(k,true).headMap(k,true).put(k,k+1);}},
579 new MapFrobber() {void frob(NavigableMap m) {
580 m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}}
581 };
582 return new MapFrobber() {void frob(NavigableMap m) {
583 randomAdders[rnd.nextInt(randomAdders.length)].frob(m);
584 if (maybe(2)) equal(m.get(k), k+1);
585 if (maybe(4)) {
586 equal(m.put(k, k+1), k+1);
587 equal(m.get(k), k+1);}}};
588 }
589
590 static SetFrobber randomAdder(NavigableSet s) {
591 final Integer e = unusedElt(s);
592 final SetFrobber[] randomAdders = {
593 new SetFrobber() {void frob(NavigableSet s) {
594 check(s.add(e));}},
595 new SetFrobber() {void frob(NavigableSet s) {
596 s.descendingSet().add(e);}},
597 new SetFrobber() {void frob(NavigableSet s) {
598 s.tailSet(e,true).headSet(e,true).add(e);}},
599 new SetFrobber() {void frob(NavigableSet s) {
600 s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}}
601 };
602 return new SetFrobber() {void frob(NavigableSet s) {
603 if (maybe(2)) check(! s.contains(e));
604 randomAdders[rnd.nextInt(randomAdders.length)].frob(s);
605 if (maybe(2)) check(! s.add(e));
606 if (maybe(2)) check(s.contains(e));}};
607 }
608
609 static Integer unusedElt(NavigableSet s) {
610 Integer e;
611 do { e = rnd.nextInt(1024); }
612 while (s.contains(e));
613 return e;
614 }
615
616 static Integer unusedKey(NavigableMap m) {
617 Integer k;
618 do { k = rnd.nextInt(1024); }
619 while (m.containsKey(k));
620 return k;
621 }
622
623 static Integer usedKey(NavigableMap m) {
624 Integer x = rnd.nextInt(1024);
625 Integer floor = (Integer) m.floorKey(x);
626 Integer ceiling = (Integer) m.ceilingKey(x);
627 if (floor != null) return floor;
628 check(ceiling != null);
629 return ceiling;
630 }
631
632 static Integer usedElt(NavigableSet s) {
633 Integer x = rnd.nextInt(1024);
634 Integer floor = (Integer) s.floor(x);
635 Integer ceiling = (Integer) s.ceiling(x);
636 if (floor != null) return floor;
637 check(ceiling != null);
638 return ceiling;
639 }
640
641 static void checkUnusedKey(NavigableMap m, Object k) {
642 check(! m.containsKey(k));
643 equal(m.get(k), null);
644 if (maybe(2))
645 equal(m.remove(k), null);
646 }
647
648 static void checkUnusedElt(NavigableSet s, Object e) {
649 if (maybe(2))
650 check(! s.contains(e));
651 if (maybe(2)) {
652 check(s.ceiling(e) != e);
653 check(s.floor(e) != e);
654 }
655 if (maybe(2))
656 check(! s.remove(e));
657 }
658
659 static Fun remover(final Iterator it) {
660 return () -> it.remove();
661 }
662
663 static MapFrobber randomRemover(NavigableMap m) {
664 final Integer k = usedKey(m);
665 final MapFrobber[] randomRemovers = {
666 new MapFrobber() {void frob(NavigableMap m) {
667 Map.Entry e = m.firstEntry();
668 equal(m.pollFirstEntry(), e);
669 checkUnusedKey(m, e.getKey());}},
670 new MapFrobber() {void frob(NavigableMap m) {
671 Map.Entry e = m.lastEntry();
672 equal(m.pollLastEntry(), e);
673 checkUnusedKey(m, e.getKey());}},
674 new MapFrobber() {void frob(NavigableMap m) {
675 check(m.remove(k) != null);
676 checkUnusedKey(m, k);}},
677 new MapFrobber() {void frob(NavigableMap m) {
678 m.subMap(k, true, k, true).clear();
679 checkUnusedKey(m, k);}},
680 new MapFrobber() {void frob(NavigableMap m) {
681 m.descendingMap().subMap(k, true, k, true).clear();
682 checkUnusedKey(m, k);}},
683 new MapFrobber() {void frob(NavigableMap m) {
684 final Iterator it = m.keySet().iterator();
685 while (it.hasNext())
686 if (it.next().equals(k)) {
687 it.remove();
688 if (maybe(2))
689 THROWS(IllegalStateException.class,
690 () -> it.remove());
691 }
692 checkUnusedKey(m, k);}},
693 new MapFrobber() {void frob(NavigableMap m) {
694 final Iterator it = m.navigableKeySet().descendingIterator();
695 while (it.hasNext())
696 if (it.next().equals(k)) {
697 it.remove();
698 if (maybe(2))
699 THROWS(IllegalStateException.class,
700 () -> it.remove());
701 }
702 checkUnusedKey(m, k);}},
703 new MapFrobber() {void frob(NavigableMap m) {
704 final Iterator<Map.Entry> it = m.entrySet().iterator();
705 while (it.hasNext())
706 if (it.next().getKey().equals(k)) {
707 it.remove();
708 if (maybe(2))
709 THROWS(IllegalStateException.class, remover(it));
710 }
711 checkUnusedKey(m, k);}},
712 };
713
714 return randomRemovers[rnd.nextInt(randomRemovers.length)];
715 }
716
717 static SetFrobber randomRemover(NavigableSet s) {
718 final Integer e = usedElt(s);
719
720 final SetFrobber[] randomRemovers = {
721 new SetFrobber() {void frob(NavigableSet s) {
722 Object e = s.first();
723 equal(s.pollFirst(), e);
724 checkUnusedElt(s, e);}},
725 new SetFrobber() {void frob(NavigableSet s) {
726 Object e = s.last();
727 equal(s.pollLast(), e);
728 checkUnusedElt(s, e);}},
729 new SetFrobber() {void frob(NavigableSet s) {
730 check(s.remove(e));
731 checkUnusedElt(s, e);}},
732 new SetFrobber() {void frob(NavigableSet s) {
733 s.subSet(e, true, e, true).clear();
734 checkUnusedElt(s, e);}},
735 new SetFrobber() {void frob(NavigableSet s) {
736 s.descendingSet().subSet(e, true, e, true).clear();
737 checkUnusedElt(s, e);}},
738 new SetFrobber() {void frob(NavigableSet s) {
739 final Iterator it = s.iterator();
740 while (it.hasNext())
741 if (it.next().equals(e)) {
742 it.remove();
743 if (maybe(2))
744 THROWS(IllegalStateException.class,
745 () -> it.remove());
746 }
747 checkUnusedElt(s, e);}},
748 new SetFrobber() {void frob(NavigableSet s) {
749 final Iterator it = s.descendingSet().iterator();
750 while (it.hasNext())
751 if (it.next().equals(e)) {
752 it.remove();
753 if (maybe(2))
754 THROWS(IllegalStateException.class,
755 () -> it.remove());
756 }
757 checkUnusedElt(s, e);}},
758 new SetFrobber() {void frob(NavigableSet s) {
759 final Iterator it = s.descendingIterator();
760 while (it.hasNext())
761 if (it.next().equals(e)) {
762 it.remove();
763 if (maybe(2))
764 THROWS(IllegalStateException.class,
765 () -> it.remove());
766 }
767 checkUnusedElt(s, e);}}
768 };
769
770 return randomRemovers[rnd.nextInt(randomRemovers.length)];
771 }
772
773 static void lockStep(NavigableMap m1,
774 NavigableMap m2) {
775 if (! (thorough || maybe(3))) return;
776 if (maybe(4)) m1 = serialClone(m1);
777 if (maybe(4)) m2 = serialClone(m2);
778
779 List<NavigableMap> maps = Arrays.asList(m1, m2);
780 for (NavigableMap m : maps) testEmptyMap(m);
781 final Set<Integer> ints = new HashSet<>();
782 while (ints.size() < size)
783 ints.add(rnd.nextInt(1024));
784 final Integer[] elts = ints.toArray(new Integer[size]);
785 for (int i = 0; i < size; i++) {
786 MapFrobber adder = randomAdder(m1);
787 for (final NavigableMap m : maps) {
788 adder.frob(m);
789 equal(m.size(), i+1);
790 }
791 equalNavigableMaps(m1, m2);
792 }
793 for (final NavigableMap m : maps) {
794 final Object e = usedKey(m);
795 THROWS(IllegalArgumentException.class,
796 () -> {m.subMap(e,true,e,false)
797 .subMap(e,true,e,true);},
798 () -> {m.subMap(e,false,e,true)
799 .subMap(e,true,e,true);},
800 () -> m.tailMap(e,false).tailMap(e,true),
801 () -> m.headMap(e,false).headMap(e,true));
802 }
803 //System.out.printf("%s%n", m1);
804 for (int i = size; i > 0; i--) {
805 MapFrobber remover = randomRemover(m1);
806 for (final NavigableMap m : maps) {
807 remover.frob(m);
808 equal(m.size(), i-1);
809 }
810 equalNavigableMaps(m1, m2);
811 }
812 for (NavigableMap m : maps) testEmptyMap(m);
813 }
814
815 static void lockStep(NavigableSet s1,
816 NavigableSet s2) {
817 if (! (thorough || maybe(3))) return;
818 if (maybe(4)) s1 = serialClone(s1);
819 if (maybe(4)) s2 = serialClone(s2);
820
821 List<NavigableSet> sets = Arrays.asList(s1, s2);
822 for (NavigableSet s : sets) testEmptySet(s);
823 final Set<Integer> ints = new HashSet<>();
824 while (ints.size() < size)
825 ints.add(rnd.nextInt(1024));
826 final Integer[] elts = ints.toArray(new Integer[size]);
827 for (int i = 0; i < size; i++) {
828 SetFrobber adder = randomAdder(s1);
829 for (final NavigableSet s : sets) {
830 adder.frob(s);
831 equal(s.size(), i+1);
832 }
833 equalNavigableSets(s1, s2);
834 }
835 for (final NavigableSet s : sets) {
836 final Object e = usedElt(s);
837 THROWS(IllegalArgumentException.class,
838 () -> {s.subSet(e,true,e,false)
839 .subSet(e,true,e,true);},
840 () -> {s.subSet(e,false,e,true)
841 .subSet(e,true,e,true);},
842 () -> s.tailSet(e,false).tailSet(e,true),
843 () -> s.headSet(e,false).headSet(e,true));
844 }
845 //System.out.printf("%s%n", s1);
846 for (int i = size; i > 0; i--) {
847 SetFrobber remover = randomRemover(s1);
848 for (final NavigableSet s : sets) {
849 remover.frob(s);
850 equal(s.size(), i-1);
851 }
852 equalNavigableSets(s1, s2);
853 }
854 for (NavigableSet s : sets) testEmptySet(s);
855 }
856
857 //--------------------- Infrastructure ---------------------------
858 static volatile int passed = 0, failed = 0;
859 static void pass() { passed++; }
860 static void fail() { failed++; Thread.dumpStack(); }
861 static void fail(String msg) { System.out.println(msg); fail(); }
862 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
863 static void check(boolean cond) { if (cond) pass(); else fail(); }
864 static void equal(Object x, Object y) {
865 if (x == null ? y == null : x.equals(y)) pass();
866 else {System.out.println(x + " not equal to " + y); fail();}}
867 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
868 public static void main(String[] args) throws Throwable {
869 try { realMain(args); } catch (Throwable t) { unexpected(t); }
870
871 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
872 if (failed > 0) throw new Exception("Some tests failed");
873 }
874 interface Fun {void f() throws Throwable;}
875 static void THROWS(Class<? extends Throwable> k, Fun... fs) {
876 for (Fun f : fs)
877 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
878 catch (Throwable t) {
879 if (k.isAssignableFrom(t.getClass())) pass();
880 else unexpected(t);}}
881 static byte[] serializedForm(Object obj) {
882 try {
883 ByteArrayOutputStream baos = new ByteArrayOutputStream();
884 new ObjectOutputStream(baos).writeObject(obj);
885 return baos.toByteArray();
|
29 * @run main/othervm -XX:+IgnoreUnrecognizedVMOptions -XX:+EliminateAutoBox -XX:AutoBoxCacheMax=20000 LockStep
30 * @run main/othervm -XX:+IgnoreUnrecognizedVMOptions -XX:+EliminateAutoBox -XX:AutoBoxCacheMax=20000 -Dthorough=true LockStep
31 * @author Martin Buchholz
32 * @key randomness
33 */
34
35 import java.io.ByteArrayInputStream;
36 import java.io.ByteArrayOutputStream;
37 import java.io.IOException;
38 import java.io.InputStream;
39 import java.io.NotSerializableException;
40 import java.io.ObjectInputStream;
41 import java.io.ObjectOutputStream;
42 import java.io.Serializable;
43 import java.util.Arrays;
44 import java.util.Collection;
45 import java.util.Collections;
46 import java.util.Comparator;
47 import java.util.HashSet;
48 import java.util.Iterator;
49 import java.util.Map;
50 import java.util.NavigableMap;
51 import java.util.NavigableSet;
52 import java.util.NoSuchElementException;
53 import java.util.Objects;
54 import java.util.Random;
55 import java.util.Set;
56 import java.util.TreeMap;
57 import java.util.TreeSet;
58 import java.util.concurrent.ConcurrentSkipListMap;
59 import java.util.concurrent.ConcurrentSkipListSet;
60
61 import static java.util.Collections.reverseOrder;
62 import static java.util.Collections.singleton;
63 import static java.util.Collections.singletonMap;
64
65 @SuppressWarnings("unchecked")
66 public class LockStep {
67 static final int DEFAULT_SIZE = 5;
68 static int size; // Running time is O(size**2)
69
70 static int intArg(String[] args, int i, int defaultValue) {
71 return args.length > i ? Integer.parseInt(args[i]) : defaultValue;
72 }
73
74 // Pass -Dthorough=true for more exhaustive testing
75 static final boolean thorough = Boolean.getBoolean("thorough");
76
77 static boolean maybe(int n) { return rnd.nextInt(n) == 0; }
78
79 static void realMain(String[] args) {
80 size = intArg(args, 0, DEFAULT_SIZE);
81
82 lockSteps(new TreeMap<>(),
83 new ConcurrentSkipListMap<>());
84 lockSteps(new TreeMap<>(),
85 Collections.checkedNavigableMap(new TreeMap<>(), Integer.class, Integer.class));
86 lockSteps(new TreeMap<>(),
87 Collections.synchronizedNavigableMap(new TreeMap<>()));
88 lockSteps(new TreeMap<>(reverseOrder()),
89 new ConcurrentSkipListMap<>(reverseOrder()));
90
91 lockSteps(new TreeSet<>(),
92 new ConcurrentSkipListSet<>());
93 lockSteps(new TreeSet<>(),
94 Collections.checkedNavigableSet(new TreeSet<>(), Integer.class));
95 lockSteps(new TreeSet<>(),
96 Collections.synchronizedNavigableSet(new TreeSet<>()));
97 lockSteps(new TreeSet<>(reverseOrder()),
98 new ConcurrentSkipListSet<>(reverseOrder()));
99 }
100
101 static void lockSteps(NavigableMap<Integer, Integer> m1, NavigableMap<Integer, Integer> m2) {
102 if (maybe(4)) m1 = serialClone(m1);
103 if (maybe(4)) m2 = serialClone(m2);
104 lockStep(m1,
105 m2);
106 lockStep(m1.descendingMap(),
107 m2.descendingMap());
108 lockStep(fullSubMap(m1),
109 fullSubMap(m2));
110 lockStep(fullSubMap(m1.descendingMap()),
111 fullSubMap(m2.descendingMap()));
112 lockStep(fullHeadMap(m1),
113 fullHeadMap(m2));
114 lockStep(fullHeadMap(m1.descendingMap()),
115 fullHeadMap(m2.descendingMap()));
116 lockStep(fullTailMap(m1),
117 fullTailMap(m2));
118 lockStep(fullTailMap(m1.descendingMap()),
119 fullTailMap(m2.descendingMap()));
120 }
121
122 static void lockSteps(NavigableSet<Integer> s1, NavigableSet<Integer> s2) {
123 if (maybe(4)) s1 = serialClone(s1);
124 if (maybe(4)) s2 = serialClone(s2);
125 lockStep(s1,
126 s2);
127 lockStep(s1.descendingSet(),
128 s2.descendingSet());
129 lockStep(fullSubSet(s1),
130 fullSubSet(s2));
131 lockStep(fullSubSet(s1.descendingSet()),
132 fullSubSet(s2.descendingSet()));
133 lockStep(fullHeadSet(s1),
134 fullHeadSet(s2));
135 lockStep(fullHeadSet(s1.descendingSet()),
136 fullHeadSet(s2.descendingSet()));
137 lockStep(fullTailSet(s1),
138 fullTailSet(s2));
139 lockStep(fullTailSet(s1.descendingSet()),
140 fullTailSet(s2.descendingSet()));
141 }
142
143 static boolean isAscending(NavigableMap<Integer, Integer> m) {
144 var cmp = m.comparator();
145 return (cmp == null || cmp.compare(1, 2) < 0);
146 }
147
148 static NavigableMap<Integer, Integer> fullSubMap(NavigableMap<Integer, Integer> m) {
149 return isAscending(m)
150 ? m.subMap(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)
151 : m.subMap(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);
152 }
153
154 static NavigableMap<Integer, Integer> fullHeadMap(NavigableMap<Integer, Integer> m) {
155 return isAscending(m)
156 ? m.headMap(Integer.MAX_VALUE, true)
157 : m.headMap(Integer.MIN_VALUE, true);
158 }
159
160 static NavigableMap<Integer, Integer> fullTailMap(NavigableMap<Integer, Integer> m) {
161 return isAscending(m)
162 ? m.tailMap(Integer.MIN_VALUE, true)
163 : m.tailMap(Integer.MAX_VALUE, true);
164 }
165
166 static boolean isAscending(NavigableSet<Integer> s) {
167 var cmp = s.comparator();
168 return (cmp == null || cmp.compare(1, 2) < 0);
169 }
170
171 static NavigableSet<Integer> fullSubSet(NavigableSet<Integer> s) {
172 return isAscending(s)
173 ? s.subSet(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)
174 : s.subSet(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);
175 }
176
177 static NavigableSet<Integer> fullHeadSet(NavigableSet<Integer> s) {
178 return isAscending(s)
179 ? s.headSet(Integer.MAX_VALUE, true)
180 : s.headSet(Integer.MIN_VALUE, true);
181 }
182
183 static NavigableSet<Integer> fullTailSet(NavigableSet<Integer> s) {
184 return isAscending(s)
185 ? s.tailSet(Integer.MIN_VALUE, true)
186 : s.tailSet(Integer.MAX_VALUE, true);
187 }
188
189 static void testEmptyCollection(Collection<?> c) {
190 check(c.isEmpty());
191 equal(c.size(), 0);
192 equal(c.toString(),"[]");
193 equal(c.toArray().length, 0);
194 equal(c.toArray(new Object[0]).length, 0);
195
196 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
197 equal(c.toArray(a), a);
198 equal(a[0], null);
199 check(! c.iterator().hasNext());
200 }
201
202 static void testEmptySet(Set<?> c) {
203 testEmptyCollection(c);
214 testEmptySet(m.entrySet());
215 testEmptyCollection(m.values());
216 }
217
218 static final Random rnd;
219
220 static {
221 // sufficiently random for this test
222 long seed = System.nanoTime();
223 System.out.println(LockStep.class.getCanonicalName() + ": Trial random seed: " + seed );
224
225 rnd = new Random(seed);
226 }
227
228 static void equalNext(final Iterator<?> it, Object expected) {
229 if (maybe(2))
230 check(it.hasNext());
231 equal(it.next(), expected);
232 }
233
234 static Comparator<? super Integer> comparator(NavigableSet<Integer> s) {
235 var cmp = s.comparator();
236 return cmp != null ? cmp : Comparator.naturalOrder();
237 }
238
239 static Comparator<? super Integer> comparator(NavigableMap<Integer, Integer> m) {
240 var cmp = m.comparator();
241 return cmp != null ? cmp : Comparator.naturalOrder();
242 }
243
244 static void checkNavigableSet(final NavigableSet<Integer> s) {
245 if (s.comparator() == null)
246 check(s.descendingSet().descendingSet().comparator() == null);
247 equal(s.isEmpty(), s.size() == 0);
248 equal2(s, s.descendingSet());
249 if (maybe(4) && s instanceof Serializable) {
250 try {
251 equal2(s, serialClone(s));
252 } catch (RuntimeException uhoh) {
253 if (!(uhoh.getCause() instanceof NotSerializableException)) {
254 throw uhoh;
255 }
256 }
257 }
258 var cmp = comparator(s);
259 if (s.isEmpty()) {
260 THROWS(NoSuchElementException.class,
261 () -> s.first(),
262 () -> s.last());
263 equal(null, s.lower(1));
264 equal(null, s.floor(1));
265 equal(null, s.ceiling(1));
266 equal(null, s.higher(1));
267 } else {
268 Integer a = s.first();
269 Integer z = s.last();
270 equal(s.lower(a), null);
271 equal(s.higher(z), null);
272 equal2(s, s.tailSet(a));
273 equal2(s, s.headSet(z, true));
274 equal2(s, s.subSet(a, true, z, true));
275
276 testEmptySet(s.subSet(a, true, a, false));
277 testEmptySet(s.subSet(z, true, z, false));
278 testEmptySet(s.headSet(a, false));
279 testEmptySet(s.tailSet(z, false));
280
281 equal2(s.headSet(a, true), singleton(a));
282 equal2(s.tailSet(z, true), singleton(z));
283 }
284 Iterator<?>[] its = new Iterator[] {
285 s.iterator(),
286 s.descendingSet().descendingSet().iterator(),
287 };
288 for (final Iterator<?> it : its)
289 if (maybe(4))
290 THROWS(IllegalStateException.class, () -> it.remove());
291 Integer prev = null;
292 for (final Integer e : s) {
293 check(s.contains(e));
294 for (Iterator<?> it : its) equalNext(it, e);
295 equal(e, s.ceiling(e));
296 equal(e, s.floor(e));
297 check(s.higher(e) == null || cmp.compare(e, s.higher(e)) < 0);
298 equal(s.lower(e), prev);
299 if (prev != null) {
300 check(cmp.compare(prev, e) < 0);
301 }
302 prev = e;
303 }
304 for (final Iterator<?> it : its) {
305 if (maybe(2))
306 check(! it.hasNext());
307 Fun fun = () -> it.next();
308 THROWS(NoSuchElementException.class, fun, fun, fun);
309 }
310 }
311
312 static void equalIterators(final Iterator<?> it1,
313 final Iterator<?> it2) {
314 while (it1.hasNext()) {
315 if (maybe(2))
316 check(it2.hasNext());
317 equal(it1.next(), it2.next());
318 }
319 check(! it2.hasNext());
320 }
321
322 static void equalSetsLeaf(final Set<?> s1, final Set<?> s2) {
323 equal2(s1, s2);
324 equal( s1.size(), s2.size());
325 equal( s1.isEmpty(), s2.isEmpty());
326 equal( s1.hashCode(), s2.hashCode());
327 equal( s1.toString(), s2.toString());
328 equal( s1.containsAll(s2), s2.containsAll(s1));
329 }
330
331 static void equalNavigableSetsLeaf(final NavigableSet<Integer> s1,
332 final NavigableSet<Integer> s2) {
333 equal2(s1, s2);
334 equal( s1.size(), s2.size());
335 equal( s1.isEmpty(), s2.isEmpty());
336 equal( s1.hashCode(), s2.hashCode());
337 equal( s1.toString(), s2.toString());
338 if (! s1.isEmpty()) {
339 equal(s1.first(), s2.first());
340 equal(s1.last(), s2.last());
341 }
342 equalIterators(s1.iterator(), s2.iterator());
343 equalIterators(s1.descendingIterator(), s2.descendingIterator());
344 checkNavigableSet(s1);
345 checkNavigableSet(s2);
346 }
347
348 static void equalNavigableSets(final NavigableSet<Integer> s1,
349 final NavigableSet<Integer> s2) {
350 equalNavigableSetsLeaf(s1, s2);
351 equalNavigableSetsLeaf(s1.descendingSet(), s2.descendingSet());
352 equalNavigableSetsLeaf(s1.descendingSet().descendingSet(), s2);
353 Integer min = s1.isEmpty() ? Integer.MIN_VALUE : s1.first();
354 Integer max = s2.isEmpty() ? Integer.MAX_VALUE : s2.last();
355 if (s1.comparator() != null &&
356 s1.comparator().compare(min, max) > 0) {
357 Integer tmp = min; min = max; max = tmp;
358 }
359
360 equalNavigableSetsLeaf(s1.subSet(min, true, max, true),
361 s2.subSet(min, true, max, true));
362 equalNavigableSetsLeaf(s1.tailSet(min, true),
363 s2.tailSet(min, true));
364 equalNavigableSetsLeaf(s1.headSet(max, true),
365 s2.headSet(max, true));
366 equalNavigableSetsLeaf((NavigableSet<Integer>) s1.subSet(min, max),
367 (NavigableSet<Integer>) s2.subSet(min, max));
368 equalNavigableSetsLeaf((NavigableSet<Integer>) s1.tailSet(min),
369 (NavigableSet<Integer>) s2.tailSet(min));
370 equalNavigableSetsLeaf((NavigableSet<Integer>) s1.headSet(max),
371 (NavigableSet<Integer>) s2.headSet(max));
372 }
373
374 // Destined for a Collections.java near you?
375 static <T> T[] concat(T[]... arrays) {
376 int len = 0;
377 for (T[] arr : arrays) len += arr.length;
378 T[] a = (T[])java.lang.reflect.Array
379 .newInstance(arrays[0].getClass().getComponentType(), len);
380 int k = 0;
381 for (T[] arr : arrays) {
382 System.arraycopy(arr, 0, a, k, arr.length);
383 k += arr.length;
384 }
385 return a;
386 }
387
388 static void checkNavigableMap(final NavigableMap<Integer, Integer> m) {
389 if (m.comparator() == null) {
390 check(m.descendingMap().descendingMap().comparator() == null);
391 check(m.descendingKeySet().descendingSet().comparator() == null);
392 }
393 equal(m.isEmpty(), m.size() == 0);
394 equal2(m, m.descendingMap());
395 if (maybe(4))
396 equal2(m, serialClone(m));
397 equal2(m.keySet(), m.descendingKeySet());
398 var cmp = comparator(m);
399 if (m.isEmpty()) {
400 THROWS(NoSuchElementException.class,
401 () -> m.firstKey(),
402 () -> m.lastKey());
403 equal(null, m.firstEntry());
404 equal(null, m.lastEntry());
405 equal(null, m.pollFirstEntry());
406 equal(null, m.pollLastEntry());
407 equal(null, m.lowerKey(1));
408 equal(null, m.floorKey(1));
409 equal(null, m.ceilingKey(1));
410 equal(null, m.higherKey(1));
411 equal(null, m.lowerEntry(1));
412 equal(null, m.floorEntry(1));
413 equal(null, m.ceilingEntry(1));
414 equal(null, m.higherEntry(1));
415 } else {
416 Integer a = m.firstKey();
417 Integer z = m.lastKey();
418 equal(m.lowerKey(a), null);
419 equal(m.higherKey(z), null);
420 equal(a, m.firstEntry().getKey());
421 equal(z, m.lastEntry().getKey());
422 equal2(m, m.tailMap(a));
423 equal2(m, m.headMap(z, true));
424 equal2(m, m.subMap(a, true, z, true));
425
426 testEmptyMap(m.subMap(a, true, a, false));
427 testEmptyMap(m.subMap(z, true, z, false));
428 testEmptyMap(m.headMap(a, false));
429 testEmptyMap(m.tailMap(z, false));
430
431 equal2(m.headMap(a, true), singletonMap(a, m.get(a)));
432 equal2(m.tailMap(z, true), singletonMap(z, m.get(z)));
433 }
434
435 Iterator<?>[] kits = new Iterator[] {
436 m.keySet().iterator(),
437 m.descendingMap().descendingKeySet().iterator(),
438 m.descendingKeySet().descendingSet().iterator(),
439 };
440 Iterator<?>[] vits = new Iterator[] {
441 m.values().iterator(),
442 m.descendingMap().descendingMap().values().iterator(),
443 };
444 Iterator<?>[] eits = new Iterator[] {
445 m.entrySet().iterator(),
446 m.descendingMap().descendingMap().entrySet().iterator(),
447 };
448 Iterator<?>[] its = concat(kits, vits, eits);
449 for (final Iterator<?> it : its)
450 if (maybe(4))
451 THROWS(IllegalStateException.class, () -> it.remove());
452 Map.Entry<Integer, Integer> prev = null;
453 for (var e : m.entrySet()) {
454 Integer k = e.getKey();
455 Integer v = e.getValue();
456 check(m.containsKey(k));
457 check(m.containsValue(v));
458 for (var kit : kits) equalNext(kit, k);
459 for (var vit : vits) equalNext(vit, v);
460 for (var eit : eits) equalNext(eit, e);
461 equal(k, m.ceilingKey(k));
462 equal(k, m.ceilingEntry(k).getKey());
463 equal(k, m.floorKey(k));
464 equal(k, m.floorEntry(k).getKey());
465 check(m.higherKey(k) == null || cmp.compare(k, m.higherKey(k)) < 0);
466 check(m.lowerKey(k) == null || cmp.compare(k, m.lowerKey(k)) > 0);
467 equal(m.lowerEntry(k), prev);
468 if (prev == null) {
469 equal(m.lowerKey(k), null);
470 } else {
471 equal(m.lowerKey(k), prev.getKey());
472 check(cmp.compare(prev.getKey(), e.getKey()) < 0);
473 }
474 prev = e;
475 }
476 for (final var it : its) {
477 if (maybe(2))
478 check(! it.hasNext());
479 Fun fun = () -> it.next();
480 THROWS(NoSuchElementException.class, fun, fun, fun);
481 }
482 }
483
484 static void equalNavigableMapsLeaf(final NavigableMap<Integer, Integer> m1,
485 final NavigableMap<Integer, Integer> m2) {
486 equal2(m1, m2);
487 equal( m1.size(), m2.size());
488 equal( m1.isEmpty(), m2.isEmpty());
489 equal( m1.hashCode(), m2.hashCode());
490 equal( m1.toString(), m2.toString());
491 equal2(m1.firstEntry(), m2.firstEntry());
492 equal2(m1.lastEntry(), m2.lastEntry());
493 checkNavigableMap(m1);
494 checkNavigableMap(m2);
495 }
496
497 static void equalNavigableMaps(NavigableMap<Integer, Integer> m1,
498 NavigableMap<Integer, Integer> m2) {
499 equalNavigableMapsLeaf(m1, m2);
500 equalSetsLeaf(m1.keySet(), m2.keySet());
501 equalNavigableSets(m1.navigableKeySet(),
502 m2.navigableKeySet());
503 equalNavigableSets(m1.descendingKeySet(),
504 m2.descendingKeySet());
505 equal2(m1.entrySet(),
506 m2.entrySet());
507 equalNavigableMapsLeaf(m1.descendingMap(),
508 m2.descendingMap());
509 equalNavigableMapsLeaf(m1.descendingMap().descendingMap(),
510 m2);
511 equalNavigableSetsLeaf((NavigableSet<Integer>) m1.descendingMap().keySet(),
512 (NavigableSet<Integer>) m2.descendingMap().keySet());
513 equalNavigableSetsLeaf(m1.descendingMap().descendingKeySet(),
514 m2.descendingMap().descendingKeySet());
515 equal2(m1.descendingMap().entrySet(),
516 m2.descendingMap().entrySet());
517
518 //----------------------------------------------------------------
519 // submaps
520 //----------------------------------------------------------------
521 Integer min = Integer.MIN_VALUE;
522 Integer max = Integer.MAX_VALUE;
523 if (m1.comparator() != null
524 && m1.comparator().compare(min, max) > 0) {
525 Integer tmp = min; min = max; max = tmp;
526 }
527 switch (rnd.nextInt(6)) {
528 case 0:
529 equalNavigableMapsLeaf(m1.subMap(min, true, max, true),
530 m2.subMap(min, true, max, true));
531 break;
532 case 1:
533 equalNavigableMapsLeaf(m1.tailMap(min, true),
534 m2.tailMap(min, true));
535 break;
536 case 2:
537 equalNavigableMapsLeaf(m1.headMap(max, true),
538 m2.headMap(max, true));
539 break;
540 case 3:
541 equalNavigableMapsLeaf((NavigableMap<Integer, Integer>) m1.subMap(min, max),
542 (NavigableMap<Integer, Integer>) m2.subMap(min, max));
543 break;
544 case 4:
545 equalNavigableMapsLeaf((NavigableMap<Integer, Integer>) m1.tailMap(min),
546 (NavigableMap<Integer, Integer>) m2.tailMap(min));
547 break;
548 case 5:
549 equalNavigableMapsLeaf((NavigableMap<Integer, Integer>) m1.headMap(max),
550 (NavigableMap<Integer, Integer>) m2.headMap(max));
551 break;
552 }
553 }
554
555 interface MapFrobber { void frob(NavigableMap<Integer, Integer> m); }
556 interface SetFrobber { void frob(NavigableSet<Integer> m); }
557
558 static MapFrobber randomAdder(NavigableMap<Integer, Integer> m) {
559 final Integer k = unusedKey(m);
560 final MapFrobber[] randomAdders = {
561 map -> {
562 equal(map.put(k, k + 1), null);
563 equal(map.get(k), k + 1);
564 if (maybe(4)) {
565 equal(map.put(k, k + 1), k + 1);
566 equal(map.get(k), k + 1);}},
567 map -> {
568 map.descendingMap().put(k, k + 1);
569 equal(map.get(k), k + 1);},
570 map -> map.tailMap(k,true).headMap(k,true).put(k, k + 1),
571 map -> {
572 equal(map.tailMap(k,true).headMap(k,true).putIfAbsent(k, k + 1), null);
573 equal(map.tailMap(k,true).headMap(k,true).putIfAbsent(k, k + 1), k + 1);},
574 map -> {
575 equal(map.tailMap(k,true).headMap(k,true).merge(k,k,Integer::sum), k);
576 equal(map.tailMap(k,true).headMap(k,true).merge(k,1,Integer::sum), k+1);},
577 map -> equal(map.subMap(k,true, k, true).computeIfAbsent(k, key -> key + 1), k + 1),
578 map -> {
579 equal(map.subMap(k,true, k, true).computeIfPresent(k, (key, val) -> 1), null);
580 equal(map.tailMap(k,true).compute(k, (key, val) -> {
581 equal(val, null);
582 return 1;
583 }), 1);
584 equal(map.headMap(k, true).computeIfPresent(k, (key, val) -> val + key), k + 1);
585 equal(map.tailMap(k, false).computeIfPresent(k, (key, val) -> 1), null);
586 equal(map.headMap(k, false).compute(k, (key, val) -> null), null);
587 equal(map.tailMap(k, false).computeIfAbsent(k, key -> null), null);
588 },
589 map -> map.tailMap(k,true).headMap(k,true).descendingMap().put(k, k + 1)
590 };
591 return map -> {
592 randomAdders[rnd.nextInt(randomAdders.length)].frob(map);
593 if (maybe(2)) equal(map.get(k), k + 1);
594 if (maybe(4)) {
595 equal(map.put(k, k + 1), k + 1);
596 equal(map.get(k), k + 1);}};
597 }
598
599 static SetFrobber randomAdder(NavigableSet<Integer> s) {
600 final Integer e = unusedElt(s);
601 final SetFrobber[] randomAdders = {
602 set -> check(set.add(e)),
603 set -> set.descendingSet().add(e),
604 set -> set.tailSet(e,true).headSet(e,true).add(e),
605 set -> set.descendingSet().tailSet(e,true).headSet(e,true).add(e)
606 };
607 return set -> {
608 if (maybe(2)) check(! set.contains(e));
609 randomAdders[rnd.nextInt(randomAdders.length)].frob(set);
610 if (maybe(2)) check(! set.add(e));
611 if (maybe(2)) check(set.contains(e));};
612 }
613
614 static Integer unusedElt(NavigableSet<Integer> s) {
615 Integer e;
616 do { e = rnd.nextInt(1024); }
617 while (s.contains(e));
618 return e;
619 }
620
621 static Integer unusedKey(NavigableMap<Integer, Integer> m) {
622 Integer k;
623 do { k = rnd.nextInt(1024); }
624 while (m.containsKey(k));
625 return k;
626 }
627
628 static Integer usedKey(NavigableMap<Integer, Integer> m) {
629 Integer x = rnd.nextInt(1024);
630 Integer floor = m.floorKey(x);
631 Integer ceiling = m.ceilingKey(x);
632 if (floor != null) return floor;
633 check(ceiling != null);
634 return ceiling;
635 }
636
637 static Integer usedElt(NavigableSet<Integer> s) {
638 Integer x = rnd.nextInt(1024);
639 Integer floor = s.floor(x);
640 Integer ceiling = s.ceiling(x);
641 if (floor != null) return floor;
642 check(ceiling != null);
643 return ceiling;
644 }
645
646 static void checkUnusedKey(NavigableMap<Integer, Integer> m, Integer k) {
647 check(! m.containsKey(k));
648 equal(m.get(k), null);
649 if (maybe(2))
650 equal(m.remove(k), null);
651 }
652
653 static void checkUnusedElt(NavigableSet<Integer> s, Integer e) {
654 if (maybe(2))
655 check(! s.contains(e));
656 if (maybe(2)) {
657 check(s.ceiling(e) != e);
658 check(s.floor(e) != e);
659 }
660 if (maybe(2))
661 check(! s.remove(e));
662 }
663
664 static Fun remover(final Iterator<?> it) {
665 return () -> it.remove();
666 }
667
668 static MapFrobber randomRemover(NavigableMap<Integer, Integer> m) {
669 final Integer k = usedKey(m);
670 final MapFrobber[] randomRemovers = {
671 map -> {
672 var e = map.firstEntry();
673 equal(map.pollFirstEntry(), e);
674 checkUnusedKey(map, e.getKey());},
675 map -> {
676 var e = map.lastEntry();
677 equal(map.pollLastEntry(), e);
678 checkUnusedKey(map, e.getKey());},
679 map -> {
680 check(map.remove(k) != null);
681 checkUnusedKey(map, k);},
682 map -> {
683 map.subMap(k, true, k, true).clear();
684 checkUnusedKey(map, k);},
685 map -> {
686 map.descendingMap().subMap(k, true, k, true).clear();
687 checkUnusedKey(map, k);},
688 map -> {
689 final var it = map.keySet().iterator();
690 while (it.hasNext())
691 if (it.next().equals(k)) {
692 it.remove();
693 if (maybe(2))
694 THROWS(IllegalStateException.class,
695 () -> it.remove());
696 }
697 checkUnusedKey(map, k);},
698 map -> {
699 final var it = map.navigableKeySet().descendingIterator();
700 while (it.hasNext())
701 if (it.next().equals(k)) {
702 it.remove();
703 if (maybe(2))
704 THROWS(IllegalStateException.class,
705 () -> it.remove());
706 }
707 checkUnusedKey(map, k);},
708 map -> {
709 final var it = map.entrySet().iterator();
710 while (it.hasNext())
711 if (it.next().getKey().equals(k)) {
712 it.remove();
713 if (maybe(2))
714 THROWS(IllegalStateException.class, remover(it));
715 }
716 checkUnusedKey(map, k);},
717 };
718
719 return randomRemovers[rnd.nextInt(randomRemovers.length)];
720 }
721
722 static SetFrobber randomRemover(NavigableSet<Integer> s) {
723 final Integer e = usedElt(s);
724
725 final SetFrobber[] randomRemovers = {
726 set -> {
727 var fst = set.first();
728 equal(set.pollFirst(), fst);
729 checkUnusedElt(set, fst);},
730 set -> {
731 var lst = set.last();
732 equal(set.pollLast(), lst);
733 checkUnusedElt(set, lst);},
734 set -> {
735 check(set.remove(e));
736 checkUnusedElt(set, e);},
737 set -> {
738 set.subSet(e, true, e, true).clear();
739 checkUnusedElt(set, e);},
740 set -> {
741 set.descendingSet().subSet(e, true, e, true).clear();
742 checkUnusedElt(set, e);},
743 set -> {
744 final var it = set.iterator();
745 while (it.hasNext())
746 if (it.next().equals(e)) {
747 it.remove();
748 if (maybe(2))
749 THROWS(IllegalStateException.class,
750 () -> it.remove());
751 }
752 checkUnusedElt(set, e);},
753 set -> {
754 final var it = set.descendingSet().iterator();
755 while (it.hasNext())
756 if (it.next().equals(e)) {
757 it.remove();
758 if (maybe(2))
759 THROWS(IllegalStateException.class,
760 () -> it.remove());
761 }
762 checkUnusedElt(set, e);},
763 set -> {
764 final var it = set.descendingIterator();
765 while (it.hasNext())
766 if (it.next().equals(e)) {
767 it.remove();
768 if (maybe(2))
769 THROWS(IllegalStateException.class,
770 () -> it.remove());
771 }
772 checkUnusedElt(set, e);}
773 };
774
775 return randomRemovers[rnd.nextInt(randomRemovers.length)];
776 }
777
778 static void lockStep(NavigableMap<Integer, Integer> m1,
779 NavigableMap<Integer, Integer> m2) {
780 if (! (thorough || maybe(3))) return;
781 if (maybe(4)) m1 = serialClone(m1);
782 if (maybe(4)) m2 = serialClone(m2);
783
784 var maps = Arrays.asList(m1, m2);
785 for (var m : maps) testEmptyMap(m);
786 final Set<Integer> ints = new HashSet<>();
787 while (ints.size() < size)
788 ints.add(rnd.nextInt(1024));
789 final Integer[] elts = ints.toArray(new Integer[size]);
790 equal(elts.length, size);
791 for (int i = 0; i < size; i++) {
792 MapFrobber adder = randomAdder(m1);
793 for (var m : maps) {
794 adder.frob(m);
795 equal(m.size(), i+1);
796 }
797 equalNavigableMaps(m1, m2);
798 }
799 for (var m : maps) {
800 final var e = usedKey(m);
801 THROWS(IllegalArgumentException.class,
802 () -> m.subMap(e,true,e,false).subMap(e,true,e,true),
803 () -> m.subMap(e,false,e,true).subMap(e,true,e,true),
804 () -> m.tailMap(e,false).tailMap(e,true),
805 () -> m.headMap(e,false).headMap(e,true),
806 () -> m.headMap(e, false).put(e, 0),
807 () -> m.tailMap(e, false).putIfAbsent(e, 0),
808 () -> m.headMap(e, false).computeIfAbsent(e, k -> 1),
809 () -> m.tailMap(e, false).compute(e, (k, v) -> 0));
810 }
811 //System.out.printf("%s%n", m1);
812 for (int i = size; i > 0; i--) {
813 MapFrobber remover = randomRemover(m1);
814 for (var m : maps) {
815 remover.frob(m);
816 equal(m.size(), i-1);
817 }
818 equalNavigableMaps(m1, m2);
819 }
820 for (var m : maps) testEmptyMap(m);
821 }
822
823 static void lockStep(NavigableSet<Integer> s1,
824 NavigableSet<Integer> s2) {
825 if (! (thorough || maybe(3))) return;
826 if (maybe(4)) s1 = serialClone(s1);
827 if (maybe(4)) s2 = serialClone(s2);
828
829 var sets = Arrays.asList(s1, s2);
830 for (var s : sets) testEmptySet(s);
831 final Set<Integer> ints = new HashSet<>();
832 while (ints.size() < size)
833 ints.add(rnd.nextInt(1024));
834 final Integer[] elts = ints.toArray(new Integer[size]);
835 equal(elts.length, size);
836 for (int i = 0; i < size; i++) {
837 SetFrobber adder = randomAdder(s1);
838 for (var s : sets) {
839 adder.frob(s);
840 equal(s.size(), i+1);
841 }
842 equalNavigableSets(s1, s2);
843 }
844 for (var s : sets) {
845 final Integer e = usedElt(s);
846 THROWS(IllegalArgumentException.class,
847 () -> s.subSet(e,true,e,false).subSet(e,true,e,true),
848 () -> s.subSet(e,false,e,true).subSet(e,true,e,true),
849 () -> s.tailSet(e,false).tailSet(e,true),
850 () -> s.headSet(e,false).headSet(e,true));
851 }
852 //System.out.printf("%s%n", s1);
853 for (int i = size; i > 0; i--) {
854 SetFrobber remover = randomRemover(s1);
855 for (var s : sets) {
856 remover.frob(s);
857 equal(s.size(), i-1);
858 }
859 equalNavigableSets(s1, s2);
860 }
861 for (var s : sets) testEmptySet(s);
862 }
863
864 //--------------------- Infrastructure ---------------------------
865 static volatile int passed = 0, failed = 0;
866 static void pass() { passed++; }
867 static void fail() { failed++; Thread.dumpStack(); }
868 static void fail(String msg) { System.out.println(msg); fail(); }
869 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
870 static void check(boolean cond) { if (cond) pass(); else fail(); }
871 static void equal(Object x, Object y) {
872 if (Objects.equals(x, y)) pass();
873 else {System.out.println(x + " not equal to " + y); fail();}}
874 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
875 public static void main(String[] args) throws Throwable {
876 try { realMain(args); } catch (Throwable t) { unexpected(t); }
877
878 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
879 if (failed > 0) throw new Exception("Some tests failed");
880 }
881 interface Fun {void f() throws Throwable;}
882 static void THROWS(Class<? extends Throwable> k, Fun... fs) {
883 for (Fun f : fs)
884 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
885 catch (Throwable t) {
886 if (k.isAssignableFrom(t.getClass())) pass();
887 else unexpected(t);}}
888 static byte[] serializedForm(Object obj) {
889 try {
890 ByteArrayOutputStream baos = new ByteArrayOutputStream();
891 new ObjectOutputStream(baos).writeObject(obj);
892 return baos.toByteArray();
|