common/cache/CacheBuilderTest.java

/*
 * Copyright (C) 2009 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.cache;

import static com.google.common.cache.TestingCacheLoaders.constantLoader;
import static com.google.common.cache.TestingCacheLoaders.identityLoader;
import static com.google.common.cache.TestingRemovalListeners.countingRemovalListener;
import static com.google.common.cache.TestingRemovalListeners.nullRemovalListener;
import static com.google.common.cache.TestingRemovalListeners.queuingRemovalListener;
import static com.google.common.cache.TestingWeighers.constantWeigher;
import static java.util.concurrent.TimeUnit.NANOSECONDS;
import static java.util.concurrent.TimeUnit.SECONDS;

import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.base.Ticker;
import com.google.common.cache.TestingRemovalListeners.CountingRemovalListener;
import com.google.common.cache.TestingRemovalListeners.QueuingRemovalListener;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.common.testing.NullPointerTester;

import junit.framework.TestCase;

import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Unit tests for CacheBuilder.
 */
@GwtCompatible(emulated = true)
public class CacheBuilderTest extends TestCase {

  public void testNewBuilder() {
    CacheLoader<Object, Integer> loader = constantLoader(1);

    LoadingCache<String, Integer> cache = CacheBuilder.newBuilder()
        .removalListener(countingRemovalListener())
        .build(loader);

    assertEquals(Integer.valueOf(1), cache.getUnchecked("one"));
    assertEquals(1, cache.size());
  }

