diff --git a/src/test/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberKeyTest.java b/src/test/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberKeyTest.java
index f8094d7..61c4685 100644
--- a/src/test/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberKeyTest.java
+++ b/src/test/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberKeyTest.java
@@ -29,129 +29,90 @@
   @Test
   public void fieldKey_bridgeOfInstanceRead() {
     FieldKey fieldKey =
-        FieldKey.create(
-            /* ownerClass= */ "a/b/Charlie",
-            /* name= */ "instanceFieldOfLongType",
-            /* descriptor= */ "J");
+        FieldKey.create(ClassName.create("a/b/Charlie"), "instanceFieldOfLongType", "J");
     assertThat(fieldKey.bridgeOfInstanceRead())
         .isEqualTo(
             MethodKey.create(
-                /* ownerClass= */ "a/b/Charlie",
-                /* name= */ "instanceFieldOfLongType$bridge_getter",
-                /* descriptor= */ "(La/b/Charlie;)J"));
+                ClassName.create("a/b/Charlie"),
+                "instanceFieldOfLongType$bridge_getter",
+                "(La/b/Charlie;)J"));
   }
 
   @Test
   public void fieldKey_bridgeOfInstanceWrite() {
+
     FieldKey fieldKey =
-        FieldKey.create(
-            /* ownerClass= */ "a/b/Charlie",
-            /* name= */ "instanceFieldOfLongType",
-            /* descriptor= */ "J");
+        FieldKey.create(ClassName.create("a/b/Charlie"), "instanceFieldOfLongType", "J");
     assertThat(fieldKey.bridgeOfInstanceWrite())
         .isEqualTo(
             MethodKey.create(
-                /* ownerClass= */ "a/b/Charlie",
-                /* name= */ "instanceFieldOfLongType$bridge_setter",
-                /* descriptor= */ "(La/b/Charlie;J)J"));
+                ClassName.create("a/b/Charlie"),
+                "instanceFieldOfLongType$bridge_setter",
+                "(La/b/Charlie;J)J"));
   }
 
   @Test
   public void fieldKey_bridgeOfStaticRead() {
     FieldKey fieldKey =
-        FieldKey.create(
-            /* ownerClass= */ "a/b/Charlie",
-            /* name= */ "staticFieldOfLongType",
-            /* descriptor= */ "J");
+        FieldKey.create(ClassName.create("a/b/Charlie"), "staticFieldOfLongType", "J");
     assertThat(fieldKey.bridgeOfStaticRead())
         .isEqualTo(
             MethodKey.create(
-                /* ownerClass= */ "a/b/Charlie",
-                /* name= */ "staticFieldOfLongType$bridge_getter",
-                /* descriptor= */ "()J"));
+                ClassName.create("a/b/Charlie"), "staticFieldOfLongType$bridge_getter", "()J"));
   }
 
   @Test
   public void fieldKey_bridgeOfStaticWrite() {
     FieldKey fieldKey =
-        FieldKey.create(
-            /* ownerClass= */ "a/b/Charlie",
-            /* name= */ "staticFieldOfLongType",
-            /* descriptor= */ "J");
+        FieldKey.create(ClassName.create("a/b/Charlie"), "staticFieldOfLongType", "J");
     assertThat(fieldKey.bridgeOfStaticWrite())
         .isEqualTo(
             MethodKey.create(
-                /* ownerClass= */ "a/b/Charlie",
-                /* name= */ "staticFieldOfLongType$bridge_setter",
-                /* descriptor= */ "(J)J"));
+                ClassName.create("a/b/Charlie"), "staticFieldOfLongType$bridge_setter", "(J)J"));
   }
 
   @Test
   public void methodKey_bridgeOfClassInstanceMethod() {
-    MethodKey methodKey =
-        MethodKey.create(
-            /* ownerClass= */ "a/b/Charlie", /* name= */ "twoLongSum", /* descriptor= */ "(JJ)J");
+    MethodKey methodKey = MethodKey.create(ClassName.create("a/b/Charlie"), "twoLongSum", "(JJ)J");
     assertThat(methodKey.bridgeOfClassInstanceMethod())
         .isEqualTo(
             MethodKey.create(
-                /* ownerClass= */ "a/b/Charlie",
-                /* name= */ "twoLongSum$bridge",
-                /* descriptor= */ "(La/b/Charlie;JJ)J"));
+                ClassName.create("a/b/Charlie"), "twoLongSum$bridge", "(La/b/Charlie;JJ)J"));
   }
 
   @Test
   public void methodKey_bridgeOfClassStaticMethod() {
-    MethodKey methodKey =
-        MethodKey.create(
-            /* ownerClass= */ "a/b/Charlie", /* name= */ "twoLongSum", /* descriptor= */ "(JJ)J");
+    MethodKey methodKey = MethodKey.create(ClassName.create("a/b/Charlie"), "twoLongSum", "(JJ)J");
     assertThat(methodKey.bridgeOfClassStaticMethod())
-        .isEqualTo(
-            MethodKey.create(
-                /* ownerClass= */ "a/b/Charlie",
-                /* name= */ "twoLongSum$bridge",
-                /* descriptor= */ "(JJ)J"));
+        .isEqualTo(MethodKey.create(ClassName.create("a/b/Charlie"), "twoLongSum$bridge", "(JJ)J"));
   }
 
   @Test
   public void methodKey_bridgeOfConstructor() {
-    MethodKey methodKey =
-        MethodKey.create(
-            /* ownerClass= */ "a/b/Charlie", /* name= */ "<init>", /* descriptor= */ "(JJ)V");
-    assertThat(methodKey.bridgeOfConstructor("a/b/Charlie$NestCC"))
+    MethodKey methodKey = MethodKey.create(ClassName.create("a/b/Charlie"), "<init>", "(JJ)V");
+    assertThat(methodKey.bridgeOfConstructor(ClassName.create("a/b/Charlie$NestCC")))
         .isEqualTo(
             MethodKey.create(
-                /* ownerClass= */ "a/b/Charlie",
-                /* name= */ "<init>",
-                /* descriptor= */ "(JJLa/b/Charlie$NestCC;)V"));
+                ClassName.create("a/b/Charlie"), "<init>", "(JJLa/b/Charlie$NestCC;)V"));
   }
 
   @Test
   public void methodKey_substituteOfInterfaceInstanceMethod() {
     MethodKey methodKey =
-        MethodKey.create(
-            /* ownerClass= */ "a/b/Charlie",
-            /* name= */ "instanceInstanceMethod",
-            /* descriptor= */ "(JJ)J");
+        MethodKey.create(ClassName.create("a/b/Charlie"), "instanceInstanceMethod", "(JJ)J");
     assertThat(methodKey.substituteOfInterfaceInstanceMethod())
         .isEqualTo(
             MethodKey.create(
-                /* ownerClass= */ "a/b/Charlie",
-                /* name= */ "instanceInstanceMethod",
-                /* descriptor= */ "(La/b/Charlie;JJ)J"));
+                ClassName.create("a/b/Charlie"), "instanceInstanceMethod", "(La/b/Charlie;JJ)J"));
   }
 
   @Test
   public void methodKey_substituteOfInterfaceStaticMethod() {
+
     MethodKey methodKey =
-        MethodKey.create(
-            /* ownerClass= */ "a/b/Charlie",
-            /* name= */ "instanceStaticMethod",
-            /* descriptor= */ "(JJ)J");
+        MethodKey.create(ClassName.create("a/b/Charlie"), "instanceStaticMethod", "(JJ)J");
     assertThat(methodKey.substituteOfInterfaceStaticMethod())
         .isEqualTo(
-            MethodKey.create(
-                /* ownerClass= */ "a/b/Charlie",
-                /* name= */ "instanceStaticMethod",
-                /* descriptor= */ "(JJ)J"));
+            MethodKey.create(ClassName.create("a/b/Charlie"), "instanceStaticMethod", "(JJ)J"));
   }
 }
diff --git a/src/test/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberRecordTest.java b/src/test/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberRecordTest.java
index 7e01e1e..85b4553 100644
--- a/src/test/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberRecordTest.java
+++ b/src/test/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberRecordTest.java
@@ -31,8 +31,8 @@
 
   @Test
   public void trackFieldUse() {
-    ClassMemberKey classMemberKey =
-        FieldKey.create("package/path/OwnerClass", "fieldOfPrimitiveLong", "J");
+    FieldKey classMemberKey =
+        FieldKey.create(ClassName.create("package/path/OwnerClass"), "fieldOfPrimitiveLong", "J");
     classMemberRecord.logMemberUse(classMemberKey, Opcodes.GETFIELD);
     classMemberRecord.logMemberUse(classMemberKey, Opcodes.PUTFIELD);
     classMemberRecord.logMemberUse(classMemberKey, Opcodes.H_GETFIELD);
@@ -48,7 +48,8 @@
 
   @Test
   public void trackConstructorUse() {
-    ClassMemberKey classMemberKey = MethodKey.create("package/path/OwnerClass", "<init>", "()V");
+    MethodKey classMemberKey =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "<init>", "()V");
     classMemberRecord.logMemberUse(classMemberKey, Opcodes.INVOKESPECIAL);
     classMemberRecord.logMemberUse(classMemberKey, Opcodes.H_NEWINVOKESPECIAL);
 
@@ -58,7 +59,8 @@
 
   @Test
   public void trackMethodUse() {
-    ClassMemberKey classMemberKey = MethodKey.create("package/path/OwnerClass", "method", "(II)I");
+    MethodKey classMemberKey =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "method", "(II)I");
     classMemberRecord.logMemberUse(classMemberKey, Opcodes.INVOKEVIRTUAL);
     classMemberRecord.logMemberUse(classMemberKey, Opcodes.INVOKESPECIAL);
     classMemberRecord.logMemberUse(classMemberKey, Opcodes.INVOKESTATIC);
@@ -86,7 +88,8 @@
 
   @Test
   public void trackMemberDeclaration() {
-    ClassMemberKey classMemberKey = MethodKey.create("package/path/OwnerClass", "method", "(II)I");
+    MethodKey classMemberKey =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "method", "(II)I");
     classMemberRecord.logMemberDecl(
         classMemberKey, Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER, Opcodes.ACC_PRIVATE);
 
@@ -98,7 +101,8 @@
 
   @Test
   public void trackMemberDeclaration_withDeprecatedAnnotation() {
-    ClassMemberKey classMemberKey = MethodKey.create("package/path/OwnerClass", "method", "(II)I");
+    MethodKey classMemberKey =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "method", "(II)I");
     classMemberRecord.logMemberDecl(
         classMemberKey,
         Opcodes.ACC_DEPRECATED | Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER,
@@ -113,9 +117,12 @@
   public void mergeRecord_trackingReasons() {
     ClassMemberRecord otherClassMemberRecord = ClassMemberRecord.create();
 
-    ClassMemberKey method1 = MethodKey.create("package/path/OwnerClass", "method1", "(II)I");
-    ClassMemberKey method2 = MethodKey.create("package/path/OwnerClass", "method2", "(II)I");
-    ClassMemberKey method3 = MethodKey.create("package/path/OwnerClass", "method3", "(II)I");
+    MethodKey method1 =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "method1", "(II)I");
+    MethodKey method2 =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "method2", "(II)I");
+    MethodKey method3 =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "method3", "(II)I");
 
     classMemberRecord.logMemberDecl(method1, Opcodes.ACC_SUPER, Opcodes.ACC_PRIVATE);
     classMemberRecord.logMemberUse(method2, Opcodes.INVOKEVIRTUAL);
@@ -146,7 +153,8 @@
 
   @Test
   public void filterUsedMemberWithTrackedDeclaration_noMemberDeclaration() {
-    ClassMemberKey classMemberKey = MethodKey.create("package/path/OwnerClass", "method", "(II)I");
+    MethodKey classMemberKey =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "method", "(II)I");
 
     classMemberRecord.logMemberUse(classMemberKey, Opcodes.INVOKEVIRTUAL);
     assertThat(classMemberRecord.hasTrackingReason(classMemberKey)).isTrue();
@@ -157,7 +165,8 @@
 
   @Test
   public void filterUsedMemberWithTrackedDeclaration_noMemberUse() {
-    ClassMemberKey classMemberKey = MethodKey.create("package/path/OwnerClass", "method", "(II)I");
+    MethodKey classMemberKey =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "method", "(II)I");
 
     classMemberRecord.logMemberDecl(
         classMemberKey, Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER, Opcodes.ACC_PRIVATE);
@@ -169,7 +178,8 @@
 
   @Test
   public void filterUsedMemberWithTrackedDeclaration_interfaceMemberWithoutUse_shouldTrack() {
-    ClassMemberKey classMemberKey = MethodKey.create("package/path/OwnerClass", "method", "(II)I");
+    MethodKey classMemberKey =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "method", "(II)I");
 
     classMemberRecord.logMemberDecl(
         classMemberKey, Opcodes.ACC_PUBLIC | Opcodes.ACC_INTERFACE, Opcodes.ACC_PRIVATE);
diff --git a/src/test/java/com/google/devtools/build/android/desugar/nest/BUILD b/src/test/java/com/google/devtools/build/android/desugar/nest/BUILD
index 99f9ffd..8751692 100644
--- a/src/test/java/com/google/devtools/build/android/desugar/nest/BUILD
+++ b/src/test/java/com/google/devtools/build/android/desugar/nest/BUILD
@@ -61,10 +61,10 @@
 )
 
 java_test(
-    name = "NestCompanionsTest",
+    name = "NestDigestTest",
     size = "small",
-    srcs = ["NestCompanionsTest.java"],
-    test_class = "com.google.devtools.build.android.desugar.nest.NestCompanionsTest",
+    srcs = ["NestDigestTest.java"],
+    test_class = "com.google.devtools.build.android.desugar.nest.NestDigestTest",
     deps = [
         "//src/tools/android/java/com/google/devtools/build/android/desugar/langmodel",
         "//src/tools/android/java/com/google/devtools/build/android/desugar/nest",
@@ -218,6 +218,7 @@
         "//src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/complexcase:srcs",
         "//src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/nestanalyzer:srcs",
         "//src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/constructor:srcs",
+        "//src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/core/javadesugar/testing:srcs",
         "//src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/classfileformat:srcs",
         "//src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/field:srcs",
         "//src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/interfacemethod:srcs",
diff --git a/src/test/java/com/google/devtools/build/android/desugar/nest/NestAnalyzerTest.java b/src/test/java/com/google/devtools/build/android/desugar/nest/NestAnalyzerTest.java
index b240c67..24c3343 100644
--- a/src/test/java/com/google/devtools/build/android/desugar/nest/NestAnalyzerTest.java
+++ b/src/test/java/com/google/devtools/build/android/desugar/nest/NestAnalyzerTest.java
@@ -53,16 +53,14 @@
 
   private final ClassMemberRecord classMemberRecord = ClassMemberRecord.create();
   private final ClassAttributeRecord classAttributeRecord = ClassAttributeRecord.create();
-  private final NestCompanions nestCompanions =
-      NestCompanions.create(classMemberRecord, classAttributeRecord);
+  private final NestDigest nestDigest = NestDigest.create(classMemberRecord, classAttributeRecord);
 
   @Test
   public void emptyInputFiles() throws IOException {
     NestAnalyzer nestAnalyzer =
-        new NestAnalyzer(
-            ImmutableList.of(), nestCompanions, classMemberRecord, classAttributeRecord);
+        new NestAnalyzer(ImmutableList.of(), nestDigest, classMemberRecord, classAttributeRecord);
     nestAnalyzer.analyze();
-    assertThat(nestCompanions.getAllCompanionClasses()).isEmpty();
+    assertThat(nestDigest.getAllCompanionClassNames()).isEmpty();
   }
 
   @Test
@@ -82,13 +80,13 @@
                         new FileContentProvider<>(
                             entry.getName(), () -> getJarEntryInputStream(jarFile, entry)))
                 .collect(toImmutableList()),
-            nestCompanions,
+            nestDigest,
             classMemberRecord,
             classAttributeRecord);
 
     nestAnalyzer.analyze();
 
