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