diff --git a/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java b/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
index f37ce58..ae54120 100644
--- a/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
@@ -6,7 +6,6 @@
 
 import com.android.tools.r8.graph.GraphLens.NonIdentityGraphLens;
 import com.android.tools.r8.graph.classmerging.VerticallyMergedClasses;
-import com.android.tools.r8.ir.code.Invoke;
 import com.android.tools.r8.utils.MapUtils;
 import com.android.tools.r8.utils.collections.BidirectionalManyToOneMap;
 import com.google.common.collect.BiMap;
@@ -138,26 +137,32 @@
   }
 
   @Override
-  public DexType internalDescribeLookupClassType(DexType previous) {
-    return renamedTypeNames.getOrDefault(previous, previous);
-  }
-
-  @Override
-  public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Invoke.Type type) {
-    return GraphLens.getIdentityLens().lookupMethod(method, context, type);
-  }
-
-  @Override
   public RewrittenPrototypeDescription lookupPrototypeChangesForMethodDefinition(DexMethod method) {
     return GraphLens.getIdentityLens().lookupPrototypeChangesForMethodDefinition(method);
   }
 
   @Override
+  public DexType internalDescribeLookupClassType(DexType previous) {
+    return renamedTypeNames.getOrDefault(previous, previous);
+  }
+
+  @Override
   protected FieldLookupResult internalDescribeLookupField(FieldLookupResult previous) {
     return previous;
   }
 
   @Override
+  public MethodLookupResult internalDescribeLookupMethod(
+      MethodLookupResult previous, DexMethod context) {
+    return previous;
+  }
+
+  @Override
+  protected DexMethod internalGetPreviousMethodSignature(DexMethod method) {
+    return method;
+  }
+
+  @Override
   public boolean isContextFreeForMethods() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/GraphLens.java b/src/main/java/com/android/tools/r8/graph/GraphLens.java
index 5f49c95..361ef09 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLens.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.graph;
 
+import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.horizontalclassmerging.ClassMerger;
 import com.android.tools.r8.ir.code.Invoke.Type;
 import com.android.tools.r8.ir.desugar.InterfaceProcessor.InterfaceProcessorNestedGraphLens;
