diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD
index eb3b78d..18b40a4 100644
--- a/src/main/java/com/google/devtools/build/lib/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -37,6 +37,7 @@
         "//src/main/java/com/google/devtools/build/lib/rules/genquery:srcs",
         "//src/main/java/com/google/devtools/build/lib/rules/genrule:srcs",
         "//src/main/java/com/google/devtools/build/lib/rules/objc:srcs",
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization:srcs",
         "//src/main/java/com/google/devtools/build/lib/analysis/featurecontrol:srcs",
         "//src/main/java/com/google/devtools/build/lib/analysis/platform:srcs",
         "//src/main/java/com/google/devtools/build/lib/analysis/whitelisting:srcs",
@@ -641,6 +642,7 @@
         "//src/main/java/com/google/devtools/build/lib/buildeventstream/proto:build_event_stream_java_proto",
         "//src/main/java/com/google/devtools/build/lib/causes",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
         "//src/main/java/com/google/devtools/build/skyframe",
         "//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
         "//src/main/java/com/google/devtools/common/options",
diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/AppleCommandLineOptions.java b/src/main/java/com/google/devtools/build/lib/rules/apple/AppleCommandLineOptions.java
index 36c9449..268c47d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/apple/AppleCommandLineOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/apple/AppleCommandLineOptions.java
@@ -14,6 +14,8 @@
 
 package com.google.devtools.build.lib.rules.apple;
 
+import static com.google.devtools.build.lib.skyframe.serialization.SerializationCommonUtils.STRING_LIST_CODEC;
+
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Strings;
 import com.google.common.collect.ImmutableList;
@@ -24,6 +26,10 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.rules.apple.AppleConfiguration.ConfigurationDistinguisher;
 import com.google.devtools.build.lib.rules.apple.ApplePlatform.PlatformType;
