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 
15 package com.google.common.cache;
16 
17 import static com.google.common.cache.CacheTesting.checkEmpty;
18 import static com.google.common.cache.CacheTesting.checkValidState;
19 import static com.google.common.cache.TestingCacheLoaders.identityLoader;
20 import static com.google.common.truth.Truth.assertThat;
21 import static java.util.concurrent.TimeUnit.DAYS;
22 import static java.util.concurrent.TimeUnit.SECONDS;
23 
24 import com.google.common.base.Function;
25 import com.google.common.cache.CacheBuilderFactory.DurationSpec;
26 import com.google.common.cache.LocalCache.Strength;
27 import com.google.common.collect.ImmutableMap;
28 import com.google.common.collect.ImmutableSet;
29 import com.google.common.collect.Iterables;
30 import com.google.common.collect.Iterators;
31 import com.google.common.collect.Lists;
32 import com.google.common.collect.Maps;
33 import com.google.common.testing.EqualsTester;
34 
35 import junit.framework.TestCase;
36 
37 import java.util.Collection;
38 import java.util.List;
39 import java.util.Map;
40 import java.util.Map.Entry;
41 import java.util.Set;
42 
43 /**
44  * {@link LoadingCache} tests that deal with caches that actually contain some key-value mappings.
45  *
46  * @author mike nonemacher
47  */
48 
49 public class PopulatedCachesTest extends TestCase {
50   // we use integers as keys; make sure the range covers some values that ARE cached by
51   // Integer.valueOf(int), and some that are not cached. (127 is the highest cached value.)
52   static final int WARMUP_MIN = 120;
53   static final int WARMUP_MAX = 135;
54   static final int WARMUP_SIZE = WARMUP_MAX - WARMUP_MIN;
55 
testSize_populated()56   public void testSize_populated() {
57     for (LoadingCache<Object, Object> cache : caches()) {
58       // don't let the entries get GCed
59       List<Entry<Object, Object>> warmed = warmUp(cache);
60       assertEquals(WARMUP_SIZE, cache.size());
61       assertMapSize(cache.asMap(), WARMUP_SIZE);
62       checkValidState(cache);
63     }
64   }
65 
testContainsKey_found()66   public void testContainsKey_found() {
67     for (LoadingCache<Object, Object> cache : caches()) {
68       // don't let the entries get GCed
69       List<Entry<Object, Object>> warmed = warmUp(cache);
70       for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
71         Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN);
72         assertTrue(cache.asMap().containsKey(entry.getKey()));
73         assertTrue(cache.asMap().containsValue(entry.getValue()));
74         // this getUnchecked() call shouldn't be a cache miss; verified below
75         assertEquals(entry.getValue(), cache.getUnchecked(entry.getKey()));
76       }
77       assertEquals(WARMUP_SIZE, cache.stats().missCount());
78       checkValidState(cache);
79     }
80   }
81 
testPut_populated()82   public void testPut_populated() {
83     for (LoadingCache<Object, Object> cache : caches()) {
84       // don't let the entries get GCed
85       List<Entry<Object, Object>> warmed = warmUp(cache);
86       for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
87         Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN);
88         Object newValue = new Object();
89         assertSame(entry.getValue(), cache.asMap().put(entry.getKey(), newValue));
90         // don't let the new entry get GCed
91         warmed.add(entryOf(entry.getKey(), newValue));
92         Object newKey = new Object();
93         assertNull(cache.asMap().put(newKey, entry.getValue()));
94         // this getUnchecked() call shouldn't be a cache miss; verified below
95         assertEquals(newValue, cache.getUnchecked(entry.getKey()));
96         assertEquals(entry.getValue(), cache.getUnchecked(newKey));
97         // don't let the new entry get GCed
98         warmed.add(entryOf(newKey, entry.getValue()));
99       }
100       assertEquals(WARMUP_SIZE, cache.stats().missCount());
101       checkValidState(cache);
102     }
103   }
104 
testPutIfAbsent_populated()105   public void testPutIfAbsent_populated() {
106     for (LoadingCache<Object, Object> cache : caches()) {
107       // don't let the entries get GCed
108       List<Entry<Object, Object>> warmed = warmUp(cache);
109       for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
110         Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN);
111         Object newValue = new Object();
112         assertSame(entry.getValue(), cache.asMap().putIfAbsent(entry.getKey(), newValue));
113         Object newKey = new Object();
114         assertNull(cache.asMap().putIfAbsent(newKey, entry.getValue()));
115         // this getUnchecked() call shouldn't be a cache miss; verified below
116         assertEquals(entry.getValue(), cache.getUnchecked(entry.getKey()));
117         assertEquals(entry.getValue(), cache.getUnchecked(newKey));
118         // don't let the new entry get GCed
119         warmed.add(entryOf(newKey, entry.getValue()));
120       }
121       assertEquals(WARMUP_SIZE, cache.stats().missCount());
122       checkValidState(cache);
123     }
124   }
125 
testPutAll_populated()126   public void testPutAll_populated() {
127     for (LoadingCache<Object, Object> cache : caches()) {
128       // don't let the entries get GCed
129       List<Entry<Object, Object>> warmed = warmUp(cache);
130       Object newKey = new Object();
131       Object newValue = new Object();
132       cache.asMap().putAll(ImmutableMap.of(newKey, newValue));
133       // this getUnchecked() call shouldn't be a cache miss; verified below
134       assertEquals(newValue, cache.getUnchecked(newKey));
135       assertEquals(WARMUP_SIZE, cache.stats().missCount());
136       checkValidState(cache);
137     }
138   }
139 
testReplace_populated()140   public void testReplace_populated() {
141     for (LoadingCache<Object, Object> cache : caches()) {
142       // don't let the entries get GCed
143       List<Entry<Object, Object>> warmed = warmUp(cache);
144       for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
145         Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN);
146         Object newValue = new Object();
147         assertSame(entry.getValue(), cache.asMap().replace(entry.getKey(), newValue));
148         assertTrue(cache.asMap().replace(entry.getKey(), newValue, entry.getValue()));
149         Object newKey = new Object();
150         assertNull(cache.asMap().replace(newKey, entry.getValue()));
151         assertFalse(cache.asMap().replace(newKey, entry.getValue(), newValue));
152         // this getUnchecked() call shouldn't be a cache miss; verified below
153         assertEquals(entry.getValue(), cache.getUnchecked(entry.getKey()));
154         assertFalse(cache.asMap().containsKey(newKey));
155       }
156       assertEquals(WARMUP_SIZE, cache.stats().missCount());
157       checkValidState(cache);
158     }
159   }
160 
testRemove_byKey()161   public void testRemove_byKey() {
162     for (LoadingCache<Object, Object> cache : caches()) {
163       // don't let the entries get GCed
164       List<Entry<Object, Object>> warmed = warmUp(cache);
165       for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
166         Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN);
167         Object key = entry.getKey();
168         assertEquals(entry.getValue(), cache.asMap().remove(key));
169         assertNull(cache.asMap().remove(key));
170         assertFalse(cache.asMap().containsKey(key));
171       }
172       checkEmpty(cache);
173     }
174   }
175 
testRemove_byKeyAndValue()176   public void testRemove_byKeyAndValue() {
177     for (LoadingCache<Object, Object> cache : caches()) {
178       // don't let the entries get GCed
179       List<Entry<Object, Object>> warmed = warmUp(cache);
180       for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
181         Object key = warmed.get(i - WARMUP_MIN).getKey();
182         Object value = warmed.get(i - WARMUP_MIN).getValue();
183         assertFalse(cache.asMap().remove(key, -1));
184         assertTrue(cache.asMap().remove(key, value));
185         assertFalse(cache.asMap().remove(key, -1));
186         assertFalse(cache.asMap().containsKey(key));
187       }
188       checkEmpty(cache);
189     }
190   }
191 
testKeySet_populated()192   public void testKeySet_populated() {
193     for (LoadingCache<Object, Object> cache : caches()) {
194       Set<Object> keys = cache.asMap().keySet();
195       List<Entry<Object, Object>> warmed = warmUp(cache);
196 
197       Set<Object> expected = Maps.newHashMap(cache.asMap()).keySet();
198       assertThat(keys).has().exactlyAs(expected);
199       assertThat(keys.toArray()).asList().has().exactlyAs(expected);
200       assertThat(keys.toArray(new Object[0])).asList().has().exactlyAs(expected);
201 
202       new EqualsTester()
203           .addEqualityGroup(cache.asMap().keySet(), keys)
204           .addEqualityGroup(ImmutableSet.of())
205           .testEquals();
206       assertEquals(WARMUP_SIZE, keys.size());
207       for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
208         Object key = warmed.get(i - WARMUP_MIN).getKey();
209         assertTrue(keys.contains(key));
210         assertTrue(keys.remove(key));
211         assertFalse(keys.remove(key));
212         assertFalse(keys.contains(key));
213       }
214       checkEmpty(keys);
215       checkEmpty(cache);
216     }
217   }
218 
testValues_populated()219   public void testValues_populated() {
220     for (LoadingCache<Object, Object> cache : caches()) {
221       Collection<Object> values = cache.asMap().values();
222       List<Entry<Object, Object>> warmed = warmUp(cache);
223 
224       Collection<Object> expected = Maps.newHashMap(cache.asMap()).values();
225       assertThat(values).has().exactlyAs(expected);
226       assertThat(values.toArray()).asList().has().exactlyAs(expected);
227       assertThat(values.toArray(new Object[0])).asList().has().exactlyAs(expected);
228 
229       assertEquals(WARMUP_SIZE, values.size());
230       for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) {
231         Object value = warmed.get(i - WARMUP_MIN).getValue();
232         assertTrue(values.contains(value));
233         assertTrue(values.remove(value));
234         assertFalse(values.remove(value));
235         assertFalse(values.contains(value));
236       }
237       checkEmpty(values);
238       checkEmpty(cache);
239     }
240   }
241 
242   @SuppressWarnings("unchecked") // generic array creation
243 
testEntrySet_populated()244   public void testEntrySet_populated() {
245     for (LoadingCache<Object, Object> cache : caches()) {
246       Set<Entry<Object, Object>> entries = cache.asMap().entrySet();
247       List<Entry<Object, Object>> warmed = warmUp(cache, WARMUP_MIN, WARMUP_MAX);
248 
249       Set<?> expected = Maps.newHashMap(cache.asMap()).entrySet();
250       assertThat(entries).has().exactlyAs((Collection<Entry<Object, Object>>) expected);
251       assertThat(entries.toArray()).asList().has().exactlyAs((Collection<Object>) expected);
252       assertThat(entries.toArray(new Entry[0])).asList()
253           .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 
testWriteThroughEntry()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    */
caches()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(1, DAYS)))
324         .withExpireAfterAccesses(ImmutableSet.of(
325             // DurationSpec.of(500, MILLISECONDS),
326             DurationSpec.of(1, SECONDS),
327             DurationSpec.of(1, DAYS)))
328         .withRefreshes(ImmutableSet.of(
329             // DurationSpec.of(500, MILLISECONDS),
330             DurationSpec.of(1, SECONDS),
331             DurationSpec.of(1, DAYS)));
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