diff --git a/src/main/java/com/android/tools/r8/graph/DexTypeList.java b/src/main/java/com/android/tools/r8/graph/DexTypeList.java
index 8df5030..45a1548 100644
--- a/src/main/java/com/android/tools/r8/graph/DexTypeList.java
+++ b/src/main/java/com/android/tools/r8/graph/DexTypeList.java
@@ -66,8 +66,11 @@
   @Override
   public String toString() {
     StringBuilder builder = new StringBuilder();
-    for (DexType type : values) {
-      builder.append(' ').append(type);
+    if (values.length > 0) {
+      builder.append(values[0]);
+      for (int i = 1; i < values.length; i++) {
+        builder.append(' ').append(values[i]);
+      }
     }
     return builder.toString();
   }
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardClassSpecification.java b/src/main/java/com/android/tools/r8/shaking/ProguardClassSpecification.java
index 2aff5df..1d970a3 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardClassSpecification.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardClassSpecification.java
@@ -230,6 +230,10 @@
     return inheritanceIsExtends;
   }
 
+  public boolean getInheritanceIsImplements() {
+    return !inheritanceIsExtends;
+  }
+
   public boolean hasInheritanceClassName() {
     return inheritanceClassName != null;
   }
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
index e117462..432ae10 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -47,7 +47,6 @@
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Future;
-import java.util.function.Function;
 import java.util.function.Predicate;
 import java.util.stream.Collectors;
 
@@ -80,7 +79,7 @@
   public RootSetBuilder(
       AppView<? extends AppInfo> appView,
       DexApplication application,
-      List<ProguardConfigurationRule> rules,
+      Collection<? extends ProguardConfigurationRule> rules,
       InternalOptions options) {
     this.appView = appView;
     this.application = application.asDirect();
@@ -89,64 +88,10 @@
   }
 
   RootSetBuilder(
-      AppView<? extends AppInfo> appView, Set<ProguardIfRule> ifRules, InternalOptions options) {
-    this.appView = appView;
-    this.application = appView.appInfo().app.asDirect();
-    this.rules = Collections.unmodifiableCollection(ifRules);
-    this.options = options;
-  }
-
-  private boolean anySuperTypeMatches(
-      DexType type,
-      Function<DexType, DexClass> definitionFor,
-      ProguardTypeMatcher name,
-      ProguardTypeMatcher annotation) {
-    while (type != null) {
-      DexClass clazz = definitionFor.apply(type);
-      if (clazz == null) {
-        // TODO(herhut): Warn about broken supertype chain?
-        return false;
-      }
-      // TODO(b/110141157): Should the vertical class merger move annotations from the source to
-      // the target class? If so, it is sufficient only to apply the annotation-matcher to the
-      // annotations of `class`.
-      if (name.matches(clazz.type, appView) && containsAnnotation(annotation, clazz.annotations)) {
-        return true;
-      }
-      type = clazz.superType;
-    }
-    return false;
-  }
-
-  private boolean anyImplementedInterfaceMatches(
-      DexClass clazz,
-      Function<DexType, DexClass> definitionFor,
-      ProguardTypeMatcher className,
-      ProguardTypeMatcher annotation) {
-    if (clazz == null) {
-      return false;
-    }
-    for (DexType iface : clazz.interfaces.values) {
-      DexClass ifaceClass = definitionFor.apply(iface);
-      if (ifaceClass == null) {
-        // TODO(herhut): Warn about broken supertype chain?
-        return false;
-      }
-      // TODO(herhut): Maybe it would be better to do this breadth first.
-      if ((className.matches(iface) && containsAnnotation(annotation, ifaceClass.annotations))
-          || anyImplementedInterfaceMatches(ifaceClass, definitionFor, className, annotation)) {
-        return true;
-      }
-    }
-    if (clazz.superType == null) {
-      return false;
-    }
-    DexClass superClass = definitionFor.apply(clazz.superType);
-    if (superClass == null) {
-      // TODO(herhut): Warn about broken supertype chain?
-      return false;
-    }
-    return anyImplementedInterfaceMatches(superClass, definitionFor, className, annotation);
+      AppView<? extends AppInfo> appView,
+      Collection<ProguardIfRule> ifRules,
+      InternalOptions options) {
+    this(appView, appView.appInfo().app, ifRules, options);
   }
 
   // Process a class with the keep rule.
