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}