001/*
002 * Copyright (C) 2009 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect.testing;
018
019import static java.util.Collections.sort;
020import static junit.framework.Assert.assertEquals;
021import static junit.framework.Assert.assertFalse;
022import static junit.framework.Assert.assertTrue;
023
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.annotations.GwtIncompatible;
026import com.google.errorprone.annotations.CanIgnoreReturnValue;
027import java.io.Serializable;
028import java.lang.reflect.Method;
029import java.util.ArrayList;
030import java.util.Arrays;
031import java.util.Collection;
032import java.util.Collections;
033import java.util.Comparator;
034import java.util.Iterator;
035import java.util.LinkedHashSet;
036import java.util.List;
037import java.util.ListIterator;
038import java.util.Map;
039import java.util.Map.Entry;
040import java.util.Set;
041import junit.framework.Assert;
042import junit.framework.AssertionFailedError;
043import org.checkerframework.checker.nullness.qual.Nullable;
044
045@GwtCompatible(emulated = true)
046public class Helpers {
047  // Clone of Objects.equal
048  static boolean equal(@Nullable Object a, @Nullable Object b) {
049    return a == b || (a != null && a.equals(b));
050  }
051
052  // Clone of Lists.newArrayList
053  public static <E> List<E> copyToList(Iterable<? extends E> elements) {
054    List<E> list = new ArrayList<>();
055    addAll(list, elements);
056    return list;
057  }
058
059  public static <E> List<E> copyToList(E[] elements) {
060    return copyToList(Arrays.asList(elements));
061  }
062
063  // Clone of Sets.newLinkedHashSet
064  public static <E> Set<E> copyToSet(Iterable<? extends E> elements) {
065    Set<E> set = new LinkedHashSet<>();
066    addAll(set, elements);
067    return set;
068  }
069
070  public static <E> Set<E> copyToSet(E[] elements) {
071    return copyToSet(Arrays.asList(elements));
072  }
073
074  // Would use Maps.immutableEntry
075  public static <K, V> Entry<K, V> mapEntry(K key, V value) {
076    return Collections.singletonMap(key, value).entrySet().iterator().next();
077  }
078
079  private static boolean isEmpty(Iterable<?> iterable) {
080    return iterable instanceof Collection
081        ? ((Collection<?>) iterable).isEmpty()
082        : !iterable.iterator().hasNext();
083  }
084
085  public static void assertEmpty(Iterable<?> iterable) {
086    if (!isEmpty(iterable)) {
087      Assert.fail("Not true that " + iterable + " is empty");
088    }
089  }
090
091  public static void assertEmpty(Map<?, ?> map) {
092    if (!map.isEmpty()) {
093      Assert.fail("Not true that " + map + " is empty");
094    }
095  }
096
097  public static void assertEqualInOrder(Iterable<?> expected, Iterable<?> actual) {
098    Iterator<?> expectedIter = expected.iterator();
099    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}