+import com.google.devtools.build.lib.skyframe.serialization.EnumCodec;
+import com.google.devtools.build.lib.skyframe.serialization.FastStringCodec;
+import com.google.devtools.build.lib.skyframe.serialization.LabelCodec;
+import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
@@ -34,6 +40,9 @@
 import com.google.devtools.common.options.OptionDocumentationCategory;
 import com.google.devtools.common.options.OptionEffectTag;
 import com.google.devtools.common.options.OptionMetadataTag;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
 import java.util.List;
 
 /**
@@ -470,6 +479,8 @@
         super(AppleBitcodeMode.class, "apple bitcode mode");
       }
     }
+
+    static final EnumCodec<AppleBitcodeMode> CODEC = new EnumCodec<>(AppleBitcodeMode.class);
   }
 
   @Override
@@ -492,6 +503,65 @@
     return host;
   }
 
+  void serialize(CodedOutputStream out) throws IOException, SerializationException {
+    out.writeBoolNoTag(mandatoryMinimumVersion);
+    xcodeVersion.serialize(out);
+    iosSdkVersion.serialize(out);
+    watchOsSdkVersion.serialize(out);
+    tvOsSdkVersion.serialize(out);
+    macOsSdkVersion.serialize(out);
+    iosMinimumOs.serialize(out);
+    watchosMinimumOs.serialize(out);
+    tvosMinimumOs.serialize(out);
+    macosMinimumOs.serialize(out);
+    FastStringCodec.INSTANCE.serialize(iosCpu, out);
+    LabelCodec.INSTANCE.serialize(appleCrosstoolTop, out);
+    PlatformType.CODEC.serialize(applePlatformType, out);
+    FastStringCodec.INSTANCE.serialize(appleSplitCpu, out);
+    ConfigurationDistinguisher.CODEC.serialize(configurationDistinguisher, out);
+    STRING_LIST_CODEC.serialize((ImmutableList<String>) iosMultiCpus, out);
+    STRING_LIST_CODEC.serialize((ImmutableList<String>) watchosCpus, out);
+    STRING_LIST_CODEC.serialize((ImmutableList<String>) tvosCpus, out);
+    STRING_LIST_CODEC.serialize((ImmutableList<String>) macosCpus, out);
+    LabelCodec.INSTANCE.serialize(defaultProvisioningProfile, out);
+    LabelCodec.INSTANCE.serialize(xcodeVersionConfig, out);
+    FastStringCodec.INSTANCE.serialize(xcodeToolchain, out);
+    AppleBitcodeMode.CODEC.serialize(appleBitcodeMode, out);
+    out.writeBoolNoTag(enableAppleCrosstoolTransition);
+    out.writeBoolNoTag(targetUsesAppleCrosstool);
+  }
+
+  static AppleCommandLineOptions deserialize(CodedInputStream in)
+      throws IOException, SerializationException {
+    AppleCommandLineOptions result = new AppleCommandLineOptions();
+    result.mandatoryMinimumVersion = in.readBool();
+    result.xcodeVersion = DottedVersion.deserialize(in);
+    result.iosSdkVersion = DottedVersion.deserialize(in);
+    result.watchOsSdkVersion = DottedVersion.deserialize(in);
+    result.tvOsSdkVersion = DottedVersion.deserialize(in);
+    result.macOsSdkVersion = DottedVersion.deserialize(in);
+    result.iosMinimumOs = DottedVersion.deserialize(in);
+    result.watchosMinimumOs = DottedVersion.deserialize(in);
+    result.tvosMinimumOs = DottedVersion.deserialize(in);
+    result.macosMinimumOs = DottedVersion.deserialize(in);
+    result.iosCpu = FastStringCodec.INSTANCE.deserialize(in);
+    result.appleCrosstoolTop = LabelCodec.INSTANCE.deserialize(in);
+    result.applePlatformType = PlatformType.CODEC.deserialize(in);
+    result.appleSplitCpu = FastStringCodec.INSTANCE.deserialize(in);
+    result.configurationDistinguisher = ConfigurationDistinguisher.CODEC.deserialize(in);
+    result.iosMultiCpus = STRING_LIST_CODEC.deserialize(in);
+    result.watchosCpus = STRING_LIST_CODEC.deserialize(in);
+    result.tvosCpus = STRING_LIST_CODEC.deserialize(in);
+    result.macosCpus = STRING_LIST_CODEC.deserialize(in);
+    result.defaultProvisioningProfile = LabelCodec.INSTANCE.deserialize(in);
+    result.xcodeVersionConfig = LabelCodec.INSTANCE.deserialize(in);
+    result.xcodeToolchain = FastStringCodec.INSTANCE.deserialize(in);
+    result.appleBitcodeMode = AppleBitcodeMode.CODEC.deserialize(in);
+    result.enableAppleCrosstoolTransition = in.readBool();
+    result.targetUsesAppleCrosstool = in.readBool();
+    return result;
+  }
+
   /** Converter for the Apple configuration distinguisher. */
   public static final class ConfigurationDistinguisherConverter
       extends EnumConverter<ConfigurationDistinguisher> {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/AppleConfiguration.java b/src/main/java/com/google/devtools/build/lib/rules/apple/AppleConfiguration.java
index 3ab182a..b2a1a98 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/apple/AppleConfiguration.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/apple/AppleConfiguration.java
@@ -31,13 +31,20 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.rules.apple.AppleCommandLineOptions.AppleBitcodeMode;
 import com.google.devtools.build.lib.rules.apple.ApplePlatform.PlatformType;
+import com.google.devtools.build.lib.skyframe.serialization.EnumCodec;
+import com.google.devtools.build.lib.skyframe.serialization.FastStringCodec;
+import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.util.Preconditions;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Map;
+import java.util.Objects;
 import javax.annotation.Nullable;
 
 /** A configuration containing flags required for Apple platforms and tools. */
@@ -99,10 +106,11 @@
   @Nullable private final Label defaultProvisioningProfileLabel;
   private final boolean mandatoryMinimumVersion;
 
+  @VisibleForTesting
   AppleConfiguration(
       AppleCommandLineOptions options,
-      String cpu,
-      XcodeVersionProperties xcodeVersionProperties,
+      String iosCpu,
+      @Nullable DottedVersion xcodeVersion,
       DottedVersion iosSdkVersion,
       DottedVersion iosMinimumOs,
       DottedVersion watchosSdkVersion,
@@ -126,8 +134,8 @@
         Preconditions.checkNotNull(macosSdkVersion, "macOsSdkVersion");
     this.macosMinimumOs = Preconditions.checkNotNull(macosMinimumOs, "macOsMinimumOs");
 
-    this.xcodeVersion = xcodeVersionProperties.getXcodeVersion().orNull();
-    this.iosCpu = iosCpuFromCpu(cpu);
+    this.xcodeVersion = xcodeVersion;
+    this.iosCpu = iosCpu;
     this.appleSplitCpu = Preconditions.checkNotNull(options.appleSplitCpu, "appleSplitCpu");
     this.applePlatformType =
         Preconditions.checkNotNull(options.applePlatformType, "applePlatformType");
@@ -670,6 +678,81 @@
         .build();
   }
 
+  @Override
+  public boolean equals(Object obj) {
+    if (this == obj) {
+      return true;
+    }
+    if (!(obj instanceof AppleConfiguration)) {
+      return false;
+    }
+    AppleConfiguration that = (AppleConfiguration) obj;
+    return this.options.equals(that.options)
+        && Objects.equals(this.xcodeVersion, that.xcodeVersion)
+        && this.iosSdkVersion.equals(that.iosSdkVersion)
+        && this.iosMinimumOs.equals(that.iosMinimumOs)
+        && this.watchosSdkVersion.equals(that.watchosSdkVersion)
+        && this.watchosMinimumOs.equals(that.watchosMinimumOs)
+        && this.tvosSdkVersion.equals(that.tvosSdkVersion)
+        && this.tvosMinimumOs.equals(that.tvosMinimumOs)
+        && this.macosSdkVersion.equals(that.macosSdkVersion)
+        && this.macosMinimumOs.equals(that.macosMinimumOs);
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(
+        options,
+        xcodeVersion,
+        iosSdkVersion,
+        iosMinimumOs,
+        watchosSdkVersion,
+        watchosMinimumOs,
+        tvosSdkVersion,
+        tvosMinimumOs,
+        macosSdkVersion,
+        macosMinimumOs);
+  }
+
+  void serialize(CodedOutputStream out) throws IOException, SerializationException {
+    options.serialize(out);
+    out.writeStringNoTag(iosCpu);
+    if (xcodeVersion == null) {
+      out.writeBoolNoTag(false);
+    } else {
+      out.writeBoolNoTag(true);
+      xcodeVersion.serialize(out);
+    }
+    iosSdkVersion.serialize(out);
+    iosMinimumOs.serialize(out);
+    watchosSdkVersion.serialize(out);
+    watchosMinimumOs.serialize(out);
+    tvosSdkVersion.serialize(out);
+    tvosMinimumOs.serialize(out);
+    macosSdkVersion.serialize(out);
+    macosMinimumOs.serialize(out);
+  }
+
+  static AppleConfiguration deserialize(CodedInputStream in)
+      throws IOException, SerializationException {
+    AppleCommandLineOptions options = AppleCommandLineOptions.deserialize(in);
+    String iosCpu = FastStringCodec.INSTANCE.deserialize(in);
+    boolean hasXcodeVersion = in.readBool();
+    DottedVersion xcodeVersion = hasXcodeVersion ? DottedVersion.deserialize(in) : null;
+    return new AppleConfiguration(
+        options,
+        iosCpu,
+        xcodeVersion,
+        DottedVersion.deserialize(in),
+        DottedVersion.deserialize(in),
+        DottedVersion.deserialize(in),
+        DottedVersion.deserialize(in),
+        DottedVersion.deserialize(in),
+        DottedVersion.deserialize(in),
+        DottedVersion.deserialize(in),
+        DottedVersion.deserialize(in));
+  }
+
   /**
    * Loads {@link AppleConfiguration} from build options.
    */
@@ -701,8 +784,8 @@
       AppleConfiguration configuration =
           new AppleConfiguration(
               appleOptions,
-              cpu,
-              xcodeVersionProperties,
+              iosCpuFromCpu(cpu),
+              xcodeVersionProperties.getXcodeVersion().orNull(),
               iosSdkVersion,
               iosMinimumOsVersion,
               watchosSdkVersion,
@@ -781,5 +864,8 @@
     public String getFileSystemName() {
       return fileSystemName;
     }
+
+    static final EnumCodec<ConfigurationDistinguisher> CODEC =
+        new EnumCodec<>(ConfigurationDistinguisher.class);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java b/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java
index 6be2024..bccee16 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java
@@ -19,6 +19,7 @@
 import com.google.devtools.build.lib.packages.Info;
 import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.packages.Provider;
+import com.google.devtools.build.lib.skyframe.serialization.EnumCodec;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
@@ -299,5 +300,7 @@
     public void repr(SkylarkPrinter printer) {
       printer.append(toString());
     }
+
+    static final EnumCodec<PlatformType> CODEC = new EnumCodec<>(PlatformType.class);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/BUILD b/src/main/java/com/google/devtools/build/lib/rules/apple/BUILD
index 15ae78d..b6fb301 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/apple/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/rules/apple/BUILD
@@ -14,15 +14,14 @@
         "//src/main/java/com/google/devtools/build/lib:events",
         "//src/main/java/com/google/devtools/build/lib:packages-internal",
         "//src/main/java/com/google/devtools/build/lib:preconditions",
-        "//src/main/java/com/google/devtools/build/lib:shell",
         "//src/main/java/com/google/devtools/build/lib:skylarkinterface",
         "//src/main/java/com/google/devtools/build/lib:syntax",
-        "//src/main/java/com/google/devtools/build/lib:vfs",
-        "//src/main/java/com/google/devtools/build/lib/actions",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
         "//src/main/java/com/google/devtools/common/options",
         "//third_party:guava",
         "//third_party:jsr305",
+        "//third_party/protobuf:protobuf_java",
     ],
 )
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/DottedVersion.java b/src/main/java/com/google/devtools/build/lib/rules/apple/DottedVersion.java
index bdbc910..5fbbef5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/apple/DottedVersion.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/apple/DottedVersion.java
@@ -26,10 +26,14 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Objects;
 import java.util.regex.Matcher;
 import java.util.regex.Pattern;
