1 /* 2 * Copyright (c) 2012, 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 import java.util.ArrayList; 25 import java.util.Arrays; 26 import java.util.Collections; 27 import java.util.Comparator; 28 import java.util.List; 29 import java.util.LinkedList; 30 import java.util.Stack; 31 import java.util.Vector; 32 import java.util.concurrent.CopyOnWriteArrayList; 33 import java.util.concurrent.atomic.AtomicBoolean; 34 import java.util.concurrent.atomic.AtomicInteger; 35 36 import org.testng.annotations.DataProvider; 37 import org.testng.annotations.Test; 38 39 import static org.testng.Assert.assertEquals; 40 import static org.testng.Assert.assertFalse; 41 import static org.testng.Assert.assertTrue; 42 import static org.testng.Assert.fail; 43 44 import java.lang.reflect.Constructor; 45 import java.util.ConcurrentModificationException; 46 import java.util.function.Predicate; 47 import java.util.function.Supplier; 48 49 /** 50 * @test 51 * @summary Unit tests for extension methods on List 52 * @bug 8023367 53 * @library ../Collection/testlibrary 54 * @build CollectionAsserts CollectionSupplier ExtendsAbstractList 55 * @run testng ListDefaults 56 */ 57 public class ListDefaults { 58 59 private static final Supplier<?>[] LIST_CLASSES = { 60 java.util.ArrayList::new, 61 java.util.LinkedList::new, 62 java.util.Vector::new, 63 java.util.concurrent.CopyOnWriteArrayList::new, 64 ExtendsAbstractList::new 65 }; 66 67 private static final Supplier<?>[] LIST_CME_CLASSES = { 68 java.util.ArrayList::new, 69 java.util.Vector::new 70 }; 71 72 private static final Predicate<Integer> pEven = x -> 0 == x % 2; 73 private static final Predicate<Integer> pOdd = x -> 1 == x % 2; 74 75 private static final Comparator<Integer> BIT_COUNT_COMPARATOR = 76 (x, y) -> Integer.bitCount(x) - Integer.bitCount(y); 77 78 private static final Comparator<AtomicInteger> ATOMIC_INTEGER_COMPARATOR = 79 (x, y) -> x.intValue() - y.intValue(); 80 81 private static final int SIZE = 100; 82 private static final int SUBLIST_FROM = 20; 83 private static final int SUBLIST_TO = SIZE - 5; 84 private static final int SUBLIST_SIZE = SUBLIST_TO - SUBLIST_FROM; 85 86 private static interface Callback { 87 void call(List<Integer> list); 88 } 89 90 // call the callback for each recursive subList 91 private void trimmedSubList(final List<Integer> list, final Callback callback) { 92 int size = list.size(); 93 if (size > 1) { 94 // trim 1 element from both ends 95 final List<Integer> subList = list.subList(1, size - 1); 96 callback.call(subList); 97 trimmedSubList(subList, callback); 98 } 99 } 100 101 @DataProvider(name="listProvider", parallel=true) 102 public static Object[][] listCases() { 103 final List<Object[]> cases = new LinkedList<>(); 104 cases.add(new Object[] { Collections.emptyList() }); 105 cases.add(new Object[] { new ArrayList<>() }); 106 cases.add(new Object[] { new LinkedList<>() }); 107 cases.add(new Object[] { new Vector<>() }); 108 cases.add(new Object[] { new Stack<>() }); 109 cases.add(new Object[] { new CopyOnWriteArrayList<>() }); 110 111 cases.add(new Object[] { new ArrayList(){{add(42);}} }); 112 cases.add(new Object[] { new LinkedList(){{add(42);}} }); 113 cases.add(new Object[] { new Vector(){{add(42);}} }); 114 cases.add(new Object[] { new Stack(){{add(42);}} }); 115 cases.add(new Object[] { new CopyOnWriteArrayList(){{add(42);}} }); 116 return cases.toArray(new Object[0][cases.size()]); 117 } 118 119 @Test(dataProvider = "listProvider") 120 public void testProvidedWithNull(final List<Integer> list) throws Exception { 121 try { 122 list.forEach(null); 123 fail("expected NPE not thrown"); 124 } catch (NullPointerException npe) {} 125 try { 126 list.replaceAll(null); 127 fail("expected NPE not thrown"); 128 } catch (NullPointerException npe) {} 129 try { 130 list.removeIf(null); 131 fail("expected NPE not thrown"); 132 } catch (NullPointerException npe) {} 133 try { 134 list.sort(null); 135 } catch (Throwable t) { 136 fail("Exception not expected: " + t); 137 } 138 } 139 140 @Test 141 public void testForEach() throws Exception { 142 final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier((Supplier<List<Integer>>[])LIST_CLASSES, SIZE); 143 for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) { 144 final List<Integer> original = ((List<Integer>) test.expected); 145 final List<Integer> list = ((List<Integer>) test.collection); 146 147 try { 148 list.forEach(null); 149 fail("expected NPE not thrown"); 150 } catch (NullPointerException npe) {} 151 CollectionAsserts.assertContents(list, original); 152 153 final List<Integer> actual = new LinkedList<>(); 154 list.forEach(actual::add); 155 CollectionAsserts.assertContents(actual, list); 156 CollectionAsserts.assertContents(actual, original); 157 158 if (original.size() > SUBLIST_SIZE) { 159 final List<Integer> subList = original.subList(SUBLIST_FROM, SUBLIST_TO); 160 final List<Integer> actualSubList = new LinkedList<>(); 161 subList.forEach(actualSubList::add); 162 assertEquals(actualSubList.size(), SUBLIST_SIZE); 163 for (int i = 0; i < SUBLIST_SIZE; i++) { 164 assertEquals(actualSubList.get(i), original.get(i + SUBLIST_FROM)); 165 } 166 } 167 168 trimmedSubList(list, new Callback() { 169 @Override 170 public void call(final List<Integer> list) { 171 final List<Integer> actual = new LinkedList<>(); 172 list.forEach(actual::add); 173 CollectionAsserts.assertContents(actual, list); 174 } 175 }); 176 } 177 } 178 179 @Test 180 public void testRemoveIf() throws Exception { 181 final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier((Supplier<List<Integer>>[])LIST_CLASSES, SIZE); 182 for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) { 183 final List<Integer> original = ((List<Integer>) test.expected); 184 final List<Integer> list = ((List<Integer>) test.collection); 185 186 try { 187 list.removeIf(null); 188 fail("expected NPE not thrown"); 189 } catch (NullPointerException npe) {} 190 CollectionAsserts.assertContents(list, original); 191 192 final AtomicInteger offset = new AtomicInteger(1); 193 while (list.size() > 0) { 194 removeFirst(original, list, offset); 195 } 196 } 197 198 for (final CollectionSupplier.TestCase test : supplier.get()) { 199 final List<Integer> original = ((List<Integer>) test.expected); 200 final List<Integer> list = ((List<Integer>) test.collection); 201 list.removeIf(pOdd); 202 for (int i : list) { 203 assertTrue((i % 2) == 0); 204 } 205 for (int i : original) { 206 if (i % 2 == 0) { 207 assertTrue(list.contains(i)); 208 } 209 } 210 list.removeIf(pEven); 211 assertTrue(list.isEmpty()); 212 } 213 214 for (final CollectionSupplier.TestCase test : supplier.get()) { 215 final List<Integer> original = ((List<Integer>) test.expected); 216 final List<Integer> list = ((List<Integer>) test.collection); 217 final List<Integer> listCopy = new ArrayList<>(list); 218 if (original.size() > SUBLIST_SIZE) { 219 final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO); 220 final List<Integer> subListCopy = new ArrayList<>(subList); 221 listCopy.removeAll(subList); 222 subList.removeIf(pOdd); 223 for (int i : subList) { 224 assertTrue((i % 2) == 0); 225 } 226 for (int i : subListCopy) { 227 if (i % 2 == 0) { 228 assertTrue(subList.contains(i)); 229 } else { 230 assertFalse(subList.contains(i)); 231 } 232 } 233 subList.removeIf(pEven); 234 assertTrue(subList.isEmpty()); 235 // elements outside the view should remain 236 CollectionAsserts.assertContents(list, listCopy); 237 } 238 } 239 240 for (final CollectionSupplier.TestCase test : supplier.get()) { 241 final List<Integer> list = ((List<Integer>) test.collection); 242 trimmedSubList(list, new Callback() { 243 @Override 244 public void call(final List<Integer> list) { 245 final List<Integer> copy = new ArrayList<>(list); 246 list.removeIf(pOdd); 247 for (int i : list) { 248 assertTrue((i % 2) == 0); 249 } 250 for (int i : copy) { 251 if (i % 2 == 0) { 252 assertTrue(list.contains(i)); 253 } else { 254 assertFalse(list.contains(i)); 255 } 256 } 257 } 258 }); 259 } 260 } 261 262 // remove the first element 263 private void removeFirst(final List<Integer> original, final List<Integer> list, final AtomicInteger offset) { 264 final AtomicBoolean first = new AtomicBoolean(true); 265 list.removeIf(x -> first.getAndSet(false)); 266 CollectionAsserts.assertContents(original.subList(offset.getAndIncrement(), original.size()), list); 267 } 268 269 @Test 270 public void testReplaceAll() throws Exception { 271 final int scale = 3; 272 final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier((Supplier<List<Integer>>[])LIST_CLASSES, SIZE); 273 for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) { 274 final List<Integer> original = ((List<Integer>) test.expected); 275 final List<Integer> list = ((List<Integer>) test.collection); 276 277 try { 278 list.replaceAll(null); 279 fail("expected NPE not thrown"); 280 } catch (NullPointerException npe) {} 281 CollectionAsserts.assertContents(list, original); 282 283 list.replaceAll(x -> scale * x); 284 for (int i=0; i < original.size(); i++) { 285 assertTrue(list.get(i) == (scale * original.get(i)), "mismatch at index " + i); 286 } 287 288 if (original.size() > SUBLIST_SIZE) { 289 final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO); 290 subList.replaceAll(x -> x + 1); 291 // verify elements in view [from, to) were replaced 292 for (int i = 0; i < SUBLIST_SIZE; i++) { 293 assertTrue(subList.get(i) == ((scale * original.get(i + SUBLIST_FROM)) + 1), 294 "mismatch at sublist index " + i); 295 } 296 // verify that elements [0, from) remain unmodified 297 for (int i = 0; i < SUBLIST_FROM; i++) { 298 assertTrue(list.get(i) == (scale * original.get(i)), 299 "mismatch at original index " + i); 300 } 301 // verify that elements [to, size) remain unmodified 302 for (int i = SUBLIST_TO; i < list.size(); i++) { 303 assertTrue(list.get(i) == (scale * original.get(i)), 304 "mismatch at original index " + i); 305 } 306 } 307 } 308 309 for (final CollectionSupplier.TestCase test : supplier.get()) { 310 final List<Integer> list = ((List<Integer>) test.collection); 311 trimmedSubList(list, new Callback() { 312 @Override 313 public void call(final List<Integer> list) { 314 final List<Integer> copy = new ArrayList<>(list); 315 final int offset = 5; 316 list.replaceAll(x -> offset + x); 317 for (int i=0; i < copy.size(); i++) { 318 assertTrue(list.get(i) == (offset + copy.get(i)), "mismatch at index " + i); 319 } 320 } 321 }); 322 } 323 } 324 325 @Test 326 public void testSort() throws Exception { 327 final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier((Supplier<List<Integer>>[])LIST_CLASSES, SIZE); 328 for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) { 329 final List<Integer> original = ((List<Integer>) test.expected); 330 final List<Integer> list = ((List<Integer>) test.collection); 331 CollectionSupplier.shuffle(list); 332 list.sort(Integer::compare); 333 CollectionAsserts.assertSorted(list, Integer::compare); 334 if (test.name.startsWith("reverse")) { 335 Collections.reverse(list); 336 } 337 CollectionAsserts.assertContents(list, original); 338 339 CollectionSupplier.shuffle(list); 340 list.sort(null); 341 CollectionAsserts.assertSorted(list, Comparator.<Integer>naturalOrder()); 342 if (test.name.startsWith("reverse")) { 343 Collections.reverse(list); 344 } 345 CollectionAsserts.assertContents(list, original); 346 347 CollectionSupplier.shuffle(list); 348 list.sort(Comparator.<Integer>naturalOrder()); 349 CollectionAsserts.assertSorted(list, Comparator.<Integer>naturalOrder()); 350 if (test.name.startsWith("reverse")) { 351 Collections.reverse(list); 352 } 353 CollectionAsserts.assertContents(list, original); 354 355 CollectionSupplier.shuffle(list); 356 list.sort(Comparator.<Integer>reverseOrder()); 357 CollectionAsserts.assertSorted(list, Comparator.<Integer>reverseOrder()); 358 if (!test.name.startsWith("reverse")) { 359 Collections.reverse(list); 360 } 361 CollectionAsserts.assertContents(list, original); 362 363 CollectionSupplier.shuffle(list); 364 list.sort(BIT_COUNT_COMPARATOR); 365 CollectionAsserts.assertSorted(list, BIT_COUNT_COMPARATOR); 366 // check sort by verifying that bitCount increases and never drops 367 int minBitCount = 0; 368 int bitCount = 0; 369 for (final Integer i : list) { 370 bitCount = Integer.bitCount(i); 371 assertTrue(bitCount >= minBitCount); 372 minBitCount = bitCount; 373 } 374 375 @SuppressWarnings("unchecked") 376 final Constructor<? extends List<?>> defaultConstructor = ((Class<? extends List<?>>)test.collection.getClass()).getConstructor(); 377 final List<AtomicInteger> incomparables = (List<AtomicInteger>) defaultConstructor.newInstance(); 378 379 for (int i=0; i < test.expected.size(); i++) { 380 incomparables.add(new AtomicInteger(i)); 381 } 382 CollectionSupplier.shuffle(incomparables); 383 incomparables.sort(ATOMIC_INTEGER_COMPARATOR); 384 for (int i=0; i < test.expected.size(); i++) { 385 assertEquals(i, incomparables.get(i).intValue()); 386 } 387 388 if (original.size() > SUBLIST_SIZE) { 389 final List<Integer> copy = new ArrayList<>(list); 390 final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO); 391 CollectionSupplier.shuffle(subList); 392 subList.sort(Comparator.<Integer>naturalOrder()); 393 CollectionAsserts.assertSorted(subList, Comparator.<Integer>naturalOrder()); 394 // verify that elements [0, from) remain unmodified 395 for (int i = 0; i < SUBLIST_FROM; i++) { 396 assertTrue(list.get(i) == copy.get(i), 397 "mismatch at index " + i); 398 } 399 // verify that elements [to, size) remain unmodified 400 for (int i = SUBLIST_TO; i < list.size(); i++) { 401 assertTrue(list.get(i) == copy.get(i), 402 "mismatch at index " + i); 403 } 404 } 405 } 406 407 for (final CollectionSupplier.TestCase test : supplier.get()) { 408 final List<Integer> list = ((List<Integer>) test.collection); 409 trimmedSubList(list, new Callback() { 410 @Override 411 public void call(final List<Integer> list) { 412 final List<Integer> copy = new ArrayList<>(list); 413 CollectionSupplier.shuffle(list); 414 list.sort(Comparator.<Integer>naturalOrder()); 415 CollectionAsserts.assertSorted(list, Comparator.<Integer>naturalOrder()); 416 } 417 }); 418 } 419 } 420 421 @Test 422 public void testForEachThrowsCME() throws Exception { 423 final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier((Supplier<List<Integer>>[])LIST_CME_CLASSES, SIZE); 424 for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) { 425 final List<Integer> list = ((List<Integer>) test.collection); 426 427 if (list.size() <= 1) { 428 continue; 429 } 430 boolean gotException = false; 431 try { 432 // bad predicate that modifies its list, should throw CME 433 list.forEach((x) -> {list.add(x);}); 434 } catch (ConcurrentModificationException cme) { 435 gotException = true; 436 } 437 if (!gotException) { 438 fail("expected CME was not thrown from " + test); 439 } 440 } 441 } 442 443 @Test 444 public void testRemoveIfThrowsCME() throws Exception { 445 final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier((Supplier<List<Integer>>[])LIST_CME_CLASSES, SIZE); 446 for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) { 447 final List<Integer> original = ((List<Integer>) test.expected); 448 final List<Integer> list = ((List<Integer>) test.collection); 449 450 if (list.size() <= 1) { 451 continue; 452 } 453 boolean gotException = false; 454 try { 455 // bad predicate that modifies its list, should throw CME 456 list.removeIf((x) -> {return list.add(x);}); 457 } catch (ConcurrentModificationException cme) { 458 gotException = true; 459 } 460 if (!gotException) { 461 fail("expected CME was not thrown from " + test); 462 } 463 } 464 } 465 466 @Test 467 public void testReplaceAllThrowsCME() throws Exception { 468 final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier((Supplier<List<Integer>>[])LIST_CME_CLASSES, SIZE); 469 for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) { 470 final List<Integer> list = ((List<Integer>) test.collection); 471 472 if (list.size() <= 1) { 473 continue; 474 } 475 boolean gotException = false; 476 try { 477 // bad predicate that modifies its list, should throw CME 478 list.replaceAll(x -> {int n = 3 * x; list.add(n); return n;}); 479 } catch (ConcurrentModificationException cme) { 480 gotException = true; 481 } 482 if (!gotException) { 483 fail("expected CME was not thrown from " + test); 484 } 485 } 486 } 487 488 @Test 489 public void testSortThrowsCME() throws Exception { 490 final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier((Supplier<List<Integer>>[])LIST_CME_CLASSES, SIZE); 491 for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) { 492 final List<Integer> list = ((List<Integer>) test.collection); 493 494 if (list.size() <= 1) { 495 continue; 496 } 497 boolean gotException = false; 498 try { 499 // bad predicate that modifies its list, should throw CME 500 list.sort((x, y) -> {list.add(x); return x - y;}); 501 } catch (ConcurrentModificationException cme) { 502 gotException = true; 503 } 504 if (!gotException) { 505 fail("expected CME was not thrown from " + test); 506 } 507 } 508 } 509 510 private static final List<Integer> SLICED_EXPECTED = Arrays.asList(0, 1, 2, 3, 5, 6, 7, 8, 9); 511 private static final List<Integer> SLICED_EXPECTED2 = Arrays.asList(0, 1, 2, 5, 6, 7, 8, 9); 512 513 @DataProvider(name="shortIntListProvider", parallel=true) 514 public static Object[][] intListCases() { 515 final Integer[] DATA = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 516 final List<Object[]> cases = new LinkedList<>(); 517 cases.add(new Object[] { new ArrayList<>(Arrays.asList(DATA)) }); 518 cases.add(new Object[] { new LinkedList<>(Arrays.asList(DATA)) }); 519 cases.add(new Object[] { new Vector<>(Arrays.asList(DATA)) }); 520 cases.add(new Object[] { new CopyOnWriteArrayList<>(Arrays.asList(DATA)) }); 521 cases.add(new Object[] { new ExtendsAbstractList<>(Arrays.asList(DATA)) }); 522 return cases.toArray(new Object[0][cases.size()]); 523 } 524 525 @Test(dataProvider = "shortIntListProvider") 526 public void testRemoveIfFromSlice(final List<Integer> list) throws Exception { 527 final List<Integer> sublist = list.subList(3, 6); 528 assertTrue(sublist.removeIf(x -> x == 4)); 529 CollectionAsserts.assertContents(list, SLICED_EXPECTED); 530 531 final List<Integer> sublist2 = list.subList(2, 5); 532 assertTrue(sublist2.removeIf(x -> x == 3)); 533 CollectionAsserts.assertContents(list, SLICED_EXPECTED2); 534 } 535 }