1 /*
2  * Copyright (c) 2013, 2017, 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 /**
25  * @test
26  * @bug 8005698
27  * @library /lib/testlibrary/bootlib
28  * @build java.base/java.util.SpliteratorTestHelper
29  * @run testng SpliteratorCollisions
30  * @summary Spliterator traversing and splitting hash maps containing colliding hashes
31  */
32 
33 import org.testng.annotations.DataProvider;
34 import org.testng.annotations.Test;
35 
36 import java.util.ArrayList;
37 import java.util.Arrays;
38 import java.util.Collection;
39 import java.util.Collections;
40 import java.util.HashMap;
41 import java.util.HashSet;
42 import java.util.LinkedHashMap;
43 import java.util.LinkedHashSet;
44 import java.util.List;
45 import java.util.Map;
46 import java.util.Spliterator;
47 import java.util.SpliteratorTestHelper;
48 import java.util.TreeSet;
49 import java.util.function.Function;
50 import java.util.function.Supplier;
51 import java.util.function.UnaryOperator;
52 
53 public class SpliteratorCollisions extends SpliteratorTestHelper {
54 
55     private static final List<Integer> SIZES = Arrays.asList(0, 1, 10, 100, 1000);
56 
57     private static class SpliteratorDataBuilder<T> {
58         List<Object[]> data;
59         List<T> exp;
60         Map<T, T> mExp;
61 
SpliteratorDataBuilder(List<Object[]> data, List<T> exp)62         SpliteratorDataBuilder(List<Object[]> data, List<T> exp) {
63             this.data = data;
64             this.exp = exp;
65             this.mExp = createMap(exp);
66         }
67 
createMap(List<T> l)68         Map<T, T> createMap(List<T> l) {
69             Map<T, T> m = new LinkedHashMap<>();
70             for (T t : l) {
71                 m.put(t, t);
72             }
73             return m;
74         }
75 
add(String description, Collection<?> expected, Supplier<Spliterator<?>> s)76         void add(String description, Collection<?> expected, Supplier<Spliterator<?>> s) {
77             description = joiner(description).toString();
78             data.add(new Object[]{description, expected, s});
79         }
80 
add(String description, Supplier<Spliterator<?>> s)81         void add(String description, Supplier<Spliterator<?>> s) {
82             add(description, exp, s);
83         }
84 
addCollection(Function<Collection<T>, ? extends Collection<T>> c)85         void addCollection(Function<Collection<T>, ? extends Collection<T>> c) {
86             add("new " + c.apply(Collections.<T>emptyList()).getClass().getName() + ".spliterator()",
87                 () -> c.apply(exp).spliterator());
88         }
89 
addList(Function<Collection<T>, ? extends List<T>> l)90         void addList(Function<Collection<T>, ? extends List<T>> l) {
91             // @@@ If collection is instance of List then add sub-list tests
92             addCollection(l);
93         }
94 
addMap(Function<Map<T, T>, ? extends Map<T, T>> m)95         void addMap(Function<Map<T, T>, ? extends Map<T, T>> m) {
96             String description = "new " + m.apply(Collections.<T, T>emptyMap()).getClass().getName();
97             add(description + ".keySet().spliterator()", () -> m.apply(mExp).keySet().spliterator());
98             add(description + ".values().spliterator()", () -> m.apply(mExp).values().spliterator());
99             add(description + ".entrySet().spliterator()", mExp.entrySet(), () -> m.apply(mExp).entrySet().spliterator());
100         }
101 
joiner(String description)102         StringBuilder joiner(String description) {
103             return new StringBuilder(description).
104                     append(" {").
105                     append("size=").append(exp.size()).
106                     append("}");
107         }
108     }
109 
110     static Object[][] spliteratorDataProvider;
111 
112     @DataProvider(name = "HashableIntSpliterator")
spliteratorDataProvider()113     public static Object[][] spliteratorDataProvider() {
114         if (spliteratorDataProvider != null) {
115             return spliteratorDataProvider;
116         }
117 
118         List<Object[]> data = new ArrayList<>();
119         for (int size : SIZES) {
120             List<HashableInteger> exp = listIntRange(size, false);
121             SpliteratorDataBuilder<HashableInteger> db = new SpliteratorDataBuilder<>(data, exp);
122 
123             // Maps
124             db.addMap(HashMap::new);
125             db.addMap(LinkedHashMap::new);
126 
127             // Collections that use HashMap
128             db.addCollection(HashSet::new);
129             db.addCollection(LinkedHashSet::new);
130             db.addCollection(TreeSet::new);
131         }
132         return spliteratorDataProvider = data.toArray(new Object[0][]);
133     }
134 
135     static Object[][] spliteratorDataProviderWithNull;
136 
137     @DataProvider(name = "HashableIntSpliteratorWithNull")
spliteratorNullDataProvider()138     public static Object[][] spliteratorNullDataProvider() {
139         if (spliteratorDataProviderWithNull != null) {
140             return spliteratorDataProviderWithNull;
141         }
142 
143         List<Object[]> data = new ArrayList<>();
144         for (int size : SIZES) {
145             List<HashableInteger> exp = listIntRange(size, true);
146             SpliteratorDataBuilder<HashableInteger> db = new SpliteratorDataBuilder<>(data, exp);
147 
148             // Maps
149             db.addMap(HashMap::new);
150             db.addMap(LinkedHashMap::new);
151             // TODO: add this back in if we decide to keep TreeBin in WeakHashMap
152             //db.addMap(WeakHashMap::new);
153 
154             // Collections that use HashMap
155             db.addCollection(HashSet::new);
156             db.addCollection(LinkedHashSet::new);
157 //            db.addCollection(TreeSet::new);
158 
159         }
160         return spliteratorDataProviderWithNull = data.toArray(new Object[0][]);
161     }
162 
163     static final class HashableInteger implements Comparable<HashableInteger> {
164 
165         final int value;
166         final int hashmask; //yes duplication
167 
HashableInteger(int value, int hashmask)168         HashableInteger(int value, int hashmask) {
169             this.value = value;
170             this.hashmask = hashmask;
171         }
172 
173         @Override
equals(Object obj)174         public boolean equals(Object obj) {
175             if (obj instanceof HashableInteger) {
176                 HashableInteger other = (HashableInteger) obj;
177 
178                 return other.value == value;
179             }
180 
181             return false;
182         }
183 
184         @Override
hashCode()185         public int hashCode() {
186             return value % hashmask;
187         }
188 
189         @Override
compareTo(HashableInteger o)190         public int compareTo(HashableInteger o) {
191             return value - o.value;
192         }
193 
194         @Override
toString()195         public String toString() {
196             return Integer.toString(value);
197         }
198     }
199 
listIntRange(int upTo, boolean withNull)200     private static List<HashableInteger> listIntRange(int upTo, boolean withNull) {
201         List<HashableInteger> exp = new ArrayList<>();
202         if (withNull) {
203             exp.add(null);
204         }
205         for (int i = 0; i < upTo; i++) {
206             exp.add(new HashableInteger(i, 10));
207         }
208         return Collections.unmodifiableList(exp);
209     }
210 
211     @Test(dataProvider = "HashableIntSpliterator")
testNullPointerException(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)212     void testNullPointerException(String description,
213                                   Collection<HashableInteger> exp,
214                                   Supplier<Spliterator<HashableInteger>> s) {
215         assertThrowsNPE(() -> s.get().forEachRemaining(null));
216         assertThrowsNPE(() -> s.get().tryAdvance(null));
217     }
218 
219     @Test(dataProvider = "HashableIntSpliteratorWithNull")
testNullPointerExceptionWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)220     void testNullPointerExceptionWithNull(String description,
221                                           Collection<HashableInteger> exp,
222                                           Supplier<Spliterator<HashableInteger>> s) {
223         assertThrowsNPE(() -> s.get().forEachRemaining(null));
224         assertThrowsNPE(() -> s.get().tryAdvance(null));
225     }
226 
227 
228     @Test(dataProvider = "HashableIntSpliterator")
testForEach(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)229     void testForEach(String description,
230                      Collection<HashableInteger> exp,
231                      Supplier<Spliterator<HashableInteger>> s) {
232         testForEach(exp, s, UnaryOperator.identity());
233     }
234 
235     @Test(dataProvider = "HashableIntSpliteratorWithNull")
testForEachWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)236     void testForEachWithNull(String description,
237                              Collection<HashableInteger> exp,
238                              Supplier<Spliterator<HashableInteger>> s) {
239         testForEach(exp, s, UnaryOperator.identity());
240     }
241 
242 
243     @Test(dataProvider = "HashableIntSpliterator")
testTryAdvance(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)244     void testTryAdvance(String description,
245                         Collection<HashableInteger> exp,
246                         Supplier<Spliterator<HashableInteger>> s) {
247         testTryAdvance(exp, s, UnaryOperator.identity());
248     }
249 
250     @Test(dataProvider = "HashableIntSpliteratorWithNull")
testTryAdvanceWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)251     void testTryAdvanceWithNull(String description,
252                                 Collection<HashableInteger> exp,
253                                 Supplier<Spliterator<HashableInteger>> s) {
254         testTryAdvance(exp, s, UnaryOperator.identity());
255     }
256 
257     @Test(dataProvider = "HashableIntSpliterator")
testMixedTryAdvanceForEach(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)258     void testMixedTryAdvanceForEach(String description,
259                                     Collection<HashableInteger> exp,
260                                     Supplier<Spliterator<HashableInteger>> s) {
261         testMixedTryAdvanceForEach(exp, s, UnaryOperator.identity());
262     }
263 
264     @Test(dataProvider = "HashableIntSpliteratorWithNull")
testMixedTryAdvanceForEachWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)265     void testMixedTryAdvanceForEachWithNull(String description,
266                                             Collection<HashableInteger> exp,
267                                             Supplier<Spliterator<HashableInteger>> s) {
268         testMixedTryAdvanceForEach(exp, s, UnaryOperator.identity());
269     }
270 
271     @Test(dataProvider = "HashableIntSpliterator")
testMixedTraverseAndSplit(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)272     void testMixedTraverseAndSplit(String description,
273                                    Collection<HashableInteger> exp,
274                                    Supplier<Spliterator<HashableInteger>> s) {
275         testMixedTraverseAndSplit(exp, s, UnaryOperator.identity());
276     }
277 
278     @Test(dataProvider = "HashableIntSpliteratorWithNull")
testMixedTraverseAndSplitWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)279     void testMixedTraverseAndSplitWithNull(String description,
280                                            Collection<HashableInteger> exp,
281                                            Supplier<Spliterator<HashableInteger>> s) {
282         testMixedTraverseAndSplit(exp, s, UnaryOperator.identity());
283     }
284 
285     @Test(dataProvider = "HashableIntSpliterator")
testSplitAfterFullTraversal(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)286     void testSplitAfterFullTraversal(String description,
287                                      Collection<HashableInteger> exp,
288                                      Supplier<Spliterator<HashableInteger>> s) {
289         testSplitAfterFullTraversal(s, UnaryOperator.identity());
290     }
291 
292     @Test(dataProvider = "HashableIntSpliteratorWithNull")
testSplitAfterFullTraversalWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)293     void testSplitAfterFullTraversalWithNull(String description,
294                                              Collection<HashableInteger> exp,
295                                              Supplier<Spliterator<HashableInteger>> s) {
296         testSplitAfterFullTraversal(s, UnaryOperator.identity());
297     }
298 
299 
300     @Test(dataProvider = "HashableIntSpliterator")
testSplitOnce(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)301     void testSplitOnce(String description,
302                        Collection<HashableInteger> exp,
303                        Supplier<Spliterator<HashableInteger>> s) {
304         testSplitOnce(exp, s, UnaryOperator.identity());
305     }
306 
307     @Test(dataProvider = "HashableIntSpliteratorWithNull")
testSplitOnceWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)308     void testSplitOnceWithNull(String description,
309                                Collection<HashableInteger> exp,
310                                Supplier<Spliterator<HashableInteger>> s) {
311         testSplitOnce(exp, s, UnaryOperator.identity());
312     }
313 
314     @Test(dataProvider = "HashableIntSpliterator")
testSplitSixDeep(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)315     void testSplitSixDeep(String description,
316                           Collection<HashableInteger> exp,
317                           Supplier<Spliterator<HashableInteger>> s) {
318         testSplitSixDeep(exp, s, UnaryOperator.identity());
319     }
320 
321     @Test(dataProvider = "HashableIntSpliteratorWithNull")
testSplitSixDeepWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)322     void testSplitSixDeepWithNull(String description,
323                                   Collection<HashableInteger> exp,
324                                   Supplier<Spliterator<HashableInteger>> s) {
325         testSplitSixDeep(exp, s, UnaryOperator.identity());
326     }
327 
328     @Test(dataProvider = "HashableIntSpliterator")
testSplitUntilNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)329     void testSplitUntilNull(String description,
330                             Collection<HashableInteger> exp,
331                             Supplier<Spliterator<HashableInteger>> s) {
332         testSplitUntilNull(exp, s, UnaryOperator.identity());
333     }
334 
335     @Test(dataProvider = "HashableIntSpliteratorWithNull")
testSplitUntilNullWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)336     void testSplitUntilNullWithNull(String description,
337                                     Collection<HashableInteger> exp,
338                                     Supplier<Spliterator<HashableInteger>> s) {
339         testSplitUntilNull(exp, s, UnaryOperator.identity());
340     }
341 
342 }
343