+import javax.annotation.Nullable;
 
 /**
  * Represents a value with multiple components, separated by periods, for example {@code 4.5.6} or
@@ -249,13 +253,35 @@
     printer.append(stringRepresentation);
   }
 
+  void serialize(CodedOutputStream out) throws IOException {
+    out.writeInt32NoTag(components.size());
+    for (Component component : components) {
+      component.serialize(out);
+    }
+    out.writeStringNoTag(stringRepresentation);
+    out.writeInt32NoTag(numOriginalComponents);
+  }
+
+  static DottedVersion deserialize(CodedInputStream in) throws IOException {
+    int numComponents = in.readInt32();
+    // TODO(janakr: Presize this if/when https://github.com/google/guava/issues/196 is resolved.
+    ImmutableList.Builder<Component> components = ImmutableList.builder();
+    for (int i = 0; i < numComponents; i++) {
+      components.add(Component.deserialize(in));
+    }
+    return new DottedVersion(components.build(), in.readString(), in.readInt32());
+  }
+
   private static final class Component implements Comparable<Component> {
     private final int firstNumber;
-    private final String alphaSequence;
+    @Nullable private final String alphaSequence;
     private final int secondNumber;
     private final String stringRepresentation;
 
-    public Component(int firstNumber, String alphaSequence, int secondNumber,
+    public Component(
+        int firstNumber,
+        @Nullable String alphaSequence,
+        int secondNumber,
         String stringRepresentation) {
       this.firstNumber = firstNumber;
       this.alphaSequence = alphaSequence;
@@ -293,5 +319,25 @@
     public String toString() {
       return stringRepresentation;
     }
+
+    void serialize(CodedOutputStream out) throws IOException {
+      if (alphaSequence == null) {
+        out.writeBoolNoTag(false);
+      } else {
+        out.writeBoolNoTag(true);
+        out.writeStringNoTag(alphaSequence);
+      }
+      out.writeInt32NoTag(firstNumber);
+      out.writeInt32NoTag(secondNumber);
+      out.writeStringNoTag(stringRepresentation);
+    }
+
+    static Component deserialize(CodedInputStream in) throws IOException {
+      String alphaSequence = null;
+      if (in.readBool()) {
+        alphaSequence = in.readString();
+      }
+      return new Component(in.readInt32(), alphaSequence, in.readInt32(), in.readString());
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseValue.java
index 5d23707..49cd581 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseValue.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.pkgcache.LoadingResult;
 import com.google.devtools.build.lib.pkgcache.TestFilter;
+import com.google.devtools.build.lib.skyframe.serialization.NotSerializableRuntimeException;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TestSuiteExpansionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TestSuiteExpansionValue.java
index 1da1fee..8bc2f2b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TestSuiteExpansionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TestSuiteExpansionValue.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.skyframe.serialization.NotSerializableRuntimeException;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TestsInSuiteValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TestsInSuiteValue.java
index bed1646..63a55fb 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TestsInSuiteValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TestsInSuiteValue.java
@@ -19,6 +19,7 @@
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.packages.TargetUtils;
+import com.google.devtools.build.lib.skyframe.serialization.NotSerializableRuntimeException;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
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
new file mode 100644
index 0000000..6de7a8e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BUILD
@@ -0,0 +1,20 @@
+# TODO(janakr): find out how to avoid this default visibility and still have
+# automatic BUILD-file generation.
+package(default_visibility = ["//src:__subpackages__"])
+
+java_library(
+    name = "serialization",
+    srcs = glob(["*.java"]),
+    deps = [
+        "//src/main/java/com/google/devtools/build/lib:vfs",
+        "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
+        "//third_party:guava",
+        "//third_party/protobuf:protobuf_java",
+    ],
+)
+
+filegroup(
+    name = "srcs",
+    srcs = glob(["**"]),
+)
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BaseCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BaseCodec.java
new file mode 100644
index 0000000..dd286fc
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BaseCodec.java
@@ -0,0 +1,31 @@
+// Copyright 2017 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;
+
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+/** An opaque interface for codecs that just reveals the {@link Class} of its objects. */
+interface BaseCodec<T> {
+  /**
+   * Returns the class of the objects serialized/deserialized by this codec.
+   *
+   * <p>This is useful for automatically dispatching to the correct codec, e.g. in {@link
+   * ObjectCodecs} and {@link BaseCodecMap}. It may also be useful for automatically registering
+   * codecs for {@link SkyKey}s and {@link SkyValue}s instead of using the current manual mapping
+   * (b/26186886).
+   */
+  Class<T> getEncodedClass();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/EnumCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/EnumCodec.java
new file mode 100644
index 0000000..523620e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/EnumCodec.java
@@ -0,0 +1,59 @@
+// Copyright 2017 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;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
+
+/** Codec for an enum. */
+public class EnumCodec<T extends Enum<T>> implements ObjectCodec<T> {
+
+  private final Class<T> enumClass;
+
+  /**
+   * A cached copy of T.values(), to avoid allocating an array upon every deserialization operation.
+   */
+  private final ImmutableList<T> values;
+
+  public EnumCodec(Class<T> enumClass) {
+    this.enumClass = enumClass;
+    this.values = ImmutableList.copyOf(enumClass.getEnumConstants());
+  }
+
+  @Override
+  public Class<T> getEncodedClass() {
+    return enumClass;
+  }
+
+  @Override
+  public void serialize(T value, CodedOutputStream codedOut) throws IOException {
+    Preconditions.checkNotNull(value, "Enum value for %s is null", enumClass);
+    codedOut.writeEnumNoTag(value.ordinal());
+  }
+
+  @Override
+  public T deserialize(CodedInputStream codedIn) throws SerializationException, IOException {
+    int ordinal = codedIn.readEnum();
+    try {
+      return values.get(ordinal);
+    } catch (ArrayIndexOutOfBoundsException e) {
+      throw new SerializationException(
+          "Invalid ordinal for " + enumClass.getName() + " enum: " + ordinal, e);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/FastStringCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/FastStringCodec.java
new file mode 100644
index 0000000..23bf38b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/FastStringCodec.java
@@ -0,0 +1,140 @@
+// Copyright 2017 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;
+
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
+import java.lang.reflect.Field;
+import java.nio.charset.StandardCharsets;
+import java.security.AccessController;
+import java.security.PrivilegedActionException;
+import java.security.PrivilegedExceptionAction;
+import sun.misc.Unsafe;
+
+/**
+ * Similar to {@link StringCodec}, except with deserialization optimized for ascii data. It can
+ * still handle UTF-8, though less efficiently than {@link StringCodec}. Should be used when the
+ * majority of the data passing through will be ascii.
+ */
+public class FastStringCodec implements ObjectCodec<String> {
+  public static final FastStringCodec INSTANCE = new FastStringCodec();
+
+  private static final Unsafe theUnsafe;
+  private static final long STRING_VALUE_OFFSET;
+
+  private static final String EMPTY_STRING = "";
+
+  static {
+    theUnsafe = getUnsafe();
+    try {
+      // String's 'value' field stores its char[]. If this field changes name or type then the
+      // reflective check below will fail. We can reasonably expect our approach to be stable for
+      // now, but things are likely to change in java 9, hopefully in a way which obsoletes this
+      // optimization.
+      Field valueField = String.class.getDeclaredField("value");
+      Class<?> valueFieldType = valueField.getType();
+      if (!valueFieldType.equals(char[].class)) {
+        throw new AssertionError(
+            "Expected String's value field to be char[], but was " + valueFieldType);
+      }
+      STRING_VALUE_OFFSET = theUnsafe.objectFieldOffset(valueField);
+    } catch (NoSuchFieldException | SecurityException e) {
+      throw new AssertionError("Failed to find String's 'value' offset", e);
+    }
+  }
+
+  @Override
+  public Class<String> getEncodedClass() {
+    return String.class;
+  }
+
+  @Override
+  public void serialize(String string, CodedOutputStream codedOut) throws IOException {
+    codedOut.writeStringNoTag(string);
+  }
+
+  @Override
+  public String deserialize(CodedInputStream codedIn) throws IOException {
+    int length = codedIn.readInt32();
+    if (length == 0) {
+      return EMPTY_STRING;
+    }
+
+    char[] maybeDecoded = new char[length];
+    for (int i = 0; i < length; i++) {
+      // Read one byte at a time to avoid creating a new ByteString/copy of the underlying array.
+      byte b = codedIn.readRawByte();
+      // Check highest order bit, if it's set we've crossed into extended ascii/utf8.
+      if ((b & 0x80) == 0) {
+        maybeDecoded[i] = (char) b;
+      } else {
+        // Fail, we encountered a non-ascii byte. Copy what we have so far plus and then the rest
+        // of the data into a buffer and let String's constructor do the UTF-8 decoding work.
+        byte[] decodeFrom = new byte[length];
+        for (int j = 0; j < i; j++) {
+          decodeFrom[j] = (byte) maybeDecoded[j];
+        }
+        decodeFrom[i] = b;
+        for (int j = i + 1; j < length; j++) {
+          decodeFrom[j] = codedIn.readRawByte();
+        }
+        return new String(decodeFrom, StandardCharsets.UTF_8);
+      }
+    }
+
+    try {
+      String result = (String) theUnsafe.allocateInstance(String.class);
+      theUnsafe.putObject(result, STRING_VALUE_OFFSET, maybeDecoded);
+      return result;
+    } catch (Exception e) {
+      // This should only catch InstantiationException, but that makes IntelliJ unhappy for
+      // some reason; it insists that that exception cannot be thrown from here, even though it
+      // is set to JDK 8
+      throw new IllegalStateException("Could not create string", e);
+    }
+  }
+
+  /**
+   * Get a reference to {@link sun.misc.Unsafe} or throw an {@link AssertionError} if failing to do
+   * so. Failure is highly unlikely, but possible if the underlying VM stores unsafe in an
+   * unexpected location.
+   */
+  private static Unsafe getUnsafe() {
+    try {
+      // sun.misc.Unsafe is intentionally difficult to get a hold of - it gives us the power to
+      // do things like access raw memory and segfault the JVM.
+      return AccessController.doPrivileged(
+          new PrivilegedExceptionAction<Unsafe>() {
+            @Override
+            public Unsafe run() throws Exception {
+              Class<Unsafe> unsafeClass = Unsafe.class;
+              // Unsafe usually exists in the field 'theUnsafe', however check all fields
+              // in case it's somewhere else in this VM's version of Unsafe.
+              for (Field f : unsafeClass.getDeclaredFields()) {
+                f.setAccessible(true);
+                Object fieldValue = f.get(null);
+                if (unsafeClass.isInstance(fieldValue)) {
+                  return unsafeClass.cast(fieldValue);
+                }
+              }
+              throw new AssertionError("Failed to find sun.misc.Unsafe instance");
+            }
+          });
+    } catch (PrivilegedActionException pae) {
+      throw new AssertionError("Unable to get sun.misc.Unsafe", pae);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableListCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableListCodec.java
new file mode 100644
index 0000000..1b54d1f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableListCodec.java
@@ -0,0 +1,62 @@
+// Copyright 2017 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;
+
+import com.google.common.collect.ImmutableList;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
+
+/** Encodes a list of elements using a specified {@link ObjectCodec}. */
+public class ImmutableListCodec<T> implements ObjectCodec<ImmutableList<T>> {
+
+  private final ObjectCodec<T> codec;
+
+  public ImmutableListCodec(ObjectCodec<T> codec) {
+    this.codec = codec;
+  }
+
+  @SuppressWarnings("unchecked")
+  @Override
+  public Class<ImmutableList<T>> getEncodedClass() {
+    // Compiler doesn't like cast from Class<ImmutableList> -> Class<ImmutableList<T>>, but it
+    // does allow what we see below. Type is lost at runtime anyway, so while gross this works.
+    return (Class<ImmutableList<T>>) ((Class<?>) ImmutableList.class);
+  }
+
+  @Override
+  public void serialize(ImmutableList<T> list, CodedOutputStream codedOut)
+      throws SerializationException, IOException {
+    codedOut.writeInt32NoTag(list.size());
+    for (T item : list) {
+      codec.serialize(item, codedOut);
+    }
+  }
+
+  @Override
+  public ImmutableList<T> deserialize(CodedInputStream codedIn)
+      throws SerializationException, IOException {
+    int length = codedIn.readInt32();
+    if (length < 0) {
+      throw new SerializationException("Expected non-negative length: " + length);
+    }
+
+    ImmutableList.Builder<T> builder = ImmutableList.builder();
+    for (int i = 0; i < length; i++) {
+      builder.add(codec.deserialize(codedIn));
+    }
+    return builder.build();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LabelCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LabelCodec.java
new file mode 100644
index 0000000..6f8881d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LabelCodec.java
@@ -0,0 +1,49 @@
+// Copyright 2017 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;
+
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
+
+/** Custom serialization logic for {@link Label}s. */
+public class LabelCodec implements ObjectCodec<Label> {
+  public static final LabelCodec INSTANCE = new LabelCodec();
+
+  // TODO(michajlo): Share single instance of package id codec among all the codecs.
+  private final PackageIdentifierCodec packageIdCodec = new PackageIdentifierCodec();
+  private final ObjectCodec<String> stringCodec = new FastStringCodec();
+
+  @Override
+  public Class<Label> getEncodedClass() {
+    return Label.class;
+  }
+
+  @Override
+  public void serialize(Label label, CodedOutputStream codedOut)
+      throws IOException, SerializationException {
+    packageIdCodec.serialize(label.getPackageIdentifier(), codedOut);
+    stringCodec.serialize(label.getName(), codedOut);
+  }
+
+  @Override
+  public Label deserialize(CodedInputStream codedIn) throws SerializationException, IOException {
+    PackageIdentifier packageId = packageIdCodec.deserialize(codedIn);
+    String name = stringCodec.deserialize(codedIn);
+    return Label.createUnvalidated(packageId, name);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/NotSerializableRuntimeException.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/NotSerializableRuntimeException.java
similarity index 93%
rename from src/main/java/com/google/devtools/build/lib/skyframe/NotSerializableRuntimeException.java
rename to src/main/java/com/google/devtools/build/lib/skyframe/serialization/NotSerializableRuntimeException.java
index c54bd45..78dcc25 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/NotSerializableRuntimeException.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/NotSerializableRuntimeException.java
@@ -11,7 +11,8 @@
 // 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;
+
+package com.google.devtools.build.lib.skyframe.serialization;
 
 import java.io.Serializable;
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodec.java
new file mode 100644
index 0000000..b700923
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ObjectCodec.java
@@ -0,0 +1,47 @@
+// Copyright 2017 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;
+
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
+
+/**
+ * Generic object serialization/deserialization. Implementations should serialize values
+ * deterministically.
+ */
+public interface ObjectCodec<T> extends BaseCodec<T> {
+
+  /**
+   * Serializes {@code obj}, inverse of {@link #deserialize(CodedInputStream)}.
+   *
+   * @param obj the object to serialize
+   * @param codedOut the {@link CodedOutputStream} to write this object into. Implementations need
+   *     not call {@link CodedOutputStream#flush()}, this should be handled by the caller.
+   * @throws SerializationException on failure to serialize
+   * @throws IOException on {@link IOException} during serialization
+   */
+  void serialize(T obj, CodedOutputStream codedOut) throws SerializationException, IOException;
+
+  /**
+   * Deserializes from {@code codedIn}, inverse of {@link #serialize(Object, CodedOutputStream)}.
+   *
+   * @param codedIn the {@link CodedInputStream} to read the serialized object from
+   * @return the object deserialized from {@code codedIn}
+   * @throws SerializationException on failure to deserialize
+   * @throws IOException on {@link IOException} during deserialization
+   */
+  T deserialize(CodedInputStream codedIn) throws SerializationException, IOException;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/PackageIdentifierCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/PackageIdentifierCodec.java
new file mode 100644
index 0000000..73aede6
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/PackageIdentifierCodec.java
@@ -0,0 +1,49 @@
+// Copyright 2017 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;
+
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
+
+/** Custom serialization logic for {@link PackageIdentifier}s. */
+class PackageIdentifierCodec implements ObjectCodec<PackageIdentifier> {
+
+  private final RepositoryNameCodec repoNameCodec = new RepositoryNameCodec();
+  private final PathFragmentCodec pathFragmentCodec = new PathFragmentCodec();
+
+  @Override
+  public Class<PackageIdentifier> getEncodedClass() {
+    return PackageIdentifier.class;
+  }
+
+  @Override
+  public void serialize(PackageIdentifier pkgId, CodedOutputStream codedOut)
+      throws IOException, SerializationException {
+    repoNameCodec.serialize(pkgId.getRepository(), codedOut);
+    pathFragmentCodec.serialize(pkgId.getPackageFragment(), codedOut);
+  }
+
+  @Override
+  public PackageIdentifier deserialize(CodedInputStream codedIn)
+      throws IOException, SerializationException {
+    RepositoryName repoName = repoNameCodec.deserialize(codedIn);
+    PathFragment pathFragment = pathFragmentCodec.deserialize(codedIn);
+    return PackageIdentifier.create(repoName, pathFragment);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/PathFragmentCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/PathFragmentCodec.java
new file mode 100644
index 0000000..7438f6d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/PathFragmentCodec.java
@@ -0,0 +1,55 @@
+// Copyright 2017 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;
+
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
+
+/** Custom serialization for {@link PathFragment}s. */
+class PathFragmentCodec implements ObjectCodec<PathFragment> {
+
+  private final ObjectCodec<String> stringCodec = new FastStringCodec();
+
+  @Override
+  public Class<PathFragment> getEncodedClass() {
+    return PathFragment.class;
+  }
+
+  @Override
+  public void serialize(PathFragment pathFragment, CodedOutputStream codedOut)
+      throws IOException, SerializationException {
+    codedOut.writeInt32NoTag(pathFragment.getDriveLetter());
+    codedOut.writeBoolNoTag(pathFragment.isAbsolute());
+    codedOut.writeInt32NoTag(pathFragment.segmentCount());
+    for (int i = 0; i < pathFragment.segmentCount(); i++) {
+      stringCodec.serialize(pathFragment.getSegment(i), codedOut);
+    }
+  }
+
+  @Override
+  public PathFragment deserialize(CodedInputStream codedIn)
+      throws IOException, SerializationException {
+    char driveLetter = (char) codedIn.readInt32();
+    boolean isAbsolute = codedIn.readBool();
+    int segmentCount = codedIn.readInt32();
+    String[] segments = new String[segmentCount];
+    for (int i = 0; i < segmentCount; i++) {
+      segments[i] = stringCodec.deserialize(codedIn);
+    }
+    return PathFragment.create(driveLetter, isAbsolute, segments);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/RepositoryNameCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/RepositoryNameCodec.java
new file mode 100644
index 0000000..c9d0976
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/RepositoryNameCodec.java
@@ -0,0 +1,56 @@
+// Copyright 2017 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;
+
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
+
+/** Custom serialization for {@link RepositoryName}. */
+class RepositoryNameCodec implements ObjectCodec<RepositoryName> {
+
+  @Override
+  public Class<RepositoryName> getEncodedClass() {
+    return RepositoryName.class;
+  }
+
+  @Override
+  public void serialize(RepositoryName repoName, CodedOutputStream codedOut) throws IOException {
+    boolean isMain = repoName.isMain();
+    // Main is by far the most common. Use boolean to short-circuit string encoding on
+    // serialization and byte[]/ByteString creation on deserialization.
+    codedOut.writeBoolNoTag(isMain);
+    if (!isMain) {
+      codedOut.writeStringNoTag(repoName.getName());
+    }
+  }
+
+  @Override
+  public RepositoryName deserialize(CodedInputStream codedIn)
+      throws SerializationException, IOException {
+    boolean isMain = codedIn.readBool();
+    if (isMain) {
+      return RepositoryName.MAIN;
+    }
+    try {
+      // We can read the string we wrote back as bytes to avoid string decoding/copying.
+      return SerializationCommonUtils.deserializeRepoName(codedIn.readBytes());
+    } catch (LabelSyntaxException e) {
+      throw new SerializationException("Failed to deserialize RepositoryName", e);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationCommonUtils.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationCommonUtils.java
new file mode 100644
index 0000000..50d81b4
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationCommonUtils.java
@@ -0,0 +1,41 @@
+// Copyright 2017 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;
+
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.protobuf.ByteString;
+
+/** Common utilities for serialization. */
+public class SerializationCommonUtils {
+  public static final ImmutableListCodec<String> STRING_LIST_CODEC =
+      new ImmutableListCodec<>(FastStringCodec.INSTANCE);
+  private static final ByteString DEFAULT_REPOSITORY =
+      ByteString.copyFromUtf8(RepositoryName.DEFAULT.getName());
+  private static final ByteString MAIN_REPOSITORY =
+      ByteString.copyFromUtf8(RepositoryName.MAIN.getName());
+
+  public static RepositoryName deserializeRepoName(ByteString repoNameBytes)
+      throws LabelSyntaxException {
+    // We expect MAIN_REPOSITORY the vast majority of the time, so check for it first.
+    if (repoNameBytes.equals(MAIN_REPOSITORY)) {
+      return RepositoryName.MAIN;
+    } else if (repoNameBytes.equals(DEFAULT_REPOSITORY)) {
+      return RepositoryName.DEFAULT;
+    } else {
+      return RepositoryName.create(repoNameBytes.toStringUtf8());
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationException.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationException.java
new file mode 100644
index 0000000..1477e3a
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationException.java
@@ -0,0 +1,50 @@
+// Copyright 2017 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;
+
+import java.io.NotSerializableException;
+
+/** Exception signaling a failure to Serialize or Deserialize an Object. */
+public class SerializationException extends Exception {
+
+  public SerializationException(String msg) {
+    super(msg);
+  }
+
+  public SerializationException(String msg, Throwable cause) {
+    super(msg, cause);
+  }
+
+  // No SerializationException(Throwable) overload because serialization errors should always
+  // provide as much context as possible.
+
+  /**
+   * {@link SerializationException} indicating that Blaze has no serialization schema for an object
+   * or type of object.
+   */
+  public static class NoCodecException extends SerializationException {
+    NoCodecException(String message) {
+      super(message);
+    }
+
+    NoCodecException(String message, NotSerializableException e) {
+      super(message, e);
+    }
+
+    NoCodecException(String message, NotSerializableRuntimeException e) {
+      super(message, e);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/StringCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/StringCodec.java
new file mode 100644
index 0000000..4b1bc70
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/StringCodec.java
@@ -0,0 +1,38 @@
+// Copyright 2017 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;
+
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
+
+/** Dead-simple serialization for {@link String}s. */
+public class StringCodec implements ObjectCodec<String> {
+
+  @Override
+  public Class<String> getEncodedClass() {
+    return String.class;
+  }
+
+  @Override
+  public void serialize(String str, CodedOutputStream codedOut) throws IOException {
+    codedOut.writeStringNoTag(str);
+  }
+
+  @Override
+  public String deserialize(CodedInputStream codedIn) throws IOException {
+    return codedIn.readString();
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/rules/apple/AppleConfigurationSerializationTest.java b/src/test/java/com/google/devtools/build/lib/rules/apple/AppleConfigurationSerializationTest.java
new file mode 100644
index 0000000..532dac6
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/rules/apple/AppleConfigurationSerializationTest.java
@@ -0,0 +1,96 @@
+// Copyright 2017 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.rules.apple;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.skyframe.serialization.AbstractObjectCodecTest;
+import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
+import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.IOException;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for serialization of {@link AppleConfiguration}. */
+@RunWith(JUnit4.class)
+public class AppleConfigurationSerializationTest
+    extends AbstractObjectCodecTest<AppleConfiguration> {
+  public AppleConfigurationSerializationTest() {
+    super(
+        new ObjectCodec<AppleConfiguration>() {
+          @Override
+          public void serialize(AppleConfiguration obj, CodedOutputStream codedOut)
+              throws SerializationException, IOException {
+            obj.serialize(codedOut);
+          }
+
+          @Override
+          public AppleConfiguration deserialize(CodedInputStream codedIn)
+              throws SerializationException, IOException {
+            return AppleConfiguration.deserialize(codedIn);
+          }
+
+          @Override
+          public Class<AppleConfiguration> getEncodedClass() {
+            return AppleConfiguration.class;
+          }
+        },
+        subject());
+  }
+
+  private static AppleConfiguration subject() {
+    AppleCommandLineOptions options = new AppleCommandLineOptions();
+    options.mandatoryMinimumVersion = false;
+    options.xcodeVersion = DottedVersion.fromString("1.0");
+    options.iosSdkVersion = DottedVersion.fromString("2.0");
+    options.watchOsSdkVersion = DottedVersion.fromString("3.0");
+    options.tvOsSdkVersion = DottedVersion.fromString("4.0");
+    options.macOsSdkVersion = DottedVersion.fromString("5.0");
+    options.iosMinimumOs = DottedVersion.fromString("6.1beta3.7");
+    options.watchosMinimumOs = DottedVersion.fromString("7.0");
+    options.tvosMinimumOs = DottedVersion.fromString("8.0");
+    options.macosMinimumOs = DottedVersion.fromString("9.0");
+    options.iosCpu = "ioscpu1";
+    options.appleCrosstoolTop = Label.parseAbsoluteUnchecked("//apple/crosstool:top");
+    options.applePlatformType = ApplePlatform.PlatformType.WATCHOS;
+    options.appleSplitCpu = "appleSplitCpu1";
+    options.configurationDistinguisher =
+        AppleConfiguration.ConfigurationDistinguisher.APPLEBIN_TVOS;
+    options.iosMultiCpus = ImmutableList.of("iosMultiCpu1", "iosMultiCpu2");
+    options.watchosCpus = ImmutableList.of("watchosCpu1", "watchosCpu2", "watchosCpu3");
+    options.tvosCpus = ImmutableList.of("tvosCpu1");
+    options.macosCpus = ImmutableList.of();
+    options.defaultProvisioningProfile = Label.parseAbsoluteUnchecked("//default/provisioning");
+    options.xcodeVersionConfig = Label.parseAbsoluteUnchecked("//xcode/version:config");
+    options.xcodeToolchain = "xcodeToolchain1";
+    options.appleBitcodeMode = AppleCommandLineOptions.AppleBitcodeMode.EMBEDDED_MARKERS;
+    options.enableAppleCrosstoolTransition = false;
+    options.targetUsesAppleCrosstool = true;
+    return new AppleConfiguration(
+        options,
+        "iosCpuArg",
+        DottedVersion.fromString("10.0"),
+        DottedVersion.fromString("11.0"),
+        DottedVersion.fromString("12.0"),
+        DottedVersion.fromString("13.0"),
+        DottedVersion.fromString("14.0"),
+        DottedVersion.fromString("15.0"),
+        DottedVersion.fromString("16.0"),
+        DottedVersion.fromString("17.0"),
+        DottedVersion.fromString("18.0"));
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/rules/apple/BUILD b/src/test/java/com/google/devtools/build/lib/rules/apple/BUILD
index 2b85ae5..89015b0 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/apple/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/rules/apple/BUILD
@@ -4,9 +4,38 @@
     visibility = ["//src/test/java/com/google/devtools/build/lib:__pkg__"],
 )
 
+SERIALIZATION_TEST_SRCS = ["AppleConfigurationSerializationTest.java"]
+
+java_library(
+    name = "AppleConfigurationSerializationTest_lib",
+    testonly = 1,
+    srcs = SERIALIZATION_TEST_SRCS,
+    deps = [
+        "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//src/main/java/com/google/devtools/build/lib/rules/apple",
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
+        "//src/test/java/com/google/devtools/build/lib/skyframe/serialization:serialization-test-base",
+        "//third_party:guava",
+        "//third_party:junit4",
+        "//third_party/protobuf:protobuf_java",
+    ],
+)
+
+java_test(
+    name = "AppleConfigurationSerializationTest",
+    test_class = "com.google.devtools.build.lib.AllTests",
+    runtime_deps = [
+        ":AppleConfigurationSerializationTest_lib",
+        "//src/test/java/com/google/devtools/build/lib:test_runner",
+    ],
+)
+
 java_library(
     name = "AppleRulesTests_lib",
-    srcs = glob(["*.java"]),
+    srcs = glob(
+        ["*.java"],
+        exclude = SERIALIZATION_TEST_SRCS,
+    ),
     deps = [
         "//src/main/java/com/google/devtools/build/lib:build-base",
         "//src/main/java/com/google/devtools/build/lib/rules/apple",
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/BUILD b/src/test/java/com/google/devtools/build/lib/skyframe/BUILD
index fd6714e..8bc5a45 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/BUILD
@@ -1,6 +1,9 @@
 filegroup(
     name = "srcs",
-    srcs = glob(["**"]) + ["//src/test/java/com/google/devtools/build/lib/skyframe/packages:srcs"],
+    srcs = glob(["**"]) + [
+        "//src/test/java/com/google/devtools/build/lib/skyframe/packages:srcs",
+        "//src/test/java/com/google/devtools/build/lib/skyframe/serialization:srcs",
+    ],
     visibility = ["//src/test/java/com/google/devtools/build/lib:__pkg__"],
 )
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/AbstractObjectCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/AbstractObjectCodecTest.java
new file mode 100644
index 0000000..4fa00b3
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/AbstractObjectCodecTest.java
@@ -0,0 +1,107 @@
+// Copyright 2017 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;
+
+import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.fail;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.protobuf.CodedInputStream;
+import java.io.IOException;
+import java.nio.charset.StandardCharsets;
+import javax.annotation.Nullable;
+import org.junit.Before;
+import org.junit.Test;
+
+/** Common ObjectCodec tests. */
+public abstract class AbstractObjectCodecTest<T> {
+
+  @Nullable protected ObjectCodec<T> underTest;
+  @Nullable protected ImmutableList<T> subjects;
+
+  /**
+   * Override to false to skip testDeserializeBadDataThrowsSerializationException(). Codecs that
+   * cannot distinguish good and bad data should do this.
+   */
+  protected boolean shouldTestDeserializeBadData = true;
+
+  /** Construct with the given codec and subjects. */
+  protected AbstractObjectCodecTest(
+      ObjectCodec<T> underTest, @SuppressWarnings("unchecked") T... subjects) {
+    this.underTest = underTest;
+    this.subjects = ImmutableList.copyOf(subjects);
+  }
+
+  /**
+   * Construct without a codec and subjects. They must be set in the subclass's constructor instead.
+   *
+   * <p>This is useful if the logic for creating the codec and/or subjects is non-trivial. Using
+   * this super constructor, the logic can be placed in the subclass's constructor; whereas if using
+   * the above super constructor, the logic must be factored into a static method.
+   */
+  protected AbstractObjectCodecTest() {}
+
+  @Before
+  public void checkInitialized() {
+    Preconditions.checkNotNull(underTest);
+    Preconditions.checkNotNull(subjects);
+  }
+
+  @Test
+  public void testSuccessfulSerializationDeserialization() throws Exception {
+    for (T subject : subjects) {
+      byte[] serialized = toBytes(subject);
+      Object deserialized = fromBytes(serialized);
+      verifyDeserialization(deserialized, subject);
+    }
+  }
+
+  @Test
+  public void testSerializationRoundTripBytes() throws Exception {
+    for (T subject : subjects) {
+      byte[] serialized = toBytes(subject);
+      T deserialized = fromBytes(serialized);
+      byte[] reserialized = toBytes(deserialized);
+      assertThat(reserialized).isEqualTo(serialized);
+    }
+  }
+
+  @Test
+  public void testDeserializeBadDataThrowsSerializationException() {
+    if (!shouldTestDeserializeBadData) {
+      return;
+    }
+    try {
+      underTest.deserialize(CodedInputStream.newInstance("junk".getBytes(StandardCharsets.UTF_8)));
+      fail("Expected exception");
+    } catch (SerializationException | IOException e) {
+      // Expected.
+    }
+  }
+
+  protected T fromBytes(byte[] bytes) throws SerializationException, IOException {
+    return TestUtils.fromBytes(underTest, bytes);
+  }
+
+  /** Serialize subject using the {@link ObjectCodec} under test. */
+  protected byte[] toBytes(T subject) throws IOException, SerializationException {
+    return TestUtils.toBytes(underTest, subject);
+  }
+
+  protected void verifyDeserialization(Object deserialized, T subject) {
+    assertThat(deserialized).isEqualTo(subject);
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/BUILD b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/BUILD
new file mode 100644
index 0000000..4111713
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/BUILD
@@ -0,0 +1,63 @@
+TEST_BASE_FILES = [
+    "AbstractObjectCodecTest.java",
+    "TestUtils.java",
+]
+
+java_library(
+    name = "serialization-test-base",
+    testonly = 1,
+    srcs = TEST_BASE_FILES,
+    visibility = [
+        "//src/test/java/com/google/devtools/build/lib:__subpackages__",
+    ],
+    deps = [
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
+        "//third_party:guava",
+        "//third_party:jsr305",
+        "//third_party:junit4",
+        "//third_party:truth",
+        "//third_party/protobuf:protobuf_java",
+    ],
+)
+
+java_library(
+    name = "serialization-tests",
+    testonly = 1,
+    srcs = glob(
+        [
+            "*.java",
+        ],
+        exclude = TEST_BASE_FILES,
+    ),
+    deps = [
+        ":serialization-test-base",
+        "//src/main/java/com/google/devtools/build/lib:build-base",
+        "//src/main/java/com/google/devtools/build/lib:packages-internal",
+        "//src/main/java/com/google/devtools/build/lib:util",
+        "//src/main/java/com/google/devtools/build/lib:vfs",
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
+        "//third_party:guava",
+        "//third_party:guava-testlib",
+        "//third_party:jsr305",
+        "//third_party:junit4",
+        "//third_party:mockito",
+        "//third_party:truth",
+    ],
+)
+
+java_test(
+    name = "SerializationTests",
+    test_class = "com.google.devtools.build.lib.AllTests",
+    runtime_deps = [
+        ":serialization-tests",
+        "//src/test/java/com/google/devtools/build/lib:test_runner",
+    ],
+)
+
+filegroup(
+    name = "srcs",
+    srcs = glob(["**"]),
+    visibility = [
+        "//src/test/java/com/google/devtools/build/lib/skyframe:__subpackages__",
+    ],
+)
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/EnumCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/EnumCodecTest.java
new file mode 100644
index 0000000..c71d554
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/EnumCodecTest.java
@@ -0,0 +1,33 @@
+// Copyright 2017 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;
+
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for {@link EnumCodec}. */
+@RunWith(JUnit4.class)
+public class EnumCodecTest extends AbstractObjectCodecTest<EnumCodecTest.DummyEnum> {
+
+  /** Test enum (dummy comment for lint). */
+  public enum DummyEnum {
+    DUMB_ONE,
+    DUMB_TWO
+  }
+
+  public EnumCodecTest() {
+    super(new EnumCodec<>(DummyEnum.class), DummyEnum.DUMB_ONE, DummyEnum.DUMB_TWO);
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/FastStringCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/FastStringCodecTest.java
new file mode 100644
index 0000000..6aef73e
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/FastStringCodecTest.java
@@ -0,0 +1,53 @@
+// Copyright 2017 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;
+
+import com.google.common.testing.EqualsTester;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for {@link FastStringCodec}. */
+@RunWith(JUnit4.class)
+public class FastStringCodecTest extends AbstractObjectCodecTest<String> {
+
+  public FastStringCodecTest() {
+    super(
+        new FastStringCodec(),
+        "ow now brown cow. ow now brown cow",
+        "（╯°□°）╯︵┻━┻ string with utf8/ascii",
+        "string with ascii/utf8 （╯°□°）╯︵┻━┻",
+        "last character utf8 ╯",
+        "last char only non-ascii ƒ",
+        "ƒ",
+        "╯",
+        "",
+        Character.toString((char) 0xc3));;
+  }
+
+  // hashCode is stored in String. Because we're using Unsafe to bypass standard String
+  // constructors, make sure it still works.
+  @Test
+  public void testEqualsAndHashCodePreserved() throws Exception {
+    String original1 = "hello world";
+    String original2 = "dlrow olleh";
+
+    // Equals tester tests equals and hash code.
+    new EqualsTester()
+        .addEqualityGroup(original1, fromBytes(toBytes(original1)))
+        .addEqualityGroup(original2, fromBytes(toBytes(original2)))
+        .testEquals();
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableListCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableListCodecTest.java
new file mode 100644
index 0000000..23f3855
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableListCodecTest.java
@@ -0,0 +1,33 @@
+// Copyright 2017 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;
+
+import com.google.common.collect.ImmutableList;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for {@link ImmutableListCodec}. */
+@RunWith(JUnit4.class)
+public class ImmutableListCodecTest extends AbstractObjectCodecTest<ImmutableList<String>> {
+
+  @SuppressWarnings("unchecked")
+  public ImmutableListCodecTest() {
+    super(
+        new ImmutableListCodec<>(new StringCodec()),
+        ImmutableList.of(),
+        ImmutableList.of("foo"),
+        ImmutableList.of("bar", "baz"));
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/LabelCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/LabelCodecTest.java
new file mode 100644
index 0000000..4dc1b14
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/LabelCodecTest.java
@@ -0,0 +1,29 @@
+// Copyright 2017 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;
+
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Basic tests for {@link LabelCodec}. */
+@RunWith(JUnit4.class)
+public class LabelCodecTest extends AbstractObjectCodecTest<Label> {
+
+  public LabelCodecTest() throws LabelSyntaxException {
+    super(new LabelCodec(), Label.parseAbsolute("//foo/bar:baz"));
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/PackageIdentifierCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/PackageIdentifierCodecTest.java
new file mode 100644
index 0000000..9bc860a
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/PackageIdentifierCodecTest.java
@@ -0,0 +1,30 @@
+// Copyright 2017 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;
+
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Basic tests for {@link PackageIdentifierCodec}. */
+@RunWith(JUnit4.class)
+public class PackageIdentifierCodecTest extends AbstractObjectCodecTest<PackageIdentifier> {
+
+  public PackageIdentifierCodecTest() throws Exception {
+    super(
+        new PackageIdentifierCodec(), PackageIdentifier.create("@foo", PathFragment.create("bar")));
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/PathFragmentCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/PathFragmentCodecTest.java
new file mode 100644
index 0000000..4ce91f8
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/PathFragmentCodecTest.java
@@ -0,0 +1,28 @@
+// Copyright 2017 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;
+
+import com.google.devtools.build.lib.vfs.PathFragment;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Basic tests for {@link PathFragmentCodec}. */
+@RunWith(JUnit4.class)
+public class PathFragmentCodecTest extends AbstractObjectCodecTest<PathFragment> {
+
+  public PathFragmentCodecTest() {
+    super(new PathFragmentCodec(), PathFragment.create("/a/path/fragment/with/lots/of/parts"));
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/RepositoryNameCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/RepositoryNameCodecTest.java
new file mode 100644
index 0000000..97e38ed
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/RepositoryNameCodecTest.java
@@ -0,0 +1,54 @@
+// Copyright 2017 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;
+
+import static org.junit.Assert.fail;
+
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import java.io.IOException;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for {@link RepositoryNameCodec}. */
+@RunWith(JUnit4.class)
+public class RepositoryNameCodecTest extends AbstractObjectCodecTest<RepositoryName> {
+
+  // Set 0th byte (isMain) false, so that we'll try to read a string from the rest of the
+  // data and fail.
+  public static final byte[] INVALID_ENCODED_REPOSITORY_NAME = new byte[] {0, 10, 9, 8, 7};
+
+  public RepositoryNameCodecTest() throws LabelSyntaxException {
+    super(
+        new RepositoryNameCodec(),
+        RepositoryName.create(RepositoryName.DEFAULT.getName()),
+        RepositoryName.create(RepositoryName.MAIN.getName()),
+        RepositoryName.create("@externalandshouldntexistinthisworkspace"));
+  }
+
+  // The default bad data test from AbstractObjectCodecTest doesn't play nice with boolean prefixed
+  // encodings.
+  @Override
+  @Test
+  public void testDeserializeBadDataThrowsSerializationException() {
+    try {
+      fromBytes(INVALID_ENCODED_REPOSITORY_NAME);
+      fail("Expected exception");
+    } catch (SerializationException | IOException e) {
+      // Expected.
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/StringCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/StringCodecTest.java
new file mode 100644
index 0000000..423ffdc
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/StringCodecTest.java
@@ -0,0 +1,27 @@
+// Copyright 2017 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;
+
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Basic tests for {@link StringCodec}. */
+@RunWith(JUnit4.class)
+public class StringCodecTest extends AbstractObjectCodecTest<String> {
+
+  public StringCodecTest() {
+    super(new StringCodec(), "usually precomputed and supports weird unicodes: （╯°□°）╯︵┻━┻ ");
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/TestUtils.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/TestUtils.java
new file mode 100644
index 0000000..df84b38
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/TestUtils.java
@@ -0,0 +1,42 @@
+// Copyright 2017 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;
+
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+
+/** Helpers for serialization tests. */
+class TestUtils {
+
+  private TestUtils() {}
+
+  /** Serialize a value to a new byte array. */
+  static <T> byte[] toBytes(ObjectCodec<T> codec, T value)
+      throws IOException, SerializationException {
+    ByteArrayOutputStream bytes = new ByteArrayOutputStream();
+    CodedOutputStream codedOut = CodedOutputStream.newInstance(bytes);
+    codec.serialize(value, codedOut);
+    codedOut.flush();
+    return bytes.toByteArray();
+  }
+
+  /** Deserialize a value from a byte array. */
+  static <T> T fromBytes(ObjectCodec<T> codec, byte[] bytes)
+      throws SerializationException, IOException {
+    return codec.deserialize(CodedInputStream.newInstance(bytes));
+  }
+}