guava

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
import static junit.framework.Assert.fail;
24

25
import com.google.common.annotations.GwtCompatible;
26
import com.google.common.annotations.GwtIncompatible;
27
import com.google.common.annotations.J2ktIncompatible;
28
import com.google.errorprone.annotations.CanIgnoreReturnValue;
29
import java.io.Serializable;
30
import java.lang.reflect.Method;
31
import java.util.AbstractList;
32
import java.util.ArrayList;
33
import java.util.Arrays;
34
import java.util.Collection;
35
import java.util.Collections;
36
import java.util.Comparator;
37
import java.util.Iterator;
38
import java.util.LinkedHashSet;
39
import java.util.List;
40
import java.util.ListIterator;
41
import java.util.Map;
42
import java.util.Map.Entry;
43
import java.util.Set;
44
import org.checkerframework.checker.nullness.qual.Nullable;
45

46
@GwtCompatible(emulated = true)
47
@ElementTypesAreNonnullByDefault
48
public class Helpers {
49
  // Clone of Objects.equal
50
  static boolean equal(@Nullable Object a, @Nullable Object b) {
51
    return a == b || (a != null && a.equals(b));
52
  }
53

54
  // Clone of Lists.newArrayList
55
  public static <E extends @Nullable Object> List<E> copyToList(Iterable<? extends E> elements) {
56
    List<E> list = new ArrayList<>();
57
    addAll(list, elements);
58
    return list;
59
  }
60

61
  public static <E extends @Nullable Object> List<E> copyToList(E[] elements) {
62
    return copyToList(Arrays.asList(elements));
63
  }
64

65
  // Clone of Sets.newLinkedHashSet
66
  public static <E extends @Nullable Object> Set<E> copyToSet(Iterable<? extends E> elements) {
67
    Set<E> set = new LinkedHashSet<>();
68
    addAll(set, elements);
69
    return set;
70
  }
71

72
  public static <E extends @Nullable Object> Set<E> copyToSet(E[] elements) {
73
    return copyToSet(Arrays.asList(elements));
74
  }
75

76
  // Would use Maps.immutableEntry
77
  public static <K extends @Nullable Object, V extends @Nullable Object> Entry<K, V> mapEntry(
78
      K key, V value) {
79
    return Collections.singletonMap(key, value).entrySet().iterator().next();
80
  }
81

82
  private static boolean isEmpty(Iterable<?> iterable) {
83
    return iterable instanceof Collection
84
        ? ((Collection<?>) iterable).isEmpty()
85
        : !iterable.iterator().hasNext();
86
  }
87

88
  public static void assertEmpty(Iterable<?> iterable) {
89
    if (!isEmpty(iterable)) {
90
      fail("Not true that " + iterable + " is empty");
91
    }
92
  }
93

94
  public static void assertEmpty(Map<?, ?> map) {
95
    if (!map.isEmpty()) {
96
      fail("Not true that " + map + " is empty");
97
    }
98
  }
99

100
  public static void assertEqualInOrder(Iterable<?> expected, Iterable<?> actual) {
101
    Iterator<?> expectedIter = expected.iterator();
102
    Iterator<?> actualIter = actual.iterator();
103

104
    while (expectedIter.hasNext() && actualIter.hasNext()) {
105
      if (!equal(expectedIter.next(), actualIter.next())) {
106
        fail(
107
            "contents were not equal and in the same order: "
108
                + "expected = "
109
                + expected
110
                + ", actual = "
111
                + actual);
112
      }
113
    }
114

115
    if (expectedIter.hasNext() || actualIter.hasNext()) {
116
      // actual either had too few or too many elements
117
      fail(
118
          "contents were not equal and in the same order: "
119
              + "expected = "
120
              + expected
121
              + ", actual = "
122
              + actual);
123
    }
124
  }
125

126
  public static void assertContentsInOrder(Iterable<?> actual, Object... expected) {
127
    assertEqualInOrder(Arrays.asList(expected), actual);
128
  }
129

130
  public static void assertEqualIgnoringOrder(Iterable<?> expected, Iterable<?> actual) {
131
    List<?> exp = copyToList(expected);
132
    List<?> act = copyToList(actual);
133
    String actString = act.toString();
134

135
    // Of course we could take pains to give the complete description of the
136
    // problem on any failure.
137

138
    // Yeah it's n^2.
139
    for (Object object : exp) {
140
      if (!act.remove(object)) {
141
        fail(
142
            "did not contain expected element "
143
                + object
144
                + ", "
145
                + "expected = "
146
                + exp
147
                + ", actual = "
148
                + actString);
149
      }
150
    }
151
    assertTrue("unexpected elements: " + act, act.isEmpty());
152
  }
153

154
  public static void assertContentsAnyOrder(Iterable<?> actual, Object... expected) {
155
    assertEqualIgnoringOrder(Arrays.asList(expected), actual);
156
  }
157

158
  public static void assertContains(Iterable<?> actual, Object expected) {
159
    boolean contained = false;
160
    if (actual instanceof Collection) {
161
      contained = ((Collection<?>) actual).contains(expected);
162
    } else {
163
      for (Object o : actual) {
164
        if (equal(o, expected)) {
165
          contained = true;
166
          break;
167
        }
168
      }
169
    }
170

171
    if (!contained) {
172
      fail("Not true that " + actual + " contains " + expected);
173
    }
174
  }
175

176
  public static void assertContainsAllOf(Iterable<?> actual, Object... expected) {
177
    List<Object> expectedList = new ArrayList<>(Arrays.asList(expected));
178

179
    for (Object o : actual) {
180
      expectedList.remove(o);
181
    }
182

183
    if (!expectedList.isEmpty()) {
184
      fail("Not true that " + actual + " contains all of " + Arrays.asList(expected));
185
    }
186
  }
187

188
  @CanIgnoreReturnValue
189
  public static <E extends @Nullable Object> boolean addAll(
190
      Collection<E> addTo, Iterable<? extends E> elementsToAdd) {
191
    boolean modified = false;
192
    for (E e : elementsToAdd) {
193
      modified |= addTo.add(e);
194
    }
195
    return modified;
196
  }
197

198
  static <T extends @Nullable Object> Iterable<T> reverse(List<T> list) {
199
    return new Iterable<T>() {
200
      @Override
201
      public Iterator<T> iterator() {
202
        ListIterator<T> listIter = list.listIterator(list.size());
203
        return new Iterator<T>() {
204
          @Override
205
          public boolean hasNext() {
206
            return listIter.hasPrevious();
207
          }
208

209
          @Override
210
          public T next() {
211
            return listIter.previous();
212
          }
213

214
          @Override
215
          public void remove() {
216
            listIter.remove();
217
          }
218
        };
219
      }
220
    };
221
  }
222

223
  static <T extends @Nullable Object> Iterator<T> cycle(Iterable<T> iterable) {
224
    return new Iterator<T>() {
225
      Iterator<T> iterator = Collections.<T>emptySet().iterator();
226

227
      @Override
228
      public boolean hasNext() {
229
        return true;
230
      }
231

232
      @Override
233
      public T next() {
234
        if (!iterator.hasNext()) {
235
          iterator = iterable.iterator();
236
        }
237
        return iterator.next();
238
      }
239

240
      @Override
241
      public void remove() {
242
        throw new UnsupportedOperationException();
243
      }
244
    };
245
  }
246

247
  static <T extends @Nullable Object> T get(Iterator<T> iterator, int position) {
248
    for (int i = 0; i < position; i++) {
249
      iterator.next();
250
    }
251
    return iterator.next();
252
  }
253

254
  private static class EntryComparator<K extends @Nullable Object, V extends @Nullable Object>
255
      implements Comparator<Entry<K, V>> {
256
    final @Nullable Comparator<? super K> keyComparator;
257

258
    public EntryComparator(@Nullable Comparator<? super K> keyComparator) {
259
      this.keyComparator = keyComparator;
260
    }
261

262
    @Override
263
    @SuppressWarnings("unchecked") // no less safe than putting it in the map!
264
    public int compare(Entry<K, V> a, Entry<K, V> b) {
265
      return (keyComparator == null)
266
          ? ((Comparable) a.getKey()).compareTo(b.getKey())
267
          : keyComparator.compare(a.getKey(), b.getKey());
268
    }
269
  }
270

271
  public static <K extends @Nullable Object, V extends @Nullable Object>
272
      Comparator<Entry<K, V>> entryComparator(@Nullable Comparator<? super K> keyComparator) {
273
    return new EntryComparator<K, V>(keyComparator);
274
  }
275

276
  /**
277
   * Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
278
   * consistently between their order within {@code valuesInExpectedOrder} and the order implied by
279
   * the given {@code comparator}.
280
   *
281
   * @see #testComparator(Comparator, List)
282
   */
283
  public static <T extends @Nullable Object> void testComparator(
284
      Comparator<? super T> comparator, T... valuesInExpectedOrder) {
285
    testComparator(comparator, Arrays.asList(valuesInExpectedOrder));
286
  }
287

288
  /**
289
   * Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
290
   * consistently between their order within {@code valuesInExpectedOrder} and the order implied by
291
   * the given {@code comparator}.
292
   *
293
   * <p>In detail, this method asserts
294
   *
295
   * <ul>
296
   *   <li><i>reflexivity</i>: {@code comparator.compare(t, t) = 0} for all {@code t} in {@code
297
   *       valuesInExpectedOrder}; and
298
   *   <li><i>consistency</i>: {@code comparator.compare(ti, tj) < 0} and {@code
299
   *       comparator.compare(tj, ti) > 0} for {@code i < j}, where {@code ti =
300
   *       valuesInExpectedOrder.get(i)} and {@code tj = valuesInExpectedOrder.get(j)}.
301
   * </ul>
302
   */
303
  public static <T extends @Nullable Object> void testComparator(
304
      Comparator<? super T> comparator, List<T> valuesInExpectedOrder) {
305
    // This does an O(n^2) test of all pairs of values in both orders
306
    for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
307
      T t = valuesInExpectedOrder.get(i);
308

309
      for (int j = 0; j < i; j++) {
310
        T lesser = valuesInExpectedOrder.get(j);
311
        assertTrue(
312
            comparator + ".compare(" + lesser + ", " + t + ")", comparator.compare(lesser, t) < 0);
313
      }
314

315
      assertEquals(comparator + ".compare(" + t + ", " + t + ")", 0, comparator.compare(t, t));
316

317
      for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
318
        T greater = valuesInExpectedOrder.get(j);
319
        assertTrue(
320
            comparator + ".compare(" + greater + ", " + t + ")",
321
            comparator.compare(greater, t) > 0);
322
      }
323
    }
