Implement lookupVirtualTarget emulating dynamic dispatch

Bug: 148271337
Bug: 149363086
Change-Id: I9a6c2d843e995486d17f9ef99586d530f8b03805
diff --git a/src/main/java/com/android/tools/r8/graph/AccessFlags.java b/src/main/java/com/android/tools/r8/graph/AccessFlags.java
index c709a31..a6a9471 100644
--- a/src/main/java/com/android/tools/r8/graph/AccessFlags.java
+++ b/src/main/java/com/android/tools/r8/graph/AccessFlags.java
@@ -150,6 +150,10 @@
     return visibilityOrdinal() == 1 || visibilityOrdinal() == 2;
   }
 
+  public boolean isPackagePrivate() {
+    return !isPublic() && !isPrivate() && !isProtected();
+  }
+
   public boolean isPublic() {
     return isSet(Constants.ACC_PUBLIC);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/ResolutionResult.java b/src/main/java/com/android/tools/r8/graph/ResolutionResult.java
index 6b091a7..76e7c9a 100644
--- a/src/main/java/com/android/tools/r8/graph/ResolutionResult.java
+++ b/src/main/java/com/android/tools/r8/graph/ResolutionResult.java
@@ -86,6 +86,9 @@
     return lookupVirtualDispatchTargets(context, appView, appView.appInfo());
   }
 
+  public abstract DexEncodedMethod lookupVirtualDispatchTarget(
+      DexProgramClass dynamicInstance, AppView<? extends AppInfoWithClassHierarchy> appView);
+
   /** Result for a resolution that succeeds with a known declaration/definition. */
   public static class SingleResolutionResult extends ResolutionResult {
     private final DexClass initialResolutionHolder;
@@ -350,16 +353,14 @@
       }
       assert resolvedMethod.isNonPrivateVirtualMethod();
       Set<DexEncodedMethod> result = Sets.newIdentityHashSet();
