Serializer implementations for Guava Collections

PiperOrigin-RevId: 183248133

15 files changed, 843 insertions, 30 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BUILD b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BUILD
index 6fc533c0a8..b9a5b4cbeb 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BUILD
@@ -5,6 +5,7 @@ filegroup(
     srcs = glob(["**"]) + [
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec:srcs",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils:srcs",
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers:srcs",
     ],
 )
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/BUILD b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/BUILD
new file mode 100644
index 0000000000..2ff7dbf587
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/BUILD
@@ -0,0 +1,18 @@
+package(
+    default_visibility = ["//src:__subpackages__"],
+)
+
+filegroup(
+    name = "srcs",
+    srcs = glob(["**"]),
+)
+
+java_library(
+    name = "serializers",
+    srcs = glob(["*.java"]),
+    deps = [
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization:kryo",
+        "//third_party:guava",
+        "//third_party/protobuf:protobuf_java",
+    ],
+)
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableListSerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableListSerializer.java
new file mode 100644
index 0000000000..0556d02615
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableListSerializer.java
@@ -0,0 +1,95 @@
+// 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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+import com.google.common.collect.HashBasedTable;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableTable;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Table;
+
+/** A {@link Serializer} for {@link ImmutableList}. */
+class ImmutableListSerializer extends Serializer<ImmutableList<Object>> {
+
+  private ImmutableListSerializer() {
+    setImmutable(true);
+  }
+
+  @Override
+  public void write(Kryo kryo, Output output, ImmutableList<Object> object) {
+    output.writeInt(object.size(), true);
+    for (Object elm : object) {
+      kryo.writeClassAndObject(output, elm);
+    }
+  }
+
+  @Override
+  public ImmutableList<Object> read(Kryo kryo, Input input, Class<ImmutableList<Object>> type) {
+    int size = input.readInt(true);
+    Object[] list = new Object[size];
+    for (int i = 0; i < size; ++i) {
+      list[i] = kryo.readClassAndObject(input);
+    }
+    return ImmutableList.copyOf(list);
+  }
+
+  /**
+   * Creates a new {@link ImmutableListSerializer} and registers its serializer for the several
+   * ImmutableList related classes.
+   *
+   * @param kryo the {@link Kryo} instance to set the serializer on
+   */
+  static void registerSerializers(Kryo kryo) {
+
+    // ImmutableList (abstract class)
+    //  +- RegularImmutableList
+    //  |   RegularImmutableList
+    //  +- SingletonImmutableList
+    //  |   Optimized for List with only 1 element.
+    //  +- SubList
+    //  |   Representation for part of ImmutableList
+    //  +- ReverseImmutableList
+    //  |   For iterating in reverse order
+    //  +- StringAsImmutableList
+    //  |   Used by Lists#charactersOf
+    //  +- Values (ImmutableTable values)
+    //      Used by return value of #values() when there are multiple cells
+
+    ImmutableListSerializer serializer = new ImmutableListSerializer();
+
+    kryo.register(ImmutableList.class, serializer);
+
+    // Note:
+    //  Only registering above is good enough for serializing/deserializing.
+    //  but if using Kryo#copy, following is required.
+
+    kryo.register(ImmutableList.of().getClass(), serializer);
+    kryo.register(ImmutableList.of(1).getClass(), serializer);
+    kryo.register(ImmutableList.of(1, 2, 3, 4).subList(1, 3).getClass(), serializer);
+    kryo.register(ImmutableList.of(1, 2).reverse().getClass(), serializer);
+
+    kryo.register(Lists.charactersOf("KryoRocks").getClass(), serializer);
+
+    Table<Integer, Integer, Integer> baseTable = HashBasedTable.create();
+    baseTable.put(1, 2, 3);
+    baseTable.put(4, 5, 6);
+    Table<Integer, Integer, Integer> table = ImmutableTable.copyOf(baseTable);
+    kryo.register(table.values().getClass(), serializer);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableMapSerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableMapSerializer.java
new file mode 100644
index 0000000000..70af65f6f1
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableMapSerializer.java
@@ -0,0 +1,77 @@
+// 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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+import com.google.common.collect.ImmutableMap;
+import java.util.EnumMap;
+import java.util.Map;
+
+/** {@link Serializer} for {@link ImmutableMap}. */
+class ImmutableMapSerializer extends Serializer<ImmutableMap<Object, Object>> {
+
+  private ImmutableMapSerializer() {
+    setImmutable(true);
+  }
+
+  @Override
+  public void write(Kryo kryo, Output output, ImmutableMap<Object, Object> immutableMap) {
+    output.writeInt(immutableMap.size(), true);
+    for (Map.Entry<Object, Object> entry : immutableMap.entrySet()) {
+      kryo.writeClassAndObject(output, entry.getKey());
+      kryo.writeClassAndObject(output, entry.getValue());
+    }
+  }
+
+  @Override
+  public ImmutableMap<Object, Object> read(
+      Kryo kryo, Input input, Class<ImmutableMap<Object, Object>> type) {
+    ImmutableMap.Builder<Object, Object> builder = ImmutableMap.builder();
+    int length = input.readInt(true);
+    for (int i = 0; i < length; ++i) {
+      builder.put(kryo.readClassAndObject(input), kryo.readClassAndObject(input));
+    }
+    return builder.build();
+  }
+
+  /** Registers serializers for {@link ImmutableMap}. */
+  static void registerSerializers(Kryo kryo) {
+    ImmutableMapSerializer serializer = new ImmutableMapSerializer();
+
+    kryo.register(ImmutableMap.class, serializer);
+    kryo.register(ImmutableMap.of().getClass(), serializer);
+
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    kryo.register(ImmutableMap.of(o1, o1).getClass(), serializer);
+    kryo.register(ImmutableMap.of(o1, o1, o2, o2).getClass(), serializer);
+
+    Map<DummyEnum, Object> enumMap = new EnumMap<>(DummyEnum.class);
+    for (DummyEnum e : DummyEnum.values()) {
+      enumMap.put(e, o1);
+    }
+
+    kryo.register(ImmutableMap.copyOf(enumMap).getClass(), serializer);
+  }
+
+  private enum DummyEnum {
+    VALUE1,
+    VALUE2
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableMultimapSerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableMultimapSerializer.java
new file mode 100644
index 0000000000..98b4e7b970
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableMultimapSerializer.java
@@ -0,0 +1,75 @@
+// 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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+import com.google.common.collect.ImmutableListMultimap;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableMultimap;
+import com.google.common.collect.ImmutableSetMultimap;
+import java.util.Collection;
+import java.util.Map;
+
+/** {@link Serializer} for {@link ImmutableMultimap}. */
+class ImmutableMultimapSerializer extends Serializer<ImmutableMultimap<Object, Object>> {
+
+  private ImmutableMultimapSerializer() {
+    setImmutable(true);
+  }
+
+  @Override
+  public void write(Kryo kryo, Output output, ImmutableMultimap<Object, Object> immutableMultiMap) {
+    kryo.writeObject(output, ImmutableMap.copyOf(immutableMultiMap.asMap()));
+  }
+
+  @Override
+  public ImmutableMultimap<Object, Object> read(
+      Kryo kryo, Input input, Class<ImmutableMultimap<Object, Object>> type) {
+    ImmutableMultimap.Builder<Object, Object> builder;
+    if (type.equals(ImmutableListMultimap.class)) {
+      builder = ImmutableMultimap.builder();
+    } else if (type.equals(ImmutableSetMultimap.class)) {
+      builder = ImmutableSetMultimap.builder();
+    } else {
+      builder = ImmutableMultimap.builder();
+    }
+
+    @SuppressWarnings("unchecked")
+    Map<Object, Collection<Object>> map = kryo.readObject(input, ImmutableMap.class);
+    for (Map.Entry<Object, Collection<Object>> entry : map.entrySet()) {
+      builder.putAll(entry.getKey(), entry.getValue());
+    }
+    return builder.build();
+  }
+
+  static void registerSerializers(Kryo kryo) {
+    ImmutableMultimapSerializer serializer = new ImmutableMultimapSerializer();
+
+    // ImmutableMultimap (abstract class)
+    //  +- EmptyImmutableListMultimap
+    //  +- ImmutableListMultimap
+    //  +- EmptyImmutableSetMultimap
+    //  +- ImmutableSetMultimap
+
+    kryo.register(ImmutableMultimap.class, serializer);
+    kryo.register(ImmutableListMultimap.of().getClass(), serializer);
+    kryo.register(ImmutableListMultimap.of("A", "B").getClass(), serializer);
+    kryo.register(ImmutableSetMultimap.of().getClass(), serializer);
+    kryo.register(ImmutableSetMultimap.of("A", "B").getClass(), serializer);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableSetSerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableSetSerializer.java
new file mode 100644
index 0000000000..999494d901
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableSetSerializer.java
@@ -0,0 +1,81 @@
+// 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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+
+/** {@link Serializer} for {@link ImmutableSet}. */
+class ImmutableSetSerializer extends Serializer<ImmutableSet<Object>> {
+
+  private ImmutableSetSerializer() {
+    setImmutable(true);
+  }
+
+  @Override
+  public void write(Kryo kryo, Output output, ImmutableSet<Object> object) {
+    output.writeInt(object.size(), true);
+    for (Object elt : object) {
+      kryo.writeClassAndObject(output, elt);
+    }
+  }
+
+  @Override
+  public ImmutableSet<Object> read(Kryo kryo, Input input, Class<ImmutableSet<Object>> type) {
+    int size = input.readInt(true);
+    ImmutableSet.Builder<Object> builder = ImmutableSet.builder();
+    for (int i = 0; i < size; ++i) {
+      builder.add(kryo.readClassAndObject(input));
+    }
+    return builder.build();
+  }
+
+  static void registerSerializers(Kryo kryo) {
+
+    // ImmutableList (abstract class)
+    //  +- EmptyImmutableSet
+    //  |   EmptyImmutableSet
+    //  +- SingletonImmutableSet
+    //  |   Optimized for Set with only 1 element.
+    //  +- RegularImmutableSet
+    //  |   RegularImmutableList
+    //  +- EnumImmutableSet
+    //  |   EnumImmutableSet
+
+    ImmutableSetSerializer serializer = new ImmutableSetSerializer();
+
+    kryo.register(ImmutableSet.class, serializer);
+
+    // Note:
+    //  Only registering above is good enough for serializing/deserializing.
+    //  but if using Kryo#copy, following is required.
+
+    kryo.register(ImmutableSet.of().getClass(), serializer);
+    kryo.register(ImmutableSet.of(1).getClass(), serializer);
+    kryo.register(ImmutableSet.of(1, 2, 3).getClass(), serializer);
+
+    kryo.register(Sets.immutableEnumSet(SomeEnum.A, SomeEnum.B, SomeEnum.C).getClass(), serializer);
+  }
+
+  private enum SomeEnum {
+    A,
+    B,
+    C
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableSortedSetSerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableSortedSetSerializer.java
new file mode 100644
index 0000000000..77f76632ea
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ImmutableSortedSetSerializer.java
@@ -0,0 +1,73 @@
+// 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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+import com.google.common.collect.ImmutableSortedSet;
+import java.util.Comparator;
+
+/** {@link Serializer} for {@link ImmutableSortedSet}. */
+class ImmutableSortedSetSerializer extends Serializer<ImmutableSortedSet<Object>> {
+
+  private ImmutableSortedSetSerializer() {
+    setImmutable(true);
+  }
+
+  @Override
+  public void write(Kryo kryo, Output output, ImmutableSortedSet<Object> object) {
+    kryo.writeClassAndObject(output, object.comparator());
+    output.writeInt(object.size(), true);
+    for (Object elt : object) {
+      kryo.writeClassAndObject(output, elt);
+    }
+  }
+
+  @Override
+  public ImmutableSortedSet<Object> read(
+      Kryo kryo, Input input, Class<ImmutableSortedSet<Object>> type) {
+    @SuppressWarnings("unchecked")
+    ImmutableSortedSet.Builder<Object> builder =
+        ImmutableSortedSet.orderedBy((Comparator<Object>) kryo.readClassAndObject(input));
+    int size = input.readInt(true);
+    for (int i = 0; i < size; ++i) {
+      builder.add(kryo.readClassAndObject(input));
+    }
+    return builder.build();
+  }
+
+  /**
+   * Creates a new {@link ImmutableSortedSetSerializer} and registers its serializer for the several
+   * ImmutableSortedSet related classes.
+   *
+   * @param kryo the {@link Kryo} instance to set the serializer on
+   */
+  static void registerSerializers(Kryo kryo) {
+
+    // ImmutableSortedSet (abstract class)
+    //  +- EmptyImmutableSortedSet
+    //  +- RegularImmutableSortedSet
+    //  +- DescendingImmutableSortedSet
+
+    ImmutableSortedSetSerializer serializer = new ImmutableSortedSetSerializer();
+
+    kryo.register(ImmutableSortedSet.class, serializer);
+    kryo.register(ImmutableSortedSet.of().getClass(), serializer);
+    kryo.register(ImmutableSortedSet.of("").getClass(), serializer);
+    kryo.register(ImmutableSortedSet.of().descendingSet().getClass(), serializer);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/MultimapSerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/MultimapSerializer.java
new file mode 100644
index 0000000000..40b9570c51
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/MultimapSerializer.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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.HashMultimap;
+import com.google.common.collect.LinkedHashMultimap;
+import com.google.common.collect.LinkedListMultimap;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.TreeMultimap;
+import java.util.Map;
+import java.util.function.Supplier;
+
+/** {@link Serializer} for {@link MultiMap} subclasses. */
+class MultimapSerializer<E, T extends Multimap<E, E>> extends Serializer<T> {
+
+  private final Supplier<T> create;
+
+  /**
+   * Constructor.
+   *
+   * @param create reference to T.create
+   */
+  private MultimapSerializer(Supplier<T> create) {
+    this.create = create;
+  }
+
+  @Override
+  public void write(Kryo kryo, Output output, T multimap) {
+    output.writeInt(multimap.size(), true);
+    for (Map.Entry<E, E> entry : multimap.entries()) {
+      kryo.writeClassAndObject(output, entry.getKey());
+      kryo.writeClassAndObject(output, entry.getValue());
+    }
+  }
+
+  @SuppressWarnings("unchecked")
+  @Override
+  public T read(Kryo kryo, Input input, Class<T> unusedType) {
+    T multimap = create.get();
+    int size = input.readInt(true);
+    for (int i = 0; i < size; ++i) {
+      multimap.put((E) kryo.readClassAndObject(input), (E) kryo.readClassAndObject(input));
+    }
+    return multimap;
+  }
+
+  /** Registers serializers for {@link Multimap} subclasses. */
+  static void registerSerializers(Kryo kryo) {
+    kryo.register(ArrayListMultimap.class, new MultimapSerializer<>(ArrayListMultimap::create));
+    kryo.register(HashMultimap.class, new MultimapSerializer<>(HashMultimap::create));
+    kryo.register(LinkedHashMultimap.class, new MultimapSerializer<>(LinkedHashMultimap::create));
+    kryo.register(LinkedListMultimap.class, new MultimapSerializer<>(LinkedListMultimap::create));
+    kryo.register(TreeMultimap.class, new MultimapSerializer<>(TreeMultimap::create));
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/PatternSerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/PatternSerializer.java
new file mode 100644
index 0000000000..704937ddda
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/PatternSerializer.java
@@ -0,0 +1,44 @@
+// 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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+import java.util.regex.Pattern;
+
+/** Serializer for {@link Pattern}. */
+class PatternSerializer extends Serializer<Pattern> {
+
+  PatternSerializer() {
+    setImmutable(true);
+  }
+
+  @Override
+  public void write(Kryo unusedKryo, Output output, Pattern pattern) {
+    output.writeString(pattern.pattern());
+    output.writeInt(pattern.flags(), true);
+  }
+
+  @Override
+  public Pattern read(Kryo unusedKryo, Input input, Class<Pattern> patternClass) {
+    return Pattern.compile(input.readString(), input.readInt(true));
+  }
+
+  static void registerSerializers(Kryo kryo) {
+    kryo.register(Pattern.class, new PatternSerializer());
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ProtoSerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ProtoSerializer.java
new file mode 100644
index 0000000000..432b406814
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ProtoSerializer.java
@@ -0,0 +1,65 @@
+// 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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.KryoException;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+import com.google.protobuf.AbstractMessage;
+import com.google.protobuf.InvalidProtocolBufferException;
+
+/**
+ * Serializer for protos.
+ *
+ * <p>A separate instance must be registered for each distinct proto.
+ */
+public class ProtoSerializer<T extends AbstractMessage> extends Serializer<T> {
+
+  private final ParseFromHandle<T> handle;
+
+  /** Wrapper for {@code parseFrom} references. */
+  @FunctionalInterface
+  public static interface ParseFromHandle<T> {
+    T parseFrom(byte[] bytes) throws InvalidProtocolBufferException;
+  }
+
+  /**
+   * Constructor.
+   *
+   * @param handle reference to T.parseFrom
+   */
+  public ProtoSerializer(ParseFromHandle<T> handle) {
+    setImmutable(true);
+    this.handle = handle;
+  }
+
+  @Override
+  public void write(Kryo kryo, Output output, T message) {
+    byte[] bytes = message.toByteArray();
+    output.writeInt(bytes.length, true);
+    output.writeBytes(bytes);
+  }
+
+  @Override
+  public T read(Kryo kryo, Input input, Class<T> type) {
+    try {
+      return handle.parseFrom(input.readBytes(input.readInt(true)));
+    } catch (InvalidProtocolBufferException e) {
+      throw new KryoException("Failed to parse " + type.getCanonicalName(), e);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/RegistrationUtil.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/RegistrationUtil.java
new file mode 100644
index 0000000000..c6f4efe8c0
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/RegistrationUtil.java
@@ -0,0 +1,38 @@
+// 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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.google.common.collect.Ordering;
+import java.util.Collections;
+
+/** Utility for registering Serializers defined in this package. */
+public interface RegistrationUtil {
+
+  static void registerSerializers(Kryo kryo) {
+    kryo.register(Ordering.natural().getClass());
+    kryo.register(Collections.reverseOrder().getClass());
+
+    ImmutableListSerializer.registerSerializers(kryo);
+    ImmutableMapSerializer.registerSerializers(kryo);
+    ImmutableMultimapSerializer.registerSerializers(kryo);
+    ImmutableSetSerializer.registerSerializers(kryo);
+    ImmutableSortedSetSerializer.registerSerializers(kryo);
+    MultimapSerializer.registerSerializers(kryo);
+    PatternSerializer.registerSerializers(kryo);
+    ReverseListSerializer.registerSerializers(kryo);
+    UnmodifiableNavigableSetSerializer.registerSerializers(kryo);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ReverseListSerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ReverseListSerializer.java
new file mode 100644
index 0000000000..326585398c
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/ReverseListSerializer.java
@@ -0,0 +1,86 @@
+// 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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.Lists;
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+
+/**
+ * A {@link Lists.ReverseList} Serializer.
+ *
+ * <p>Reverses the list before writing and then again when reading. This preserves the initial type
+ * as there is no other way to obtain Guava's "hidden" reversed list types.
+ */
+abstract class ReverseListSerializer extends Serializer<List<Object>> {
+
+  @Override
+  public void write(Kryo kryo, Output output, List<Object> list) {
+    List<Object> reversed = Lists.reverse(list);
+    output.writeInt(reversed.size(), true);
+    for (Object elt : reversed) {
+      kryo.writeClassAndObject(output, elt);
+    }
+  }
+
+  static void registerSerializers(Kryo kryo) {
+    kryo.register(getReversedLinkedClass(), new ReverseList());
+    kryo.register(getReversedArrayClass(), new RandomAccessReverseList());
+  }
+
+  @VisibleForTesting
+  static @SuppressWarnings("rawtypes") Class<? extends List> getReversedLinkedClass() {
+    return Lists.reverse(Lists.newLinkedList()).getClass();
+  }
+
+  @VisibleForTesting
+  static @SuppressWarnings("rawtypes") Class<? extends List> getReversedArrayClass() {
+    return Lists.reverse(Lists.newArrayList()).getClass();
+  }
+
+  /** A {@link Lists.ReverseList} implementation based on a {@link LinkedList}. */
+  private static class ReverseList extends ReverseListSerializer {
+
+    @Override
+    public List<Object> read(Kryo kryo, Input input, Class<List<Object>> type) {
+      LinkedList<Object> list = new LinkedList<>();
+      int length = input.readInt(true);
+      for (int i = 0; i < length; ++i) {
+        list.add(kryo.readClassAndObject(input));
+      }
+      return Lists.reverse(list);
+    }
+  }
+
+  /** A {@link Lists.ReverseList} implementation based on an {@link ArrayList}. */
+  private static class RandomAccessReverseList extends ReverseListSerializer {
+
+    @Override
+    public List<Object> read(Kryo kryo, Input input, Class<List<Object>> type) {
+      int length = input.readInt(true);
+      ArrayList<Object> list = new ArrayList<>(length);
+      for (int i = 0; i < length; ++i) {
+        list.add(kryo.readClassAndObject(input));
+      }
+      return Lists.reverse(list);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/UnmodifiableNavigableSetSerializer.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/UnmodifiableNavigableSetSerializer.java
new file mode 100644
index 0000000000..7785b6327d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers/UnmodifiableNavigableSetSerializer.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.serialization.serializers;
+
+import com.esotericsoftware.kryo.Kryo;
+import com.esotericsoftware.kryo.Serializer;
+import com.esotericsoftware.kryo.io.Input;
+import com.esotericsoftware.kryo.io.Output;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.ImmutableSortedSet;
+import com.google.common.collect.Sets;
+import java.lang.reflect.Field;
+import java.util.NavigableSet;
+import java.util.TreeSet;
+
+/** A {@link Serializer} for {@link ImmutableSortedSet}. */
+class UnmodifiableNavigableSetSerializer extends Serializer<NavigableSet<?>> {
+
+  private final Field delegate;
+
+  private UnmodifiableNavigableSetSerializer() {
+    setImmutable(true);
+    try {
+      Class<?> clazz = Class.forName(Sets.class.getCanonicalName() + "$UnmodifiableNavigableSet");
+      delegate = clazz.getDeclaredField("delegate");
+      delegate.setAccessible(true);
+    } catch (ReflectiveOperationException e) {
+      throw new IllegalStateException("Issues reflectively writing UnmodifiableNavigableSet", e);
+    }
+  }
+
+  private Object getDelegateFromUnmodifiableNavigableSet(NavigableSet<?> object) {
+    try {
+      return delegate.get(object);
+    } catch (IllegalAccessException e) {
+      throw new IllegalStateException("Issues reflectively writing UnmodifiableNavigableSet", e);
+    }
+  }
+
+  @Override
+  public void write(Kryo kryo, Output output, NavigableSet<?> object) {
+    // We want to preserve the underlying delegate class, so we need to reflectively get it and
+    // write it directly via kryo
+    kryo.writeClassAndObject(output, getDelegateFromUnmodifiableNavigableSet(object));
+  }
+
+  @Override
+  public NavigableSet<?> read(Kryo kryo, Input input, Class<NavigableSet<?>> type) {
+    return Sets.unmodifiableNavigableSet((NavigableSet<?>) kryo.readClassAndObject(input));
+  }
+
+  static void registerSerializers(Kryo kryo) {
+    kryo.register(getSerializedClass(), new UnmodifiableNavigableSetSerializer());
+  }
+
+  @VisibleForTesting
+  static @SuppressWarnings("rawtypes") Class<? extends NavigableSet> getSerializedClass() {
+    return Sets.unmodifiableNavigableSet(new TreeSet<Object>()).getClass();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/BUILD b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/BUILD
index ea7cf9b9bb..71f19b8310 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/BUILD
@@ -13,6 +13,7 @@ java_library(
         "//src/main/java/com/google/devtools/build/lib:syntax",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization:kryo",
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/serializers",
         "//src/main/java/com/google/devtools/build/lib/vfs",
         "//src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs",
         "//third_party:guava",
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializerTester.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializerTester.java
index e4fd2d1748..77319a3253 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializerTester.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/SerializerTester.java
@@ -23,12 +23,13 @@ import com.esotericsoftware.kryo.io.UnsafeInput;
 import com.esotericsoftware.kryo.io.UnsafeOutput;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.skyframe.serialization.serializers.RegistrationUtil;
 import java.io.ByteArrayOutputStream;
 import java.util.Random;
 import org.objenesis.instantiator.ObjectInstantiator;
 
 /** Utility for testing {@link Serializer} instances. */
-public class SerializerTester<T> {
+public class SerializerTester<SubjectT, SerializerT extends SubjectT> {
   public static final int DEFAULT_JUNK_INPUTS = 20;
   public static final int JUNK_LENGTH_UPPER_BOUND = 20;
 
@@ -48,20 +49,20 @@ public class SerializerTester<T> {
    *
    * <p>See {@link SerializerTester.Builder} for details.
    */
-  public static <T> SerializerTester.Builder<T> newBuilder(Class<T> type) {
+  public static <T> SerializerTester.Builder<T, T> newBuilder(Class<T> type) {
     return new SerializerTester.Builder<>(type);
   }
 
-  private final Class<T> type;
+  private final Class<SerializerT> type;
   private final Kryo kryo;
-  private final ImmutableList<T> subjects;
-  private final VerificationFunction<T> verificationFunction;
+  private final ImmutableList<SubjectT> subjects;
+  private final VerificationFunction<SubjectT> verificationFunction;
 
   private SerializerTester(
-      Class<T> type,
+      Class<SerializerT> type,
       Kryo kryo,
-      ImmutableList<T> subjects,
-      VerificationFunction<T> verificationFunction) {
+      ImmutableList<SubjectT> subjects,
+      VerificationFunction<SubjectT> verificationFunction) {
     this.type = type;
     this.kryo = kryo;
     Preconditions.checkState(!subjects.isEmpty(), "No subjects provided");
@@ -77,18 +78,18 @@ public class SerializerTester<T> {
 
   /** Runs serialization/deserialization tests. */
   void testSerializeDeserialize() throws Exception {
-    for (T subject : subjects) {
+    for (SubjectT subject : subjects) {
       byte[] serialized = toBytes(subject);
-      T deserialized = fromBytes(serialized);
+      SubjectT deserialized = fromBytes(serialized);
       verificationFunction.verifyDeserialized(subject, deserialized);
     }
   }
 
   /** Runs serialized bytes stability tests. */
   void testStableSerialization() throws Exception {
-    for (T subject : subjects) {
+    for (SubjectT subject : subjects) {
       byte[] serialized = toBytes(subject);
-      T deserialized = fromBytes(serialized);
+      SubjectT deserialized = fromBytes(serialized);
       byte[] reserialized = toBytes(deserialized);
       assertThat(reserialized).isEqualTo(serialized);
     }
@@ -99,8 +100,9 @@ public class SerializerTester<T> {
    *
    * <p>Verifies that the Serializer only throws KryoException or IndexOutOfBoundsException.
    *
-   * <p>TODO(shahan): Allowing IndexOutOfBoundsException here is not ideal, but Kryo itself encodes
-   * lengths in the stream and seeking to random lengths triggers this.
+   * <p>TODO(shahan): Allowing IndexOutOfBoundsException and NegativeArraySizeException here is not
+   * ideal, but Kryo itself encodes lengths in the stream and seeking to random lengths triggers
+   * this.
    */
   void testDeserializeJunkData() {
     Random rng = new Random(0);
@@ -112,7 +114,7 @@ public class SerializerTester<T> {
         UnsafeInput input = new UnsafeInput(junkData);
         kryo.readObject(input, type);
         // OK. Junk string was coincidentally parsed.
-      } catch (IndexOutOfBoundsException | KryoException e) {
+      } catch (IndexOutOfBoundsException | NegativeArraySizeException | KryoException e) {
         // OK. Deserialization of junk failed.
         ++numFailures;
       }
@@ -120,11 +122,11 @@ public class SerializerTester<T> {
     assertThat(numFailures).isAtLeast(1);
   }
 
-  private T fromBytes(byte[] bytes) {
+  private SubjectT fromBytes(byte[] bytes) {
     return kryo.readObject(new UnsafeInput(bytes), type);
   }
 
-  private byte[] toBytes(T subject) {
+  private byte[] toBytes(SubjectT subject) {
     ByteArrayOutputStream byteOut = new ByteArrayOutputStream();
     UnsafeOutput out = new UnsafeOutput(byteOut);
     kryo.writeObject(out, subject);
@@ -133,42 +135,54 @@ public class SerializerTester<T> {
   }
 
   /** Builder for {@link SerializerTester}. */
-  public static class Builder<T> {
-    private final Class<T> type;
+  public static class Builder<SubjectT, SerializerT extends SubjectT> {
+    private final Class<SerializerT> type;
     private final Kryo kryo;
-    private final ImmutableList.Builder<T> subjectsBuilder = ImmutableList.builder();
-    private VerificationFunction<T> verificationFunction =
+    private final ImmutableList.Builder<SubjectT> subjectsBuilder = ImmutableList.builder();
+    private VerificationFunction<SubjectT> verificationFunction =
         (original, deserialized) -> assertThat(deserialized).isEqualTo(original);
 
-    private Builder(Class<T> type) {
+    private Builder(Class<SerializerT> type) {
       this.type = type;
       this.kryo = new Kryo();
+      RegistrationUtil.registerSerializers(kryo);
       kryo.setRegistrationRequired(true);
     }
 
-    public <X> Builder<T> register(Class<X> type, Serializer<X> serializer) {
+    public Builder(Class<SubjectT> unusedSubjectType, Class<SerializerT> type) {
+      this(type);
+    }
+
+    public Builder<SubjectT, SerializerT> registerSerializer(Serializer<SerializerT> serializer) {
+      kryo.register(type, serializer);
+      return this;
+    }
+
+    public <X> Builder<SubjectT, SerializerT> register(Class<X> type, Serializer<X> serializer) {
       kryo.register(type, serializer);
       return this;
     }
 
-    public <X> Builder<T> register(Class<X> type) {
+    public <X> Builder<SubjectT, SerializerT> register(Class<X> type) {
       kryo.register(type);
       return this;
     }
 
-    public <X> Builder<T> register(Class<X> type, ObjectInstantiator instantiator) {
+    public <X> Builder<SubjectT, SerializerT> register(
+        Class<X> type, ObjectInstantiator instantiator) {
       kryo.register(type).setInstantiator(instantiator);
       return this;
     }
 
     /** Adds subjects to be tested for serialization/deserialization. */
     @SafeVarargs
-    public final Builder<T> addSubjects(@SuppressWarnings("unchecked") T... subjects) {
+    public final Builder<SubjectT, SerializerT> addSubjects(
+        @SuppressWarnings("unchecked") SubjectT... subjects) {
       return addSubjects(ImmutableList.copyOf(subjects));
     }
 
     /** Adds subjects to be tested for serialization/deserialization. */
-    public Builder<T> addSubjects(ImmutableList<T> subjects) {
+    public Builder<SubjectT, SerializerT> addSubjects(ImmutableList<SubjectT> subjects) {
       subjectsBuilder.addAll(subjects);
       return this;
     }
@@ -179,12 +193,13 @@ public class SerializerTester<T> {
      * <p>Default is simple equality assertion, a custom version may be provided for more, or less,
      * detailed checks.
      */
-    public Builder<T> setVerificationFunction(VerificationFunction<T> verificationFunction) {
+    public Builder<SubjectT, SerializerT> setVerificationFunction(
+        VerificationFunction<SubjectT> verificationFunction) {
       this.verificationFunction = Preconditions.checkNotNull(verificationFunction);
       return this;
     }
 
-    public Builder<T> setRegistrationRequired(boolean isRequired) {
+    public Builder<SubjectT, SerializerT> setRegistrationRequired(boolean isRequired) {
       kryo.setRegistrationRequired(isRequired);
       return this;
     }
@@ -195,7 +210,7 @@ public class SerializerTester<T> {
     }
 
     /** Creates a new {@link SerializerTester} from this builder. */
-    private SerializerTester<T> build() {
+    private SerializerTester<SubjectT, SerializerT> build() {
       return new SerializerTester<>(type, kryo, subjectsBuilder.build(), verificationFunction);
     }
   }