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 }