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}