Debian Codegraph @

guava-testlib/src/com/google/common/collect/testing/Helpers.java

raw
1 /*
2 * Copyright (C) 2009 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect.testing;
18
19 import static java.util.Collections.sort;
20 import static junit.framework.Assert.assertEquals;
21 import static junit.framework.Assert.assertFalse;
22 import static junit.framework.Assert.assertTrue;
23
24 import com.google.common.annotations.GwtCompatible;
25 import com.google.common.annotations.GwtIncompatible;
26 import com.google.errorprone.annotations.CanIgnoreReturnValue;
27 import java.io.Serializable;
28 import java.lang.reflect.Method;
29 import java.util.ArrayList;
30 import java.util.Arrays;
31 import java.util.Collection;
32 import java.util.Collections;
33 import java.util.Comparator;
34 import java.util.Iterator;
35 import java.util.LinkedHashSet;
36 import java.util.List;
37 import java.util.ListIterator;
38 import java.util.Map;
39 import java.util.Map.Entry;
40 import java.util.Set;
41 import junit.framework.Assert;
42 import junit.framework.AssertionFailedError;
43 import org.checkerframework.checker.nullness.qual.Nullable;
44
45 @GwtCompatible(emulated = true)
46 public class Helpers {
47 // Clone of Objects.equal
48 static boolean equal(@Nullable Object a, @Nullable Object b) {
49 return a == b || (a != null && a.equals(b));
50 }
51
52 // Clone of Lists.newArrayList
53 public static <E> List<E> copyToList(Iterable<? extends E> elements) {
54 List<E> list = new ArrayList<>();
55 addAll(list, elements);
56 return list;
57 }
58
59 public static <E> List<E> copyToList(E[] elements) {
60 return copyToList(Arrays.asList(elements));
61 }
62
63 // Clone of Sets.newLinkedHashSet
64 public static <E> Set<E> copyToSet(Iterable<? extends E> elements) {
65 Set<E> set = new LinkedHashSet<>();
66 addAll(set, elements);
67 return set;
68 }
69
70 public static <E> Set<E> copyToSet(E[] elements) {
71 return copyToSet(Arrays.asList(elements));
72 }
73
74 // Would use Maps.immutableEntry
75 public static <K, V> Entry<K, V> mapEntry(K key, V value) {
76 return Collections.singletonMap(key, value).entrySet().iterator().next();
77 }
78
79 private static boolean isEmpty(Iterable<?> iterable) {
80 return iterable instanceof Collection
81 ? ((Collection<?>) iterable).isEmpty()
82 : !iterable.iterator().hasNext();
83 }
84
85 public static void assertEmpty(Iterable<?> iterable) {
86 if (!isEmpty(iterable)) {
87 Assert.fail("Not true that " + iterable + " is empty");
88 }
89 }
90
91 public static void assertEmpty(Map<?, ?> map) {
92 if (!map.isEmpty()) {
93 Assert.fail("Not true that " + map + " is empty");
94 }
95 }
96
97 public static void assertEqualInOrder(Iterable<?> expected, Iterable<?> actual) {
98 Iterator<?> expectedIter = expected.iterator();
99 Iterator<?> actualIter = actual.iterator();
100
101 while (expectedIter.hasNext() && actualIter.hasNext()) {
102 if (!equal(expectedIter.next(), actualIter.next())) {
103 Assert.fail(
104 "contents were not equal and in the same order: "
105 + "expected = "
106 + expected
107 + ", actual = "
108 + actual);
109 }
110 }
111
112 if (expectedIter.hasNext() || actualIter.hasNext()) {
113 // actual either had too few or too many elements
114 Assert.fail(
115 "contents were not equal and in the same order: "
116 + "expected = "
117 + expected
118 + ", actual = "
119 + actual);
120 }
121 }
122
123 public static void assertContentsInOrder(Iterable<?> actual, Object... expected) {
124 assertEqualInOrder(Arrays.asList(expected), actual);
125 }
126
127 public static void assertEqualIgnoringOrder(Iterable<?> expected, Iterable<?> actual) {
128 List<?> exp = copyToList(expected);
129 List<?> act = copyToList(actual);
130 String actString = act.toString();
131
132 // Of course we could take pains to give the complete description of the
133 // problem on any failure.
134
135 // Yeah it's n^2.
136 for (Object object : exp) {
137 if (!act.remove(object)) {
138 Assert.fail(
139 "did not contain expected element "
140 + object
141 + ", "
142 + "expected = "
143 + exp
144 + ", actual = "
145 + actString);
146 }
147 }
148 assertTrue("unexpected elements: " + act, act.isEmpty());
149 }
150
151 public static void assertContentsAnyOrder(Iterable<?> actual, Object... expected) {
152 assertEqualIgnoringOrder(Arrays.asList(expected), actual);
153 }
154
155 public static void assertContains(Iterable<?> actual, Object expected) {
156 boolean contained = false;
157 if (actual instanceof Collection) {
158 contained = ((Collection<?>) actual).contains(expected);
159 } else {
160 for (Object o : actual) {
161 if (equal(o, expected)) {
162 contained = true;
163 break;
164 }
165 }
166 }
167
168 if (!contained) {
169 Assert.fail("Not true that " + actual + " contains " + expected);
170 }
171 }
172
173 public static void assertContainsAllOf(Iterable<?> actual, Object... expected) {
174 List<Object> expectedList = new ArrayList<>(Arrays.asList(expected));
175
176 for (Object o : actual) {
177 expectedList.remove(o);
178 }
179
180 if (!expectedList.isEmpty()) {
181 Assert.fail("Not true that " + actual + " contains all of " + Arrays.asList(expected));
182 }
183 }
184
185 @CanIgnoreReturnValue
186 public static <E> boolean addAll(Collection<E> addTo, Iterable<? extends E> elementsToAdd) {
187 boolean modified = false;
188 for (E e : elementsToAdd) {
189 modified |= addTo.add(e);
190 }
191 return modified;
192 }
193
194 static <T> Iterable<T> reverse(List<T> list) {
195 return new Iterable<T>() {
196 @Override
197 public Iterator<T> iterator() {
198 ListIterator<T> listIter = list.listIterator(list.size());
199 return new Iterator<T>() {
200 @Override
201 public boolean hasNext() {
202 return listIter.hasPrevious();
203 }
204
205 @Override
206 public T next() {
207 return listIter.previous();
208 }
209
210 @Override
211 public void remove() {
212 listIter.remove();
213 }
214 };
215 }
216 };
217 }
218
219 static <T> Iterator<T> cycle(Iterable<T> iterable) {
220 return new Iterator<T>() {
221 Iterator<T> iterator = Collections.<T>emptySet().iterator();
222
223 @Override
224 public boolean hasNext() {
225 return true;
226 }
227
228 @Override
229 public T next() {
230 if (!iterator.hasNext()) {
231 iterator = iterable.iterator();
232 }
233 return iterator.next();
234 }
235
236 @Override
237 public void remove() {
238 throw new UnsupportedOperationException();
239 }
240 };
241 }
242
243 static <T> T get(Iterator<T> iterator, int position) {
244 for (int i = 0; i < position; i++) {
245 iterator.next();
246 }
247 return iterator.next();
248 }
249
250 static void fail(Throwable cause, Object message) {
251 AssertionFailedError assertionFailedError = new AssertionFailedError(String.valueOf(message));
252 assertionFailedError.initCause(cause);
253 throw assertionFailedError;
254 }
255
256 private static class EntryComparator<K, V> implements Comparator<Entry<K, V>> {
257 final @Nullable Comparator<? super K> keyComparator;
258
259 public EntryComparator(@Nullable Comparator<? super K> keyComparator) {
260 this.keyComparator = keyComparator;
261 }
262
263 @Override
264 @SuppressWarnings("unchecked") // no less safe than putting it in the map!
265 public int compare(Entry<K, V> a, Entry<K, V> b) {
266 return (keyComparator == null)
267 ? ((Comparable) a.getKey()).compareTo(b.getKey())
268 : keyComparator.compare(a.getKey(), b.getKey());
269 }
270 }
271
272 public static <K, V> Comparator<Entry<K, V>> entryComparator(
273 @Nullable Comparator<? super K> keyComparator) {
274 return new EntryComparator<K, V>(keyComparator);
275 }
276
277 /**
278 * Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
279 * consistently between their order within {@code valuesInExpectedOrder} and the order implied by
280 * the given {@code comparator}.
281 *
282 * @see #testComparator(Comparator, List)
283 */
284 public static <T> void testComparator(
285 Comparator<? super T> comparator, T... valuesInExpectedOrder) {
286 testComparator(comparator, Arrays.asList(valuesInExpectedOrder));
287 }
288
289 /**
290 * Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
291 * consistently between their order within {@code valuesInExpectedOrder} and the order implied by
292 * the given {@code comparator}.
293 *
294 * <p>In detail, this method asserts
295 *
296 * <ul>
297 * <li><i>reflexivity</i>: {@code comparator.compare(t, t) = 0} for all {@code t} in {@code
298 * valuesInExpectedOrder}; and
299 * <li><i>consistency</i>: {@code comparator.compare(ti, tj) < 0} and {@code
300 * comparator.compare(tj, ti) > 0} for {@code i < j}, where {@code ti =
301 * valuesInExpectedOrder.get(i)} and {@code tj = valuesInExpectedOrder.get(j)}.
302 * </ul>
303 */
304 public static <T> void testComparator(
305 Comparator<? super T> comparator, List<T> valuesInExpectedOrder) {
306 // This does an O(n^2) test of all pairs of values in both orders
307 for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
308 T t = valuesInExpectedOrder.get(i);
309
310 for (int j = 0; j < i; j++) {
311 T lesser = valuesInExpectedOrder.get(j);
312 assertTrue(
313 comparator + ".compare(" + lesser + ", " + t + ")", comparator.compare(lesser, t) < 0);
314 }
315
316 assertEquals(comparator + ".compare(" + t + ", " + t + ")", 0, comparator.compare(t, t));
317
318 for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
319 T greater = valuesInExpectedOrder.get(j);
320 assertTrue(
321 comparator + ".compare(" + greater + ", " + t + ")",
322 comparator.compare(greater, t) > 0);
323 }
324 }
325 }
326
327 @SuppressWarnings({"SelfComparison", "SelfEquals"})
328 public static <T extends Comparable<? super T>> void testCompareToAndEquals(
329 List<T> valuesInExpectedOrder) {
330 // This does an O(n^2) test of all pairs of values in both orders
331 for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
332 T t = valuesInExpectedOrder.get(i);
333
334 for (int j = 0; j < i; j++) {
335 T lesser = valuesInExpectedOrder.get(j);
336 assertTrue(lesser + ".compareTo(" + t + ')', lesser.compareTo(t) < 0);
337 assertFalse(lesser.equals(t));
338 }
339
340 assertEquals(t + ".compareTo(" + t + ')', 0, t.compareTo(t));
341 assertTrue(t.equals(t));
342
343 for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
344 T greater = valuesInExpectedOrder.get(j);
345 assertTrue(greater + ".compareTo(" + t + ')', greater.compareTo(t) > 0);
346 assertFalse(greater.equals(t));
347 }
348 }
349 }
350
351 /**
352 * Returns a collection that simulates concurrent modification by having its size method return
353 * incorrect values. This is useful for testing methods that must treat the return value from
354 * size() as a hint only.
355 *
356 * @param delta the difference between the true size of the collection and the values returned by
357 * the size method
358 */
359 public static <T> Collection<T> misleadingSizeCollection(int delta) {
360 // It would be nice to be able to return a real concurrent
361 // collection like ConcurrentLinkedQueue, so that e.g. concurrent
362 // iteration would work, but that would not be GWT-compatible.
363 return new ArrayList<T>() {
364 @Override
365 public int size() {
366 return Math.max(0, super.size() + delta);
367 }
368 };
369 }
370
371 /**
372 * Returns a "nefarious" map entry with the specified key and value, meaning an entry that is
373 * suitable for testing that map entries cannot be modified via a nefarious implementation of
374 * equals. This is used for testing unmodifiable collections of map entries; for example, it
375 * should not be possible to access the raw (modifiable) map entry via a nefarious equals method.
376 */
377 public static <K, V> Entry<K, V> nefariousMapEntry(K key, V value) {
378 return new Entry<K, V>() {
379 @Override
380 public K getKey() {
381 return key;
382 }
383
384 @Override
385 public V getValue() {
386 return value;
387 }
388
389 @Override
390 public V setValue(V value) {
391 throw new UnsupportedOperationException();
392 }
393
394 @SuppressWarnings("unchecked")
395 @Override
396 public boolean equals(@Nullable Object o) {
397 if (o instanceof Entry) {
398 Entry<K, V> e = (Entry<K, V>) o;
399 e.setValue(value); // muhahaha!
400
401 return equal(this.getKey(), e.getKey()) && equal(this.getValue(), e.getValue());
402 }
403 return false;
404 }
405
406 @Override
407 public int hashCode() {
408 K k = getKey();
409 V v = getValue();
410 return ((k == null) ? 0 : k.hashCode()) ^ ((v == null) ? 0 : v.hashCode());
411 }
412
413 @Override
414 public String toString() {
415 return getKey() + "=" + getValue();
416 }
417 };
418 }
419
420 static <E> List<E> castOrCopyToList(Iterable<E> iterable) {
421 if (iterable instanceof List) {
422 return (List<E>) iterable;
423 }
424 List<E> list = new ArrayList<>();
425 for (E e : iterable) {
426 list.add(e);
427 }
428 return list;
429 }
430
431 private static final Comparator<Comparable> NATURAL_ORDER =
432 new Comparator<Comparable>() {
433 @SuppressWarnings("unchecked") // assume any Comparable is Comparable<Self>
434 @Override
435 public int compare(Comparable left, Comparable right) {
436 return left.compareTo(right);
437 }
438 };
439
440 public static <K extends Comparable, V> Iterable<Entry<K, V>> orderEntriesByKey(
441 List<Entry<K, V>> insertionOrder) {
442 sort(insertionOrder, Helpers.<K, V>entryComparator(NATURAL_ORDER));
443 return insertionOrder;
444 }
445
446 /**
447 * Private replacement for {@link com.google.gwt.user.client.rpc.GwtTransient} to work around
448 * build-system quirks.
449 */
450 private @interface GwtTransient {}
451
452 /**
453 * Compares strings in natural order except that null comes immediately before a given value. This
454 * works better than Ordering.natural().nullsFirst() because, if null comes before all other
455 * values, it lies outside the submap/submultiset ranges we test, and the variety of tests that
456 * exercise null handling fail on those subcollections.
457 */
458 public abstract static class NullsBefore implements Comparator<String>, Serializable {
459 /*
460 * We don't serialize this class in GWT, so we don't care about whether GWT will serialize this
461 * field.
462 */
463 @GwtTransient private final String justAfterNull;
464
465 protected NullsBefore(String justAfterNull) {
466 if (justAfterNull == null) {
467 throw new NullPointerException();
468 }
469
470 this.justAfterNull = justAfterNull;
471 }
472
473 @Override
474 public int compare(@Nullable String lhs, @Nullable String rhs) {
475 if (lhs == rhs) {
476 return 0;
477 }
478 if (lhs == null) {
479 // lhs (null) comes just before justAfterNull.
480 // If rhs is b, lhs comes first.
481 if (rhs.equals(justAfterNull)) {
482 return -1;
483 }
484 return justAfterNull.compareTo(rhs);
485 }
486 if (rhs == null) {
487 // rhs (null) comes just before justAfterNull.
488 // If lhs is b, rhs comes first.
489 if (lhs.equals(justAfterNull)) {
490 return 1;
491 }
492 return lhs.compareTo(justAfterNull);
493 }
494 return lhs.compareTo(rhs);
495 }
496
497 @Override
498 public boolean equals(@Nullable Object obj) {
499 if (obj instanceof NullsBefore) {
500 NullsBefore other = (NullsBefore) obj;
501 return justAfterNull.equals(other.justAfterNull);
502 }
503 return false;
504 }
505
506 @Override
507 public int hashCode() {
508 return justAfterNull.hashCode();
509 }
510 }
511
512 public static final class NullsBeforeB extends NullsBefore {
513 public static final NullsBeforeB INSTANCE = new NullsBeforeB();
514
515 private NullsBeforeB() {
516 super("b");
517 }
518 }
519
520 public static final class NullsBeforeTwo extends NullsBefore {
521 public static final NullsBeforeTwo INSTANCE = new NullsBeforeTwo();
522
523 private NullsBeforeTwo() {
524 super("two"); // from TestStringSortedMapGenerator's sample keys
525 }
526 }
527
528 @GwtIncompatible // reflection
529 public static Method getMethod(Class<?> clazz, String name) {
530 try {
531 return clazz.getMethod(name);
532 } catch (Exception e) {
533 throw new IllegalArgumentException(e);
534 }
535 }
536 }