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
33import org.testng.annotations.DataProvider;
34import org.testng.annotations.Test;
35
36import java.util.ArrayList;
37import java.util.Arrays;
38import java.util.Collection;
39import java.util.Collections;
40import java.util.HashMap;
41import java.util.HashSet;
42import java.util.LinkedHashMap;
43import java.util.LinkedHashSet;
44import java.util.List;
45import java.util.Map;
46import java.util.Spliterator;
47import java.util.SpliteratorTestHelper;
48import java.util.TreeSet;
49import java.util.function.Function;
50import java.util.function.Supplier;
51import java.util.function.UnaryOperator;
52
53public 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
62        SpliteratorDataBuilder(List<Object[]> data, List<T> exp) {
63            this.data = data;
64            this.exp = exp;
65            this.mExp = createMap(exp);
66        }
67
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
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
81        void add(String description, Supplier<Spliterator<?>> s) {
82            add(description, exp, s);
83        }
84
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
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
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
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")
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")
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
168        HashableInteger(int value, int hashmask) {
169            this.value = value;
170            this.hashmask = hashmask;
171        }
172
173        @Override
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
185        public int hashCode() {
186            return value % hashmask;
187        }
188
189        @Override
190        public int compareTo(HashableInteger o) {
191            return value - o.value;
192        }
193
194        @Override
195        public String toString() {
196            return Integer.toString(value);
197        }
198    }
199
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")
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")
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")
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")
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")
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")
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")
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")
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")
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")
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")
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")
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")
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")
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")
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")
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")
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")
336    void testSplitUntilNullWithNull(String description,
337                                    Collection<HashableInteger> exp,
338                                    Supplier<Spliterator<HashableInteger>> s) {
339        testSplitUntilNull(exp, s, UnaryOperator.identity());
340    }
341
342}
343