/* * Copyright (c) 2007, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ /* * @test * @bug 6359979 * @summary Compare List implementations for identical behavior * @author Martin Buchholz * @key randomness */ import java.io.*; import java.util.*; import java.util.concurrent.*; import static java.util.Collections.*; @SuppressWarnings("unchecked") public class LockStep { final int DEFAULT_SIZE = 5; int size; // Running time is O(size**2) int intArg(String[] args, int i, int defaultValue) { return args.length > i ? Integer.parseInt(args[i]) : defaultValue; } boolean maybe(int n) { return rnd.nextInt(n) == 0; } void test(String[] args) { size = intArg(args, 0, DEFAULT_SIZE); lockSteps(new ArrayList(), new LinkedList(), new Vector()); } void equalLists(List... lists) { for (List list : lists) equalLists(list, lists[0]); } void equalLists(List x, List y) { equal(x, y); equal(y, x); equal(x.size(), y.size()); equal(x.isEmpty(), y.isEmpty()); equal(x.hashCode(), y.hashCode()); equal(x.toString(), y.toString()); equal(x.toArray(), y.toArray()); } void lockSteps(List... lists) { for (int i = 0; i < lists.length; i++) if (maybe(4)) lists[i] = serialClone(lists[i]); for (final List list : lists) testEmptyList(list); for (int i = 0; i < size; i++) { ListFrobber adder = randomAdder(); for (final List list : lists) { adder.frob(list); equal(list.size(), i+1); } equalLists(lists); } { final ListFrobber adder = randomAdder(); final ListFrobber remover = randomRemover(); for (final List list : lists) { THROWS(ConcurrentModificationException.class, new F(){void f(){ Iterator it = list.iterator(); adder.frob(list); it.next();}}, new F(){void f(){ Iterator it = asSubList(list).iterator(); remover.frob(list); it.next();}}, new F(){void f(){ Iterator it = asSubList(asSubList(list)).iterator(); adder.frob(list); it.next();}}, new F(){void f(){ List subList = asSubList(list); remover.frob(list); subList.get(0);}}, new F(){void f(){ List sl = asSubList(list); List ssl = asSubList(sl); adder.frob(sl); ssl.get(0);}}, new F(){void f(){ List sl = asSubList(list); List ssl = asSubList(sl); remover.frob(sl); ssl.get(0);}}); } } for (final List l : lists) { final List sl = asSubList(l); final List ssl = asSubList(sl); ssl.add(0, 42); equal(ssl.get(0), 42); equal(sl.get(0), 42); equal(l.get(0), 42); final int s = l.size(); final int rndIndex = rnd.nextInt(l.size()); THROWS(IndexOutOfBoundsException.class, new F(){void f(){l.subList(rndIndex, rndIndex).get(0);}}, new F(){void f(){l.subList(s/2, s).get(s/2 + 1);}}, new F(){void f(){l.subList(s/2, s).get(-1);}} ); THROWS(IllegalArgumentException.class, new F(){void f(){ l.subList(1, 0);}}, new F(){void f(){ sl.subList(1, 0);}}, new F(){void f(){ssl.subList(1, 0);}}); } equalLists(lists); for (final List list : lists) { equalLists(list, asSubList(list)); equalLists(list, asSubList(asSubList(list))); } for (final List list : lists) System.out.println(list); for (int i = lists[0].size(); i > 0; i--) { ListFrobber remover = randomRemover(); for (final List list : lists) remover.frob(list); equalLists(lists); } } List asSubList(List list) { return list.subList(0, list.size()); } void testEmptyCollection(Collection c) { check(c.isEmpty()); equal(c.size(), 0); equal(c.toString(),"[]"); equal(c.toArray().length, 0); equal(c.toArray(new Object[0]).length, 0); Object[] a = new Object[1]; a[0] = Boolean.TRUE; equal(c.toArray(a), a); equal(a[0], null); } void testEmptyList(List list) { testEmptyCollection(list); equal(list.hashCode(), 1); equal(list, Collections.emptyList()); } final Random rnd = new Random(); abstract class ListFrobber { abstract void frob(List l); } ListFrobber randomAdder() { final Integer e = rnd.nextInt(1024); final int subListCount = rnd.nextInt(3); final boolean atBeginning = rnd.nextBoolean(); final boolean useIterator = rnd.nextBoolean(); final boolean simpleIterator = rnd.nextBoolean(); return new ListFrobber() {void frob(List l) { final int s = l.size(); List ll = l; for (int i = 0; i < subListCount; i++) ll = asSubList(ll); if (! useIterator) { if (atBeginning) { switch (rnd.nextInt(3)) { case 0: ll.add(0, e); break; case 1: ll.subList(0, rnd.nextInt(s+1)).add(0, e); break; case 2: ll.subList(0, rnd.nextInt(s+1)).subList(0,0).add(0,e); break; default: throw new Error(); } } else { switch (rnd.nextInt(3)) { case 0: check(ll.add(e)); break; case 1: ll.subList(s/2, s).add(s - s/2, e); break; case 2: ll.subList(s, s).subList(0, 0).add(0, e); break; default: throw new Error(); } } } else { if (atBeginning) { ListIterator it = ll.listIterator(); equal(it.nextIndex(), 0); check(! it.hasPrevious()); it.add(e); equal(it.previousIndex(), 0); equal(it.nextIndex(), 1); check(it.hasPrevious()); } else { final int siz = ll.size(); ListIterator it = ll.listIterator(siz); equal(it.previousIndex(), siz-1); check(! it.hasNext()); it.add(e); equal(it.previousIndex(), siz); equal(it.nextIndex(), siz+1); check(! it.hasNext()); check(it.hasPrevious()); } }}}; } ListFrobber randomRemover() { final int position = rnd.nextInt(3); final int subListCount = rnd.nextInt(3); return new ListFrobber() {void frob(List l) { final int s = l.size(); List ll = l; for (int i = 0; i < subListCount; i++) ll = asSubList(ll); switch (position) { case 0: // beginning switch (rnd.nextInt(3)) { case 0: ll.remove(0); break; case 1: { final Iterator it = ll.iterator(); check(it.hasNext()); THROWS(IllegalStateException.class, new F(){void f(){it.remove();}}); it.next(); it.remove(); THROWS(IllegalStateException.class, new F(){void f(){it.remove();}}); break;} case 2: { final ListIterator it = ll.listIterator(); check(it.hasNext()); THROWS(IllegalStateException.class, new F(){void f(){it.remove();}}); it.next(); it.remove(); THROWS(IllegalStateException.class, new F(){void f(){it.remove();}}); break;} default: throw new Error(); } break; case 1: // midpoint switch (rnd.nextInt(3)) { case 0: ll.remove(s/2); break; case 1: { final ListIterator it = ll.listIterator(s/2); it.next(); it.remove(); break; } case 2: { final ListIterator it = ll.listIterator(s/2+1); it.previous(); it.remove(); break; } default: throw new Error(); } break; case 2: // end switch (rnd.nextInt(3)) { case 0: ll.remove(s-1); break; case 1: ll.subList(s-1, s).clear(); break; case 2: final ListIterator it = ll.listIterator(s); check(! it.hasNext()); check(it.hasPrevious()); THROWS(IllegalStateException.class, new F(){void f(){it.remove();}}); it.previous(); equal(it.nextIndex(), s-1); check(it.hasNext()); it.remove(); equal(it.nextIndex(), s-1); check(! it.hasNext()); THROWS(IllegalStateException.class, new F(){void f(){it.remove();}}); break; default: throw new Error(); } break; default: throw new Error(); }}}; } //--------------------- Infrastructure --------------------------- volatile int passed = 0, failed = 0; void pass() {passed++;} void fail() {failed++; Thread.dumpStack();} void fail(String msg) {System.err.println(msg); fail();} void unexpected(Throwable t) {failed++; t.printStackTrace();} void check(boolean cond) {if (cond) pass(); else fail();} void equal(Object x, Object y) { if (x == null ? y == null : x.equals(y)) pass(); else fail(x + " not equal to " + y);} void equal(T[] x, T[] y) {check(Arrays.equals(x,y));} public static void main(String[] args) throws Throwable { new LockStep().instanceMain(args);} void instanceMain(String[] args) throws Throwable { try {test(args);} catch (Throwable t) {unexpected(t);} System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); if (failed > 0) throw new AssertionError("Some tests failed");} abstract class F {abstract void f() throws Throwable;} void THROWS(Class k, F... fs) { for (F f : fs) try {f.f(); fail("Expected " + k.getName() + " not thrown");} catch (Throwable t) { if (k.isAssignableFrom(t.getClass())) pass(); else unexpected(t);}} static byte[] serializedForm(Object obj) { try { ByteArrayOutputStream baos = new ByteArrayOutputStream(); new ObjectOutputStream(baos).writeObject(obj); return baos.toByteArray(); } catch (IOException e) { throw new RuntimeException(e); }} static Object readObject(byte[] bytes) throws IOException, ClassNotFoundException { InputStream is = new ByteArrayInputStream(bytes); return new ObjectInputStream(is).readObject();} @SuppressWarnings("unchecked") static T serialClone(T obj) { try { return (T) readObject(serializedForm(obj)); } catch (Exception e) { throw new RuntimeException(e); }} }