Enable memoization in LeafObjectCodec.

This will be used to serialize SkyKeys that need to then be looked up
in Skyframe during deserialization. To avoid the complexity of having to
add a 2nd layer of continuations to codec implementations or making them
blocking, they will use LeafObjectCodec and be immediate by construction.

Since LeafObjectCodec is always MEMOIZE_AFTER, it can never have object
cycles and can use an abbreviated form of memoization which doesn't
require memoization IDs.

PiperOrigin-RevId: 628404708
Change-Id: I8095828e3d939c5dd6743d3012e906e5c5ef31f8
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java
index ea8eb19..d8076b2 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java
@@ -28,8 +28,9 @@
 import com.google.common.collect.MapDifference;
 import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.skyframe.serialization.LeafDeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.LeafObjectCodec;
-import com.google.devtools.build.lib.skyframe.serialization.SerializationDependencyProvider;
+import com.google.devtools.build.lib.skyframe.serialization.LeafSerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.devtools.build.lib.skyframe.serialization.VisibleForSerialization;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.SerializationConstant;
@@ -487,23 +488,19 @@
 
     @Override
     public void serialize(
-        SerializationDependencyProvider dependencies,
-        BuildOptions options,
-        CodedOutputStream codedOut)
+        LeafSerializationContext context, BuildOptions options, CodedOutputStream codedOut)
         throws SerializationException, IOException {
-      if (!dependencies.getDependency(OptionsChecksumCache.class).prime(options)) {
+      if (!context.getDependency(OptionsChecksumCache.class).prime(options)) {
         throw new SerializationException("Failed to prime cache for " + options.checksum());
       }
-      stringCodec().serialize(dependencies, options.checksum(), codedOut);
+      context.serializeLeaf(options.checksum(), stringCodec(), codedOut);
     }
 
     @Override
-    public BuildOptions deserialize(
-        SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+    public BuildOptions deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
         throws SerializationException, IOException {
-      String checksum = stringCodec().deserialize(dependencies, codedIn);
-      BuildOptions result =
-          dependencies.getDependency(OptionsChecksumCache.class).getOptions(checksum);
+      String checksum = context.deserializeLeaf(codedIn, stringCodec());
+      BuildOptions result = context.getDependency(OptionsChecksumCache.class).getOptions(checksum);
       if (result == null) {
         throw new SerializationException("No options instance for " + checksum);
       }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/NativeAspectClass.java b/src/main/java/com/google/devtools/build/lib/packages/NativeAspectClass.java
index c1ea40c..e150584 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/NativeAspectClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/NativeAspectClass.java
@@ -16,8 +16,9 @@
 import static com.google.devtools.build.lib.skyframe.serialization.strings.UnsafeStringCodec.stringCodec;
 
 import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.skyframe.serialization.LeafDeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.LeafObjectCodec;
-import com.google.devtools.build.lib.skyframe.serialization.SerializationDependencyProvider;
+import com.google.devtools.build.lib.skyframe.serialization.LeafSerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.errorprone.annotations.Keep;
 import com.google.protobuf.CodedInputStream;
@@ -47,24 +48,22 @@
 
     @Override
     public void serialize(
-        SerializationDependencyProvider dependencies,
-        NativeAspectClass obj,
-        CodedOutputStream codedOut)
+        LeafSerializationContext context, NativeAspectClass obj, CodedOutputStream codedOut)
         throws SerializationException, IOException {
-      RuleClassProvider ruleClassProvider = dependencies.getDependency(RuleClassProvider.class);
+      RuleClassProvider ruleClassProvider = context.getDependency(RuleClassProvider.class);
       NativeAspectClass storedAspect = ruleClassProvider.getNativeAspectClass(obj.getKey());
       Preconditions.checkState(
           obj == storedAspect, "Not stored right: %s %s %s", obj, storedAspect, ruleClassProvider);
-      stringCodec().serialize(dependencies, obj.getKey(), codedOut);
+      context.serializeLeaf(obj.getKey(), stringCodec(), codedOut);
     }
 
     @Override
     public NativeAspectClass deserialize(
-        SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+        LeafDeserializationContext context, CodedInputStream codedIn)
         throws SerializationException, IOException {
-      String aspectKey = stringCodec().deserialize(dependencies, codedIn);
+      String aspectKey = context.deserializeLeaf(codedIn, stringCodec());
       return Preconditions.checkNotNull(
-          dependencies.getDependency(RuleClassProvider.class).getNativeAspectClass(aspectKey),
+          context.getDependency(RuleClassProvider.class).getNativeAspectClass(aspectKey),
           aspectKey);
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleCodec.java b/src/main/java/com/google/devtools/build/lib/packages/RuleCodec.java
index 1000ace..316fefd 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleCodec.java
@@ -15,8 +15,9 @@
 package com.google.devtools.build.lib.packages;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.devtools.build.lib.skyframe.serialization.LeafDeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.LeafObjectCodec;
-import com.google.devtools.build.lib.skyframe.serialization.SerializationDependencyProvider;
+import com.google.devtools.build.lib.skyframe.serialization.LeafSerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
@@ -42,14 +43,13 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, Rule obj, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, Rule obj, CodedOutputStream codedOut)
       throws SerializationException {
     throw new SerializationException(String.format(SERIALIZATION_ERROR_TEMPLATE, obj));
   }
 
   @Override
-  public Rule deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public Rule deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException {
     throw new SerializationException(DESERIALIZATION_ERROR_TEMPLATE);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/AsyncDeserializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/AsyncDeserializationContext.java
index 7ad101d..a0d907d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/AsyncDeserializationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/AsyncDeserializationContext.java
@@ -36,7 +36,7 @@
  *       to guarantee that the provided value is complete due to the cycle.
  * </ul>
  */
-public interface AsyncDeserializationContext extends SerializationDependencyProvider {
+public interface AsyncDeserializationContext extends LeafDeserializationContext {
   /** Defines a way to set a field in a given object. */
   interface FieldSetter<T> {
     /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BigIntegerCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BigIntegerCodec.java
index 94d2654..cf28ae2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BigIntegerCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BigIntegerCodec.java
@@ -28,14 +28,13 @@
 
   @Override
   public void serialize(
-      SerializationDependencyProvider dependencies, BigInteger obj, CodedOutputStream codedOut)
+      LeafSerializationContext context, BigInteger obj, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeByteArrayNoTag(obj.toByteArray());
   }
 
   @Override
-  public BigInteger deserialize(
-      SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public BigInteger deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException {
     return new BigInteger(codedIn.readByteArray());
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BitSetCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BitSetCodec.java
index 8a6bfec..a31b3f6 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BitSetCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BitSetCodec.java
@@ -28,16 +28,15 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, BitSet obj, CodedOutputStream codedOut)
-      throws IOException {
+  public void serialize(LeafSerializationContext context, BitSet obj, CodedOutputStream codedOut)
+      throws IOException, SerializationException {
     long[] data = obj.toLongArray();
-    DELEGATE.serialize(dependencies, data, codedOut);
+    context.serializeLeaf(data, DELEGATE, codedOut);
   }
 
   @Override
-  public BitSet deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
-      throws IOException {
-    return BitSet.valueOf(DELEGATE.deserialize(dependencies, codedIn));
+  public BitSet deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
+      throws IOException, SerializationException {
+    return BitSet.valueOf(context.deserializeLeaf(codedIn, DELEGATE));
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BooleanCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BooleanCodec.java
index ec45613..1cff1c6 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BooleanCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/BooleanCodec.java
@@ -27,14 +27,13 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, Boolean value, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, Boolean value, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeBoolNoTag(value);
   }
 
   @Override
-  public Boolean deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public Boolean deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws IOException {
     return codedIn.readBool();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ByteArrayCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ByteArrayCodec.java
index 744ab45..d3165fe 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ByteArrayCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ByteArrayCodec.java
@@ -26,14 +26,13 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, byte[] obj, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, byte[] obj, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeByteArrayNoTag(obj);
   }
 
   @Override
-  public byte[] deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public byte[] deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws IOException {
     return codedIn.readByteArray();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ByteStringCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ByteStringCodec.java
index b421058..bad3ad3 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ByteStringCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ByteStringCodec.java
@@ -29,14 +29,14 @@
 
   @Override
   public void serialize(
-      SerializationDependencyProvider dependencies, ByteString obj, CodedOutputStream codedOut)
+      LeafSerializationContext context, ByteString obj, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeBytesNoTag(obj);
   }
 
   @Override
-  public ByteString deserialize(
-      SerializationDependencyProvider dependencies, CodedInputStream codedIn) throws IOException {
+  public ByteString deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
+      throws IOException {
     return codedIn.readBytes();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ClassCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ClassCodec.java
index 9745a8f..3184738 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ClassCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ClassCodec.java
@@ -37,26 +37,24 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, Class<?> obj, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, Class<?> obj, CodedOutputStream codedOut)
       throws SerializationException, IOException {
     codedOut.writeBoolNoTag(obj.isPrimitive());
     if (obj.isPrimitive()) {
       codedOut.writeInt32NoTag(Preconditions.checkNotNull(PRIMITIVE_CLASS_INDEX_MAP.get(obj), obj));
     } else {
-      stringCodec().serialize(dependencies, obj.getName(), codedOut);
+      context.serializeLeaf(obj.getName(), stringCodec(), codedOut);
     }
   }
 
   @Override
-  public Class<?> deserialize(
-      SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public Class<?> deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException {
     boolean isPrimitive = codedIn.readBool();
     if (isPrimitive) {
       return PRIMITIVE_CLASS_INDEX_MAP.inverse().get(codedIn.readInt32());
     }
-    String className = stringCodec().deserialize(dependencies, codedIn);
+    String className = context.deserializeLeaf(codedIn, stringCodec());
     try {
       return Class.forName(className);
     } catch (ClassNotFoundException e) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/CodecWithFailure.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/CodecWithFailure.java
index ea91998..4383b2a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/CodecWithFailure.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/CodecWithFailure.java
@@ -37,14 +37,13 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, T obj, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, T obj, CodedOutputStream codedOut)
       throws SerializationException {
     throw new SerializationException(message);
   }
 
   @Override
-  public T deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public T deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException {
     throw new SerializationException(message);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContext.java
index 64bb39e..8111976 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DeserializationContext.java
@@ -146,7 +146,11 @@
     return deserializeAndMaybeMemoize(registry.getCodecDescriptorByTag(tag).getCodec(), codedIn);
   }
 
-  @ForOverride
+  @Nullable
+  final Object maybeGetConstantByTag(int tag) {
+    return registry.maybeGetConstantByTag(tag);
+  }
+
   abstract Object getMemoizedBackReference(int memoIndex);
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DoubleCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DoubleCodec.java
index 1d5dbd3..7c97f6a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DoubleCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DoubleCodec.java
@@ -26,14 +26,13 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, Double value, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, Double value, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeDoubleNoTag(value);
   }
 
   @Override
-  public Double deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public Double deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws IOException {
     return codedIn.readDouble();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DurationCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DurationCodec.java
index b15896b..9895bf9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DurationCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/DurationCodec.java
@@ -22,16 +22,15 @@
 /** Encodes a Duration. */
 public class DurationCodec extends LeafObjectCodec<Duration> {
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, Duration obj, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, Duration obj, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeInt64NoTag(obj.getSeconds());
     codedOut.writeInt32NoTag(obj.getNano());
   }
 
   @Override
-  public Duration deserialize(
-      SerializationDependencyProvider dependencies, CodedInputStream codedIn) throws IOException {
+  public Duration deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
+      throws IOException {
     return Duration.ofSeconds(codedIn.readInt64(), codedIn.readInt32());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/EmptyListCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/EmptyListCodec.java
index a20f646..67d729b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/EmptyListCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/EmptyListCodec.java
@@ -35,13 +35,10 @@
 
   @Override
   public void serialize(
-      SerializationDependencyProvider dependencies,
-      List unusedValue,
-      CodedOutputStream unusedCodedOut) {}
+      LeafSerializationContext context, List unusedValue, CodedOutputStream unusedCodedOut) {}
 
   @Override
-  public List deserialize(
-      SerializationDependencyProvider dependencies, CodedInputStream unusedCodedIn) {
+  public List deserialize(LeafDeserializationContext context, CodedInputStream unusedCodedIn) {
     return Collections.emptyList();
   }
 }
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
index a877e59..8b46040 100644
--- 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
@@ -41,15 +41,14 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, T value, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, T value, CodedOutputStream codedOut)
       throws IOException {
     Preconditions.checkNotNull(value, "Enum value for %s is null", enumClass);
     codedOut.writeEnumNoTag(value.ordinal());
   }
 
   @Override
-  public T deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public T deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException {
     int ordinal = codedIn.readEnum();
     try {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/HashCodeCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/HashCodeCodec.java
index 30c146f..6af8e8b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/HashCodeCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/HashCodeCodec.java
@@ -23,15 +23,14 @@
 public class HashCodeCodec extends LeafObjectCodec<HashCode> {
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, HashCode obj, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, HashCode obj, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeByteArrayNoTag(obj.asBytes());
   }
 
   @Override
-  public HashCode deserialize(
-      SerializationDependencyProvider dependencies, CodedInputStream codedIn) throws IOException {
+  public HashCode deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
+      throws IOException {
     return HashCode.fromBytes(codedIn.readByteArray());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableDeserializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableDeserializationContext.java
index 0db4e9e..dcb00a0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableDeserializationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableDeserializationContext.java
@@ -52,6 +52,12 @@
   }
 
   @Override
+  public <T> T deserializeLeaf(CodedInputStream codedIn, LeafObjectCodec<T> codec)
+      throws SerializationException, IOException {
+    return codec.deserialize((LeafDeserializationContext) this, codedIn);
+  }
+
+  @Override
   Object getMemoizedBackReference(int memoIndex) {
     throw new UnsupportedOperationException(
         "The tag should never be less than 0 in the stateless case");
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableSerializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableSerializationContext.java
index cc8b64a..4bfadd7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableSerializationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/ImmutableSerializationContext.java
@@ -57,6 +57,12 @@
   }
 
   @Override
+  public <T> void serializeLeaf(T obj, LeafObjectCodec<T> codec, CodedOutputStream codedOut)
+      throws SerializationException, IOException {
+    codec.serialize((LeafSerializationContext) this, obj, codedOut);
+  }
+
+  @Override
   boolean writeBackReferenceIfMemoized(Object obj, CodedOutputStream codedOut) {
     return false;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/IntegerCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/IntegerCodec.java
index aa1fcf0..db629ff 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/IntegerCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/IntegerCodec.java
@@ -27,14 +27,13 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, Integer value, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, Integer value, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeInt32NoTag(value);
   }
 
   @Override
-  public Integer deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public Integer deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws IOException {
     return codedIn.readInt32();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LeafDeserializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LeafDeserializationContext.java
new file mode 100644
index 0000000..c36249e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LeafDeserializationContext.java
@@ -0,0 +1,29 @@
+// Copyright 2024 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 java.io.IOException;
+
+/**
+ * Context provided to {@link LeafObjectCodec} implementations.
+ *
+ * <p>This context permits delegation only to other {@link LeafObjectCodec} instances and dependency
+ * lookups.
+ */
+public interface LeafDeserializationContext extends SerializationDependencyProvider {
+  /** Deserializes an object from {@code codedIn} using {@code codec}. */
+  public <T> T deserializeLeaf(CodedInputStream codedIn, LeafObjectCodec<T> codec)
+      throws IOException, SerializationException;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LeafObjectCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LeafObjectCodec.java
index 1462d80..b6ccbfa 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LeafObjectCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LeafObjectCodec.java
@@ -20,34 +20,35 @@
 /**
  * A codec that directly deserializes from the {@link CodedInputStream}.
  *
- * <p>Since it never delegates to the {@link DeserializationContext}, it is asynchronous compatible.
+ * <p>{@link LeafObjectCodec}s may only delegate to other {@link LeafObjectCodec}s and are
+ * restricted from using any asynchronous features. By construction, they can only be used to
+ * serialize acyclic values and are always synchronous.
  */
 public abstract class LeafObjectCodec<T> implements ObjectCodec<T> {
   @Override
   public final void serialize(SerializationContext context, T obj, CodedOutputStream codedOut)
       throws SerializationException, IOException {
-    serialize((SerializationDependencyProvider) context, obj, codedOut);
+    serialize((LeafSerializationContext) context, obj, codedOut);
   }
 
   /**
    * This has the same contract as {@link #serialize}, but may only depend on {@link
-   * SerializationDependencyProvider} instead of the full {@link SerializationContext}.
+   * LeafSerializationContext} instead of the full {@link SerializationContext}.
    */
   public abstract void serialize(
-      SerializationDependencyProvider dependencies, T obj, CodedOutputStream codedOut)
+      LeafSerializationContext context, T obj, CodedOutputStream codedOut)
       throws SerializationException, IOException;
 
   @Override
   public final T deserialize(DeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException {
-    return deserialize((SerializationDependencyProvider) context, codedIn);
+    return deserialize((LeafDeserializationContext) context, codedIn);
   }
 
   /**
    * This has the same contract as {@link #deserialize}, but may only depend on {@link
-   * SerializationDependencyProvider} instead of the full {@link DeserializationContext}.
+   * LeafDeserializationContext} instead of the full {@link DeserializationContext}.
    */
-  public abstract T deserialize(
-      SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public abstract T deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException;
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LeafSerializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LeafSerializationContext.java
new file mode 100644
index 0000000..3bb8705
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LeafSerializationContext.java
@@ -0,0 +1,31 @@
+// Copyright 2024 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.CodedOutputStream;
+import java.io.IOException;
+import javax.annotation.Nullable;
+
+/**
+ * Context provided to {@link LeafObjectCodec} implementations.
+ *
+ * <p>This context permits delegation only to other {@link LeafObjectCodec} instances and dependency
+ * lookups.
+ */
+public interface LeafSerializationContext extends SerializationDependencyProvider {
+  /** Serializes {@code obj} using {@code codec} into {@code codedOut}. */
+  public <T> void serializeLeaf(
+      @Nullable T obj, LeafObjectCodec<T> codec, CodedOutputStream codedOut)
+      throws IOException, SerializationException;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LongArrayCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LongArrayCodec.java
index 2b13b95..c1e8fe9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LongArrayCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LongArrayCodec.java
@@ -25,8 +25,7 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, long[] obj, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, long[] obj, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeInt32NoTag(obj.length);
     for (long l : obj) {
@@ -35,7 +34,7 @@
   }
 
   @Override
-  public long[] deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public long[] deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws IOException {
     long[] result = new long[codedIn.readInt32()];
     for (int i = 0; i < result.length; i++) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LongCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LongCodec.java
index c651399..8444315 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LongCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/LongCodec.java
@@ -27,14 +27,13 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, Long value, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, Long value, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeInt64NoTag(value);
   }
 
   @Override
-  public Long deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public Long deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws IOException {
     return codedIn.readInt64();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MemoizingDeserializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MemoizingDeserializationContext.java
index 563f0d6..ec7a4c7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MemoizingDeserializationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MemoizingDeserializationContext.java
@@ -76,6 +76,27 @@
   }
 
   @Override
+  public final <T> T deserializeLeaf(CodedInputStream codedIn, LeafObjectCodec<T> codec)
+      throws IOException, SerializationException {
+    int tag = codedIn.readSInt32();
+    if (tag == 0) {
+      return null;
+    }
+    Object maybeConstant = maybeGetConstantByTag(tag);
+    if (maybeConstant != null) {
+      return codec.safeCast(maybeConstant);
+    }
+    if (tag < -1) {
+      // Subtracts 2 to undo the corresponding operation in SerializationContext.serializeLeaf.
+      return codec.safeCast(getMemoizedBackReference(-tag - 2));
+    }
+    checkState(tag == -1, "Unexpected tag for immediate value; %s", tag);
+    T value = codec.deserialize((LeafDeserializationContext) this, codedIn);
+    memoize(memoTable.size(), value);
+    return value;
+  }
+
+  @Override
   public final void registerInitialValue(Object initialValue) {
     checkState(tagForMemoizedBefore != -1, "Not called with memoize before: %s", initialValue);
     int tag = tagForMemoizedBefore;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MemoizingSerializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MemoizingSerializationContext.java
index c178748..99ae256 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MemoizingSerializationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MemoizingSerializationContext.java
@@ -182,6 +182,28 @@
   }
 
   @Override
+  public final <T> void serializeLeaf(
+      @Nullable T obj, LeafObjectCodec<T> codec, CodedOutputStream codedOut)
+      throws IOException, SerializationException {
+    if (writeIfNullOrConstant(obj, codedOut)) {
+      return;
+    }
+    int maybePrevious = getMemoizedIndex(obj);
+    if (maybePrevious != NO_VALUE) {
+      // There was a previous entry. Writes a backreference, subtracting 2 to avoid 0 (which
+      // indicates null), and -1 (which indicates an immediate value).
+      codedOut.writeSInt32NoTag(-maybePrevious - 2);
+      return;
+    }
+    // A new entry was added, emits -1 to signal an immediate value, then serializes the value.
+    codedOut.writeSInt32NoTag(-1);
+    codec.serialize((LeafSerializationContext) this, obj, codedOut);
+    // By necessity, a LeafCodec is treated like MEMOIZE_AFTER because when deserializing, the
+    // value will only be available as a backreference after its deserialization is complete.
+    int unusedId = memoize(obj);
+  }
+
+  @Override
   public final void addExplicitlyAllowedClass(Class<?> allowedClass) {
     explicitlyAllowedClasses.add(allowedClass);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MessageLiteCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MessageLiteCodec.java
index ac82373..24c4c4a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MessageLiteCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MessageLiteCodec.java
@@ -49,14 +49,13 @@
 
   @Override
   public void serialize(
-      SerializationDependencyProvider dependencies, MessageLite message, CodedOutputStream codedOut)
+      LeafSerializationContext context, MessageLite message, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeMessageNoTag(message);
   }
 
   @Override
-  public MessageLite deserialize(
-      SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public MessageLite deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws IOException, SerializationException {
     // Don't hold on to full byte array when constructing this proto.
     codedIn.enableAliasing(false);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MethodCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MethodCodec.java
index 083a552..2ec957d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MethodCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/MethodCodec.java
@@ -31,27 +31,26 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, Method obj, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, Method obj, CodedOutputStream codedOut)
       throws SerializationException, IOException {
-    classCodec().serialize(dependencies, obj.getDeclaringClass(), codedOut);
-    stringCodec().serialize(dependencies, obj.getName(), codedOut);
+    context.serializeLeaf(obj.getDeclaringClass(), classCodec(), codedOut);
+    context.serializeLeaf(obj.getName(), stringCodec(), codedOut);
     Class<?>[] parameterTypes = obj.getParameterTypes();
     codedOut.writeInt32NoTag(parameterTypes.length);
     for (Class<?> parameter : parameterTypes) {
-      classCodec().serialize(dependencies, parameter, codedOut);
+      context.serializeLeaf(parameter, classCodec(), codedOut);
     }
   }
 
   @Override
-  public Method deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public Method deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException {
-    Class<?> clazz = classCodec().deserialize(dependencies, codedIn);
-    String name = stringCodec().deserialize(dependencies, codedIn);
+    Class<?> clazz = context.deserializeLeaf(codedIn, classCodec());
+    String name = context.deserializeLeaf(codedIn, stringCodec());
 
     Class<?>[] parameters = new Class<?>[codedIn.readInt32()];
     for (int i = 0; i < parameters.length; i++) {
-      parameters[i] = classCodec().deserialize(dependencies, codedIn);
+      parameters[i] = context.deserializeLeaf(codedIn, classCodec());
     }
     try {
       return clazz.getDeclaredMethod(name, parameters);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContext.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContext.java
index 3b12441..86eb6ec 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SerializationContext.java
@@ -35,7 +35,7 @@
  * only makes sense to tie the lifetime of a {@link CodedOutputStream} to the lifetime of a {@link
  * MemoizingSerializationContext}.
  */
-public abstract class SerializationContext implements SerializationDependencyProvider {
+public abstract class SerializationContext implements LeafSerializationContext {
   private final ObjectCodecRegistry codecRegistry;
   private final ImmutableClassToInstanceMap<Object> dependencies;
 
@@ -179,7 +179,7 @@
 
   public abstract boolean isMemoizing();
 
-  private final boolean writeIfNullOrConstant(@Nullable Object object, CodedOutputStream codedOut)
+  final boolean writeIfNullOrConstant(@Nullable Object object, CodedOutputStream codedOut)
       throws IOException {
     if (object == null) {
       codedOut.writeSInt32NoTag(0);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SingletonCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SingletonCodec.java
index b208842..c645a7f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SingletonCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/SingletonCodec.java
@@ -53,14 +53,13 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, T t, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, T t, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeByteArrayNoTag(mnemonic);
   }
 
   @Override
-  public T deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public T deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException {
     // Get ByteBuffer instead of raw bytes, as it may be a direct view of the data and not a copy,
     // which is much more efficient.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/UUIDCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/UUIDCodec.java
index 70392d7..9db41c2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/UUIDCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/UUIDCodec.java
@@ -27,15 +27,14 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, UUID uuid, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, UUID uuid, CodedOutputStream codedOut)
       throws IOException {
     codedOut.writeInt64NoTag(uuid.getMostSignificantBits());
     codedOut.writeInt64NoTag(uuid.getLeastSignificantBits());
   }
 
   @Override
-  public UUID deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public UUID deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException {
     return new UUID(codedIn.readInt64(), codedIn.readInt64());
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/CharsetCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/CharsetCodec.java
index 717e1b2..1fb5aa4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/CharsetCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/CharsetCodec.java
@@ -15,8 +15,9 @@
 
 import static com.google.devtools.build.lib.skyframe.serialization.strings.UnsafeStringCodec.stringCodec;
 
+import com.google.devtools.build.lib.skyframe.serialization.LeafDeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.LeafObjectCodec;
-import com.google.devtools.build.lib.skyframe.serialization.SerializationDependencyProvider;
+import com.google.devtools.build.lib.skyframe.serialization.LeafSerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
@@ -32,14 +33,14 @@
 
   @Override
   public void serialize(
-      SerializationDependencyProvider dependencies, Charset charset, CodedOutputStream codedOut)
+      LeafSerializationContext context, Charset charset, CodedOutputStream codedOut)
       throws SerializationException, IOException {
-    stringCodec().serialize(dependencies, charset.name(), codedOut);
+    context.serializeLeaf(charset.name(), stringCodec(), codedOut);
   }
 
   @Override
-  public Charset deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public Charset deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException {
-    return Charset.forName(stringCodec().deserialize(dependencies, codedIn));
+    return Charset.forName(context.deserializeLeaf(codedIn, stringCodec()));
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/PatternCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/PatternCodec.java
index 4f73a40..64ed22e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/PatternCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/PatternCodec.java
@@ -15,8 +15,9 @@
 
 import static com.google.devtools.build.lib.skyframe.serialization.strings.UnsafeStringCodec.stringCodec;
 
+import com.google.devtools.build.lib.skyframe.serialization.LeafDeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.LeafObjectCodec;
-import com.google.devtools.build.lib.skyframe.serialization.SerializationDependencyProvider;
+import com.google.devtools.build.lib.skyframe.serialization.LeafSerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
@@ -32,15 +33,15 @@
 
   @Override
   public void serialize(
-      SerializationDependencyProvider dependencies, Pattern pattern, CodedOutputStream codedOut)
+      LeafSerializationContext context, Pattern pattern, CodedOutputStream codedOut)
       throws SerializationException, IOException {
-    stringCodec().serialize(dependencies, pattern.pattern(), codedOut);
+    context.serializeLeaf(pattern.pattern(), stringCodec(), codedOut);
     codedOut.writeInt32NoTag(pattern.flags());
   }
 
   @Override
-  public Pattern deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public Pattern deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException {
-    return Pattern.compile(stringCodec().deserialize(dependencies, codedIn), codedIn.readInt32());
+    return Pattern.compile(context.deserializeLeaf(codedIn, stringCodec()), codedIn.readInt32());
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/UnsafeStringCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/UnsafeStringCodec.java
index f805799..6af65f1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/UnsafeStringCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/strings/UnsafeStringCodec.java
@@ -14,9 +14,10 @@
 
 package com.google.devtools.build.lib.skyframe.serialization.strings;
 
+import com.google.devtools.build.lib.skyframe.serialization.LeafDeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.LeafObjectCodec;
+import com.google.devtools.build.lib.skyframe.serialization.LeafSerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
-import com.google.devtools.build.lib.skyframe.serialization.SerializationDependencyProvider;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.devtools.build.lib.unsafe.StringUnsafe;
 import com.google.protobuf.CodedInputStream;
@@ -50,8 +51,7 @@
   }
 
   @Override
-  public void serialize(
-      SerializationDependencyProvider dependencies, String obj, CodedOutputStream codedOut)
+  public void serialize(LeafSerializationContext context, String obj, CodedOutputStream codedOut)
       throws SerializationException, IOException {
     byte coder = stringUnsafe.getCoder(obj);
     byte[] value = stringUnsafe.getByteArray(obj);
@@ -69,7 +69,7 @@
   }
 
   @Override
-  public String deserialize(SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+  public String deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
       throws SerializationException, IOException {
     int length = codedIn.readInt32();
     byte coder;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/NotSerializableCodec.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/NotSerializableCodec.java
index 170789f..8e9e8d9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/NotSerializableCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/NotSerializableCodec.java
@@ -14,8 +14,9 @@
 
 package com.google.devtools.build.lib.skyframe.serialization.testutils;
 
+import com.google.devtools.build.lib.skyframe.serialization.LeafDeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.LeafObjectCodec;
-import com.google.devtools.build.lib.skyframe.serialization.SerializationDependencyProvider;
+import com.google.devtools.build.lib.skyframe.serialization.LeafSerializationContext;
 import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
 import java.io.NotSerializableException;
@@ -35,16 +36,13 @@
 
   @Override
   public void serialize(
-      SerializationDependencyProvider dependencies,
-      Object unusedObj,
-      CodedOutputStream unusedCodedOut)
+      LeafSerializationContext context, Object unusedObj, CodedOutputStream unusedCodedOut)
       throws NotSerializableException {
     throw new NotSerializableException(type + " marked not serializable");
   }
 
   @Override
-  public Object deserialize(
-      SerializationDependencyProvider dependencies, CodedInputStream unusedCodedIn)
+  public Object deserialize(LeafDeserializationContext context, CodedInputStream unusedCodedIn)
       throws NotSerializableException {
     throw new NotSerializableException(type + " marked not serializable");
   }
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/FileAccessException.java b/src/main/java/com/google/devtools/build/lib/vfs/FileAccessException.java
index 1fe7594..e8fcf4e 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/FileAccessException.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/FileAccessException.java
@@ -15,8 +15,9 @@
 
 import static com.google.devtools.build.lib.skyframe.serialization.strings.UnsafeStringCodec.stringCodec;
 
+import com.google.devtools.build.lib.skyframe.serialization.LeafDeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.LeafObjectCodec;
-import com.google.devtools.build.lib.skyframe.serialization.SerializationDependencyProvider;
+import com.google.devtools.build.lib.skyframe.serialization.LeafSerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
@@ -55,9 +56,7 @@
 
     @Override
     public void serialize(
-        SerializationDependencyProvider dependencies,
-        FileAccessException fae,
-        CodedOutputStream codedOut)
+        LeafSerializationContext context, FileAccessException fae, CodedOutputStream codedOut)
         throws SerializationException, IOException {
       String message = fae.getMessage();
       if (message == null) {
@@ -65,18 +64,18 @@
         return;
       }
       codedOut.writeBoolNoTag(true);
-      stringCodec().serialize(dependencies, message, codedOut);
+      context.serializeLeaf(message, stringCodec(), codedOut);
     }
 
     @Override
     public FileAccessException deserialize(
-        SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+        LeafDeserializationContext context, CodedInputStream codedIn)
         throws SerializationException, IOException {
       boolean hasMessage = codedIn.readBool();
       if (!hasMessage) {
         return new FileAccessException(null);
       }
-      String message = stringCodec().deserialize(dependencies, codedIn);
+      String message = context.deserializeLeaf(codedIn, stringCodec());
       return new FileAccessException(message);
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java b/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java
index ba1ea01..8252564 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java
@@ -18,8 +18,9 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.CommandLineItem;
+import com.google.devtools.build.lib.skyframe.serialization.LeafDeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.LeafObjectCodec;
-import com.google.devtools.build.lib.skyframe.serialization.SerializationDependencyProvider;
+import com.google.devtools.build.lib.skyframe.serialization.LeafSerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.SerializationConstant;
 import com.google.devtools.build.lib.util.FileType;
@@ -848,16 +849,15 @@
 
     @Override
     public void serialize(
-        SerializationDependencyProvider dependencies, PathFragment obj, CodedOutputStream codedOut)
+        LeafSerializationContext context, PathFragment obj, CodedOutputStream codedOut)
         throws SerializationException, IOException {
-      stringCodec().serialize(dependencies, obj.normalizedPath, codedOut);
+      context.serializeLeaf(obj.normalizedPath, stringCodec(), codedOut);
     }
 
     @Override
-    public PathFragment deserialize(
-        SerializationDependencyProvider dependencies, CodedInputStream codedIn)
+    public PathFragment deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
         throws SerializationException, IOException {
-      return createAlreadyNormalized(stringCodec().deserialize(dependencies, codedIn));
+      return createAlreadyNormalized(context.deserializeLeaf(codedIn, stringCodec()));
     }
   }
 }
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
index 8a35f1c..6c12b78 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/BUILD
@@ -91,9 +91,11 @@
     deps = [
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils",
+        "//third_party:guava",
         "//third_party:jsr305",
         "//third_party:junit4",
         "//third_party:truth",
+        "//third_party/protobuf:protobuf_java",
     ],
 )
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/MemoizerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/MemoizerTest.java
index 6acee71..4c07cb1 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/serialization/MemoizerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/serialization/MemoizerTest.java
@@ -14,8 +14,12 @@
 package com.google.devtools.build.lib.skyframe.serialization;
 
 import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.lib.skyframe.serialization.strings.UnsafeStringCodec.stringCodec;
 
+import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.TestUtils;
+import com.google.protobuf.CodedInputStream;
+import com.google.protobuf.CodedOutputStream;
 import java.io.IOException;
 import javax.annotation.Nullable;
 import org.junit.Test;
@@ -127,6 +131,89 @@
     assertABcycle(TestUtils.roundTripMemoized(a));
   }
 
+  // The following two tests verify that objects memoized using serialize can interoperate with
+  // objects memoized using serializeLeaf, bidirectionally.
+
+  @Test
+  public void serializedLeaf_canBeBackreferenced() throws Exception {
+    @SuppressWarnings("StringCopy") // deliberate to create different references
+    String first = new String("foo");
+    @SuppressWarnings("StringCopy") // deliberate to create different references
+    String second = new String("foo");
+    ImmutableList<Object> subject = ImmutableList.of(new Wrapper(first), second);
+    assertThat(((Wrapper) subject.get(0)).value).isNotSameInstanceAs(subject.get(1));
+
+    ImmutableList<Object> deserialized =
+        TestUtils.roundTripMemoized(subject, new WrapperLeafCodec());
+    assertThat(subject).isEqualTo(deserialized);
+    // The "foo" instance memoized via serializeLeaf can be backreferenced by a codec that isn't
+    // explicitly invoked via serializeLeaf.
+    assertThat(((Wrapper) deserialized.get(0)).value).isSameInstanceAs(deserialized.get(1));
+  }
+
+  @Test
+  public void serializeLeaf_canBackreferenceNonSerializeLeaf() throws Exception {
+    @SuppressWarnings("StringCopy") // deliberate to create different references
+    String first = new String("foo");
+    @SuppressWarnings("StringCopy") // deliberate to create different references
+    String second = new String("foo");
+    ImmutableList<Object> subject = ImmutableList.of(first, new Wrapper(second));
+    assertThat(subject.get(0)).isNotSameInstanceAs(((Wrapper) subject.get(1)).value);
+
+    ImmutableList<Object> deserialized =
+        TestUtils.roundTripMemoized(subject, new WrapperLeafCodec());
+    assertThat(subject).isEqualTo(deserialized);
+    // The "foo" instance memoized via serialize can be backreferenced by a codec that uses
+    // serializeLeaf.
+    assertThat(deserialized.get(0)).isSameInstanceAs(((Wrapper) deserialized.get(1)).value);
+  }
+
+  /** An example class that allows {@link LeafObjectCodec} to be exercised. */
+  private static class Wrapper {
+    private final String value;
+
+    private Wrapper(String value) {
+      this.value = value;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (obj instanceof Wrapper that) {
+        return value.equals(that.value);
+      }
+      return false;
+    }
+
+    @Override
+    public int hashCode() {
+      return value.hashCode();
+    }
+  }
+
+  private static final class WrapperLeafCodec extends LeafObjectCodec<Wrapper> {
+    @Override
+    public Class<Wrapper> getEncodedClass() {
+      return Wrapper.class;
+    }
+
+    @Override
+    public boolean autoRegister() {
+      return false;
+    }
+
+    @Override
+    public void serialize(LeafSerializationContext context, Wrapper obj, CodedOutputStream codedOut)
+        throws SerializationException, IOException {
+      context.serializeLeaf(obj.value, stringCodec(), codedOut);
+    }
+
+    @Override
+    public Wrapper deserialize(LeafDeserializationContext context, CodedInputStream codedIn)
+        throws SerializationException, IOException {
+      return new Wrapper(context.deserializeLeaf(codedIn, stringCodec()));
+    }
+  }
+
   /** Asserts that {@code value} has the linked list structure {@code A -> B -> C}. */
   private static void assertABC(DummyLinkedList value) {
     assertThat(value.getValue()).isEqualTo("A");