324
  }
325

326
  @SuppressWarnings({"SelfComparison", "SelfEquals"})
327
  public static <T extends Comparable<? super T>> void testCompareToAndEquals(
328
      List<T> valuesInExpectedOrder) {
329
    // This does an O(n^2) test of all pairs of values in both orders
330
    for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
331
      T t = valuesInExpectedOrder.get(i);
332

333
      for (int j = 0; j < i; j++) {
334
        T lesser = valuesInExpectedOrder.get(j);
335
        assertTrue(lesser + ".compareTo(" + t + ')', lesser.compareTo(t) < 0);
336
        assertFalse(lesser.equals(t));
337
      }
338

339
      assertEquals(t + ".compareTo(" + t + ')', 0, t.compareTo(t));
340
      assertTrue(t.equals(t));
341

342
      for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
343
        T greater = valuesInExpectedOrder.get(j);
344
        assertTrue(greater + ".compareTo(" + t + ')', greater.compareTo(t) > 0);
345
        assertFalse(greater.equals(t));
346
      }
347
    }
348
  }
349

350
  /**
351
   * Returns a collection that simulates concurrent modification by having its size method return
352
   * incorrect values. This is useful for testing methods that must treat the return value from
353
   * size() as a hint only.
354
   *
355
   * @param delta the difference between the true size of the collection and the values returned by
356
   *     the size method
357
   */
