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.collect.testing.Helpers.entryComparator;
020import static java.lang.Math.max;
021import static java.util.Arrays.asList;
022import static java.util.Collections.singletonMap;
023import static java.util.Collections.sort;
024import static junit.framework.Assert.assertEquals;
025import static junit.framework.Assert.assertFalse;
026import static junit.framework.Assert.assertTrue;
027import static junit.framework.Assert.fail;
028
029import com.google.common.annotations.GwtCompatible;
030import com.google.common.annotations.GwtIncompatible;
031import com.google.common.annotations.J2ktIncompatible;
032import com.google.errorprone.annotations.CanIgnoreReturnValue;
033import java.io.Serializable;
034import java.lang.reflect.Method;
035import java.util.AbstractList;
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.Set;
047import org.jspecify.annotations.NullMarked;
048import org.jspecify.annotations.Nullable;
049
050@GwtCompatible(emulated = true)
051@NullMarked
052public class Helpers {
053  // Clone of Objects.equal
054  static boolean equal(@Nullable Object a, @Nullable Object b) {
055    return a == b || (a != null && a.equals(b));
056  }
057
058  // Clone of Lists.newArrayList
059  public static <E extends @Nullable Object> List<E> copyToList(Iterable<? extends E> elements) {
060    List<E> list = new ArrayList<>();
061    addAll(list, elements);
062    return list;
063  }
064
065  public static <E extends @Nullable Object> List<E> copyToList(E[] elements) {
066    return copyToList(asList(elements));
067  }
068
069  // Clone of Sets.newLinkedHashSet
070  public static <E extends @Nullable Object> Set<E> copyToSet(Iterable<? extends E> elements) {
071    Set<E> set = new LinkedHashSet<>();
072    addAll(set, elements);
073    return set;
074  }
075
076  public static <E extends @Nullable Object> Set<E> copyToSet(E[] elements) {
077    return copyToSet(asList(elements));
078  }
079
080  // Would use Maps.immutableEntry
081  public static <K extends @Nullable Object, V extends @Nullable Object> Entry<K, V> mapEntry(
082      K key, V value) {
083    return singletonMap(key, value).entrySet().iterator().next();
084  }
085
086  private static boolean isEmpty(Iterable<?> iterable) {
087    return iterable instanceof Collection
088        ? ((Collection<?>) iterable).isEmpty()
089        : !iterable.iterator().hasNext();
090  }
091
092  public static void assertEmpty(Iterable<?> iterable) {
093    if (!isEmpty(iterable)) {
094      fail("Not true that " + iterable + " is empty");
095    }
096  }
097
098  public static void assertEmpty(Map<?, ?> map) {
099    if (!map.isEmpty()) {
100      fail("Not true that " + map + " is empty");
101    }
102  }
103
104  public static void assertEqualInOrder(Iterable<?> expected, Iterable<?> actual) {
105    Iterator<?> expectedIter = expected.iterator();
106    Iterator<?> actualIter = actual.iterator();
107
108    while (expectedIter.hasNext() && actualIter.hasNext()) {
109      if (!equal(expectedIter.next(), actualIter.next())) {
110        fail(
111            "contents were not equal and in the same order: "
112                + "expected = "
113                + expected
114                + ", actual = "
115                + actual);
116      }
117    }
118
119    if (expectedIter.hasNext() || actualIter.hasNext()) {
120      // actual either had too few or too many elements
121      fail(
122          "contents were not equal and in the same order: "
123              + "expected = "
124              + expected
125              + ", actual = "
126              + actual);
127    }
128  }
129
130  public static void assertContentsInOrder(Iterable<?> actual, Object... expected) {
131    assertEqualInOrder(asList(expected), actual);
132  }
133
134  public static void assertEqualIgnoringOrder(Iterable<?> expected, Iterable<?> actual) {
135    List<?> exp = copyToList(expected);
136    List<?> act = copyToList(actual);
137    String actString = act.toString();
138
139    // Of course we could take pains to give the complete description of the
140    // problem on any failure.
141
142    // Yeah it's n^2.
143    for (Object object : exp) {
144      if (!act.remove(object)) {
145        fail(
146            "did not contain expected element "
147                + object
148                + ", "
149                + "expected = "
150                + exp
151                + ", actual = "
152                + actString);
153      }
154    }
155    assertTrue("unexpected elements: " + act, act.isEmpty());
156  }
157
158  public static void assertContentsAnyOrder(Iterable<?> actual, Object... expected) {
159    assertEqualIgnoringOrder(asList(expected), actual);
160  }
161
162  public static void assertContains(Iterable<?> actual, Object expected) {
163    boolean contained = false;
164    if (actual instanceof Collection) {
165      contained = ((Collection<?>) actual).contains(expected);
166    } else {
167      for (Object o : actual) {
168        if (equal(o, expected)) {
169          contained = true;
170          break;
171        }
172      }
173    }
174
175    if (!contained) {
176      fail("Not true that " + actual + " contains " + expected);
177    }
178  }
179
180  public static void assertContainsAllOf(Iterable<?> actual, Object... expected) {
181    List<Object> expectedList = new ArrayList<>(asList(expected));
182
183    for (Object o : actual) {
184      expectedList.remove(o);
185    }
186
187    if (!expectedList.isEmpty()) {
188      fail("Not true that " + actual + " contains all of " + asList(expected));
189    }
190  }
191
192  @CanIgnoreReturnValue
193  public static <E extends @Nullable Object> boolean addAll(
194      Collection<E> addTo, Iterable<? extends E> elementsToAdd) {
195    boolean modified = false;
196    for (E e : elementsToAdd) {
197      modified |= addTo.add(e);
198    }
199    return modified;
200  }
201
202  static <T extends @Nullable Object> Iterable<T> reverse(List<T> list) {
203    return () ->
204        new Iterator<T>() {
205          private final ListIterator<T> listIter = list.listIterator(list.size());
206
207          @Override
208          public boolean hasNext() {
209            return listIter.hasPrevious();
210          }
211
212          @Override
213          public T next() {
214            return listIter.previous();
215          }
216
217          @Override
218          public void remove() {
219            listIter.remove();
220          }
221        };
222  }
223
224  static <T extends @Nullable Object> Iterator<T> cycle(Iterable<T> iterable) {
225    return new Iterator<T>() {
226      Iterator<T> iterator = Collections.<T>emptySet().iterator();
227
228      @Override
229      public boolean hasNext() {
230        return true;
231      }
232
233      @Override
234      public T next() {
235        if (!iterator.hasNext()) {
236          iterator = iterable.iterator();
237        }
238        return iterator.next();
239      }
240
241      @Override
242      public void remove() {
243        throw new UnsupportedOperationException();
244      }
245    };
246  }
247
248  static <T extends @Nullable Object> T get(Iterator<T> iterator, int position) {
249    for (int i = 0; i < position; i++) {
250      iterator.next();
251    }
252    return iterator.next();
253  }
254
255  private static class EntryComparator<K extends @Nullable Object, V extends @Nullable Object>
256      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 extends @Nullable Object, V extends @Nullable Object>
273      Comparator<Entry<K, V>> entryComparator(@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 extends @Nullable Object> void testComparator(
285      Comparator<? super T> comparator, T... valuesInExpectedOrder) {
286    testComparator(comparator, 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 extends @Nullable Object> 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 extends @Nullable Object> 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    // We are not "just" inheriting from ArrayList here as this doesn't work for J2kt.
364    return new AbstractList<T>() {
365      ArrayList<T> data = new ArrayList<>();
366
367      @Override
368      public int size() {
369        return max(0, data.size() + delta);
370      }
371
372      @Override
373      public T get(int index) {
374        return data.get(index);
375      }
376
377      @Override
378      public T set(int index, T element) {
379        return data.set(index, element);
380      }
381
382      @Override
383      public boolean add(T element) {
384        return data.add(element);
385      }
386
387      @Override
388      public void add(int index, T element) {
389        data.add(index, element);
390      }
391
392      @Override
393      public T remove(int index) {
394        return data.remove(index);
395      }
396
397      @Override
398      public @Nullable Object[] toArray() {
399        return data.toArray();
400      }
401    };
402  }
403
404  /**
405   * Returns a "nefarious" map entry with the specified key and value, meaning an entry that is
406   * suitable for testing that map entries cannot be modified via a nefarious implementation of
407   * equals. This is used for testing unmodifiable collections of map entries; for example, it
408   * should not be possible to access the raw (modifiable) map entry via a nefarious equals method.
409   */
410  public static <K extends @Nullable Object, V extends @Nullable Object>
411      Entry<K, V> nefariousMapEntry(K key, V value) {
412    return new Entry<K, V>() {
413      @Override
414      public K getKey() {
415        return key;
416      }
417
418      @Override
419      public V getValue() {
420        return value;
421      }
422
423      @Override
424      public V setValue(V value) {
425        throw new UnsupportedOperationException();
426      }
427
428      @SuppressWarnings("unchecked")
429      @Override
430      public boolean equals(@Nullable Object o) {
431        if (o instanceof Entry) {
432          Entry<K, V> e = (Entry<K, V>) o;
433          e.setValue(value); // muhahaha!
434
435          return equal(this.getKey(), e.getKey()) && equal(this.getValue(), e.getValue());
436        }
437        return false;
438      }
439
440      @Override
441      public int hashCode() {
442        K k = getKey();
443        V v = getValue();
444        return ((k == null) ? 0 : k.hashCode()) ^ ((v == null) ? 0 : v.hashCode());
445      }
446
447      @Override
448      public String toString() {
449        return getKey() + "=" + getValue();
450      }
451    };
452  }
453
454  static <E extends @Nullable Object> List<E> castOrCopyToList(Iterable<E> iterable) {
455    if (iterable instanceof List) {
456      return (List<E>) iterable;
457    }
458    List<E> list = new ArrayList<>();
459    for (E e : iterable) {
460      list.add(e);
461    }
462    return list;
463  }
464
465  @SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989
466  public static <K extends Comparable, V extends @Nullable Object>
467      Iterable<Entry<K, V>> orderEntriesByKey(List<Entry<K, V>> insertionOrder) {
468    @SuppressWarnings("unchecked") // assume any Comparable is Comparable<Self>
469    Comparator<? super K> keyComparator = (Comparator<? super K>) Comparable::compareTo;
470    sort(insertionOrder, entryComparator(keyComparator));
471    return insertionOrder;
472  }
473
474  /**
475   * Private replacement for {@link com.google.gwt.user.client.rpc.GwtTransient} to work around
476   * build-system quirks.
477   */
478  private @interface GwtTransient {}
479
480  /**
481   * Compares strings in natural order except that null comes immediately before a given value. This
482   * works better than Ordering.natural().nullsFirst() because, if null comes before all other
483   * values, it lies outside the submap/submultiset ranges we test, and the variety of tests that
484   * exercise null handling fail on those subcollections.
485   */
486  public abstract static class NullsBefore implements Comparator<@Nullable String>, Serializable {
487    /*
488     * We don't serialize this class in GWT, so we don't care about whether GWT will serialize this
489     * field.
490     */
491    @GwtTransient private final String justAfterNull;
492
493    protected NullsBefore(String justAfterNull) {
494      if (justAfterNull == null) {
495        throw new NullPointerException();
496      }
497
498      this.justAfterNull = justAfterNull;
499    }
500
501    @Override
502    public int compare(@Nullable String lhs, @Nullable String rhs) {
503      if (lhs == rhs) {
504        return 0;
505      }
506      if (lhs == null) {
507        // lhs (null) comes just before justAfterNull.
508        // If rhs is b, lhs comes first.
509        if (rhs.equals(justAfterNull)) {
510          return -1;
511        }
512        return justAfterNull.compareTo(rhs);
513      }
514      if (rhs == null) {
515        // rhs (null) comes just before justAfterNull.
516        // If lhs is b, rhs comes first.
517        if (lhs.equals(justAfterNull)) {
518          return 1;
519        }
520        return lhs.compareTo(justAfterNull);
521      }
522      return lhs.compareTo(rhs);
523    }
524
525    @Override
526    public boolean equals(@Nullable Object obj) {
527      if (obj instanceof NullsBefore) {
528        NullsBefore other = (NullsBefore) obj;
529        return justAfterNull.equals(other.justAfterNull);
530      }
531      return false;
532    }
533
534    @Override
535    public int hashCode() {
536      return justAfterNull.hashCode();
537    }
538  }
539
540  public static final class NullsBeforeB extends NullsBefore {
541    public static final NullsBeforeB INSTANCE = new NullsBeforeB();
542
543    private NullsBeforeB() {
544      super("b");
545    }
546  }
547
548  public static final class NullsBeforeTwo extends NullsBefore {
549    public static final NullsBeforeTwo INSTANCE = new NullsBeforeTwo();
550
551    private NullsBeforeTwo() {
552      super("two"); // from TestStringSortedMapGenerator's sample keys
553    }
554  }
555
556  @J2ktIncompatible
557  @GwtIncompatible // reflection
558  public static Method getMethod(Class<?> clazz, String name) {
559    try {
560      return clazz.getMethod(name);
561    } catch (Exception e) {
562      throw new IllegalArgumentException(e);
563    }
564  }
565}