Use `ClassToInstanceMap` for serialization dependencies.

Serialization deps are mappings from a class to an instance of that class. Using `ClassToInstanceMap` provides compile-time enforcement that the value is in fact an instance of the key.

Also use `checkNotNull` in `getDependency` to throw when a dependency is not present, so that callers don't have to check.

PiperOrigin-RevId: 369249742
diff --git a/src/main/java/com/google/devtools/build/lib/packages/NativeAspectClass.java b/src/main/java/com/google/devtools/build/lib/packages/NativeAspectClass.java
index 6386ea8..b57532b 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/NativeAspectClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/NativeAspectClass.java
@@ -49,8 +49,7 @@
     public void serialize(
         SerializationContext context, NativeAspectClass obj, CodedOutputStream codedOut)
         throws SerializationException, IOException {
-      RuleClassProvider ruleClassProvider =
-          Preconditions.checkNotNull(context.getDependency(RuleClassProvider.class), obj);
+      RuleClassProvider ruleClassProvider = context.getDependency(RuleClassProvider.class);
       NativeAspectClass storedAspect = ruleClassProvider.getNativeAspectClass(obj.getKey());
       Preconditions.checkState(
           obj == storedAspect, "Not stored right: %s %s %s", obj, storedAspect, ruleClassProvider);
@@ -62,8 +61,7 @@
         throws SerializationException, IOException {
       String aspectKey = context.deserialize(codedIn);
       return Preconditions.checkNotNull(
-          Preconditions.checkNotNull(context.getDependency(RuleClassProvider.class), aspectKey)
-              .getNativeAspectClass(aspectKey),
+          context.getDependency(RuleClassProvider.class).getNativeAspectClass(aspectKey),
           aspectKey);
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContext.java
index e8b156d..917fcf7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContext.java
@@ -14,9 +14,10 @@
 
 package com.google.devtools.build.lib.skyframe.serialization;
 
+import static com.google.common.base.Preconditions.checkNotNull;
+
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.devtools.build.lib.skyframe.serialization.Memoizer.Deserializer;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec.MemoizationStrategy;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodecRegistry.CodecDescriptor;
@@ -33,12 +34,12 @@
  */
 public class DeserializationContext {
   private final ObjectCodecRegistry registry;
-  private final ImmutableMap<Class<?>, Object> dependencies;
+  private final ImmutableClassToInstanceMap<Object> dependencies;
   private final Memoizer.Deserializer deserializer;
 
   private DeserializationContext(
       ObjectCodecRegistry registry,
-      ImmutableMap<Class<?>, Object> dependencies,
+      ImmutableClassToInstanceMap<Object> dependencies,
       Deserializer deserializer) {
     this.registry = registry;
     this.dependencies = dependencies;
@@ -47,12 +48,12 @@
 
   @VisibleForTesting
   public DeserializationContext(
-      ObjectCodecRegistry registry, ImmutableMap<Class<?>, Object> dependencies) {
+      ObjectCodecRegistry registry, ImmutableClassToInstanceMap<Object> dependencies) {
     this(registry, dependencies, /*deserializer=*/ null);
   }
 
   @VisibleForTesting
-  public DeserializationContext(ImmutableMap<Class<?>, Object> dependencies) {
+  public DeserializationContext(ImmutableClassToInstanceMap<Object> dependencies) {
     this(AutoRegistry.get(), dependencies);
   }
 
@@ -112,8 +113,7 @@
   }
 
   public <T> T getDependency(Class<T> type) {
-    Preconditions.checkNotNull(type);
-    return type.cast(dependencies.get(type));
+    return checkNotNull(dependencies.getInstance(type), "Missing dependency of type %s", type);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecs.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecs.java
index 9667d23..fe28d03 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecs.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecs.java
@@ -15,7 +15,7 @@
 package com.google.devtools.build.lib.skyframe.serialization;
 
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.protobuf.ByteString;
 import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
@@ -34,13 +34,13 @@
    * ObjectCodec}s.
    */
   public ObjectCodecs(
-      ObjectCodecRegistry codecRegistry, ImmutableMap<Class<?>, Object> dependencies) {
+      ObjectCodecRegistry codecRegistry, ImmutableClassToInstanceMap<Object> dependencies) {
     serializationContext = new SerializationContext(codecRegistry, dependencies);
     deserializationContext = new DeserializationContext(codecRegistry, dependencies);
   }
 
   public ObjectCodecs(ObjectCodecRegistry codecRegistry) {
-    this(codecRegistry, ImmutableMap.of());
+    this(codecRegistry, ImmutableClassToInstanceMap.of());
   }
 
   @VisibleForTesting
@@ -131,7 +131,7 @@
   }
 
   @FunctionalInterface
-  private static interface SerializeCall {
+  private interface SerializeCall {
     void serialize(Object subject, CodedOutputStream codedOut) throws SerializationException;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContext.java
index 6c93486..9466e76 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContext.java
@@ -14,9 +14,11 @@
 
 package com.google.devtools.build.lib.skyframe.serialization;
 
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.util.concurrent.FutureCallback;
 import com.google.common.util.concurrent.Futures;
@@ -43,7 +45,7 @@
  */
 public class SerializationContext {
   private final ObjectCodecRegistry registry;
-  private final ImmutableMap<Class<?>, Object> dependencies;
+  private final ImmutableClassToInstanceMap<Object> dependencies;
   @Nullable private final Memoizer.Serializer serializer;
   private final Set<Class<?>> explicitlyAllowedClasses;
   /** Initialized lazily. */
@@ -53,7 +55,7 @@
 
   private SerializationContext(
       ObjectCodecRegistry registry,
-      ImmutableMap<Class<?>, Object> dependencies,
+      ImmutableClassToInstanceMap<Object> dependencies,
       @Nullable Serializer serializer,
       boolean allowFuturesToBlockWritingOn) {
     this.registry = registry;
@@ -65,12 +67,12 @@
 
   @VisibleForTesting
   public SerializationContext(
-      ObjectCodecRegistry registry, ImmutableMap<Class<?>, Object> dependencies) {
+      ObjectCodecRegistry registry, ImmutableClassToInstanceMap<Object> dependencies) {
     this(registry, dependencies, /*serializer=*/ null, /*allowFuturesToBlockWritingOn=*/ false);
   }
 
   @VisibleForTesting
-  public SerializationContext(ImmutableMap<Class<?>, Object> dependencies) {
+  public SerializationContext(ImmutableClassToInstanceMap<Object> dependencies) {
     this(AutoRegistry.get(), dependencies);
   }
 
@@ -106,10 +108,8 @@
     }
   }
 
-  @SuppressWarnings("unchecked")
   public <T> T getDependency(Class<T> type) {
-    Preconditions.checkNotNull(type);
-    return (T) dependencies.get(type);
+    return checkNotNull(dependencies.getInstance(type), "Missing dependency of type %s", type);
   }
 
   /**
@@ -132,10 +132,8 @@
 
   @CheckReturnValue
   SerializationContext getMemoizingAndBlockingOnWriteContext() {
-    Preconditions.checkState(
-        serializer == null, "Should only be called on base serializationContext");
-    Preconditions.checkState(
-        !allowFuturesToBlockWritingOn, "Should only be called on base serializationContext");
+    checkState(serializer == null, "Should only be called on base serializationContext");
+    checkState(!allowFuturesToBlockWritingOn, "Should only be called on base serializationContext");
     return getNewMemoizingContext(/*allowFuturesToBlockWritingOn=*/ true);
   }
 
@@ -165,7 +163,7 @@
    */
   public void addFutureToBlockWritingOn(
       ListenableFuture<Void> future, FutureCallback<Void> crashTerminatingCallback) {
-    Preconditions.checkState(allowFuturesToBlockWritingOn, "This context cannot block on a future");
+    checkState(allowFuturesToBlockWritingOn, "This context cannot block on a future");
     if (futuresToBlockWritingOn == null) {
       futuresToBlockWritingOn = new ArrayList<>();
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/ObjectCodecTester.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/ObjectCodecTester.java
index 62f9392..4969cb4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/ObjectCodecTester.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/ObjectCodecTester.java
@@ -19,8 +19,8 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.base.Stopwatch;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.flogger.GoogleLogger;
 import com.google.devtools.build.lib.skyframe.serialization.DeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
@@ -138,8 +138,8 @@
   public static class Builder<T> {
     private final ObjectCodec<T> underTest;
     private final ImmutableList.Builder<T> subjectsBuilder = ImmutableList.builder();
-    private final ImmutableMap.Builder<Class<?>, Object> dependenciesBuilder =
-        ImmutableMap.builder();
+    private final ImmutableClassToInstanceMap.Builder<Object> dependenciesBuilder =
+        ImmutableClassToInstanceMap.builder();
     private boolean skipBadDataTest = false;
     private VerificationFunction<T> verificationFunction =
         (original, deserialized) -> assertThat(deserialized).isEqualTo(original);
@@ -201,7 +201,7 @@
      * individually.
      */
     ObjectCodecTester<T> build() {
-      ImmutableMap<Class<?>, Object> dependencies = dependenciesBuilder.build();
+      ImmutableClassToInstanceMap<Object> dependencies = dependenciesBuilder.build();
       return new ObjectCodecTester<>(
           underTest,
           subjectsBuilder.build(),
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializationDepsUtils.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializationDepsUtils.java
index 5d829b9..3396224 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializationDepsUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializationDepsUtils.java
@@ -13,7 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe.serialization.testutils;
 
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SourceArtifact;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -32,8 +32,9 @@
 public class SerializationDepsUtils {
 
   /** Default serialization dependencies for testing. */
-  public static final ImmutableMap<Class<?>, Object> SERIALIZATION_DEPS_FOR_TEST =
-      ImmutableMap.of(ArtifactResolverSupplier.class, new ArtifactResolverSupplierForTest());
+  public static final ImmutableClassToInstanceMap<?> SERIALIZATION_DEPS_FOR_TEST =
+      ImmutableClassToInstanceMap.of(
+          ArtifactResolverSupplier.class, new ArtifactResolverSupplierForTest());
 
   /**
    * An {@link ArtifactResolverSupplier} that calls directly into the {@link SourceArtifact}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializationTester.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializationTester.java
index 66179d8..0022d66 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializationTester.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializationTester.java
@@ -19,8 +19,9 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.base.Stopwatch;
+import com.google.common.collect.ClassToInstanceMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.flogger.GoogleLogger;
 import com.google.devtools.build.lib.skyframe.serialization.AutoRegistry;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
@@ -28,10 +29,7 @@
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodecs;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.protobuf.ByteString;
-import com.google.protobuf.InvalidProtocolBufferException;
-import java.io.IOException;
 import java.util.ArrayList;
-import java.util.Map;
 import java.util.Random;
 
 /**
@@ -58,7 +56,8 @@
   }
 
   private final ImmutableList<?> subjects;
-  private final ImmutableMap.Builder<Class<?>, Object> dependenciesBuilder;
+  private final ImmutableClassToInstanceMap.Builder<Object> dependenciesBuilder =
+      ImmutableClassToInstanceMap.builder();
   private final ArrayList<ObjectCodec<?>> additionalCodecs = new ArrayList<>();
   private boolean memoize;
   private boolean allowFutureBlocking;
@@ -77,7 +76,6 @@
   public SerializationTester(ImmutableList<?> subjects) {
     Preconditions.checkArgument(!subjects.isEmpty());
     this.subjects = subjects;
-    this.dependenciesBuilder = ImmutableMap.builder();
   }
 
   public <D> SerializationTester addDependency(Class<? super D> type, D dependency) {
@@ -85,7 +83,7 @@
     return this;
   }
 
-  public SerializationTester addDependencies(Map<Class<?>, Object> dependencies) {
+  public SerializationTester addDependencies(ClassToInstanceMap<?> dependencies) {
     dependenciesBuilder.putAll(dependencies);
     return this;
   }
@@ -154,7 +152,7 @@
 
   private ObjectCodecs createObjectCodecs() {
     ObjectCodecRegistry registry = AutoRegistry.get();
-    ImmutableMap<Class<?>, Object> dependencies = dependenciesBuilder.build();
+    ImmutableClassToInstanceMap<Object> dependencies = dependenciesBuilder.build();
     ObjectCodecRegistry.Builder registryBuilder = registry.getBuilder();
     for (Object val : dependencies.values()) {
       registryBuilder.addReferenceConstant(val);
@@ -178,7 +176,7 @@
   }
 
   private Object deserialize(ByteString serialized, ObjectCodecs codecs)
-      throws SerializationException, IOException {
+      throws SerializationException {
     if (memoize) {
       return codecs.deserializeMemoized(serialized);
     } else {
@@ -205,8 +203,7 @@
   }
 
   /** Runs serialized bytes stability tests. */
-  private void testStableSerialization(ObjectCodecs codecs)
-      throws SerializationException, IOException {
+  private void testStableSerialization(ObjectCodecs codecs) throws SerializationException {
     for (Object subject : subjects) {
       ByteString serialized = serialize(subject, codecs);
       Object deserialized = deserialize(serialized, codecs);
@@ -216,7 +213,7 @@
   }
 
   /** Runs junk-data recognition tests. */
-  private void testDeserializeJunkData(ObjectCodecs codecs) throws IOException {
+  private void testDeserializeJunkData(ObjectCodecs codecs) {
     Random rng = new Random(0);
     for (int i = 0; i < DEFAULT_JUNK_INPUTS; ++i) {
       byte[] junkData = new byte[rng.nextInt(JUNK_LENGTH_UPPER_BOUND)];
@@ -224,7 +221,7 @@
       try {
         deserialize(ByteString.copyFrom(junkData), codecs);
         // OK. Junk string was coincidentally parsed.
-      } catch (SerializationException | InvalidProtocolBufferException e) {
+      } catch (SerializationException e) {
         // OK. Deserialization of junk failed.
         return;
       }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/TestUtils.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/TestUtils.java
index effb474..bffa8a5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/TestUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/TestUtils.java
@@ -16,7 +16,7 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.devtools.build.lib.skyframe.serialization.AutoRegistry;
 import com.google.devtools.build.lib.skyframe.serialization.DeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
@@ -29,9 +29,7 @@
 import com.google.protobuf.CodedOutputStream;
 import java.io.ByteArrayOutputStream;
 import java.io.IOException;
-import javax.annotation.Nullable;
 import net.starlark.java.eval.Module;
-import net.starlark.java.eval.Mutability;
 
 /** Helpers for serialization tests. */
 public class TestUtils {
@@ -48,11 +46,6 @@
     return bytes.toByteArray();
   }
 
-  public static <T> ByteString toBytes(T value, ImmutableMap<Class<?>, Object> dependencies)
-      throws IOException, SerializationException {
-    return toBytes(new SerializationContext(dependencies), value);
-  }
-
   public static <T> ByteString toBytes(SerializationContext serializationContext, T value)
       throws IOException, SerializationException {
     ByteString.Output output = ByteString.newOutput();
@@ -75,12 +68,13 @@
 
   public static <T> T roundTrip(T value, ObjectCodecRegistry registry)
       throws IOException, SerializationException {
-    return new DeserializationContext(registry, ImmutableMap.of())
+    return new DeserializationContext(registry, ImmutableClassToInstanceMap.of())
         .deserialize(
-            toBytes(new SerializationContext(registry, ImmutableMap.of()), value).newCodedInput());
+            toBytes(new SerializationContext(registry, ImmutableClassToInstanceMap.of()), value)
+                .newCodedInput());
   }
 
-  public static <T> T roundTrip(T value, ImmutableMap<Class<?>, Object> dependencies)
+  public static <T> T roundTrip(T value, ImmutableClassToInstanceMap<Object> dependencies)
       throws IOException, SerializationException {
     ObjectCodecRegistry.Builder builder = AutoRegistry.get().getBuilder();
     for (Object constant : dependencies.values()) {
@@ -93,7 +87,7 @@
   }
 
   public static <T> T roundTrip(T value) throws IOException, SerializationException {
-    return TestUtils.roundTrip(value, ImmutableMap.of());
+    return TestUtils.roundTrip(value, ImmutableClassToInstanceMap.of());
   }
 
   /**
@@ -118,7 +112,7 @@
   }
 
   public static Object fromBytesMemoized(ByteString bytes, ObjectCodecRegistry registry)
-      throws IOException, SerializationException {
+      throws SerializationException {
     return new ObjectCodecs(registry).deserializeMemoized(bytes.newCodedInput());
   }
 
@@ -135,12 +129,6 @@
     return roundTripMemoized(original, getBuilderWithAdditionalCodecs(codecs).build());
   }
 
-  public static <T> T roundTripMemoized(
-      T original, @Nullable Mutability mutability, ObjectCodec<?>... codecs)
-      throws IOException, SerializationException {
-    return roundTripMemoized(original, getBuilderWithAdditionalCodecs(codecs).build());
-  }
-
   public static ObjectCodecRegistry.Builder getBuilderWithAdditionalCodecs(
       ObjectCodec<?>... codecs) {
     ObjectCodecRegistry.Builder builder = AutoRegistry.get().getBuilder();
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ArtifactRootTest.java b/src/test/java/com/google/devtools/build/lib/actions/ArtifactRootTest.java
index a343551..1e0ccc6 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ArtifactRootTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ArtifactRootTest.java
@@ -16,7 +16,7 @@
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.assertThrows;
 
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.testing.EqualsTester;
 import com.google.devtools.build.lib.actions.ArtifactRoot.RootType;
 import com.google.devtools.build.lib.skyframe.serialization.AutoRegistry;
@@ -178,8 +178,8 @@
     ArtifactRoot derivedRoot =
         ArtifactRoot.asDerivedRoot(execRoot, RootType.Output, "first", "second", "third");
     ObjectCodecRegistry registry = AutoRegistry.get();
-    ImmutableMap<Class<?>, Object> dependencies =
-        ImmutableMap.<Class<?>, Object>builder()
+    ImmutableClassToInstanceMap<Object> dependencies =
+        ImmutableClassToInstanceMap.builder()
             .put(FileSystem.class, scratch.getFileSystem())
             .put(
                 Root.RootCodecDependencies.class,
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java b/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
index b9d2ed2..66dd3b5d 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
@@ -17,7 +17,7 @@
 import static org.junit.Assert.assertThrows;
 import static org.mockito.Mockito.mock;
 
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.Lists;
 import com.google.common.testing.EqualsTester;
 import com.google.devtools.build.lib.actions.Artifact.ArchivedTreeArtifact;
@@ -324,7 +324,7 @@
                 .addReferenceConstant(scratch.getFileSystem())
                 .setAllowDefaultCodec(true)
                 .build(),
-            ImmutableMap.<Class<?>, Object>builder()
+            ImmutableClassToInstanceMap.builder()
                 .put(FileSystem.class, scratch.getFileSystem())
                 .put(ArtifactResolverSupplier.class, artifactResolverSupplierForTest)
                 .put(
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/config/BuildOptionsTest.java b/src/test/java/com/google/devtools/build/lib/analysis/config/BuildOptionsTest.java
index 82eaffd..c403563 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/config/BuildOptionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/config/BuildOptionsTest.java
@@ -16,6 +16,7 @@
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.assertThrows;
 
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
@@ -29,9 +30,12 @@
 import com.google.devtools.build.lib.rules.java.JavaOptions;
 import com.google.devtools.build.lib.rules.proto.ProtoConfiguration;
 import com.google.devtools.build.lib.rules.python.PythonOptions;
+import com.google.devtools.build.lib.skyframe.serialization.SerializationContext;
+import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.TestUtils;
 import com.google.devtools.common.options.OptionsParser;
 import com.google.protobuf.ByteString;
+import java.io.IOException;
 import java.util.AbstractMap;
 import java.util.stream.Collectors;
 import org.junit.Test;
@@ -345,16 +349,8 @@
     OptionsDiffForReconstruction diff1 = BuildOptions.diffForReconstruction(one, two);
     OptionsDiffForReconstruction diff2 = BuildOptions.diffForReconstruction(one, two);
     assertThat(diff2).isEqualTo(diff1);
-    assertThat(
-            TestUtils.toBytes(
-                diff2,
-                ImmutableMap.of(
-                    BuildOptions.OptionsDiffCache.class, new BuildOptions.DiffToByteCache())))
-        .isEqualTo(
-            TestUtils.toBytes(
-                diff1,
-                ImmutableMap.of(
-                    BuildOptions.OptionsDiffCache.class, new BuildOptions.DiffToByteCache())));
+    assertThat(toBytes(diff2, new BuildOptions.DiffToByteCache()))
+        .isEqualTo(toBytes(diff1, new BuildOptions.DiffToByteCache()));
   }
 
   @Test
@@ -363,9 +359,7 @@
     BuildOptions two = BuildOptions.of(BUILD_CONFIG_OPTIONS, "--compilation_mode=dbg", "cpu=k8");
     OptionsDiffForReconstruction diff = BuildOptions.diffForReconstruction(one, two);
     BuildOptions.OptionsDiffCache cache = new BuildOptions.FingerprintingKDiffToByteStringCache();
-    assertThat(TestUtils.toBytes(diff, ImmutableMap.of(BuildOptions.OptionsDiffCache.class, cache)))
-        .isEqualTo(
-            TestUtils.toBytes(diff, ImmutableMap.of(BuildOptions.OptionsDiffCache.class, cache)));
+    assertThat(toBytes(diff, cache)).isEqualTo(toBytes(diff, cache));
   }
 
   @Test
@@ -599,4 +593,13 @@
     diff.clearCachedReconstructedForTesting();
     return diff;
   }
+
+  private static ByteString toBytes(
+      OptionsDiffForReconstruction diff, BuildOptions.OptionsDiffCache cache)
+      throws IOException, SerializationException {
+    return TestUtils.toBytes(
+        new SerializationContext(
+            ImmutableClassToInstanceMap.of(BuildOptions.OptionsDiffCache.class, cache)),
+        diff);
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java
index 9489d69..dde6f8d 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTest.java
@@ -23,7 +23,7 @@
 import static org.mockito.Mockito.times;
 import static org.mockito.Mockito.when;
 
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.testing.GcFinalization;
 import com.google.common.util.concurrent.ListenableFuture;
 import com.google.common.util.concurrent.MoreExecutors;
@@ -59,7 +59,8 @@
   public void testAutoCodecedCodec() throws Exception {
     ObjectCodecs objectCodecs =
         new ObjectCodecs(
-            AutoRegistry.get().getBuilder().setAllowDefaultCodec(true).build(), ImmutableMap.of());
+            AutoRegistry.get().getBuilder().setAllowDefaultCodec(true).build(),
+            ImmutableClassToInstanceMap.of());
     NestedSetCodecTestUtils.checkCodec(objectCodecs, false, false);
   }
 
@@ -472,6 +473,6 @@
             .setAllowDefaultCodec(true)
             .add(new NestedSetCodecWithStore(store))
             .build(),
-        /*dependencies=*/ ImmutableMap.of());
+        /*dependencies=*/ ImmutableClassToInstanceMap.of());
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/packages/ThrowingRuleCodecTest.java b/src/test/java/com/google/devtools/build/lib/packages/ThrowingRuleCodecTest.java
index 0e1a260..70dbd3e 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/ThrowingRuleCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/ThrowingRuleCodecTest.java
@@ -16,7 +16,7 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
 import com.google.devtools.build.lib.skyframe.serialization.AutoRegistry;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodecs;
@@ -36,7 +36,8 @@
 
     ObjectCodecs objectCodecs =
         new ObjectCodecs(
-            AutoRegistry.get().getBuilder().setAllowDefaultCodec(true).build(), ImmutableMap.of());
+            AutoRegistry.get().getBuilder().setAllowDefaultCodec(true).build(),
+            ImmutableClassToInstanceMap.of());
     try {
       objectCodecs.serialize(rule);
       throw new AssertionError("Should have thrown");
diff --git a/src/test/java/com/google/devtools/build/lib/packages/semantics/ConsistencyTest.java b/src/test/java/com/google/devtools/build/lib/packages/semantics/ConsistencyTest.java
index beca52c..6756c7f 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/semantics/ConsistencyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/semantics/ConsistencyTest.java
@@ -17,7 +17,7 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.devtools.build.lib.skyframe.serialization.DeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.DynamicCodec;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationContext;
@@ -85,9 +85,12 @@
       StarlarkSemantics deserialized =
           (StarlarkSemantics)
               TestUtils.fromBytes(
-                  new DeserializationContext(ImmutableMap.of()),
+                  new DeserializationContext(ImmutableClassToInstanceMap.of()),
                   codec,
-                  TestUtils.toBytes(new SerializationContext(ImmutableMap.of()), codec, semantics));
+                  TestUtils.toBytes(
+                      new SerializationContext(ImmutableClassToInstanceMap.of()),
+                      codec,
+                      semantics));
       assertThat(deserialized).isEqualTo(semantics);
     }
   }
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java
index 05e8c85..58706aa 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java
@@ -16,12 +16,11 @@
 
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.assertThrows;
-import static org.junit.Assert.fail;
 
 import com.google.common.base.Joiner;
 import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Multimap;
@@ -52,7 +51,6 @@
 import java.util.Collection;
 import java.util.List;
 import java.util.Map;
-import java.util.Set;
 import net.starlark.java.eval.EvalException;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -68,7 +66,7 @@
    * <p>If there are multiple entries with the same key, the variable will be treated as sequence
    * type.
    */
-  private CcToolchainVariables createVariables(String... entries) {
+  private static CcToolchainVariables createVariables(String... entries) {
     if (entries.length % 2 != 0) {
       throw new IllegalArgumentException(
           "createVariables takes an even number of arguments (key/value pairs)");
@@ -90,7 +88,7 @@
   }
 
   /** Creates an empty CcToolchainFeatures. */
-  private CcToolchainFeatures buildEmptyFeatures(String... toolchain) throws Exception {
+  private static CcToolchainFeatures buildEmptyFeatures(String... toolchain) throws Exception {
     CToolchain.Builder toolchainBuilder = CToolchain.newBuilder();
     TextFormat.merge(Joiner.on("").join(toolchain), toolchainBuilder);
     return new CcToolchainFeatures(
@@ -98,8 +96,8 @@
         PathFragment.EMPTY_FRAGMENT);
   }
 
-  private Set<String> getEnabledFeatures(CcToolchainFeatures features,
-      String... requestedFeatures) throws Exception {
+  private static ImmutableSet<String> getEnabledFeatures(
+      CcToolchainFeatures features, String... requestedFeatures) throws Exception {
     FeatureConfiguration configuration =
         features.getFeatureConfiguration(ImmutableSet.copyOf(requestedFeatures));
     ImmutableSet.Builder<String> enabledFeatures = ImmutableSet.builder();
@@ -171,7 +169,7 @@
   @Test
   public void testCrosstoolProtoCanBeSerialized() throws Exception {
     ObjectCodecs objectCodecs =
-        new ObjectCodecs(AutoRegistry.get().getBuilder().build(), ImmutableMap.of());
+        new ObjectCodecs(AutoRegistry.get().getBuilder().build(), ImmutableClassToInstanceMap.of());
     objectCodecs.serialize(CToolchain.WithFeatureSet.getDefaultInstance());
     objectCodecs.serialize(CToolchain.VariableWithValue.getDefaultInstance());
     objectCodecs.serialize(CToolchain.FlagGroup.getDefaultInstance());
@@ -304,16 +302,17 @@
     assertThat(env).doesNotContainEntry("doNotInclude", "doNotIncludePlease");
   }
 
-  private String getExpansionOfFlag(String value) throws Exception {
+  private static String getExpansionOfFlag(String value) throws Exception {
     return getExpansionOfFlag(value, createVariables());
   }
 
-  private String getExpansionOfFlag(String value, CcToolchainVariables variables) throws Exception {
+  private static String getExpansionOfFlag(String value, CcToolchainVariables variables)
+      throws Exception {
     return getCommandLineForFlag(value, variables).get(0);
   }
 
-  private List<String> getCommandLineForFlagGroups(String groups, CcToolchainVariables variables)
-      throws Exception {
+  private static List<String> getCommandLineForFlagGroups(
+      String groups, CcToolchainVariables variables) throws Exception {
     FeatureConfiguration configuration =
         CcToolchainTestHelper.buildFeatures(
                 "feature {",
@@ -327,41 +326,25 @@
     return configuration.getCommandLine(CppActionNames.CPP_COMPILE, variables);
   }
 
-  private List<String> getCommandLineForFlag(String value, CcToolchainVariables variables)
+  private static List<String> getCommandLineForFlag(String value, CcToolchainVariables variables)
       throws Exception {
     return getCommandLineForFlagGroups("flag_group { flag: '" + value + "' }", variables);
   }
 
-  private String getFlagParsingError(String value) throws Exception {
-    try {
-      getExpansionOfFlag(value);
-      fail("Expected EvalException");
-      return "";
-    } catch (EvalException e) {
-      return e.getMessage();
-    }
+  private static String getFlagParsingError(String value) {
+    return assertThrows(EvalException.class, () -> getExpansionOfFlag(value)).getMessage();
   }
 
-  private String getFlagExpansionError(String value, CcToolchainVariables variables)
-      throws Exception {
-    try {
-      getExpansionOfFlag(value, variables);
-      fail("Expected ExpansionException");
-      return "";
-    } catch (ExpansionException e) {
-      return e.getMessage();
-    }
+  private static String getFlagExpansionError(String value, CcToolchainVariables variables) {
+    return assertThrows(ExpansionException.class, () -> getExpansionOfFlag(value, variables))
+        .getMessage();
   }
 
-  private String getFlagGroupsExpansionError(String flagGroups, CcToolchainVariables variables)
-      throws Exception {
-    try {
-      getCommandLineForFlagGroups(flagGroups, variables).get(0);
-      fail("Expected ExpansionException");
-      return "";
-    } catch (ExpansionException e) {
-      return e.getMessage();
-    }
+  private static String getFlagGroupsExpansionError(
+      String flagGroups, CcToolchainVariables variables) {
+    return assertThrows(
+            ExpansionException.class, () -> getCommandLineForFlagGroups(flagGroups, variables))
+        .getMessage();
   }
 
   @Test
@@ -380,14 +363,14 @@
             getCommandLineForFlagGroups(
                 "flag_group{ iterate_over: 'v' flag: '%{v}' }",
                 CcToolchainVariables.builder()
-                    .addStringSequenceVariable("v", ImmutableList.<String>of())
+                    .addStringSequenceVariable("v", ImmutableList.of())
                     .build()))
         .isEmpty();
     assertThat(getFlagExpansionError("%{v}", createVariables()))
         .contains("Invalid toolchain configuration: Cannot find variable named 'v'");
   }
 
-  private CcToolchainVariables createStructureSequenceVariables(
+  private static CcToolchainVariables createStructureSequenceVariables(
       String name, StructureBuilder... values) {
     SequenceBuilder builder = new SequenceBuilder();
     for (StructureBuilder value : values) {
@@ -396,7 +379,8 @@
     return CcToolchainVariables.builder().addCustomBuiltVariable(name, builder).build();
   }
 
-  private CcToolchainVariables createStructureVariables(String name, StructureBuilder value) {
+  private static CcToolchainVariables createStructureVariables(
+      String name, StructureBuilder value) {
     return CcToolchainVariables.builder().addCustomBuiltVariable(name, value).build();
   }
 
@@ -426,7 +410,7 @@
   }
 
   @Test
-  public void testAccessingStructureAsStringFails() throws Exception {
+  public void testAccessingStructureAsStringFails() {
     assertThat(
             getFlagGroupsExpansionError(
                 "flag_group { flag: '-A%{struct}' }",
@@ -441,7 +425,7 @@
   }
 
   @Test
-  public void testAccessingStringValueAsStructureFails() throws Exception {
+  public void testAccessingStringValueAsStructureFails() {
     assertThat(
             getFlagGroupsExpansionError(
                 "flag_group { flag: '-A%{stringVar.foo}' }",
@@ -452,7 +436,7 @@
   }
 
   @Test
-  public void testAccessingSequenceAsStructureFails() throws Exception {
+  public void testAccessingSequenceAsStructureFails() {
     assertThat(
             getFlagGroupsExpansionError(
                 "flag_group { flag: '-A%{sequence.foo}' }",
@@ -463,7 +447,7 @@
   }
 
   @Test
-  public void testAccessingMissingStructureFieldFails() throws Exception {
+  public void testAccessingMissingStructureFieldFails() {
     assertThat(
             getFlagGroupsExpansionError(
                 "flag_group { flag: '-A%{struct.missing}' }",
@@ -788,8 +772,7 @@
   }
 
   @Test
-  public void testListVariableExpansionMixedWithImplicitlyAccessedListVariableFails()
-      throws Exception {
+  public void testListVariableExpansionMixedWithImplicitlyAccessedListVariableFails() {
     assertThat(
             getFlagGroupsExpansionError(
                 "flag_group { iterate_over: 'v1' flag: '%{v1} %{v2}' }",
@@ -822,7 +805,7 @@
         .containsExactly("-f", "1", "-f", "2", "1", "2");
   }
 
-  private VariableValueBuilder createNestedSequence(int depth, int count, String prefix) {
+  private static VariableValueBuilder createNestedSequence(int depth, int count, String prefix) {
     if (depth == 0) {
       StringSequenceBuilder builder = new StringSequenceBuilder();
       for (int i = 0; i < count; ++i) {
@@ -840,7 +823,7 @@
     }
   }
 
-  private CcToolchainVariables createNestedVariables(String name, int depth, int count) {
+  private static CcToolchainVariables createNestedVariables(String name, int depth, int count) {
     return CcToolchainVariables.builder()
         .addCustomBuiltVariable(name, createNestedSequence(depth, count, ""))
         .build();
@@ -994,7 +977,7 @@
   }
 
   @Test
-  public void testFeatureNameCollision() throws Exception {
+  public void testFeatureNameCollision() {
     EvalException e =
         assertThrows(
             EvalException.class,
@@ -1005,7 +988,7 @@
   }
 
   @Test
-  public void testReferenceToUndefinedFeature() throws Exception {
+  public void testReferenceToUndefinedFeature() {
     EvalException e =
         assertThrows(
             EvalException.class,
@@ -1603,7 +1586,7 @@
   }
 
   @Test
-  public void testInvalidActionConfigurationDuplicateActionConfigs() throws Exception {
+  public void testInvalidActionConfigurationDuplicateActionConfigs() {
     EvalException e =
         assertThrows(
             EvalException.class,
@@ -1623,7 +1606,7 @@
   }
 
   @Test
-  public void testInvalidActionConfigurationMultipleActionConfigsForAction() throws Exception {
+  public void testInvalidActionConfigurationMultipleActionConfigsForAction() {
     EvalException e =
         assertThrows(
             EvalException.class,
@@ -1658,7 +1641,7 @@
   }
 
   @Test
-  public void testErrorForFlagFromActionConfigWithSpecifiedAction() throws Exception {
+  public void testErrorForFlagFromActionConfigWithSpecifiedAction() {
     EvalException e =
         assertThrows(
             EvalException.class,
@@ -1706,12 +1689,11 @@
       objectNames.add(object.getStringValue("name"));
     }
     assertThat(objectNames.build())
-        .containsExactlyElementsIn(
-            Iterables.transform(testArtifacts, testArtifact -> testArtifact.getExecPathString()));
+        .containsExactlyElementsIn(Iterables.transform(testArtifacts, Artifact::getExecPathString));
   }
 
   @Test
-  public void testProvidesCollision() throws Exception {
+  public void testProvidesCollision() {
     Exception e =
         assertThrows(
             Exception.class,
@@ -1730,7 +1712,7 @@
   }
 
   @Test
-  public void testErrorForNoMatchingArtifactNamePatternCategory() throws Exception {
+  public void testErrorForNoMatchingArtifactNamePatternCategory() {
     EvalException e =
         assertThrows(
             EvalException.class,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TargetPatternSequenceCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TargetPatternSequenceCodecTest.java
index c43ec70..fb9a317 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TargetPatternSequenceCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TargetPatternSequenceCodecTest.java
@@ -15,8 +15,8 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.skyframe.PrepareDepsOfPatternsValue.TargetPatternSequence;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
@@ -45,7 +45,7 @@
 
   @Test
   public void testPatternsOrderSignificant() throws Exception {
-    SerializationContext writeContext = new SerializationContext(ImmutableMap.of());
+    SerializationContext writeContext = new SerializationContext(ImmutableClassToInstanceMap.of());
 
     ByteArrayOutputStream outputBytes = new ByteArrayOutputStream();
     CodedOutputStream codedOut = CodedOutputStream.newInstance(outputBytes);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ArrayCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ArrayCodecTest.java
index 09910de..c6411e1 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ArrayCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ArrayCodecTest.java
@@ -17,7 +17,7 @@
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.assertThrows;
 
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.TestUtils;
 import org.junit.Test;
@@ -49,7 +49,9 @@
       cur[0] = new Object[1];
       cur = (Object[]) cur[0];
     }
-    assertThrows(SerializationException.class, () -> TestUtils.toBytes(obj, ImmutableMap.of()));
+    assertThrows(
+        SerializationException.class,
+        () -> TestUtils.toBytes(new SerializationContext(ImmutableClassToInstanceMap.of()), obj));
   }
 
   private static void verifyDeserialized(Object[] original, Object[] deserialized) {
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContextTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContextTest.java
index fc8f5b2..c1f6e57a 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContextTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContextTest.java
@@ -18,8 +18,8 @@
 import static org.mockito.Mockito.doReturn;
 import static org.mockito.Mockito.when;
 
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec.MemoizationStrategy;
 import com.google.protobuf.CodedInputStream;
 import java.io.IOException;
@@ -37,7 +37,7 @@
     CodedInputStream codedInputStream = Mockito.mock(CodedInputStream.class);
     when(codedInputStream.readSInt32()).thenReturn(0);
     DeserializationContext deserializationContext =
-        new DeserializationContext(registry, ImmutableMap.of());
+        new DeserializationContext(registry, ImmutableClassToInstanceMap.of());
     assertThat((Object) deserializationContext.deserialize(codedInputStream)).isNull();
     Mockito.verify(codedInputStream).readSInt32();
     Mockito.verifyZeroInteractions(registry);
@@ -51,7 +51,7 @@
     CodedInputStream codedInputStream = Mockito.mock(CodedInputStream.class);
     when(codedInputStream.readSInt32()).thenReturn(1);
     DeserializationContext deserializationContext =
-        new DeserializationContext(registry, ImmutableMap.of());
+        new DeserializationContext(registry, ImmutableClassToInstanceMap.of());
     assertThat((Object) deserializationContext.deserialize(codedInputStream))
         .isSameInstanceAs(constant);
     Mockito.verify(codedInputStream).readSInt32();
@@ -67,7 +67,7 @@
     CodedInputStream codedInputStream = Mockito.mock(CodedInputStream.class);
     when(codedInputStream.readSInt32()).thenReturn(1);
     DeserializationContext deserializationContext =
-        new DeserializationContext(registry, ImmutableMap.of());
+        new DeserializationContext(registry, ImmutableClassToInstanceMap.of());
     Object returnValue = new Object();
     when(codecDescriptor.deserialize(deserializationContext, codedInputStream))
         .thenReturn(returnValue);
@@ -83,7 +83,7 @@
     ObjectCodecRegistry registry = Mockito.mock(ObjectCodecRegistry.class);
     CodedInputStream codedInputStream = Mockito.mock(CodedInputStream.class);
     DeserializationContext deserializationContext =
-        new DeserializationContext(registry, ImmutableMap.of());
+        new DeserializationContext(registry, ImmutableClassToInstanceMap.of());
     when(codedInputStream.readSInt32()).thenReturn(0);
     assertThat((Object) deserializationContext.getMemoizingContext().deserialize(codedInputStream))
         .isEqualTo(null);
@@ -98,7 +98,7 @@
     when(registry.maybeGetConstantByTag(1)).thenReturn(constant);
     CodedInputStream codedInputStream = Mockito.mock(CodedInputStream.class);
     DeserializationContext deserializationContext =
-        new DeserializationContext(registry, ImmutableMap.of());
+        new DeserializationContext(registry, ImmutableClassToInstanceMap.of());
     when(codedInputStream.readSInt32()).thenReturn(1);
     assertThat((Object) deserializationContext.getMemoizingContext().deserialize(codedInputStream))
         .isEqualTo(constant);
@@ -121,7 +121,8 @@
     when(registry.getCodecDescriptorByTag(1)).thenReturn(codecDescriptor);
     CodedInputStream codedInputStream = Mockito.mock(CodedInputStream.class);
     DeserializationContext deserializationContext =
-        new DeserializationContext(registry, ImmutableMap.of()).getMemoizingContext();
+        new DeserializationContext(registry, ImmutableClassToInstanceMap.of())
+            .getMemoizingContext();
     when(codec.deserialize(deserializationContext, codedInputStream)).thenReturn(returned);
     when(codedInputStream.readSInt32()).thenReturn(1);
     assertThat((Object) deserializationContext.deserialize(codedInputStream)).isEqualTo(returned);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/DynamicCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/DynamicCodecTest.java
index a26e18d..8a7c889 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/DynamicCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/DynamicCodecTest.java
@@ -17,7 +17,7 @@
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.assertThrows;
 
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
 import com.google.protobuf.ByteString;
 import com.google.protobuf.CodedInputStream;
@@ -390,7 +390,7 @@
 
   @Test
   public void testNoCodecExample() {
-    ObjectCodecs codecs = new ObjectCodecs(AutoRegistry.get(), ImmutableMap.of());
+    ObjectCodecs codecs = new ObjectCodecs(AutoRegistry.get(), ImmutableClassToInstanceMap.of());
     SerializationException.NoCodecException expected =
         assertThrows(
             SerializationException.NoCodecException.class,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/EnumMapCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/EnumMapCodecTest.java
index 92a959f..04e8333 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/EnumMapCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/EnumMapCodecTest.java
@@ -17,6 +17,7 @@
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.assertThrows;
 
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.TestUtils;
@@ -44,7 +45,10 @@
     SerializationException exception =
         assertThrows(
             SerializationException.class,
-            () -> TestUtils.toBytes(new SubEnum<>(TestEnum.class), ImmutableMap.of()));
+            () ->
+                TestUtils.toBytes(
+                    new SerializationContext(ImmutableClassToInstanceMap.of()),
+                    new SubEnum<>(TestEnum.class)));
     assertThat(exception).hasMessageThat().contains("Cannot serialize subclasses of EnumMap");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableBiMapCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableBiMapCodecTest.java
index 448ab5d..64a685c 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableBiMapCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableBiMapCodecTest.java
@@ -19,6 +19,7 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableBiMap;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester.VerificationFunction;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.TestUtils;
@@ -74,14 +75,14 @@
             .build();
     ByteString data =
         TestUtils.toBytes(
-            new SerializationContext(registry, ImmutableBiMap.of()),
+            new SerializationContext(registry, ImmutableClassToInstanceMap.of()),
             ImmutableBiMap.of("a", new Dummy()));
     SerializationException expected =
         assertThrows(
             SerializationException.class,
             () ->
                 TestUtils.fromBytes(
-                    new DeserializationContext(registry, ImmutableBiMap.of()), data));
+                    new DeserializationContext(registry, ImmutableClassToInstanceMap.of()), data));
     assertThat(expected)
         .hasMessageThat()
         .contains("Exception while deserializing value for key 'a'");
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableClassToInstanceMapCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableClassToInstanceMapCodecTest.java
index d6ecbee..bf60323 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableClassToInstanceMapCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableClassToInstanceMapCodecTest.java
@@ -19,7 +19,6 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableClassToInstanceMap;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester.VerificationFunction;
@@ -80,13 +79,14 @@
             .build();
     ByteString data =
         TestUtils.toBytes(
-            new SerializationContext(registry, ImmutableMap.of()),
+            new SerializationContext(registry, ImmutableClassToInstanceMap.of()),
             ImmutableClassToInstanceMap.of(Dummy.class, new Dummy()));
     SerializationException expected =
         assertThrows(
             SerializationException.class,
             () ->
-                TestUtils.fromBytes(new DeserializationContext(registry, ImmutableMap.of()), data));
+                TestUtils.fromBytes(
+                    new DeserializationContext(registry, ImmutableClassToInstanceMap.of()), data));
     assertThat(expected)
         .hasMessageThat()
         .containsMatch("Exception while deserializing value for key 'class .*\\$Dummy'");
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableMapCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableMapCodecTest.java
index 97bf00d..3bf9b44 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableMapCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableMapCodecTest.java
@@ -18,6 +18,7 @@
 import static org.junit.Assert.assertThrows;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSortedMap;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
@@ -88,13 +89,14 @@
             .build();
     ByteString data =
         TestUtils.toBytes(
-            new SerializationContext(registry, ImmutableMap.of()),
+            new SerializationContext(registry, ImmutableClassToInstanceMap.of()),
             ImmutableMap.of("a", new Dummy()));
     SerializationException expected =
         assertThrows(
             SerializationException.class,
             () ->
-                TestUtils.fromBytes(new DeserializationContext(registry, ImmutableMap.of()), data));
+                TestUtils.fromBytes(
+                    new DeserializationContext(registry, ImmutableClassToInstanceMap.of()), data));
     assertThat(expected)
         .hasMessageThat()
         .contains("Exception while deserializing value for key 'a'");
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecsTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecsTest.java
index 63f74ff..90599a8 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodecsTest.java
@@ -23,13 +23,12 @@
 import static org.mockito.Mockito.doThrow;
 import static org.mockito.Mockito.spy;
 
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.protobuf.ByteString;
 import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
 import java.io.IOException;
-import java.util.List;
 import java.util.concurrent.atomic.AtomicInteger;
 import org.junit.Before;
 import org.junit.Test;
@@ -50,7 +49,7 @@
     // We have to override the default explicitly here because Mockito can't delegate to default
     // methods on interfaces.
     @Override
-    public List<Class<? extends Integer>> additionalEncodedClasses() {
+    public ImmutableList<Class<? extends Integer>> additionalEncodedClasses() {
       return ImmutableList.of();
     }
 
@@ -67,6 +66,7 @@
     }
 
     /** Disables auto-registration. */
+    @SuppressWarnings("unused") // Used reflectively.
     private static class IntegerCodecRegisterer implements CodecRegisterer<IntegerCodec> {}
   }
 
@@ -79,7 +79,8 @@
     spyObjectCodec = spy(new IntegerCodec());
     this.underTest =
         new ObjectCodecs(
-            ObjectCodecRegistry.newBuilder().add(spyObjectCodec).build(), ImmutableMap.of());
+            ObjectCodecRegistry.newBuilder().add(spyObjectCodec).build(),
+            ImmutableClassToInstanceMap.of());
   }
 
   @Test
@@ -192,7 +193,7 @@
     ObjectCodecs underTest =
         new ObjectCodecs(
             ObjectCodecRegistry.newBuilder().setAllowDefaultCodec(false).build(),
-            ImmutableMap.of());
+            ImmutableClassToInstanceMap.of());
     SerializationException.NoCodecException expected =
         assertThrows(SerializationException.NoCodecException.class, () -> underTest.serialize("Y"));
     assertThat(expected)
@@ -206,14 +207,14 @@
     ObjectCodecs underTest =
         new ObjectCodecs(
             ObjectCodecRegistry.newBuilder().setAllowDefaultCodec(false).build(),
-            ImmutableMap.of());
+            ImmutableClassToInstanceMap.of());
     assertThrows(
         SerializationException.NoCodecException.class, () -> underTest.deserialize(serialized));
   }
 
   @Test
   public void testSerializeDeserialize() throws Exception {
-    ObjectCodecs underTest = new ObjectCodecs(AutoRegistry.get(), ImmutableMap.of());
+    ObjectCodecs underTest = new ObjectCodecs(AutoRegistry.get(), ImmutableClassToInstanceMap.of());
     assertThat((String) underTest.deserialize(underTest.serialize("hello"))).isEqualTo("hello");
     assertThat(underTest.deserialize(underTest.serialize(null))).isNull();
   }
@@ -225,7 +226,7 @@
     MyException exception = new MyException();
     // Force initialization of stack trace.
     StackTraceElement[] stackTrace = exception.getStackTrace();
-    ObjectCodecs underTest = new ObjectCodecs(AutoRegistry.get(), ImmutableMap.of());
+    ObjectCodecs underTest = new ObjectCodecs(AutoRegistry.get(), ImmutableClassToInstanceMap.of());
     assertThat(
             ((MyException) underTest.deserializeMemoized(underTest.serializeMemoized(exception)))
                 .getStackTrace())
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContextTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContextTest.java
index c76c796..89db6b5 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContextTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContextTest.java
@@ -20,8 +20,8 @@
 import static org.mockito.Mockito.when;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec.MemoizationStrategy;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.TestUtils;
 import com.google.protobuf.CodedInputStream;
@@ -43,7 +43,7 @@
     ObjectCodecRegistry registry = Mockito.mock(ObjectCodecRegistry.class);
     CodedOutputStream codedOutputStream = Mockito.mock(CodedOutputStream.class);
     SerializationContext serializationContext =
-        new SerializationContext(registry, ImmutableMap.of());
+        new SerializationContext(registry, ImmutableClassToInstanceMap.of());
     serializationContext.serialize(null, codedOutputStream);
     Mockito.verify(codedOutputStream).writeSInt32NoTag(0);
     Mockito.verifyZeroInteractions(registry);
@@ -55,7 +55,7 @@
     when(registry.maybeGetTagForConstant(ArgumentMatchers.any())).thenReturn(1);
     CodedOutputStream codedOutputStream = Mockito.mock(CodedOutputStream.class);
     SerializationContext serializationContext =
-        new SerializationContext(registry, ImmutableMap.of());
+        new SerializationContext(registry, ImmutableClassToInstanceMap.of());
     Object constant = new Object();
     serializationContext.serialize(constant, codedOutputStream);
     Mockito.verify(codedOutputStream).writeSInt32NoTag(1);
@@ -71,7 +71,8 @@
     when(registry.maybeGetTagForConstant(ArgumentMatchers.any())).thenReturn(null);
     when(registry.getCodecDescriptorForObject("string")).thenReturn(codecDescriptor);
     CodedOutputStream codedOutputStream = Mockito.mock(CodedOutputStream.class);
-    SerializationContext underTest = new SerializationContext(registry, ImmutableMap.of());
+    SerializationContext underTest =
+        new SerializationContext(registry, ImmutableClassToInstanceMap.of());
     underTest.serialize("string", codedOutputStream);
     Mockito.verify(codedOutputStream).writeSInt32NoTag(1);
     Mockito.verify(registry).maybeGetTagForConstant("string");
@@ -85,7 +86,7 @@
     ObjectCodecRegistry registry = Mockito.mock(ObjectCodecRegistry.class);
     CodedOutputStream codedOutputStream = Mockito.mock(CodedOutputStream.class);
     SerializationContext serializationContext =
-        new SerializationContext(registry, ImmutableMap.of());
+        new SerializationContext(registry, ImmutableClassToInstanceMap.of());
     serializationContext.getMemoizingContext().serialize(null, codedOutputStream);
     Mockito.verify(codedOutputStream).writeSInt32NoTag(0);
     Mockito.verifyZeroInteractions(registry);
@@ -97,7 +98,7 @@
     when(registry.maybeGetTagForConstant(ArgumentMatchers.any())).thenReturn(1);
     CodedOutputStream codedOutputStream = Mockito.mock(CodedOutputStream.class);
     SerializationContext serializationContext =
-        new SerializationContext(registry, ImmutableMap.of());
+        new SerializationContext(registry, ImmutableClassToInstanceMap.of());
     Object constant = new Object();
     serializationContext.getMemoizingContext().serialize(constant, codedOutputStream);
     Mockito.verify(codedOutputStream).writeSInt32NoTag(1);
@@ -118,7 +119,7 @@
     when(registry.getCodecDescriptorForObject("string")).thenReturn(codecDescriptor);
     CodedOutputStream codedOutputStream = Mockito.mock(CodedOutputStream.class);
     SerializationContext underTest =
-        new SerializationContext(registry, ImmutableMap.of()).getMemoizingContext();
+        new SerializationContext(registry, ImmutableClassToInstanceMap.of()).getMemoizingContext();
     underTest.serialize("string", codedOutputStream);
     Mockito.verify(codedOutputStream).writeSInt32NoTag(1);
     Mockito.verify(registry).maybeGetTagForConstant("string");
@@ -144,7 +145,8 @@
   @Test
   public void explicitlyAllowedClassCheck() throws SerializationException {
     SerializationContext underTest =
-        new SerializationContext(ObjectCodecRegistry.newBuilder().build(), ImmutableMap.of())
+        new SerializationContext(
+                ObjectCodecRegistry.newBuilder().build(), ImmutableClassToInstanceMap.of())
             .getMemoizingContext();
     underTest.addExplicitlyAllowedClass(String.class);
     underTest.checkClassExplicitlyAllowed(String.class, "str");
@@ -160,7 +162,8 @@
   @Test
   public void explicitlyAllowedClassCheckFailsIfNotMemoizing() {
     SerializationContext underTest =
-        new SerializationContext(ObjectCodecRegistry.newBuilder().build(), ImmutableMap.of());
+        new SerializationContext(
+            ObjectCodecRegistry.newBuilder().build(), ImmutableClassToInstanceMap.of());
     assertThrows(
         SerializationException.class, () -> underTest.addExplicitlyAllowedClass(String.class));
   }
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentTest.java b/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentTest.java
index 4af015d..80c62c7 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentTest.java
+++ b/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentTest.java
@@ -19,12 +19,13 @@
 import static com.google.devtools.build.lib.vfs.PathFragment.create;
 import static org.junit.Assert.assertThrows;
 
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Lists;
 import com.google.common.testing.EqualsTester;
 import com.google.devtools.build.lib.skyframe.serialization.DeserializationContext;
+import com.google.devtools.build.lib.skyframe.serialization.SerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.TestUtils;
 import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
@@ -295,7 +296,7 @@
   }
 
   @Test
-  public void testBasename() throws Exception {
+  public void testBasename() {
     assertThat(create("foo/bar").getBaseName()).isEqualTo("bar");
     assertThat(create("/foo/bar").getBaseName()).isEqualTo("bar");
     assertThat(create("foo/").getBaseName()).isEqualTo("foo");
@@ -307,7 +308,7 @@
   }
 
   @Test
-  public void testFileExtension() throws Exception {
+  public void testFileExtension() {
     assertThat(create("foo.bar").getFileExtension()).isEqualTo("bar");
     assertThat(create("foo.barr").getFileExtension()).isEqualTo("barr");
     assertThat(create("foo.b").getFileExtension()).isEqualTo("b");
@@ -321,7 +322,7 @@
   }
 
   @Test
-  public void testReplaceName() throws Exception {
+  public void testReplaceName() {
     assertThat(create("foo/bar").replaceName("baz").getPathString()).isEqualTo("foo/baz");
     assertThat(create("/foo/bar").replaceName("baz").getPathString()).isEqualTo("/foo/baz");
     assertThat(create("foo/bar").replaceName("").getPathString()).isEqualTo("foo");
@@ -341,8 +342,9 @@
     assertThat(create("foo/bar").replaceName("/absolute").getPathString()).isEqualTo("/absolute");
     assertThat(create("foo/bar").replaceName("/").getPathString()).isEqualTo("/");
   }
+
   @Test
-  public void testSubFragment() throws Exception {
+  public void testSubFragment() {
     assertThat(create("/foo/bar/baz").subFragment(0, 3).getPathString()).isEqualTo("/foo/bar/baz");
     assertThat(create("foo/bar/baz").subFragment(0, 3).getPathString()).isEqualTo("foo/bar/baz");
     assertThat(create("/foo/bar/baz").subFragment(0, 2).getPathString()).isEqualTo("/foo/bar");
@@ -403,7 +405,7 @@
     PathFragment.checkAllPathsAreUnder(toPathsSet("a/b", "a/c"), create("a"));
 
     // Check trivially passes:
-    PathFragment.checkAllPathsAreUnder(ImmutableList.<PathFragment>of(), create("a"));
+    PathFragment.checkAllPathsAreUnder(ImmutableList.of(), create("a"));
 
     // Check fails when some path does not start with startingWithPath:
     assertThrows(
@@ -467,7 +469,7 @@
     assertThrows(IllegalArgumentException.class, () -> create("foo").getDriveStr());
   }
 
-  static List<PathFragment> toPaths(List<String> strs) {
+  private static List<PathFragment> toPaths(List<String> strs) {
     List<PathFragment> paths = Lists.newArrayList();
     for (String s : strs) {
       paths.add(create(s));
@@ -475,7 +477,7 @@
     return paths;
   }
 
-  static ImmutableSet<PathFragment> toPathsSet(String... strs) {
+  private static ImmutableSet<PathFragment> toPathsSet(String... strs) {
     ImmutableSet.Builder<PathFragment> builder = ImmutableSet.builder();
     for (String str : strs) {
       builder.add(create(str));
@@ -484,7 +486,7 @@
   }
 
   @Test
-  public void testCompareTo() throws Exception {
+  public void testCompareTo() {
     List<String> pathStrs =
         ImmutableList.of(
             "",
@@ -619,13 +621,16 @@
     checkSerialization("foo/bar/baz", 16);
   }
 
-  private void checkSerialization(String pathFragmentString, int expectedSize) throws Exception {
+  private static void checkSerialization(String pathFragmentString, int expectedSize)
+      throws Exception {
     PathFragment a = create(pathFragmentString);
-    ByteString sa = TestUtils.toBytes(a, ImmutableMap.of());
+    ByteString sa =
+        TestUtils.toBytes(new SerializationContext(ImmutableClassToInstanceMap.of()), a);
     assertThat(sa.size()).isEqualTo(expectedSize);
 
     PathFragment a2 =
-        (PathFragment) TestUtils.fromBytes(new DeserializationContext(ImmutableMap.of()), sa);
+        (PathFragment)
+            TestUtils.fromBytes(new DeserializationContext(ImmutableClassToInstanceMap.of()), sa);
     assertThat(a2).isEqualTo(a);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/RootTest.java b/src/test/java/com/google/devtools/build/lib/vfs/RootTest.java
index d20ccd2..ccbfe3b 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/RootTest.java
+++ b/src/test/java/com/google/devtools/build/lib/vfs/RootTest.java
@@ -16,8 +16,8 @@
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.assertThrows;
 
+import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Lists;
 import com.google.common.testing.EqualsTester;
 import com.google.devtools.build.lib.clock.BlazeClock;
@@ -39,12 +39,12 @@
   private FileSystem fs;
 
   @Before
-  public final void initializeFileSystem() throws Exception {
+  public final void initializeFileSystem() {
     fs = new InMemoryFileSystem(BlazeClock.instance(), DigestHashFunction.SHA256);
   }
 
   @Test
-  public void testEqualsAndHashCodeContract() throws Exception {
+  public void testEqualsAndHashCodeContract() {
     FileSystem otherFs = new InMemoryFileSystem(BlazeClock.instance(), DigestHashFunction.SHA256);
     new EqualsTester()
         .addEqualityGroup(Root.absoluteRoot(fs), Root.absoluteRoot(fs))
@@ -54,7 +54,7 @@
   }
 
   @Test
-  public void testPathRoot() throws Exception {
+  public void testPathRoot() {
     Root root = Root.fromPath(fs.getPath("/foo"));
     assertThat(root.asPath()).isEqualTo(fs.getPath("/foo"));
     assertThat(root.contains(fs.getPath("/foo/bar"))).isTrue();
@@ -71,7 +71,7 @@
   }
 
   @Test
-  public void testFilesystemTransform() throws Exception {
+  public void testFilesystemTransform() {
     FileSystem fs2 = new InMemoryFileSystem(BlazeClock.instance(), DigestHashFunction.SHA256);
     Root root = Root.fromPath(fs.getPath("/foo"));
     Root root2 = Root.toFileSystem(root, fs2);
@@ -81,7 +81,7 @@
   }
 
   @Test
-  public void testFileSystemAbsoluteRoot() throws Exception {
+  public void testFileSystemAbsoluteRoot() {
     Root root = Root.absoluteRoot(fs);
     assertThat(root.asPath()).isNull();
     assertThat(root.contains(fs.getPath("/foo"))).isTrue();
@@ -99,7 +99,7 @@
   }
 
   @Test
-  public void testCompareTo() throws Exception {
+  public void testCompareTo() {
     Root a = Root.fromPath(fs.getPath("/a"));
     Root b = Root.fromPath(fs.getPath("/b"));
     Root root = Root.absoluteRoot(fs);
@@ -132,8 +132,8 @@
     assertThat(fooPathRoot).isEqualTo(otherFooPathRoot);
 
     ObjectCodecRegistry registry = AutoRegistry.get();
-    ImmutableMap<Class<?>, Object> dependencies =
-        ImmutableMap.<Class<?>, Object>builder()
+    ImmutableClassToInstanceMap<Object> dependencies =
+        ImmutableClassToInstanceMap.builder()
             .put(FileSystem.class, fs)
             .put(
                 Root.RootCodecDependencies.class,