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