1/*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15package com.google.common.cache;
16
17import static com.google.common.cache.CacheTesting.checkEmpty;
18import static com.google.common.cache.CacheTesting.checkValidState;
19import static com.google.common.cache.TestingCacheLoaders.identityLoader;
20import static java.util.concurrent.TimeUnit.SECONDS;
21import static org.truth0.Truth.ASSERT;
22
23import com.google.common.base.Function;
24import com.google.common.cache.CacheBuilderFactory.DurationSpec;
25import com.google.common.cache.LocalCache.Strength;
26import com.google.common.collect.ImmutableMap;
27import com.google.common.collect.ImmutableSet;
28import com.google.common.collect.Iterables;
29import com.google.common.collect.Iterators;
30import com.google.common.collect.Lists;
31import com.google.common.collect.Maps;
32import com.google.common.testing.EqualsTester;
33
34import junit.framework.TestCase;
35
36import junit.framework.TestCase;
37
38import java.util.Collection;
39import java.util.List;
40import java.util.Map;
41import java.util.Map.Entry;
42import java.util.Set;
43
44/**
45 * {@link LoadingCache} tests that deal with caches that actually contain some key-value mappings.
46 *
47 * @author mike nonemacher
48 */
49
50public class PopulatedCachesTest extends TestCase {
51  // we use integers as keys; make sure the range covers some values that ARE cached by
52  // Integer.valueOf(int), and some that are not cached. (127 is the highest cached value.)
53  static final int WARMUP_MIN = 120;
54  static final int WARMUP_MAX = 135;
55  static final int WARMUP_SIZE = WARMUP_MAX - WARMUP_MIN;
56
57  public void testSize_populated() {
58    for (LoadingCache<Object, Object> cache : caches()) {
59      // don't let the entries get GCed
60      List<Entry<Object, Object>> warmed = warmUp(cache);
61      assertEquals(WARMUP_SIZE, cache.size());
62      assertMapSize(cache.asMap(), WARMUP_SIZE);
63      checkValidState(cache);
64    }
65  }
66
67  public void testContainsKey_found() {
68    for (LoadingCache<Object, Object> cache : caches()) {
69      // don't let the entries get GCed
70      List<Entry<Object, Object>> warmed = warmUp(cache);
71      for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
72        Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN);
73        assertTrue(cache.asMap().containsKey(entry.getKey()));
74        assertTrue(cache.asMap().containsValue(entry.getValue()));
75        // this getUnchecked() call shouldn't be a cache miss; verified below
76        assertEquals(entry.getValue(), cache.getUnchecked(entry.getKey()));
77      }
78      assertEquals(WARMUP_SIZE, cache.stats().missCount());
79      checkValidState(cache);
80    }
81  }
82
83  public void testPut_populated() {
84    for (LoadingCache<Object, Object> cache : caches()) {
85      // don't let the entries get GCed
86      List<Entry<Object, Object>> warmed = warmUp(cache);
87      for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
88        Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN);
89        Object newValue = new Object();
90        assertSame(entry.getValue(), cache.asMap().put(entry.getKey(), newValue));
91        // don't let the new entry get GCed
92        warmed.add(entryOf(entry.getKey(), newValue));
93        Object newKey = new Object();
94        assertNull(cache.asMap().put(newKey, entry.getValue()));
95        // this getUnchecked() call shouldn't be a cache miss; verified below
96        assertEquals(newValue, cache.getUnchecked(entry.getKey()));
97        assertEquals(entry.getValue(), cache.getUnchecked(newKey));
98        // don't let the new entry get GCed
99        warmed.add(entryOf(newKey, entry.getValue()));
100      }
101      assertEquals(WARMUP_SIZE, cache.stats().missCount());
102      checkValidState(cache);
103    }
104  }
105
106  public void testPutIfAbsent_populated() {
107    for (LoadingCache<Object, Object> cache : caches()) {
108      // don't let the entries get GCed
109      List<Entry<Object, Object>> warmed = warmUp(cache);
110      for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
111        Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN);
112        Object newValue = new Object();
113        assertSame(entry.getValue(), cache.asMap().putIfAbsent(entry.getKey(), newValue));
114        Object newKey = new Object();
115        assertNull(cache.asMap().putIfAbsent(newKey, entry.getValue()));
116        // this getUnchecked() call shouldn't be a cache miss; verified below
117        assertEquals(entry.getValue(), cache.getUnchecked(entry.getKey()));
118        assertEquals(entry.getValue(), cache.getUnchecked(newKey));
119        // don't let the new entry get GCed
120        warmed.add(entryOf(newKey, entry.getValue()));
121      }
122      assertEquals(WARMUP_SIZE, cache.stats().missCount());
123      checkValidState(cache);
124    }
125  }
126
127  public void testPutAll_populated() {
128    for (LoadingCache<Object, Object> cache : caches()) {
129      // don't let the entries get GCed
130      List<Entry<Object, Object>> warmed = warmUp(cache);
131      Object newKey = new Object();
132      Object newValue = new Object();
133      cache.asMap().putAll(ImmutableMap.of(newKey, newValue));
134      // this getUnchecked() call shouldn't be a cache miss; verified below
135      assertEquals(newValue, cache.getUnchecked(newKey));
136      assertEquals(WARMUP_SIZE, cache.stats().missCount());
137      checkValidState(cache);
138    }
139  }
140
141  public void testReplace_populated() {
142    for (LoadingCache<Object, Object> cache : caches()) {
143      // don't let the entries get GCed
144      List<Entry<Object, Object>> warmed = warmUp(cache);
145      for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
146        Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN);
147        Object newValue = new Object();
148        assertSame(entry.getValue(), cache.asMap().replace(entry.getKey(), newValue));
149        assertTrue(cache.asMap().replace(entry.getKey(), newValue, entry.getValue()));
150        Object newKey = new Object();
151        assertNull(cache.asMap().replace(newKey, entry.getValue()));
152        assertFalse(cache.asMap().replace(newKey, entry.getValue(), newValue));
153        // this getUnchecked() call shouldn't be a cache miss; verified below
154        assertEquals(entry.getValue(), cache.getUnchecked(entry.getKey()));
155        assertFalse(cache.asMap().containsKey(newKey));
156      }
157      assertEquals(WARMUP_SIZE, cache.stats().missCount());
158      checkValidState(cache);
159    }
160  }
161
162  public void testRemove_byKey() {
163    for (LoadingCache<Object, Object> cache : caches()) {
164      // don't let the entries get GCed
165      List<Entry<Object, Object>> warmed = warmUp(cache);
166      for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
167        Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN);
168        Object key = entry.getKey();
169        assertEquals(entry.getValue(), cache.asMap().remove(key));
170        assertNull(cache.asMap().remove(key));
171        assertFalse(cache.asMap().containsKey(key));
172      }
173      checkEmpty(cache);
174    }
175  }
176
177  public void testRemove_byKeyAndValue() {
178    for (LoadingCache<Object, Object> cache : caches()) {
179      // don't let the entries get GCed
180      List<Entry<Object, Object>> warmed = warmUp(cache);
181      for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
182        Object key = warmed.get(i - WARMUP_MIN).getKey();
183        Object value = warmed.get(i - WARMUP_MIN).getValue();
184        assertFalse(cache.asMap().remove(key, -1));
185        assertTrue(cache.asMap().remove(key, value));
186        assertFalse(cache.asMap().remove(key, -1));
187        assertFalse(cache.asMap().containsKey(key));
188      }
189      checkEmpty(cache);
190    }
191  }
192
193  public void testKeySet_populated() {
194    for (LoadingCache<Object, Object> cache : caches()) {
195      Set<Object> keys = cache.asMap().keySet();
196      List<Entry<Object, Object>> warmed = warmUp(cache);
197
198      Set<Object> expected = Maps.newHashMap(cache.asMap()).keySet();
199      ASSERT.that(keys).has().exactlyAs(expected);
200      ASSERT.that(keys.toArray()).has().exactlyAs(expected);
201      ASSERT.that(keys.toArray(new Object[0])).has().exactlyAs(expected);
202
203      new EqualsTester()
204          .addEqualityGroup(cache.asMap().keySet(), keys)
205          .addEqualityGroup(ImmutableSet.of())
206          .testEquals();
207      assertEquals(WARMUP_SIZE, keys.size());
208      for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
209        Object key = warmed.get(i - WARMUP_MIN).getKey();
210        assertTrue(keys.contains(key));
211        assertTrue(keys.remove(key));
212        assertFalse(keys.remove(key));
213        assertFalse(keys.contains(key));
214      }
215      checkEmpty(keys);
216      checkEmpty(cache);
217    }
218  }
219
220  public void testValues_populated() {
221    for (LoadingCache<Object, Object> cache : caches()) {
222      Collection<Object> values = cache.asMap().values();
223      List<Entry<Object, Object>> warmed = warmUp(cache);
224
225      Collection<Object> expected = Maps.newHashMap(cache.asMap()).values();
226      ASSERT.that(values).has().exactlyAs(expected);
227      ASSERT.that(values.toArray()).has().exactlyAs(expected);
228      ASSERT.that(values.toArray(new Object[0])).has().exactlyAs(expected);
229
230      assertEquals(WARMUP_SIZE, values.size());
231      for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
232        Object value = warmed.get(i - WARMUP_MIN).getValue();
233        assertTrue(values.contains(value));
234        assertTrue(values.remove(value));
235        assertFalse(values.remove(value));
236        assertFalse(values.contains(value));
237      }
238      checkEmpty(values);
239      checkEmpty(cache);
240    }
241  }
242
243  @SuppressWarnings("unchecked") // generic array creation
244
245  public void testEntrySet_populated() {
246    for (LoadingCache<Object, Object> cache : caches()) {
247      Set<Entry<Object, Object>> entries = cache.asMap().entrySet();
248      List<Entry<Object, Object>> warmed = warmUp(cache, WARMUP_MIN, WARMUP_MAX);
249
250      Set<?> expected = Maps.newHashMap(cache.asMap()).entrySet();
251      ASSERT.that(entries).has().exactlyAs((Collection<Entry<Object, Object>>) expected);
252      ASSERT.that(entries.toArray()).has().exactlyAs((Collection<Object>) expected);
253      ASSERT.that(entries.toArray(new Entry[0])).has().exactlyAs((Collection<Entry>) expected);
254
255      new EqualsTester()
256          .addEqualityGroup(cache.asMap().entrySet(), entries)
257          .addEqualityGroup(ImmutableSet.of())
258          .testEquals();
259      assertEquals(WARMUP_SIZE, entries.size());
260      for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
261        Entry<Object, Object> newEntry = warmed.get(i - WARMUP_MIN);
262        assertTrue(entries.contains(newEntry));
263        assertTrue(entries.remove(newEntry));
264        assertFalse(entries.remove(newEntry));
265        assertFalse(entries.contains(newEntry));
266      }
267      checkEmpty(entries);
268      checkEmpty(cache);
269    }
270  }
271
272  public void testWriteThroughEntry() {
273    for (LoadingCache<Object, Object> cache : caches()) {
274      cache.getUnchecked(1);
275      Entry<Object, Object> entry = Iterables.getOnlyElement(cache.asMap().entrySet());
276      try {
277        entry.setValue(3);
278        fail("expected entry.setValue to throw UnsupportedOperationException");
279      } catch (UnsupportedOperationException expected) {
280      }
281      try {
282        entry.setValue(null);
283        fail("expected entry.setValue(null) to throw UnsupportedOperationException");
284      } catch (UnsupportedOperationException expected) {
285      }
286      checkValidState(cache);
287    }
288  }
289
290  /* ---------------- Local utilities -------------- */
291
292  /**
293   * Most of the tests in this class run against every one of these caches.
294   */
295  private Iterable<LoadingCache<Object, Object>> caches() {
296    // lots of different ways to configure a LoadingCache
297    CacheBuilderFactory factory = cacheFactory();
298    return Iterables.transform(factory.buildAllPermutations(),
299        new Function<CacheBuilder<Object, Object>, LoadingCache<Object, Object>>() {
300          @Override public LoadingCache<Object, Object> apply(
301              CacheBuilder<Object, Object> builder) {
302            return builder.recordStats().build(identityLoader());
303          }
304        });
305  }
306
307  private CacheBuilderFactory cacheFactory() {
308    // This is trickier than expected. We plan to put 15 values in each of these (WARMUP_MIN to
309    // WARMUP_MAX), but the tests assume no values get evicted. Even with a maximumSize of 100, one
310    // of the values gets evicted. With weak keys, we use identity equality, which means using
311    // System.identityHashCode, which means the assignment of keys to segments is nondeterministic,
312    // so more than (maximumSize / #segments) keys could get assigned to the same segment, which
313    // would cause one to be evicted.
314    return new CacheBuilderFactory()
315        .withKeyStrengths(ImmutableSet.of(Strength.STRONG, Strength.WEAK))
316        .withValueStrengths(ImmutableSet.copyOf(Strength.values()))
317        .withConcurrencyLevels(ImmutableSet.of(1, 4, 16, 64))
318        .withMaximumSizes(ImmutableSet.of(400, 1000))
319        .withInitialCapacities(ImmutableSet.of(0, 1, 10, 100, 1000))
320        .withExpireAfterWrites(ImmutableSet.of(
321            // DurationSpec.of(500, MILLISECONDS),
322            DurationSpec.of(1, SECONDS),
323            DurationSpec.of(24 * 60 * 60 * 1, SECONDS)))
324        .withExpireAfterAccesses(ImmutableSet.of(
325            // DurationSpec.of(500, MILLISECONDS),
326            DurationSpec.of(1, SECONDS),
327            DurationSpec.of(24 * 60 * 60 * 1, SECONDS)))
328        .withRefreshes(ImmutableSet.of(
329            // DurationSpec.of(500, MILLISECONDS),
330            DurationSpec.of(1, SECONDS),
331            DurationSpec.of(24 * 60 * 60 * 1, SECONDS)));
332  }
333
334  private List<Map.Entry<Object, Object>> warmUp(LoadingCache<Object, Object> cache) {
335    return warmUp(cache, WARMUP_MIN, WARMUP_MAX);
336  }
337
338  /**
339   * Returns the entries that were added to the map, so they won't fall out of a map with weak or
340   * soft references until the caller drops the reference to the returned entries.
341   */
342  private List<Map.Entry<Object, Object>> warmUp(
343      LoadingCache<Object, Object> cache, int minimum, int maximum) {
344
345    List<Map.Entry<Object, Object>> entries = Lists.newArrayList();
346    for (int i = minimum; i < maximum; i++) {
347      Object key = i;
348      Object value = cache.getUnchecked(key);
349      entries.add(entryOf(key, value));
350    }
351    return entries;
352  }
353
354  private Entry<Object, Object> entryOf(Object key, Object value) {
355    return Maps.immutableEntry(key, value);
356  }
357
358  private void assertMapSize(Map<?, ?> map, int size) {
359    assertEquals(size, map.size());
360    if (size > 0) {
361      assertFalse(map.isEmpty());
362    } else {
363      assertTrue(map.isEmpty());
364    }
365    assertCollectionSize(map.keySet(), size);
366    assertCollectionSize(map.entrySet(), size);
367    assertCollectionSize(map.values(), size);
368  }
369
370  private void assertCollectionSize(Collection<?> collection, int size) {
371    assertEquals(size, collection.size());
372    if (size > 0) {
373      assertFalse(collection.isEmpty());
374    } else {
375      assertTrue(collection.isEmpty());
376    }
377    assertEquals(size, Iterables.size(collection));
378    assertEquals(size, Iterators.size(collection.iterator()));
379  }
380}
381