358
  public static <T extends @Nullable Object> Collection<T> misleadingSizeCollection(int delta) {
359
    // It would be nice to be able to return a real concurrent
360
    // collection like ConcurrentLinkedQueue, so that e.g. concurrent
361
    // iteration would work, but that would not be GWT-compatible.
362
    // We are not "just" inheriting from ArrayList here as this doesn't work for J2kt.
363
    return new AbstractList<T>() {
364
      ArrayList<T> data = new ArrayList<>();
365

366
      @Override
367
      public int size() {
368
        return Math.max(0, data.size() + delta);
369
      }
370

371
      @Override
372
      public T get(int index) {
373
        return data.get(index);
374
      }
375

376
      @Override
377
      public T set(int index, T element) {
378
        return data.set(index, element);
379
      }
380

381
      @Override
382
      public boolean add(T element) {
383
        return data.add(element);
384
      }
385

386
      @Override
387
      public void add(int index, T element) {
388
        data.add(index, element);
389
      }
390

391
      @Override
392
      public T remove(int index) {
393
        return data.remove(index);
394
      }
395

396
      @Override
397
      public @Nullable Object[] toArray() {
398
        return data.toArray();
399
      }
400
    };
401
  }
402

403
  /**
404
   * Returns a "nefarious" map entry with the specified key and value, meaning an entry that is
405
   * suitable for testing that map entries cannot be modified via a nefarious implementation of
406
   * equals. This is used for testing unmodifiable collections of map entries; for example, it
407
   * should not be possible to access the raw (modifiable) map entry via a nefarious equals method.
408
   */
409
  public static <K extends @Nullable Object, V extends @Nullable Object>