-      DexMethod method = resolvedMethod.method;
       instantiatedInfo.forEachInstantiatedSubType(
           resolvedHolder.type,
           subClass -> {
-            ResolutionResult targetMethods = appView.appInfo().resolveMethod(subClass, method);
-            if (!targetMethods.isSingleResolution()) {
+            DexEncodedMethod lookupTarget = lookupVirtualDispatchTarget(subClass, appView);
+            if (lookupTarget == null) {
               return;
             }
-            SingleResolutionResult resolutionResult = targetMethods.asSingleResolution();
-            addVirtualDispatchTarget(resolutionResult, result);
+            addVirtualDispatchTarget(lookupTarget, resolvedHolder.isInterface(), result);
           },
           dexCallSite -> {
             // TODO(b/148769279): We need to look at the call site to see if it overrides
@@ -369,11 +370,9 @@
     }
 
     private static void addVirtualDispatchTarget(
-        SingleResolutionResult resolutionResult,
-        Set<DexEncodedMethod> result) {
-      assert resolutionResult != null;
-      DexEncodedMethod singleTarget = resolutionResult.resolvedMethod;
-      if (resolutionResult.resolvedHolder.isInterface()) {
+        DexEncodedMethod target, boolean holderIsInterface, Set<DexEncodedMethod> result) {
+      assert !target.isPrivateMethod();
+      if (holderIsInterface) {
         // Add default interface methods to the list of targets.
         //
         // This helps to make sure we take into account synthesized lambda classes
@@ -396,21 +395,118 @@
         //     public void bar() { }
         //   }
         //
-        if (singleTarget.isDefaultMethod()) {
-          result.add(singleTarget);
+        if (target.isDefaultMethod()) {
+          result.add(target);
         }
         // Default methods are looked up when looking at a specific subtype that does not override
         // them. Otherwise, we would look up default methods that are actually never used.
         // However, we have to add bridge methods, otherwise we can remove a bridge that will be
         // used.
-        if (!singleTarget.accessFlags.isAbstract() && singleTarget.accessFlags.isBridge()) {
-          result.add(singleTarget);
+        if (!target.accessFlags.isAbstract() && target.accessFlags.isBridge()) {
+          result.add(target);
         }
       } else {
-        if (singleTarget.isNonPrivateVirtualMethod()) {
-          result.add(singleTarget);
+        result.add(target);
+      }
+    }
+
+    /**
+     * This implements the logic for the actual method selection for a virtual target, according to
+     * https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.5.invokevirtual where
+     * we have an object ref on the stack.
+     */
+    @Override
+    public DexEncodedMethod lookupVirtualDispatchTarget(
+        DexProgramClass dynamicInstance, AppView<? extends AppInfoWithClassHierarchy> appView) {
+      // TODO(b/148591377): Enable this assertion.
+      // The dynamic type cannot be an interface.
+      // assert !dynamicInstance.isInterface();
+      boolean allowPackageBlocked = resolvedMethod.accessFlags.isPackagePrivate();
+      DexClass current = dynamicInstance;
+      DexEncodedMethod overrideTarget = resolvedMethod;
+      do {
+        DexEncodedMethod candidate = lookupOverrideCandidate(overrideTarget, current);
+        if (candidate == DexEncodedMethod.SENTINEL && allowPackageBlocked) {
+          overrideTarget = findWideningOverride(resolvedMethod, current, appView);
+          allowPackageBlocked = false;
+          continue;
+        }
+        if (candidate == null || candidate == DexEncodedMethod.SENTINEL) {
+          current = current.superType == null ? null : appView.definitionFor(current.superType);
+          continue;
+        }
+        return candidate;
+      } while (current != null && current.type != overrideTarget.method.holder);
+      assert resolvedHolder.isInterface();
+      return lookupMaximallySpecificDispatchTarget(dynamicInstance, appView);
+    }
+
+    private DexEncodedMethod lookupMaximallySpecificDispatchTarget(
+        DexProgramClass dynamicInstance, AppView<? extends AppInfoWithClassHierarchy> appView) {
+      ResolutionResult maximallySpecificResult =
+          appView.appInfo().resolveMaximallySpecificMethods(dynamicInstance, resolvedMethod.method);
+      if (maximallySpecificResult.isSingleResolution()) {
+        return maximallySpecificResult.asSingleResolution().resolvedMethod;
+      }
+      return null;
+    }
+
+    /**
+     * C contains a declaration for an instance method m that overrides (§5.4.5) the resolved
+     * method, then m is the method to be invoked. If the candidate is not a valid override, we
+     * return sentinel to indicate that we have to search for a method that is widening access
+     * inside the package.
+     */
+    private static DexEncodedMethod lookupOverrideCandidate(
+        DexEncodedMethod method, DexClass clazz) {
+      DexEncodedMethod candidate = clazz.lookupVirtualMethod(method.method);
+      assert candidate == null || !candidate.isPrivateMethod();
+      if (candidate != null) {
+        return isOverriding(method, candidate) ? candidate : DexEncodedMethod.SENTINEL;
+      }
+      return null;
+    }
+
+    private static DexEncodedMethod findWideningOverride(
+        DexEncodedMethod resolvedMethod,
+        DexClass clazz,
+        AppView<? extends AppInfoWithClassHierarchy> appView) {
+      // Otherwise, lookup to first override that is distinct from resolvedMethod.
+      assert resolvedMethod.accessFlags.isPackagePrivate();
+      while (clazz.superType != null) {
+        clazz = appView.definitionFor(clazz.superType);
+        if (clazz == null) {
+          return resolvedMethod;
+        }
+        DexEncodedMethod otherOverride = clazz.lookupVirtualMethod(resolvedMethod.method);
+        if (otherOverride != null
+            && isOverriding(resolvedMethod, otherOverride)
+            && (otherOverride.accessFlags.isPublic() || otherOverride.accessFlags.isProtected())) {
+          assert resolvedMethod != otherOverride;
+          return otherOverride;
         }
       }
+      return resolvedMethod;
+    }
+
+    /**
+     * Implementation of method overriding according to the jvm specification
+     * https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.5
+     *
+     * <p>The implementation assumes that the holder of the candidate is a subtype of the holder of
+     * the resolved method. It also assumes that resolvedMethod is the actual method to find a
+     * lookup for (that is, it is either mA or m').
+     */
+    private static boolean isOverriding(
+        DexEncodedMethod resolvedMethod, DexEncodedMethod candidate) {
+      assert resolvedMethod.method.match(candidate.method);
+      assert !candidate.isPrivateMethod();
+      if (resolvedMethod.accessFlags.isPublic() || resolvedMethod.accessFlags.isProtected()) {
+        return true;
+      }
+      // For package private methods, a valid override has to be inside the package.
+      assert resolvedMethod.accessFlags.isPackagePrivate();
+      return resolvedMethod.method.holder.isSamePackage(candidate.method.holder);
     }
   }
 
@@ -447,6 +543,12 @@
         InstantiatedSubTypeInfo instantiatedInfo) {
       return LookupResult.getIncompleteEmptyResult();
     }
+
+    @Override
+    public DexEncodedMethod lookupVirtualDispatchTarget(
+        DexProgramClass dynamicInstance, AppView<? extends AppInfoWithClassHierarchy> appView) {
+      return null;
+    }
   }
 
   /** Singleton result for the special case resolving the array clone() method. */
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java
index ea0ea32..4c3085e 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreLookupTest.java
@@ -79,17 +79,16 @@
             .lookupVirtualDispatchTargets(clazz, appView, appInfo);
     assertTrue(lookupResult.isLookupResultSuccess());
     Set<DexEncodedMethod> targets = lookupResult.asLookupResultSuccess().getMethodTargets();
-    // TODO(b/148591377): Temporarily disable.
-    // if (appInfo.subtypes(method.method.holder).stream()
-    //     .allMatch(t -> appInfo.definitionFor(t).isInterface())) {
-    //   assertEquals(
-    //       0,
-    //       targets.stream()
-    //           .filter(m -> m.accessFlags.isAbstract() || !m.accessFlags.isBridge())
-    //           .count());
-    // } else {
-    //   assertEquals(0, targets.stream().filter(m -> m.accessFlags.isAbstract()).count());
-    // }
+    if (appInfo.subtypes(method.method.holder).stream()
+        .allMatch(t -> appInfo.definitionFor(t).isInterface())) {
+      assertEquals(
+          0,
+          targets.stream()
+              .filter(m -> m.accessFlags.isAbstract() || !m.accessFlags.isBridge())
+              .count());
+    } else {
+      assertEquals(0, targets.stream().filter(m -> m.accessFlags.isAbstract()).count());
+    }
   }
 
   private void testLookup(DexProgramClass clazz) {
diff --git a/src/test/java/com/android/tools/r8/resolution/packageprivate/NonAbstractWidening.java b/src/test/java/com/android/tools/r8/resolution/packageprivate/NonAbstractWidening.java
new file mode 100644
index 0000000..f9d75e4
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/packageprivate/NonAbstractWidening.java
@@ -0,0 +1,16 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.resolution.packageprivate;
+
+import com.android.tools.r8.resolution.packageprivate.a.AbstractWidening;
+import com.android.tools.r8.resolution.packageprivate.a.I;
+
+public class NonAbstractWidening extends AbstractWidening implements I {
+
+  @Override
+  public void foo() {
+    System.out.println("Method declaration will be removed");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateReentryTest.java b/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateReentryTest.java
index d574917..eb08197 100644
--- a/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateReentryTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateReentryTest.java
@@ -65,12 +65,10 @@
         lookupResult.asLookupResultSuccess().getMethodTargets().stream()
             .map(DexEncodedMethod::qualifiedName)
             .collect(Collectors.toSet());
-    // TODO(b/149363086): Fix expection, should not include C.bar().
     ImmutableSet<String> expected =
         ImmutableSet.of(
             A.class.getTypeName() + ".bar",
             B.class.getTypeName() + ".bar",
-            C.class.getTypeName() + ".bar",
             D.class.getTypeName() + ".bar");
     assertEquals(expected, targets);
   }
diff --git a/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateReentryWithNarrowingTest.java b/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateReentryWithNarrowingTest.java
index 068e45d..619ee45 100644
--- a/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateReentryWithNarrowingTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateReentryWithNarrowingTest.java
@@ -69,12 +69,10 @@
         lookupResult.asLookupResultSuccess().getMethodTargets().stream()
             .map(DexEncodedMethod::qualifiedName)
             .collect(Collectors.toSet());
-    // TODO(b/149363086): Fix expection, should not include C.bar().
     ImmutableSet<String> expected =
         ImmutableSet.of(
             A.class.getTypeName() + ".bar",
             B.class.getTypeName() + ".bar",
-            C.class.getTypeName() + ".bar",
             D.class.getTypeName() + ".bar");
     assertEquals(expected, targets);
   }
diff --git a/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateWithDefaultMethod2Test.java b/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateWithDefaultMethod2Test.java
new file mode 100644
index 0000000..cc85b0d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/packageprivate/PackagePrivateWithDefaultMethod2Test.java
@@ -0,0 +1,166 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.resolution.packageprivate;
+
+import static org.hamcrest.CoreMatchers.containsString;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeTrue;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.R8TestRunResult;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.TestRunResult;
+import com.android.tools.r8.ToolHelper.DexVm;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.LookupResult;
+import com.android.tools.r8.graph.ResolutionResult;
+import com.android.tools.r8.resolution.packageprivate.a.Abstract;
+import com.android.tools.r8.resolution.packageprivate.a.AbstractWidening;
+import com.android.tools.r8.resolution.packageprivate.a.I;
+import com.android.tools.r8.resolution.packageprivate.a.J;
+import com.android.tools.r8.resolution.packageprivate.a.NonAbstractWideningExtendingA;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.transformers.ClassTransformer;
+import com.google.common.collect.ImmutableSet;
+import java.io.IOException;
+import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import java.util.stream.Collectors;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+import org.objectweb.asm.MethodVisitor;
+
+@RunWith(Parameterized.class)
+public class PackagePrivateWithDefaultMethod2Test extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public PackagePrivateWithDefaultMethod2Test(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testResolution() throws Exception {
+    assumeTrue(parameters.useRuntimeAsNoneRuntime());
+    AppView<AppInfoWithLiveness> appView =
+        computeAppViewWithLiveness(
+            buildClasses(
+                    Abstract.class,
+                    AbstractWidening.class,
+                    I.class,
+                    A.class,
+                    NonAbstractWideningExtendingA.class,
+                    J.class,
+                    Main.class)
+                .addClassProgramData(getNonAbstractWithoutDeclaredMethods())
+                .build(),
+            Main.class);
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    DexMethod method = buildNullaryVoidMethod(A.class, "foo", appInfo.dexItemFactory());
+    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
+    DexProgramClass context =
+        appView.definitionForProgramType(buildType(A.class, appInfo.dexItemFactory()));
+    LookupResult lookupResult = resolutionResult.lookupVirtualDispatchTargets(context, appView);
+    assertTrue(lookupResult.isLookupResultSuccess());
+    Set<String> targets =
+        lookupResult.asLookupResultSuccess().getMethodTargets().stream()
+            .map(DexEncodedMethod::qualifiedName)
+            .collect(Collectors.toSet());
+    // TODO(b/148591377): The set should be empty.
+    ImmutableSet<String> expected = ImmutableSet.of(AbstractWidening.class.getTypeName() + ".foo");
+    assertEquals(expected, targets);
+  }
+
+  @Test
+  public void testRuntime() throws ExecutionException, CompilationFailedException, IOException {
+    TestRunResult<?> runResult =
+        testForRuntime(parameters)
+            .addProgramClasses(
+                Abstract.class,
+                AbstractWidening.class,
+                I.class,
+                A.class,
+                NonAbstractWideningExtendingA.class,
+                J.class,
+                Main.class)
+            .addProgramClassFileData(getNonAbstractWithoutDeclaredMethods())
+            .run(parameters.getRuntime(), Main.class);
+    if (parameters.isDexRuntime()
+        && parameters.getRuntime().asDex().getVm().isOlderThanOrEqual(DexVm.ART_4_4_4_TARGET)) {
+      runResult.assertFailure();
+    } else {
+      runResult.assertFailureWithErrorThatMatches(containsString("AbstractMethodError"));
+    }
+  }
+
+  @Test
+  public void testR8() throws ExecutionException, CompilationFailedException, IOException {
+    R8TestRunResult runResult =
+        testForR8(parameters.getBackend())
+            .addProgramClasses(
+                Abstract.class,
+                AbstractWidening.class,
+                I.class,
+                A.class,
+                NonAbstractWideningExtendingA.class,
+                J.class,
+                Main.class)
+            .addProgramClassFileData(getNonAbstractWithoutDeclaredMethods())
+            .setMinApi(parameters.getApiLevel())
+            .addKeepMainRule(Main.class)
+            .run(parameters.getRuntime(), Main.class)
+            .disassemble();
+    if (parameters.isDexRuntime()
+        && parameters.getRuntime().asDex().getVm().isOlderThanOrEqual(DexVm.ART_4_4_4_TARGET)) {
+      runResult.assertFailure();
+    } else {
+      runResult.assertFailureWithErrorThatMatches(containsString("AbstractMethodError"));
+    }
+  }
+
+  private byte[] getNonAbstractWithoutDeclaredMethods() throws IOException {
+    return transformer(NonAbstractWidening.class)
+        .addClassTransformer(
+            new ClassTransformer() {
+              @Override
+              public MethodVisitor visitMethod(
+                  int access,
+                  String name,
+                  String descriptor,
+                  String signature,
+                  String[] exceptions) {
+                if (!name.equals("foo")) {
+                  return super.visitMethod(access, name, descriptor, signature, exceptions);
+                }
+                return null;
+              }
+            })
+        .transform();
+  }
+
+  public static class A extends NonAbstractWidening {}
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      NonAbstractWideningExtendingA d = new NonAbstractWideningExtendingA();
+      Abstract.run(d);
+      d.foo();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/packageprivate/WidenAccessOutsidePackageTest.java b/src/test/java/com/android/tools/r8/resolution/packageprivate/WidenAccessOutsidePackageTest.java
index 84d66d8..b761626 100644
--- a/src/test/java/com/android/tools/r8/resolution/packageprivate/WidenAccessOutsidePackageTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/packageprivate/WidenAccessOutsidePackageTest.java
@@ -64,12 +64,8 @@
         lookupResult.asLookupResultSuccess().getMethodTargets().stream()
             .map(DexEncodedMethod::qualifiedName)
             .collect(Collectors.toSet());
-    // TODO(b/149363086): Fix expectation.
     ImmutableSet<String> expected =
-        ImmutableSet.of(
-            A.class.getTypeName() + ".bar",
-            B.class.getTypeName() + ".bar",
-            C.class.getTypeName() + ".bar");
+        ImmutableSet.of(A.class.getTypeName() + ".bar", B.class.getTypeName() + ".bar");
     assertEquals(expected, targets);
   }
 
diff --git a/src/test/java/com/android/tools/r8/resolution/packageprivate/a/AbstractWidening.java b/src/test/java/com/android/tools/r8/resolution/packageprivate/a/AbstractWidening.java
new file mode 100644
index 0000000..472a97b
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/packageprivate/a/AbstractWidening.java
@@ -0,0 +1,11 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.resolution.packageprivate.a;
+
+public abstract class AbstractWidening extends Abstract {
+
+  @Override
+  public abstract void foo();
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/packageprivate/a/NonAbstractWideningExtendingA.java b/src/test/java/com/android/tools/r8/resolution/packageprivate/a/NonAbstractWideningExtendingA.java
new file mode 100644
index 0000000..ec0bd6a
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/packageprivate/a/NonAbstractWideningExtendingA.java
@@ -0,0 +1,10 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.resolution.packageprivate.a;
+
+import com.android.tools.r8.resolution.packageprivate.PackagePrivateWithDefaultMethod2Test;
+
+public class NonAbstractWideningExtendingA extends PackagePrivateWithDefaultMethod2Test.A
+    implements J {}
diff --git a/src/test/java/com/android/tools/r8/resolution/virtualtargets/PackagePrivateChainTest.java b/src/test/java/com/android/tools/r8/resolution/virtualtargets/PackagePrivateChainTest.java
index 45c208a..37c071a 100644
--- a/src/test/java/com/android/tools/r8/resolution/virtualtargets/PackagePrivateChainTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/virtualtargets/PackagePrivateChainTest.java
@@ -5,6 +5,9 @@
 package com.android.tools.r8.resolution.virtualtargets;
 
 import static org.hamcrest.CoreMatchers.containsString;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeTrue;
 
 import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.TestBase;
@@ -12,11 +15,21 @@
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.TestRunResult;
 import com.android.tools.r8.ToolHelper.DexVm;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.LookupResult;
+import com.android.tools.r8.graph.ResolutionResult;
 import com.android.tools.r8.resolution.virtualtargets.package_a.Middle;
 import com.android.tools.r8.resolution.virtualtargets.package_a.Top;
 import com.android.tools.r8.resolution.virtualtargets.package_a.TopRunner;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.google.common.collect.ImmutableSet;
 import java.io.IOException;
+import java.util.Set;
 import java.util.concurrent.ExecutionException;
+import java.util.stream.Collectors;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -39,6 +52,30 @@
   }
 
   @Test
+  public void testResolution() throws Exception {
+    assumeTrue(parameters.useRuntimeAsNoneRuntime());
+    AppView<AppInfoWithLiveness> appView =
+        computeAppViewWithLiveness(
+            buildClasses(Top.class, Middle.class, Bottom.class, TopRunner.class, Main.class)
+                .build(),
+            Main.class);
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    DexMethod method = buildNullaryVoidMethod(Top.class, "clear", appInfo.dexItemFactory());
+    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
+    DexProgramClass context =
+        appView.definitionForProgramType(buildType(TopRunner.class, appInfo.dexItemFactory()));
+    LookupResult lookupResult = resolutionResult.lookupVirtualDispatchTargets(context, appView);
+    assertTrue(lookupResult.isLookupResultSuccess());
+    Set<String> targets =
+        lookupResult.asLookupResultSuccess().getMethodTargets().stream()
+            .map(DexEncodedMethod::qualifiedName)
+            .collect(Collectors.toSet());
+    ImmutableSet<String> expected =
+        ImmutableSet.of(Top.class.getTypeName() + ".clear", Middle.class.getTypeName() + ".clear");
+    assertEquals(expected, targets);
+  }
+
+  @Test
   public void testRuntime() throws ExecutionException, CompilationFailedException, IOException {
     TestRunResult<?> runResult =
         testForRuntime(parameters.getRuntime(), parameters.getApiLevel())
@@ -60,7 +97,7 @@
         .addKeepMainRule(Main.class)
         .setMinApi(parameters.getApiLevel())
         .run(parameters.getRuntime(), Main.class)
-        .assertSuccessWithOutputLines("Bottom.clear()", "Bottom.clear()");
+        .assertFailureWithErrorThatMatches(containsString("AbstractMethodError"));
   }
 
   public static class Bottom extends Middle {
diff --git a/src/test/java/com/android/tools/r8/resolution/virtualtargets/PackagePrivateFinalOverrideTest.java b/src/test/java/com/android/tools/r8/resolution/virtualtargets/PackagePrivateFinalOverrideTest.java
index 98499a2..dfc9d43 100644
--- a/src/test/java/com/android/tools/r8/resolution/virtualtargets/PackagePrivateFinalOverrideTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/virtualtargets/PackagePrivateFinalOverrideTest.java
@@ -5,22 +5,34 @@
 package com.android.tools.r8.resolution.virtualtargets;
 
 import static org.hamcrest.CoreMatchers.containsString;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeTrue;
 
 import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
-import com.android.tools.r8.R8TestRunResult;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.TestRunResult;
 import com.android.tools.r8.ToolHelper.DexVm;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.LookupResult;
+import com.android.tools.r8.graph.ResolutionResult;
 import com.android.tools.r8.resolution.virtualtargets.package_a.ViewModel;
 import com.android.tools.r8.resolution.virtualtargets.package_a.ViewModelRunner;
 import com.android.tools.r8.resolution.virtualtargets.package_a.ViewModelRunnerWithCast;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.DescriptorUtils;
+import com.google.common.collect.ImmutableSet;
 import java.io.IOException;
+import java.util.Set;
 import java.util.concurrent.ExecutionException;
+import java.util.stream.Collectors;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -32,6 +44,9 @@
   private static final String[] EXPECTED =
       new String[] {"ViewModel.clear()", "MyViewModel.clear()", "ViewModel.clear()"};
 
+  private static final String[] R8_OUTPUT =
+      new String[] {"MyViewModel.clear()", "MyViewModel.clear()", "MyViewModel.clear()"};
+
   private final TestParameters parameters;
 
   @Parameters(name = "{0}")
@@ -44,6 +59,30 @@
   }
 
   @Test
+  public void testResolution() throws Exception {
+    assumeTrue(parameters.useRuntimeAsNoneRuntime());
+    AppView<AppInfoWithLiveness> appView =
+        computeAppViewWithLiveness(
+            buildClasses(MyViewModel.class, ViewModel.class, Main.class, ViewModelRunner.class)
+                .build(),
+            Main.class);
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    DexMethod method = buildNullaryVoidMethod(ViewModel.class, "clear", appInfo.dexItemFactory());
+    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
+    DexProgramClass context =
+        appView.definitionForProgramType(
+            buildType(ViewModelRunner.class, appInfo.dexItemFactory()));
+    LookupResult lookupResult = resolutionResult.lookupVirtualDispatchTargets(context, appView);
+    assertTrue(lookupResult.isLookupResultSuccess());
+    Set<String> targets =
+        lookupResult.asLookupResultSuccess().getMethodTargets().stream()
+            .map(DexEncodedMethod::qualifiedName)
+            .collect(Collectors.toSet());
+    ImmutableSet<String> expected = ImmutableSet.of(ViewModel.class.getTypeName() + ".clear");
+    assertEquals(expected, targets);
+  }
+
+  @Test
   public void testRuntime() throws ExecutionException, CompilationFailedException, IOException {
     TestRunResult<?> runResult =
         testForRuntime(parameters.getRuntime(), parameters.getApiLevel())
@@ -60,19 +99,30 @@
 
   @Test
   public void testR8() throws ExecutionException, CompilationFailedException, IOException {
-    R8TestRunResult runResult =
-        testForR8(parameters.getBackend())
-            .addProgramClasses(
-                MyViewModel.class, Main.class, ViewModel.class, ViewModelRunner.class)
-            .addKeepMainRule(Main.class)
-            .setMinApi(parameters.getApiLevel())
-            .run(parameters.getRuntime(), Main.class);
-    if (parameters.isDexRuntime()
-        && parameters.getRuntime().asDex().getVm().isOlderThanOrEqual(DexVm.ART_4_4_4_TARGET)) {
-      runResult.assertFailureWithErrorThatMatches(containsString("overrides final"));
-    } else {
-      runResult.assertFailureWithErrorThatMatches(containsString("java.lang.NullPointerException"));
-    }
+    // TODO(b/148429150): Fix R8 to output expected.
+    testForR8(parameters.getBackend())
+        .addProgramClasses(MyViewModel.class, Main.class, ViewModel.class, ViewModelRunner.class)
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(R8_OUTPUT);
+  }
+
+  @Test
+  public void testResolutionWithInvalidInvoke() throws Exception {
+    assumeTrue(parameters.useRuntimeAsNoneRuntime());
+    AppView<AppInfoWithLiveness> appView =
+        computeAppViewWithLiveness(
+            buildClasses(MyViewModel.class, ViewModel.class, Main.class, ViewModelRunner.class)
+                .build(),
+            Main.class);
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    DexMethod method = buildNullaryVoidMethod(ViewModel.class, "clear", appInfo.dexItemFactory());
+    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
+    DexProgramClass context =
+        appView.definitionForProgramType(buildType(Main.class, appInfo.dexItemFactory()));
+    LookupResult lookupResult = resolutionResult.lookupVirtualDispatchTargets(context, appView);
+    assertTrue(lookupResult.isLookupResultFailure());
   }
 
   @Test
@@ -94,20 +144,39 @@
   @Test
   public void testR8WithInvalidInvoke()
       throws ExecutionException, CompilationFailedException, IOException {
-    R8TestRunResult runResult =
-        testForR8(parameters.getBackend())
-            .addProgramClasses(MyViewModel.class, ViewModel.class, ViewModelRunner.class)
-            .addProgramClassFileData(getModifiedMainWithIllegalInvokeToViewModelClear())
-            .addKeepMainRule(Main.class)
-            .setMinApi(parameters.getApiLevel())
-            .run(parameters.getRuntime(), Main.class);
-    if (parameters.isDexRuntime()
-        && parameters.getRuntime().asDex().getVm().isOlderThanOrEqual(DexVm.ART_4_4_4_TARGET)) {
-      runResult.assertFailureWithErrorThatMatches(containsString("overrides final"));
-    } else {
-      // TODO(b/149363086): Ensure the error is similar to runtime for package override.
-      runResult.assertFailure();
-    }
+    // TODO(b/148429150): Fix R8 to output expected.
+    testForR8(parameters.getBackend())
+        .addProgramClasses(MyViewModel.class, ViewModel.class, ViewModelRunner.class)
+        .addProgramClassFileData(getModifiedMainWithIllegalInvokeToViewModelClear())
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), Main.class)
+        .assertFailureWithErrorThatMatches(containsString("java.lang.NullPointerException"));
+  }
+
+  @Test
+  public void testResolutionWithAmbiguousInvoke() throws Exception {
+    assumeTrue(parameters.useRuntimeAsNoneRuntime());
+    AppView<AppInfoWithLiveness> appView =
+        computeAppViewWithLiveness(
+            buildClasses(
+                    MyViewModel.class, ViewModel.class, Main.class, ViewModelRunnerWithCast.class)
+                .build(),
+            Main.class);
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    DexMethod method = buildNullaryVoidMethod(ViewModel.class, "clear", appInfo.dexItemFactory());
+    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
+    DexProgramClass context =
+        appView.definitionForProgramType(
+            buildType(ViewModelRunnerWithCast.class, appInfo.dexItemFactory()));
+    LookupResult lookupResult = resolutionResult.lookupVirtualDispatchTargets(context, appView);
+    assertTrue(lookupResult.isLookupResultSuccess());
+    Set<String> targets =
+        lookupResult.asLookupResultSuccess().getMethodTargets().stream()
+            .map(DexEncodedMethod::qualifiedName)
+            .collect(Collectors.toSet());
+    ImmutableSet<String> expected = ImmutableSet.of(ViewModel.class.getTypeName() + ".clear");
+    assertEquals(expected, targets);
   }
 
   @Test
@@ -130,19 +199,14 @@
   @Test
   public void testR8WithAmbiguousInvoke()
       throws ExecutionException, CompilationFailedException, IOException {
-    R8TestRunResult runResult =
-        testForR8(parameters.getBackend())
-            .addProgramClasses(MyViewModel.class, ViewModel.class, Main.class)
-            .addProgramClassFileData(getModifiedViewModelRunnerWithDirectMyViewModelTarget())
-            .addKeepMainRule(Main.class)
-            .setMinApi(parameters.getApiLevel())
-            .run(parameters.getRuntime(), Main.class);
-    if (parameters.isDexRuntime()
-        && parameters.getRuntime().asDex().getVm().isOlderThanOrEqual(DexVm.ART_4_4_4_TARGET)) {
-      runResult.assertFailureWithErrorThatMatches(containsString("overrides final"));
-    } else {
-      runResult.assertFailureWithErrorThatMatches(containsString("java.lang.NullPointerException"));
-    }
+    // TODO(b/148429150): Fix R8 to output expected.
+    testForR8(parameters.getBackend())
+        .addProgramClasses(MyViewModel.class, ViewModel.class, Main.class)
+        .addProgramClassFileData(getModifiedViewModelRunnerWithDirectMyViewModelTarget())
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(R8_OUTPUT);
   }
 
   private byte[] getModifiedMainWithIllegalInvokeToViewModelClear() throws IOException {
diff --git a/src/test/java/com/android/tools/r8/resolution/virtualtargets/PrivateOverrideOfVirtualTargetTest.java b/src/test/java/com/android/tools/r8/resolution/virtualtargets/PrivateOverrideOfVirtualTargetTest.java
new file mode 100644
index 0000000..915cd21
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/virtualtargets/PrivateOverrideOfVirtualTargetTest.java
@@ -0,0 +1,149 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.resolution.virtualtargets;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeTrue;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.LookupResult;
+import com.android.tools.r8.graph.ResolutionResult;
+import com.android.tools.r8.resolution.virtualtargets.package_a.A;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.Box;
+import com.android.tools.r8.utils.DescriptorUtils;
+import com.google.common.collect.ImmutableSet;
+import java.io.IOException;
+import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import java.util.stream.Collectors;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+import org.objectweb.asm.Opcodes;
+
+@RunWith(Parameterized.class)
+public class PrivateOverrideOfVirtualTargetTest extends TestBase {
+
+  private final TestParameters parameters;
+  private static final String[] EXPECTED =
+      new String[] {"A.foo", "A.bar", "B.foo", "A.bar", "B.bar"};
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public PrivateOverrideOfVirtualTargetTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testResolution() throws Exception {
+    assumeTrue(parameters.useRuntimeAsNoneRuntime());
+    AppView<AppInfoWithLiveness> appView =
+        computeAppViewWithLiveness(
+            buildClasses(A.class, Main.class)
+                .addClassProgramData(getBWithModifiedInvokes())
+                .build(),
+            DefaultWithoutTopTest.Main.class);
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    DexMethod method = buildNullaryVoidMethod(A.class, "bar", appInfo.dexItemFactory());
+    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
+    DexProgramClass context =
+        appView.definitionForProgramType(buildType(B.class, appInfo.dexItemFactory()));
+    LookupResult lookupResult = resolutionResult.lookupVirtualDispatchTargets(context, appView);
+    assertTrue(lookupResult.isLookupResultSuccess());
+    Set<String> targets =
+        lookupResult.asLookupResultSuccess().getMethodTargets().stream()
+            .map(DexEncodedMethod::qualifiedName)
+            .collect(Collectors.toSet());
+    ImmutableSet<String> expected = ImmutableSet.of(A.class.getTypeName() + ".bar");
+    assertEquals(expected, targets);
+  }
+
+  @Test
+  public void testRuntime()
+      throws NoSuchMethodException, IOException, CompilationFailedException, ExecutionException {
+    testForRuntime(parameters)
+        .addProgramClasses(A.class, Main.class)
+        .addProgramClassFileData(getBWithModifiedInvokes())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(EXPECTED);
+  }
+
+  @Test
+  public void testR8()
+      throws NoSuchMethodException, IOException, CompilationFailedException, ExecutionException {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(A.class, Main.class)
+        .addProgramClassFileData(getBWithModifiedInvokes())
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(Main.class)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(EXPECTED);
+  }
+
+  private byte[] getBWithModifiedInvokes() throws NoSuchMethodException, IOException {
+    Box<Boolean> modifyOwner = new Box<>(true);
+    return transformer(B.class)
+        .setPrivate(B.class.getDeclaredMethod("bar"))
+        .transformMethodInsnInMethod(
+            "callOnB",
+            (opcode, owner, name, descriptor, isInterface, continuation) -> {
+              if (name.equals("foo")) {
+                continuation.apply(opcode, owner, name, descriptor, isInterface);
+                return;
+              }
+              if (modifyOwner.get()) {
+                continuation.apply(
+                    Opcodes.INVOKEVIRTUAL,
+                    DescriptorUtils.getBinaryNameFromJavaType(A.class.getTypeName()),
+                    name,
+                    descriptor,
+                    isInterface);
+                modifyOwner.set(false);
+              } else {
+                continuation.apply(Opcodes.INVOKEVIRTUAL, owner, name, descriptor, isInterface);
+              }
+            })
+        .transform();
+  }
+
+  public static class B extends A {
+    private void foo() {
+      System.out.println("B.foo");
+    }
+
+    @Override
+    protected /* private */ void bar() {
+      System.out.println("B.bar");
+    }
+
+    void callOnB() {
+      foo();
+      bar(); /* will become A.bar() */
+      bar(); /* will become B.bar() */
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      B b = new B();
+      A.run(b);
+      b.callOnB();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/virtualtargets/package_a/A.java b/src/test/java/com/android/tools/r8/resolution/virtualtargets/package_a/A.java
new file mode 100644
index 0000000..1b311d5
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/virtualtargets/package_a/A.java
@@ -0,0 +1,21 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.resolution.virtualtargets.package_a;
+
+public class A {
+
+  void foo() {
+    System.out.println("A.foo");
+  }
+
+  protected void bar() {
+    System.out.println("A.bar");
+  }
+
+  public static void run(A a) {
+    a.foo();
+    a.bar();
+  }
+}