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 
  32 import java.io.*;
  33 import java.util.*;
  34 import java.util.concurrent.*;
  35 import static java.util.Collections.*;
  36 
  37 @SuppressWarnings("unchecked")
  38 public 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 }