1 /* 2 * Copyright (c) 2007, 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 6359979 27 * @summary Compare List implementations for identical behavior 28 * @author Martin Buchholz 29 */ 30 31 import java.io.*; 32 import java.util.*; 33 import java.util.concurrent.*; 34 import static java.util.Collections.*; 35 36 @SuppressWarnings("unchecked") 37 public class LockStep { 38 final int DEFAULT_SIZE = 5; 39 int size; // Running time is O(size**2) 40 41 int intArg(String[] args, int i, int defaultValue) { 42 return args.length > i ? Integer.parseInt(args[i]) : defaultValue; 43 } 44 45 boolean maybe(int n) { return rnd.nextInt(n) == 0; } 46 47 void test(String[] args) { 48 size = intArg(args, 0, DEFAULT_SIZE); 49 50 lockSteps(new ArrayList(), 51 new LinkedList(), 52 new Vector()); 53 } 54 55 void equalLists(List... lists) { 56 for (List list : lists) 57 equalLists(list, lists[0]); 58 } 59 60 void equalLists(List x, List y) { 61 equal(x, y); 62 equal(y, x); 63 equal(x.size(), y.size()); 64 equal(x.isEmpty(), y.isEmpty()); 65 equal(x.hashCode(), y.hashCode()); 66 equal(x.toString(), y.toString()); 67 equal(x.toArray(), y.toArray()); 68 } 69 70 void lockSteps(List... lists) { 71 for (int i = 0; i < lists.length; i++) 72 if (maybe(4)) lists[i] = serialClone(lists[i]); 73 for (final List list : lists) 74 testEmptyList(list); 75 for (int i = 0; i < size; i++) { 76 ListFrobber adder = randomAdder(); 77 for (final List list : lists) { 78 adder.frob(list); 79 equal(list.size(), i+1); 80 } 81 equalLists(lists); 82 } 83 { 84 final ListFrobber adder = randomAdder(); 85 final ListFrobber remover = randomRemover(); 86 for (final List list : lists) { 87 88 THROWS(ConcurrentModificationException.class, 89 new F(){void f(){ 90 Iterator it = list.iterator(); 91 adder.frob(list); 92 it.next();}}, 93 new F(){void f(){ 94 Iterator it = asSubList(list).iterator(); 95 remover.frob(list); 96 it.next();}}, 97 new F(){void f(){ 98 Iterator it = asSubList(asSubList(list)).iterator(); 99 adder.frob(list); 100 it.next();}}, 101 new F(){void f(){ 102 List subList = asSubList(list); 103 remover.frob(list); 104 subList.get(0);}}, 105 new F(){void f(){ 106 List sl = asSubList(list); 107 List ssl = asSubList(sl); 108 adder.frob(sl); 109 ssl.get(0);}}, 110 new F(){void f(){ 111 List sl = asSubList(list); 112 List ssl = asSubList(sl); 113 remover.frob(sl); 114 ssl.get(0);}}); 115 } 116 } 117 118 for (final List l : lists) { 119 final List sl = asSubList(l); 120 final List ssl = asSubList(sl); 121 ssl.add(0, 42); 122 equal(ssl.get(0), 42); 123 equal(sl.get(0), 42); 124 equal(l.get(0), 42); 125 final int s = l.size(); 126 final int rndIndex = rnd.nextInt(l.size()); 127 THROWS(IndexOutOfBoundsException.class, 128 new F(){void f(){l.subList(rndIndex, rndIndex).get(0);}}, 129 new F(){void f(){l.subList(s/2, s).get(s/2 + 1);}}, 130 new F(){void f(){l.subList(s/2, s).get(-1);}} 131 ); 132 THROWS(IllegalArgumentException.class, 133 new F(){void f(){ l.subList(1, 0);}}, 134 new F(){void f(){ sl.subList(1, 0);}}, 135 new F(){void f(){ssl.subList(1, 0);}}); 136 } 137 138 equalLists(lists); 139 140 for (final List list : lists) { 141 equalLists(list, asSubList(list)); 142 equalLists(list, asSubList(asSubList(list))); 143 } 144 for (final List list : lists) 145 System.out.println(list); 146 147 for (int i = lists[0].size(); i > 0; i--) { 148 ListFrobber remover = randomRemover(); 149 for (final List list : lists) 150 remover.frob(list); 151 equalLists(lists); 152 } 153 } 154 155 <T> List<T> asSubList(List<T> list) { 156 return list.subList(0, list.size()); 157 } 158 159 void testEmptyCollection(Collection<?> c) { 160 check(c.isEmpty()); 161 equal(c.size(), 0); 162 equal(c.toString(),"[]"); 163 equal(c.toArray().length, 0); 164 equal(c.toArray(new Object[0]).length, 0); 165 166 Object[] a = new Object[1]; a[0] = Boolean.TRUE; 167 equal(c.toArray(a), a); 168 equal(a[0], null); 169 } 170 171 void testEmptyList(List list) { 172 testEmptyCollection(list); 173 equal(list.hashCode(), 1); 174 equal(list, Collections.emptyList()); 175 } 176 177 final Random rnd = new Random(); 178 179 abstract class ListFrobber { abstract void frob(List l); } 180 181 ListFrobber randomAdder() { 182 final Integer e = rnd.nextInt(1024); 183 final int subListCount = rnd.nextInt(3); 184 final boolean atBeginning = rnd.nextBoolean(); 185 final boolean useIterator = rnd.nextBoolean(); 186 final boolean simpleIterator = rnd.nextBoolean(); 187 return new ListFrobber() {void frob(List l) { 188 final int s = l.size(); 189 List ll = l; 190 for (int i = 0; i < subListCount; i++) 191 ll = asSubList(ll); 192 if (! useIterator) { 193 if (atBeginning) { 194 switch (rnd.nextInt(3)) { 195 case 0: ll.add(0, e); break; 196 case 1: ll.subList(0, rnd.nextInt(s+1)).add(0, e); break; 197 case 2: ll.subList(0, rnd.nextInt(s+1)).subList(0,0).add(0,e); break; 198 default: throw new Error(); 199 } 200 } else { 201 switch (rnd.nextInt(3)) { 202 case 0: check(ll.add(e)); break; 203 case 1: ll.subList(s/2, s).add(s - s/2, e); break; 204 case 2: ll.subList(s, s).subList(0, 0).add(0, e); break; 205 default: throw new Error(); 206 } 207 } 208 } else { 209 if (atBeginning) { 210 ListIterator it = ll.listIterator(); 211 equal(it.nextIndex(), 0); 212 check(! it.hasPrevious()); 213 it.add(e); 214 equal(it.previousIndex(), 0); 215 equal(it.nextIndex(), 1); 216 check(it.hasPrevious()); 217 } else { 218 final int siz = ll.size(); 219 ListIterator it = ll.listIterator(siz); 220 equal(it.previousIndex(), siz-1); 221 check(! it.hasNext()); 222 it.add(e); 223 equal(it.previousIndex(), siz); 224 equal(it.nextIndex(), siz+1); 225 check(! it.hasNext()); 226 check(it.hasPrevious()); 227 } 228 }}}; 229 } 230 231 ListFrobber randomRemover() { 232 final int position = rnd.nextInt(3); 233 final int subListCount = rnd.nextInt(3); 234 return new ListFrobber() {void frob(List l) { 235 final int s = l.size(); 236 List ll = l; 237 for (int i = 0; i < subListCount; i++) 238 ll = asSubList(ll); 239 switch (position) { 240 case 0: // beginning 241 switch (rnd.nextInt(3)) { 242 case 0: ll.remove(0); break; 243 case 1: { 244 final Iterator it = ll.iterator(); 245 check(it.hasNext()); 246 THROWS(IllegalStateException.class, 247 new F(){void f(){it.remove();}}); 248 it.next(); 249 it.remove(); 250 THROWS(IllegalStateException.class, 251 new F(){void f(){it.remove();}}); 252 break;} 253 case 2: { 254 final ListIterator it = ll.listIterator(); 255 check(it.hasNext()); 256 THROWS(IllegalStateException.class, 257 new F(){void f(){it.remove();}}); 258 it.next(); 259 it.remove(); 260 THROWS(IllegalStateException.class, 261 new F(){void f(){it.remove();}}); 262 break;} 263 default: throw new Error(); 264 } 265 break; 266 case 1: // midpoint 267 switch (rnd.nextInt(3)) { 268 case 0: ll.remove(s/2); break; 269 case 1: { 270 final ListIterator it = ll.listIterator(s/2); 271 it.next(); 272 it.remove(); 273 break; 274 } 275 case 2: { 276 final ListIterator it = ll.listIterator(s/2+1); 277 it.previous(); 278 it.remove(); 279 break; 280 } 281 default: throw new Error(); 282 } 283 break; 284 case 2: // end 285 switch (rnd.nextInt(3)) { 286 case 0: ll.remove(s-1); break; 287 case 1: ll.subList(s-1, s).clear(); break; 288 case 2: 289 final ListIterator it = ll.listIterator(s); 290 check(! it.hasNext()); 291 check(it.hasPrevious()); 292 THROWS(IllegalStateException.class, 293 new F(){void f(){it.remove();}}); 294 it.previous(); 295 equal(it.nextIndex(), s-1); 296 check(it.hasNext()); 297 it.remove(); 298 equal(it.nextIndex(), s-1); 299 check(! it.hasNext()); 300 THROWS(IllegalStateException.class, 301 new F(){void f(){it.remove();}}); 302 break; 303 default: throw new Error(); 304 } 305 break; 306 default: throw new Error(); 307 }}}; 308 } 309 310 //--------------------- Infrastructure --------------------------- 311 volatile int passed = 0, failed = 0; 312 void pass() {passed++;} 313 void fail() {failed++; Thread.dumpStack();} 314 void fail(String msg) {System.err.println(msg); fail();} 315 void unexpected(Throwable t) {failed++; t.printStackTrace();} 316 void check(boolean cond) {if (cond) pass(); else fail();} 317 void equal(Object x, Object y) { 318 if (x == null ? y == null : x.equals(y)) pass(); 319 else fail(x + " not equal to " + y);} 320 <T> void equal(T[] x, T[] y) {check(Arrays.equals(x,y));} 321 public static void main(String[] args) throws Throwable { 322 new LockStep().instanceMain(args);} 323 void instanceMain(String[] args) throws Throwable { 324 try {test(args);} catch (Throwable t) {unexpected(t);} 325 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 326 if (failed > 0) throw new AssertionError("Some tests failed");} 327 abstract class F {abstract void f() throws Throwable;} 328 void THROWS(Class<? extends Throwable> k, F... fs) { 329 for (F f : fs) 330 try {f.f(); fail("Expected " + k.getName() + " not thrown");} 331 catch (Throwable t) { 332 if (k.isAssignableFrom(t.getClass())) pass(); 333 else unexpected(t);}} 334 static byte[] serializedForm(Object obj) { 335 try { 336 ByteArrayOutputStream baos = new ByteArrayOutputStream(); 337 new ObjectOutputStream(baos).writeObject(obj); 338 return baos.toByteArray(); 339 } catch (IOException e) { throw new RuntimeException(e); }} 340 static Object readObject(byte[] bytes) 341 throws IOException, ClassNotFoundException { 342 InputStream is = new ByteArrayInputStream(bytes); 343 return new ObjectInputStream(is).readObject();} 344 @SuppressWarnings("unchecked") 345 static <T> T serialClone(T obj) { 346 try { return (T) readObject(serializedForm(obj)); } 347 catch (Exception e) { throw new RuntimeException(e); }} 348 }