Add a TrimmedConfigurationCache. This cache is the first step to the prototype retroactive trimming mechanism, and the heart of it. It hasn't been much optimized; the expectation is that these operations will need to be more heavily optimized for speed once the cache is in active use. RELNOTES: None. PiperOrigin-RevId: 220158685
diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD index e366141..943dee6 100644 --- a/src/main/java/com/google/devtools/build/lib/BUILD +++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -58,6 +58,7 @@ "//src/main/java/com/google/devtools/build/lib/shell:srcs", "//src/main/java/com/google/devtools/build/lib/skyframe/packages:srcs", "//src/main/java/com/google/devtools/build/lib/skyframe/serialization:srcs", + "//src/main/java/com/google/devtools/build/lib/skyframe/trimming:srcs", "//src/main/java/com/google/devtools/build/lib/skylarkbuildapi:srcs", "//src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android:srcs", "//src/main/java/com/google/devtools/build/lib/skylarkbuildapi/apple:srcs",
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/trimming/BUILD b/src/main/java/com/google/devtools/build/lib/skyframe/trimming/BUILD new file mode 100644 index 0000000..9b2c425 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/skyframe/trimming/BUILD
@@ -0,0 +1,23 @@ +# Classes which provide support for automatically trimming configuration to avoid wasted work during a build. + +package( + default_visibility = ["//src:__subpackages__"], +) + +filegroup( + name = "srcs", + srcs = glob(["**"]), +) + +java_library( + name = "trimmed_configuration_cache", + srcs = [ + "ConfigurationComparer.java", + "KeyAndState.java", + "TrimmedConfigurationCache.java", + ], + deps = [ + "//third_party:auto_value", + "//third_party:guava", + ], +)
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/trimming/ConfigurationComparer.java b/src/main/java/com/google/devtools/build/lib/skyframe/trimming/ConfigurationComparer.java new file mode 100644 index 0000000..91b63b4 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/skyframe/trimming/ConfigurationComparer.java
@@ -0,0 +1,72 @@ +// Copyright 2018 The Bazel Authors. All rights reserved. +// +// 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.devtools.build.lib.skyframe.trimming; + +import java.util.function.BiFunction; + +/** + * Interface describing a function which compares two configurations and determines their + * relationship. + */ +@FunctionalInterface +public interface ConfigurationComparer<ConfigurationT> + extends BiFunction<ConfigurationT, ConfigurationT, ConfigurationComparer.Result> { + /** The outcome of comparing two configurations. */ + public enum Result { + /** + * All fragments in the first configuration are present and equal in the second, and vice versa. + */ + EQUAL(true, true, true), + /** + * All shared fragments are equal, but the second configuration has additional fragments the + * first does not. + */ + SUBSET(true, false, true), + /** + * All shared fragments are equal, but the first configuration has additional fragments the + * second does not. + */ + SUPERSET(false, true, true), + /** + * The two configurations each have fragments the other does not, but the shared fragments are + * equal. + */ + ALL_SHARED_FRAGMENTS_EQUAL(false, false, true), + /** At least one fragment shared between the two configurations is unequal. */ + DIFFERENT(false, false, false); + + private final boolean isSubsetOrEqual; + private final boolean isSupersetOrEqual; + private final boolean hasEqualSharedFragments; + + Result(boolean isSubsetOrEqual, boolean isSupersetOrEqual, boolean hasEqualSharedFragments) { + this.isSubsetOrEqual = isSubsetOrEqual; + this.isSupersetOrEqual = isSupersetOrEqual; + this.hasEqualSharedFragments = hasEqualSharedFragments; + } + + public boolean isSubsetOrEqual() { + return isSubsetOrEqual; + } + + public boolean isSupersetOrEqual() { + return isSupersetOrEqual; + } + + public boolean hasEqualSharedFragments() { + return hasEqualSharedFragments; + } + } +}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/trimming/KeyAndState.java b/src/main/java/com/google/devtools/build/lib/skyframe/trimming/KeyAndState.java new file mode 100644 index 0000000..b30f42c --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/skyframe/trimming/KeyAndState.java
@@ -0,0 +1,64 @@ +// Copyright 2018 The Bazel Authors. All rights reserved. +// +// 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.devtools.build.lib.skyframe.trimming; + +import com.google.auto.value.AutoValue; + +/** + * A pair of some key type and a valid/invalid state, for use in {@link TrimmedConfigurationCache}. + */ +@AutoValue +abstract class KeyAndState<KeyT> { + enum State { + VALID(true), + POSSIBLY_INVALID(false); + + private final boolean isKnownValid; + + State(boolean isKnownValid) { + this.isKnownValid = isKnownValid; + } + + boolean isKnownValid() { + return isKnownValid; + } + } + + abstract KeyT getKey(); + + abstract State getState(); + + static <KeyT> KeyAndState<KeyT> create(KeyT key) { + return create(key, State.VALID); + } + + private static <KeyT> KeyAndState<KeyT> create(KeyT key, State state) { + return new AutoValue_KeyAndState<>(key, state); + } + + KeyAndState<KeyT> asValidated() { + if (State.VALID.equals(getState())) { + return this; + } + return create(getKey(), State.VALID); + } + + KeyAndState<KeyT> asInvalidated() { + if (State.POSSIBLY_INVALID.equals(getState())) { + return this; + } + return create(getKey(), State.POSSIBLY_INVALID); + } +}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/trimming/TrimmedConfigurationCache.java b/src/main/java/com/google/devtools/build/lib/skyframe/trimming/TrimmedConfigurationCache.java new file mode 100644 index 0000000..ea82f13 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/skyframe/trimming/TrimmedConfigurationCache.java
@@ -0,0 +1,392 @@ +// Copyright 2018 The Bazel Authors. All rights reserved. +// +// 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.devtools.build.lib.skyframe.trimming; + +import com.google.common.base.Preconditions; +import java.util.Map.Entry; +import java.util.Optional; +import java.util.concurrent.ConcurrentHashMap; +import java.util.function.Function; +import java.util.function.UnaryOperator; + +/** + * Cache which tracks canonical invocations and matches keys to equivalent keys (after trimming). + * + * <p>This cache can be built independently of the massive build dependency that is build-base + * (SkyFunctions and BuildConfiguration and so on), and so it is - thus, it uses type parameters to + * speak more abstractly about what it cares about. + * + * <p>Consider a {@code <KeyT>} as a pair of {@code <DescriptorT>} and {@code <ConfigurationT>}. The + * descriptor describes what the key builds, while the configuration describes how to build it. + * + * <p>For example, a ConfiguredTargetKey is made up of a Label, which is its descriptor, and a + * BuildConfiguration, which is its configuration. An AspectKey is made up of a Label and a set of + * AspectDescriptors describing the aspect and the aspects it depends on, all of which are part of + * the AspectKey's descriptor, and also has a BuildConfiguration, which is its configuration. + * + * <p>A key always uses all of its descriptor, but it may only use part of its configuration. A Java + * configured target may have no use for Python configuration, for example. Thus, it would produce + * the same result to evaluate that target with a configuration which doesn't include Python data. + * Reducing the configuration to the subset configuration which only includes the bits the target + * actually needs is called trimming the configuration. + * + * <p>If this trimmed configuration is a subset of another configuration, then building whatever the + * descriptor refers to with that other configuration will produce the same result as the trimmed + * configuration, which is the same result as the configuration that the trimmed configuration was + * trimmed from. + * + * <p>This cache provides methods for matching keys which would evaluate to the same result because + * they have the same descriptor and trim to the same configuration, allowing callers to avoid doing + * work that has already been done. It also permits invalidating, revalidating, and removing these + * keys, as might happen during their lifecycle (if something they depend on has changed, etc.). + * + * <p>Internally, this cache is essentially a very sparse table. Each row, headed by a descriptor, + * describes the possible configurations of that descriptor. Columns, headed by a trimmed + * configuration, represent minimal configurations that descriptors can be invoked with. And a cell + * contains the key which corresponds to the canonical invocation of that descriptor with that + * configuration. + * + * <p>This class expects to be used in ways which are consistent with trimming. That is to say: + * + * <ul> + * <li>If the same key is put in the cache twice with different trimmed configurations, it must be + * invalidated between the two puts. Afterward, the original trimmed configuration is no + * longer valid for the rest of this build. + * <li>No trimmed configuration must be put in the cache which has equal values for every fragment + * it shares with another trimmed configuration already in the cache, unless the key + * associated with the other configuration has been invalidated. Afterward, the configuration + * which had previously been invalidated is no longer valid for the rest of this build. + * <li>Methods which read and add to the cache - {@link #get(KeyT)}, {@link #revalidate(KeyT)}, + * and {@link #putIfAbsent(KeyT, ConfigurationT)} - may be used together in one phase of the + * build. Methods which remove from the cache - {@link #invalidate(KeyT)}, {@link + * #remove(KeyT)}, and {@link #clear()} - may be used together in another phase of the build. + * Calls to these groups of methods must never be interleaved. + * </ul> + * + * <p>If used as described above, this class is thread-safe. + */ +public final class TrimmedConfigurationCache<KeyT, DescriptorT, ConfigurationT> { + + // ======== Tuning parameters ========== + /** The initial capacity of the cache of descriptors. */ + private static final int CACHE_INITIAL_SIZE = 100; + /** The table density for the cache of descriptors. */ + private static final float CACHE_LOAD_FACTOR = 0.9f; + /** The number of threads expected to be writing to the descriptor cache at a time. */ + private static final int CACHE_CONCURRENCY_LEVEL = 16; + /** + * The number of configurations to expect in a single descriptor - that is, the initial capacity + * of descriptors' maps. + */ + private static final int EXPECTED_CONFIGURATIONS_PER_DESCRIPTOR = 4; + /** + * The table density for the {@link ConcurrentHashMap ConcurrentHashMaps} created for tracking + * configurations of each descriptor. + */ + private static final float DESCRIPTOR_LOAD_FACTOR = 0.9f; + /** The number of threads expected to be writing to a single descriptor at a time. */ + private static final int DESCRIPTOR_CONCURRENCY_LEVEL = 1; + + private final Function<KeyT, DescriptorT> descriptorExtractor; + private final Function<KeyT, ConfigurationT> configurationExtractor; + + private final ConfigurationComparer<ConfigurationT> configurationComparer; + + private volatile ConcurrentHashMap< + DescriptorT, ConcurrentHashMap<ConfigurationT, KeyAndState<KeyT>>> + descriptors; + + /** + * Constructs a new TrimmedConfigurationCache with the given methods of extracting descriptors and + * configurations from keys, and uses the given predicate to determine the relationship between + * two configurations. + * + * <p>{@code configurationComparer} should be consistent with equals - that is, + * {@code a.equals(b) == b.equals(a) == configurationComparer.compare(a, b).equals(Result.EQUAL)} + */ + public TrimmedConfigurationCache( + Function<KeyT, DescriptorT> descriptorExtractor, + Function<KeyT, ConfigurationT> configurationExtractor, + ConfigurationComparer<ConfigurationT> configurationComparer) { + this.descriptorExtractor = descriptorExtractor; + this.configurationExtractor = configurationExtractor; + this.configurationComparer = configurationComparer; + this.descriptors = newCacheMap(); + } + + /** + * Looks for a key with the same descriptor as the input key, which has a configuration that + * trimmed to a subset of the input key's. + * + * <p>Note that this is not referring to a <em>proper</em> subset; it's quite possible for a key + * to "trim" to a configuration equal to its configuration. That is, without anything being + * removed. + * + * <p>If such a key has been added to this cache, it is returned in a present {@link Optional}. + * Invoking this key will produce the same result as invoking the input key. + * + * <p>If no such key has been added to this cache, or if a key has been added to the cache and + * subsequently been the subject of an {@link #invalidate(KeyT)}, an absent Optional will be + * returned instead. No currently-valid key has trimmed to an equivalent configuration, and so the + * input key should be executed. + */ + public Optional<KeyT> get(KeyT input) { + DescriptorT descriptor = getDescriptorFor(input); + ConcurrentHashMap<ConfigurationT, KeyAndState<KeyT>> trimmingsOfDescriptor = + descriptors.get(descriptor); + if (trimmingsOfDescriptor == null) { + // There are no entries at all for this descriptor. + return Optional.empty(); + } + ConfigurationT candidateConfiguration = getConfigurationFor(input); + for (Entry<ConfigurationT, KeyAndState<KeyT>> entry : trimmingsOfDescriptor.entrySet()) { + ConfigurationT trimmedConfig = entry.getKey(); + KeyAndState<KeyT> canonicalKeyAndState = entry.getValue(); + if (canSubstituteFor(candidateConfiguration, trimmedConfig, canonicalKeyAndState)) { + return Optional.of(canonicalKeyAndState.getKey()); + } + } + return Optional.empty(); + } + + /** + * Returns whether the given trimmed configuration and key are a suitable substitute for the + * candidate configuration. + */ + private boolean canSubstituteFor( + ConfigurationT candidateConfiguration, + ConfigurationT trimmedConfiguration, + KeyAndState<KeyT> canonicalKeyAndState) { + return canonicalKeyAndState.getState().isKnownValid() + && compareConfigurations(trimmedConfiguration, candidateConfiguration).isSubsetOrEqual(); + } + + /** + * Attempts to record the given key as the canonical invocation for its descriptor and the + * passed-in trimmed configuration. + * + * <p>The trimmed configuration must be a subset of the input key's configuration. Otherwise, + * {@link IllegalArgumentException} will be thrown. + * + * <p>If another key matching this configuration is found, that key will be returned. That key + * represents the canonical invocation, which should produce the same result as the input key. It + * may have been previously invalidated, but will be considered revalidated at this point. + * + * <p>Otherwise, if the input key is the first to trim to this configuration, the input key is + * returned. + */ + public KeyT putIfAbsent(KeyT canonicalKey, ConfigurationT trimmedConfiguration) { + ConfigurationT fullConfiguration = getConfigurationFor(canonicalKey); + Preconditions.checkArgument( + compareConfigurations(trimmedConfiguration, fullConfiguration).isSubsetOrEqual()); + ConcurrentHashMap<ConfigurationT, KeyAndState<KeyT>> trimmingsOfDescriptor = + descriptors.computeIfAbsent(getDescriptorFor(canonicalKey), unused -> newDescriptorMap()); + KeyAndState<KeyT> currentMapping = + trimmingsOfDescriptor.compute( + trimmedConfiguration, + (configuration, currentValue) -> { + if (currentValue == null) { + return KeyAndState.create(canonicalKey); + } else { + return currentValue.asValidated(); + } + }); + boolean newlyAdded = currentMapping.getKey().equals(canonicalKey); + int failedRemoves; + do { + failedRemoves = 0; + for (Entry<ConfigurationT, KeyAndState<KeyT>> entry : trimmingsOfDescriptor.entrySet()) { + if (entry.getValue().getState().equals(KeyAndState.State.POSSIBLY_INVALID)) { + // Remove invalidated keys where: + // * the same key evaluated to a different configuration than it does now + // * (for trimmed configurations not yet seen) the new trimmed configuration has equal + // values for every fragment it shares with the old configuration (including subsets + // or supersets). + // These are keys we know will not be revalidated as part of the current build. + // Although it also ensures that we don't remove the entry we just added, the check for + // invalidation is mainly to avoid wasting time checking entries that are still valid for + // the current build and therefore will not match either of these properties. + if (entry.getValue().getKey().equals(canonicalKey) + || (newlyAdded + && compareConfigurations(trimmedConfiguration, entry.getKey()) + .hasEqualSharedFragments())) { + if (!trimmingsOfDescriptor.remove(entry.getKey(), entry.getValue())) { + // It's possible that this entry was removed by another thread in the meantime. + failedRemoves += 1; + } + } + } + } + } while (failedRemoves > 0); + return currentMapping.getKey(); + } + + /** + * Marks the given key as invalidated. + * + * <p>An invalidated key will not be returned from {@link #get(KeyT)}, as it cannot be proven that + * the key will still trim to the same configuration. + * + * <p>This invalidation is undone if the input key is passed to {@link #revalidate(KeyT)}, or if + * the configuration it originally trimmed to is passed to a call of {@link putIfAbsent(KeyT, + * ConfigurationT)}. This is true regardless of whether the key passed to putIfAbsent is the same + * as the input to this method. + * + * <p>If the key is not currently canonical for any descriptor/configuration pair, or if the key + * had previously been invalidated and not revalidated, this method has no effect. + */ + public void invalidate(KeyT key) { + updateEntryWithRetries(key, KeyAndState::asInvalidated); + } + + /** + * Unmarks the given key as invalidated. + * + * <p>This undoes the effects of {@link #invalidate(KeyT)}, allowing the key to be returned from + * {@link #get(KeyT)} again. + * + * <p>If the key is not currently canonical for any descriptor/configuration pair, or if the key + * had not previously been invalidated or had since been revalidated, this method has no effect. + */ + public void revalidate(KeyT key) { + updateEntryWithRetries(key, KeyAndState::asValidated); + } + + /** + * Completely removes the given key from the cache. + * + * <p>After this call, {@link #get(KeyT)} and {@link #putIfAbsent(KeyT, ConfigurationT)} will no + * longer return this key unless it is put back in the cache with putIfAbsent. + * + * <p>If the key is not currently canonical for any descriptor/configuration pair, this method has + * no effect. + */ + public void remove(KeyT key) { + // Return null from the transformer to remove the key from the map. + updateEntryWithRetries(key, unused -> null); + + DescriptorT descriptor = getDescriptorFor(key); + ConcurrentHashMap<ConfigurationT, KeyAndState<KeyT>> trimmingsOfDescriptor = + descriptors.get(descriptor); + if (trimmingsOfDescriptor != null && trimmingsOfDescriptor.isEmpty()) { + descriptors.remove(descriptor, trimmingsOfDescriptor); + } + } + + /** + * Finds the entry in the cache where the given key is canonical and updates or removes it. + * + * <p>The transformation is applied transactionally; that is, if another change has happened since + * the value was first looked up, the new value is retrieved and the transformation is applied + * again. This repeats until there are no conflicts. + * + * <p>This method has no effect if this key is currently not canonical. + * + * @param transformation The transformation to apply to the given entry. The entry will be + * replaced with the value returned from invoking this on the original value. If it returns + * null, the entry will be removed instead. If it returns the same instance, nothing will be + * done to the entry. + */ + private void updateEntryWithRetries(KeyT key, UnaryOperator<KeyAndState<KeyT>> transformation) { + while (!updateEntryIfNoConflicts(key, transformation)) {} + } + + /** + * Finds the entry in the cache where the given key is canonical and updates or removes it. + * + * <p>Only one attempt is made, and if there's a collision with another change, false is returned + * and the map is not changed. + * + * <p>This method succeeds (returns {@code true}) without doing anything if this key is currently + * not canonical. + * + * @param transformation The transformation to apply to the given entry. The entry will be + * replaced with the value returned from invoking this on the original value. If it returns + * null, the entry will be removed instead. If it returns the same instance, nothing will be + * done to the entry. + */ + private boolean updateEntryIfNoConflicts( + KeyT key, UnaryOperator<KeyAndState<KeyT>> transformation) { + DescriptorT descriptor = getDescriptorFor(key); + ConcurrentHashMap<ConfigurationT, KeyAndState<KeyT>> trimmingsOfDescriptor = + descriptors.get(descriptor); + if (trimmingsOfDescriptor == null) { + // There are no entries at all for this descriptor. + return true; + } + + for (Entry<ConfigurationT, KeyAndState<KeyT>> entry : trimmingsOfDescriptor.entrySet()) { + KeyAndState<KeyT> currentValue = entry.getValue(); + if (currentValue.getKey().equals(key)) { + KeyAndState<KeyT> newValue = transformation.apply(currentValue); + if (newValue == null) { + return trimmingsOfDescriptor.remove(entry.getKey(), currentValue); + } else if (newValue != currentValue) { + return trimmingsOfDescriptor.replace(entry.getKey(), currentValue, newValue); + } else { + // newValue == currentValue, there's nothing to do + return true; + } + } + } + // The key requested wasn't in the map, so there's nothing to do + return true; + } + + /** + * Removes all keys from this cache, resetting it to its empty state. + * + * <p>This is equivalent to calling {@link #remove(KeyT)} on every key which had ever been passed + * to {@link #putIfAbsent(KeyT, ConfigurationT)}. + */ + public void clear() { + // Getting a brand new instance lets the old map be garbage collected, reducing its memory + // footprint from its previous expansions. + this.descriptors = newCacheMap(); + } + + /** Retrieves the descriptor by calling the descriptorExtractor. */ + private DescriptorT getDescriptorFor(KeyT key) { + return descriptorExtractor.apply(key); + } + + /** Retrieves the configuration by calling the configurationExtractor. */ + private ConfigurationT getConfigurationFor(KeyT key) { + return configurationExtractor.apply(key); + } + + /** + * Checks whether the first configuration is equal to or a subset of the second by calling the + * configurationComparer. + */ + private ConfigurationComparer.Result compareConfigurations( + ConfigurationT left, ConfigurationT right) { + return configurationComparer.apply(left, right); + } + + /** Generates a new map suitable for storing the cache as a whole. */ + private ConcurrentHashMap<DescriptorT, ConcurrentHashMap<ConfigurationT, KeyAndState<KeyT>>> + newCacheMap() { + return new ConcurrentHashMap<>(CACHE_INITIAL_SIZE, CACHE_LOAD_FACTOR, CACHE_CONCURRENCY_LEVEL); + } + + /** Generates a new map suitable for storing the cache of configurations for a descriptor. */ + private ConcurrentHashMap<ConfigurationT, KeyAndState<KeyT>> newDescriptorMap() { + return new ConcurrentHashMap<>( + EXPECTED_CONFIGURATIONS_PER_DESCRIPTOR, + DESCRIPTOR_LOAD_FACTOR, + DESCRIPTOR_CONCURRENCY_LEVEL); + } +}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/BUILD b/src/test/java/com/google/devtools/build/lib/skyframe/BUILD index 2f0e017..086e999 100644 --- a/src/test/java/com/google/devtools/build/lib/skyframe/BUILD +++ b/src/test/java/com/google/devtools/build/lib/skyframe/BUILD
@@ -6,7 +6,7 @@ filegroup( name = "srcs", testonly = 0, - srcs = glob(["**"]), + srcs = glob(["**"]) + ["//src/test/java/com/google/devtools/build/lib/skyframe/trimming:srcs"], visibility = ["//src/test/java/com/google/devtools/build/lib:__pkg__"], )
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/trimming/BUILD b/src/test/java/com/google/devtools/build/lib/skyframe/trimming/BUILD new file mode 100644 index 0000000..a508186 --- /dev/null +++ b/src/test/java/com/google/devtools/build/lib/skyframe/trimming/BUILD
@@ -0,0 +1,42 @@ +# Tests for the trimming support classes. + +package( + default_testonly = 1, +) + +filegroup( + name = "srcs", + testonly = 0, + srcs = glob(["**"]), + visibility = ["//src:__subpackages__"], +) + +java_library( + name = "test_key", + srcs = ["TestKey.java"], + deps = [ + "//src/main/java/com/google/devtools/build/lib/skyframe/trimming:trimmed_configuration_cache", + "//third_party:auto_value", + "//third_party:guava", + ], +) + +java_test( + name = "TrimmedConfigurationCacheTests", + size = "small", + srcs = [ + "TestKeyTest.java", + "TrimmedConfigurationCacheTest.java", + ], + test_class = "com.google.devtools.build.lib.AllTests", + runtime_deps = ["//src/test/java/com/google/devtools/build/lib:test_runner"], + deps = [ + ":test_key", + "//src/main/java/com/google/devtools/build/lib/skyframe/trimming:trimmed_configuration_cache", + "//third_party:guava", + "//third_party:guava-testlib", + "//third_party:junit4", + "//third_party:truth", + "//third_party:truth8", + ], +)
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/trimming/TestKey.java b/src/test/java/com/google/devtools/build/lib/skyframe/trimming/TestKey.java new file mode 100644 index 0000000..45316c1 --- /dev/null +++ b/src/test/java/com/google/devtools/build/lib/skyframe/trimming/TestKey.java
@@ -0,0 +1,91 @@ +// Copyright 2018 The Bazel Authors. All rights reserved. +// +// 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.devtools.build.lib.skyframe.trimming; + +import com.google.auto.value.AutoValue; +import com.google.common.base.Preconditions; +import com.google.common.base.Splitter; +import com.google.common.base.Strings; +import com.google.common.collect.ImmutableMap; +import com.google.common.collect.Sets; +import java.util.Set; +import java.util.regex.Matcher; +import java.util.regex.Pattern; + +/** A simple key suitable for putting into a TrimmedConfigurationCache for testing it. */ +@AutoValue +abstract class TestKey { + abstract String descriptor(); + + abstract ImmutableMap<String, String> configuration(); + + static TestKey create(String descriptor, ImmutableMap<String, String> configuration) { + return new AutoValue_TestKey(descriptor, configuration); + } + + // Test keys look like <config: value, config: value> descriptor + private static final Pattern TEST_KEY_SHAPE = + Pattern.compile("<(?<config>[^>]*)>(?<descriptor>.+)"); + + static TestKey parse(String input) { + Matcher matcher = TEST_KEY_SHAPE.matcher(input.trim()); + Preconditions.checkArgument(matcher.matches()); + return create( + matcher.group("descriptor").trim(), parseConfiguration(matcher.group("config").trim())); + } + + static ImmutableMap<String, String> parseConfiguration(String input) { + if (Strings.isNullOrEmpty(input)) { + return ImmutableMap.of(); + } + return ImmutableMap.copyOf( + Splitter.on(',') + .trimResults() + .withKeyValueSeparator(Splitter.on(':').trimResults()) + .split(input)); + } + + static ConfigurationComparer.Result compareConfigurations( + ImmutableMap<String, String> left, + ImmutableMap<String, String> right) { + Set<String> sharedKeys = Sets.intersection(left.keySet(), right.keySet()); + for (String key : sharedKeys) { + if (!left.get(key).equals(right.get(key))) { + return ConfigurationComparer.Result.DIFFERENT; + } + } + boolean hasLeftOnlyKeys = !Sets.difference(left.keySet(), right.keySet()).isEmpty(); + boolean hasRightOnlyKeys = !Sets.difference(right.keySet(), left.keySet()).isEmpty(); + if (hasLeftOnlyKeys) { + if (hasRightOnlyKeys) { + return ConfigurationComparer.Result.ALL_SHARED_FRAGMENTS_EQUAL; + } else { + return ConfigurationComparer.Result.SUPERSET; + } + } else { + if (hasRightOnlyKeys) { + return ConfigurationComparer.Result.SUBSET; + } else { + return ConfigurationComparer.Result.EQUAL; + } + } + } + + /** Produces a cache suitable for storing TestKeys. */ + static TrimmedConfigurationCache<TestKey, String, ImmutableMap<String, String>> newCache() { + return new TrimmedConfigurationCache<>( + TestKey::descriptor, TestKey::configuration, TestKey::compareConfigurations); + } +}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/trimming/TestKeyTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/trimming/TestKeyTest.java new file mode 100644 index 0000000..ede356f --- /dev/null +++ b/src/test/java/com/google/devtools/build/lib/skyframe/trimming/TestKeyTest.java
@@ -0,0 +1,152 @@ +// Copyright 2018 The Bazel Authors. All rights reserved. +// +// 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.devtools.build.lib.skyframe.trimming; + +import static com.google.common.truth.Truth.assertThat; + +import com.google.common.collect.ImmutableMap; +import com.google.common.testing.EqualsTester; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.JUnit4; + +/** Tests for TestKey's parsing functionality. */ +@RunWith(JUnit4.class) +public final class TestKeyTest { + + @Test + public void parseEmptyConfig() throws Exception { + assertThat(TestKey.parse("<> //foo").configuration()).isEmpty(); + assertThat(TestKey.parse("< > //foo").configuration()).isEmpty(); + assertThat(TestKey.parse(" < > //foo").configuration()).isEmpty(); + } + + @Test + public void parseOneElementConfig() throws Exception { + assertThat(TestKey.parse("<A:1> //foo").configuration()).containsExactly("A", "1"); + assertThat(TestKey.parse("< A : 1 > //foo").configuration()).containsExactly("A", "1"); + assertThat(TestKey.parse(" < A : 1 > //foo").configuration()) + .containsExactly("A", "1"); + } + + @Test + public void parseMultiElementConfig() throws Exception { + assertThat(TestKey.parse("<A:1,B:6,C:90> //foo").configuration()) + .containsExactly("A", "1", "B", "6", "C", "90"); + assertThat(TestKey.parse("< A : 1 , B : 6 , C : 90 > //foo").configuration()) + .containsExactly("A", "1", "B", "6", "C", "90"); + assertThat(TestKey.parse(" < A : 1, B: 6, C :90 > //foo").configuration()) + .containsExactly("A", "1", "B", "6", "C", "90"); + } + + @Test + public void parseConfigWithSpaces() throws Exception { + assertThat(TestKey.parse("<An Item: A Value> //foo").configuration()) + .containsExactly("An Item", "A Value"); + } + + @Test + public void parseDescriptor() throws Exception { + assertThat(TestKey.parse("<>//foo").descriptor()).isEqualTo("//foo"); + assertThat(TestKey.parse("<> //foo ").descriptor()).isEqualTo("//foo"); + assertThat(TestKey.parse(" < A : 1, B: 6, C :90 > //foo ").descriptor()) + .isEqualTo("//foo"); + } + + @Test + public void parseDescriptorWithSpaces() throws Exception { + assertThat(TestKey.parse("<>//foo with space").descriptor()).isEqualTo("//foo with space"); + assertThat(TestKey.parse("<> //foo with space ").descriptor()) + .isEqualTo("//foo with space"); + } + + @Test + public void parseMissingConfiguration() throws Exception { + assertThat(TestKey.parse("<>//foo with space").descriptor()).isEqualTo("//foo with space"); + assertThat(TestKey.parse("<> //foo with space ").descriptor()) + .isEqualTo("//foo with space"); + } + + @Test + public void equality() throws Exception { + new EqualsTester() + .addEqualityGroup( + TestKey.parse("<>//foo"), + TestKey.parse(" < > //foo "), + TestKey.create("//foo", ImmutableMap.of())) + .addEqualityGroup( + TestKey.parse("<A:1>//foo"), + TestKey.parse(" < A : 1 > //foo "), + TestKey.create("//foo", ImmutableMap.of("A", "1"))) + .addEqualityGroup( + TestKey.parse("<>//bar"), + TestKey.parse(" < > //bar "), + TestKey.create("//bar", ImmutableMap.of())) + .addEqualityGroup( + TestKey.parse("<A:1>//bar"), + TestKey.parse(" < A : 1 > //bar "), + TestKey.create("//bar", ImmutableMap.of("A", "1"))) + .testEquals(); + } + + @Test + public void compareConfigurations_EqualCases() throws Exception { + assertThat(TestKey.compareConfigurations(ImmutableMap.of(), ImmutableMap.of())) + .isEqualTo(ConfigurationComparer.Result.EQUAL); + assertThat(TestKey.compareConfigurations(ImmutableMap.of("A", "1"), ImmutableMap.of("A", "1"))) + .isEqualTo(ConfigurationComparer.Result.EQUAL); + } + + @Test + public void compareConfigurations_SubsetCases() throws Exception { + assertThat(TestKey.compareConfigurations(ImmutableMap.of(), ImmutableMap.of("A", "1"))) + .isEqualTo(ConfigurationComparer.Result.SUBSET); + assertThat( + TestKey.compareConfigurations( + ImmutableMap.of("A", "1"), ImmutableMap.of("A", "1", "B", "2"))) + .isEqualTo(ConfigurationComparer.Result.SUBSET); + } + + @Test + public void compareConfigurations_SupersetCases() throws Exception { + assertThat(TestKey.compareConfigurations(ImmutableMap.of("A", "1"), ImmutableMap.of())) + .isEqualTo(ConfigurationComparer.Result.SUPERSET); + assertThat( + TestKey.compareConfigurations( + ImmutableMap.of("A", "1", "B", "2"), ImmutableMap.of("A", "1"))) + .isEqualTo(ConfigurationComparer.Result.SUPERSET); + } + + @Test + public void compareConfigurations_AllSharedFragmentsEqualCases() throws Exception { + assertThat(TestKey.compareConfigurations(ImmutableMap.of("A", "1"), ImmutableMap.of("B", "1"))) + .isEqualTo(ConfigurationComparer.Result.ALL_SHARED_FRAGMENTS_EQUAL); + assertThat( + TestKey.compareConfigurations( + ImmutableMap.of("A", "1", "B", "2"), ImmutableMap.of("A", "1", "C", "3"))) + .isEqualTo(ConfigurationComparer.Result.ALL_SHARED_FRAGMENTS_EQUAL); + } + + @Test + public void compareConfigurations_DifferentCases() throws Exception { + assertThat(TestKey.compareConfigurations(ImmutableMap.of("A", "1"), ImmutableMap.of("A", "2"))) + .isEqualTo(ConfigurationComparer.Result.DIFFERENT); + assertThat( + TestKey.compareConfigurations( + ImmutableMap.of("A", "1", "B", "2", "C", "3"), + ImmutableMap.of("A", "2", "B", "2", "D", "4"))) + .isEqualTo(ConfigurationComparer.Result.DIFFERENT); + } +}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/trimming/TrimmedConfigurationCacheTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/trimming/TrimmedConfigurationCacheTest.java new file mode 100644 index 0000000..e3ae994 --- /dev/null +++ b/src/test/java/com/google/devtools/build/lib/skyframe/trimming/TrimmedConfigurationCacheTest.java
@@ -0,0 +1,401 @@ +// Copyright 2018 The Bazel Authors. All rights reserved. +// +// 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.devtools.build.lib.skyframe.trimming; + +import static com.google.common.truth.Truth.assertThat; +import static com.google.common.truth.Truth8.assertThat; + +import com.google.common.collect.ImmutableMap; +import org.junit.Before; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.JUnit4; + +/** Tests for the TrimmedConfigurationCache. */ +@RunWith(JUnit4.class) +public final class TrimmedConfigurationCacheTest { + + private TrimmedConfigurationCache<TestKey, String, ImmutableMap<String, String>> cache; + + @Before + public void initializeCache() { + cache = TestKey.newCache(); + } + + @Test + public void get_onFreshCache_returnsEmpty() throws Exception { + assertThat(cache.get(TestKey.parse("<A: 1> //foo"))).isEmpty(); + } + + @Test + public void get_afterAddingSubsetCacheEntry_returnsMatchingValue() throws Exception { + TestKey canonicalKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(canonicalKey, TestKey.parseConfiguration("A: 1")); + + assertThat(cache.get(TestKey.parse("<A: 1, C: 1> //foo"))).hasValue(canonicalKey); + } + + @Test + public void get_afterRemovingMatchingCacheEntry_returnsEmpty() throws Exception { + TestKey canonicalKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(canonicalKey, TestKey.parseConfiguration("A: 1")); + cache.remove(canonicalKey); + + assertThat(cache.get(TestKey.parse("<A: 1, B: 2> //foo"))).isEmpty(); + } + + @Test + public void get_afterRemovingCacheEntryWithDifferentConfig_returnsOriginalKey() throws Exception { + TestKey canonicalKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(canonicalKey, TestKey.parseConfiguration("A: 1")); + TestKey removedOtherKey = TestKey.parse("<A: 1, B: 2> //foo"); + cache.remove(removedOtherKey); + + assertThat(cache.get(canonicalKey)).hasValue(canonicalKey); + } + + @Test + public void get_afterRemovingCacheEntryWithDifferentDescriptor_returnsOriginalKey() + throws Exception { + TestKey canonicalKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(canonicalKey, TestKey.parseConfiguration("A: 1")); + TestKey removedOtherKey = TestKey.parse("<A: 1, B: 1> //bar"); + cache.remove(removedOtherKey); + + assertThat(cache.get(canonicalKey)).hasValue(canonicalKey); + } + + @Test + public void get_afterClearingMatchingCacheEntry_returnsEmpty() throws Exception { + cache.putIfAbsent(TestKey.parse("<A: 1, B: 1> //foo"), TestKey.parseConfiguration("A: 1")); + cache.clear(); + + assertThat(cache.get(TestKey.parse("<A: 1, B: 2> //foo"))).isEmpty(); + } + + @Test + public void get_afterRemovingAndReAddingCacheEntry_returnsNewValue() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedConfiguration = TestKey.parseConfiguration("A: 1"); + cache.putIfAbsent(oldKey, trimmedConfiguration); + cache.remove(oldKey); + TestKey newKey = TestKey.parse("<A: 1, C: 1> //foo"); + cache.putIfAbsent(newKey, trimmedConfiguration); + + assertThat(cache.get(TestKey.parse("<A: 1, D: 1> //foo"))).hasValue(newKey); + } + + @Test + public void get_afterAddingMatchingConfigurationForDifferentDescriptor_returnsEmpty() + throws Exception { + cache.putIfAbsent(TestKey.parse("<A: 1, B: 1> //bar"), TestKey.parseConfiguration("A: 1")); + + assertThat(cache.get(TestKey.parse("<A: 1, B: 1> //foo"))).isEmpty(); + } + + @Test + public void get_afterAddingNonMatchingConfigurationForSameDescriptor_returnsEmpty() + throws Exception { + cache.putIfAbsent(TestKey.parse("<A: 1, B: 1> //foo"), TestKey.parseConfiguration("A: 1")); + + assertThat(cache.get(TestKey.parse("<A: 2, B: 1> //foo"))).isEmpty(); + } + + @Test + public void get_afterAddingAndInvalidatingMatchingCacheEntry_returnsEmpty() throws Exception { + TestKey canonicalKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(canonicalKey, TestKey.parseConfiguration("A: 1")); + cache.invalidate(canonicalKey); + + assertThat(cache.get(TestKey.parse("<A: 1, C: 1> //foo"))).isEmpty(); + } + + @Test + public void get_afterAddingAndInvalidatingAndReAddingMatchingCacheEntry_returnsOriginalValue() + throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedConfiguration = TestKey.parseConfiguration("A: 1"); + cache.putIfAbsent(oldKey, trimmedConfiguration); + cache.invalidate(oldKey); + TestKey newKey = TestKey.parse("<A: 1, C: 1> //foo"); + cache.putIfAbsent(newKey, trimmedConfiguration); + + assertThat(cache.get(TestKey.parse("<A: 1, D: 1> //foo"))).hasValue(oldKey); + } + + @Test + public void get_afterAddingAndInvalidatingAndRevalidatingMatchingCacheEntry_returnsOriginalValue() + throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedConfiguration = TestKey.parseConfiguration("A: 1"); + cache.putIfAbsent(oldKey, trimmedConfiguration); + cache.invalidate(oldKey); + cache.revalidate(oldKey); + + assertThat(cache.get(TestKey.parse("<A: 1, D: 1> //foo"))).hasValue(oldKey); + } + + @Test + public void get_afterMovingKeyToDifferentTrimming_returnsEmpty() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(oldKey, TestKey.parseConfiguration("A: 1")); + cache.invalidate(oldKey); + cache.putIfAbsent(oldKey, TestKey.parseConfiguration("B: 1")); + + assertThat(cache.get(TestKey.parse("<A: 1, B: 2> //foo"))).isEmpty(); + } + + @Test(expected = IllegalArgumentException.class) + public void putIfAbsent_forNonSubsetConfiguration_throwsIllegalArgumentException() + throws Exception { + cache.putIfAbsent(TestKey.parse("<A: 1> //foo"), TestKey.parseConfiguration("A: 2")); + } + + @Test + public void putIfAbsent_onFreshCache_returnsInputKey() throws Exception { + TestKey inputKey = TestKey.parse("<A: 1, B: 1> //foo"); + + assertThat(cache.putIfAbsent(inputKey, TestKey.parseConfiguration("A: 1"))).isEqualTo(inputKey); + } + + @Test + public void putIfAbsent_afterRemoving_returnsNewKey() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedConfiguration = TestKey.parseConfiguration("A: 1"); + cache.putIfAbsent(oldKey, trimmedConfiguration); + cache.remove(oldKey); + TestKey newKey = TestKey.parse("<A: 1, B: 2> //foo"); + + assertThat(cache.putIfAbsent(newKey, trimmedConfiguration)).isEqualTo(newKey); + } + + @Test + public void putIfAbsent_afterAddingEqualConfigurationForDifferentDescriptor_returnsInputKey() + throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedConfiguration = TestKey.parseConfiguration("A: 1"); + cache.putIfAbsent(oldKey, trimmedConfiguration); + TestKey newKey = TestKey.parse("<A: 1, B: 1> //bar"); + + assertThat(cache.putIfAbsent(newKey, trimmedConfiguration)).isEqualTo(newKey); + } + + @Test + public void putIfAbsent_afterAddingNonEqualConfigurationForSameDescriptor_returnsInputKey() + throws Exception { + cache.putIfAbsent(TestKey.parse("<A: 1, B: 1> //foo"), TestKey.parseConfiguration("A: 1")); + TestKey newKey = TestKey.parse("<A: 2, B: 2> //foo"); + + assertThat(cache.putIfAbsent(newKey, TestKey.parseConfiguration("A: 2"))).isEqualTo(newKey); + } + + @Test + public void putIfAbsent_afterAddingEqualConfigurationForSameDescriptor_returnsOriginalKey() + throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedConfiguration = TestKey.parseConfiguration("A: 1"); + cache.putIfAbsent(oldKey, trimmedConfiguration); + + assertThat(cache.putIfAbsent(TestKey.parse("<A: 1, B: 2> //foo"), trimmedConfiguration)) + .isEqualTo(oldKey); + } + + @Test + public void putIfAbsent_afterInvalidatingEqualEntry_returnsOriginalKey() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedConfiguration = TestKey.parseConfiguration("A: 1"); + cache.putIfAbsent(oldKey, trimmedConfiguration); + cache.invalidate(oldKey); + + assertThat(cache.putIfAbsent(TestKey.parse("<A: 1, B: 2> //foo"), trimmedConfiguration)) + .isEqualTo(oldKey); + } + + @Test + public void putIfAbsent_forKeyAssociatedWithDifferentTrimming_returnsOldKey() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(oldKey, TestKey.parseConfiguration("A: 1")); + cache.invalidate(oldKey); + + assertThat(cache.putIfAbsent(oldKey, TestKey.parseConfiguration("B: 1"))).isEqualTo(oldKey); + } + + @Test + public void putIfAbsent_afterMovingPreviousAssociatedKeyToNewTrimming_returnsNewKey() + throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedA1 = TestKey.parseConfiguration("A: 1"); + ImmutableMap<String, String> trimmedB1 = TestKey.parseConfiguration("B: 1"); + cache.putIfAbsent(oldKey, trimmedA1); + cache.invalidate(oldKey); + cache.putIfAbsent(oldKey, trimmedB1); + cache.invalidate(oldKey); + TestKey newKey = TestKey.parse("<A: 1, B: 2> //foo"); + + // This is testing that oldKey is not still associated with trimmedA1, because now it's + // associated with trimmedB1 instead. + assertThat(cache.putIfAbsent(newKey, trimmedA1)).isEqualTo(newKey); + } + + @Test + public void putIfAbsent_afterInvalidatingAndReAddingEqualEntry_returnsOriginalKey() + throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedConfiguration = TestKey.parseConfiguration("A: 1"); + cache.putIfAbsent(oldKey, trimmedConfiguration); + cache.invalidate(oldKey); + cache.putIfAbsent(TestKey.parse("<A: 1, B: 2> //foo"), trimmedConfiguration); + + assertThat(cache.putIfAbsent(TestKey.parse("<A: 1, B: 3> //foo"), trimmedConfiguration)) + .isEqualTo(oldKey); + } + + @Test + public void putIfAbsent_afterInvalidatingAndRevalidatingEqualEntry_returnsOriginalKey() + throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedConfiguration = TestKey.parseConfiguration("A: 1"); + cache.putIfAbsent(oldKey, trimmedConfiguration); + cache.invalidate(oldKey); + cache.revalidate(oldKey); + + assertThat(cache.putIfAbsent(TestKey.parse("<A: 1, B: 2> //foo"), trimmedConfiguration)) + .isEqualTo(oldKey); + } + + @Test + public void putIfAbsent_afterAddingAndInvalidatingSubsetConfiguration_returnsInputKey() + throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + ImmutableMap<String, String> trimmedConfiguration = TestKey.parseConfiguration("A: 1"); + cache.putIfAbsent(oldKey, trimmedConfiguration); + cache.invalidate(oldKey); + TestKey newKey = TestKey.parse("<A: 1, B: 2> //foo"); + + assertThat(cache.putIfAbsent(newKey, TestKey.parseConfiguration("A: 1, B: 2"))) + .isEqualTo(newKey); + } + + @Test + public void putIfAbsent_afterAddingAndInvalidatingSupersetConfiguration_returnsInputKey() + throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1, C: 1> //foo"); + cache.putIfAbsent(oldKey, TestKey.parseConfiguration("A: 1, B: 1")); + cache.invalidate(oldKey); + TestKey newKey = TestKey.parse("<A: 1, B: 1, C: 2> //foo"); + + assertThat(cache.putIfAbsent(newKey, TestKey.parseConfiguration("A: 1"))).isEqualTo(newKey); + } + + @Test + public void invalidate_onEntryNotInCache_doesNotThrow() throws Exception { + // Expect no exception here. + cache.invalidate(TestKey.parse("<A: 1> //foo")); + } + + @Test + public void invalidate_onAlreadyInvalidatedEntry_doesNotThrow() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(oldKey, TestKey.parseConfiguration("A: 1")); + cache.invalidate(oldKey); + + // Expect no exception here. + cache.invalidate(oldKey); + } + + @Test + public void invalidate_onRemovedEntry_doesNotThrow() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(oldKey, TestKey.parseConfiguration("A: 1")); + cache.remove(oldKey); + + // Expect no exception here. + cache.invalidate(oldKey); + } + + @Test + public void revalidate_onEntryNotInCache_doesNotThrow() throws Exception { + // Expect no exception here. + cache.revalidate(TestKey.parse("<A: 1> //foo")); + } + + @Test + public void revalidate_onAlreadyInvalidatedAndRevalidatedEntry_doesNotThrow() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(oldKey, TestKey.parseConfiguration("A: 1")); + cache.invalidate(oldKey); + cache.revalidate(oldKey); + + // Expect no exception here. + cache.revalidate(oldKey); + } + + @Test + public void revalidate_onRemovedEntry_doesNotThrow() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(oldKey, TestKey.parseConfiguration("A: 1")); + cache.remove(oldKey); + + // Expect no exception here. + cache.revalidate(oldKey); + } + + @Test + public void remove_onEntryNotInCache_doesNotThrow() throws Exception { + // Expect no exception here. + cache.remove(TestKey.parse("<A: 1> //foo")); + } + + @Test + public void remove_onAlreadyInvalidatedEntry_doesNotThrow() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(oldKey, TestKey.parseConfiguration("A: 1")); + cache.invalidate(oldKey); + + // Expect no exception here. + cache.remove(oldKey); + } + + @Test + public void remove_onEntryWithDifferentConfiguration_doesNotThrow() throws Exception { + cache.putIfAbsent(TestKey.parse("<A: 1, B: 1> //foo"), TestKey.parseConfiguration("A: 1")); + + // Expect no exception here. + cache.remove(TestKey.parse("<A: 1, B: 2> //foo")); + } + + @Test + public void remove_onEntryWithDifferentDescriptor_doesNotThrow() throws Exception { + cache.putIfAbsent(TestKey.parse("<A: 1, B: 1> //foo"), TestKey.parseConfiguration("A: 1")); + + // Expect no exception here. + cache.remove(TestKey.parse("<A: 1, B: 1> //bar")); + } + + @Test + public void remove_onRemovedEntry_doesNotThrow() throws Exception { + TestKey oldKey = TestKey.parse("<A: 1, B: 1> //foo"); + cache.putIfAbsent(oldKey, TestKey.parseConfiguration("A: 1")); + cache.remove(oldKey); + + // Expect no exception here. + cache.remove(oldKey); + } + + @Test + public void clear_onEmptyCache_doesNotThrow() throws Exception { + cache.clear(); + } +}