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();
+  }
+}