diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignature.java b/src/main/java/com/android/tools/r8/graph/GenericSignature.java
index 2fa08c8..bf7c42b 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignature.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignature.java
@@ -167,14 +167,15 @@
       return interfaceBounds;
     }
 
-    public void visit(GenericSignatureVisitor visitor) {
-      visitor.visitClassBound(classBound);
-      if (interfaceBounds == null) {
-        return;
+    public FormalTypeParameter visit(GenericSignatureVisitor visitor) {
+      FieldTypeSignature rewrittenClassBound =
+          classBound == null ? null : visitor.visitClassBound(classBound);
+      List<FieldTypeSignature> rewrittenInterfaceBounds =
+          visitor.visitInterfaceBounds(interfaceBounds);
+      if (classBound == rewrittenClassBound && interfaceBounds == rewrittenInterfaceBounds) {
+        return this;
       }
-      for (FieldTypeSignature interfaceBound : interfaceBounds) {
-        visitor.visitInterfaceBound(interfaceBound);
-      }
+      return new FormalTypeParameter(name, rewrittenClassBound, rewrittenInterfaceBounds);
     }
   }
 
@@ -232,12 +233,18 @@
       return formalTypeParameters;
     }
 
-    public void visit(GenericSignatureVisitor visitor) {
-      visitor.visitFormalTypeParameters(formalTypeParameters);
-      visitor.visitSuperClass(superClassSignature);
-      for (ClassTypeSignature superInterface : superInterfaceSignatures) {
-        visitor.visitSuperInterface(superInterface);
+    public ClassSignature visit(GenericSignatureVisitor visitor) {
+      List<FormalTypeParameter> rewrittenParameters =
+          visitor.visitFormalTypeParameters(formalTypeParameters);
+      ClassTypeSignature rewrittenSuperClass = visitor.visitSuperClass(superClassSignature);
+      List<ClassTypeSignature> rewrittenInterfaces =
+          visitor.visitSuperInterfaces(superInterfaceSignatures);
+      if (formalTypeParameters == rewrittenParameters
+          && superClassSignature == rewrittenSuperClass
+          && superInterfaceSignatures == rewrittenInterfaces) {
+        return this;
       }
+      return new ClassSignature(rewrittenParameters, rewrittenSuperClass, rewrittenInterfaces);
     }
 
     public String toRenamedString(NamingLens namingLens, Predicate<DexType> isTypeMissing) {
@@ -286,8 +293,9 @@
     }
 
     @Override
-    public void visit(GenericSignatureVisitor visitor) {
+    public ClassSignature visit(GenericSignatureVisitor visitor) {
       assert false : "Should not visit an invalid signature";
+      return this;
     }
 
     @Override
@@ -447,7 +455,8 @@
 
   static final class StarFieldTypeSignature extends FieldTypeSignature {
 
-    static final StarFieldTypeSignature STAR_FIELD_TYPE_SIGNATURE = new StarFieldTypeSignature();
+    private static final StarFieldTypeSignature STAR_FIELD_TYPE_SIGNATURE =
+        new StarFieldTypeSignature();
 
     private StarFieldTypeSignature() {
       super(WildcardIndicator.NONE);
@@ -462,6 +471,10 @@
     public boolean isStar() {
       return true;
     }
+
+    public static StarFieldTypeSignature getStarFieldTypeSignature() {
+      return STAR_FIELD_TYPE_SIGNATURE;
+    }
   }
 
   private static final ClassTypeSignature NO_FIELD_TYPE_SIGNATURE =
@@ -475,26 +488,34 @@
     // Note that this could be nested, e.g., Map<K, Consumer<V>>.
     final List<FieldTypeSignature> typeArguments;
 
-    // TODO(b/129925954): towards immutable structure?
-    // Double-linked enclosing-inner relations.
-    ClassTypeSignature enclosingTypeSignature;
-    ClassTypeSignature innerTypeSignature;
+    final ClassTypeSignature enclosingTypeSignature;
 
     public ClassTypeSignature(DexType type) {
-      this(type, EMPTY_TYPE_ARGUMENTS);
+      this(type, EMPTY_TYPE_ARGUMENTS, null);
     }
 
     public ClassTypeSignature(DexType type, List<FieldTypeSignature> typeArguments) {
-      this(type, typeArguments, WildcardIndicator.NOT_AN_ARGUMENT);
+      this(type, typeArguments, null, WildcardIndicator.NOT_AN_ARGUMENT);
+    }
+
+    public ClassTypeSignature(
+        DexType type,
+        List<FieldTypeSignature> typeArguments,
+        ClassTypeSignature enclosingTypeSignature) {
+      this(type, typeArguments, enclosingTypeSignature, WildcardIndicator.NOT_AN_ARGUMENT);
     }
 
     private ClassTypeSignature(
-        DexType type, List<FieldTypeSignature> typeArguments, WildcardIndicator indicator) {
+        DexType type,
+        List<FieldTypeSignature> typeArguments,
+        ClassTypeSignature enclosingTypeSignature,
+        WildcardIndicator indicator) {
       super(indicator);
       assert type != null;
       assert typeArguments != null;
       this.type = type;
       this.typeArguments = typeArguments;
+      this.enclosingTypeSignature = enclosingTypeSignature;
       assert typeArguments.stream().allMatch(FieldTypeSignature::isArgument);
     }
 
@@ -519,10 +540,7 @@
     @Override
     public ClassTypeSignature asArgument(WildcardIndicator indicator) {
       assert indicator != WildcardIndicator.NOT_AN_ARGUMENT;
-      ClassTypeSignature argument = new ClassTypeSignature(type, typeArguments, indicator);
-      argument.innerTypeSignature = this.innerTypeSignature;
-      argument.enclosingTypeSignature = this.enclosingTypeSignature;
-      return argument;
+      return new ClassTypeSignature(type, typeArguments, enclosingTypeSignature, indicator);
     }
 
     @Override
@@ -530,17 +548,23 @@
       return new ArrayTypeSignature(this);
     }
 
-    static void link(ClassTypeSignature outer, ClassTypeSignature inner) {
-      assert outer.innerTypeSignature == null && inner.enclosingTypeSignature == null;
-      outer.innerTypeSignature = inner;
-      inner.enclosingTypeSignature = outer;
-    }
-
-    public void visit(GenericSignatureVisitor visitor) {
-      visitor.visitTypeArguments(typeArguments);
-      if (innerTypeSignature != null) {
-        visitor.visitSimpleClass(innerTypeSignature);
+    public ClassTypeSignature visit(GenericSignatureVisitor visitor) {
+      DexType visitedType = visitor.visitType(type);
+      if (visitedType == null) {
+        return null;
       }
+      List<FieldTypeSignature> rewrittenArguments = visitor.visitTypeArguments(typeArguments);
+      ClassTypeSignature rewrittenOuter = null;
+      if (enclosingTypeSignature != null) {
+        rewrittenOuter = visitor.visitSimpleClass(enclosingTypeSignature);
+      }
+      if (type == visitedType
+          && typeArguments == rewrittenArguments
+          && enclosingTypeSignature == rewrittenOuter) {
+        return this;
+      }
+      return new ClassTypeSignature(
+          visitedType, rewrittenArguments, rewrittenOuter, getWildcardIndicator());
     }
 
     public boolean hasTypeVariableArguments() {
@@ -592,8 +616,15 @@
       return new ArrayTypeSignature(this);
     }
 
-    public void visit(GenericSignatureVisitor visitor) {
-      visitor.visitTypeSignature(elementSignature);
+    public ArrayTypeSignature visit(GenericSignatureVisitor visitor) {
+      TypeSignature rewrittenElementSignature = visitor.visitTypeSignature(elementSignature);
+      if (rewrittenElementSignature == null) {
+        return null;
+      }
+      if (elementSignature == rewrittenElementSignature) {
+        return this;
+      }
+      return new ArrayTypeSignature(elementSignature, getWildcardIndicator());
     }
   }
 
@@ -743,11 +774,20 @@
       return this;
     }
 
-    public void visit(GenericSignatureVisitor visitor) {
-      visitor.visitFormalTypeParameters(formalTypeParameters);
-      visitor.visitMethodTypeSignatures(typeSignatures);
-      visitor.visitReturnType(returnType);
-      visitor.visitThrowsSignatures(throwsSignatures);
+    public MethodTypeSignature visit(GenericSignatureVisitor visitor) {
+      List<FormalTypeParameter> rewrittenParameters =
+          visitor.visitFormalTypeParameters(formalTypeParameters);
+      List<TypeSignature> rewrittenSignatures = visitor.visitMethodTypeSignatures(typeSignatures);
+      ReturnType rewrittenReturnType = visitor.visitReturnType(returnType);
+      List<TypeSignature> rewrittenThrows = visitor.visitThrowsSignatures(throwsSignatures);
+      if (formalTypeParameters == rewrittenParameters
+          && typeSignatures == rewrittenSignatures
+          && returnType == rewrittenReturnType
+          && throwsSignatures == rewrittenThrows) {
+        return this;
+      }
+      return new MethodTypeSignature(
+          rewrittenParameters, rewrittenSignatures, rewrittenReturnType, rewrittenThrows);
     }
 
     public List<FormalTypeParameter> getFormalTypeParameters() {
@@ -800,8 +840,9 @@
     }
 
     @Override
-    public void visit(GenericSignatureVisitor visitor) {
+    public MethodTypeSignature visit(GenericSignatureVisitor visitor) {
       assert false : "Should not visit an invalid signature";
+      return this;
     }
 
     @Override
@@ -1072,12 +1113,11 @@
       DexType parsedEnclosingType = parsedTypeName(qualIdent.toString());
 
       List<FieldTypeSignature> typeArguments = updateOptTypeArguments();
-      ClassTypeSignature outerMostTypeSignature =
+
+      ClassTypeSignature outerTypeSignature =
           new ClassTypeSignature(
               parsedEnclosingType, typeArguments.isEmpty() ? EMPTY_TYPE_ARGUMENTS : typeArguments);
-
-      ClassTypeSignature outerTypeSignature = outerMostTypeSignature;
-      ClassTypeSignature innerTypeSignature;
+      ClassTypeSignature innerTypeSignature = null;
       while (symbol == '.') {
         // Deal with Member Classes.
         scanSymbol();
@@ -1088,13 +1128,13 @@
         innerTypeSignature =
             new ClassTypeSignature(
                 parsedEnclosingType,
-                typeArguments.isEmpty() ? EMPTY_TYPE_ARGUMENTS : typeArguments);
-        ClassTypeSignature.link(outerTypeSignature, innerTypeSignature);
+                typeArguments.isEmpty() ? EMPTY_TYPE_ARGUMENTS : typeArguments,
+                outerTypeSignature);
         outerTypeSignature = innerTypeSignature;
       }
 
       expect(';');
-      return outerMostTypeSignature;
+      return innerTypeSignature != null ? innerTypeSignature : outerTypeSignature;
     }
 
     private List<FieldTypeSignature> updateOptTypeArguments() {
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureEnqueuerAnalysis.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureEnqueuerAnalysis.java
index a7e9927..ea66ba7 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureEnqueuerAnalysis.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureEnqueuerAnalysis.java
@@ -54,105 +54,136 @@
     }
 
     @Override
-    public void visitClassSignature(ClassSignature classSignature) {
+    public ClassSignature visitClassSignature(ClassSignature classSignature) {
       if (classSignature.hasNoSignature()) {
-        return;
+        return classSignature;
       }
-      classSignature.visit(this);
+      return classSignature.visit(this);
     }
 
     @Override
-    public void visitMethodSignature(MethodTypeSignature methodSignature) {
+    public MethodTypeSignature visitMethodSignature(MethodTypeSignature methodSignature) {
       if (methodSignature.hasNoSignature()) {
-        return;
+        return methodSignature;
       }
-      methodSignature.visit(this);
+      return methodSignature.visit(this);
     }
 
     @Override
-    public void visitFieldTypeSignature(FieldTypeSignature fieldSignature) {
+    public FieldTypeSignature visitFieldTypeSignature(FieldTypeSignature fieldSignature) {
       if (fieldSignature.hasNoSignature()) {
-        return;
+        return fieldSignature;
       }
       if (fieldSignature.isStar()) {
-        return;
+        return fieldSignature;
       }
       if (fieldSignature.isTypeVariableSignature()) {
-        return;
+        return fieldSignature;
       }
       if (fieldSignature.isArrayTypeSignature()) {
         fieldSignature.asArrayTypeSignature().visit(this);
-        return;
+        return fieldSignature;
       }
       assert fieldSignature.isClassTypeSignature();
-      visitClassTypeSignature(fieldSignature.asClassTypeSignature());
-    }
-
-    private void visitClassTypeSignature(ClassTypeSignature classTypeSignature) {
-      enqueuerDefinitionSupplier.definitionFor(classTypeSignature.type, context);
-      classTypeSignature.visit(this);
+      return fieldSignature.asClassTypeSignature().visit(this);
     }
 
     @Override
-    public void visitFormalTypeParameters(List<FormalTypeParameter> formalTypeParameters) {
+    public List<FormalTypeParameter> visitFormalTypeParameters(
+        List<FormalTypeParameter> formalTypeParameters) {
       formalTypeParameters.forEach(formalTypeParameter -> formalTypeParameter.visit(this));
+      return formalTypeParameters;
     }
 
     @Override
-    public void visitClassBound(FieldTypeSignature fieldSignature) {
-      visitFieldTypeSignature(fieldSignature);
+    public FieldTypeSignature visitClassBound(FieldTypeSignature fieldSignature) {
+      return visitFieldTypeSignature(fieldSignature);
     }
 
     @Override
-    public void visitInterfaceBound(FieldTypeSignature fieldSignature) {
-      visitFieldTypeSignature(fieldSignature);
+    public List<FieldTypeSignature> visitInterfaceBounds(List<FieldTypeSignature> fieldSignatures) {
+      if (fieldSignatures == null) {
+        return null;
+      }
+      fieldSignatures.forEach(this::visitInterfaceBound);
+      return fieldSignatures;
     }
 
     @Override
-    public void visitSuperClass(ClassTypeSignature classTypeSignature) {
-      visitClassTypeSignature(classTypeSignature);
+    public FieldTypeSignature visitInterfaceBound(FieldTypeSignature fieldSignature) {
+      return visitFieldTypeSignature(fieldSignature);
     }
 
     @Override
-    public void visitSuperInterface(ClassTypeSignature classTypeSignature) {
-      visitClassTypeSignature(classTypeSignature);
+    public ClassTypeSignature visitSuperClass(ClassTypeSignature classTypeSignature) {
+      return classTypeSignature.visit(this);
     }
 
     @Override
-    public void visitTypeSignature(TypeSignature typeSignature) {
+    public List<ClassTypeSignature> visitSuperInterfaces(
+        List<ClassTypeSignature> interfaceSignatures) {
+      if (interfaceSignatures == null) {
+        return null;
+      }
+      interfaceSignatures.forEach(this::visitSuperInterface);
+      return interfaceSignatures;
+    }
+
+    @Override
+    public ClassTypeSignature visitSuperInterface(ClassTypeSignature classTypeSignature) {
+      return classTypeSignature.visit(this);
+    }
+
+    @Override
+    public TypeSignature visitTypeSignature(TypeSignature typeSignature) {
       if (typeSignature.isBaseTypeSignature()) {
-        return;
+        return typeSignature;
       }
       assert typeSignature.isFieldTypeSignature();
-      visitFieldTypeSignature(typeSignature.asFieldTypeSignature());
+      return visitFieldTypeSignature(typeSignature.asFieldTypeSignature());
     }
 
     @Override
-    public void visitSimpleClass(ClassTypeSignature classTypeSignature) {
-      visitClassTypeSignature(classTypeSignature);
+    public ClassTypeSignature visitSimpleClass(ClassTypeSignature classTypeSignature) {
+      return classTypeSignature.visit(this);
     }
 
     @Override
-    public void visitReturnType(ReturnType returnType) {
+    public ReturnType visitReturnType(ReturnType returnType) {
       if (returnType.isVoidDescriptor()) {
-        return;
+        return returnType;
       }
       visitTypeSignature(returnType.typeSignature);
+      return returnType;
     }
 
     @Override
-    public void visitMethodTypeSignatures(List<TypeSignature> typeSignatures) {
+    public List<TypeSignature> visitMethodTypeSignatures(List<TypeSignature> typeSignatures) {
       typeSignatures.forEach(this::visitTypeSignature);
+      return typeSignatures;
     }
 
     @Override
-    public void visitThrowsSignatures(List<TypeSignature> typeSignatures) {
+    public List<TypeSignature> visitThrowsSignatures(List<TypeSignature> typeSignatures) {
       typeSignatures.forEach(this::visitTypeSignature);
+      return typeSignatures;
     }
 
     @Override
-    public void visitTypeArguments(List<FieldTypeSignature> typeArguments) {
+    public List<FieldTypeSignature> visitTypeArguments(List<FieldTypeSignature> typeArguments) {
       typeArguments.forEach(this::visitFieldTypeSignature);
+      return typeArguments;
+    }
+
+    @Override
+    public FormalTypeParameter visitFormalTypeParameter(FormalTypeParameter formalTypeParameter) {
+      return formalTypeParameter.visit(this);
+    }
+
+    @Override
+    public DexType visitType(DexType type) {
+      enqueuerDefinitionSupplier.definitionFor(type, context);
+      return type;
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignaturePrinter.java b/src/main/java/com/android/tools/r8/graph/GenericSignaturePrinter.java
index a670da0..739bc27 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignaturePrinter.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignaturePrinter.java
@@ -30,98 +30,123 @@
   private final StringBuilder sb = new StringBuilder();
 
   @Override
-  public void visitClassSignature(ClassSignature classSignature) {
-    classSignature.visit(this);
+  public ClassSignature visitClassSignature(ClassSignature classSignature) {
+    return classSignature.visit(this);
   }
 
   @Override
-  public void visitFieldTypeSignature(FieldTypeSignature fieldSignature) {
+  public FieldTypeSignature visitFieldTypeSignature(FieldTypeSignature fieldSignature) {
     printFieldTypeSignature(fieldSignature, false);
+    return fieldSignature;
   }
 
   @Override
-  public void visitMethodSignature(MethodTypeSignature methodSignature) {
-    methodSignature.visit(this);
+  public MethodTypeSignature visitMethodSignature(MethodTypeSignature methodSignature) {
+    return methodSignature.visit(this);
   }
 
   @Override
-  public void visitMethodTypeSignatures(List<TypeSignature> typeSignatures) {
+  public List<TypeSignature> visitMethodTypeSignatures(List<TypeSignature> typeSignatures) {
     sb.append("(");
     typeSignatures.forEach(this::visitTypeSignature);
     sb.append(")");
+    return typeSignatures;
   }
 
   @Override
-  public void visitReturnType(ReturnType returnType) {
+  public ReturnType visitReturnType(ReturnType returnType) {
     if (returnType.isVoidDescriptor()) {
       sb.append("V");
     } else {
       visitTypeSignature(returnType.typeSignature);
     }
+    return returnType;
   }
 
   @Override
-  public void visitThrowsSignatures(List<TypeSignature> typeSignatures) {
+  public List<TypeSignature> visitThrowsSignatures(List<TypeSignature> typeSignatures) {
     for (TypeSignature typeSignature : typeSignatures) {
       sb.append("^");
       visitTypeSignature(typeSignature);
     }
+    return typeSignatures;
   }
 
   @Override
-  public void visitFormalTypeParameters(List<FormalTypeParameter> formalTypeParameters) {
+  public List<FormalTypeParameter> visitFormalTypeParameters(
+      List<FormalTypeParameter> formalTypeParameters) {
     if (formalTypeParameters.isEmpty()) {
-      return;
+      return formalTypeParameters;
     }
     sb.append("<");
-    for (FormalTypeParameter formalTypeParameter : formalTypeParameters) {
-      sb.append(formalTypeParameter.name);
-      formalTypeParameter.visit(this);
-    }
+    formalTypeParameters.forEach(this::visitFormalTypeParameter);
     sb.append(">");
+    return formalTypeParameters;
   }
 
   @Override
-  public void visitClassBound(FieldTypeSignature fieldSignature) {
+  public FieldTypeSignature visitClassBound(FieldTypeSignature fieldSignature) {
     sb.append(":");
     printFieldTypeSignature(fieldSignature, false);
+    return fieldSignature;
   }
 
   @Override
-  public void visitInterfaceBound(FieldTypeSignature fieldSignature) {
+  public List<FieldTypeSignature> visitInterfaceBounds(List<FieldTypeSignature> fieldSignatures) {
+    if (fieldSignatures == null) {
+      return null;
+    }
+    fieldSignatures.forEach(this::visitInterfaceBound);
+    return fieldSignatures;
+  }
+
+  @Override
+  public FieldTypeSignature visitInterfaceBound(FieldTypeSignature fieldSignature) {
     sb.append(":");
     printFieldTypeSignature(fieldSignature, false);
+    return fieldSignature;
   }
 
   @Override
-  public void visitSuperClass(ClassTypeSignature classTypeSignature) {
+  public ClassTypeSignature visitSuperClass(ClassTypeSignature classTypeSignature) {
     printFieldTypeSignature(classTypeSignature, false);
+    return classTypeSignature;
   }
 
   @Override
-  public void visitSuperInterface(ClassTypeSignature classTypeSignature) {
+  public List<ClassTypeSignature> visitSuperInterfaces(
+      List<ClassTypeSignature> interfaceSignatures) {
+    interfaceSignatures.forEach(this::visitSuperInterface);
+    return interfaceSignatures;
+  }
+
+  @Override
+  public ClassTypeSignature visitSuperInterface(ClassTypeSignature classTypeSignature) {
     printFieldTypeSignature(classTypeSignature, false);
+    return classTypeSignature;
   }
 
   @Override
-  public void visitTypeSignature(TypeSignature typeSignature) {
+  public TypeSignature visitTypeSignature(TypeSignature typeSignature) {
     if (typeSignature.isBaseTypeSignature()) {
       DexType type = typeSignature.asBaseTypeSignature().type;
       sb.append(type.toDescriptorString());
     } else {
       printFieldTypeSignature(typeSignature.asFieldTypeSignature(), false);
     }
+    return typeSignature;
   }
 
   @Override
-  public void visitSimpleClass(ClassTypeSignature classTypeSignature) {
+  public ClassTypeSignature visitSimpleClass(ClassTypeSignature classTypeSignature) {
     printFieldTypeSignature(classTypeSignature, true);
+    return classTypeSignature;
   }
 
   @Override
-  public void visitTypeArguments(List<FieldTypeSignature> typeArguments) {
+  public List<FieldTypeSignature> visitTypeArguments(List<FieldTypeSignature> typeArguments) {
     if (typeArguments.isEmpty()) {
-      return;
+      return typeArguments;
     }
     sb.append("<");
     for (FieldTypeSignature typeArgument : typeArguments) {
@@ -133,10 +158,17 @@
       visitTypeSignature(typeArgument);
     }
     sb.append(">");
+    return typeArguments;
+  }
+
+  @Override
+  public FormalTypeParameter visitFormalTypeParameter(FormalTypeParameter formalTypeParameter) {
+    sb.append(formalTypeParameter.name);
+    return formalTypeParameter.visit(this);
   }
 
   private void printFieldTypeSignature(
-      FieldTypeSignature fieldTypeSignature, boolean printingInner) {
+      FieldTypeSignature fieldTypeSignature, boolean printingOuter) {
     // For inner member classes we only print the inner name and the type-arguments.
     if (fieldTypeSignature.isStar()) {
       sb.append("*");
@@ -151,11 +183,14 @@
       if (classTypeSignature.hasNoSignature()) {
         return;
       }
+      // Visit enclosing before printing the type name to ensure we
+      if (classTypeSignature.enclosingTypeSignature != null) {
+        visitSimpleClass(classTypeSignature.enclosingTypeSignature);
+      }
       String renamedString = namingLens.lookupDescriptor(classTypeSignature.type).toString();
-      if (!printingInner) {
+      if (classTypeSignature.enclosingTypeSignature == null) {
         sb.append("L").append(DescriptorUtils.getBinaryNameFromDescriptor(renamedString));
       } else {
-        assert classTypeSignature.enclosingTypeSignature != null;
         DexType enclosingType = classTypeSignature.enclosingTypeSignature.type;
         String outerDescriptor = namingLens.lookupDescriptor(enclosingType).toString();
         String innerClassName = DescriptorUtils.getInnerClassName(outerDescriptor, renamedString);
@@ -170,14 +205,21 @@
         }
         sb.append(".").append(innerClassName);
       }
-      classTypeSignature.visit(this);
-      if (!printingInner) {
+      visitTypeArguments(classTypeSignature.typeArguments);
+      if (!printingOuter) {
         sb.append(";");
       }
     }
   }
 
   @Override
+  public DexType visitType(DexType type) {
+    // We need to delay printing of class type until enclosing class has been visited. We therefore
+    // only print in printFieldTypeSignature.
+    return type;
+  }
+
+  @Override
   public String toString() {
     return sb.toString();
   }
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeRewriter.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeRewriter.java
index d20833f..5820a4c 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeRewriter.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeRewriter.java
@@ -8,19 +8,17 @@
 import static com.android.tools.r8.graph.GenericSignature.EMPTY_TYPE_ARGUMENTS;
 import static com.android.tools.r8.graph.GenericSignature.EMPTY_TYPE_PARAMS;
 import static com.android.tools.r8.graph.GenericSignature.EMPTY_TYPE_SIGNATURES;
-import static com.android.tools.r8.graph.GenericSignature.FieldTypeSignature.noSignature;
-import static com.android.tools.r8.graph.GenericSignature.StarFieldTypeSignature.STAR_FIELD_TYPE_SIGNATURE;
 import static com.google.common.base.Predicates.alwaysFalse;
 
-import com.android.tools.r8.graph.GenericSignature.ArrayTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.ClassSignature;
 import com.android.tools.r8.graph.GenericSignature.ClassTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.FieldTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.FormalTypeParameter;
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.ReturnType;
+import com.android.tools.r8.graph.GenericSignature.StarFieldTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.TypeSignature;
-import java.util.ArrayList;
+import com.android.tools.r8.utils.ListUtils;
 import java.util.List;
 import java.util.function.Function;
 import java.util.function.Predicate;
@@ -60,14 +58,15 @@
     if (classSignature.hasNoSignature() || classSignature.isInvalid()) {
       return classSignature;
     }
-    return new ClassSignatureRewriter().run(classSignature);
+    return new GenericSignatureRewriter().visitClassSignature(classSignature);
   }
 
   public FieldTypeSignature rewrite(FieldTypeSignature fieldTypeSignature) {
     if (fieldTypeSignature.hasNoSignature() || fieldTypeSignature.isInvalid()) {
       return fieldTypeSignature;
     }
-    FieldTypeSignature rewrittenSignature = new TypeSignatureRewriter().run(fieldTypeSignature);
+    FieldTypeSignature rewrittenSignature =
+        new GenericSignatureRewriter().visitFieldTypeSignature(fieldTypeSignature);
     return rewrittenSignature == null ? FieldTypeSignature.noSignature() : rewrittenSignature;
   }
 
@@ -75,268 +74,169 @@
     if (methodTypeSignature.hasNoSignature() || methodTypeSignature.isInvalid()) {
       return methodTypeSignature;
     }
-    return new MethodTypeSignatureRewriter().run(methodTypeSignature);
+    return new GenericSignatureRewriter().visitMethodSignature(methodTypeSignature);
   }
 
-  private class ClassSignatureRewriter implements GenericSignatureVisitor {
-
-    private final List<FormalTypeParameter> rewrittenTypeParameters = new ArrayList<>();
-    private ClassTypeSignature rewrittenSuperClass;
-    private final List<ClassTypeSignature> rewrittenSuperInterfaces = new ArrayList<>();
+  private class GenericSignatureRewriter implements GenericSignatureVisitor {
 
     @Override
-    public void visitClassSignature(ClassSignature classSignature) {
-      classSignature.visit(this);
-    }
-
-    @Override
-    public void visitFormalTypeParameters(List<FormalTypeParameter> formalTypeParameters) {
-      for (FormalTypeParameter formalTypeParameter : formalTypeParameters) {
-        rewrittenTypeParameters.add(new FormalTypeParameterRewriter().run(formalTypeParameter));
-      }
-    }
-
-    @Override
-    public void visitSuperClass(ClassTypeSignature classTypeSignature) {
-      rewrittenSuperClass = new ClassTypeSignatureRewriter(true).run(classTypeSignature);
-      if (rewrittenSuperClass == null) {
-        rewrittenSuperClass = new ClassTypeSignature(factory.objectType, EMPTY_TYPE_ARGUMENTS);
-      }
-    }
-
-    @Override
-    public void visitSuperInterface(ClassTypeSignature classTypeSignature) {
-      ClassTypeSignature superInterface =
-          new ClassTypeSignatureRewriter(true).run(classTypeSignature);
-      if (superInterface != null) {
-        rewrittenSuperInterfaces.add(superInterface);
-      }
-    }
-
-    private ClassSignature run(ClassSignature classSignature) {
-      classSignature.visit(this);
-      if (rewrittenTypeParameters.isEmpty()
-          && rewrittenSuperInterfaces.isEmpty()
-          && rewrittenSuperClass.hasNoSignature()
-          && rewrittenSuperClass.type == factory.objectType) {
+    public ClassSignature visitClassSignature(ClassSignature classSignature) {
+      ClassSignature rewritten = classSignature.visit(this);
+      if (rewritten.getFormalTypeParameters().isEmpty()
+          && rewritten.superInterfaceSignatures.isEmpty()
+          && rewritten.superClassSignature.type == factory.objectType) {
         return ClassSignature.noSignature();
       }
-      return new ClassSignature(
-          rewrittenTypeParameters.isEmpty() ? EMPTY_TYPE_PARAMS : rewrittenTypeParameters,
-          rewrittenSuperClass,
-          rewrittenSuperInterfaces.isEmpty() ? EMPTY_SUPER_INTERFACES : rewrittenSuperInterfaces);
-    }
-  }
-
-  private class MethodTypeSignatureRewriter implements GenericSignatureVisitor {
-
-    private final List<FormalTypeParameter> rewrittenTypeParameters = new ArrayList<>();
-    private final List<TypeSignature> rewrittenTypeSignatures = new ArrayList<>();
-
-    ReturnType rewrittenReturnType = null;
-    private final List<TypeSignature> rewrittenThrowsSignatures = new ArrayList<>();
-
-    @Override
-    public void visitFormalTypeParameters(List<FormalTypeParameter> formalTypeParameters) {
-      for (FormalTypeParameter formalTypeParameter : formalTypeParameters) {
-        rewrittenTypeParameters.add(new FormalTypeParameterRewriter().run(formalTypeParameter));
-      }
+      return rewritten;
     }
 
     @Override
-    public void visitMethodTypeSignatures(List<TypeSignature> typeSignatures) {
-      for (TypeSignature typeSignature : typeSignatures) {
-        TypeSignature rewrittenType = new TypeSignatureRewriter().run(typeSignature);
-        rewrittenTypeSignatures.add(rewrittenType == null ? objectTypeSignature : rewrittenType);
-      }
+    public MethodTypeSignature visitMethodSignature(MethodTypeSignature methodSignature) {
+      return methodSignature.visit(this);
     }
 
     @Override
-    public void visitReturnType(ReturnType returnType) {
-      if (returnType.isVoidDescriptor()) {
-        rewrittenReturnType = ReturnType.VOID;
+    public FieldTypeSignature visitFieldTypeSignature(FieldTypeSignature fieldSignature) {
+      if (fieldSignature.isStar() || fieldSignature.isTypeVariableSignature()) {
+        return fieldSignature;
+      } else if (fieldSignature.isArrayTypeSignature()) {
+        return fieldSignature.asArrayTypeSignature().visit(this);
       } else {
-        TypeSignature originalType = returnType.typeSignature();
-        TypeSignature rewrittenType = new TypeSignatureRewriter().run(originalType);
-        if (rewrittenType == null) {
-          rewrittenReturnType = ReturnType.VOID;
-        } else if (rewrittenType == originalType) {
-          rewrittenReturnType = returnType;
-        } else {
-          rewrittenReturnType = new ReturnType(rewrittenType);
-        }
+        assert fieldSignature.isClassTypeSignature();
+        return fieldSignature.asClassTypeSignature().visit(this);
       }
     }
 
     @Override
-    public void visitThrowsSignatures(List<TypeSignature> typeSignatures) {
-      for (TypeSignature typeSignature : typeSignatures) {
-        TypeSignature rewrittenType = new TypeSignatureRewriter().run(typeSignature);
-        // If a throwing type is no longer found we remove it from the signature.
-        if (rewrittenType != null) {
-          rewrittenThrowsSignatures.add(rewrittenType);
-        }
-      }
-    }
-
-    private MethodTypeSignature run(MethodTypeSignature methodTypeSignature) {
-      methodTypeSignature.visit(this);
-      assert rewrittenReturnType != null;
-      if (rewrittenTypeParameters.isEmpty()
-          && rewrittenTypeSignatures.isEmpty()
-          && rewrittenReturnType.isVoidDescriptor()
-          && rewrittenThrowsSignatures.isEmpty()) {
-        return MethodTypeSignature.noSignature();
-      }
-      return new MethodTypeSignature(
-          rewrittenTypeParameters.isEmpty() ? EMPTY_TYPE_PARAMS : rewrittenTypeParameters,
-          rewrittenTypeSignatures.isEmpty() ? EMPTY_TYPE_SIGNATURES : rewrittenTypeSignatures,
-          rewrittenReturnType,
-          rewrittenThrowsSignatures.isEmpty() ? EMPTY_TYPE_SIGNATURES : rewrittenThrowsSignatures);
-    }
-  }
-
-  private class FormalTypeParameterRewriter implements GenericSignatureVisitor {
-
-    private FieldTypeSignature rewrittenClassBound = noSignature();
-    private final List<FieldTypeSignature> rewrittenInterfaceBounds = new ArrayList<>();
-
-    @Override
-    public void visitClassBound(FieldTypeSignature fieldSignature) {
-      rewrittenClassBound = new TypeSignatureRewriter().run(fieldSignature);
-    }
-
-    @Override
-    public void visitInterfaceBound(FieldTypeSignature fieldSignature) {
-      FieldTypeSignature interfaceBound = new TypeSignatureRewriter().run(fieldSignature);
-      if (interfaceBound != null) {
-        rewrittenInterfaceBounds.add(interfaceBound);
-      }
-    }
-
-    private FormalTypeParameter run(FormalTypeParameter formalTypeParameter) {
-      formalTypeParameter.visit(this);
-      // Guard against the case where we have <T::...> that is, no class or interfaces bounds.
-      if (rewrittenInterfaceBounds.isEmpty()
-          && (rewrittenClassBound == null || !rewrittenClassBound.hasSignature())) {
-        rewrittenClassBound = objectTypeSignature;
-      }
-      return new FormalTypeParameter(
-          formalTypeParameter.name,
-          rewrittenClassBound == null ? noSignature() : rewrittenClassBound,
-          rewrittenInterfaceBounds.isEmpty() ? EMPTY_TYPE_ARGUMENTS : rewrittenInterfaceBounds);
-    }
-  }
-
-  private class TypeSignatureRewriter implements GenericSignatureVisitor {
-
-    private TypeSignature run(TypeSignature typeSignature) {
+    public TypeSignature visitTypeSignature(TypeSignature typeSignature) {
       if (typeSignature.isBaseTypeSignature()) {
         return typeSignature;
+      } else {
+        return visitFieldTypeSignature(typeSignature.asFieldTypeSignature());
       }
-      assert typeSignature.isFieldTypeSignature();
-      return run(typeSignature.asFieldTypeSignature());
     }
 
-    private FieldTypeSignature run(FieldTypeSignature fieldTypeSignature) {
-      if (fieldTypeSignature.isStar()) {
-        return fieldTypeSignature;
+    @Override
+    public List<FormalTypeParameter> visitFormalTypeParameters(
+        List<FormalTypeParameter> formalTypeParameters) {
+      if (formalTypeParameters.isEmpty()) {
+        return EMPTY_TYPE_PARAMS;
       }
-      if (fieldTypeSignature.isTypeVariableSignature()) {
-        return fieldTypeSignature;
+      return ListUtils.map(formalTypeParameters, this::visitFormalTypeParameter);
+    }
+
+    @Override
+    public FormalTypeParameter visitFormalTypeParameter(FormalTypeParameter formalTypeParameter) {
+      return formalTypeParameter.visit(this);
+    }
+
+    @Override
+    public ClassTypeSignature visitSuperClass(ClassTypeSignature classTypeSignature) {
+      ClassTypeSignature rewritten = classTypeSignature.visit(this);
+      return rewritten == null || rewritten.type() == context.type
+          ? new ClassTypeSignature(factory.objectType, EMPTY_TYPE_ARGUMENTS)
+          : rewritten;
+    }
+
+    @Override
+    public List<ClassTypeSignature> visitSuperInterfaces(
+        List<ClassTypeSignature> interfaceSignatures) {
+      if (interfaceSignatures.isEmpty()) {
+        return EMPTY_SUPER_INTERFACES;
       }
-      if (fieldTypeSignature.isArrayTypeSignature()) {
-        ArrayTypeSignature arrayTypeSignature = fieldTypeSignature.asArrayTypeSignature();
-        TypeSignature rewrittenElement = run(arrayTypeSignature.elementSignature);
-        if (rewrittenElement == null) {
-          return new ArrayTypeSignature(objectTypeSignature);
+      return ListUtils.mapNotNull(interfaceSignatures, this::visitSuperInterface);
+    }
+
+    @Override
+    public ClassTypeSignature visitSuperInterface(ClassTypeSignature classTypeSignature) {
+      ClassTypeSignature rewritten = classTypeSignature.visit(this);
+      return rewritten == null || rewritten.type() == context.type ? null : rewritten;
+    }
+
+    @Override
+    public List<TypeSignature> visitMethodTypeSignatures(List<TypeSignature> typeSignatures) {
+      if (typeSignatures.isEmpty()) {
+        return EMPTY_TYPE_SIGNATURES;
+      }
+      return ListUtils.map(
+          typeSignatures,
+          typeSignature -> {
+            TypeSignature rewrittenSignature = visitTypeSignature(typeSignature);
+            return rewrittenSignature == null ? objectTypeSignature : rewrittenSignature;
+          });
+    }
+
+    @Override
+    public ReturnType visitReturnType(ReturnType returnType) {
+      if (returnType.isVoidDescriptor()) {
+        return ReturnType.VOID;
+      } else {
+        TypeSignature originalType = returnType.typeSignature();
+        TypeSignature rewrittenType = visitTypeSignature(originalType);
+        if (rewrittenType == null) {
+          return ReturnType.VOID;
+        } else if (rewrittenType == originalType) {
+          return returnType;
+        } else {
+          return new ReturnType(rewrittenType);
         }
-        return rewrittenElement.toArrayTypeSignature();
       }
-      assert fieldTypeSignature.isClassTypeSignature();
-      ClassTypeSignature classTypeSignature = fieldTypeSignature.asClassTypeSignature();
-      if (classTypeSignature.hasNoSignature()) {
-        return classTypeSignature;
-      }
-      return new ClassTypeSignatureRewriter(false).run(classTypeSignature);
-    }
-  }
-
-  private class ClassTypeSignatureRewriter implements GenericSignatureVisitor {
-
-    private final boolean isSuperClassOrInterface;
-
-    // These fields are updated when iterating the modeled structure.
-    private DexType currentType;
-
-    // The following references are used to have a head and tail pointer to the classTypeSignature
-    // link we are building. The topClassSignature will have a reference to the top-most package
-    // and class-name. The parentClassSignature is a pointer pointing to the tail always and will
-    // be linked and updated when calling ClassTypeSignature.link.
-    private ClassTypeSignature topClassSignature;
-    private ClassTypeSignature parentClassSignature;
-
-    private ClassTypeSignatureRewriter(boolean isSuperClassOrInterface) {
-      this.isSuperClassOrInterface = isSuperClassOrInterface;
     }
 
     @Override
-    public void visitSimpleClass(ClassTypeSignature classTypeSignature) {
-      currentType = getTarget(classTypeSignature.type);
-      if (currentType == null) {
-        return;
+    public List<TypeSignature> visitThrowsSignatures(List<TypeSignature> typeSignatures) {
+      if (typeSignatures.isEmpty()) {
+        return EMPTY_TYPE_SIGNATURES;
       }
-      classTypeSignature.visit(this);
+      // If a throwing type is no longer found we remove it from the signature.
+      return ListUtils.mapNotNull(typeSignatures, this::visitTypeSignature);
     }
 
     @Override
-    public void visitTypeArguments(List<FieldTypeSignature> typeArguments) {
-      ClassTypeSignature newClassTypeSignature;
+    public FieldTypeSignature visitClassBound(FieldTypeSignature fieldSignature) {
+      return visitFieldTypeSignature(fieldSignature);
+    }
+
+    @Override
+    public List<FieldTypeSignature> visitInterfaceBounds(List<FieldTypeSignature> fieldSignatures) {
+      if (fieldSignatures == null) {
+        return null;
+      }
+      if (fieldSignatures.isEmpty()) {
+        return EMPTY_TYPE_ARGUMENTS;
+      }
+      return ListUtils.mapNotNull(fieldSignatures, this::visitFieldTypeSignature);
+    }
+
+    @Override
+    public FieldTypeSignature visitInterfaceBound(FieldTypeSignature fieldSignature) {
+      return visitFieldTypeSignature(fieldSignature);
+    }
+
+    @Override
+    public ClassTypeSignature visitSimpleClass(ClassTypeSignature classTypeSignature) {
+      return classTypeSignature.visit(this);
+    }
+
+    @Override
+    public List<FieldTypeSignature> visitTypeArguments(List<FieldTypeSignature> typeArguments) {
       if (typeArguments.isEmpty()) {
-        newClassTypeSignature = new ClassTypeSignature(currentType, EMPTY_TYPE_ARGUMENTS);
-      } else {
-        List<FieldTypeSignature> rewrittenTypeArguments = new ArrayList<>(typeArguments.size());
-        for (FieldTypeSignature typeArgument : typeArguments) {
-          if (typeArgument.isStar()) {
-            rewrittenTypeArguments.add(typeArgument);
-            continue;
-          }
-          FieldTypeSignature rewritten = new TypeSignatureRewriter().run(typeArgument);
-          if (rewritten != null) {
-            rewrittenTypeArguments.add(rewritten.asArgument(typeArgument.getWildcardIndicator()));
-          } else {
-            rewrittenTypeArguments.add(STAR_FIELD_TYPE_SIGNATURE);
-          }
-        }
-        newClassTypeSignature = new ClassTypeSignature(currentType, rewrittenTypeArguments);
+        return EMPTY_TYPE_ARGUMENTS;
       }
-      if (topClassSignature == null) {
-        topClassSignature = newClassTypeSignature;
-        parentClassSignature = newClassTypeSignature;
-      } else {
-        ClassTypeSignature.link(parentClassSignature, newClassTypeSignature);
-        parentClassSignature = newClassTypeSignature;
-      }
+      return ListUtils.map(
+          typeArguments,
+          fieldTypeSignature -> {
+            FieldTypeSignature rewrittenSignature = visitFieldTypeSignature(fieldTypeSignature);
+            return rewrittenSignature == null
+                ? StarFieldTypeSignature.getStarFieldTypeSignature()
+                : rewrittenSignature;
+          });
     }
 
-    private ClassTypeSignature run(ClassTypeSignature classTypeSignature) {
-      currentType = getTarget(classTypeSignature.type);
-      if (currentType == null) {
-        return null;
-      }
-      classTypeSignature.visit(this);
-      return topClassSignature;
-    }
-
-    private DexType getTarget(DexType type) {
+    @Override
+    public DexType visitType(DexType type) {
       DexType rewrittenType = lookupType.apply(type);
-      if (wasPruned.test(rewrittenType)) {
-        return null;
-      }
-      if (isSuperClassOrInterface && context.type == rewrittenType) {
-        return null;
-      }
-      return rewrittenType;
+      return wasPruned.test(rewrittenType) ? null : rewrittenType;
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureVisitor.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureVisitor.java
index d3840dd..ba1d8f2 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureVisitor.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureVisitor.java
@@ -16,59 +16,77 @@
 
 public interface GenericSignatureVisitor {
 
-  default void visitClassSignature(ClassSignature classSignature) {
+  default ClassSignature visitClassSignature(ClassSignature classSignature) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitMethodSignature(MethodTypeSignature methodSignature) {
+  default MethodTypeSignature visitMethodSignature(MethodTypeSignature methodSignature) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitFieldTypeSignature(FieldTypeSignature fieldSignature) {
+  default FieldTypeSignature visitFieldTypeSignature(FieldTypeSignature fieldSignature) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitFormalTypeParameters(List<FormalTypeParameter> formalTypeParameters) {
+  default List<FormalTypeParameter> visitFormalTypeParameters(
+      List<FormalTypeParameter> formalTypeParameters) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitClassBound(FieldTypeSignature fieldSignature) {
+  default FormalTypeParameter visitFormalTypeParameter(FormalTypeParameter formalTypeParameter) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitInterfaceBound(FieldTypeSignature fieldSignature) {
+  default FieldTypeSignature visitClassBound(FieldTypeSignature fieldSignature) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitSuperClass(ClassTypeSignature classTypeSignature) {
+  default List<FieldTypeSignature> visitInterfaceBounds(List<FieldTypeSignature> fieldSignatures) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitSuperInterface(ClassTypeSignature classTypeSignature) {
+  default FieldTypeSignature visitInterfaceBound(FieldTypeSignature fieldSignature) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitTypeSignature(TypeSignature typeSignature) {
+  default ClassTypeSignature visitSuperClass(ClassTypeSignature classTypeSignature) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitSimpleClass(ClassTypeSignature classTypeSignature) {
+  default List<ClassTypeSignature> visitSuperInterfaces(
+      List<ClassTypeSignature> interfaceSignatures) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitReturnType(ReturnType returnType) {
+  default ClassTypeSignature visitSuperInterface(ClassTypeSignature classTypeSignature) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitMethodTypeSignatures(List<TypeSignature> typeSignatures) {
+  default TypeSignature visitTypeSignature(TypeSignature typeSignature) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitThrowsSignatures(List<TypeSignature> typeSignatures) {
+  default ClassTypeSignature visitSimpleClass(ClassTypeSignature classTypeSignature) {
     throw new Unreachable("Implement if visited");
   }
 
-  default void visitTypeArguments(List<FieldTypeSignature> typeArguments) {
+  default ReturnType visitReturnType(ReturnType returnType) {
+    throw new Unreachable("Implement if visited");
+  }
+
+  default List<TypeSignature> visitMethodTypeSignatures(List<TypeSignature> typeSignatures) {
+    throw new Unreachable("Implement if visited");
+  }
+
+  default List<TypeSignature> visitThrowsSignatures(List<TypeSignature> typeSignatures) {
+    throw new Unreachable("Implement if visited");
+  }
+
+  default List<FieldTypeSignature> visitTypeArguments(List<FieldTypeSignature> typeArguments) {
+    throw new Unreachable("Implement if visited");
+  }
+
+  default DexType visitType(DexType type) {
     throw new Unreachable("Implement if visited");
   }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/ListUtils.java b/src/main/java/com/android/tools/r8/utils/ListUtils.java
index f4c8deb..b04728e 100644
--- a/src/main/java/com/android/tools/r8/utils/ListUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ListUtils.java
@@ -87,6 +87,17 @@
     return result;
   }
 
+  public static <S, T> List<T> mapNotNull(Collection<S> list, Function<S, T> fn) {
+    List<T> result = new ArrayList<>(list.size());
+    for (S element : list) {
+      T mapped = fn.apply(element);
+      if (mapped != null) {
+        result.add(mapped);
+      }
+    }
+    return result;
+  }
+
   /**
    * Rewrites the input list based on the given function. Returns the mapped list if any elements
    * were rewritten, otherwise returns the original list.
diff --git a/src/test/java/com/android/tools/r8/graph/GenericSignatureTest.java b/src/test/java/com/android/tools/r8/graph/GenericSignatureTest.java
index 2d1be5b..df62f93 100644
--- a/src/test/java/com/android/tools/r8/graph/GenericSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/graph/GenericSignatureTest.java
@@ -125,10 +125,16 @@
     assertNull(formalTypeParameter.interfaceBounds);
     assertTrue(formalTypeParameter.classBound.isClassTypeSignature());
     ClassTypeSignature classBoundSignature = formalTypeParameter.classBound.asClassTypeSignature();
-    assertEquals(y.getDexProgramClass().type, classBoundSignature.innerTypeSignature.type);
-    assertEquals(1, classBoundSignature.typeArguments.size());
+    assertEquals(y.getDexProgramClass().type, classBoundSignature.type);
+    assertEquals(1, classBoundSignature.enclosingTypeSignature.typeArguments.size());
     assertEquals(
-        "T", classBoundSignature.typeArguments.get(0).asTypeVariableSignature().typeVariable);
+        "T",
+        classBoundSignature
+            .enclosingTypeSignature
+            .typeArguments
+            .get(0)
+            .asTypeVariableSignature()
+            .typeVariable);
 
     assertTrue(classSignature.superInterfaceSignatures.isEmpty());
     classTypeSignature = classSignature.superClassSignature;
@@ -173,7 +179,7 @@
     assertTrue(methodFormalParameter.classBound.isClassTypeSignature());
     assertEquals(
         y.getDexProgramClass().getType(),
-        methodFormalParameter.classBound.asClassTypeSignature().innerTypeSignature.type);
+        methodFormalParameter.classBound.asClassTypeSignature().type);
     assertNotNull(methodFormalParameter.interfaceBounds);
     assertEquals(1, methodFormalParameter.interfaceBounds.size());
     FieldTypeSignature interfaceBound = methodFormalParameter.interfaceBounds.get(0);
@@ -258,29 +264,31 @@
     check_A_Y_foo_bar_baz(y, appView);
   }
 
-  private void check_A_Y(ClassSubject a, ClassSubject y, ClassTypeSignature signature) {
+  private void check_A(ClassSubject a, ClassTypeSignature signature) {
     assertEquals(a.getDexProgramClass().type, signature.type);
     List<FieldTypeSignature> typeArguments = signature.typeArguments;
     assertEquals(1, typeArguments.size());
     FieldTypeSignature typeArgument = typeArguments.get(0);
     assertTrue(typeArgument.isTypeVariableSignature());
     assertEquals("T", typeArgument.asTypeVariableSignature().typeVariable);
-    assertEquals(y.getDexProgramClass().type, signature.innerTypeSignature.type);
+  }
+
+  private void check_A_Y(ClassSubject a, ClassSubject y, ClassTypeSignature signature) {
+    check_A(a, signature.enclosingTypeSignature);
+    assertEquals(y.getDexProgramClass().type, signature.type);
   }
 
   private void check_A_Y_YY(
       ClassSubject a, ClassSubject y, ClassSubject yy, ClassTypeSignature signature) {
-    check_A_Y(a, y, signature);
-    assertEquals(
-        yy.getDexProgramClass().type, signature.innerTypeSignature.innerTypeSignature.type);
+    check_A_Y(a, y, signature.enclosingTypeSignature);
+    assertEquals(yy.getDexProgramClass().type, signature.type);
   }
 
   private void check_A_Y_ZZ(
       ClassSubject a, ClassSubject y, ClassSubject zz, ClassTypeSignature signature) {
-    check_A_Y(a, y, signature);
-    ClassTypeSignature innerMost = signature.innerTypeSignature.innerTypeSignature;
-    assertEquals(zz.getDexProgramClass().type, innerMost.type);
-    List<FieldTypeSignature> typeArguments = innerMost.typeArguments;
+    check_A_Y(a, y, signature.enclosingTypeSignature);
+    assertEquals(zz.getDexProgramClass().type, signature.type);
+    List<FieldTypeSignature> typeArguments = signature.typeArguments;
     assertEquals(1, typeArguments.size());
     FieldTypeSignature typeArgument = typeArguments.get(0);
     assertTrue(typeArgument.isTypeVariableSignature());