@@ -42,25 +43,21 @@
  */
 public abstract class GraphLens {
 
-  /**
-   * Intermediate result of a field lookup that stores the actual non-rebound reference and the
-   * rebound reference that points to the definition of the field.
-   */
-  public static class FieldLookupResult {
+  abstract static class MemberLookupResult<R extends DexMember<?, R>> {
 
-    private final DexField reference;
-    private final DexField reboundReference;
+    private final R reference;
+    private final R reboundReference;
 
-    private FieldLookupResult(DexField reference, DexField reboundReference) {
+    private MemberLookupResult(R reference, R reboundReference) {
       this.reference = reference;
       this.reboundReference = reboundReference;
     }
 
-    public DexField getReference() {
+    public R getReference() {
       return reference;
     }
 
-    public DexField getRewrittenReference(Map<DexField, DexField> rewritings) {
+    public R getRewrittenReference(Map<R, R> rewritings) {
       return rewritings.getOrDefault(reference, reference);
     }
 
@@ -68,35 +65,57 @@
       return reboundReference != null;
     }
 
-    public DexField getReboundReference() {
+    public R getReboundReference() {
       return reboundReference;
     }
 
-    public DexField getRewrittenReboundReference(Map<DexField, DexField> rewritings) {
+    public R getRewrittenReboundReference(Map<R, R> rewritings) {
       return rewritings.getOrDefault(reboundReference, reboundReference);
     }
 
+    abstract static class Builder<R extends DexMember<?, R>, Self extends Builder<R, Self>> {
+
+      R reference;
+      R reboundReference;
+
+      public Self setReference(R reference) {
+        this.reference = reference;
+        return self();
+      }
+
+      public Self setReboundReference(R reboundReference) {
+        this.reboundReference = reboundReference;
+        return self();
+      }
+
+      public abstract Self self();
+    }
+  }
+
+  /**
+   * Intermediate result of a field lookup that stores the actual non-rebound reference and the
+   * rebound reference that points to the definition of the field.
+   */
+  public static class FieldLookupResult extends MemberLookupResult<DexField> {
+
+    private FieldLookupResult(DexField reference, DexField reboundReference) {
+      super(reference, reboundReference);
+    }
+
     public static Builder builder(GraphLens lens) {
       return new Builder(lens);
     }
 
-    public static class Builder {
+    public static class Builder extends MemberLookupResult.Builder<DexField, Builder> {
 
       private GraphLens lens;
-      private DexField reference;
-      private DexField reboundReference;
 
       private Builder(GraphLens lens) {
         this.lens = lens;
       }
 
-      public Builder setReference(DexField reference) {
-        this.reference = reference;
-        return this;
-      }
-
-      public Builder setReboundReference(DexField reboundReference) {
-        this.reboundReference = reboundReference;
+      @Override
+      public Builder self() {
         return this;
       }
 
@@ -114,21 +133,23 @@
    * prototype changes that have been made to the target method and the corresponding required
    * changes to the invoke arguments.
    */
-  public static class MethodLookupResult {
+  public static class MethodLookupResult extends MemberLookupResult<DexMethod> {
 
-    private final DexMethod method;
     private final Type type;
     private final RewrittenPrototypeDescription prototypeChanges;
 
     public MethodLookupResult(
-        DexMethod method, Type type, RewrittenPrototypeDescription prototypeChanges) {
-      this.method = method;
+        DexMethod reference,
+        DexMethod reboundReference,
+        Type type,
+        RewrittenPrototypeDescription prototypeChanges) {
+      super(reference, reboundReference);
       this.type = type;
       this.prototypeChanges = prototypeChanges;
     }
 
-    public DexMethod getReference() {
-      return method;
+    public static Builder builder(GraphLens lens) {
+      return new Builder(lens);
     }
 
     public Type getType() {
@@ -138,6 +159,38 @@
     public RewrittenPrototypeDescription getPrototypeChanges() {
       return prototypeChanges;
     }
+
+    public static class Builder extends MemberLookupResult.Builder<DexMethod, Builder> {
+
+      private final GraphLens lens;
+      private RewrittenPrototypeDescription prototypeChanges = RewrittenPrototypeDescription.none();
+      private Type type;
+
+      private Builder(GraphLens lens) {
+        this.lens = lens;
+      }
+
+      public Builder setPrototypeChanges(RewrittenPrototypeDescription prototypeChanges) {
+        this.prototypeChanges = prototypeChanges;
+        return this;
+      }
+
+      public Builder setType(Type type) {
+        this.type = type;
+        return this;
+      }
+
+      public MethodLookupResult build() {
+        assert reference != null;
+        // TODO(b/168282032): All non-identity graph lenses should set the rebound reference.
+        return new MethodLookupResult(reference, reboundReference, type, prototypeChanges);
+      }
+
+      @Override
+      public Builder self() {
+        return this;
+      }
+    }
   }
 
   public static class Builder {
@@ -268,12 +321,23 @@
   public abstract DexType lookupType(DexType type);
 
   // This overload can be used when the graph lens is known to be context insensitive.
-  public DexMethod lookupMethod(DexMethod method) {
+  public final DexMethod lookupMethod(DexMethod method) {
     assert verifyIsContextFreeForMethod(method);
     return lookupMethod(method, null, null).getReference();
   }
 
-  public abstract MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type);
+  /** Lookup a rebound or non-rebound method reference using the current graph lens. */
+  public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
+    return internalLookupMethod(method, context, type, result -> result);
+  }
+
+  protected abstract MethodLookupResult internalLookupMethod(
+      DexMethod reference, DexMethod context, Type type, LookupMethodContinuation continuation);
+
+  interface LookupMethodContinuation {
+
+    MethodLookupResult lookupMethod(MethodLookupResult previous);
+  }
 
   public abstract RewrittenPrototypeDescription lookupPrototypeChangesForMethodDefinition(
       DexMethod method);
@@ -562,16 +626,31 @@
     }
 
     @Override
-    protected final DexField internalLookupField(
+    protected DexField internalLookupField(
         DexField reference, LookupFieldContinuation continuation) {
       return previousLens.internalLookupField(
           reference, previous -> continuation.lookupField(internalDescribeLookupField(previous)));
     }
 
+    @Override
+    protected MethodLookupResult internalLookupMethod(
+        DexMethod reference, DexMethod context, Type type, LookupMethodContinuation continuation) {
+      return previousLens.internalLookupMethod(
+          reference,
+          internalGetPreviousMethodSignature(context),
+          type,
+          previous -> continuation.lookupMethod(internalDescribeLookupMethod(previous, context)));
+    }
+
     protected abstract FieldLookupResult internalDescribeLookupField(FieldLookupResult previous);
 
+    protected abstract MethodLookupResult internalDescribeLookupMethod(
+        MethodLookupResult previous, DexMethod context);
+
     protected abstract DexType internalDescribeLookupClassType(DexType previous);
 
+    protected abstract DexMethod internalGetPreviousMethodSignature(DexMethod method);
+
     @Override
     public final boolean isIdentityLens() {
       return false;
@@ -645,11 +724,6 @@
     }
 
     @Override
-    public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
-      return new MethodLookupResult(method, type, RewrittenPrototypeDescription.none());
-    }
-
-    @Override
     public RewrittenPrototypeDescription lookupPrototypeChangesForMethodDefinition(
         DexMethod method) {
       return RewrittenPrototypeDescription.none();
@@ -665,6 +739,15 @@
     }
 
     @Override
+    protected MethodLookupResult internalLookupMethod(
+        DexMethod reference, DexMethod context, Type type, LookupMethodContinuation continuation) {
+      // Passes the method reference back to the next graph lens. The identity lens intentionally
+      // does not set the rebound method reference, since it does not know what that is.
+      return continuation.lookupMethod(
+          MethodLookupResult.builder(this).setReference(reference).setType(type).build());
+    }
+
+    @Override
     public boolean isContextFreeForMethods() {
       return true;
     }
@@ -711,27 +794,45 @@
     }
 
     @Override
-    public final DexType internalDescribeLookupClassType(DexType previous) {
-      return previous;
-    }
-
-    @Override
-    public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
-      return getIdentityLens().lookupMethod(method, context, type);
-    }
-
-    @Override
     public RewrittenPrototypeDescription lookupPrototypeChangesForMethodDefinition(
         DexMethod method) {
       return getIdentityLens().lookupPrototypeChangesForMethodDefinition(method);
     }
 
     @Override
-    protected FieldLookupResult internalDescribeLookupField(FieldLookupResult previous) {
+    public final DexType internalDescribeLookupClassType(DexType previous) {
       return previous;
     }
 
     @Override
+    protected DexField internalLookupField(
+        DexField reference, LookupFieldContinuation continuation) {
+      return getIdentityLens().internalLookupField(reference, continuation);
+    }
+
+    @Override
+    protected FieldLookupResult internalDescribeLookupField(FieldLookupResult previous) {
+      throw new Unreachable();
+    }
+
+    @Override
+    protected MethodLookupResult internalLookupMethod(
+        DexMethod reference, DexMethod context, Type type, LookupMethodContinuation continuation) {
+      return getIdentityLens().internalLookupMethod(reference, context, type, continuation);
+    }
+
+    @Override
+    public MethodLookupResult internalDescribeLookupMethod(
+        MethodLookupResult previous, DexMethod context) {
+      throw new Unreachable();
+    }
+
+    @Override
+    protected DexMethod internalGetPreviousMethodSignature(DexMethod method) {
+      return method;
+    }
+
+    @Override
     public boolean isContextFreeForMethods() {
       return getIdentityLens().isContextFreeForMethods();
     }
@@ -839,23 +940,40 @@
     }
 
     @Override
-    public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
-      DexMethod previousContext = internalGetPreviousMethodSignature(context);
-      MethodLookupResult previousLookup = getPrevious().lookupMethod(method, previousContext, type);
-      return lookupMethod(method, previousLookup);
+    protected FieldLookupResult internalDescribeLookupField(FieldLookupResult previous) {
+      if (previous.hasReboundReference()) {
+        // Rewrite the rebound reference and then "fixup" the non-rebound reference.
+        DexField rewrittenReboundReference = previous.getRewrittenReboundReference(fieldMap);
+        return FieldLookupResult.builder(this)
+            .setReboundReference(rewrittenReboundReference)
+            .setReference(
+                rewrittenReboundReference.withHolder(
+                    internalDescribeLookupClassType(previous.getReference().getHolderType()),
+                    dexItemFactory))
+            .build();
+      } else {
+        // TODO(b/168282032): We should always have the rebound reference, so this should become
+        //  unreachable.
+        DexField rewrittenReference = previous.getRewrittenReference(fieldMap);
+        return FieldLookupResult.builder(this).setReference(rewrittenReference).build();
+      }
     }
 
-    protected MethodLookupResult lookupMethod(DexMethod method, MethodLookupResult previousLookup) {
-      DexMethod newMethod = methodMap.get(previousLookup.getReference());
+    @Override
+    public MethodLookupResult internalDescribeLookupMethod(
+        MethodLookupResult previous, DexMethod context) {
+      DexMethod newMethod = methodMap.get(previous.getReference());
       if (newMethod == null) {
-        return previousLookup;
+        return previous;
       }
       // TODO(sgjesse): Should we always do interface to virtual mapping? Is it a performance win
       //  that only subclasses which are known to need it actually do it?
-      return new MethodLookupResult(
-          newMethod,
-          mapInvocationType(newMethod, method, previousLookup.getType()),
-          internalDescribePrototypeChanges(previousLookup.getPrototypeChanges(), newMethod));
+      return MethodLookupResult.builder(this)
+          .setReference(newMethod)
+          .setPrototypeChanges(
+              internalDescribePrototypeChanges(previous.getPrototypeChanges(), newMethod))
+          .setType(mapInvocationType(newMethod, previous.getReference(), previous.getType()))
+          .build();
     }
 
     @Override
@@ -872,6 +990,7 @@
       return prototypeChanges;
     }
 
+    @Override
     protected DexMethod internalGetPreviousMethodSignature(DexMethod method) {
       return originalMethodSignatures != null
           ? originalMethodSignatures.getOrDefault(method, method)
@@ -927,26 +1046,6 @@
     }
 
     @Override
-    protected FieldLookupResult internalDescribeLookupField(FieldLookupResult previous) {
-      if (previous.hasReboundReference()) {
-        // Rewrite the rebound reference and then "fixup" the non-rebound reference.
-        DexField rewrittenReboundReference = previous.getRewrittenReboundReference(fieldMap);
-        return FieldLookupResult.builder(this)
-            .setReboundReference(rewrittenReboundReference)
-            .setReference(
-                rewrittenReboundReference.withHolder(
-                    internalDescribeLookupClassType(previous.getReference().getHolderType()),
-                    dexItemFactory))
-            .build();
-      } else {
-        // TODO(b/168282032): We should always have the rebound reference, so this should become
-        //  unreachable.
-        DexField rewrittenReference = previous.getRewrittenReference(fieldMap);
-        return FieldLookupResult.builder(this).setReference(rewrittenReference).build();
-      }
-    }
-
-    @Override
     public boolean isContextFreeForMethods() {
       return getPrevious().isContextFreeForMethods();
     }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
index 5cae0a2..395409f 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
@@ -10,8 +10,6 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GraphLens;
 import com.android.tools.r8.graph.GraphLens.NestedGraphLens;
-import com.android.tools.r8.graph.RewrittenPrototypeDescription;
-import com.android.tools.r8.ir.code.Invoke.Type;
 import com.android.tools.r8.ir.conversion.ExtraParameter;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
@@ -68,23 +66,18 @@
    * constructor. Otherwise return the lookup on the underlying graph lens.
    */
   @Override
-  public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
-    DexMethod previousContext = internalGetPreviousMethodSignature(context);
-    MethodLookupResult previousLookup = getPrevious().lookupMethod(method, previousContext, type);
-    List<ExtraParameter> extraParameters = methodExtraParameters.get(previousLookup.getReference());
-
-    MethodLookupResult lookup = super.lookupMethod(method, previousLookup);
-    if (extraParameters != null) {
-      DexMethod newMethod = lookup.getReference();
-
-      RewrittenPrototypeDescription prototypeChanges =
-          lookup.getPrototypeChanges().withExtraParameters(extraParameters);
-
-      return new MethodLookupResult(
-          newMethod, mapInvocationType(newMethod, method, lookup.getType()), prototypeChanges);
-    } else {
+  public MethodLookupResult internalDescribeLookupMethod(
+      MethodLookupResult previous, DexMethod context) {
+    List<ExtraParameter> extraParameters = methodExtraParameters.get(previous.getReference());
+    MethodLookupResult lookup = super.internalDescribeLookupMethod(previous, context);
+    if (extraParameters == null) {
       return lookup;
     }
+    return MethodLookupResult.builder(this)
+        .setReference(lookup.getReference())
+        .setPrototypeChanges(lookup.getPrototypeChanges().withExtraParameters(extraParameters))
+        .setType(lookup.getType())
+        .build();
   }
 
   public static class Builder {
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
index fad4980..2faa07a 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
@@ -354,14 +354,20 @@
     for (DexProgramClass clazz : appView.appInfo().classes()) {
       EnclosingMethodAttribute enclosingMethod = clazz.getEnclosingMethodAttribute();
       if (enclosingMethod != null) {
-        DexMethod mappedEnclosingMethod = lens.lookupMethod(enclosingMethod.getEnclosingMethod());
-        if (mappedEnclosingMethod != null
-            && mappedEnclosingMethod != enclosingMethod.getEnclosingMethod()) {
-          clazz.setEnclosingMethodAttribute(new EnclosingMethodAttribute(mappedEnclosingMethod));
+        if (enclosingMethod.getEnclosingMethod() != null) {
+          DexMethod mappedEnclosingMethod = lens.lookupMethod(enclosingMethod.getEnclosingMethod());
+          if (mappedEnclosingMethod != enclosingMethod.getEnclosingMethod()) {
+            clazz.setEnclosingMethodAttribute(new EnclosingMethodAttribute(mappedEnclosingMethod));
+          }
+        } else {
+          assert enclosingMethod.getEnclosingClass() != null;
+          DexType mappedEnclosingClass = lens.lookupType(enclosingMethod.getEnclosingClass());
+          if (mappedEnclosingClass != enclosingMethod.getEnclosingClass()) {
+            clazz.setEnclosingMethodAttribute(new EnclosingMethodAttribute(mappedEnclosingClass));
+          }
         }
       }
     }
-    ;
     // Return lens without method map (but still retaining originalMethodSignatures), as the
     // generated lambdas classes are generated with the an invoke to the new method, so no
     // code rewriting is required.
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/NestedPrivateMethodLens.java b/src/main/java/com/android/tools/r8/ir/desugar/NestedPrivateMethodLens.java
index 2dc813e..7bc5e6b 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/NestedPrivateMethodLens.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/NestedPrivateMethodLens.java
@@ -11,7 +11,7 @@
 import com.android.tools.r8.graph.GraphLens;
 import com.android.tools.r8.graph.GraphLens.NestedGraphLens;
 import com.android.tools.r8.graph.RewrittenPrototypeDescription;
-import com.android.tools.r8.ir.code.Invoke;
+import com.android.tools.r8.ir.code.Invoke.Type;
 import com.google.common.collect.ImmutableMap;
 import java.util.IdentityHashMap;
 import java.util.Map;
@@ -110,24 +110,28 @@
   }
 
   @Override
-  public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Invoke.Type type) {
+  public MethodLookupResult internalDescribeLookupMethod(
+      MethodLookupResult previous, DexMethod context) {
     assert originalMethodSignatures == null;
-    MethodLookupResult lookup = getPrevious().lookupMethod(method, context, type);
-    DexMethod bridge = methodMap.get(lookup.getReference());
+    DexMethod bridge = methodMap.get(previous.getReference());
     if (bridge == null) {
-      return lookup;
+      return previous;
     }
     assert context != null : "Guaranteed by isContextFreeForMethod";
     if (bridge.holder == context.holder) {
-      return lookup;
+      return previous;
     }
+    MethodLookupResult.Builder resultBuilder =
+        MethodLookupResult.builder(this).setReference(bridge);
     if (isConstructorBridge(bridge)) {
-      return new MethodLookupResult(
-          bridge,
-          Invoke.Type.DIRECT,
-          internalDescribePrototypeChanges(lookup.getPrototypeChanges(), bridge));
+      resultBuilder
+          .setPrototypeChanges(
+              internalDescribePrototypeChanges(previous.getPrototypeChanges(), bridge))
+          .setType(Type.DIRECT);
+    } else {
+      resultBuilder.setPrototypeChanges(previous.getPrototypeChanges()).setType(Type.STATIC);
     }
-    return new MethodLookupResult(bridge, Invoke.Type.STATIC, lookup.getPrototypeChanges());
+    return resultBuilder.build();
   }
 
   public static Builder builder() {
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLens.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLens.java
index 1a51e48..7838e5b 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLens.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLens.java
@@ -12,7 +12,6 @@
 import com.android.tools.r8.graph.GraphLens;
 import com.android.tools.r8.graph.GraphLens.NonIdentityGraphLens;
 import com.android.tools.r8.graph.RewrittenPrototypeDescription;
-import com.android.tools.r8.ir.code.Invoke.Type;
 import java.util.IdentityHashMap;
 import java.util.Map;
 
@@ -52,6 +51,23 @@
   }
 
   @Override
+  public MethodLookupResult internalDescribeLookupMethod(
+      MethodLookupResult previous, DexMethod context) {
+    assert previous.getReboundReference() == null;
+    return MethodLookupResult.builder(this)
+        .setReference(previous.getReference())
+        .setReboundReference(getReboundMethodReference(previous.getReference()))
+        .setPrototypeChanges(previous.getPrototypeChanges())
+        .setType(previous.getType())
+        .build();
+  }
+
+  private DexMethod getReboundMethodReference(DexMethod method) {
+    // TODO(b/168282032): Return the rebound method reference.
+    return method;
+  }
+
+  @Override
   public DexType getOriginalType(DexType type) {
     return getPrevious().getOriginalType(type);
   }
@@ -82,8 +98,8 @@
   }
 
   @Override
-  public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
-    return getPrevious().lookupMethod(method, context, type);
+  protected DexMethod internalGetPreviousMethodSignature(DexMethod method) {
+    return method;
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingLens.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingLens.java
index 2d59762..a6a6021 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingLens.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingLens.java
@@ -86,17 +86,19 @@
   }
 
   @Override
-  public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
-    MethodLookupResult lookup = getPrevious().lookupMethod(method, context, type);
-    Map<DexMethod, DexMethod> methodMap = methodMaps.getOrDefault(type, Collections.emptyMap());
-    DexMethod newMethod = methodMap.get(lookup.getReference());
+  public MethodLookupResult internalDescribeLookupMethod(
+      MethodLookupResult previous, DexMethod context) {
+    Map<DexMethod, DexMethod> methodMap =
+        methodMaps.getOrDefault(previous.getType(), Collections.emptyMap());
+    DexMethod newMethod = methodMap.get(previous.getReference());
     if (newMethod == null) {
-      return lookup;
+      return previous;
     }
-    return new MethodLookupResult(
-        newMethod,
-        mapInvocationType(newMethod, method, lookup.getType()),
-        lookup.getPrototypeChanges());
+    return MethodLookupResult.builder(this)
+        .setReference(newMethod)
+        .setPrototypeChanges(previous.getPrototypeChanges())
+        .setType(mapInvocationType(newMethod, previous.getReference(), previous.getType()))
+        .build();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/optimize/PublicizerLens.java b/src/main/java/com/android/tools/r8/optimize/PublicizerLens.java
index 78ab924..d36cbee 100644
--- a/src/main/java/com/android/tools/r8/optimize/PublicizerLens.java
+++ b/src/main/java/com/android/tools/r8/optimize/PublicizerLens.java
@@ -40,14 +40,17 @@
   }
 
   @Override
-  public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
-    MethodLookupResult lookup = getPrevious().lookupMethod(method, context, type);
-    if (lookup.getType() == Type.DIRECT && publicizedMethods.contains(lookup.getReference())) {
-      assert publicizedMethodIsPresentOnHolder(lookup.getReference(), context);
-      return new MethodLookupResult(
-          lookup.getReference(), Type.VIRTUAL, lookup.getPrototypeChanges());
+  public MethodLookupResult internalDescribeLookupMethod(
+      MethodLookupResult previous, DexMethod context) {
+    if (previous.getType() == Type.DIRECT && publicizedMethods.contains(previous.getReference())) {
+      assert publicizedMethodIsPresentOnHolder(previous.getReference(), context);
+      return MethodLookupResult.builder(this)
+          .setReference(previous.getReference())
+          .setPrototypeChanges(previous.getPrototypeChanges())
+          .setType(Type.VIRTUAL)
+          .build();
     }
-    return lookup;
+    return previous;
   }
 
   private boolean publicizedMethodIsPresentOnHolder(DexMethod method, DexMethod context) {
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index d61fbd7..953779d 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -1140,7 +1140,7 @@
         // resolve to a method on an interface never hit an implementation below that interface.
         deferredRenamings.mapVirtualMethodToDirectInType(
             oldTarget,
-            prototypeChanges -> new MethodLookupResult(newTarget, STATIC, prototypeChanges),
+            prototypeChanges -> new MethodLookupResult(newTarget, null, STATIC, prototypeChanges),
             target.type);
       } else {
         // If we merge class B into class C, and class C contains an invocation super.m(), then it
@@ -1161,7 +1161,8 @@
           if (resolutionSucceeds) {
             deferredRenamings.mapVirtualMethodToDirectInType(
                 signatureInHolder,
-                prototypeChanges -> new MethodLookupResult(newTarget, DIRECT, prototypeChanges),
+                prototypeChanges ->
+                    new MethodLookupResult(newTarget, null, DIRECT, prototypeChanges),
                 target.type);
           } else {
             break;
@@ -1185,7 +1186,8 @@
               if (resolutionSucceededBeforeMerge) {
                 deferredRenamings.mapVirtualMethodToDirectInType(
                     signatureInType,
-                    prototypeChanges -> new MethodLookupResult(newTarget, DIRECT, prototypeChanges),
+                    prototypeChanges ->
+                        new MethodLookupResult(newTarget, null, DIRECT, prototypeChanges),
                     target.type);
               }
             }
@@ -1735,6 +1737,11 @@
     }
 
     @Override
+    protected DexMethod internalGetPreviousMethodSignature(DexMethod method) {
+      throw new Unreachable();
+    }
+
+    @Override
     public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
       // First look up the method using the existing graph lens (for example, the type will have
       // changed if the method was publicized by ClassAndMemberPublicizer).
@@ -1744,16 +1751,28 @@
       if (newMethod == null) {
         return lookup;
       }
+      MethodLookupResult.Builder methodLookupResultBuilder =
+          MethodLookupResult.builder(this)
+              .setReference(newMethod)
+              .setPrototypeChanges(lookup.getPrototypeChanges())
+              .setType(lookup.getType());
       if (lookup.getType() == Type.INTERFACE) {
         // If an interface has been merged into a class, invoke-interface needs to be translated
         // to invoke-virtual.
         DexClass clazz = appInfo.definitionFor(newMethod.holder);
         if (clazz != null && !clazz.accessFlags.isInterface()) {
           assert appInfo.definitionFor(method.holder).accessFlags.isInterface();
-          return new MethodLookupResult(newMethod, Type.VIRTUAL, lookup.getPrototypeChanges());
+          methodLookupResultBuilder.setType(Type.VIRTUAL);
         }
       }
-      return new MethodLookupResult(newMethod, lookup.getType(), lookup.getPrototypeChanges());
+      return methodLookupResultBuilder.build();
+    }
+
+    @Override
+    protected MethodLookupResult internalDescribeLookupMethod(
+        MethodLookupResult previous, DexMethod context) {
+      // This is unreachable since we override the implementation of lookupMethod() above.
+      throw new Unreachable();
     }
 
     @Override
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
index 8feaefe..2848d3f 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
@@ -98,19 +98,16 @@
   }
 
   @Override
-  public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
-    assert context != null || verifyIsContextFreeForMethod(method);
-    assert context == null || type != null;
-    DexMethod previousContext =
-        originalMethodSignaturesForBridges.containsKey(context)
-            ? originalMethodSignaturesForBridges.get(context)
-            : originalMethodSignatures.getOrDefault(context, context);
-    MethodLookupResult lookup = getPrevious().lookupMethod(method, previousContext, type);
-    if (lookup.getType() == Type.SUPER && !mergedMethods.contains(context)) {
+  public MethodLookupResult internalDescribeLookupMethod(
+      MethodLookupResult previous, DexMethod context) {
+    assert context != null || verifyIsContextFreeForMethod(previous.getReference());
+    assert context == null || previous.getType() != null;
+    if (previous.getType() == Type.SUPER && !mergedMethods.contains(context)) {
       Map<DexMethod, GraphLensLookupResultProvider> virtualToDirectMethodMap =
-          contextualVirtualToDirectMethodMaps.get(context.holder);
+          contextualVirtualToDirectMethodMaps.get(context.getHolderType());
       if (virtualToDirectMethodMap != null) {
-        GraphLensLookupResultProvider result = virtualToDirectMethodMap.get(lookup.getReference());
+        GraphLensLookupResultProvider result =
+            virtualToDirectMethodMap.get(previous.getReference());
         if (result != null) {
           // If the super class A of the enclosing class B (i.e., context.holder())
           // has been merged into B during vertical class merging, and this invoke-super instruction
@@ -118,18 +115,20 @@
           // method and moved into B, so that we need to use an invoke-direct instruction instead of
           // invoke-super (or invoke-static, if the method was originally a default interface
           // method).
-          return result.get(lookup.getPrototypeChanges());
+          return result.get(previous.getPrototypeChanges());
         }
       }
     }
-    DexMethod newMethod = methodMap.get(lookup.getReference());
+    DexMethod newMethod = methodMap.get(previous.getReference());
     if (newMethod == null) {
-      return lookup;
+      return previous;
     }
-    return new MethodLookupResult(
-        newMethod,
-        mapInvocationType(newMethod, lookup.getReference(), lookup.getType()),
-        internalDescribePrototypeChanges(lookup.getPrototypeChanges(), newMethod));
+    return MethodLookupResult.builder(this)
+        .setReference(newMethod)
+        .setPrototypeChanges(
+            internalDescribePrototypeChanges(previous.getPrototypeChanges(), newMethod))
+        .setType(mapInvocationType(newMethod, previous.getReference(), previous.getType()))
+        .build();
   }
 
   @Override
@@ -200,7 +199,8 @@
               builder.getMethodSignatureAfterClassMerging(rewriting.getReference(), mergedClasses);
           newBuilder.mapVirtualMethodToDirectInType(
               from,
-              prototypeChanges -> new MethodLookupResult(to, rewriting.getType(), prototypeChanges),
+              prototypeChanges ->
+                  new MethodLookupResult(to, null, rewriting.getType(), prototypeChanges),
               context);
         }
       }