@@ -168,8 +113,7 @@
     // seems not to care, so users have started to use this inconsistently. We are thus
     // inconsistent, as well, but tell them.
     // TODO(herhut): One day make this do what it says.
-    if (rule.hasInheritanceClassName()
-        && !satisfyInheritanceRule(clazz, application::definitionFor, rule)) {
+    if (rule.hasInheritanceClassName() && !satisfyInheritanceRule(clazz, rule)) {
       return;
     }
 
@@ -180,7 +124,7 @@
         switch (((ProguardKeepRule) rule).getType()) {
           case KEEP_CLASS_MEMBERS: {
             // Members mentioned at -keepclassmembers always depend on their holder.
-            preconditionSupplier = ImmutableMap.of((definition -> true), clazz);
+            preconditionSupplier = ImmutableMap.of(definition -> true, clazz);
             markMatchingVisibleMethods(clazz, memberKeepRules, rule, preconditionSupplier);
             markMatchingFields(clazz, memberKeepRules, rule, preconditionSupplier);
             break;
@@ -395,7 +339,7 @@
       if (rule.hasInheritanceClassName()) {
         // Note that, in presence of vertical class merging, we check if the resulting class
         // (i.e., the target class) satisfies the implements/extends-matcher.
-        if (!satisfyInheritanceRule(targetClass, this::definitionForWithLiveTypes, rule)) {
+        if (!satisfyInheritanceRule(targetClass, rule)) {
           // Try another live type since the current one doesn't satisfy the inheritance rule.
           return;
         }
@@ -458,12 +402,6 @@
       ProguardIfRule materializedRule = rule.materialize();
       runPerRule(executorService, futures, materializedRule.subsequentRule, materializedRule);
     }
-
-    private DexClass definitionForWithLiveTypes(DexType type) {
-      assert appView.verticallyMergedClasses() == null
-          || !appView.verticallyMergedClasses().hasBeenMergedIntoSubtype(type);
-      return liveTypes.contains(type) ? appView.appInfo().definitionFor(type) : null;
-    }
   }
 
   private static DexDefinition testAndGetPrecondition(
@@ -593,27 +531,23 @@
     return containsAnnotation(rule.getClassAnnotation(), clazz.annotations);
   }
 
-  private boolean satisfyInheritanceRule(
-      DexClass clazz, Function<DexType, DexClass> definitionFor, ProguardConfigurationRule rule) {
-    ProguardTypeMatcher inheritanceClassName = rule.getInheritanceClassName();
-    ProguardTypeMatcher inheritanceAnnotation = rule.getInheritanceAnnotation();
-    boolean extendsExpected =
-        satisfyExtendsRule(clazz, definitionFor, inheritanceClassName, inheritanceAnnotation);
+  private boolean satisfyInheritanceRule(DexClass clazz, ProguardConfigurationRule rule) {
+    boolean extendsExpected = satisfyExtendsRule(clazz, rule);
     boolean implementsExpected = false;
     if (!extendsExpected) {
-      implementsExpected =
-          anyImplementedInterfaceMatches(
-              clazz, definitionFor, inheritanceClassName, inheritanceAnnotation);
+      implementsExpected = satisfyImplementsRule(clazz, rule);
     }
     if (extendsExpected || implementsExpected) {
       // Warn if users got it wrong, but only warn once.
       if (rule.getInheritanceIsExtends()) {
         if (implementsExpected && rulesThatUseExtendsOrImplementsWrong.add(rule)) {
+          assert options.testing.allowProguardRulesThatUseExtendsOrImplementsWrong;
           options.reporter.warning(
               new StringDiagnostic(
                   "The rule `" + rule + "` uses extends but actually matches implements."));
         }
       } else if (extendsExpected && rulesThatUseExtendsOrImplementsWrong.add(rule)) {
+        assert options.testing.allowProguardRulesThatUseExtendsOrImplementsWrong;
         options.reporter.warning(
             new StringDiagnostic(
                 "The rule `" + rule + "` uses implements but actually matches extends."));
@@ -623,27 +557,90 @@
     return false;
   }
 
-  private boolean satisfyExtendsRule(
-      DexClass clazz,
-      Function<DexType, DexClass> definitionFor,
-      ProguardTypeMatcher inheritanceClassName,
-      ProguardTypeMatcher inheritanceAnnotation) {
-    if (anySuperTypeMatches(
-        clazz.superType, definitionFor, inheritanceClassName, inheritanceAnnotation)) {
+  private boolean satisfyExtendsRule(DexClass clazz, ProguardConfigurationRule rule) {
+    if (anySuperTypeMatchesExtendsRule(clazz.superType, rule)) {
       return true;
     }
-
     // It is possible that this class used to inherit from another class X, but no longer does it,
     // because X has been merged into `clazz`.
-    if (appView.verticallyMergedClasses() != null) {
-      // TODO(b/110141157): Figure out what to do with annotations. Should the annotations of
-      // the DexClass corresponding to `sourceType` satisfy the `annotation`-matcher?
-      return appView.verticallyMergedClasses().getSourcesFor(clazz.type).stream()
-          .anyMatch(inheritanceClassName::matches);
+    return anySourceMatchesInheritanceRuleDirectly(clazz, rule, false);
+  }
+
+  private boolean anySuperTypeMatchesExtendsRule(DexType type, ProguardConfigurationRule rule) {
+    while (type != null) {
+      DexClass clazz = application.definitionFor(type);
+      if (clazz == null) {
+        // TODO(herhut): Warn about broken supertype chain?
+        return false;
+      }
+      // TODO(b/110141157): Should the vertical class merger move annotations from the source to
+      // the target class? If so, it is sufficient only to apply the annotation-matcher to the
+      // annotations of `class`.
+      if (rule.getInheritanceClassName().matches(clazz.type, appView)
+          && containsAnnotation(rule.getInheritanceAnnotation(), clazz.annotations)) {
+        return true;
+      }
+      type = clazz.superType;
     }
     return false;
   }
 
+  private boolean satisfyImplementsRule(DexClass clazz, ProguardConfigurationRule rule) {
+    if (anyImplementedInterfaceMatchesImplementsRule(clazz, rule)) {
+      return true;
+    }
+    // It is possible that this class used to implement an interface I, but no longer does it,
+    // because I has been merged into `clazz`.
+    return anySourceMatchesInheritanceRuleDirectly(clazz, rule, true);
+  }
+
+  private boolean anyImplementedInterfaceMatchesImplementsRule(
+      DexClass clazz, ProguardConfigurationRule rule) {
+    // TODO(herhut): Maybe it would be better to do this breadth first.
+    if (clazz == null) {
+      return false;
+    }
+    for (DexType iface : clazz.interfaces.values) {
+      DexClass ifaceClass = application.definitionFor(iface);
+      if (ifaceClass == null) {
+        // TODO(herhut): Warn about broken supertype chain?
+        return false;
+      }
+      // TODO(b/110141157): Should the vertical class merger move annotations from the source to
+      // the target class? If so, it is sufficient only to apply the annotation-matcher to the
+      // annotations of `ifaceClass`.
+      if (rule.getInheritanceClassName().matches(iface, appView)
+          && containsAnnotation(rule.getInheritanceAnnotation(), ifaceClass.annotations)) {
+        return true;
+      }
+      if (anyImplementedInterfaceMatchesImplementsRule(ifaceClass, rule)) {
+        return true;
+      }
+    }
+    if (clazz.superType == null) {
+      return false;
+    }
+    DexClass superClass = application.definitionFor(clazz.superType);
+    if (superClass == null) {
+      // TODO(herhut): Warn about broken supertype chain?
+      return false;
+    }
+    return anyImplementedInterfaceMatchesImplementsRule(superClass, rule);
+  }
+
+  private boolean anySourceMatchesInheritanceRuleDirectly(
+      DexClass clazz, ProguardConfigurationRule rule, boolean isInterface) {
+    // TODO(b/110141157): Figure out what to do with annotations. Should the annotations of
+    // the DexClass corresponding to `sourceType` satisfy the `annotation`-matcher?
+    return appView.verticallyMergedClasses() != null
+        && appView.verticallyMergedClasses().getSourcesFor(clazz.type).stream()
+            .filter(
+                sourceType ->
+                    appView.appInfo().definitionFor(sourceType).accessFlags.isInterface()
+                        == isInterface)
+            .anyMatch(rule.getInheritanceClassName()::matches);
+  }
+
   private boolean allRulesSatisfied(Collection<ProguardMemberRule> memberKeepRules,
       DexClass clazz) {
     for (ProguardMemberRule rule : memberKeepRules) {
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index e6fd878..d83ad75 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -453,6 +453,7 @@
             ? NondeterministicIROrdering.getInstance()
             : IdentityIROrdering.getInstance();
 
+    public boolean allowProguardRulesThatUseExtendsOrImplementsWrong = true;
     public boolean alwaysUsePessimisticRegisterAllocation = false;
     public boolean invertConditionals = false;
     public boolean placeExceptionalBlocksLast = false;
diff --git a/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/IfRuleWithVerticalClassMerging.java b/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/IfRuleWithVerticalClassMerging.java
index 18783750..b026c31 100644
--- a/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/IfRuleWithVerticalClassMerging.java
+++ b/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/IfRuleWithVerticalClassMerging.java
@@ -60,7 +60,6 @@
 
 // TODO(b/110141157):
 // - Add tests where fields and methods get renamed due to naming conflicts.
-// - Add tests where the type in a implements clause has changed.
 // - Add tests where the then-clause of an -if rule keeps a class that has been merged into another.
 @RunWith(Parameterized.class)
 public class IfRuleWithVerticalClassMerging extends TestBase {
diff --git a/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/ImplementsMergedTypeDirectlyTest.java b/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/ImplementsMergedTypeDirectlyTest.java
new file mode 100644
index 0000000..6e8b394
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/ImplementsMergedTypeDirectlyTest.java
@@ -0,0 +1,58 @@
+// Copyright (c) 2018, 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.shaking.ifrule.verticalclassmerging;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.core.IsNot.not;
+import static org.junit.Assert.assertThat;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+
+public class ImplementsMergedTypeDirectlyTest extends MergedTypeBaseTest {
+
+  static class TestClass implements K {
+
+    public static void main(String[] args) {
+      System.out.print("Hello world");
+    }
+  }
+
+  public ImplementsMergedTypeDirectlyTest(Backend backend, boolean enableVerticalClassMerging) {
+    super(backend, enableVerticalClassMerging);
+  }
+
+  @Override
+  public Class<?> getTestClass() {
+    return TestClass.class;
+  }
+
+  @Override
+  public String getConditionForProguardIfRule() {
+    // After class merging, TestClass will no longer implement K, but we should still keep the
+    // class Unused in the output.
+    return "-if class **$TestClass implements **$K";
+  }
+
+  @Override
+  public String getExpectedStdout() {
+    return "Hello world";
+  }
+
+  public void inspect(CodeInspector inspector) {
+    super.inspect(inspector);
+
+    if (enableVerticalClassMerging) {
+      // Check that TestClass no longer implements K.
+      ClassSubject testClassSubject = inspector.clazz(TestClass.class);
+      assertThat(testClassSubject, isPresent());
+      assertTrue(testClassSubject.getDexClass().interfaces.isEmpty());
+
+      // Check that K is no longer present.
+      assertThat(inspector.clazz(K.class), not(isPresent()));
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/ImplementsMergedTypeIndirectlyTest.java b/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/ImplementsMergedTypeIndirectlyTest.java
new file mode 100644
index 0000000..4583978
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/ImplementsMergedTypeIndirectlyTest.java
@@ -0,0 +1,55 @@
+// Copyright (c) 2018, 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.shaking.ifrule.verticalclassmerging;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+
+public class ImplementsMergedTypeIndirectlyTest extends MergedTypeBaseTest {
+
+  static class TestClass implements J {
+
+    public static void main(String[] args) {
+      System.out.print("Hello world");
+    }
+  }
+
+  public ImplementsMergedTypeIndirectlyTest(Backend backend, boolean enableVerticalClassMerging) {
+    super(backend, enableVerticalClassMerging);
+  }
+
+  @Override
+  public Class<?> getTestClass() {
+    return TestClass.class;
+  }
+
+  @Override
+  public String getAdditionalKeepRules() {
+    // Keep interface J to prevent it from being merged into TestClass.
+    return "-keep class **$J";
+  }
+
+  @Override
+  public String getConditionForProguardIfRule() {
+    // After class merging, J will no longer extend I (and therefore, TestClass will no longer
+    // implement I indirectly), but we should still keep the class Unused in the output.
+    return "-if class **$TestClass implements **$I";
+  }
+
+  @Override
+  public String getExpectedStdout() {
+    return "Hello world";
+  }
+
+  public void inspect(CodeInspector inspector) {
+    super.inspect(inspector);
+
+    // Verify that TestClass still implements J.
+    ClassSubject testClassSubject = inspector.clazz(TestClass.class);
+    assertEquals(J.class.getTypeName(), testClassSubject.getDexClass().interfaces.toSourceString());
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/MergedTypeBaseTest.java b/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/MergedTypeBaseTest.java
index d2ce210..ac341eb 100644
--- a/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/MergedTypeBaseTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/MergedTypeBaseTest.java
@@ -28,7 +28,8 @@
 public abstract class MergedTypeBaseTest extends TestBase {
 
   private final List<Class> CLASSES =
-      ImmutableList.of(A.class, B.class, C.class, Unused.class, getTestClass());
+      ImmutableList.of(
+          A.class, B.class, C.class, I.class, J.class, K.class, Unused.class, getTestClass());
 
   static class A {}
 
@@ -36,6 +37,12 @@
 
   static class C {}
 
+  interface I {}
+
+  interface J extends I {}
+
+  interface K {}
+
   static class Unused {}
 
   final Backend backend;
@@ -58,6 +65,10 @@
 
   public abstract Class<?> getTestClass();
 
+  public String getAdditionalKeepRules() {
+    return "";
+  }
+
   public abstract String getConditionForProguardIfRule();
 
   public abstract String getExpectedStdout();
@@ -65,9 +76,10 @@
   public void inspect(CodeInspector inspector) {
     assertThat(inspector.clazz(Unused.class), isPresent());
 
-    // Verify that A is no longer present when vertical class merging is enabled.
+    // Verify that A and I are no longer present when vertical class merging is enabled.
     if (enableVerticalClassMerging) {
       assertThat(inspector.clazz(A.class), not(isPresent()));
+      assertThat(inspector.clazz(I.class), not(isPresent()));
     }
   }
 
@@ -82,7 +94,8 @@
             "  public static void main(java.lang.String[]);",
             "}",
             getConditionForProguardIfRule(),
-            "-keep class " + Unused.class.getTypeName());
+            "-keep class " + Unused.class.getTypeName(),
+            getAdditionalKeepRules());
     AndroidApp output = compileWithR8(readClasses(CLASSES), config, this::configure, backend);
     assertEquals(expected, runOnVM(output, getTestClass(), backend));
     inspect(new CodeInspector(output));
@@ -92,6 +105,10 @@
     options.enableMinification = false;
     options.enableVerticalClassMerging = enableVerticalClassMerging;
 
+    // To ensure that the handling of extends and implements rules work as intended,
+    // and that we don't end up keeping `Unused` only because one of the two implementations work.
+    options.testing.allowProguardRulesThatUseExtendsOrImplementsWrong = false;
+
     // TODO(b/110148109): Allow ordinary method inlining when -if rules work with inlining.
     options.testing.validInliningReasons = ImmutableSet.of(Reason.FORCE);
   }