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 }