Resolve all super classes even if we have found missing super classes. This is

necessary. If we stop resolving the super classes, then the checker will
complain that some methods are missign. In fact, these methods exist, but their
class is not resolved due to the existing early-break strategy.

RELNOTES: none
PiperOrigin-RevId: 198594008

27 files changed, 577 insertions, 408 deletions

diff --git a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/AbstractClassEntryState.java b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/AbstractClassEntryState.java
index 209bf83fcb..eeb162f3ba 100644
--- a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/AbstractClassEntryState.java
+++ b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/AbstractClassEntryState.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.importdeps;
 
-import static com.google.common.base.Preconditions.checkArgument;
 
 import com.google.auto.value.AutoValue;
 import com.google.common.collect.ImmutableList;
@@ -100,20 +99,15 @@ public abstract class AbstractClassEntryState {
   public abstract static class IncompleteState extends AbstractClassEntryState {
 
     public static IncompleteState create(
-        ClassInfo classInfo, ImmutableList<String> resolutionFailurePath) {
-      checkArgument(
-          !resolutionFailurePath.isEmpty(),
-          "The resolution path should contain at least one element, the missing ancestor. %s",
-          resolutionFailurePath);
+        ClassInfo classInfo, ResolutionFailureChain resolutionFailureChain) {
       return new AutoValue_AbstractClassEntryState_IncompleteState(
-          Optional.of(classInfo), resolutionFailurePath);
+          Optional.of(classInfo), resolutionFailureChain);
     }
 
-    public abstract ImmutableList<String> getResolutionFailurePath();
+    public abstract ResolutionFailureChain resolutionFailureChain();
 
-    public String getMissingAncestor() {
-      ImmutableList<String> path = getResolutionFailurePath();
-      return path.get(path.size() - 1);
+    public ImmutableList<String> missingAncestors() {
+      return resolutionFailureChain().missingClasses();
     }
 
     @Override
diff --git a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassCache.java b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassCache.java
index 232e69b936..292d5752b2 100644
--- a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassCache.java
+++ b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassCache.java
@@ -37,6 +37,7 @@ import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;
 import java.util.Objects;
+import java.util.Optional;
 import java.util.function.Predicate;
 import java.util.zip.ZipEntry;
 import java.util.zip.ZipFile;
@@ -145,43 +146,29 @@ public final class ClassCache implements Closeable {
               classEntry.zipFile.getEntry(entryName), "The zip entry %s is null.", entryName);
       try (InputStream inputStream = classEntry.zipFile.getInputStream(zipEntry)) {
         ClassReader classReader = new ClassReader(inputStream);
-        ImmutableList<String> resolutionFailurePath = null;
+        ImmutableList.Builder<ResolutionFailureChain> resolutionFailureChainsBuilder =
+            ImmutableList.builder();
         for (String superName :
             combineWithoutNull(classReader.getSuperName(), classReader.getInterfaces())) {
-          LazyClassEntry superClassEntry = lazyClasspath.getLazyEntry(superName);
-
-          if (superClassEntry == null) {
-            resolutionFailurePath = ImmutableList.of(superName);
-            break;
-          } else {
-            resolveClassEntry(superClassEntry, lazyClasspath);
-            AbstractClassEntryState superState = superClassEntry.state;
-            if (superState instanceof ExistingState) {
-              // Do nothing. Good to proceed.
-              continue;
-            } else if (superState instanceof IncompleteState) {
-              resolutionFailurePath =
-                  ImmutableList.<String>builder()
-                      .add(superName)
-                      .addAll(((IncompleteState) superState).getResolutionFailurePath())
-                      .build();
-              break;
-            } else {
-              throw new RuntimeException("Cannot reach here. superState is " + superState);
-            }
-          }
+          Optional<ResolutionFailureChain> failurePath =
+              resolveSuperClassEntry(superName, lazyClasspath);
+          failurePath.map(resolutionFailureChainsBuilder::add);
         }
         ClassInfoBuilder classInfoBuilder =
             new ClassInfoBuilder().setJarPath(classEntry.jarPath).setDirect(classEntry.direct);
         classReader.accept(classInfoBuilder, ClassReader.SKIP_DEBUG | ClassReader.SKIP_FRAMES);
-        if (resolutionFailurePath == null) {
+
+        ImmutableList<ResolutionFailureChain> resolutionFailureChains =
+            resolutionFailureChainsBuilder.build();
+        if (resolutionFailureChains.isEmpty()) {
           classEntry.state =
               ExistingState.create(classInfoBuilder.build(lazyClasspath, /*incomplete=*/ false));
         } else {
+          ClassInfo classInfo = classInfoBuilder.build(lazyClasspath, /*incomplete=*/ true);
           classEntry.state =
               IncompleteState.create(
-                  classInfoBuilder.build(lazyClasspath, /*incomplete=*/ true),
-                  resolutionFailurePath);
+                  classInfo,
+                  ResolutionFailureChain.createWithParent(classInfo, resolutionFailureChains));
         }
       } catch (IOException e) {
         throw new RuntimeException("Error when resolving class entry " + entryName);
@@ -193,6 +180,26 @@ public final class ClassCache implements Closeable {
         throw e;
       }
     }
+
+    private static Optional<ResolutionFailureChain> resolveSuperClassEntry(
+        String superName, LazyClasspath lazyClasspath) {
+      LazyClassEntry superClassEntry = lazyClasspath.getLazyEntry(superName);
+
+      if (superClassEntry == null) {
+        return Optional.of(ResolutionFailureChain.createMissingClass(superName));
+      } else {
+        resolveClassEntry(superClassEntry, lazyClasspath);
+        AbstractClassEntryState superState = superClassEntry.state;
+        if (superState instanceof ExistingState) {
+          // Do nothing. Good to proceed.
+          return Optional.empty();
+        } else if (superState instanceof IncompleteState) {
+          return Optional.of(superState.asIncompleteState().resolutionFailureChain());
+        } else {
+          throw new RuntimeException("Cannot reach here. superState is " + superState);
+        }
+      }
+    }
   }
 
   private static ImmutableList<String> combineWithoutNull(
diff --git a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassInfo.java b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassInfo.java
index 0a1e921ad0..3d5a5a6432 100644
--- a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassInfo.java
+++ b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassInfo.java
@@ -18,6 +18,7 @@ import static com.google.common.base.Preconditions.checkArgument;
 import com.google.auto.value.AutoValue;
 import com.google.auto.value.extension.memoized.Memoized;
 import com.google.common.base.Strings;
+import com.google.common.collect.ComparisonChain;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import java.nio.file.Path;
@@ -27,7 +28,7 @@ import java.nio.file.Path;
  * classes.
  */
 @AutoValue
-public abstract class ClassInfo {
+public abstract class ClassInfo implements Comparable<ClassInfo> {
 
   public static ClassInfo create(
       String internalName,
@@ -64,6 +65,15 @@ public abstract class ClassInfo {
     return false;
   }
 
+  @Override
+  public int compareTo(ClassInfo other) {
+    return ComparisonChain.start()
+        .compare(internalName(), other.internalName())
+        .compare(jarPath(), other.jarPath())
+        .compareFalseFirst(directDep(), other.directDep())
+        .result();
+  }
+
   /** A member is either a method or a field. */
   @AutoValue
   public abstract static class MemberInfo {
diff --git a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/DepsCheckerClassVisitor.java b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/DepsCheckerClassVisitor.java
index b57c273e10..b536a39633 100644
--- a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/DepsCheckerClassVisitor.java
+++ b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/DepsCheckerClassVisitor.java
@@ -174,12 +174,19 @@ public class DepsCheckerClassVisitor extends ClassVisitor {
       resultCollector.addMissingOrIncompleteClass(internalName, state);
     } else {
       if (state.isIncompleteState()) {
-        String missingAncestor = state.asIncompleteState().getMissingAncestor();
-        AbstractClassEntryState ancestorState = classCache.getClassState(missingAncestor);
-        checkState(
-            ancestorState.isMissingState(), "The ancestor should be missing. %s", ancestorState);
-        resultCollector.addMissingOrIncompleteClass(missingAncestor, ancestorState);
-        resultCollector.addMissingOrIncompleteClass(internalName, state);
+        state
+            .asIncompleteState()
+            .missingAncestors()
+            .forEach(
+                missingAncestor -> {
+                  AbstractClassEntryState ancestorState = classCache.getClassState(missingAncestor);
+                  checkState(
+                      ancestorState.isMissingState(),
+                      "The ancestor should be missing. %s",
+                      ancestorState);
+                  resultCollector.addMissingOrIncompleteClass(missingAncestor, ancestorState);
+                  resultCollector.addMissingOrIncompleteClass(internalName, state);
+                });
       }
       ClassInfo info = state.classInfo().get();
       if (!info.directDep()) {
diff --git a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ImportDepsChecker.java b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ImportDepsChecker.java
index 9276d92eb6..7e837a8f53 100644
--- a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ImportDepsChecker.java
+++ b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ImportDepsChecker.java
@@ -13,8 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.importdeps;
 
-import static com.google.common.base.Preconditions.checkState;
 
+import com.google.common.collect.HashMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.importdeps.AbstractClassEntryState.IncompleteState;
 import com.google.devtools.build.importdeps.ResultCollector.MissingMember;
@@ -27,9 +27,10 @@ import java.io.IOException;
 import java.io.InputStream;
 import java.io.UncheckedIOException;
 import java.nio.file.Path;
+import java.util.LinkedHashMap;
+import java.util.Map;
 import java.util.Objects;
 import java.util.jar.JarFile;
-import java.util.stream.Collectors;
 import java.util.zip.ZipFile;
 import javax.annotation.Nullable;
 import org.objectweb.asm.ClassReader;
@@ -108,61 +109,21 @@ public final class ImportDepsChecker implements Closeable {
   public String computeResultOutput(String ruleLabel) {
     StringBuilder builder = new StringBuilder();
     ImmutableList<String> missingClasses = resultCollector.getSortedMissingClassInternalNames();
-    for (String missing : missingClasses) {
-      builder.append("Missing ").append(missing.replace('/', '.')).append('\n');
-    }
+    outputMissingClasses(builder, missingClasses);
 
     ImmutableList<IncompleteState> incompleteClasses = resultCollector.getSortedIncompleteClasses();
-    for (IncompleteState incomplete : incompleteClasses) {
-      builder
-          .append("Incomplete ancestor classpath for ")
-          .append(incomplete.classInfo().get().internalName().replace('/', '.'))
-          .append('\n');
+    outputIncompleteClasses(builder, incompleteClasses);
 
-      ImmutableList<String> failurePath = incomplete.getResolutionFailurePath();
-      checkState(!failurePath.isEmpty(), "The resolution failure path is empty. %s", failurePath);
-      builder
-          .append(INDENT)
-          .append("missing ancestor: ")
-          .append(failurePath.get(failurePath.size() - 1).replace('/', '.'))
-          .append('\n');
-      builder
-          .append(INDENT)
-          .append("resolution failure path: ")
-          .append(
-              failurePath
-                  .stream()
-                  .map(internalName -> internalName.replace('/', '.'))
-                  .collect(Collectors.joining(" -> ")))
-          .append('\n');
-    }
     ImmutableList<MissingMember> missingMembers = resultCollector.getSortedMissingMembers();
-    for (MissingMember missing : missingMembers) {
-      builder
-          .append("Missing member '")
-          .append(missing.memberName())
-          .append("' in class ")
-          .append(missing.owner().replace('/', '.'))
-          .append(" : name=")
-          .append(missing.memberName())
-          .append(", descriptor=")
-          .append(missing.descriptor())
-          .append('\n');
-    }
-    if (missingClasses.size() + incompleteClasses.size() + missingMembers.size() != 0) {
-      builder
-          .append("===Total===\n")
-          .append("missing=")
-          .append(missingClasses.size())
-          .append('\n')
-          .append("incomplete=")
-          .append(incompleteClasses.size())
-          .append('\n')
-          .append("missing_members=")
-          .append(missingMembers.size())
-          .append('\n');
-    }
+    outputMissingMembers(builder, missingMembers);
+
+    outputStatistics(builder, missingClasses, incompleteClasses, missingMembers);
+
+    emitAddDepCommandForIndirectJars(ruleLabel, builder);
+    return builder.toString();
+  }
 
+  private void emitAddDepCommandForIndirectJars(String ruleLabel, StringBuilder builder) {
     ImmutableList<Path> indirectJars = resultCollector.getSortedIndirectDeps();
     if (!indirectJars.isEmpty()) {
       ImmutableList<String> labels = extractLabels(indirectJars);
@@ -186,7 +147,82 @@ public final class ImportDepsChecker implements Closeable {
         builder.append(ruleLabel).append('\n');
       }
     }
-    return builder.toString();
+  }
+
+  private void outputStatistics(
+      StringBuilder builder,
+      ImmutableList<String> missingClasses,
+      ImmutableList<IncompleteState> incompleteClasses,
+      ImmutableList<MissingMember> missingMembers) {
+    if (missingClasses.size() + incompleteClasses.size() + missingMembers.size() != 0) {
+      builder
+          .append("===Total===\n")
+          .append("missing=")
+          .append(missingClasses.size())
+          .append('\n')
+          .append("incomplete=")
+          .append(incompleteClasses.size())
+          .append('\n')
+          .append("missing_members=")
+          .append(missingMembers.size())
+          .append('\n');
+    }
+  }
+
+  private void outputMissingMembers(
+      StringBuilder builder, ImmutableList<MissingMember> missingMembers) {
+    for (MissingMember missing : missingMembers) {
+      builder
+          .append("Missing member '")
+          .append(missing.memberName())
+          .append("' in class ")
+          .append(missing.owner().replace('/', '.'))
+          .append(" : name=")
+          .append(missing.memberName())
+          .append(", descriptor=")
+          .append(missing.descriptor())
+          .append('\n');
+    }
+  }
+
+  private void outputIncompleteClasses(
+      StringBuilder builder, ImmutableList<IncompleteState> incompleteClasses) {
+    new LinkedHashMap<>();
+    HashMultimap<String, ClassInfo> map = HashMultimap.create();
+    for (IncompleteState incomplete : incompleteClasses) {
+      ResolutionFailureChain chain = incomplete.resolutionFailureChain();
+      map.putAll(chain.getMissingClassesWithSubclasses());
+    }
+    map.asMap()
+        .entrySet()
+        .stream()
+        .sorted(Map.Entry.comparingByKey())
+        .forEach(
+            entry -> {
+              builder
+                  .append("Indirectly missing class ")
+                  .append(entry.getKey().replace('/', '.'))
+                  .append(". Referenced by:")
+                  .append('\n');
+              entry
+                  .getValue()
+                  .stream()
+                  .distinct()
+                  .sorted()
+                  .forEach(
+                      reference -> {
+                        builder
+                            .append(INDENT)
+                            .append(reference.internalName().replace('/', '.'))
+                            .append('\n');
+                      });
+            });
+  }
+
+  private void outputMissingClasses(StringBuilder builder, ImmutableList<String> missingClasses) {
+    for (String missing : missingClasses) {
+      builder.append("Missing ").append(missing.replace('/', '.')).append('\n');
+    }
   }
 
   private static ImmutableList<String> extractLabels(ImmutableList<Path> jars) {
diff --git a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ResolutionFailureChain.java b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ResolutionFailureChain.java
new file mode 100644
index 0000000000..3ac67c1daf
--- /dev/null
+++ b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ResolutionFailureChain.java
@@ -0,0 +1,82 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.importdeps;
+
+import static com.google.common.base.Preconditions.checkState;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMultimap;
+import javax.annotation.Nullable;
+
+/** The resolution failure path. */
+@AutoValue
+public abstract class ResolutionFailureChain {
+
+  public static ResolutionFailureChain createMissingClass(String missingClass) {
+    return new AutoValue_ResolutionFailureChain(
+        ImmutableList.of(missingClass),
+        /*resolutionStartClass=*/ null,
+        /*parentChains=*/ ImmutableList.of());
+  }
+
+  public static ResolutionFailureChain createWithParent(
+      ClassInfo resolutionStartClass, ImmutableList<ResolutionFailureChain> parentChains) {
+    Preconditions.checkArgument(!parentChains.isEmpty(), "The parentChains cannot be empty.");
+    return new AutoValue_ResolutionFailureChain(
+        parentChains
+            .stream()
+            .flatMap(chain -> chain.missingClasses().stream())
+            .sorted()
+            .distinct()
+            .collect(ImmutableList.toImmutableList()),
+        resolutionStartClass,
+        parentChains);
+  }
+
+  /** The missing class that causes the resolution failure. */
+  public abstract ImmutableList<String> missingClasses();
+
+  /** The start of this resolution chain. */
+  @Nullable
+  public abstract ClassInfo resolutionStartClass();
+
+  /** The resolution chain of the parent class. */
+  public abstract ImmutableList<ResolutionFailureChain> parentChains();
+
+  /** For all the missing classes, represent the first chains that lead to the missing classes. */
+  public ImmutableMultimap<String, ClassInfo> getMissingClassesWithSubclasses() {
+    ImmutableMultimap.Builder<String, ClassInfo> result = ImmutableMultimap.builder();
+    getMissingClassesWithSubclasses(resolutionStartClass(), this.parentChains(), result);
+    return result.build();
+  }
+
+  private static void getMissingClassesWithSubclasses(
+      ClassInfo subclass,
+      ImmutableList<ResolutionFailureChain> parentChains,
+      ImmutableMultimap.Builder<String, ClassInfo> result) {
+    for (ResolutionFailureChain parentChain : parentChains) {
+      if (parentChain.resolutionStartClass() == null) {
+        checkState(
+            parentChain.parentChains().isEmpty() && parentChain.missingClasses().size() == 1);
+        result.put(parentChain.missingClasses().get(0), subclass);
+      } else {
+        checkState(!parentChain.parentChains().isEmpty());
+        getMissingClassesWithSubclasses(
+            parentChain.resolutionStartClass(), parentChain.parentChains(), result);
+      }
+    }
+  }
+}
diff --git a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ResultCollector.java b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ResultCollector.java
index 5288799f07..7a1fe39b0a 100644
--- a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ResultCollector.java
+++ b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ResultCollector.java
@@ -48,7 +48,8 @@ public class ResultCollector {
           "The old value and the new value are not the same object. old=%s, new=%s",
           oldValue,
           state);
-      missingClasss.add(state.asIncompleteState().getMissingAncestor()); // Add the real missing.
+      // Add the real missing.
+      state.asIncompleteState().missingAncestors().forEach(missingClasss::add);
     } else if (state.isMissingState()) {
       missingClasss.add(internalName);
     } else {
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/AbstractClassCacheTest.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/AbstractClassCacheTest.java
index 2432c70b33..a2cb0bca1d 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/AbstractClassCacheTest.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/AbstractClassCacheTest.java
@@ -41,7 +41,7 @@ public abstract class AbstractClassCacheTest {
       ImmutableList.<String>builder()
           .add("Library")
           .addAll(
-              IntStream.range(1, 11)
+              IntStream.range(1, 12)
                   .mapToObj(i -> "Library$Class" + i)
                   .collect(ImmutableList.toImmutableList()))
           .build()
@@ -83,7 +83,9 @@ public abstract class AbstractClassCacheTest {
           PACKAGE_NAME + "LibraryInterface",
           PACKAGE_NAME + "LibraryInterface$Func",
           PACKAGE_NAME + "LibraryInterface$One",
-          PACKAGE_NAME + "LibraryInterface$Two");
+          PACKAGE_NAME + "LibraryInterface$Two",
+          PACKAGE_NAME + "LibraryInterface$InterfaceFoo",
+          PACKAGE_NAME + "LibraryInterface$InterfaceBar");
 
   static Path getPathFromSystemProperty(String propertyName) {
     String path =
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ClassCacheTest.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ClassCacheTest.java
index 09fcf9eadd..bf4ca0a6ab 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ClassCacheTest.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ClassCacheTest.java
@@ -38,16 +38,13 @@ public class ClassCacheTest extends AbstractClassCacheTest {
     try (ClassCache cache =
         new ClassCache(
             ImmutableList.of(bootclasspath),
-            ImmutableList.of(libraryJar),
-            ImmutableList.of(libraryJar),
+            ImmutableList.of(),
+            ImmutableList.of(libraryJar, libraryInterfaceJar),
             ImmutableList.of())) {
       assertCache(
           cache,
           libraryJarPositives,
-          combine(
-              libraryInterfacePositives,
-              libraryAnnotationsJarPositives,
-              libraryExceptionJarPositives));
+          combine(libraryAnnotationsJarPositives, libraryExceptionJarPositives));
     }
   }
 
@@ -80,8 +77,24 @@ public class ClassCacheTest extends AbstractClassCacheTest {
         AbstractClassEntryState state = cache.getClassState(PACKAGE_NAME + "Client");
         assertThat(state.isIncompleteState()).isTrue();
 
-        ImmutableList<String> failureCause = state.asIncompleteState().getResolutionFailurePath();
-        assertThat(failureCause).containsExactly(PACKAGE_NAME + "Library").inOrder();
+        ImmutableList<String> successPart =
+            state
+                .asIncompleteState()
+                .resolutionFailureChain()
+                .getMissingClassesWithSubclasses()
+                .values()
+                .stream()
+                .distinct()
+                .sorted()
+                .map(ClassInfo::internalName)
+                .collect(ImmutableList.toImmutableList());
+        assertThat(successPart).containsExactly(PACKAGE_NAME + "Client").inOrder();
+        assertThat(state.asIncompleteState().missingAncestors())
+            .containsExactly(
+                PACKAGE_NAME + "Library",
+                PACKAGE_NAME + "LibraryInterface",
+                PACKAGE_NAME + "LibraryInterface$One",
+                PACKAGE_NAME + "LibraryInterface$Two");
       }
       assertThat(cache.getClassState(PACKAGE_NAME + "Client").isIncompleteState()).isTrue();
       assertThat(cache.getClassState(PACKAGE_NAME + "Client$NestedAnnotation"))
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ImportDepsCheckerTest.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ImportDepsCheckerTest.java
index be46cb3ffb..0f5a341a25 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ImportDepsCheckerTest.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ImportDepsCheckerTest.java
@@ -57,7 +57,7 @@ public class ImportDepsCheckerTest extends AbstractClassCacheTest {
         ImmutableList.of(bootclasspath),
         ImmutableList.of(libraryAnnotationsJar),
         ImmutableList.of(libraryJar),
-        true,
+        false,
         ImmutableList.of());
     testJdepsProto(
         ImmutableList.of(bootclasspath),
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/LazyClassEntryStateTest.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/LazyClassEntryStateTest.java
index f042c34600..4baaa20687 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/LazyClassEntryStateTest.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/LazyClassEntryStateTest.java
@@ -59,9 +59,13 @@ public class LazyClassEntryStateTest {
   public void testIncompleteState() {
     assertThrows(
         IllegalArgumentException.class,
-        () -> IncompleteState.create(LIST_CLASS_INFO, ImmutableList.of()));
+        () ->
+            IncompleteState.create(
+                LIST_CLASS_INFO,
+                ResolutionFailureChain.createWithParent(LIST_CLASS_INFO, ImmutableList.of())));
     IncompleteState state =
-        IncompleteState.create(LIST_CLASS_INFO, ImmutableList.of("java/lang/Object"));
+        IncompleteState.create(
+            LIST_CLASS_INFO, ResolutionFailureChain.createMissingClass("java/lang/Object"));
 
     assertThat(state.isExistingState()).isFalse();
     assertThat(state.isIncompleteState()).isTrue();
@@ -76,9 +80,9 @@ public class LazyClassEntryStateTest {
     assertThat(classInfo.declaredMembers()).hasSize(1);
     assertThat(classInfo.declaredMembers()).containsExactly(MemberInfo.create("hashCode", "()I"));
 
-    ImmutableList<String> failurePath = state.getResolutionFailurePath();
-    assertThat(failurePath).hasSize(1);
-    assertThat(failurePath).containsExactly("java/lang/Object");
+    assertThat(state.resolutionFailureChain().getMissingClassesWithSubclasses()).isEmpty();
+    assertThat(state.missingAncestors()).hasSize(1);
+    assertThat(state.missingAncestors()).containsExactly("java/lang/Object");
   }
 
   @Test
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ResolutionFailureChainTest.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ResolutionFailureChainTest.java
new file mode 100644
index 0000000000..362a435cb5
--- /dev/null
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ResolutionFailureChainTest.java
@@ -0,0 +1,85 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.importdeps;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import java.nio.file.Paths;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Test for {@link ResolutionFailureChain} */
+@RunWith(JUnit4.class)
+public class ResolutionFailureChainTest {
+
+  private final ClassInfo charSequenceClass =
+      ClassInfo.create(
+          "java/lang/CharSequence",
+          Paths.get("string.jar"),
+          false,
+          ImmutableList.of(),
+          ImmutableSet.of());
+  private final ResolutionFailureChain objectMissingChain =
+      ResolutionFailureChain.createMissingClass("java/lang/Object");
+  private final ResolutionFailureChain charSequenceFailureChain =
+      ResolutionFailureChain.createWithParent(
+          charSequenceClass, ImmutableList.of(objectMissingChain));
+
+  @Test
+  public void testArgumentCheck() {
+    Assert.assertThrows(
+        IllegalArgumentException.class,
+        () -> ResolutionFailureChain.createWithParent(charSequenceClass, ImmutableList.of()));
+  }
+
+  @Test
+  public void testMissingClassChain() {
+    assertThat(objectMissingChain.missingClasses()).containsExactly("java/lang/Object");
+    assertThat(objectMissingChain.getMissingClassesWithSubclasses()).isEmpty();
+    assertThat(objectMissingChain.parentChains()).isEmpty();
+    assertThat(objectMissingChain.resolutionStartClass()).isNull();
+  }
+
+  @Test
+  public void testChainWithOneHead() {
+    assertThat(charSequenceFailureChain.missingClasses()).containsExactly("java/lang/Object");
+    assertThat(charSequenceFailureChain.resolutionStartClass()).isEqualTo(charSequenceClass);
+    assertThat(charSequenceFailureChain.getMissingClassesWithSubclasses().values())
+        .containsExactly(charSequenceClass);
+    assertThat(charSequenceFailureChain.parentChains()).containsExactly(objectMissingChain);
+  }
+
+  @Test
+  public void testChainWithTwoHeads() {
+    ClassInfo stringClass =
+        ClassInfo.create(
+            "java/lang/String",
+            Paths.get("string.jar"),
+            false,
+            ImmutableList.of(),
+            ImmutableSet.of());
+    ResolutionFailureChain chain =
+        ResolutionFailureChain.createWithParent(
+            stringClass, ImmutableList.of(objectMissingChain, charSequenceFailureChain));
+    assertThat(chain.missingClasses()).containsExactly("java/lang/Object");
+    assertThat(chain.parentChains()).containsExactly(objectMissingChain, charSequenceFailureChain);
+    assertThat(chain.getMissingClassesWithSubclasses().values())
+        .containsExactly(stringClass, charSequenceClass);
+    assertThat(chain.resolutionStartClass()).isEqualTo(stringClass);
+  }
+}
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ResultCollectorTest.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ResultCollectorTest.java
index db76c26d7b..6256c77ec1 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ResultCollectorTest.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ResultCollectorTest.java
@@ -24,7 +24,6 @@ import com.google.devtools.build.importdeps.ResultCollector.MissingMember;
 import java.io.IOException;
 import java.nio.file.Path;
 import java.nio.file.Paths;
-import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -33,12 +32,21 @@ import org.junit.runners.JUnit4;
 @RunWith(JUnit4.class)
 public class ResultCollectorTest {
 
-  private ResultCollector collector;
-
-  @Before
-  public void setup() throws IOException {
-    collector = new ResultCollector();
-  }
+  private final ClassInfo objectClass =
+      ClassInfo.create(
+          "java/lang/Object",
+          Paths.get("bootclasspath.jar"),
+          false,
+          ImmutableList.of(),
+          ImmutableSet.of());
+  private final ClassInfo stringClass =
+      ClassInfo.create(
+          "java/lang/String",
+          Paths.get("string.jar"),
+          false,
+          ImmutableList.of(objectClass),
+          ImmutableSet.of());
+  private ResultCollector collector = new ResultCollector();
 
   @Test
   public void testEmptyCollector() throws IOException {
@@ -67,14 +75,16 @@ public class ResultCollectorTest {
     collector.addMissingOrIncompleteClass(
         "java/lang/String",
         IncompleteState.create(
-            ClassInfo.create(
-                "java/lang/String", Paths.get("a"), true, ImmutableList.of(), ImmutableSet.of()),
-            ImmutableList.of("java/lang/Object")));
+            stringClass, ResolutionFailureChain.createMissingClass("java/lang/Object")));
     assertThat(collector.getSortedIncompleteClasses()).hasSize(1);
     assertThat(collector.getSortedIncompleteClasses().get(0).classInfo().get())
         .isEqualTo(
             ClassInfo.create(
-                "java/lang/String", Paths.get("a"), true, ImmutableList.of(), ImmutableSet.of()));
+                "java/lang/String",
+                Paths.get("string.jar"),
+                false,
+                ImmutableList.of(objectClass),
+                ImmutableSet.of()));
     assertThat(collector.isEmpty()).isFalse();
   }
 
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.stderr.txt b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.stderr.txt
index a037fa0556..e7470b5514 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.stderr.txt
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.stderr.txt
@@ -21,93 +21,49 @@ Missing java.lang.invoke.MethodHandle
 Missing java.lang.invoke.MethodHandles$Lookup
 Missing java.lang.invoke.MethodType
 Missing java.util.Objects
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client
-    missing ancestor: java.lang.Object
-    resolution failure path: com.google.devtools.build.importdeps.testdata.Library -> java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client$EnumTest
-    missing ancestor: java.lang.Enum
-    resolution failure path: java.lang.Enum
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client$InnerClassWithSyntheticConstructorParam
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class1
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class10
-    missing ancestor: java.lang.Object
-    resolution failure path: com.google.devtools.build.importdeps.testdata.Library$Class9 -> java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class2
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class3
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class4
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class5
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class6
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class7
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class8
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class9
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationFlag
-    missing ancestor: java.lang.Enum
-    resolution failure path: java.lang.Enum
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ClassAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ConstructorAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$FieldAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$MethodAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ParameterAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$TypeAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryException
-    missing ancestor: java.lang.Exception
-    resolution failure path: java.lang.Exception
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface$Func
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface$One
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface$Two
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
+Indirectly missing class java.lang.Enum. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client$EnumTest
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationFlag
+Indirectly missing class java.lang.Exception. Referenced by:
+    com.google.devtools.build.importdeps.testdata.LibraryException
+Indirectly missing class java.lang.Object. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client$InnerClassWithSyntheticConstructorParam
+    com.google.devtools.build.importdeps.testdata.Library
+    com.google.devtools.build.importdeps.testdata.Library$Class1
+    com.google.devtools.build.importdeps.testdata.Library$Class11
+    com.google.devtools.build.importdeps.testdata.Library$Class2
+    com.google.devtools.build.importdeps.testdata.Library$Class3
+    com.google.devtools.build.importdeps.testdata.Library$Class4
+    com.google.devtools.build.importdeps.testdata.Library$Class5
+    com.google.devtools.build.importdeps.testdata.Library$Class6
+    com.google.devtools.build.importdeps.testdata.Library$Class7
+    com.google.devtools.build.importdeps.testdata.Library$Class8
+    com.google.devtools.build.importdeps.testdata.Library$Class9
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ClassAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ConstructorAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$FieldAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$MethodAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ParameterAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$TypeAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryInterface
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$Func
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceBar
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceFoo
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$One
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$Two
+Indirectly missing class java.lang.annotation.Annotation. Referenced by:
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ClassAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ConstructorAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$FieldAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$MethodAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ParameterAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$TypeAnnotation
 Missing member 'name' in class com.google.devtools.build.importdeps.testdata.Client$EnumTest : name=name, descriptor=()Ljava/lang/String;
 Missing member 'ordinal' in class com.google.devtools.build.importdeps.testdata.Client$EnumTest : name=ordinal, descriptor=()I
 ===Total===
 missing=20
-incomplete=28
+incomplete=29
 missing_members=2
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.stderr.warning.txt b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.stderr.warning.txt
index 2bb0b97f86..a5a3f24a15 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.stderr.warning.txt
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.stderr.warning.txt
@@ -21,93 +21,49 @@ Missing java.lang.invoke.MethodHandle
 Missing java.lang.invoke.MethodHandles$Lookup
 Missing java.lang.invoke.MethodType
 Missing java.util.Objects
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client
-    missing ancestor: java.lang.Object
-    resolution failure path: com.google.devtools.build.importdeps.testdata.Library -> java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client$EnumTest
-    missing ancestor: java.lang.Enum
-    resolution failure path: java.lang.Enum
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client$InnerClassWithSyntheticConstructorParam
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class1
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class10
-    missing ancestor: java.lang.Object
-    resolution failure path: com.google.devtools.build.importdeps.testdata.Library$Class9 -> java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class2
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class3
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class4
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class5
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class6
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class7
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class8
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class9
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationFlag
-    missing ancestor: java.lang.Enum
-    resolution failure path: java.lang.Enum
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ClassAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ConstructorAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$FieldAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$MethodAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ParameterAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$TypeAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryException
-    missing ancestor: java.lang.Exception
-    resolution failure path: java.lang.Exception
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface$Func
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface$One
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface$Two
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
+Indirectly missing class java.lang.Enum. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client$EnumTest
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationFlag
+Indirectly missing class java.lang.Exception. Referenced by:
+    com.google.devtools.build.importdeps.testdata.LibraryException
+Indirectly missing class java.lang.Object. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client$InnerClassWithSyntheticConstructorParam
+    com.google.devtools.build.importdeps.testdata.Library
+    com.google.devtools.build.importdeps.testdata.Library$Class1
+    com.google.devtools.build.importdeps.testdata.Library$Class11
+    com.google.devtools.build.importdeps.testdata.Library$Class2
+    com.google.devtools.build.importdeps.testdata.Library$Class3
+    com.google.devtools.build.importdeps.testdata.Library$Class4
+    com.google.devtools.build.importdeps.testdata.Library$Class5
+    com.google.devtools.build.importdeps.testdata.Library$Class6
+    com.google.devtools.build.importdeps.testdata.Library$Class7
+    com.google.devtools.build.importdeps.testdata.Library$Class8
+    com.google.devtools.build.importdeps.testdata.Library$Class9
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ClassAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ConstructorAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$FieldAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$MethodAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ParameterAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$TypeAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryInterface
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$Func
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceBar
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceFoo
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$One
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$Two
+Indirectly missing class java.lang.annotation.Annotation. Referenced by:
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ClassAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ConstructorAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$FieldAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$MethodAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ParameterAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$TypeAnnotation
 Missing member 'name' in class com.google.devtools.build.importdeps.testdata.Client$EnumTest : name=name, descriptor=()Ljava/lang/String;
 Missing member 'ordinal' in class com.google.devtools.build.importdeps.testdata.Client$EnumTest : name=ordinal, descriptor=()I
 ===Total===
 missing=20
-incomplete=28
+incomplete=29
 missing_members=2
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.txt b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.txt
index f68fee99ce..27d55cc9d2 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.txt
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_bootclasspath_missing.txt
@@ -18,93 +18,49 @@ Missing java.lang.invoke.MethodHandle
 Missing java.lang.invoke.MethodHandles$Lookup
 Missing java.lang.invoke.MethodType
 Missing java.util.Objects
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client
-    missing ancestor: java.lang.Object
-    resolution failure path: com.google.devtools.build.importdeps.testdata.Library -> java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client$EnumTest
-    missing ancestor: java.lang.Enum
-    resolution failure path: java.lang.Enum
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client$InnerClassWithSyntheticConstructorParam
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class1
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class10
-    missing ancestor: java.lang.Object
-    resolution failure path: com.google.devtools.build.importdeps.testdata.Library$Class9 -> java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class2
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class3
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class4
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class5
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class6
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class7
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class8
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Library$Class9
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationFlag
-    missing ancestor: java.lang.Enum
-    resolution failure path: java.lang.Enum
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ClassAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ConstructorAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$FieldAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$MethodAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ParameterAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryAnnotations$TypeAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryException
-    missing ancestor: java.lang.Exception
-    resolution failure path: java.lang.Exception
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface$Func
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface$One
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.LibraryInterface$Two
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
+Indirectly missing class java.lang.Enum. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client$EnumTest
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationFlag
+Indirectly missing class java.lang.Exception. Referenced by:
+    com.google.devtools.build.importdeps.testdata.LibraryException
+Indirectly missing class java.lang.Object. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client$InnerClassWithSyntheticConstructorParam
+    com.google.devtools.build.importdeps.testdata.Library
+    com.google.devtools.build.importdeps.testdata.Library$Class1
+    com.google.devtools.build.importdeps.testdata.Library$Class11
+    com.google.devtools.build.importdeps.testdata.Library$Class2
+    com.google.devtools.build.importdeps.testdata.Library$Class3
+    com.google.devtools.build.importdeps.testdata.Library$Class4
+    com.google.devtools.build.importdeps.testdata.Library$Class5
+    com.google.devtools.build.importdeps.testdata.Library$Class6
+    com.google.devtools.build.importdeps.testdata.Library$Class7
+    com.google.devtools.build.importdeps.testdata.Library$Class8
+    com.google.devtools.build.importdeps.testdata.Library$Class9
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ClassAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ConstructorAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$FieldAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$MethodAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ParameterAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$TypeAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryInterface
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$Func
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceBar
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceFoo
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$One
+    com.google.devtools.build.importdeps.testdata.LibraryInterface$Two
+Indirectly missing class java.lang.annotation.Annotation. Referenced by:
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$AnnotationAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ClassAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ConstructorAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$FieldAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$MethodAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$ParameterAnnotation
+    com.google.devtools.build.importdeps.testdata.LibraryAnnotations$TypeAnnotation
 Missing member 'name' in class com.google.devtools.build.importdeps.testdata.Client$EnumTest : name=name, descriptor=()Ljava/lang/String;
 Missing member 'ordinal' in class com.google.devtools.build.importdeps.testdata.Client$EnumTest : name=ordinal, descriptor=()I
 ===Total===
 missing=20
-incomplete=28
+incomplete=29
 missing_members=2
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_interface_missing.stderr.txt b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_interface_missing.stderr.txt
index 9dfb028a60..3983296240 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_interface_missing.stderr.txt
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_interface_missing.stderr.txt
@@ -3,12 +3,23 @@ ERROR: The dependencies for the following 1 jar(s) are not complete.
 The details are listed below:
 Missing com.google.devtools.build.importdeps.testdata.LibraryInterface
 Missing com.google.devtools.build.importdeps.testdata.LibraryInterface$Func
+Missing com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceBar
+Missing com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceFoo
 Missing com.google.devtools.build.importdeps.testdata.LibraryInterface$One
 Missing com.google.devtools.build.importdeps.testdata.LibraryInterface$Two
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client
-    missing ancestor: com.google.devtools.build.importdeps.testdata.LibraryInterface
-    resolution failure path: com.google.devtools.build.importdeps.testdata.LibraryInterface
+Indirectly missing class com.google.devtools.build.importdeps.testdata.LibraryInterface. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client
+Indirectly missing class com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceBar. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Library$Class11
+Indirectly missing class com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceFoo. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Library$Class11
+Indirectly missing class com.google.devtools.build.importdeps.testdata.LibraryInterface$One. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client
+Indirectly missing class com.google.devtools.build.importdeps.testdata.LibraryInterface$Two. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client
+Missing member 'bar' in class com.google.devtools.build.importdeps.testdata.Library$Class11 : name=bar, descriptor=()V
+Missing member 'foo' in class com.google.devtools.build.importdeps.testdata.Library$Class11 : name=foo, descriptor=()V
 ===Total===
-missing=4
-incomplete=1
-missing_members=0
+missing=6
+incomplete=2
+missing_members=2
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_interface_missing.txt b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_interface_missing.txt
index 98e939e08e..e8a282b575 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_interface_missing.txt
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_interface_missing.txt
@@ -1,11 +1,22 @@
 Missing com.google.devtools.build.importdeps.testdata.LibraryInterface
 Missing com.google.devtools.build.importdeps.testdata.LibraryInterface$Func
+Missing com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceBar
+Missing com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceFoo
 Missing com.google.devtools.build.importdeps.testdata.LibraryInterface$One
 Missing com.google.devtools.build.importdeps.testdata.LibraryInterface$Two
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client
-    missing ancestor: com.google.devtools.build.importdeps.testdata.LibraryInterface
-    resolution failure path: com.google.devtools.build.importdeps.testdata.LibraryInterface
+Indirectly missing class com.google.devtools.build.importdeps.testdata.LibraryInterface. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client
+Indirectly missing class com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceBar. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Library$Class11
+Indirectly missing class com.google.devtools.build.importdeps.testdata.LibraryInterface$InterfaceFoo. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Library$Class11
+Indirectly missing class com.google.devtools.build.importdeps.testdata.LibraryInterface$One. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client
+Indirectly missing class com.google.devtools.build.importdeps.testdata.LibraryInterface$Two. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client
+Missing member 'bar' in class com.google.devtools.build.importdeps.testdata.Library$Class11 : name=bar, descriptor=()V
+Missing member 'foo' in class com.google.devtools.build.importdeps.testdata.Library$Class11 : name=foo, descriptor=()V
 ===Total===
-missing=4
-incomplete=1
-missing_members=0
+missing=6
+incomplete=2
+missing_members=2
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_missing.stderr.txt b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_missing.stderr.txt
index 4c0f4a9337..0db51a99a7 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_missing.stderr.txt
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_missing.stderr.txt
@@ -4,6 +4,7 @@ The details are listed below:
 Missing com.google.devtools.build.importdeps.testdata.Library
 Missing com.google.devtools.build.importdeps.testdata.Library$Class1
 Missing com.google.devtools.build.importdeps.testdata.Library$Class10
+Missing com.google.devtools.build.importdeps.testdata.Library$Class11
 Missing com.google.devtools.build.importdeps.testdata.Library$Class2
 Missing com.google.devtools.build.importdeps.testdata.Library$Class3
 Missing com.google.devtools.build.importdeps.testdata.Library$Class4
@@ -12,10 +13,9 @@ Missing com.google.devtools.build.importdeps.testdata.Library$Class6
 Missing com.google.devtools.build.importdeps.testdata.Library$Class7
 Missing com.google.devtools.build.importdeps.testdata.Library$Class8
 Missing com.google.devtools.build.importdeps.testdata.Library$Class9
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client
-    missing ancestor: com.google.devtools.build.importdeps.testdata.Library
-    resolution failure path: com.google.devtools.build.importdeps.testdata.Library
+Indirectly missing class com.google.devtools.build.importdeps.testdata.Library. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client
 ===Total===
-missing=11
+missing=12
 incomplete=1
 missing_members=0
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_missing.txt b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_missing.txt
index 79399786a1..fa5e95c6f0 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_missing.txt
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_library_missing.txt
@@ -1,6 +1,7 @@
 Missing com.google.devtools.build.importdeps.testdata.Library
 Missing com.google.devtools.build.importdeps.testdata.Library$Class1
 Missing com.google.devtools.build.importdeps.testdata.Library$Class10
+Missing com.google.devtools.build.importdeps.testdata.Library$Class11
 Missing com.google.devtools.build.importdeps.testdata.Library$Class2
 Missing com.google.devtools.build.importdeps.testdata.Library$Class3
 Missing com.google.devtools.build.importdeps.testdata.Library$Class4
@@ -9,10 +10,9 @@ Missing com.google.devtools.build.importdeps.testdata.Library$Class6
 Missing com.google.devtools.build.importdeps.testdata.Library$Class7
 Missing com.google.devtools.build.importdeps.testdata.Library$Class8
 Missing com.google.devtools.build.importdeps.testdata.Library$Class9
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.Client
-    missing ancestor: com.google.devtools.build.importdeps.testdata.Library
-    resolution failure path: com.google.devtools.build.importdeps.testdata.Library
+Indirectly missing class com.google.devtools.build.importdeps.testdata.Library. Referenced by:
+    com.google.devtools.build.importdeps.testdata.Client
 ===Total===
-missing=11
+missing=12
 incomplete=1
 missing_members=0
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_string_annotation_value_test.stderr.txt b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_string_annotation_value_test.stderr.txt
index 3cc4b3d5ae..fb49176d2b 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_string_annotation_value_test.stderr.txt
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_string_annotation_value_test.stderr.txt
@@ -2,10 +2,12 @@ ERROR: The dependencies for the following 1 jar(s) are not complete.
       1.third_party/bazel/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/libOneAnnotationValue.jar
 The details are listed below:
 Missing java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.StringAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
+Missing java.lang.annotation.Annotation
+Indirectly missing class java.lang.Object. Referenced by:
+    com.google.devtools.build.importdeps.testdata.StringAnnotation
+Indirectly missing class java.lang.annotation.Annotation. Referenced by:
+    com.google.devtools.build.importdeps.testdata.StringAnnotation
 ===Total===
-missing=1
+missing=2
 incomplete=1
 missing_members=0
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_string_annotation_value_test.txt b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_string_annotation_value_test.txt
index b0e898dc35..4699e35478 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_string_annotation_value_test.txt
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/golden_string_annotation_value_test.txt
@@ -1,8 +1,10 @@
 Missing java.lang.Object
-Incomplete ancestor classpath for com.google.devtools.build.importdeps.testdata.StringAnnotation
-    missing ancestor: java.lang.Object
-    resolution failure path: java.lang.Object
+Missing java.lang.annotation.Annotation
+Indirectly missing class java.lang.Object. Referenced by:
+    com.google.devtools.build.importdeps.testdata.StringAnnotation
+Indirectly missing class java.lang.annotation.Annotation. Referenced by:
+    com.google.devtools.build.importdeps.testdata.StringAnnotation
 ===Total===
-missing=1
+missing=2
 incomplete=1
 missing_members=0
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/BUILD b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/BUILD
index 805bb7d6c4..bd8614d3a6 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/BUILD
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/BUILD
@@ -28,11 +28,13 @@ java_library(
 java_library(
     name = "testdata_lib_Library",
     srcs = ["Library.java"],
+    deps = [":testdata_lib_LibraryInterface"],
 )
 
 java_library(
     name = "testdata_lib_Library_no_members",
     srcs = ["library_no_members/com/google/devtools/build/importdeps/testdata/Library.java"],
+    deps = [":testdata_lib_LibraryInterface"],
 )
 
 java_library(
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/Client.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/Client.java
index 419ae82332..2f9d5b17d0 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/Client.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/Client.java
@@ -68,6 +68,10 @@ public class Client<@TypeAnnotation T> extends Library
     System.out.println(array.clone().length);
     Integer b = Integer.valueOf(0);
     System.out.println(b);
+
+    Class11 eleven = new Class11();
+    eleven.foo();
+    eleven.bar();
   }
 
   public void testEnums() {
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/Library.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/Library.java
index 31049ba2d5..0d29fb76dc 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/Library.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/Library.java
@@ -57,4 +57,8 @@ public class Library {
 
   /** A library class for testing. */
   public static class Class10 extends Class9 {}
+
+  /** A library class for testing. */
+  public static class Class11
+      implements LibraryInterface.InterfaceFoo, LibraryInterface.InterfaceBar {}
 }
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/LibraryInterface.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/LibraryInterface.java
index c4e6e07459..b85172cab6 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/LibraryInterface.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/LibraryInterface.java
@@ -34,4 +34,12 @@ public interface LibraryInterface {
   interface Two {
     void callTwo();
   }
+
+  interface InterfaceFoo {
+    default void foo() {}
+  }
+
+  interface InterfaceBar {
+    default void bar() {}
+  }
 }
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/library_no_members/com/google/devtools/build/importdeps/testdata/Library.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/library_no_members/com/google/devtools/build/importdeps/testdata/Library.java
index 991baa0cd7..624ce06dac 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/library_no_members/com/google/devtools/build/importdeps/testdata/Library.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/testdata/library_no_members/com/google/devtools/build/importdeps/testdata/Library.java
@@ -13,6 +13,9 @@
 // limitations under the License.
 package com.google.devtools.build.importdeps.testdata;
 
+import com.google.devtools.build.importdeps.testdata.LibraryInterface.InterfaceBar;
+import com.google.devtools.build.importdeps.testdata.LibraryInterface.InterfaceFoo;
+
 /**
  * A library class for testing. This library class is very similar to {@link Library}, but it does
  * not have any members (fields or methods).
@@ -48,4 +51,7 @@ public class Library {
 
   /** A library class for testing. */
   public static class Class10 extends Class9 {}
+
+  /** A library class for testing. */
+  public static class Class11 implements InterfaceBar, InterfaceFoo {}
 }