* - fresh permits (for any remaining permits)
   *
   * How this works is best explained with an example:
   *
   * For a RateLimiter that produces 1 token per second, every second that goes by with the
   * RateLimiter being unused, we increase storedPermits by 1. Say we leave the RateLimiter unused
   * for 10 seconds (i.e., we expected a request at time X, but we are at time X + 10 seconds before

     * lists (accounting for the fact that they could have been removed from the map since being
     * added to the recency queue).
     */
    @GuardedBy("this")
    void drainRecencyQueue() {
      ReferenceEntry<K, V> e;
      while ((e = recencyQueue.poll()) != null) {
        // An entry may be in the recency queue despite it being removed from
        // the map . This can occur when the entry was concurrently read while a

   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
   */
  public static <K, V> ImmutableSortedMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
    // Hack around K not being a subtype of Comparable.
    // Unsafe, see ImmutableSortedSetFauxverideShim.
    @SuppressWarnings("unchecked")
    Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER;
    return copyOfInternal(map, naturalOrder);

    ListenableFuture<List<String>> compound = allAsList(future1, future2);
    // There was a bug where the event listener for the combined future would
    // result in the sub-futures being cancelled without being interrupted.
    ListenableFuture<List<String>> otherCompound = allAsList(future1, future2);

    assertTrue(compound.cancel(true));
    assertTrue(future1.isCancelled());

  //   is). If we wanted to be strict about it, we could store the unpark() time in the Waiter node
  //   and we could use that to make a decision about whether or not we timed out prior to being
  //   unparked.

  /**
   * {@inheritDoc}
   *
   * <p>The default {@link AbstractFuture} implementation throws {@code InterruptedException} if the

   *
   * TODO(cpovirk): So make it part of the open-source build, albeit package-private there?
   *
   * So we use uncheckedCastNullableTToT here. This is a weird usage of that method: The method is
   * documented as being for use with type parameters that have parametric nullness. But Converter's
   * type parameters do not. Still, we use it here so that we can suppress a warning at a smaller

      // We don't really care which values the exception message contains, but they should be
      // different from each other. If buildKeepingLast() collapsed duplicates, that might end up
      // not being true.
      Pattern pattern = Pattern.compile("Multiple entries with same key: four=(.*) and four=(.*)");
      assertThat(expected).hasMessageThat().matches(pattern);
      Matcher matcher = pattern.matcher(expected.getMessage());

    thread.join();
    // It's possible to race and suspend the thread just before the park call actually takes effect,
    // causing the thread to be suspended for 3.5 seconds, and then park itself for 2 seconds after
    // being resumed. To avoid a flake in this scenario, calculate how long that thread actually
    // waited and assert based on that time. Empirically, the race where the thread ends up waiting
    // for 5.5 seconds happens about 2% of the time.

   * this reason.
   *
   * <p><b>Java 8+ users:</b> many use cases for this method are better addressed by {@link
   * java.util.stream.Stream#map}. This method is not being deprecated, but we gently encourage you
   * to migrate to streams.
   */
  public static <F extends @Nullable Object, T extends @Nullable Object> List<T> transform(

    assertEquals(refreshKey + suffix, map.get(refreshKey));
  }

  public void testInvalidateDuringLoading() throws InterruptedException, ExecutionException {
    // computation starts; invalidate() is called on the key being computed, computation finishes
    final CountDownLatch computationStarted = new CountDownLatch(2);
    final CountDownLatch letGetFinishSignal = new CountDownLatch(1);