  public void testInitialCapacity_negative() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>();
    try {
      builder.initialCapacity(-1);
      fail();
    } catch (IllegalArgumentException expected) {}
  }

  public void testInitialCapacity_setTwice() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>().initialCapacity(16);
    try {
      // even to the same value is not allowed
      builder.initialCapacity(16);
      fail();
    } catch (IllegalStateException expected) {}
  }

  @GwtIncompatible("CacheTesting")
  public void testInitialCapacity_small() {
    LoadingCache<?, ?> cache = CacheBuilder.newBuilder()
        .initialCapacity(5)
        .build(identityLoader());
    LocalCache<?, ?> map = CacheTesting.toLocalCache(cache);

    assertEquals(4, map.segments.length);
    assertEquals(2, map.segments[0].table.length());
    assertEquals(2, map.segments[1].table.length());
    assertEquals(2, map.segments[2].table.length());
    assertEquals(2, map.segments[3].table.length());
  }

  @GwtIncompatible("CacheTesting")
  public void testInitialCapacity_smallest() {
    LoadingCache<?, ?> cache = CacheBuilder.newBuilder()
        .initialCapacity(0)
        .build(identityLoader());
    LocalCache<?, ?> map = CacheTesting.toLocalCache(cache);

    assertEquals(4, map.segments.length);
    // 1 is as low as it goes, not 0. it feels dirty to know this/test this.
    assertEquals(1, map.segments[0].table.length());
    assertEquals(1, map.segments[1].table.length());
    assertEquals(1, map.segments[2].table.length());
    assertEquals(1, map.segments[3].table.length());
  }

  public void testInitialCapacity_large() {
    CacheBuilder.newBuilder().initialCapacity(Integer.MAX_VALUE);
    // that the builder didn't blow up is enough;
    // don't actually create this monster!
  }

  public void testConcurrencyLevel_zero() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>();
    try {
      builder.concurrencyLevel(0);
      fail();
    } catch (IllegalArgumentException expected) {}
  }

  public void testConcurrencyLevel_setTwice() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>().concurrencyLevel(16);
    try {
      // even to the same value is not allowed
      builder.concurrencyLevel(16);
      fail();
    } catch (IllegalStateException expected) {}
  }

  @GwtIncompatible("CacheTesting")
  public void testConcurrencyLevel_small() {
    LoadingCache<?, ?> cache = CacheBuilder.newBuilder()
        .concurrencyLevel(1)
        .build(identityLoader());
    LocalCache<?, ?> map = CacheTesting.toLocalCache(cache);
    assertEquals(1, map.segments.length);
  }

  public void testConcurrencyLevel_large() {
    CacheBuilder.newBuilder().concurrencyLevel(Integer.MAX_VALUE);
    // don't actually build this beast
  }

  public void testMaximumSize_negative() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>();
    try {
      builder.maximumSize(-1);
      fail();
    } catch (IllegalArgumentException expected) {}
  }

  public void testMaximumSize_setTwice() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>().maximumSize(16);
    try {
      // even to the same value is not allowed
      builder.maximumSize(16);
      fail();
    } catch (IllegalStateException expected) {}
  }

  @GwtIncompatible("maximumWeight")
  public void testMaximumSize_andWeight() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>().maximumSize(16);
    try {
      builder.maximumWeight(16);
      fail();
    } catch (IllegalStateException expected) {}
  }

  @GwtIncompatible("maximumWeight")
  public void testMaximumWeight_negative() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>();
    try {
      builder.maximumWeight(-1);
      fail();
    } catch (IllegalArgumentException expected) {}
  }

  @GwtIncompatible("maximumWeight")
  public void testMaximumWeight_setTwice() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>().maximumWeight(16);
    try {
      // even to the same value is not allowed
      builder.maximumWeight(16);
      fail();
    } catch (IllegalStateException expected) {}
    try {
      builder.maximumSize(16);
      fail();
    } catch (IllegalStateException expected) {}
  }

  @GwtIncompatible("maximumWeight")
  public void testMaximumWeight_withoutWeigher() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>()
        .maximumWeight(1);
    try {
      builder.build(identityLoader());
      fail();
    } catch (IllegalStateException expected) {}
  }

  @GwtIncompatible("weigher")
  public void testWeigher_withoutMaximumWeight() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>()
        .weigher(constantWeigher(42));
    try {
      builder.build(identityLoader());
      fail();
    } catch (IllegalStateException expected) {}
  }

  @GwtIncompatible("weigher")
  public void testWeigher_withMaximumSize() {
    try {
      CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>()
          .weigher(constantWeigher(42))
          .maximumSize(1);
      fail();
    } catch (IllegalStateException expected) {}
    try {
      CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>()
          .maximumSize(1)
          .weigher(constantWeigher(42));
      fail();
    } catch (IllegalStateException expected) {}
  }

  @GwtIncompatible("weakKeys")
  public void testKeyStrengthSetTwice() {
    CacheBuilder<Object, Object> builder1 = new CacheBuilder<Object, Object>().weakKeys();
    try {
      builder1.weakKeys();
      fail();
    } catch (IllegalStateException expected) {}
  }

  @GwtIncompatible("weakValues")
  public void testValueStrengthSetTwice() {
    CacheBuilder<Object, Object> builder1 = new CacheBuilder<Object, Object>().weakValues();
    try {
      builder1.weakValues();
      fail();
    } catch (IllegalStateException expected) {}
    try {
      builder1.softValues();
      fail();
    } catch (IllegalStateException expected) {}

    CacheBuilder<Object, Object> builder2 = new CacheBuilder<Object, Object>().softValues();
    try {
      builder2.softValues();
      fail();
    } catch (IllegalStateException expected) {}
    try {
      builder2.weakValues();
      fail();
    } catch (IllegalStateException expected) {}
  }

  public void testTimeToLive_negative() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>();
    try {
      builder.expireAfterWrite(-1, SECONDS);
      fail();
    } catch (IllegalArgumentException expected) {}
  }

  public void testTimeToLive_small() {
    CacheBuilder.newBuilder()
        .expireAfterWrite(1, NANOSECONDS)
        .build(identityLoader());
    // well, it didn't blow up.
  }

  public void testTimeToLive_setTwice() {
    CacheBuilder<Object, Object> builder =
        new CacheBuilder<Object, Object>().expireAfterWrite(3600, SECONDS);
    try {
      // even to the same value is not allowed
      builder.expireAfterWrite(3600, SECONDS);
      fail();
    } catch (IllegalStateException expected) {}
  }

  public void testTimeToIdle_negative() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>();
    try {
      builder.expireAfterAccess(-1, SECONDS);
      fail();
    } catch (IllegalArgumentException expected) {}
  }

  public void testTimeToIdle_small() {
    CacheBuilder.newBuilder()
        .expireAfterAccess(1, NANOSECONDS)
        .build(identityLoader());
    // well, it didn't blow up.
  }

  public void testTimeToIdle_setTwice() {
    CacheBuilder<Object, Object> builder =
        new CacheBuilder<Object, Object>().expireAfterAccess(3600, SECONDS);
    try {
      // even to the same value is not allowed
      builder.expireAfterAccess(3600, SECONDS);
      fail();
    } catch (IllegalStateException expected) {}
  }

  public void testTimeToIdleAndToLive() {
    CacheBuilder.newBuilder()
        .expireAfterWrite(1, NANOSECONDS)
        .expireAfterAccess(1, NANOSECONDS)
        .build(identityLoader());
    // well, it didn't blow up.
  }

  @GwtIncompatible("refreshAfterWrite")
  public void testRefresh_zero() {
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>();
    try {
      builder.refreshAfterWrite(0, SECONDS);
      fail();
    } catch (IllegalArgumentException expected) {}
  }

  @GwtIncompatible("refreshAfterWrite")
  public void testRefresh_setTwice() {
    CacheBuilder<Object, Object> builder =
        new CacheBuilder<Object, Object>().refreshAfterWrite(3600, SECONDS);
    try {
      // even to the same value is not allowed
      builder.refreshAfterWrite(3600, SECONDS);
      fail();
    } catch (IllegalStateException expected) {}
  }

  public void testTicker_setTwice() {
    Ticker testTicker = Ticker.systemTicker();
    CacheBuilder<Object, Object> builder =
        new CacheBuilder<Object, Object>().ticker(testTicker);
    try {
      // even to the same instance is not allowed
      builder.ticker(testTicker);
      fail();
    } catch (IllegalStateException expected) {}
  }

  public void testRemovalListener_setTwice() {
    RemovalListener<Object, Object> testListener = nullRemovalListener();
    CacheBuilder<Object, Object> builder =
        new CacheBuilder<Object, Object>().removalListener(testListener);
    try {
      // even to the same instance is not allowed
      builder = builder.removalListener(testListener);
      fail();
    } catch (IllegalStateException expected) {}
  }

  @GwtIncompatible("CacheTesting")
  public void testNullCache() {
    CountingRemovalListener<Object, Object> listener = countingRemovalListener();
    LoadingCache<Object, Object> nullCache = new CacheBuilder<Object, Object>()
        .maximumSize(0)
        .removalListener(listener)
        .build(identityLoader());
    assertEquals(0, nullCache.size());
    Object key = new Object();
    assertSame(key, nullCache.getUnchecked(key));
    assertEquals(1, listener.getCount());
    assertEquals(0, nullCache.size());
    CacheTesting.checkEmpty(nullCache.asMap());
  }

  @GwtIncompatible("QueuingRemovalListener")

  public void testRemovalNotification_clear() throws InterruptedException {
    // If a clear() happens while a computation is pending, we should not get a removal
    // notification.

    final AtomicBoolean shouldWait = new AtomicBoolean(false);
    final CountDownLatch computingLatch = new CountDownLatch(1);
    CacheLoader<String, String> computingFunction = new CacheLoader<String, String>() {
      @Override public String load(String key) throws InterruptedException {
        if (shouldWait.get()) {
          computingLatch.await();
        }
        return key;
      }
    };
    QueuingRemovalListener<String, String> listener = queuingRemovalListener();

    final LoadingCache<String, String> cache = CacheBuilder.newBuilder()
        .concurrencyLevel(1)
        .removalListener(listener)
        .build(computingFunction);

    // seed the map, so its segment's count > 0
    cache.getUnchecked("a");
    shouldWait.set(true);

    final CountDownLatch computationStarted = new CountDownLatch(1);
    final CountDownLatch computationComplete = new CountDownLatch(1);
    new Thread(new Runnable() {
      @Override public void run() {
        computationStarted.countDown();
        cache.getUnchecked("b");
        computationComplete.countDown();
      }
    }).start();

    // wait for the computingEntry to be created
    computationStarted.await();
    cache.invalidateAll();
    // let the computation proceed
    computingLatch.countDown();
    // don't check cache.size() until we know the get("b") call is complete
    computationComplete.await();

    // At this point, the listener should be holding the seed value (a -> a), and the map should
    // contain the computed value (b -> b), since the clear() happened before the computation
    // completed.
    assertEquals(1, listener.size());
    RemovalNotification<String, String> notification = listener.remove();
    assertEquals("a", notification.getKey());
    assertEquals("a", notification.getValue());
    assertEquals(1, cache.size());
    assertEquals("b", cache.getUnchecked("b"));
  }

  // "Basher tests", where we throw a bunch of stuff at a LoadingCache and check basic invariants.

  /**
   * This is a less carefully-controlled version of {@link #testRemovalNotification_clear} - this is
   * a black-box test that tries to create lots of different thread-interleavings, and asserts that
   * each computation is affected by a call to {@code clear()} (and therefore gets passed to the
   * removal listener), or else is not affected by the {@code clear()} (and therefore exists in the
   * cache afterward).
   */
  @GwtIncompatible("QueuingRemovalListener")

  public void testRemovalNotification_clear_basher() throws InterruptedException {
    // If a clear() happens close to the end of computation, one of two things should happen:
    // - computation ends first: the removal listener is called, and the cache does not contain the
    //   key/value pair
    // - clear() happens first: the removal listener is not called, and the cache contains the pair
    AtomicBoolean computationShouldWait = new AtomicBoolean();
    CountDownLatch computationLatch = new CountDownLatch(1);
    QueuingRemovalListener<String, String> listener = queuingRemovalListener();
    final LoadingCache <String, String> cache = CacheBuilder.newBuilder()
        .removalListener(listener)
        .concurrencyLevel(20)
        .build(
            new DelayingIdentityLoader<String>(computationShouldWait, computationLatch));

    int nThreads = 100;
    int nTasks = 1000;
    int nSeededEntries = 100;
    Set<String> expectedKeys = Sets.newHashSetWithExpectedSize(nTasks + nSeededEntries);
    // seed the map, so its segments have a count>0; otherwise, clear() won't visit the in-progress
    // entries
    for (int i = 0; i < nSeededEntries; i++) {
      String s = "b" + i;
      cache.getUnchecked(s);
      expectedKeys.add(s);
    }
    computationShouldWait.set(true);

    final AtomicInteger computedCount = new AtomicInteger();
    ExecutorService threadPool = Executors.newFixedThreadPool(nThreads);
    final CountDownLatch tasksFinished = new CountDownLatch(nTasks);
    for (int i = 0; i < nTasks; i++) {
      final String s = "a" + i;
      threadPool.submit(new Runnable() {
        @Override public void run() {
          cache.getUnchecked(s);
          computedCount.incrementAndGet();
          tasksFinished.countDown();
        }
      });
      expectedKeys.add(s);
    }

    computationLatch.countDown();
    // let some computations complete
    while (computedCount.get() < nThreads) {
      Thread.yield();
    }
    cache.invalidateAll();
    tasksFinished.await();

    // Check all of the removal notifications we received: they should have had correctly-associated
    // keys and values. (An earlier bug saw removal notifications for in-progress computations,
    // which had real keys with null values.)
    Map<String, String> removalNotifications = Maps.newHashMap();
    for (RemovalNotification<String, String> notification : listener) {
      removalNotifications.put(notification.getKey(), notification.getValue());
      assertEquals("Unexpected key/value pair passed to removalListener",
          notification.getKey(), notification.getValue());
    }

    // All of the seed values should have been visible, so we should have gotten removal
    // notifications for all of them.
    for (int i = 0; i < nSeededEntries; i++) {
      assertEquals("b" + i, removalNotifications.get("b" + i));
    }

    // Each of the values added to the map should either still be there, or have seen a removal
    // notification.
    assertEquals(expectedKeys, Sets.union(cache.asMap().keySet(), removalNotifications.keySet()));
    assertTrue(Sets.intersection(cache.asMap().keySet(), removalNotifications.keySet()).isEmpty());
  }

  /**
   * Calls get() repeatedly from many different threads, and tests that all of the removed entries
   * (removed because of size limits or expiration) trigger appropriate removal notifications.
   */
  @GwtIncompatible("QueuingRemovalListener")

  public void testRemovalNotification_get_basher() throws InterruptedException {
    int nTasks = 1000;
    int nThreads = 100;
    final int getsPerTask = 1000;
    final int nUniqueKeys = 10000;
    final Random random = new Random(); // Randoms.insecureRandom();

    QueuingRemovalListener<String, String> removalListener = queuingRemovalListener();
    final AtomicInteger computeCount = new AtomicInteger();
    final AtomicInteger exceptionCount = new AtomicInteger();
    final AtomicInteger computeNullCount = new AtomicInteger();
    CacheLoader<String, String> countingIdentityLoader =
        new CacheLoader<String, String>() {
          @Override public String load(String key) throws InterruptedException {
            int behavior = random.nextInt(4);
            if (behavior == 0) { // throw an exception
              exceptionCount.incrementAndGet();
              throw new RuntimeException("fake exception for test");
            } else if (behavior == 1) { // return null
              computeNullCount.incrementAndGet();
              return null;
            } else if (behavior == 2) { // slight delay before returning
              Thread.sleep(5);
              computeCount.incrementAndGet();
              return key;
            } else {
              computeCount.incrementAndGet();
              return key;
            }
          }
        };
    final LoadingCache<String, String> cache = CacheBuilder.newBuilder()
        .recordStats()
        .concurrencyLevel(2)
        .expireAfterWrite(100, TimeUnit.MILLISECONDS)
        .removalListener(removalListener)
        .maximumSize(5000)
        .build(countingIdentityLoader);

    ExecutorService threadPool = Executors.newFixedThreadPool(nThreads);
    for (int i = 0; i < nTasks; i++) {
      threadPool.submit(new Runnable() {
        @Override public void run() {
          for (int j = 0; j < getsPerTask; j++) {
            try {
              cache.getUnchecked("key" + random.nextInt(nUniqueKeys));
            } catch (RuntimeException e) {
            }
          }
        }
      });
    }

    threadPool.shutdown();
    threadPool.awaitTermination(300, TimeUnit.SECONDS);

    // Since we're not doing any more cache operations, and the cache only expires/evicts when doing
    // other operations, the cache and the removal queue won't change from this point on.

    // Verify that each received removal notification was valid
    for (RemovalNotification<String, String> notification : removalListener) {
      assertEquals("Invalid removal notification", notification.getKey(), notification.getValue());
    }

    CacheStats stats = cache.stats();
    assertEquals(removalListener.size(), stats.evictionCount());
    assertEquals(computeCount.get(), stats.loadSuccessCount());
    assertEquals(exceptionCount.get() + computeNullCount.get(), stats.loadExceptionCount());
    // each computed value is still in the cache, or was passed to the removal listener
    assertEquals(computeCount.get(), cache.size() + removalListener.size());
  }

  @GwtIncompatible("NullPointerTester")
  public void testNullParameters() throws Exception {
    NullPointerTester tester = new NullPointerTester();
    CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>();
    tester.testAllPublicInstanceMethods(builder);
  }

  @GwtIncompatible("CacheTesting")
  public void testSizingDefaults() {
    LoadingCache<?, ?> cache = CacheBuilder.newBuilder().build(identityLoader());
    LocalCache<?, ?> map = CacheTesting.toLocalCache(cache);
    assertEquals(4, map.segments.length); // concurrency level
    assertEquals(4, map.segments[0].table.length()); // capacity / conc level
  }

  @GwtIncompatible("CountDownLatch")
  static final class DelayingIdentityLoader<T> extends CacheLoader<T, T> {
    private final AtomicBoolean shouldWait;
    private final CountDownLatch delayLatch;

    DelayingIdentityLoader(AtomicBoolean shouldWait, CountDownLatch delayLatch) {
      this.shouldWait = shouldWait;
      this.delayLatch = delayLatch;
    }

    @Override public T load(T key) throws InterruptedException {
      if (shouldWait.get()) {
        delayLatch.await();
      }
      return key;
    }
  }
}