/*
    * 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;
     }
   }
 }