-    assertThat(nestCompanions.getAllCompanionClasses())
+    assertThat(nestDigest.getAllCompanionClassNames())
         .containsExactly(
             "com/google/devtools/build/android/desugar/nest/testsrc/nestanalyzer/AnalyzedTarget$NestCC");
   }
diff --git a/src/test/java/com/google/devtools/build/android/desugar/nest/NestCompanionsTest.java b/src/test/java/com/google/devtools/build/android/desugar/nest/NestCompanionsTest.java
deleted file mode 100644
index 3ee867b..0000000
--- a/src/test/java/com/google/devtools/build/android/desugar/nest/NestCompanionsTest.java
+++ /dev/null
@@ -1,146 +0,0 @@
-// Copyright 2019 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.android.desugar.nest;
-
-import static com.google.common.truth.Truth.assertThat;
-
-import com.google.devtools.build.android.desugar.langmodel.ClassAttributeRecord;
-import com.google.devtools.build.android.desugar.langmodel.ClassAttributes;
-import com.google.devtools.build.android.desugar.langmodel.ClassMemberRecord;
-import com.google.devtools.build.android.desugar.langmodel.MethodKey;
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-import org.objectweb.asm.Opcodes;
-
-/** The tests for {@link NestCompanions}. */
-@RunWith(JUnit4.class)
-public class NestCompanionsTest {
-
-  private final ClassMemberRecord classMemberRecord = ClassMemberRecord.create();
-  private final ClassAttributeRecord classAttributeRecord = ClassAttributeRecord.create();
-  private final NestCompanions nestCompanions =
-      NestCompanions.create(classMemberRecord, classAttributeRecord);
-
-  @Test
-  public void prepareCompanionClassWriters_noCompanionClassesGenerated() {
-    classMemberRecord.logMemberDecl(
-        MethodKey.create("package/path/OwnerClass", "method", "(II)I"),
-        /* ownerAccess= */ Opcodes.ACC_PUBLIC | Opcodes.ACC_INTERFACE,
-        /* memberDeclAccess= */ Opcodes.ACC_PRIVATE);
-
-    nestCompanions.prepareCompanionClasses();
-
-    assertThat(nestCompanions.getAllCompanionClasses()).isEmpty();
-  }
-
-  @Test
-  public void prepareCompanionClassWriters_companionClassesGenerated() {
-    MethodKey constructor = MethodKey.create("package/path/OwnerClass", "<init>", "()V");
-    classMemberRecord.logMemberDecl(
-        constructor, Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER, Opcodes.ACC_PRIVATE);
-    classMemberRecord.logMemberUse(constructor, Opcodes.INVOKESPECIAL);
-    classAttributeRecord.setClassAttributes(
-        ClassAttributes.builder()
-            .setClassBinaryName("package/path/OwnerClass$NestedClass")
-            .setNestHost("package/path/OwnerClass")
-            .build());
-    classAttributeRecord.setClassAttributes(
-        ClassAttributes.builder()
-            .setClassBinaryName("package/path/OwnerClass")
-            .addNestMember("package/path/OwnerClass$NestedClass")
-            .build());
-
-    nestCompanions.prepareCompanionClasses();
-
-    assertThat(nestCompanions.getAllCompanionClasses())
-        .containsExactly("package/path/OwnerClass$NestCC");
-  }
-
-  @Test
-  public void preparCompanionClassWriters_multipleCompanionClassesGenerated() {
-    classMemberRecord.logMemberDecl(
-        MethodKey.create("package/path/OwnerClassA", "<init>", "()V"),
-        Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER,
-        Opcodes.ACC_PRIVATE);
-    classMemberRecord.logMemberDecl(
-        MethodKey.create("package/path/OwnerClassA", "method", "(II)I"),
-        Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER,
-        Opcodes.ACC_PRIVATE);
-    classMemberRecord.logMemberDecl(
-        MethodKey.create("package/path/OwnerClassB", "<init>", "()V"),
-        Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER,
-        Opcodes.ACC_PRIVATE);
-
-    classMemberRecord.logMemberUse(
-        MethodKey.create("package/path/OwnerClassA", "<init>", "()V"), Opcodes.INVOKESPECIAL);
-    classMemberRecord.logMemberUse(
-        MethodKey.create("package/path/OwnerClassA", "method", "(II)I"), Opcodes.INVOKESPECIAL);
-    classMemberRecord.logMemberUse(
-        MethodKey.create("package/path/OwnerClassB", "<init>", "()V"), Opcodes.INVOKESPECIAL);
-
-    classAttributeRecord.setClassAttributes(
-        ClassAttributes.builder()
-            .setClassBinaryName("package/path/OwnerClassA$NestedClass")
-            .setNestHost("package/path/OwnerClassA")
-            .build());
-    classAttributeRecord.setClassAttributes(
-        ClassAttributes.builder()
-            .setClassBinaryName("package/path/OwnerClassB$NestedClass")
-            .setNestHost("package/path/OwnerClassB")
-            .build());
-
-    classAttributeRecord.setClassAttributes(
-        ClassAttributes.builder()
-            .setClassBinaryName("package/path/OwnerClassA")
-            .addNestMember("package/path/OwnerClassA$NestedClass")
-            .build());
-    classAttributeRecord.setClassAttributes(
-        ClassAttributes.builder()
-            .setClassBinaryName("package/path/OwnerClassB")
-            .addNestMember("package/path/OwnerClassB$NestedClass")
-            .build());
-
-    nestCompanions.prepareCompanionClasses();
-
-    assertThat(nestCompanions.getAllCompanionClasses())
-        .containsExactly("package/path/OwnerClassA$NestCC", "package/path/OwnerClassB$NestCC");
-  }
-
-  @Test
-  public void prepareCompanionClassWriters_classNameWithDollarSign() {
-    MethodKey constructor = MethodKey.create("package/path/$Owner$Class$", "<init>", "()V");
-
-    classMemberRecord.logMemberDecl(
-        constructor, Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER, Opcodes.ACC_PRIVATE);
-    classMemberRecord.logMemberUse(constructor, Opcodes.INVOKESPECIAL);
-
-    classAttributeRecord.setClassAttributes(
-        ClassAttributes.builder()
-            .setClassBinaryName(constructor.owner() + "$NestClass")
-            .setNestHost(constructor.owner())
-            .build());
-    classAttributeRecord.setClassAttributes(
-        ClassAttributes.builder()
-            .setClassBinaryName(constructor.owner())
-            .addNestMember(constructor.owner() + "$NestClass")
-            .build());
-
-    nestCompanions.prepareCompanionClasses();
-
-    assertThat(nestCompanions.getAllCompanionClasses())
-        .containsExactly("package/path/$Owner$Class$$NestCC");
-  }
-}
diff --git a/src/test/java/com/google/devtools/build/android/desugar/nest/NestDesugaringCoreLibTest.java b/src/test/java/com/google/devtools/build/android/desugar/nest/NestDesugaringCoreLibTest.java
new file mode 100644
index 0000000..fbd3b5e
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/android/desugar/nest/NestDesugaringCoreLibTest.java
@@ -0,0 +1,88 @@
+/*
+ * Copyright 2020 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.android.desugar.nest;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.base.Splitter;
+import com.google.devtools.build.android.desugar.testing.junit.AsmNode;
+import com.google.devtools.build.android.desugar.testing.junit.DesugarRule;
+import com.google.devtools.build.android.desugar.testing.junit.DesugarRunner;
+import com.google.devtools.build.android.desugar.testing.junit.JdkSuppress;
+import com.google.devtools.build.android.desugar.testing.junit.JdkVersion;
+import com.google.devtools.build.android.desugar.testing.junit.RuntimeMethodHandle;
+import java.lang.invoke.MethodHandle;
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.MethodHandles.Lookup;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.objectweb.asm.tree.ClassNode;
+
+/** Tests for accessing private constructors from another class within a nest. */
+@RunWith(DesugarRunner.class)
+@JdkSuppress(minJdkVersion = JdkVersion.V11)
+public class NestDesugaringCoreLibTest {
+
+  private static final Lookup lookup = MethodHandles.lookup();
+
+  @Rule
+  public final DesugarRule desugarRule =
+      DesugarRule.builder(this, lookup)
+          .addSourceInputs(getInputSourceFilesFromJvmOption("input_srcs"))
+          .addJavacOptions("-source 11", "-target 11")
+          .addCommandOptions("desugar_nest_based_private_access", "true")
+          .addCommandOptions("allow_empty_bootclasspath", "true")
+          .addCommandOptions("core_library", "true")
+          .addCommandOptions("desugar_supported_core_libs", "true")
+          .addCommandOptions("rewrite_core_library_prefix", "javadesugar/testing/")
+          .build();
+
+  private static Path[] getInputSourceFilesFromJvmOption(String jvmOptionKey) {
+    return Splitter.on(" ").trimResults().splitToList(System.getProperty(jvmOptionKey)).stream()
+        .map(Paths::get)
+        .toArray(Path[]::new);
+  }
+
+  @Test
+  public void inputClassFileMajorVersions(
+      @AsmNode(className = "javadesugar.testing.TestCoreType$MateA", round = 0) ClassNode before,
+      @AsmNode(className = "jd$.testing.TestCoreType$MateA", round = 1) ClassNode after) {
+    assertThat(before.version).isEqualTo(JdkVersion.V11);
+    assertThat(after.version).isEqualTo(JdkVersion.V1_7);
+  }
+
+  @Test
+  public void invokeInterMatePrivateStaticMethodOfCoreLibType(
+      @RuntimeMethodHandle(className = "jd$.testing.TestCoreType", memberName = "twoSum")
+          MethodHandle twoSum)
+      throws Throwable {
+    long result = (long) twoSum.invoke(1L, 2L);
+    assertThat(result).isEqualTo(3L);
+  }
+
+  @Test
+  public void invokeInterMatePrivateInstanceMethodOfCoreLibType(
+      @RuntimeMethodHandle(className = "jd$.testing.TestCoreType", memberName = "twoSumWithBase")
+          MethodHandle twoSum)
+      throws Throwable {
+    long result = (long) twoSum.invoke(1000L, 1L, 2L);
+    assertThat(result).isEqualTo(1003L);
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/android/desugar/nest/NestDigestTest.java b/src/test/java/com/google/devtools/build/android/desugar/nest/NestDigestTest.java
new file mode 100644
index 0000000..d789b3b
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/android/desugar/nest/NestDigestTest.java
@@ -0,0 +1,151 @@
+// Copyright 2019 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.android.desugar.nest;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.devtools.build.android.desugar.langmodel.ClassAttributeRecord;
+import com.google.devtools.build.android.desugar.langmodel.ClassAttributes;
+import com.google.devtools.build.android.desugar.langmodel.ClassMemberRecord;
+import com.google.devtools.build.android.desugar.langmodel.ClassName;
+import com.google.devtools.build.android.desugar.langmodel.MethodKey;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+import org.objectweb.asm.Opcodes;
+
+/** The tests for {@link NestDigest}. */
+@RunWith(JUnit4.class)
+public class NestDigestTest {
+
+  private final ClassMemberRecord classMemberRecord = ClassMemberRecord.create();
+  private final ClassAttributeRecord classAttributeRecord = ClassAttributeRecord.create();
+  private final NestDigest nestDigest = NestDigest.create(classMemberRecord, classAttributeRecord);
+
+  @Test
+  public void prepareCompanionClassWriters_noCompanionClassesGenerated() {
+    classMemberRecord.logMemberDecl(
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "method", "(II)I"),
+        /* ownerAccess= */ Opcodes.ACC_PUBLIC | Opcodes.ACC_INTERFACE,
+        /* memberDeclAccess= */ Opcodes.ACC_PRIVATE);
+
+    nestDigest.prepareCompanionClasses();
+
+    assertThat(nestDigest.getAllCompanionClassNames()).isEmpty();
+  }
+
+  @Test
+  public void prepareCompanionClassWriters_companionClassesGenerated() {
+    MethodKey constructor =
+        MethodKey.create(ClassName.create("package/path/OwnerClass"), "<init>", "()V");
+    classMemberRecord.logMemberDecl(
+        constructor, Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER, Opcodes.ACC_PRIVATE);
+    classMemberRecord.logMemberUse(constructor, Opcodes.INVOKESPECIAL);
+    classAttributeRecord.setClassAttributes(
+        ClassAttributes.builder()
+            .setClassBinaryName(ClassName.create("package/path/OwnerClass$NestedClass"))
+            .setNestHost(ClassName.create("package/path/OwnerClass"))
+            .build());
+    classAttributeRecord.setClassAttributes(
+        ClassAttributes.builder()
+            .setClassBinaryName(ClassName.create("package/path/OwnerClass"))
+            .addNestMember(ClassName.create("package/path/OwnerClass$NestedClass"))
+            .build());
+
+    nestDigest.prepareCompanionClasses();
+
+    assertThat(nestDigest.getAllCompanionClassNames())
+        .containsExactly("package/path/OwnerClass$NestCC");
+  }
+
+  @Test
+  public void preparCompanionClassWriters_multipleCompanionClassesGenerated() {
+    classMemberRecord.logMemberDecl(
+        MethodKey.create(ClassName.create("package/path/OwnerClassA"), "<init>", "()V"),
+        Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER,
+        Opcodes.ACC_PRIVATE);
+    classMemberRecord.logMemberDecl(
+        MethodKey.create(ClassName.create("package/path/OwnerClassA"), "method", "(II)I"),
+        Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER,
+        Opcodes.ACC_PRIVATE);
+    classMemberRecord.logMemberDecl(
+        MethodKey.create(ClassName.create("package/path/OwnerClassB"), "<init>", "()V"),
+        Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER,
+        Opcodes.ACC_PRIVATE);
+
+    classMemberRecord.logMemberUse(
+        MethodKey.create(ClassName.create("package/path/OwnerClassA"), "<init>", "()V"),
+        Opcodes.INVOKESPECIAL);
+    classMemberRecord.logMemberUse(
+        MethodKey.create(ClassName.create("package/path/OwnerClassA"), "method", "(II)I"),
+        Opcodes.INVOKESPECIAL);
+    classMemberRecord.logMemberUse(
+        MethodKey.create(ClassName.create("package/path/OwnerClassB"), "<init>", "()V"),
+        Opcodes.INVOKESPECIAL);
+
+    classAttributeRecord.setClassAttributes(
+        ClassAttributes.builder()
+            .setClassBinaryName(ClassName.create("package/path/OwnerClassA$NestedClass"))
+            .setNestHost(ClassName.create("package/path/OwnerClassA"))
+            .build());
+    classAttributeRecord.setClassAttributes(
+        ClassAttributes.builder()
+            .setClassBinaryName(ClassName.create("package/path/OwnerClassB$NestedClass"))
+            .setNestHost(ClassName.create("package/path/OwnerClassB"))
+            .build());
+
+    classAttributeRecord.setClassAttributes(
+        ClassAttributes.builder()
+            .setClassBinaryName(ClassName.create("package/path/OwnerClassA"))
+            .addNestMember(ClassName.create("package/path/OwnerClassA$NestedClass"))
+            .build());
+    classAttributeRecord.setClassAttributes(
+        ClassAttributes.builder()
+            .setClassBinaryName(ClassName.create("package/path/OwnerClassB"))
+            .addNestMember(ClassName.create("package/path/OwnerClassB$NestedClass"))
+            .build());
+
+    nestDigest.prepareCompanionClasses();
+
+    assertThat(nestDigest.getAllCompanionClassNames())
+        .containsExactly("package/path/OwnerClassA$NestCC", "package/path/OwnerClassB$NestCC");
+  }
+
+  @Test
+  public void prepareCompanionClassWriters_classNameWithDollarSign() {
+    MethodKey constructor =
+        MethodKey.create(ClassName.create("package/path/$Owner$Class$"), "<init>", "()V");
+
+    classMemberRecord.logMemberDecl(
+        constructor, Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER, Opcodes.ACC_PRIVATE);
+    classMemberRecord.logMemberUse(constructor, Opcodes.INVOKESPECIAL);
+
+    classAttributeRecord.setClassAttributes(
+        ClassAttributes.builder()
+            .setClassBinaryName(ClassName.create(constructor.ownerName() + "$NestClass"))
+            .setNestHost(ClassName.create(constructor.ownerName()))
+            .build());
+    classAttributeRecord.setClassAttributes(
+        ClassAttributes.builder()
+            .setClassBinaryName(ClassName.create(constructor.ownerName()))
+            .addNestMember(ClassName.create(constructor.ownerName() + "$NestClass"))
+            .build());
+
+    nestDigest.prepareCompanionClasses();
+
+    assertThat(nestDigest.getAllCompanionClassNames())
+        .containsExactly("package/path/$Owner$Class$$NestCC");
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/core/javadesugar/testing/BUILD b/src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/core/javadesugar/testing/BUILD
new file mode 100644
index 0000000..300fa54
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/core/javadesugar/testing/BUILD
@@ -0,0 +1,17 @@
+package(
+    default_testonly = 1,
+    default_visibility = ["//src/test/java/com/google/devtools/build/android/desugar:__subpackages__"],
+)
+
+licenses(["notice"])  # Apache 2.0
+
+filegroup(
+    name = "testing",
+    srcs = glob(["*.java"]),
+)
+
+filegroup(
+    name = "srcs",
+    testonly = 0,
+    srcs = glob(["*"]),
+)
diff --git a/src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/core/javadesugar/testing/TestCoreType.java b/src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/core/javadesugar/testing/TestCoreType.java
new file mode 100644
index 0000000..6f42dd1
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/android/desugar/nest/testsrc/simpleunit/core/javadesugar/testing/TestCoreType.java
@@ -0,0 +1,54 @@
+/*
+ * Copyright 2020 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 javadesugar.testing;
+
+/**
+ * A fake core library class for testing core type desugaring. Related flags include,
+ *
+ * <p>--core_library, --desugar_supported_core_libs, --rewrite_core_library_prefix
+ */
+public class TestCoreType {
+
+  /** Invocation entry point for testing to invoke private static methods in anther mate. */
+  public static long twoSum(long x, long y) {
+    return MateA.twoSum(x, y);
+  }
+
+  /** Invocation entry point for testing to invoke private instance methods in anther mate. */
+  public static long twoSumWithBase(long base, long x, long y) {
+    return new MateA(base).twoSumWithBase(x, y);
+  }
+
+  private TestCoreType() {}
+
+  private static class MateA {
+
+    private final long base;
+
+    private MateA(long base) {
+      this.base = base;
+    }
+
+    private static long twoSum(long x, long y) {
+      return x + y;
+    }
+
+    private long twoSumWithBase(long x, long y) {
+      return base + x + y;
+    }
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/CoreLibrarySupport.java b/src/tools/android/java/com/google/devtools/build/android/desugar/CoreLibrarySupport.java
index f58d5a0..aae5b5a 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/CoreLibrarySupport.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/CoreLibrarySupport.java
@@ -94,7 +94,10 @@
     this.rewriter = rewriter;
     this.targetLoader = targetLoader;
     checkArgument(
-        renamedPrefixes.stream().allMatch(prefix -> prefix.startsWith("java/")), renamedPrefixes);
+        renamedPrefixes.stream()
+            .allMatch(prefix -> prefix.startsWith("java/") || prefix.startsWith("javadesugar/")),
+        "Unexpected renamedPrefixes: Actual (%s).",
+        renamedPrefixes);
     this.renamedPrefixes = ImmutableSet.copyOf(renamedPrefixes);
     this.excludeFromEmulation = ImmutableSet.copyOf(excludeFromEmulation);
 
@@ -122,7 +125,8 @@
           "Original renamed, no need to move it: %s",
           move);
       checkArgument(
-          !pair.get(1).startsWith("java/") || isRenamedCoreLibrary(pair.get(1)),
+          !(pair.get(1).startsWith("java/") || pair.get(1).startsWith("javadesugar/"))
+              || isRenamedCoreLibrary(pair.get(1)),
           "Core library target not renamed: %s",
           move);
       checkArgument(
@@ -178,20 +182,26 @@
 
   public boolean isRenamedCoreLibrary(String internalName) {
     String unprefixedName = rewriter.unprefix(internalName);
-    if (!unprefixedName.startsWith("java/") || renamedPrefixes.isEmpty()) {
+    if (!(unprefixedName.startsWith("java/") || unprefixedName.startsWith("javadesugar/"))
+        || renamedPrefixes.isEmpty()) {
       return false; // shortcut
     }
     // Rename any classes desugar might generate under java/ (for emulated interfaces) as well as
     // configured prefixes
     return looksGenerated(unprefixedName)
-        || renamedPrefixes.stream().anyMatch(prefix -> unprefixedName.startsWith(prefix));
+        || renamedPrefixes.stream().anyMatch(unprefixedName::startsWith);
   }
 
   public String renameCoreLibrary(String internalName) {
     internalName = rewriter.unprefix(internalName);
-    return (internalName.startsWith("java/"))
-        ? "j$/" + internalName.substring(/* cut away "java/" prefix */ 5)
-        : internalName;
+    if (internalName.startsWith("java/")) {
+      return "j$/" + internalName.substring(/* cut away "java/" prefix */ 5);
+    }
+    if (internalName.startsWith("javadesugar/")) {
+      return "jd$/" + internalName.substring(/* cut away "javadesugar/" prefix */ 12);
+    }
+
+    return internalName;
   }
 
   public Remapper getRemapper() {
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/Desugar.java b/src/tools/android/java/com/google/devtools/build/android/desugar/Desugar.java
index e5de759..d033715 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/Desugar.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/Desugar.java
@@ -24,6 +24,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.common.io.ByteStreams;
 import com.google.common.io.Closer;
 import com.google.common.io.Resources;
@@ -41,8 +42,8 @@
 import com.google.devtools.build.android.desugar.langmodel.ClassMemberRecord;
 import com.google.devtools.build.android.desugar.langmodel.ClassMemberUseCounter;
 import com.google.devtools.build.android.desugar.nest.NestAnalyzer;
-import com.google.devtools.build.android.desugar.nest.NestCompanions;
 import com.google.devtools.build.android.desugar.nest.NestDesugaring;
+import com.google.devtools.build.android.desugar.nest.NestDigest;
 import com.google.devtools.build.android.desugar.strconcat.IndyStringConcatDesugaring;
 import com.google.devtools.build.lib.worker.WorkerProtocol.WorkRequest;
 import com.google.devtools.build.lib.worker.WorkerProtocol.WorkResponse;
@@ -53,7 +54,6 @@
 import com.google.devtools.common.options.OptionsBase;
 import com.google.devtools.common.options.OptionsParser;
 import com.google.devtools.common.options.ShellQuotedParamsFilePreProcessor;
-import java.io.ByteArrayInputStream;
 import java.io.IOError;
 import java.io.IOException;
 import java.io.InputStream;
@@ -70,6 +70,7 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.regex.Pattern;
 import javax.annotation.Nullable;
@@ -397,7 +398,8 @@
   private final CoreLibraryRewriter rewriter;
   private final LambdaClassMaker lambdas;
   private final GeneratedClassStore store = new GeneratedClassStore();
-  private final ClassMemberUseCounter classMemberUseCounter = new ClassMemberUseCounter();
+  private final ClassMemberUseCounter classMemberUseCounter =
+      new ClassMemberUseCounter(new ConcurrentHashMap<>());
   private final Set<String> visitedExceptionTypes = new LinkedHashSet<>();
   /** The counter to record the times of try-with-resources desugaring is invoked. */
   private final AtomicInteger numOfTryWithResourcesInvoked = new AtomicInteger();
@@ -494,7 +496,7 @@
 
       ImmutableSet.Builder<String> interfaceLambdaMethodCollector = ImmutableSet.builder();
       ClassVsInterface interfaceCache = new ClassVsInterface(classpathReader);
-      CoreLibrarySupport coreLibrarySupport =
+      final CoreLibrarySupport coreLibrarySupport =
           options.desugarCoreLibs
               ? new CoreLibrarySupport(
                   rewriter,
@@ -656,9 +658,14 @@
     ClassAttributeRecord classAttributeRecord = ClassAttributeRecord.create();
     ImmutableList<FileContentProvider<? extends InputStream>> inputFileContents =
         inputFiles.toInputFileStreams();
-    NestCompanions nestCompanions =
+    NestDigest nestDigest =
         NestAnalyzer.analyzeNests(inputFileContents, classMemberRecord, classAttributeRecord);
-    for (FileContentProvider<? extends InputStream> inputFileProvider : inputFileContents) {
+    // Apply core library type name remapping to the digest instance produced by the nest analyzer,
+    // since the analysis-oriented nest analyzer visits core library classes without name remapping
+    // as those transformation-oriented visitors.
+    nestDigest = nestDigest.acceptTypeMapper(rewriter.getPrefixer());
+    for (FileContentProvider<? extends InputStream> inputFileProvider :
+        Iterables.concat(inputFileContents, nestDigest.getCompanionFileProviders())) {
       String inputFilename = inputFileProvider.getBinaryPathName();
       if ("module-info.class".equals(inputFilename)
           || (inputFilename.endsWith("/module-info.class")
@@ -691,8 +698,7 @@
                   interfaceLambdaMethodCollector,
                   writer,
                   reader,
-                  classMemberRecord,
-                  nestCompanions);
+                  nestDigest);
           if (writer == visitor) {
             // Just copy the input if there are no rewritings
             outputFileProvider.write(inputFilename, reader.b);
@@ -728,15 +734,6 @@
         }
       }
     }
-
-    for (FileContentProvider<ByteArrayInputStream> companionFileProvider :
-        nestCompanions.getCompanionFileProviders()) {
-      try (ByteArrayInputStream companionInputStream = companionFileProvider.get()) {
-        outputFileProvider.write(
-            companionFileProvider.getBinaryPathName(),
-            ByteStreams.toByteArray(companionInputStream));
-      }
-    }
   }
 
   /**
@@ -985,8 +982,7 @@
       ImmutableSet.Builder<String> interfaceLambdaMethodCollector,
       UnprefixingClassWriter writer,
       ClassReader input,
-      ClassMemberRecord classMemberRecord,
-      NestCompanions nestCompanions) {
+      NestDigest nestDigest) {
     ClassVisitor visitor = checkNotNull(writer);
 
     if (coreLibrarySupport != null) {
@@ -1065,7 +1061,7 @@
     }
 
     if (options.desugarNestBasedPrivateAccess) {
-      visitor = new NestDesugaring(visitor, nestCompanions, classMemberRecord);
+      visitor = new NestDesugaring(visitor, nestDigest);
     }
 
     if (options.desugarIndifyStringConcat) {
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/io/BUILD b/src/tools/android/java/com/google/devtools/build/android/desugar/io/BUILD
index e10343f..ae739c2 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/io/BUILD
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/io/BUILD
@@ -11,6 +11,7 @@
         "//src/tools/android/java/com/google/devtools/build/android/desugar:__subpackages__",
     ],
     deps = [
+        "//src/tools/android/java/com/google/devtools/build/android/desugar/langmodel",
         "//third_party:asm",
         "//third_party:asm-commons",
         "//third_party:asm-tree",
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/io/CoreLibraryRewriter.java b/src/tools/android/java/com/google/devtools/build/android/desugar/io/CoreLibraryRewriter.java
index a63bc05..71e6ed2 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/io/CoreLibraryRewriter.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/io/CoreLibraryRewriter.java
@@ -13,6 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.android.desugar.io;
 
+import com.google.devtools.build.android.desugar.langmodel.ClassName;
+import com.google.devtools.build.android.desugar.langmodel.TypeMapper;
 import java.io.IOException;
 import java.io.InputStream;
 import javax.annotation.Nullable;
@@ -26,10 +28,13 @@
 
 /** Utility class to prefix or unprefix class names of core library classes */
 public class CoreLibraryRewriter {
+
   private final String prefix;
+  private final TypeMapper prefixer;
 
   public CoreLibraryRewriter(String prefix) {
     this.prefix = prefix;
+    this.prefixer = new TypeMapper(this::prefix);
   }
 
   /**
@@ -40,7 +45,7 @@
     if (prefix.isEmpty()) {
       return new ClassReader(content);
     } else {
-      return new PrefixingClassReader(content, prefix);
+      return new PrefixingClassReader(content, prefixer);
     }
   }
 
@@ -53,7 +58,11 @@
   }
 
   static boolean shouldPrefix(String typeName) {
-    return (typeName.startsWith("java/") || typeName.startsWith("sun/")) && !except(typeName);
+    return (typeName.startsWith("java/")
+            || typeName.startsWith("sun/")
+            || typeName.startsWith("javadesugar/") // Testing-only fake package prefix.
+        )
+        && !except(typeName);
   }
 
   private static boolean except(String typeName) {
@@ -90,6 +99,17 @@
     return prefix;
   }
 
+  public TypeMapper getPrefixer() {
+    return prefixer;
+  }
+
+  private ClassName prefix(ClassName className) {
+    if (shouldPrefix(className.binaryName())) {
+      return className.prependPrefix(prefix);
+    }
+    return className;
+  }
+
   /** Removes prefix from class names */
   public String unprefix(String typeName) {
     if (prefix.isEmpty() || !typeName.startsWith(prefix)) {
@@ -100,54 +120,39 @@
 
   /** ClassReader that prefixes core library class names as they are read */
   private static class PrefixingClassReader extends ClassReader {
-    private final String prefix;
 
-    PrefixingClassReader(InputStream content, String prefix) throws IOException {
+    private final TypeMapper prefixer;
+
+    PrefixingClassReader(InputStream content, TypeMapper prefixer) throws IOException {
       super(content);
-      this.prefix = prefix;
+      this.prefixer = prefixer;
     }
 
     @Override
     public void accept(ClassVisitor cv, Attribute[] attrs, int flags) {
-      cv =
-          new ClassRemapper(
-              cv,
-              new Remapper() {
-                @Override
-                public String map(String typeName) {
-                  return prefix(typeName);
-                }
-              });
+      cv = new ClassRemapper(cv, prefixer);
       super.accept(cv, attrs, flags);
     }
 
     @Override
     public String getClassName() {
-      return prefix(super.getClassName());
+      return prefixer.map(super.getClassName());
     }
 
     @Override
     public String getSuperName() {
       String result = super.getSuperName();
-      return result != null ? prefix(result) : null;
+      return result != null ? prefixer.map(result) : null;
     }
 
     @Override
     public String[] getInterfaces() {
       String[] result = super.getInterfaces();
       for (int i = 0, len = result.length; i < len; ++i) {
-        result[i] = prefix(result[i]);
+        result[i] = prefixer.map(result[i]);
       }
       return result;
     }
-
-    /** Prefixes core library class names with prefix. */
-    private String prefix(String typeName) {
-      if (shouldPrefix(typeName)) {
-        return prefix + typeName;
-      }
-      return typeName;
-    }
   }
 
   /**
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassAttributeRecord.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassAttributeRecord.java
index 4fe3db0..30564d9 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassAttributeRecord.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassAttributeRecord.java
@@ -16,24 +16,29 @@
 
 package com.google.devtools.build.android.desugar.langmodel;
 
+import static com.google.common.base.Preconditions.checkNotNull;
+import static java.util.stream.Collectors.toMap;
+
 import com.google.common.collect.ImmutableSet;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Optional;
 
 /** Tracks {@link ClassAttributes} for all classes under investigation. */
-public class ClassAttributeRecord {
+public final class ClassAttributeRecord implements TypeMappable<ClassAttributeRecord> {
 
-  private final Map<String, ClassAttributes> record = new HashMap<>();
+  private final Map<ClassName, ClassAttributes> record;
 
   public static ClassAttributeRecord create() {
-    return new ClassAttributeRecord();
+    return new ClassAttributeRecord(new HashMap<>());
   }
 
-  private ClassAttributeRecord() {}
+  private ClassAttributeRecord(Map<ClassName, ClassAttributes> record) {
+    this.record = record;
+  }
 
   public ClassAttributes setClassAttributes(ClassAttributes classAttributes) {
-    String classBinaryName = classAttributes.classBinaryName();
+    ClassName classBinaryName = classAttributes.classBinaryName();
     if (record.containsKey(classBinaryName)) {
       throw new IllegalStateException(
           String.format(
@@ -44,19 +49,36 @@
     return record.put(classBinaryName, classAttributes);
   }
 
-  public Optional<String> getNestHost(String className) {
+  public Optional<ClassName> getNestHost(ClassName className) {
     ClassAttributes classAttributes = record.get(className);
-    if (classAttributes != null) {
-      return classAttributes.nestHost();
-    }
-    return Optional.empty();
+    checkNotNull(
+        classAttributes,
+        "Expected recorded ClassAttributes for (%s). Available record: %s",
+        className,
+        record.keySet());
+    return classAttributes.nestHost();
   }
 
-  public ImmutableSet<String> getNestMembers(String className) {
+  public ImmutableSet<ClassName> getNestMembers(ClassName className) {
     ClassAttributes classAttributes = record.get(className);
-    if (classAttributes != null) {
-      return classAttributes.nestMembers();
-    }
-    return ImmutableSet.of();
+    checkNotNull(
+        classAttributes,
+        "Expected recorded ClassAttributes for (%s). Available record: %s",
+        className,
+        record.keySet());
+    return classAttributes.nestMembers();
+  }
+
+  @Override
+  public ClassAttributeRecord acceptTypeMapper(TypeMapper typeMapper) {
+    return new ClassAttributeRecord(
+        this.record.values().stream()
+            .map(attr -> attr.acceptTypeMapper(typeMapper))
+            .collect(
+                toMap(
+                    ClassAttributes::classBinaryName,
+                    attr -> attr,
+                    (prev, next) -> next,
+                    HashMap::new)));
   }
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassAttributes.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassAttributes.java
index 429215e..30b7132 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassAttributes.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassAttributes.java
@@ -26,13 +26,13 @@
  * <p>https://docs.oracle.com/javase/specs/jvms/se11/html/jvms-4.html#jvms-4.7
  */
 @AutoValue
-public abstract class ClassAttributes {
+public abstract class ClassAttributes implements TypeMappable<ClassAttributes> {
 
-  public abstract String classBinaryName();
+  public abstract ClassName classBinaryName();
 
-  public abstract Optional<String> nestHost();
+  public abstract Optional<ClassName> nestHost();
 
-  public abstract ImmutableSet<String> nestMembers();
+  public abstract ImmutableSet<ClassName> nestMembers();
 
   // Include other class attributes as necessary.
 
@@ -40,17 +40,29 @@
     return new AutoValue_ClassAttributes.Builder();
   }
 
+  @Override
+  public ClassAttributes acceptTypeMapper(TypeMapper typeMapper) {
+    ClassAttributesBuilder mappedBuilder = builder();
+    mappedBuilder.setClassBinaryName(classBinaryName().acceptTypeMapper(typeMapper));
+    if (nestHost().isPresent()) {
+      mappedBuilder.setNestHost(nestHost().get().acceptTypeMapper(typeMapper));
+    }
+    nestMembers().stream().map(typeMapper::map).forEach(mappedBuilder::addNestMember);
+    mappedBuilder.setClassBinaryName(classBinaryName().acceptTypeMapper(typeMapper));
+    return mappedBuilder.build();
+  }
+
   /** The builder of {@link ClassAttributes}. */
   @AutoValue.Builder
   public abstract static class ClassAttributesBuilder {
 
-    public abstract ClassAttributesBuilder setClassBinaryName(String classBinaryName);
+    public abstract ClassAttributesBuilder setClassBinaryName(ClassName classBinaryName);
 
-    public abstract ClassAttributesBuilder setNestHost(String nestHost);
+    public abstract ClassAttributesBuilder setNestHost(ClassName nestHost);
 
-    abstract ImmutableSet.Builder<String> nestMembersBuilder();
+    abstract ImmutableSet.Builder<ClassName> nestMembersBuilder();
 
-    public ClassAttributesBuilder addNestMember(String nestMember) {
+    public ClassAttributesBuilder addNestMember(ClassName nestMember) {
       nestMembersBuilder().add(nestMember);
       return this;
     }
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberKey.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberKey.java
index 078bfef..b80ca57 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberKey.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberKey.java
@@ -17,13 +17,13 @@
 package com.google.devtools.build.android.desugar.langmodel;
 
 /** The key that indexes a class member, including fields, constructors and methods. */
-public abstract class ClassMemberKey {
+public abstract class ClassMemberKey<T extends ClassMemberKey<T>> implements TypeMappable<T> {
 
   /**
    * The class or interface that owns the class member, i.e. the immediate enclosing class of the
    * declaration site of a field, constructor or method.
    */
-  public abstract String owner();
+  public abstract ClassName owner();
 
   /** The simple name of the class member. */
   public abstract String name();
@@ -31,6 +31,11 @@
   /** The descriptor of the class member. */
   public abstract String descriptor();
 
+  /** The binary name of {@link #owner()} */
+  public final String ownerName() {
+    return owner().binaryName();
+  }
+
   /** Whether member key represents a constructor. */
   public final boolean isConstructor() {
     return "<init>".equals(name());
@@ -40,4 +45,8 @@
   final String nameWithSuffix(String suffix) {
     return name() + '$' + suffix;
   }
+
+  /** Produces a new class member key by mapping this key instance. */
+  @Override
+  public abstract T acceptTypeMapper(TypeMapper typeMapper);
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberRecord.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberRecord.java
index b56353b..d6bd18c 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberRecord.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberRecord.java
@@ -17,6 +17,7 @@
 package com.google.devtools.build.android.desugar.langmodel;
 
 import static com.google.common.collect.ImmutableList.toImmutableList;
+import static java.util.stream.Collectors.toMap;
 
 import com.google.common.collect.ImmutableList;
 import java.util.LinkedHashMap;
@@ -27,10 +28,10 @@
  * A record that tracks the declarations and usages of a class member, including fields,
  * constructors and methods.
  */
-public final class ClassMemberRecord {
+public final class ClassMemberRecord implements TypeMappable<ClassMemberRecord> {
 
   /** Tracks a class member with a reason. */
-  private final Map<ClassMemberKey, ClassMemberTrackReason> reasons;
+  private final Map<ClassMemberKey<?>, ClassMemberTrackReason> reasons;
 
   /** The factory method of this class. */
   public static ClassMemberRecord create() {
@@ -49,7 +50,7 @@
             });
   }
 
-  private ClassMemberRecord(Map<ClassMemberKey, ClassMemberTrackReason> reasons) {
+  private ClassMemberRecord(Map<ClassMemberKey<?>, ClassMemberTrackReason> reasons) {
     this.reasons = reasons;
   }
 
@@ -68,16 +69,16 @@
     return !reasons.isEmpty();
   }
 
-  public boolean hasTrackingReason(ClassMemberKey classMemberKey) {
+  public boolean hasTrackingReason(ClassMemberKey<?> classMemberKey) {
     return reasons.containsKey(classMemberKey);
   }
 
-  boolean hasDeclReason(ClassMemberKey classMemberKey) {
+  boolean hasDeclReason(ClassMemberKey<?> classMemberKey) {
     return hasTrackingReason(classMemberKey) && reasons.get(classMemberKey).hasDeclReason();
   }
 
   /** Find the original access code for the owner of the class member. */
-  int findOwnerAccessCode(ClassMemberKey memberKey) {
+  int findOwnerAccessCode(ClassMemberKey<?> memberKey) {
     if (reasons.containsKey(memberKey)) {
       return reasons.get(memberKey).getOwnerAccess();
     }
@@ -85,7 +86,7 @@
   }
 
   /** Find the original access code for the class member declaration. */
-  int findMemberAccessCode(ClassMemberKey memberKey) {
+  int findMemberAccessCode(ClassMemberKey<?> memberKey) {
     if (reasons.containsKey(memberKey)) {
       return reasons.get(memberKey).getMemberAccess();
     }
@@ -93,7 +94,7 @@
   }
 
   /** Find all invocation codes of a class member. */
-  public ImmutableList<MemberUseKind> findAllMemberUseKind(ClassMemberKey memberKey) {
+  public ImmutableList<MemberUseKind> findAllMemberUseKind(ClassMemberKey<?> memberKey) {
     if (reasons.containsKey(memberKey)) {
       return ImmutableList.copyOf(reasons.get(memberKey).getUseAccesses());
     }
@@ -102,14 +103,14 @@
 
   /** Logs the declaration of a class member. */
   public ClassMemberTrackReason logMemberDecl(
-      ClassMemberKey memberKey, int ownerAccess, int memberDeclAccess) {
+      ClassMemberKey<?> memberKey, int ownerAccess, int memberDeclAccess) {
     return reasons
         .computeIfAbsent(memberKey, classMemberKey -> new ClassMemberTrackReason())
         .setDeclAccess(ownerAccess, memberDeclAccess);
   }
 
   /** Logs the use of a class member, including field access and method invocations. */
-  public ClassMemberTrackReason logMemberUse(ClassMemberKey memberKey, int invokeOpcode) {
+  public ClassMemberTrackReason logMemberUse(ClassMemberKey<?> memberKey, int invokeOpcode) {
     return reasons
         .computeIfAbsent(memberKey, classMemberKey -> new ClassMemberTrackReason())
         .addUseAccess(invokeOpcode);
@@ -122,4 +123,11 @@
             reasons.merge(
                 classMemberKey, classMemberTrackReason, ClassMemberTrackReason::mergeFrom));
   }
+
+  @Override
+  public ClassMemberRecord acceptTypeMapper(TypeMapper typeMapper) {
+    return new ClassMemberRecord(
+        reasons.keySet().stream()
+            .collect(toMap(key -> key.acceptTypeMapper(typeMapper), reasons::get)));
+  }
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberUse.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberUse.java
index 75c9b6a..e9ea744 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberUse.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberUse.java
@@ -24,24 +24,29 @@
  * access.
  */
 @AutoValue
-public abstract class ClassMemberUse {
+public abstract class ClassMemberUse implements TypeMappable<ClassMemberUse> {
 
-  public abstract ClassMemberKey method();
+  public abstract ClassMemberKey<?> method();
 
   public abstract MemberUseKind useKind();
 
-  public static ClassMemberUse create(ClassMemberKey memberKey, MemberUseKind memberUseKind) {
+  public static ClassMemberUse create(ClassMemberKey<?> memberKey, MemberUseKind memberUseKind) {
     return new AutoValue_ClassMemberUse(memberKey, memberUseKind);
   }
 
   // Performs the current member use on the given class visitor.
   public final void acceptClassMethodInsn(MethodVisitor mv) {
-    ClassMemberKey method = method();
+    ClassMemberKey<?> method = method();
     mv.visitMethodInsn(
         useKind().getOpcode(),
-        method.owner(),
+        method.ownerName(),
         method.name(),
         method.descriptor(),
         /* isInterface= */ false);
   }
+
+  @Override
+  public ClassMemberUse acceptTypeMapper(TypeMapper typeMapper) {
+    return create(method().acceptTypeMapper(typeMapper), useKind());
+  }
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberUseCounter.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberUseCounter.java
index b59cd83..ae4051b 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberUseCounter.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassMemberUseCounter.java
@@ -16,15 +16,19 @@
 
 package com.google.devtools.build.android.desugar.langmodel;
 
-import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentMap;
 import java.util.concurrent.atomic.LongAdder;
+import java.util.stream.Collectors;
 
 /** The counter used to track a class member use. */
-public final class ClassMemberUseCounter {
+public final class ClassMemberUseCounter implements TypeMappable<ClassMemberUseCounter> {
 
   /** Tracks a class member with its associated count. */
-  private final ConcurrentHashMap<ClassMemberUse, LongAdder> memberUseCounter =
-      new ConcurrentHashMap<>();
+  private final ConcurrentMap<ClassMemberUse, LongAdder> memberUseCounter;
+
+  public ClassMemberUseCounter(ConcurrentMap<ClassMemberUse, LongAdder> memberUseCounter) {
+    this.memberUseCounter = memberUseCounter;
+  }
 
   /** Increases the member use count by one when an member access is encountered. */
   public void incrementMemberUseCount(ClassMemberUse classMemberUse) {
@@ -35,4 +39,13 @@
   public long getMemberUseCount(ClassMemberUse memberKey) {
     return memberUseCounter.getOrDefault(memberKey, new LongAdder()).longValue();
   }
+
+  @Override
+  public ClassMemberUseCounter acceptTypeMapper(TypeMapper typeMapper) {
+    return new ClassMemberUseCounter(
+        memberUseCounter.keySet().stream()
+            .collect(
+                Collectors.toConcurrentMap(
+                    memberUse -> memberUse.acceptTypeMapper(typeMapper), memberUseCounter::get)));
+  }
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassName.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassName.java
new file mode 100644
index 0000000..fb47b5f
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/ClassName.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2020 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.android.desugar.langmodel;
+
+import static com.google.common.base.Preconditions.checkState;
+
+import com.google.auto.value.AutoValue;
+import org.objectweb.asm.Type;
+
+/**
+ * Represents the identifiable name of a Java class or interface with convenient conversions among
+ * different names.
+ */
+@AutoValue
+public abstract class ClassName implements TypeMappable<ClassName> {
+
+  /**
+   * The textual binary name used to index the class name, as defined at,
+   * https://docs.oracle.com/javase/specs/jvms/se11/html/jvms-4.html#jvms-4.2.1
+   */
+  public abstract String binaryName();
+
+  public static ClassName create(String binaryName) {
+    checkState(
+        !binaryName.contains("."),
+        "Expected a binary/internal class name ('/'-delimited) instead of a qualified name."
+            + " Actual: (%s)",
+        binaryName);
+    return new AutoValue_ClassName(binaryName);
+  }
+
+  public static ClassName create(Class<?> clazz) {
+    return create(Type.getInternalName(clazz));
+  }
+
+  public final Type toAsmObjectType() {
+    return Type.getObjectType(binaryName());
+  }
+
+  public final String qualifiedName() {
+    return binaryName().replace('/', '.');
+  }
+
+  public ClassName innerClass(String innerClassSimpleName) {
+    return ClassName.create(binaryName() + '$' + innerClassSimpleName);
+  }
+
+  public final String simpleName() {
+    String binaryName = binaryName();
+    int i = binaryName.lastIndexOf('/');
+    return i < 0 ? binaryName : binaryName.substring(i + 1);
+  }
+
+  public final String classFilePathName() {
+    return binaryName() + ".class";
+  }
+
+  public final ClassName prependPrefix(String prefix) {
+    return ClassName.create(prefix + binaryName());
+  }
+
+  @Override
+  public ClassName acceptTypeMapper(TypeMapper typeMapper) {
+    return typeMapper.map(this);
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/FieldKey.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/FieldKey.java
index c954ab2..0ed43e2 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/FieldKey.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/FieldKey.java
@@ -23,24 +23,22 @@
 
 /** The key to index a class or interface field. */
 @AutoValue
-public abstract class FieldKey extends ClassMemberKey {
+public abstract class FieldKey extends ClassMemberKey<FieldKey> {
 
   /** The factory method for {@link FieldKey}. */
-  public static FieldKey create(String ownerClass, String name, String descriptor) {
-    checkState(
-        !ownerClass.contains("."),
-        "Expected a binary/internal class name ('/'-delimited) instead of a qualified name."
-            + " Actual: (%s#%s:%s)",
-        ownerClass,
-        name,
-        descriptor);
+  public static FieldKey create(ClassName owner, String name, String descriptor) {
     checkState(
         !descriptor.startsWith("("),
         "Expected a type descriptor for field instead of a method descriptor. Actual: (%s#%s:%s)",
-        ownerClass,
+        owner,
         name,
         descriptor);
-    return new AutoValue_FieldKey(ownerClass, name, descriptor);
+    return new AutoValue_FieldKey(owner, name, descriptor);
+  }
+
+  @Override
+  public FieldKey acceptTypeMapper(TypeMapper typeMapper) {
+    return FieldKey.create(typeMapper.map(owner()), name(), typeMapper.mapDesc(descriptor()));
   }
 
   /**
@@ -82,7 +80,7 @@
     return MethodKey.create(
         owner(),
         nameWithSuffix("bridge_getter"),
-        Type.getMethodDescriptor(getFieldType(), Type.getObjectType(owner())));
+        Type.getMethodDescriptor(getFieldType(), Type.getObjectType(ownerName())));
   }
 
   /**
@@ -102,7 +100,7 @@
     return MethodKey.create(
         owner(),
         nameWithSuffix("bridge_setter"),
-        Type.getMethodDescriptor(getFieldType(), Type.getObjectType(owner()), getFieldType()));
+        Type.getMethodDescriptor(getFieldType(), Type.getObjectType(ownerName()), getFieldType()));
   }
 
   public Type getFieldType() {
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/LangModelHelper.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/LangModelHelper.java
index 731744d..d339ed5 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/LangModelHelper.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/LangModelHelper.java
@@ -142,9 +142,9 @@
    * enclosing method.
    */
   public static boolean isCrossMateRefInNest(
-      ClassMemberKey referencedMember, MethodKey enclosingMethod) {
-    String enclosingClassName = enclosingMethod.owner();
-    String referencedMemberName = referencedMember.owner();
+      ClassMemberKey<?> referencedMember, MethodKey enclosingMethod) {
+    String enclosingClassName = enclosingMethod.ownerName();
+    String referencedMemberName = referencedMember.ownerName();
     return (isEligibleAsInnerClass(enclosingClassName)
             || isEligibleAsInnerClass(referencedMemberName))
         && !referencedMemberName.equals(enclosingClassName);
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/MethodDeclInfo.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/MethodDeclInfo.java
index 7f64d26..920b120 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/MethodDeclInfo.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/MethodDeclInfo.java
@@ -22,7 +22,7 @@
 
 /** A unit data object represents a class or interface declaration. */
 // TODO(deltazulu): Consider @AutoValue-ize this class. (String[] as attribute is not supported).
-public final class MethodDeclInfo {
+public final class MethodDeclInfo implements TypeMappable<MethodDeclInfo> {
   public final MethodKey methodKey;
   public final int ownerAccess;
   public final int memberAccess;
@@ -63,4 +63,10 @@
           : visitor.visitClassInstanceMethod(this, param);
     }
   }
+
+  @Override
+  public MethodDeclInfo acceptTypeMapper(TypeMapper typeMapper) {
+    return new MethodDeclInfo(
+        methodKey.acceptTypeMapper(typeMapper), ownerAccess, memberAccess, signature, exceptions);
+  }
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/MethodKey.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/MethodKey.java
index 8c6d15e..3e153f2 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/MethodKey.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/MethodKey.java
@@ -24,17 +24,10 @@
 
 /** The key to index a class or interface method or constructor. */
 @AutoValue
-public abstract class MethodKey extends ClassMemberKey {
+public abstract class MethodKey extends ClassMemberKey<MethodKey> {
 
   /** The factory method for {@link MethodKey}. */
-  public static MethodKey create(String ownerClass, String name, String descriptor) {
-    checkState(
-        !ownerClass.contains("."),
-        "Expected a binary/internal class name ('/'-delimited) instead of a qualified name."
-            + " Actual: (%s#%s:%s)",
-        ownerClass,
-        name,
-        descriptor);
+  public static MethodKey create(ClassName ownerClass, String name, String descriptor) {
     checkState(
         descriptor.isEmpty() // Allows empty descriptor for non-overloaded methods.
             || descriptor.startsWith("("),
@@ -56,37 +49,36 @@
   }
 
   /** The synthetic constructor for a private constructor. */
-  public final MethodKey bridgeOfConstructor(String nestCompanion) {
+  public final MethodKey bridgeOfConstructor(ClassName nestCompanion) {
     checkState(isConstructor(), "Expect to use for a constructor but is %s", this);
-    Type companionClassType = Type.getObjectType(nestCompanion);
+    Type companionClassType = nestCompanion.toAsmObjectType();
     Type[] argumentTypes = getArgumentTypes();
     Type[] bridgeConstructorArgTypes = Arrays.copyOf(argumentTypes, argumentTypes.length + 1);
     bridgeConstructorArgTypes[argumentTypes.length] = companionClassType;
-    return MethodKey.create(
+    return create(
         owner(), name(), Type.getMethodDescriptor(getReturnType(), bridgeConstructorArgTypes));
   }
 
   /** The synthetic bridge method for a private static method in a class. */
   public final MethodKey bridgeOfClassStaticMethod() {
     checkState(!isConstructor(), "Expect a non-constructor method but is a constructor %s", this);
-    return MethodKey.create(owner(), nameWithSuffix("bridge"), descriptor());
+    return create(owner(), nameWithSuffix("bridge"), descriptor());
   }
 
   /** The synthetic bridge method for a private instance method in a class. */
   public final MethodKey bridgeOfClassInstanceMethod() {
-    return MethodKey.create(
-        owner(), nameWithSuffix("bridge"), instanceMethodToStaticDescriptor(this));
+    return create(owner(), nameWithSuffix("bridge"), instanceMethodToStaticDescriptor(this));
   }
 
   /** The substitute method for a private static method in an interface. */
   public final MethodKey substituteOfInterfaceStaticMethod() {
     checkState(!isConstructor(), "Expect a non-constructor: %s", this);
-    return MethodKey.create(owner(), name(), descriptor());
+    return create(owner(), name(), descriptor());
   }
 
   /** The substitute method for a private instance method in an interface. */
   public final MethodKey substituteOfInterfaceInstanceMethod() {
-    return MethodKey.create(owner(), name(), instanceMethodToStaticDescriptor(this));
+    return create(owner(), name(), instanceMethodToStaticDescriptor(this));
   }
 
   /** The descriptor of the static version of a given instance method. */
@@ -94,11 +86,16 @@
     checkState(!methodKey.isConstructor(), "Expect a Non-constructor method: %s", methodKey);
     Type[] argumentTypes = methodKey.getArgumentTypes();
     Type[] bridgeMethodArgTypes = new Type[argumentTypes.length + 1];
-    bridgeMethodArgTypes[0] = Type.getObjectType(methodKey.owner());
+    bridgeMethodArgTypes[0] = Type.getObjectType(methodKey.ownerName());
     System.arraycopy(argumentTypes, 0, bridgeMethodArgTypes, 1, argumentTypes.length);
     return Type.getMethodDescriptor(methodKey.getReturnType(), bridgeMethodArgTypes);
   }
 
+  @Override
+  public MethodKey acceptTypeMapper(TypeMapper typeMapper) {
+    return MethodKey.create(typeMapper.map(owner()), name(), typeMapper.mapDesc(descriptor()));
+  }
+
   /**
    * Accepts a {@link MethodInstrVisitor} that visits all kinds of method invocation instructions.
    */
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/TypeMappable.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/TypeMappable.java
new file mode 100644
index 0000000..b036e8b
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/TypeMappable.java
@@ -0,0 +1,32 @@
+/*
+ * Copyright 2020 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.android.desugar.langmodel;
+
+/**
+ * Imposes that the implementing class is to support deep type remapping with a given {@link
+ * TypeMapper}.
+ */
+@FunctionalInterface
+public interface TypeMappable<T> {
+
+  /**
+   * Accepts a type mapper and returns a new instance of remapped struct without changing the
+   * original source instance. Please apply {@param typeMapper} to any index-able state of the
+   * implementation class.
+   */
+  T acceptTypeMapper(TypeMapper typeMapper);
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/TypeMapper.java b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/TypeMapper.java
new file mode 100644
index 0000000..4e0d1e9
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/langmodel/TypeMapper.java
@@ -0,0 +1,39 @@
+/*
+ * Copyright 2020 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.android.desugar.langmodel;
+
+import java.util.function.Function;
+import org.objectweb.asm.commons.Remapper;
+
+/** Maps a type to another based on binary names. */
+public final class TypeMapper extends Remapper {
+
+  private final Function<ClassName, ClassName> classNameMapper;
+
+  public TypeMapper(Function<ClassName, ClassName> classNameMapper) {
+    this.classNameMapper = classNameMapper;
+  }
+
+  @Override
+  public String map(String binaryName) {
+    return map(ClassName.create(binaryName)).binaryName();
+  }
+
+  public ClassName map(ClassName internalName) {
+    return classNameMapper.apply(internalName);
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/CrossMateMainCollector.java b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/CrossMateMainCollector.java
index 521e7fb..24d7b65 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/CrossMateMainCollector.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/CrossMateMainCollector.java
@@ -17,8 +17,8 @@
 import com.google.devtools.build.android.desugar.langmodel.ClassAttributeRecord;
 import com.google.devtools.build.android.desugar.langmodel.ClassAttributes;
 import com.google.devtools.build.android.desugar.langmodel.ClassAttributes.ClassAttributesBuilder;
-import com.google.devtools.build.android.desugar.langmodel.ClassMemberKey;
 import com.google.devtools.build.android.desugar.langmodel.ClassMemberRecord;
+import com.google.devtools.build.android.desugar.langmodel.ClassName;
 import com.google.devtools.build.android.desugar.langmodel.FieldKey;
 import com.google.devtools.build.android.desugar.langmodel.LangModelHelper;
 import com.google.devtools.build.android.desugar.langmodel.MethodKey;
@@ -46,7 +46,7 @@
 
   private final ClassAttributesBuilder classAttributesBuilder = ClassAttributes.builder();
 
-  private String className;
+  private ClassName className;
   private int classAccessCode;
   private boolean isInNest;
 
@@ -65,7 +65,7 @@
       String signature,
       String superName,
       String[] interfaces) {
-    className = name;
+    className = ClassName.create(name);
     classAccessCode = access;
     classAttributesBuilder.setClassBinaryName(className);
     super.visit(
@@ -115,14 +115,14 @@
   @Override
   public void visitNestHost(String nestHost) {
     isInNest = true;
-    classAttributesBuilder.setNestHost(nestHost);
+    classAttributesBuilder.setNestHost(ClassName.create(nestHost));
     super.visitNestHost(nestHost);
   }
 
   @Override
   public void visitNestMember(String nestMember) {
     isInNest = true;
-    classAttributesBuilder.addNestMember(nestMember);
+    classAttributesBuilder.addNestMember(ClassName.create(nestMember));
     super.visitNestMember(nestMember);
   }
 
@@ -161,7 +161,7 @@
 
     @Override
     public void visitFieldInsn(int opcode, String owner, String name, String descriptor) {
-      ClassMemberKey memberKey = FieldKey.create(owner, name, descriptor);
+      FieldKey memberKey = FieldKey.create(ClassName.create(owner), name, descriptor);
       if (LangModelHelper.isCrossMateRefInNest(memberKey, enclosingMethodKey)) {
         memberRecord.logMemberUse(memberKey, opcode);
       }
@@ -171,7 +171,7 @@
     @Override
     public void visitMethodInsn(
         int opcode, String owner, String name, String descriptor, boolean isInterface) {
-      ClassMemberKey memberKey = MethodKey.create(owner, name, descriptor);
+      MethodKey memberKey = MethodKey.create(ClassName.create(owner), name, descriptor);
       if (isInterface || LangModelHelper.isCrossMateRefInNest(memberKey, enclosingMethodKey)) {
         memberRecord.logMemberUse(memberKey, opcode);
       }
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/FieldAccessBridgeEmitter.java b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/FieldAccessBridgeEmitter.java
index d2a4643..cbc1978 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/FieldAccessBridgeEmitter.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/FieldAccessBridgeEmitter.java
@@ -47,7 +47,7 @@
             /* signature= */ null,
             /* exceptions= */ null);
 
-    mv.visitFieldInsn(GETSTATIC, fieldKey.owner(), fieldKey.name(), fieldKey.descriptor());
+    mv.visitFieldInsn(GETSTATIC, fieldKey.ownerName(), fieldKey.name(), fieldKey.descriptor());
     Type fieldType = fieldKey.getFieldType();
     mv.visitInsn(fieldType.getOpcode(Opcodes.IRETURN));
     int fieldTypeSize = fieldType.getSize();
@@ -72,7 +72,8 @@
     mv.visitVarInsn(fieldType.getOpcode(Opcodes.ILOAD), 0);
     mv.visitInsn(
         LangModelHelper.getTypeSizeAlignedDupOpcode(ImmutableList.of(fieldKey.getFieldType())));
-    mv.visitFieldInsn(Opcodes.PUTSTATIC, fieldKey.owner(), fieldKey.name(), fieldKey.descriptor());
+    mv.visitFieldInsn(
+        Opcodes.PUTSTATIC, fieldKey.ownerName(), fieldKey.name(), fieldKey.descriptor());
     mv.visitInsn(fieldType.getOpcode(Opcodes.IRETURN));
     int fieldTypeSize = fieldType.getSize();
     mv.visitMaxs(fieldTypeSize, fieldTypeSize);
@@ -93,7 +94,8 @@
             /* exceptions= */ null);
     mv.visitCode();
     mv.visitVarInsn(Opcodes.ALOAD, 0);
-    mv.visitFieldInsn(Opcodes.GETFIELD, fieldKey.owner(), fieldKey.name(), fieldKey.descriptor());
+    mv.visitFieldInsn(
+        Opcodes.GETFIELD, fieldKey.ownerName(), fieldKey.name(), fieldKey.descriptor());
     Type fieldType = fieldKey.getFieldType();
     mv.visitInsn(fieldType.getOpcode(Opcodes.IRETURN));
     int fieldTypeSize = fieldType.getSize();
@@ -121,7 +123,8 @@
         LangModelHelper.getTypeSizeAlignedDupOpcode(
             ImmutableList.of(fieldKey.getFieldType()),
             ImmutableList.of(Type.getType(Object.class))));
-    mv.visitFieldInsn(Opcodes.PUTFIELD, fieldKey.owner(), fieldKey.name(), fieldKey.descriptor());
+    mv.visitFieldInsn(
+        Opcodes.PUTFIELD, fieldKey.ownerName(), fieldKey.name(), fieldKey.descriptor());
     mv.visitInsn(fieldType.getOpcode(Opcodes.IRETURN));
     int fieldTypeSize = fieldType.getSize();
     mv.visitMaxs(fieldTypeSize, fieldTypeSize);
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/MethodAccessorEmitter.java b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/MethodAccessorEmitter.java
index f842243..c9e29b8 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/MethodAccessorEmitter.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/MethodAccessorEmitter.java
@@ -21,6 +21,7 @@
 import static org.objectweb.asm.Opcodes.ACC_STATIC;
 import static org.objectweb.asm.Opcodes.ACC_SYNTHETIC;
 
+import com.google.devtools.build.android.desugar.langmodel.ClassName;
 import com.google.devtools.build.android.desugar.langmodel.MethodDeclInfo;
 import com.google.devtools.build.android.desugar.langmodel.MethodDeclVisitor;
 import com.google.devtools.build.android.desugar.langmodel.MethodKey;
@@ -36,10 +37,10 @@
 final class MethodAccessorEmitter
     implements MethodDeclVisitor<MethodVisitor, MethodDeclInfo, ClassVisitor> {
 
-  private final NestCompanions nestCompanions;
+  private final NestDigest nestDigest;
 
-  MethodAccessorEmitter(NestCompanions nestCompanions) {
-    this.nestCompanions = nestCompanions;
+  MethodAccessorEmitter(NestDigest nestDigest) {
+    this.nestDigest = nestDigest;
   }
 
   /**
@@ -59,7 +60,7 @@
    */
   @Override
   public MethodVisitor visitClassConstructor(MethodDeclInfo methodDeclInfo, ClassVisitor cv) {
-    String nestCompanion = nestCompanions.nestCompanion(methodDeclInfo.methodKey.owner());
+    ClassName nestCompanion = nestDigest.nestCompanion(methodDeclInfo.methodKey.owner());
     MethodKey constructorBridge = methodDeclInfo.methodKey.bridgeOfConstructor(nestCompanion);
     MethodVisitor mv =
         cv.visitMethod(
@@ -79,7 +80,7 @@
     }
     mv.visitMethodInsn(
         Opcodes.INVOKESPECIAL,
-        methodDeclInfo.methodKey.owner(),
+        methodDeclInfo.methodKey.ownerName(),
         methodDeclInfo.methodKey.name(),
         methodDeclInfo.methodKey.descriptor(),
         /* isInterface= */ false);
@@ -126,7 +127,7 @@
 
     mv.visitMethodInsn(
         Opcodes.INVOKESTATIC,
-        methodDeclInfo.methodKey.owner(),
+        methodDeclInfo.methodKey.ownerName(),
         methodDeclInfo.methodKey.name(),
         methodDeclInfo.methodKey.descriptor(),
         /* isInterface= */ false);
@@ -169,7 +170,7 @@
 
     mv.visitMethodInsn(
         Opcodes.INVOKESPECIAL,
-        methodDeclInfo.methodKey.owner(),
+        methodDeclInfo.methodKey.ownerName(),
         methodDeclInfo.methodKey.name(),
         methodDeclInfo.methodKey.descriptor(),
         /* isInterface= */ false);
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestAnalyzer.java b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestAnalyzer.java
index c4658cf..14a0e77 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestAnalyzer.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestAnalyzer.java
@@ -27,12 +27,12 @@
 
 /**
  * An analyzer that performs nest-based analysis and save the states to {@link ClassMemberRecord}
- * and generated {@link NestCompanions}.
+ * and generated {@link NestDigest}.
  */
 public class NestAnalyzer {
 
   private final ImmutableList<FileContentProvider<? extends InputStream>> inputFileContents;
-  private final NestCompanions nestCompanions;
+  private final NestDigest nestDigest;
   private final ClassMemberRecord classMemberRecord;
   private final ClassAttributeRecord classAttributeRecord;
 
@@ -42,27 +42,26 @@
    *
    * @return A manager class for nest companions.
    */
-  public static NestCompanions analyzeNests(
+  public static NestDigest analyzeNests(
       ImmutableList<FileContentProvider<? extends InputStream>> inputFileContents,
       ClassMemberRecord classMemberRecord,
       ClassAttributeRecord classAttributeRecord)
       throws IOException {
-    NestCompanions nestCompanions = NestCompanions.create(classMemberRecord, classAttributeRecord);
+    NestDigest nestDigest = NestDigest.create(classMemberRecord, classAttributeRecord);
     NestAnalyzer nestAnalyzer =
-        new NestAnalyzer(
-            inputFileContents, nestCompanions, classMemberRecord, classAttributeRecord);
+        new NestAnalyzer(inputFileContents, nestDigest, classMemberRecord, classAttributeRecord);
     nestAnalyzer.analyze();
-    return nestCompanions;
+    return nestDigest;
   }
 
   @VisibleForTesting
   NestAnalyzer(
       ImmutableList<FileContentProvider<? extends InputStream>> inputFileContents,
-      NestCompanions nestCompanions,
+      NestDigest nestDigest,
       ClassMemberRecord classMemberRecord,
       ClassAttributeRecord classAttributeRecord) {
     this.inputFileContents = checkNotNull(inputFileContents);
-    this.nestCompanions = checkNotNull(nestCompanions);
+    this.nestDigest = checkNotNull(nestDigest);
     this.classMemberRecord = checkNotNull(classMemberRecord);
     this.classAttributeRecord = classAttributeRecord;
   }
@@ -81,6 +80,6 @@
       }
     }
     classMemberRecord.filterUsedMemberWithTrackedDeclaration();
-    nestCompanions.prepareCompanionClasses();
+    nestDigest.prepareCompanionClasses();
   }
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestBridgeRefConverter.java b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestBridgeRefConverter.java
index 460ddc2..9844ed6 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestBridgeRefConverter.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestBridgeRefConverter.java
@@ -17,7 +17,7 @@
 import static com.google.devtools.build.android.desugar.langmodel.LangModelHelper.isCrossMateRefInNest;
 
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.android.desugar.langmodel.ClassMemberRecord;
+import com.google.devtools.build.android.desugar.langmodel.ClassName;
 import com.google.devtools.build.android.desugar.langmodel.FieldInstrVisitor;
 import com.google.devtools.build.android.desugar.langmodel.FieldKey;
 import com.google.devtools.build.android.desugar.langmodel.LangModelHelper;
@@ -32,29 +32,26 @@
 public final class NestBridgeRefConverter extends MethodVisitor {
 
   private final MethodKey enclosingMethodKey;
-  private final ClassMemberRecord bridgeOrigins;
+  private final NestDigest nestDigest;
   private final FieldAccessToBridgeRedirector directFieldAccessReplacer;
   private final MethodToBridgeRedirector methodToBridgeRedirector;
 
   NestBridgeRefConverter(
-      @Nullable MethodVisitor methodVisitor,
-      MethodKey methodKey,
-      ClassMemberRecord bridgeOrigins,
-      NestCompanions nestCompanions) {
+      @Nullable MethodVisitor methodVisitor, MethodKey methodKey, NestDigest nestDigest) {
     super(Opcodes.ASM7, methodVisitor);
     this.enclosingMethodKey = methodKey;
-    this.bridgeOrigins = bridgeOrigins;
+    this.nestDigest = nestDigest;
 
     directFieldAccessReplacer = new FieldAccessToBridgeRedirector();
-    methodToBridgeRedirector = new MethodToBridgeRedirector(nestCompanions);
+    methodToBridgeRedirector = new MethodToBridgeRedirector(nestDigest);
   }
 
   @Override
   public void visitFieldInsn(int opcode, String owner, String name, String descriptor) {
-    FieldKey fieldKey = FieldKey.create(owner, name, descriptor);
+    FieldKey fieldKey = FieldKey.create(ClassName.create(owner), name, descriptor);
     MemberUseKind useKind = MemberUseKind.fromValue(opcode);
     if (isCrossMateRefInNest(fieldKey, enclosingMethodKey)
-        && bridgeOrigins.findAllMemberUseKind(fieldKey).contains(useKind)) {
+        && nestDigest.hasAnyUse(fieldKey, useKind)) {
       fieldKey.accept(useKind, directFieldAccessReplacer, mv);
       return;
     }
@@ -64,10 +61,10 @@
   @Override
   public void visitMethodInsn(
       int opcode, String owner, String name, String descriptor, boolean isInterface) {
-    MethodKey methodKey = MethodKey.create(owner, name, descriptor);
+    MethodKey methodKey = MethodKey.create(ClassName.create(owner), name, descriptor);
     MemberUseKind useKind = MemberUseKind.fromValue(opcode);
     if ((isInterface || isCrossMateRefInNest(methodKey, enclosingMethodKey))
-        && bridgeOrigins.findAllMemberUseKind(methodKey).contains(useKind)) {
+        && nestDigest.hasAnyUse(methodKey, useKind)) {
       methodKey.accept(useKind, isInterface, methodToBridgeRedirector, mv);
       return;
     }
@@ -78,10 +75,10 @@
   static class MethodToBridgeRedirector
       implements MethodInstrVisitor<MethodKey, MethodKey, MethodVisitor> {
 
-    private final NestCompanions nestCompanions;
+    private final NestDigest nestDigest;
 
-    MethodToBridgeRedirector(NestCompanions nestCompanions) {
-      this.nestCompanions = nestCompanions;
+    MethodToBridgeRedirector(NestDigest nestDigest) {
+      this.nestDigest = nestDigest;
     }
 
     @Override
@@ -89,7 +86,7 @@
       MethodKey bridgeMethodKey = methodKey.bridgeOfClassInstanceMethod();
       mv.visitMethodInsn(
           Opcodes.INVOKESTATIC,
-          bridgeMethodKey.owner(),
+          bridgeMethodKey.ownerName(),
           bridgeMethodKey.name(),
           bridgeMethodKey.descriptor(),
           /* isInterface= */ false);
@@ -101,7 +98,7 @@
       MethodKey bridgeMethodKey = methodKey.bridgeOfClassInstanceMethod();
       mv.visitMethodInsn(
           Opcodes.INVOKESTATIC,
-          bridgeMethodKey.owner(),
+          bridgeMethodKey.ownerName(),
           bridgeMethodKey.name(),
           bridgeMethodKey.descriptor(),
           /* isInterface= */ false);
@@ -110,12 +107,12 @@
 
     @Override
     public MethodKey visitConstructorInvokeSpecial(MethodKey methodKey, MethodVisitor mv) {
-      String nestCompanion = nestCompanions.nestCompanion(methodKey.owner());
+      ClassName nestCompanion = nestDigest.nestCompanion(ClassName.create(methodKey.ownerName()));
       MethodKey constructorBridge = methodKey.bridgeOfConstructor(nestCompanion);
       mv.visitInsn(Opcodes.ACONST_NULL);
       mv.visitMethodInsn(
           Opcodes.INVOKESPECIAL,
-          constructorBridge.owner(),
+          constructorBridge.ownerName(),
           constructorBridge.name(),
           constructorBridge.descriptor(),
           /* isInterface= */ false);
@@ -127,7 +124,7 @@
       MethodKey methodBridge = methodKey.substituteOfInterfaceInstanceMethod();
       mv.visitMethodInsn(
           Opcodes.INVOKESTATIC,
-          methodBridge.owner(),
+          methodBridge.ownerName(),
           methodBridge.name(),
           methodBridge.descriptor(),
           /* isInterface= */ true);
@@ -140,7 +137,7 @@
       bridgeMethodKey = methodKey.bridgeOfClassStaticMethod();
       mv.visitMethodInsn(
           Opcodes.INVOKESTATIC,
-          bridgeMethodKey.owner(),
+          bridgeMethodKey.ownerName(),
           bridgeMethodKey.name(),
           bridgeMethodKey.descriptor(),
           /* isInterface= */ false);
@@ -153,7 +150,7 @@
       methodBridge = methodKey.substituteOfInterfaceStaticMethod();
       mv.visitMethodInsn(
           Opcodes.INVOKESTATIC,
-          methodBridge.owner(),
+          methodBridge.ownerName(),
           methodBridge.name(),
           methodBridge.descriptor(),
           /* isInterface= */ true);
@@ -166,7 +163,7 @@
       methodBridge = methodKey.substituteOfInterfaceInstanceMethod();
       mv.visitMethodInsn(
           Opcodes.INVOKESTATIC,
-          methodBridge.owner(),
+          methodBridge.ownerName(),
           methodBridge.name(),
           methodBridge.descriptor(),
           /* isInterface= */ true);
@@ -188,7 +185,7 @@
       MethodKey bridgeMethodKey = fieldKey.bridgeOfStaticRead();
       mv.visitMethodInsn(
           Opcodes.INVOKESTATIC,
-          bridgeMethodKey.owner(),
+          bridgeMethodKey.ownerName(),
           bridgeMethodKey.name(),
           bridgeMethodKey.descriptor(),
           false);
@@ -200,7 +197,7 @@
       MethodKey bridgeMethodKey = fieldKey.bridgeOfStaticWrite();
       mv.visitMethodInsn(
           Opcodes.INVOKESTATIC,
-          bridgeMethodKey.owner(),
+          bridgeMethodKey.ownerName(),
           bridgeMethodKey.name(),
           bridgeMethodKey.descriptor(),
           false);
@@ -217,7 +214,7 @@
       MethodKey bridgeMethodKey = fieldKey.bridgeOfInstanceRead();
       mv.visitMethodInsn(
           Opcodes.INVOKESTATIC,
-          bridgeMethodKey.owner(),
+          bridgeMethodKey.ownerName(),
           bridgeMethodKey.name(),
           bridgeMethodKey.descriptor(),
           false);
@@ -229,7 +226,7 @@
       MethodKey bridgeMethodKey = fieldKey.bridgeOfInstanceWrite();
       mv.visitMethodInsn(
           Opcodes.INVOKESTATIC,
-          bridgeMethodKey.owner(),
+          bridgeMethodKey.ownerName(),
           bridgeMethodKey.name(),
           bridgeMethodKey.descriptor(),
           /* isInterface= */ false);
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestCompanions.java b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestCompanions.java
deleted file mode 100644
index a8d511c..0000000
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestCompanions.java
+++ /dev/null
@@ -1,174 +0,0 @@
-// Copyright 2019 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.android.desugar.nest;
-
-import static com.google.common.base.Preconditions.checkNotNull;
-import static com.google.common.collect.ImmutableList.toImmutableList;
-import static com.google.devtools.build.android.desugar.langmodel.LangModelConstants.NEST_COMPANION_CLASS_SIMPLE_NAME;
-
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Streams;
-import com.google.devtools.build.android.desugar.io.FileContentProvider;
-import com.google.devtools.build.android.desugar.langmodel.ClassAttributeRecord;
-import com.google.devtools.build.android.desugar.langmodel.ClassMemberRecord;
-import java.io.ByteArrayInputStream;
-import java.util.HashMap;
-import java.util.Map;
-import java.util.Optional;
-import java.util.Set;
-import javax.annotation.Nullable;
-import org.objectweb.asm.ClassWriter;
-
-/** Manages the creation and IO stream for nest-companion classes. */
-public class NestCompanions {
-
-  private final ClassMemberRecord classMemberRecord;
-  private final ClassAttributeRecord classAttributeRecord;
-  private final Map<String, String> nestCompanionToHostMap;
-
-  /**
-   * A map from the class binary names of nest hosts to the associated class writer of the nest's
-   * companion.
-   */
-  private ImmutableMap<String, ClassWriter> companionWriters;
-
-  public static NestCompanions create(
-      ClassMemberRecord classMemberRecord, ClassAttributeRecord classAttributeRecord) {
-    return new NestCompanions(classMemberRecord, classAttributeRecord, new HashMap<>());
-  }
-
-  private NestCompanions(
-      ClassMemberRecord classMemberRecord,
-      ClassAttributeRecord classAttributeRecord,
-      HashMap<String, String> nestCompanionToHostMap) {
-    this.classMemberRecord = classMemberRecord;
-    this.classAttributeRecord = classAttributeRecord;
-    this.nestCompanionToHostMap = nestCompanionToHostMap;
-  }
-
-  /**
-   * Generates the nest companion class writers. The nest companion classes will be generated as the
-   * last placeholder class type for the synthetic constructor, whose originating constructor has
-   * any invocation in other classes in nest.
-   */
-  void prepareCompanionClasses() {
-    ImmutableList<String> nestHostsWithCompanion =
-        classMemberRecord.findAllConstructorMemberKeys().stream()
-            .map(
-                constructor ->
-                    nestHost(constructor.owner(), classAttributeRecord, nestCompanionToHostMap))
-            .flatMap(Streams::stream)
-            .distinct()
-            .collect(toImmutableList());
-    ImmutableMap.Builder<String, ClassWriter> companionWriterBuilders = ImmutableMap.builder();
-    for (String nestHost : nestHostsWithCompanion) {
-      String nestCompanion = nestHost + '$' + NEST_COMPANION_CLASS_SIMPLE_NAME;
-      nestCompanionToHostMap.put(nestCompanion, nestHost);
-      companionWriterBuilders.put(nestHost, new ClassWriter(ClassWriter.COMPUTE_MAXS));
-    }
-    companionWriters = companionWriterBuilders.build();
-  }
-
-  /**
-   * The public API that finds the nest host for a given class. It is expected {@link
-   * #prepareCompanionClasses()} executed before this API is ready. The method returns {@link
-   * Optional#empty()} if the class is not part of a nest. A generated nest companion class and its
-   * nest host are considered to be a nest host/member relationship.
-   */
-  public Optional<String> nestHost(String classBinaryName) {
-    // Ensures prepareCompanionClasses has been executed.
-    checkNotNull(companionWriters);
-    return nestHost(classBinaryName, classAttributeRecord, nestCompanionToHostMap);
-  }
-
-  /**
-   * The internal method finds the nest host for a given class from a class attribute record. The
-   * method returns {@link * Optional#empty()} if the class is not part of a nest. A generated nest
-   * companion class and its * nest host are considered to be a nest host/member relationship.
-   *
-   * <p>In addition to exam the NestHost_attribute from the class file, this method returns the
-   * class under investigation itself for a class with NestMembers_attribute but without
-   * NestHost_attribute.
-   */
-  private static Optional<String> nestHost(
-      String classBinaryName,
-      ClassAttributeRecord classAttributeRecord,
-      Map<String, String> companionToHostMap) {
-    if (companionToHostMap.containsKey(classBinaryName)) {
-      return Optional.of(companionToHostMap.get(classBinaryName));
-    }
-    Optional<String> nestHost = classAttributeRecord.getNestHost(classBinaryName);
-    if (nestHost.isPresent()) {
-      return nestHost;
-    }
-    Set<String> nestMembers = classAttributeRecord.getNestMembers(classBinaryName);
-    if (!nestMembers.isEmpty()) {
-      return Optional.of(classBinaryName);
-    }
-    return Optional.empty();
-  }
-
-  /**
-   * Returns the internal name of the nest companion class for a given class.
-   *
-   * <p>e.g. The nest host of a/b/C$D is a/b/C$NestCC
-   */
-  public String nestCompanion(String classBinaryName) {
-    return nestHost(classBinaryName)
-        .map(nestHost -> nestHost + '$' + NEST_COMPANION_CLASS_SIMPLE_NAME)
-        .orElseThrow(
-            () ->
-                new IllegalStateException(
-                    String.format(
-                        "Expected the presence of NestHost attribute of %s to get nest companion.",
-                        classBinaryName)));
-  }
-
-  /**
-   * Gets the class visitor of the affiliated nest host of the given class. E.g For the given class
-   * com/google/a/b/Delta$Echo, it returns the class visitor of com/google/a/b/Delta$NestCC
-   */
-  @Nullable
-  public ClassWriter getCompanionClassWriter(String classInternalName) {
-    return nestHost(classInternalName).map(nestHost -> companionWriters.get(nestHost)).orElse(null);
-  }
-
-  /** Gets all nest companion classes required to be generated. */
-  public ImmutableList<String> getAllCompanionClasses() {
-    return companionWriters.keySet().stream().map(this::nestCompanion).collect(toImmutableList());
-  }
-
-  /** Gets all nest companion files required to be generated. */
-  public ImmutableList<FileContentProvider<ByteArrayInputStream>> getCompanionFileProviders() {
-    ImmutableList.Builder<FileContentProvider<ByteArrayInputStream>> fileContents =
-        ImmutableList.builder();
-    for (String companion : getAllCompanionClasses()) {
-      fileContents.add(
-          new FileContentProvider<>(
-              companion + ".class", () -> getByteArrayInputStreamOfCompanionClass(companion)));
-    }
-    return fileContents.build();
-  }
-
-  private ByteArrayInputStream getByteArrayInputStreamOfCompanionClass(String companion) {
-    ClassWriter companionClassWriter = getCompanionClassWriter(companion);
-    checkNotNull(
-        companionClassWriter,
-        "Expected companion class (%s) to be present in (%s)",
-        companionWriters);
-    return new ByteArrayInputStream(companionClassWriter.toByteArray());
-  }
-}
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestDesugaring.java b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestDesugaring.java
index b03500e..7d0c7de 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestDesugaring.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestDesugaring.java
@@ -19,7 +19,7 @@
 import static org.objectweb.asm.Opcodes.ACC_INTERFACE;
 import static org.objectweb.asm.Opcodes.ACC_SYNTHETIC;
 
-import com.google.devtools.build.android.desugar.langmodel.ClassMemberRecord;
+import com.google.devtools.build.android.desugar.langmodel.ClassName;
 import com.google.devtools.build.android.desugar.langmodel.FieldKey;
 import com.google.devtools.build.android.desugar.langmodel.MethodDeclInfo;
 import com.google.devtools.build.android.desugar.langmodel.MethodKey;
@@ -42,31 +42,21 @@
   private static final int NEST_COMPANION_CLASS_ACCESS_CODE =
       Opcodes.ACC_SYNTHETIC | Opcodes.ACC_ABSTRACT | Opcodes.ACC_STATIC;
 
-  private final NestCompanions nestCompanions;
-
-  /**
-   * All originating members of bridges, i.e. all fields, constructors, methods with an associated
-   * bridge method or companion method.
-   */
-  private final ClassMemberRecord classMemberRecord;
+  private final NestDigest nestDigest;
 
   private FieldAccessBridgeEmitter fieldAccessBridgeEmitter;
   private MethodAccessorEmitter methodAccessorEmitter;
 
-  private String className;
+  private ClassName className;
   private int classAccess;
   @Nullable private ClassVisitor nestCompanionVisitor;
 
   /** Whether the class being visited is a nest host with with a nest companion class. */
   private boolean isNestHostWithNestCompanion;
 
-  public NestDesugaring(
-      ClassVisitor classVisitor,
-      NestCompanions nestCompanions,
-      ClassMemberRecord classMemberRecord) {
+  public NestDesugaring(ClassVisitor classVisitor, NestDigest nestDigest) {
     super(Opcodes.ASM7, classVisitor);
-    this.nestCompanions = nestCompanions;
-    this.classMemberRecord = classMemberRecord;
+    this.nestDigest = nestDigest;
   }
 
   @Override
@@ -77,14 +67,13 @@
       String signature,
       String superName,
       String[] interfaces) {
-    className = name;
+    className = ClassName.create(name);
     classAccess = access;
-    nestCompanionVisitor = nestCompanions.getCompanionClassWriter(name);
+    nestCompanionVisitor = nestDigest.getCompanionClassWriter(className);
     isNestHostWithNestCompanion =
-        (nestCompanionVisitor != null)
-            && className.equals(nestCompanions.nestHost(className).get());
+        (nestCompanionVisitor != null) && className.equals(nestDigest.nestHost(className).get());
     fieldAccessBridgeEmitter = new FieldAccessBridgeEmitter();
-    methodAccessorEmitter = new MethodAccessorEmitter(nestCompanions);
+    methodAccessorEmitter = new MethodAccessorEmitter(nestDigest);
     super.visit(
         Math.min(version, NestDesugarConstants.MIN_VERSION),
         access,
@@ -96,7 +85,7 @@
       nestCompanionVisitor.visit(
           Math.min(version, NestDesugarConstants.MIN_VERSION),
           ACC_SYNTHETIC | ACC_ABSTRACT,
-          nestCompanions.nestCompanion(className),
+          nestDigest.nestCompanion(className).binaryName(),
           /* signature= */ null,
           /* superName= */ "java/lang/Object",
           /* interfaces= */ new String[0]);
@@ -109,8 +98,8 @@
     FieldKey fieldKey = FieldKey.create(className, name, descriptor);
     // Generates necessary bridge methods for this field, including field getter methods and field
     // setter methods. See FieldAccessBridgeEmitter.
-    classMemberRecord
-        .findAllMemberUseKind(fieldKey)
+    nestDigest
+        .findAllMemberUseKinds(fieldKey)
         .forEach(useKind -> fieldKey.accept(useKind, fieldAccessBridgeEmitter, cv));
     return super.visitField(access, name, descriptor, signature, value);
   }
@@ -119,7 +108,7 @@
   public MethodVisitor visitMethod(
       int access, String name, String descriptor, String signature, String[] exceptions) {
     MethodKey methodKey = MethodKey.create(className, name, descriptor);
-    if (classMemberRecord.hasTrackingReason(methodKey)) {
+    if (nestDigest.hasAnyTrackingReason(methodKey)) {
       MethodDeclInfo methodDeclInfo =
           new MethodDeclInfo(methodKey, classAccess, access, signature, exceptions);
       // For interfaces, the following .accept converts the original method into a
@@ -137,14 +126,11 @@
           (classAccess & ACC_INTERFACE) != 0
               ? targetMethodVisitor
               : super.visitMethod(access, name, descriptor, signature, exceptions);
-      return new NestBridgeRefConverter(
-          primaryMethodVisitor, methodKey, classMemberRecord, nestCompanions);
+      return new NestBridgeRefConverter(primaryMethodVisitor, methodKey, nestDigest);
     }
     // In absence of method invocation record, fallback to the delegate method visitor.
     MethodVisitor mv = super.visitMethod(access, name, descriptor, signature, exceptions);
-    return mv == null
-        ? null
-        : new NestBridgeRefConverter(mv, methodKey, classMemberRecord, nestCompanions);
+    return mv == null ? null : new NestBridgeRefConverter(mv, methodKey, nestDigest);
   }
 
   @Override
@@ -168,17 +154,17 @@
   @Override
   public void visitEnd() {
     if (isNestHostWithNestCompanion) {
-      String nestCompanionClassName = nestCompanions.nestCompanion(className);
+      ClassName nestCompanion = nestDigest.nestCompanion(className);
       // In the nest companion class, marks its outer class as the nest host.
       nestCompanionVisitor.visitInnerClass(
-          nestCompanionClassName,
-          className,
+          nestCompanion.binaryName(),
+          className.binaryName(),
           NEST_COMPANION_CLASS_SIMPLE_NAME,
           NEST_COMPANION_CLASS_ACCESS_CODE);
       // In the nest host class, marks the nest companion as one of its inner classes.
       cv.visitInnerClass(
-          nestCompanionClassName,
-          className,
+          nestCompanion.binaryName(),
+          className.binaryName(),
           NEST_COMPANION_CLASS_SIMPLE_NAME,
           NEST_COMPANION_CLASS_ACCESS_CODE);
     }
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestDigest.java b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestDigest.java
new file mode 100644
index 0000000..71e7141
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/nest/NestDigest.java
@@ -0,0 +1,220 @@
+// Copyright 2019 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.android.desugar.nest;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.collect.ImmutableList.toImmutableList;
+import static com.google.common.collect.ImmutableMap.toImmutableMap;
+import static com.google.devtools.build.android.desugar.langmodel.LangModelConstants.NEST_COMPANION_CLASS_SIMPLE_NAME;
+import static java.util.stream.Collectors.toMap;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Streams;
+import com.google.devtools.build.android.desugar.io.FileContentProvider;
+import com.google.devtools.build.android.desugar.langmodel.ClassAttributeRecord;
+import com.google.devtools.build.android.desugar.langmodel.ClassMemberKey;
+import com.google.devtools.build.android.desugar.langmodel.ClassMemberRecord;
+import com.google.devtools.build.android.desugar.langmodel.ClassName;
+import com.google.devtools.build.android.desugar.langmodel.MemberUseKind;
+import com.google.devtools.build.android.desugar.langmodel.TypeMappable;
+import com.google.devtools.build.android.desugar.langmodel.TypeMapper;
+import java.io.ByteArrayInputStream;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Set;
+import javax.annotation.Nullable;
+import org.objectweb.asm.ClassWriter;
+
+/** Manages the creation and IO stream for nest-companion classes. */
+public class NestDigest implements TypeMappable<NestDigest> {
+
+  private final ClassMemberRecord classMemberRecord;
+  private final ClassAttributeRecord classAttributeRecord;
+  private final Map<ClassName, ClassName> nestCompanionToHostMap;
+
+  /**
+   * A map from the class binary names of nest hosts to the associated class writer of the nest's
+   * companion.
+   */
+  private ImmutableMap<ClassName, ClassWriter> companionWriters;
+
+  public static NestDigest create(
+      ClassMemberRecord classMemberRecord, ClassAttributeRecord classAttributeRecord) {
+    return new NestDigest(
+        classMemberRecord, classAttributeRecord, new HashMap<>(), /* companionWriters= */ null);
+  }
+
+  private NestDigest(
+      ClassMemberRecord classMemberRecord,
+      ClassAttributeRecord classAttributeRecord,
+      Map<ClassName, ClassName> nestCompanionToHostMap,
+      ImmutableMap<ClassName, ClassWriter> companionWriters) {
+    this.classMemberRecord = classMemberRecord;
+    this.classAttributeRecord = classAttributeRecord;
+    this.nestCompanionToHostMap = nestCompanionToHostMap;
+    this.companionWriters = companionWriters;
+  }
+
+  /**
+   * Generates the nest companion class writers. The nest companion classes will be generated as the
+   * last placeholder class type for the synthetic constructor, whose originating constructor has
+   * any invocation in other classes in nest.
+   */
+  void prepareCompanionClasses() {
+    ImmutableList<ClassName> nestHostsWithCompanion =
+        classMemberRecord.findAllConstructorMemberKeys().stream()
+            .map(
+                constructor ->
+                    nestHost(constructor.owner(), classAttributeRecord, nestCompanionToHostMap))
+            .flatMap(Streams::stream)
+            .distinct()
+            .collect(toImmutableList());
+    ImmutableMap.Builder<ClassName, ClassWriter> companionWriterBuilders = ImmutableMap.builder();
+    for (ClassName nestHost : nestHostsWithCompanion) {
+      ClassName nestCompanion = nestHost.innerClass(NEST_COMPANION_CLASS_SIMPLE_NAME);
+      nestCompanionToHostMap.put(nestCompanion, nestHost);
+      companionWriterBuilders.put(nestHost, new ClassWriter(ClassWriter.COMPUTE_MAXS));
+    }
+    companionWriters = companionWriterBuilders.build();
+  }
+
+  public boolean hasAnyTrackingReason(ClassMemberKey<?> classMemberKey) {
+    return classMemberRecord.hasTrackingReason(classMemberKey);
+  }
+
+  public boolean hasAnyUse(ClassMemberKey<?> classMemberKey, MemberUseKind useKind) {
+    return findAllMemberUseKinds(classMemberKey).contains(useKind);
+  }
+
+  public ImmutableList<MemberUseKind> findAllMemberUseKinds(ClassMemberKey<?> classMemberKey) {
+    return classMemberRecord.findAllMemberUseKind(classMemberKey);
+  }
+
+  /**
+   * The public API that finds the nest host for a given class. It is expected {@link
+   * #prepareCompanionClasses()} executed before this API is ready. The method returns {@link
+   * Optional#empty()} if the class is not part of a nest. A generated nest companion class and its
+   * nest host are considered to be a nest host/member relationship.
+   */
+  public Optional<ClassName> nestHost(ClassName className) {
+    // Ensures prepareCompanionClasses has been executed.
+    checkNotNull(companionWriters);
+    return nestHost(className, classAttributeRecord, nestCompanionToHostMap);
+  }
+
+  /**
+   * The internal method finds the nest host for a given class from a class attribute record. The
+   * method returns {@link * Optional#empty()} if the class is not part of a nest. A generated nest
+   * companion class and its * nest host are considered to be a nest host/member relationship.
+   *
+   * <p>In addition to exam the NestHost_attribute from the class file, this method returns the
+   * class under investigation itself for a class with NestMembers_attribute but without
+   * NestHost_attribute.
+   */
+  private static Optional<ClassName> nestHost(
+      ClassName className,
+      ClassAttributeRecord classAttributeRecord,
+      Map<ClassName, ClassName> companionToHostMap) {
+    if (companionToHostMap.containsKey(className)) {
+      return Optional.of(companionToHostMap.get(className));
+    }
+    Optional<ClassName> nestHost = classAttributeRecord.getNestHost(className);
+    if (nestHost.isPresent()) {
+      return nestHost;
+    }
+    Set<ClassName> nestMembers = classAttributeRecord.getNestMembers(className);
+    if (!nestMembers.isEmpty()) {
+      return Optional.of(className);
+    }
+    return Optional.empty();
+  }
+
+  /**
+   * Returns the internal name of the nest companion class for a given class.
+   *
+   * <p>e.g. The nest host of a/b/C$D is a/b/C$NestCC
+   */
+  public ClassName nestCompanion(ClassName className) {
+    return nestHost(className)
+        .map(nestHost -> nestHost.innerClass(NEST_COMPANION_CLASS_SIMPLE_NAME))
+        .orElseThrow(
+            () ->
+                new IllegalStateException(
+                    String.format(
+                        "Expected the presence of NestHost attribute of %s to get nest companion.",
+                        className)));
+  }
+
+  /**
+   * Gets the class visitor of the affiliated nest host of the given class. E.g For the given class
+   * com/google/a/b/Delta$Echo, it returns the class visitor of com/google/a/b/Delta$NestCC
+   */
+  @Nullable
+  public ClassWriter getCompanionClassWriter(ClassName className) {
+    return nestHost(className).map(nestHost -> companionWriters.get(nestHost)).orElse(null);
+  }
+
+  /** Gets all nest companion classes required to be generated. */
+  public ImmutableList<String> getAllCompanionClassNames() {
+    return getAllCompanionClasses().stream().map(ClassName::binaryName).collect(toImmutableList());
+  }
+
+  public ImmutableList<ClassName> getAllCompanionClasses() {
+    return companionWriters.keySet().stream().map(this::nestCompanion).collect(toImmutableList());
+  }
+
+  /** Gets all nest companion files required to be generated. */
+  public ImmutableList<FileContentProvider<ByteArrayInputStream>> getCompanionFileProviders() {
+    ImmutableList.Builder<FileContentProvider<ByteArrayInputStream>> fileContents =
+        ImmutableList.builder();
+    for (ClassName companion : getAllCompanionClasses()) {
+      fileContents.add(
+          new FileContentProvider<>(
+              companion.classFilePathName(),
+              () -> getByteArrayInputStreamOfCompanionClass(companion)));
+    }
+    return fileContents.build();
+  }
+
+  private ByteArrayInputStream getByteArrayInputStreamOfCompanionClass(ClassName companion) {
+    ClassWriter companionClassWriter = getCompanionClassWriter(companion);
+    companionClassWriter.visitEnd();
+    checkNotNull(
+        companionClassWriter,
+        "Expected companion class (%s) to be present in (%s)",
+        companionWriters);
+    return new ByteArrayInputStream(companionClassWriter.toByteArray());
+  }
+
+  @Override
+  public NestDigest acceptTypeMapper(TypeMapper typeMapper) {
+    return new NestDigest(
+        classMemberRecord.acceptTypeMapper(typeMapper),
+        classAttributeRecord.acceptTypeMapper(typeMapper),
+        nestCompanionToHostMap.keySet().stream()
+            .collect(
+                toMap(
+                    companion -> companion.acceptTypeMapper(typeMapper),
+                    companion ->
+                        nestCompanionToHostMap.get(companion).acceptTypeMapper(typeMapper))),
+        companionWriters.keySet().stream()
+            .collect(
+                toImmutableMap(
+                    nestHost -> nestHost.acceptTypeMapper(typeMapper),
+                    nestHost -> new ClassWriter(ClassWriter.COMPUTE_MAXS))));
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/strconcat/IndyStringConcatDesugaring.java b/src/tools/android/java/com/google/devtools/build/android/desugar/strconcat/IndyStringConcatDesugaring.java
index 4dece59..f86e7a9 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/strconcat/IndyStringConcatDesugaring.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/strconcat/IndyStringConcatDesugaring.java
@@ -23,6 +23,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.android.desugar.langmodel.ClassMemberUse;
 import com.google.devtools.build.android.desugar.langmodel.ClassMemberUseCounter;
+import com.google.devtools.build.android.desugar.langmodel.ClassName;
 import com.google.devtools.build.android.desugar.langmodel.LangModelHelper;
 import com.google.devtools.build.android.desugar.langmodel.MemberUseKind;
 import com.google.devtools.build.android.desugar.langmodel.MethodKey;
@@ -38,7 +39,7 @@
   public static final ClassMemberUse INVOKE_JDK11_STRING_CONCAT =
       ClassMemberUse.create(
           MethodKey.create(
-              "java/lang/invoke/StringConcatFactory",
+              ClassName.create("java/lang/invoke/StringConcatFactory"),
               "makeConcatWithConstants",
               "(Ljava/lang/invoke/MethodHandles$Lookup;"
                   + "Ljava/lang/String;"
@@ -51,7 +52,7 @@
   private static final ClassMemberUse INVOKE_STRING_CONCAT_REPLACEMENT_METHOD =
       ClassMemberUse.create(
           MethodKey.create(
-              "com/google/devtools/build/android/desugar/runtime/StringConcats",
+              ClassName.create("com/google/devtools/build/android/desugar/runtime/StringConcats"),
               "concat",
               "([Ljava/lang/Object;"
                   + "Ljava/lang/String;"
@@ -95,7 +96,7 @@
       ClassMemberUse bootstrapMethodInvocation =
           ClassMemberUse.create(
               MethodKey.create(
-                  bootstrapMethodHandle.getOwner(),
+                  ClassName.create(bootstrapMethodHandle.getOwner()),
                   bootstrapMethodHandle.getName(),
                   bootstrapMethodHandle.getDesc()),
               MemberUseKind.INVOKEDYNAMIC);
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/testing/junit/RuntimeEntityResolver.java b/src/tools/android/java/com/google/devtools/build/android/desugar/testing/junit/RuntimeEntityResolver.java
index b61244b..6dce8d6 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/testing/junit/RuntimeEntityResolver.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/testing/junit/RuntimeEntityResolver.java
@@ -33,6 +33,7 @@
 import com.google.common.collect.Table;
 import com.google.devtools.build.android.desugar.Desugar;
 import com.google.devtools.build.android.desugar.langmodel.ClassMemberKey;
+import com.google.devtools.build.android.desugar.langmodel.ClassName;
 import com.google.devtools.build.android.desugar.langmodel.FieldKey;
 import com.google.devtools.build.android.desugar.langmodel.MethodKey;
 import com.google.devtools.build.android.desugar.testing.junit.RuntimeMethodHandle.MemberUseContext;
@@ -97,8 +98,8 @@
   /** A table for the lookup of missing user-supplied class member descriptors. */
   private final Table<
           Integer, // Desugar round
-          ClassMemberKey, // A class member without descriptor (empty descriptor string).
-          Set<ClassMemberKey>> // The set of same-name class members with their descriptors.
+          ClassMemberKey<?>, // A class member without descriptor (empty descriptor string).
+          Set<ClassMemberKey<?>>> // The set of same-name class members with their descriptors.
       descriptorLookupRepo = HashBasedTable.create();
 
   /**
@@ -107,7 +108,7 @@
    */
   private final Table<
           Integer, // Desugar round
-          ClassMemberKey, // A class member with descriptor.
+          ClassMemberKey<?>, // A class member with descriptor.
           java.lang.reflect.Member> // A reflection-based Member instance.
       reflectionBasedMembers = HashBasedTable.create();
 
@@ -194,12 +195,12 @@
   private static void fillMissingClassMemberDescriptorRepo(
       int round,
       Class<?> classLiteral,
-      Table<Integer, ClassMemberKey, Set<ClassMemberKey>> missingDescriptorLookupRepo) {
-    String ownerName = Type.getInternalName(classLiteral);
+      Table<Integer, ClassMemberKey<?>, Set<ClassMemberKey<?>>> missingDescriptorLookupRepo) {
+    ClassName owner = ClassName.create(classLiteral);
     for (Constructor<?> constructor : classLiteral.getDeclaredConstructors()) {
-      ClassMemberKey memberKeyWithoutDescriptor = MethodKey.create(ownerName, "<init>", "");
-      ClassMemberKey memberKeyWithDescriptor =
-          MethodKey.create(ownerName, "<init>", Type.getConstructorDescriptor(constructor));
+      ClassMemberKey<?> memberKeyWithoutDescriptor = MethodKey.create(owner, "<init>", "");
+      ClassMemberKey<?> memberKeyWithDescriptor =
+          MethodKey.create(owner, "<init>", Type.getConstructorDescriptor(constructor));
       if (missingDescriptorLookupRepo.contains(round, memberKeyWithoutDescriptor)) {
         missingDescriptorLookupRepo
             .get(round, memberKeyWithoutDescriptor)
@@ -210,9 +211,9 @@
       }
     }
     for (Method method : classLiteral.getDeclaredMethods()) {
-      ClassMemberKey memberKeyWithoutDescriptor = MethodKey.create(ownerName, method.getName(), "");
-      ClassMemberKey memberKeyWithDescriptor =
-          MethodKey.create(ownerName, method.getName(), Type.getMethodDescriptor(method));
+      ClassMemberKey<?> memberKeyWithoutDescriptor = MethodKey.create(owner, method.getName(), "");
+      ClassMemberKey<?> memberKeyWithDescriptor =
+          MethodKey.create(owner, method.getName(), Type.getMethodDescriptor(method));
       if (missingDescriptorLookupRepo.contains(round, memberKeyWithoutDescriptor)) {
         missingDescriptorLookupRepo
             .get(round, memberKeyWithoutDescriptor)
@@ -223,9 +224,9 @@
       }
     }
     for (Field field : classLiteral.getDeclaredFields()) {
-      ClassMemberKey memberKeyWithoutDescriptor = FieldKey.create(ownerName, field.getName(), "");
-      ClassMemberKey memberKeyWithDescriptor =
-          FieldKey.create(ownerName, field.getName(), Type.getDescriptor(field.getType()));
+      ClassMemberKey<?> memberKeyWithoutDescriptor = FieldKey.create(owner, field.getName(), "");
+      ClassMemberKey<?> memberKeyWithDescriptor =
+          FieldKey.create(owner, field.getName(), Type.getDescriptor(field.getType()));
       if (missingDescriptorLookupRepo.contains(round, memberKeyWithoutDescriptor)) {
         missingDescriptorLookupRepo
             .get(round, memberKeyWithoutDescriptor)
@@ -237,27 +238,27 @@
     }
   }
 
-  private static ImmutableTable<Integer, ClassMemberKey, Member> getReflectionBasedClassMembers(
+  private static ImmutableTable<Integer, ClassMemberKey<?>, Member> getReflectionBasedClassMembers(
       int round, Class<?> classLiteral) {
-    ImmutableTable.Builder<Integer, ClassMemberKey, Member> reflectionBasedMembers =
+    ImmutableTable.Builder<Integer, ClassMemberKey<?>, Member> reflectionBasedMembers =
         ImmutableTable.builder();
-    String ownerName = Type.getInternalName(classLiteral);
+    ClassName owner = ClassName.create(classLiteral);
     for (Field field : classLiteral.getDeclaredFields()) {
       reflectionBasedMembers.put(
           round,
-          FieldKey.create(ownerName, field.getName(), Type.getDescriptor(field.getType())),
+          FieldKey.create(owner, field.getName(), Type.getDescriptor(field.getType())),
           field);
     }
     for (Constructor<?> constructor : classLiteral.getDeclaredConstructors()) {
       reflectionBasedMembers.put(
           round,
-          MethodKey.create(ownerName, "<init>", Type.getConstructorDescriptor(constructor)),
+          MethodKey.create(owner, "<init>", Type.getConstructorDescriptor(constructor)),
           constructor);
     }
     for (Method method : classLiteral.getDeclaredMethods()) {
       reflectionBasedMembers.put(
           round,
-          MethodKey.create(ownerName, method.getName(), Type.getMethodDescriptor(method)),
+          MethodKey.create(owner, method.getName(), Type.getMethodDescriptor(method)),
           method);
     }
     return reflectionBasedMembers.build();
@@ -267,8 +268,8 @@
       DynamicClassLiteral dynamicClassLiteralRequest,
       List<JarTransformationRecord> jarTransformationRecords,
       ClassLoader initialInputClassLoader,
-      Table<Integer, ClassMemberKey, Member> reflectionBasedMembers,
-      Table<Integer, ClassMemberKey, Set<ClassMemberKey>> missingDescriptorLookupRepo,
+      Table<Integer, ClassMemberKey<?>, Member> reflectionBasedMembers,
+      Table<Integer, ClassMemberKey<?>, Set<ClassMemberKey<?>>> missingDescriptorLookupRepo,
       String workingJavaPackage)
       throws Throwable {
     int round = dynamicClassLiteralRequest.round();
@@ -326,8 +327,8 @@
       Lookup lookup,
       List<JarTransformationRecord> jarTransformationRecords,
       ClassLoader initialInputClassLoader,
-      Table<Integer, ClassMemberKey, java.lang.reflect.Member> reflectionBasedMembers,
-      Table<Integer, ClassMemberKey, Set<ClassMemberKey>> missingDescriptorLookupRepo,
+      Table<Integer, ClassMemberKey<?>, java.lang.reflect.Member> reflectionBasedMembers,
+      Table<Integer, ClassMemberKey<?>, Set<ClassMemberKey<?>>> missingDescriptorLookupRepo,
       String workingJavaPackage)
       throws Throwable {
     int round = methodHandleRequest.round();
@@ -340,14 +341,14 @@
             missingDescriptorLookupRepo,
             workingJavaPackage);
 
-    String ownerInternalName = Type.getInternalName(classLiteral);
+    ClassName owner = ClassName.create(classLiteral);
     String memberName = methodHandleRequest.memberName();
     String memberDescriptor = methodHandleRequest.memberDescriptor();
 
-    ClassMemberKey classMemberKey =
+    ClassMemberKey<?> classMemberKey =
         methodHandleRequest.usage() == MemberUseContext.METHOD_INVOCATION
-            ? MethodKey.create(ownerInternalName, memberName, memberDescriptor)
-            : FieldKey.create(ownerInternalName, memberName, memberDescriptor);
+            ? MethodKey.create(owner, memberName, memberDescriptor)
+            : FieldKey.create(owner, memberName, memberDescriptor);
 
     if (classMemberKey.descriptor().isEmpty()) {
       classMemberKey = restoreMissingDescriptor(classMemberKey, round, missingDescriptorLookupRepo);
@@ -371,25 +372,25 @@
             methodHandleRequest.usage(), MemberUseContext.class));
   }
 
-  private static ClassMemberKey restoreMissingDescriptor(
-      ClassMemberKey classMemberKey,
+  private static ClassMemberKey<?> restoreMissingDescriptor(
+      ClassMemberKey<?> classMemberKey,
       int round,
-      Table<Integer, ClassMemberKey, Set<ClassMemberKey>> missingDescriptorLookupRepo) {
-    Set<ClassMemberKey> restoredClassMemberKeys =
+      Table<Integer, ClassMemberKey<?>, Set<ClassMemberKey<?>>> missingDescriptorLookupRepo) {
+    Set<ClassMemberKey<?>> restoredClassMemberKey =
         missingDescriptorLookupRepo.get(round, classMemberKey);
-    if (restoredClassMemberKeys == null || restoredClassMemberKeys.isEmpty()) {
+    if (restoredClassMemberKey == null || restoredClassMemberKey.isEmpty()) {
       throw new IllegalStateException(
           String.format(
               "Unable to find class member (%s). Please check its presence.",
-              restoredClassMemberKeys));
-    } else if (restoredClassMemberKeys.size() > 1) {
+              restoredClassMemberKey));
+    } else if (restoredClassMemberKey.size() > 1) {
       throw new IllegalStateException(
           String.format(
               "Class Member (%s) has same-name overloaded members: (%s) \n"
                   + "Please specify a descriptor to disambiguate overloaded method request.",
-              classMemberKey, restoredClassMemberKeys));
+              classMemberKey, restoredClassMemberKey));
     }
-    return Iterables.getOnlyElement(restoredClassMemberKeys);
+    return Iterables.getOnlyElement(restoredClassMemberKey);
   }
 
   private static FieldNode getFieldNode(