410
      Entry<K, V> nefariousMapEntry(K key, V value) {
411
    return new Entry<K, V>() {
412
      @Override
413
      public K getKey() {
414
        return key;
415
      }
416

417
      @Override
418
      public V getValue() {
419
        return value;
420
      }
421

422
      @Override
423
      public V setValue(V value) {
424
        throw new UnsupportedOperationException();
425
      }
426

427
      @SuppressWarnings("unchecked")
428
      @Override
429
      public boolean equals(@Nullable Object o) {
430
        if (o instanceof Entry) {
431
          Entry<K, V> e = (Entry<K, V>) o;
432
          e.setValue(value); // muhahaha!
433

434
          return equal(this.getKey(), e.getKey()) && equal(this.getValue(), e.getValue());
435
        }
436
        return false;
437
      }
438

439
      @Override
440
      public int hashCode() {
441
        K k = getKey();
442
        V v = getValue();
443
        return ((k == null) ? 0 : k.hashCode()) ^ ((v == null) ? 0 : v.hashCode());
444
      }
445

446
      @Override
447
      public String toString() {
448
        return getKey() + "=" + getValue();
449
      }
450
    };
451
  }
452

453
  static <E extends @Nullable Object> List<E> castOrCopyToList(Iterable<E> iterable) {
454
    if (iterable instanceof List) {
455
      return (List<E>) iterable;
456
    }
457
    List<E> list = new ArrayList<>();
458
    for (E e : iterable) {
459
      list.add(e);
460
    }
461
    return list;
462
  }
463

464
  @SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989
465
  public static <K extends Comparable, V extends @Nullable Object>
466
      Iterable<Entry<K, V>> orderEntriesByKey(List<Entry<K, V>> insertionOrder) {
467
    @SuppressWarnings("unchecked") // assume any Comparable is Comparable<Self>
468
    Comparator<? super K> keyComparator = (Comparator<? super K>) Comparable::compareTo;
469
    sort(insertionOrder, Helpers.entryComparator(keyComparator));
470
    return insertionOrder;
471
  }
472

473
  /**
474
   * Private replacement for {@link com.google.gwt.user.client.rpc.GwtTransient} to work around
475
   * build-system quirks.
476
   */
477
  private @interface GwtTransient {}
478

479
  /**
480
   * Compares strings in natural order except that null comes immediately before a given value. This
481
   * works better than Ordering.natural().nullsFirst() because, if null comes before all other
482
   * values, it lies outside the submap/submultiset ranges we test, and the variety of tests that
483
   * exercise null handling fail on those subcollections.
484
   */
485
  public abstract static class NullsBefore implements Comparator<@Nullable String>, Serializable {
486
    /*
487
     * We don't serialize this class in GWT, so we don't care about whether GWT will serialize this
488
     * field.
489
     */
490
    @GwtTransient private final String justAfterNull;
491

492
    protected NullsBefore(String justAfterNull) {
493
      if (justAfterNull == null) {
494
        throw new NullPointerException();
495
      }
496

497
      this.justAfterNull = justAfterNull;
498
    }
499

500
    @Override
501
    public int compare(@Nullable String lhs, @Nullable String rhs) {
502
      if (lhs == rhs) {
503
        return 0;
504
      }
505
      if (lhs == null) {
506
        // lhs (null) comes just before justAfterNull.
507
        // If rhs is b, lhs comes first.
508
        if (rhs.equals(justAfterNull)) {
509
          return -1;
510
        }
511
        return justAfterNull.compareTo(rhs);
512
      }
513
      if (rhs == null) {
514
        // rhs (null) comes just before justAfterNull.
515
        // If lhs is b, rhs comes first.
516
        if (lhs.equals(justAfterNull)) {
517
          return 1;
518
        }
519
        return lhs.compareTo(justAfterNull);
520
      }
521
      return lhs.compareTo(rhs);
522
    }
523

524
    @Override
525
    public boolean equals(@Nullable Object obj) {
526
      if (obj instanceof NullsBefore) {
527
        NullsBefore other = (NullsBefore) obj;
528
        return justAfterNull.equals(other.justAfterNull);
529
      }
530
      return false;
531
    }
532

533
    @Override
534
    public int hashCode() {
535
      return justAfterNull.hashCode();
536
    }
537
  }
538

539
  public static final class NullsBeforeB extends NullsBefore {
540
    public static final NullsBeforeB INSTANCE = new NullsBeforeB();
541

542
    private NullsBeforeB() {
543
      super("b");
544
    }
545
  }
546

547
  public static final class NullsBeforeTwo extends NullsBefore {
548
    public static final NullsBeforeTwo INSTANCE = new NullsBeforeTwo();
549

550
    private NullsBeforeTwo() {
551
      super("two"); // from TestStringSortedMapGenerator's sample keys
552
    }
553
  }
554

555
  @J2ktIncompatible
556
  @GwtIncompatible // reflection
557
  public static Method getMethod(Class<?> clazz, String name) {
558
    try {
559
      return clazz.getMethod(name);
560
    } catch (Exception e) {
561
      throw new IllegalArgumentException(e);
562
    }
563
  }
564
}
565