1/*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.cache;
18
19import static com.google.common.cache.CacheBuilder.EMPTY_STATS;
20import static com.google.common.cache.LocalCacheTest.SMALL_MAX_SIZE;
21import static com.google.common.cache.TestingCacheLoaders.identityLoader;
22import static com.google.common.truth.Truth.assertThat;
23
24import com.google.common.cache.LocalCache.LocalLoadingCache;
25import com.google.common.cache.LocalCache.Segment;
26import com.google.common.collect.ImmutableMap;
27import com.google.common.collect.ImmutableSet;
28import com.google.common.testing.NullPointerTester;
29
30import junit.framework.TestCase;
31
32import java.lang.Thread.UncaughtExceptionHandler;
33import java.util.Map;
34import java.util.Set;
35import java.util.concurrent.ConcurrentMap;
36import java.util.concurrent.CountDownLatch;
37import java.util.concurrent.TimeUnit;
38import java.util.concurrent.atomic.AtomicReference;
39
40/**
41 * @author Charles Fry
42 */
43public class LocalLoadingCacheTest extends TestCase {
44
45  private static <K, V> LocalLoadingCache<K, V> makeCache(
46      CacheBuilder<K, V> builder, CacheLoader<? super K, V> loader) {
47    return new LocalLoadingCache<K, V>(builder, loader);
48  }
49
50  private CacheBuilder<Object, Object> createCacheBuilder() {
51    return CacheBuilder.newBuilder().recordStats();
52  }
53
54  // constructor tests
55
56  public void testComputingFunction() {
57    CacheLoader<Object, Object> loader = new CacheLoader<Object, Object>() {
58      @Override
59      public Object load(Object from) {
60        return new Object();
61      }
62    };
63    LocalLoadingCache<Object, Object> cache = makeCache(createCacheBuilder(), loader);
64    assertSame(loader, cache.localCache.defaultLoader);
65  }
66
67  // null parameters test
68
69  public void testNullParameters() throws Exception {
70    NullPointerTester tester = new NullPointerTester();
71    CacheLoader<Object, Object> loader = identityLoader();
72    tester.testAllPublicInstanceMethods(makeCache(createCacheBuilder(), loader));
73  }
74
75  // stats tests
76
77  public void testStats() {
78    CacheBuilder<Object, Object> builder = createCacheBuilder()
79        .concurrencyLevel(1)
80        .maximumSize(2);
81    LocalLoadingCache<Object, Object> cache = makeCache(builder, identityLoader());
82    assertEquals(EMPTY_STATS, cache.stats());
83
84    Object one = new Object();
85    cache.getUnchecked(one);
86    CacheStats stats = cache.stats();
87    assertEquals(1, stats.requestCount());
88    assertEquals(0, stats.hitCount());
89    assertEquals(0.0, stats.hitRate());
90    assertEquals(1, stats.missCount());
91    assertEquals(1.0, stats.missRate());
92    assertEquals(1, stats.loadCount());
93    long totalLoadTime = stats.totalLoadTime();
94    assertTrue(totalLoadTime >= 0);
95    assertTrue(stats.averageLoadPenalty() >= 0.0);
96    assertEquals(0, stats.evictionCount());
97
98    cache.getUnchecked(one);
99    stats = cache.stats();
100    assertEquals(2, stats.requestCount());
101    assertEquals(1, stats.hitCount());
102    assertEquals(1.0/2, stats.hitRate());
103    assertEquals(1, stats.missCount());
104    assertEquals(1.0/2, stats.missRate());
105    assertEquals(1, stats.loadCount());
106    assertEquals(0, stats.evictionCount());
107
108    Object two = new Object();
109    cache.getUnchecked(two);
110    stats = cache.stats();
111    assertEquals(3, stats.requestCount());
112    assertEquals(1, stats.hitCount());
113    assertEquals(1.0/3, stats.hitRate());
114    assertEquals(2, stats.missCount());
115    assertEquals(2.0/3, stats.missRate());
116    assertEquals(2, stats.loadCount());
117    assertTrue(stats.totalLoadTime() >= totalLoadTime);
118    totalLoadTime = stats.totalLoadTime();
119    assertTrue(stats.averageLoadPenalty() >= 0.0);
120    assertEquals(0, stats.evictionCount());
121
122    Object three = new Object();
123    cache.getUnchecked(three);
124    stats = cache.stats();
125    assertEquals(4, stats.requestCount());
126    assertEquals(1, stats.hitCount());
127    assertEquals(1.0/4, stats.hitRate());
128    assertEquals(3, stats.missCount());
129    assertEquals(3.0/4, stats.missRate());
130    assertEquals(3, stats.loadCount());
131    assertTrue(stats.totalLoadTime() >= totalLoadTime);
132    totalLoadTime = stats.totalLoadTime();
133    assertTrue(stats.averageLoadPenalty() >= 0.0);
134    assertEquals(1, stats.evictionCount());
135  }
136
137  public void testStatsNoops() {
138    CacheBuilder<Object, Object> builder = createCacheBuilder()
139        .concurrencyLevel(1);
140    LocalLoadingCache<Object, Object> cache = makeCache(builder, identityLoader());
141    ConcurrentMap<Object, Object> map = cache.localCache; // modifiable map view
142    assertEquals(EMPTY_STATS, cache.stats());
143
144    Object one = new Object();
145    assertNull(map.put(one, one));
146    assertSame(one, map.get(one));
147    assertTrue(map.containsKey(one));
148    assertTrue(map.containsValue(one));
149    Object two = new Object();
150    assertSame(one, map.replace(one, two));
151    assertTrue(map.containsKey(one));
152    assertFalse(map.containsValue(one));
153    Object three = new Object();
154    assertTrue(map.replace(one, two, three));
155    assertTrue(map.remove(one, three));
156    assertFalse(map.containsKey(one));
157    assertFalse(map.containsValue(one));
158    assertNull(map.putIfAbsent(two, three));
159    assertSame(three, map.remove(two));
160    assertNull(map.put(three, one));
161    assertNull(map.put(one, two));
162
163    assertThat(map).hasKey(three).withValue(one);
164    assertThat(map).hasKey(one).withValue(two);
165
166    //TODO(user): Confirm with fry@ that this is a reasonable substitute.
167    //Set<Map.Entry<Object, Object>> entries = map.entrySet();
168    //assertThat(entries).has().exactly(
169    //    Maps.immutableEntry(three, one), Maps.immutableEntry(one, two));
170    //Set<Object> keys = map.keySet();
171    //assertThat(keys).has().exactly(one, three);
172    //Collection<Object> values = map.values();
173    //assertThat(values).has().exactly(one, two);
174
175    map.clear();
176
177    assertEquals(EMPTY_STATS, cache.stats());
178  }
179
180  public void testNoStats() {
181    CacheBuilder<Object, Object> builder = CacheBuilder.newBuilder()
182        .concurrencyLevel(1)
183        .maximumSize(2);
184    LocalLoadingCache<Object, Object> cache = makeCache(builder, identityLoader());
185    assertEquals(EMPTY_STATS, cache.stats());
186
187    Object one = new Object();
188    cache.getUnchecked(one);
189    assertEquals(EMPTY_STATS, cache.stats());
190
191    cache.getUnchecked(one);
192    assertEquals(EMPTY_STATS, cache.stats());
193
194    Object two = new Object();
195    cache.getUnchecked(two);
196    assertEquals(EMPTY_STATS, cache.stats());
197
198    Object three = new Object();
199    cache.getUnchecked(three);
200    assertEquals(EMPTY_STATS, cache.stats());
201  }
202
203  public void testRecordStats() {
204    CacheBuilder<Object, Object> builder = createCacheBuilder()
205        .recordStats()
206        .concurrencyLevel(1)
207        .maximumSize(2);
208    LocalLoadingCache<Object, Object> cache = makeCache(builder, identityLoader());
209    assertEquals(0, cache.stats().hitCount());
210    assertEquals(0, cache.stats().missCount());
211
212    Object one = new Object();
213    cache.getUnchecked(one);
214    assertEquals(0, cache.stats().hitCount());
215    assertEquals(1, cache.stats().missCount());
216
217    cache.getUnchecked(one);
218    assertEquals(1, cache.stats().hitCount());
219    assertEquals(1, cache.stats().missCount());
220
221    Object two = new Object();
222    cache.getUnchecked(two);
223    assertEquals(1, cache.stats().hitCount());
224    assertEquals(2, cache.stats().missCount());
225
226    Object three = new Object();
227    cache.getUnchecked(three);
228    assertEquals(1, cache.stats().hitCount());
229    assertEquals(3, cache.stats().missCount());
230  }
231
232  // asMap tests
233
234  public void testAsMap() {
235    CacheBuilder<Object, Object> builder = createCacheBuilder();
236    LocalLoadingCache<Object, Object> cache = makeCache(builder, identityLoader());
237    assertEquals(EMPTY_STATS, cache.stats());
238
239    Object one = new Object();
240    Object two = new Object();
241    Object three = new Object();
242
243    ConcurrentMap<Object, Object> map = cache.asMap();
244    assertNull(map.put(one, two));
245    assertSame(two, map.get(one));
246    map.putAll(ImmutableMap.of(two, three));
247    assertSame(three, map.get(two));
248    assertSame(two, map.putIfAbsent(one, three));
249    assertSame(two, map.get(one));
250    assertNull(map.putIfAbsent(three, one));
251    assertSame(one, map.get(three));
252    assertSame(two, map.replace(one, three));
253    assertSame(three, map.get(one));
254    assertFalse(map.replace(one, two, three));
255    assertSame(three, map.get(one));
256    assertTrue(map.replace(one, three, two));
257    assertSame(two, map.get(one));
258    assertEquals(3, map.size());
259
260    map.clear();
261    assertTrue(map.isEmpty());
262    assertEquals(0, map.size());
263
264    cache.getUnchecked(one);
265    assertEquals(1, map.size());
266    assertSame(one, map.get(one));
267    assertTrue(map.containsKey(one));
268    assertTrue(map.containsValue(one));
269    assertSame(one, map.remove(one));
270    assertEquals(0, map.size());
271
272    cache.getUnchecked(one);
273    assertEquals(1, map.size());
274    assertFalse(map.remove(one, two));
275    assertTrue(map.remove(one, one));
276    assertEquals(0, map.size());
277
278    cache.getUnchecked(one);
279    Map<Object, Object> newMap = ImmutableMap.of(one, one);
280    assertEquals(newMap, map);
281    assertEquals(newMap.entrySet(), map.entrySet());
282    assertEquals(newMap.keySet(), map.keySet());
283    Set<Object> expectedValues = ImmutableSet.of(one);
284    Set<Object> actualValues = ImmutableSet.copyOf(map.values());
285    assertEquals(expectedValues, actualValues);
286  }
287
288  /**
289   * Lookups on the map view shouldn't impact the recency queue.
290   */
291  public void testAsMapRecency() {
292    CacheBuilder<Object, Object> builder = createCacheBuilder()
293        .concurrencyLevel(1)
294        .maximumSize(SMALL_MAX_SIZE);
295    LocalLoadingCache<Object, Object> cache = makeCache(builder, identityLoader());
296    Segment<Object, Object> segment = cache.localCache.segments[0];
297    ConcurrentMap<Object, Object> map = cache.asMap();
298
299    Object one = new Object();
300    assertSame(one, cache.getUnchecked(one));
301    assertTrue(segment.recencyQueue.isEmpty());
302    assertSame(one, map.get(one));
303    assertSame(one, segment.recencyQueue.peek().getKey());
304    assertSame(one, cache.getUnchecked(one));
305    assertFalse(segment.recencyQueue.isEmpty());
306  }
307
308  public void testRecursiveComputation() throws InterruptedException {
309    final AtomicReference<LoadingCache<Integer, String>> cacheRef =
310        new AtomicReference<LoadingCache<Integer, String>>();
311    CacheLoader<Integer, String> recursiveLoader = new CacheLoader<Integer, String>() {
312      @Override
313      public String load(Integer key) {
314        if (key > 0) {
315          return key + ", " + cacheRef.get().getUnchecked(key - 1);
316        } else {
317          return "0";
318        }
319      }
320    };
321
322    LoadingCache<Integer, String> recursiveCache = new CacheBuilder<Integer, String>()
323        .weakKeys()
324        .weakValues()
325        .build(recursiveLoader);
326    cacheRef.set(recursiveCache);
327    assertEquals("3, 2, 1, 0", recursiveCache.getUnchecked(3));
328
329    recursiveLoader = new CacheLoader<Integer, String>() {
330      @Override
331      public String load(Integer key) {
332        return cacheRef.get().getUnchecked(key);
333      }
334    };
335
336    recursiveCache = new CacheBuilder<Integer, String>()
337        .weakKeys()
338        .weakValues()
339        .build(recursiveLoader);
340    cacheRef.set(recursiveCache);
341
342    // tells the test when the compution has completed
343    final CountDownLatch doneSignal = new CountDownLatch(1);
344
345    Thread thread = new Thread() {
346      @Override
347      public void run() {
348        try {
349          cacheRef.get().getUnchecked(3);
350        } finally {
351          doneSignal.countDown();
352        }
353      }
354    };
355    thread.setUncaughtExceptionHandler(new UncaughtExceptionHandler() {
356      @Override
357      public void uncaughtException(Thread t, Throwable e) {}
358    });
359    thread.start();
360
361    boolean done = doneSignal.await(1, TimeUnit.SECONDS);
362    if (!done) {
363      StringBuilder builder = new StringBuilder();
364      for (StackTraceElement trace : thread.getStackTrace()) {
365        builder.append("\tat ").append(trace).append('\n');
366      }
367      fail(builder.toString());
368    }
369  }
370}
371