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