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 com.google.common.base.Preconditions.checkNotNull;
020import static java.lang.Math.max;
021import static java.util.Arrays.asList;
022import static java.util.Collections.sort;
023import static junit.framework.Assert.assertEquals;
024import static junit.framework.Assert.assertFalse;
025import static junit.framework.Assert.assertTrue;
026import static junit.framework.Assert.fail;
027
028import com.google.common.annotations.GwtCompatible;
029import com.google.common.annotations.GwtIncompatible;
030import com.google.common.annotations.J2ktIncompatible;
031import com.google.errorprone.annotations.CanIgnoreReturnValue;
032import java.io.Serializable;
033import java.lang.reflect.Method;
034import java.util.AbstractList;
035import java.util.AbstractMap.SimpleImmutableEntry;
036import java.util.ArrayList;
037import java.util.Collection;
038import java.util.Collections;
039import java.util.Comparator;
040import java.util.Iterator;
041import java.util.LinkedHashSet;
042import java.util.List;
043import java.util.ListIterator;
044import java.util.Map;
045import java.util.Map.Entry;
046import java.util.Objects;
047import java.util.Set;
048import org.jspecify.annotations.NullMarked;
049import org.jspecify.annotations.Nullable;
050
051@GwtCompatible
052@NullMarked
053public class Helpers {
054  // Clone of Lists.newArrayList
055  public static <E extends @Nullable Object> List<E> copyToList(Iterable<? extends E> elements) {
056    List<E> list = new ArrayList<>();
057    addAll(list, elements);
058    return list;
059  }
060
061  public static <E extends @Nullable Object> List<E> copyToList(E[] elements) {
062    return copyToList(asList(elements));
063  }
064
065  // Clone of Sets.newLinkedHashSet
066  public static <E extends @Nullable Object> Set<E> copyToSet(Iterable<? extends E> elements) {
067    Set<E> set = new LinkedHashSet<>();
068    addAll(set, elements);
069    return set;
070  }
071
072  public static <E extends @Nullable Object> Set<E> copyToSet(E[] elements) {
073    return copyToSet(asList(elements));
074  }
075
076  public static <K extends @Nullable Object, V extends @Nullable Object> Entry<K, V> mapEntry(
077      K key, V value) {
078    return new SimpleImmutableEntry<>(key, value);
079  }
080
081  private static boolean isEmpty(Iterable<?> iterable) {
082    return iterable instanceof Collection
083        ? ((Collection<?>) iterable).isEmpty()
084        : !iterable.iterator().hasNext();
085  }
086
087  public static void assertEmpty(Iterable<?> iterable) {
088    if (!isEmpty(iterable)) {
089      fail("Not true that " + iterable + " is empty");
090    }
091  }
092
093  public static void assertEmpty(Map<?, ?> map) {
094    if (!map.isEmpty()) {
095      fail("Not true that " + map + " is empty");
096    }
097  }
098
099  public static void assertEqualInOrder(Iterable<?> expected, Iterable<?> actual) {
100    Iterator<?> expectedIter = expected.iterator();
101    Iterator<?> actualIter = actual.iterator();
102
103    while (expectedIter.hasNext() && actualIter.hasNext()) {
104      if (!Objects.equals(expectedIter.next(), actualIter.next())) {
105        fail(
106            "contents were not equal and in the same order: "
107                + "expected = "
108                + expected
109                + ", actual = "
110                + actual);
111      }
112    }
113
114    if (expectedIter.hasNext() || actualIter.hasNext()) {
115      // actual either had too few or too many elements
116      fail(
117          "contents were not equal and in the same order: "
118              + "expected = "
119              + expected
120              + ", actual = "
121              + actual);
122    }
123  }
124
125  public static void assertContentsInOrder(Iterable<?> actual, @Nullable Object... expected) {
126    assertEqualInOrder(asList(expected), actual);
127  }
128
129  public static void assertEqualIgnoringOrder(Iterable<?> expected, Iterable<?> actual) {
130    List<?> exp = copyToList(expected);
131    List<?> act = copyToList(actual);
132    String actString = act.toString();
133
134    // Of course we could take pains to give the complete description of the
135    // problem on any failure.
136
137    // Yeah it's n^2.
138    for (Object object : exp) {
139      if (!act.remove(object)) {
140        fail(
141            "did not contain expected element "
142                + object
143                + ", "
144                + "expected = "
145                + exp
146                + ", actual = "
147                + actString);
148      }
149    }
150    assertTrue("unexpected elements: " + act, act.isEmpty());
151  }
152
153  public static void assertContentsAnyOrder(Iterable<?> actual, @Nullable Object... expected) {
154    assertEqualIgnoringOrder(asList(expected), actual);
155  }
156
157  public static void assertContains(Iterable<?> actual, @Nullable Object expected) {
158    boolean contained = false;
159    if (actual instanceof Collection) {
160      contained = ((Collection<?>) actual).contains(expected);
161    } else {
162      for (Object o : actual) {
163        if (Objects.equals(o, expected)) {
164          contained = true;
165          break;
166        }
167      }
168    }
169
170    if (!contained) {
171      fail("Not true that " + actual + " contains " + expected);
172    }
173  }
174
175  public static void assertContainsAllOf(Iterable<?> actual, @Nullable Object... expected) {
176    List<Object> expectedList = new ArrayList<>(asList(expected));
177
178    for (Object o : actual) {
179      expectedList.remove(o);
180    }
181
182    if (!expectedList.isEmpty()) {
183      fail("Not true that " + actual + " contains all of " + asList(expected));
184    }
185  }
186
187  @CanIgnoreReturnValue
188  public static <E extends @Nullable Object> boolean addAll(
189      Collection<E> addTo, Iterable<? extends E> elementsToAdd) {
190    boolean modified = false;
191    for (E e : elementsToAdd) {
192      modified |= addTo.add(e);
193    }
194    return modified;
195  }
196
197  static <T extends @Nullable Object> Iterable<T> reverse(List<T> list) {
198    return () ->
199        new Iterator<T>() {
200          private final ListIterator<T> listIter = list.listIterator(list.size());
201
202          @Override
203          public boolean hasNext() {
204            return listIter.hasPrevious();
205          }
206
207          @Override
208          public T next() {
209            return listIter.previous();
210          }
211
212          @Override
213          public void remove() {
214            listIter.remove();
215          }
216        };
217  }
218
219  static <T extends @Nullable Object> 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 extends @Nullable Object> 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  private static final class EntryComparator<K extends @Nullable Object, V extends @Nullable Object>
251      implements Comparator<Entry<K, V>> {
252    final @Nullable Comparator<? super K> keyComparator;
253
254    EntryComparator(@Nullable Comparator<? super K> keyComparator) {
255      this.keyComparator = keyComparator;
256    }
257
258    @Override
259    @SuppressWarnings("unchecked") // no less safe than putting it in the map!
260    public int compare(Entry<K, V> a, Entry<K, V> b) {
261      return (keyComparator == null)
262          ? ((Comparable) a.getKey()).compareTo(b.getKey())
263          : keyComparator.compare(a.getKey(), b.getKey());
264    }
265  }
266
267  public static <K extends @Nullable Object, V extends @Nullable Object>
268      Comparator<Entry<K, V>> entryComparator(@Nullable Comparator<? super K> keyComparator) {
269    return new EntryComparator<K, V>(keyComparator);
270  }
271
272  /**
273   * Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
274   * consistently between their order within {@code valuesInExpectedOrder} and the order implied by
275   * the given {@code comparator}.
276   *
277   * @see #testComparator(Comparator, List)
278   */
279  public static <T extends @Nullable Object> void testComparator(
280      Comparator<? super T> comparator, T... valuesInExpectedOrder) {
281    testComparator(comparator, asList(valuesInExpectedOrder));
282  }
283
284  /**
285   * Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
286   * consistently between their order within {@code valuesInExpectedOrder} and the order implied by
287   * the given {@code comparator}.
288   *
289   * <p>In detail, this method asserts
290   *
291   * <ul>
292   *   <li><i>reflexivity</i>: {@code comparator.compare(t, t) = 0} for all {@code t} in {@code
293   *       valuesInExpectedOrder}; and
294   *   <li><i>consistency</i>: {@code comparator.compare(ti, tj) < 0} and {@code
295   *       comparator.compare(tj, ti) > 0} for {@code i < j}, where {@code ti =
296   *       valuesInExpectedOrder.get(i)} and {@code tj = valuesInExpectedOrder.get(j)}.
297   * </ul>
298   */
299  public static <T extends @Nullable Object> void testComparator(
300      Comparator<? super T> comparator, List<T> valuesInExpectedOrder) {
301    // This does an O(n^2) test of all pairs of values in both orders
302    for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
303      T t = valuesInExpectedOrder.get(i);
304
305      for (int j = 0; j < i; j++) {
306        T lesser = valuesInExpectedOrder.get(j);
307        assertTrue(
308            comparator + ".compare(" + lesser + ", " + t + ")", comparator.compare(lesser, t) < 0);
309      }
310
311      assertEquals(comparator + ".compare(" + t + ", " + t + ")", 0, comparator.compare(t, t));
312
313      for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
314        T greater = valuesInExpectedOrder.get(j);
315        assertTrue(
316            comparator + ".compare(" + greater + ", " + t + ")",
317            comparator.compare(greater, t) > 0);
318      }
319    }
320  }
321
322  @SuppressWarnings({"SelfComparison", "SelfEquals"})
323  public static <T extends Comparable<? super T>> void testCompareToAndEquals(
324      List<T> valuesInExpectedOrder) {
325    // This does an O(n^2) test of all pairs of values in both orders
326    for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
327      T t = valuesInExpectedOrder.get(i);
328
329      for (int j = 0; j < i; j++) {
330        T lesser = valuesInExpectedOrder.get(j);
331        assertTrue(lesser + ".compareTo(" + t + ')', lesser.compareTo(t) < 0);
332        assertFalse(lesser.equals(t));
333      }
334
335      assertEquals(t + ".compareTo(" + t + ')', 0, t.compareTo(t));
336      assertTrue(t.equals(t));
337
338      for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
339        T greater = valuesInExpectedOrder.get(j);
340        assertTrue(greater + ".compareTo(" + t + ')', greater.compareTo(t) > 0);
341        assertFalse(greater.equals(t));
342      }
343    }
344  }
345
346  /**
347   * Returns a collection that simulates concurrent modification by having its size method return
348   * incorrect values. This is useful for testing methods that must treat the return value from
349   * size() as a hint only.
350   *
351   * @param delta the difference between the true size of the collection and the values returned by
352   *     the size method
353   */
354  public static <T extends @Nullable Object> Collection<T> misleadingSizeCollection(int delta) {
355    // It would be nice to be able to return a real concurrent
356    // collection like ConcurrentLinkedQueue, so that e.g. concurrent
357    // iteration would work, but that would not be GWT-compatible.
358    // We are not "just" inheriting from ArrayList here as this doesn't work for J2kt.
359    return new AbstractList<T>() {
360      final ArrayList<T> data = new ArrayList<>();
361
362      @Override
363      public int size() {
364        return max(0, data.size() + delta);
365      }
366
367      @Override
368      public T get(int index) {
369        return data.get(index);
370      }
371
372      @Override
373      public T set(int index, T element) {
374        return data.set(index, element);
375      }
376
377      @Override
378      public boolean add(T element) {
379        return data.add(element);
380      }
381
382      @Override
383      public void add(int index, T element) {
384        data.add(index, element);
385      }
386
387      @Override
388      public T remove(int index) {
389        return data.remove(index);
390      }
391
392      @Override
393      public @Nullable Object[] toArray() {
394        return data.toArray();
395      }
396    };
397  }
398
399  /**
400   * Returns a "nefarious" map entry with the specified key and value, meaning an entry that is
401   * suitable for testing that map entries cannot be modified via a nefarious implementation of
402   * equals. This is used for testing unmodifiable collections of map entries; for example, it
403   * should not be possible to access the raw (modifiable) map entry via a nefarious equals method.
404   */
405  public static <K extends @Nullable Object, V extends @Nullable Object>
406      Entry<K, V> nefariousMapEntry(K key, V value) {
407    return new Entry<K, V>() {
408      @Override
409      public K getKey() {
410        return key;
411      }
412
413      @Override
414      public V getValue() {
415        return value;
416      }
417
418      @Override
419      public V setValue(V value) {
420        throw new UnsupportedOperationException();
421      }
422
423      @SuppressWarnings("unchecked")
424      @Override
425      public boolean equals(@Nullable Object o) {
426        if (o instanceof Entry) {
427          Entry<K, V> e = (Entry<K, V>) o;
428          e.setValue(value); // muhahaha!
429
430          return Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue());
431        }
432        return false;
433      }
434
435      @Override
436      public int hashCode() {
437        K k = getKey();
438        V v = getValue();
439        return ((k == null) ? 0 : k.hashCode()) ^ ((v == null) ? 0 : v.hashCode());
440      }
441
442      @Override
443      public String toString() {
444        return getKey() + "=" + getValue();
445      }
446    };
447  }
448
449  static <E extends @Nullable Object> List<E> castOrCopyToList(Iterable<E> iterable) {
450    if (iterable instanceof List) {
451      return (List<E>) iterable;
452    }
453    List<E> list = new ArrayList<>();
454    for (E e : iterable) {
455      list.add(e);
456    }
457    return list;
458  }
459
460  @SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989
461  public static <K extends Comparable, V extends @Nullable Object>
462      Iterable<Entry<K, V>> orderEntriesByKey(List<Entry<K, V>> insertionOrder) {
463    @SuppressWarnings("unchecked") // assume any Comparable is Comparable<Self>
464    Comparator<? super K> keyComparator = (o1, o2) -> o1.compareTo(o2);
465    sort(insertionOrder, entryComparator(keyComparator));
466    return insertionOrder;
467  }
468
469  /**
470   * Compares strings in natural order except that null comes immediately before a given value. This
471   * works better than Ordering.natural().nullsFirst() because, if null comes before all other
472   * values, it lies outside the submap/submultiset ranges we test, and the variety of tests that
473   * exercise null handling fail on those subcollections.
474   */
475  public abstract static class NullsBefore implements Comparator<@Nullable String>, Serializable {
476    private final String justAfterNull;
477
478    protected NullsBefore(String justAfterNull) {
479      this.justAfterNull = checkNotNull(justAfterNull);
480    }
481
482    @Override
483    public int compare(@Nullable String lhs, @Nullable String rhs) {
484      if (lhs == rhs) {
485        return 0;
486      }
487      if (lhs == null) {
488        // lhs (null) comes just before justAfterNull.
489        // If rhs is b, lhs comes first.
490        if (rhs.equals(justAfterNull)) {
491          return -1;
492        }
493        return justAfterNull.compareTo(rhs);
494      }
495      if (rhs == null) {
496        // rhs (null) comes just before justAfterNull.
497        // If lhs is b, rhs comes first.
498        if (lhs.equals(justAfterNull)) {
499          return 1;
500        }
501        return lhs.compareTo(justAfterNull);
502      }
503      return lhs.compareTo(rhs);
504    }
505
506    @Override
507    public boolean equals(@Nullable Object obj) {
508      if (obj instanceof NullsBefore) {
509        NullsBefore other = (NullsBefore) obj;
510        return justAfterNull.equals(other.justAfterNull);
511      }
512      return false;
513    }
514
515    @Override
516    public int hashCode() {
517      return justAfterNull.hashCode();
518    }
519  }
520
521  public static final class NullsBeforeB extends NullsBefore {
522    public static final NullsBeforeB INSTANCE = new NullsBeforeB();
523
524    private NullsBeforeB() {
525      super("b");
526    }
527  }
528
529  public static final class NullsBeforeTwo extends NullsBefore {
530    public static final NullsBeforeTwo INSTANCE = new NullsBeforeTwo();
531
532    private NullsBeforeTwo() {
533      super("two"); // from TestStringSortedMapGenerator's sample keys
534    }
535  }
536
537  @J2ktIncompatible
538  @GwtIncompatible // reflection
539  public static Method getMethod(Class<?> clazz, String name) {
540    try {
541      return clazz.getMethod(name);
542    } catch (Exception e) {
543      throw new IllegalArgumentException(e);
544    }
545  }
546
547  /**
548   * Useless constructor for a class of static utility methods.
549   *
550   * @deprecated Do not instantiate this utility class.
551   */
552  @Deprecated
553  public Helpers() {}
554}