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