When detecting a child subcomponent's superclass implementation, don't assume that that it must be nested directly in the current component's superclass implementation. The child subcomponent builder may have been a pruned binding there, causing no generation of the subcomponent to occur.

RELNOTES=n/a

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=225236202
diff --git a/java/dagger/internal/codegen/ComponentImplementationFactory.java b/java/dagger/internal/codegen/ComponentImplementationFactory.java
index c6095e9..a4f1624 100644
--- a/java/dagger/internal/codegen/ComponentImplementationFactory.java
+++ b/java/dagger/internal/codegen/ComponentImplementationFactory.java
@@ -363,26 +363,26 @@
     }
 
     final ComponentImplementation getChildSuperclassImplementation(ComponentDescriptor child) {
-      // If the current component has a superclass implementation, that superclass
-      // should contain a reference to the child.
-      if (componentImplementation.superclassImplementation().isPresent()) {
-        ComponentImplementation superclassImplementation =
-            componentImplementation.superclassImplementation().get();
+      // If the current component has superclass implementations, a superclass may contain a
+      // reference to the child. Traverse this component's superimplementation hierarchy looking for
+      // the child's implementation. The child superclass implementation may not be present in the
+      // direct superclass implementations if the subcomponent builder was previously a pruned
+      // binding.
+      Optional<ComponentImplementation> currentSuperclassImplementation =
+          componentImplementation.superclassImplementation();
+      while (currentSuperclassImplementation.isPresent()) {
         Optional<ComponentImplementation> childSuperclassImplementation =
-            superclassImplementation.childImplementation(child);
-        checkState(
-            childSuperclassImplementation.isPresent(),
-            "Cannot find abstract implementation of %s within %s while generating implemention "
-                + "within %s",
-            child.typeElement(),
-            superclassImplementation.name(),
-            componentImplementation.name());
-        return childSuperclassImplementation.get();
+            currentSuperclassImplementation.get().childImplementation(child);
+        if (childSuperclassImplementation.isPresent()) {
+          return childSuperclassImplementation.get();
+        }
+        currentSuperclassImplementation =
+            currentSuperclassImplementation.get().superclassImplementation();
       }
 
-      // Otherwise, the enclosing component is top-level, so we must recreate the implementation
-      // object for the base implementation of the child by truncating the binding graph at the
-      // child.
+      // Otherwise, the superclass implementation is top-level, so we must recreate the
+      // implementation object for the base implementation of the child by truncating the binding
+      // graph at the child.
       BindingGraph truncatedBindingGraph = bindingGraphFactory.create(child);
       return createComponentImplementation(truncatedBindingGraph);
     }
diff --git a/javatests/dagger/internal/codegen/AheadOfTimeSubcomponentsTest.java b/javatests/dagger/internal/codegen/AheadOfTimeSubcomponentsTest.java
index 2a39f24..28237b4 100644
--- a/javatests/dagger/internal/codegen/AheadOfTimeSubcomponentsTest.java
+++ b/javatests/dagger/internal/codegen/AheadOfTimeSubcomponentsTest.java
@@ -6880,6 +6880,155 @@
         .hasSourceEquivalentTo(generatedAncestor);
   }
 
+  /**
+   * This test verifies that Dagger can find the appropriate child subcomponent
+   * super-implementation, even if it is not enclosed in the current component's
+   * super-implementation. This can happen if a subcomponent is installed with a module's {@code
+   * subcomponents} attribute, but the binding is not accessed in a super-implementation. To exhibit
+   * this, we use multibindings that reference the pruned subcomponent, but make the multibinding
+   * also unresolved in the base implementation. An ancestor component defines a binding that
+   * depends on the multibinding, which induces the previously unresolved multibinding
+   * contributions, which itself induces the previously unresolved subcomponent.
+   */
+  @Test
+  public void subcomponentInducedFromAncestor() {
+    ImmutableList.Builder<JavaFileObject> filesToCompile = ImmutableList.builder();
+    createAncillaryClasses(filesToCompile, "Inducer");
+    filesToCompile.add(
+        JavaFileObjects.forSourceLines(
+            "test.InducedSubcomponent",
+            "package test;",
+            "",
+            "import dagger.Subcomponent;",
+            "",
+            "@Subcomponent",
+            "interface InducedSubcomponent {",
+            "  @Subcomponent.Builder",
+            "  interface Builder {",
+            "    InducedSubcomponent build();",
+            "  }",
+            "}"),
+        JavaFileObjects.forSourceLines(
+            "test.MaybeLeaf",
+            "package test;",
+            "",
+            "import dagger.Subcomponent;",
+            "",
+            "@Subcomponent(modules = InducedSubcomponentModule.class)",
+            "interface MaybeLeaf {",
+            "  Inducer inducer();",
+            "}"),
+        JavaFileObjects.forSourceLines(
+            "test.MaybeLeaf",
+            "package test;",
+            "",
+            "import dagger.Module;",
+            "import dagger.Provides;",
+            "import dagger.multibindings.IntoSet;",
+            "",
+            "@Module(subcomponents = InducedSubcomponent.class)",
+            "interface InducedSubcomponentModule {",
+            "  @Provides",
+            "  @IntoSet",
+            "  static Object inducedSet(InducedSubcomponent.Builder builder) {",
+            "    return new Object();",
+            "  }",
+            "}"));
+
+    JavaFileObject generatedMaybeLeaf =
+        JavaFileObjects.forSourceLines(
+            "test.DaggerLeaf",
+            "package test;",
+            "",
+            IMPORT_GENERATED_ANNOTATION,
+            "",
+            GENERATED_ANNOTATION,
+            "public abstract class DaggerMaybeLeaf implements MaybeLeaf {",
+            "  protected DaggerMaybeLeaf() {}",
+            "}");
+    Compilation compilation = compile(filesToCompile.build());
+    assertThat(compilation).succeededWithoutWarnings();
+    assertThat(compilation)
+        .generatedSourceFile("test.DaggerMaybeLeaf")
+        .hasSourceEquivalentTo(generatedMaybeLeaf);
+
+    filesToCompile.add(
+        JavaFileObjects.forSourceLines(
+            "test.AncestorModule",
+            "package test;",
+            "",
+            "import dagger.Module;",
+            "import dagger.Provides;",
+            "import dagger.multibindings.Multibinds;",
+            "import java.util.Set;",
+            "",
+            "@Module",
+            "interface AncestorModule {",
+            "  @Provides",
+            "  static Inducer inducer(Set<Object> set) {",
+            "    return null;",
+            "  }",
+            "",
+            "  @Multibinds Set<Object> set();",
+            "}"),
+        JavaFileObjects.forSourceLines(
+            "test.Ancestor",
+            "package test;",
+            "",
+            "import dagger.Subcomponent;",
+            "",
+            "@Subcomponent(modules = AncestorModule.class)",
+            "interface Ancestor {",
+            "  MaybeLeaf noLongerLeaf();",
+            "}"));
+
+    JavaFileObject generatedAncestor =
+        JavaFileObjects.forSourceLines(
+            "test.DaggerAncestor",
+            "package test;",
+            "",
+            "import com.google.common.collect.ImmutableSet;",
+            "import java.util.Set;",
+            IMPORT_GENERATED_ANNOTATION,
+            "",
+            GENERATED_ANNOTATION,
+            "public abstract class DaggerAncestor implements Ancestor {",
+            "  protected DaggerAncestor() {}",
+            "",
+            "  protected abstract class MaybeLeafImpl extends DaggerMaybeLeaf {",
+            "    protected MaybeLeafImpl() {}",
+            "",
+            "    private Object getObject() {",
+            "      return InducedSubcomponentModule_InducedSetFactory.proxyInducedSet(",
+            "          getInducedSubcomponentBuilder());",
+            "    }",
+            "",
+            "    protected abstract Object getInducedSubcomponentBuilder();",
+            "",
+            "    protected Set<Object> getSetOfObject() {",
+            "      return ImmutableSet.<Object>of(getObject());",
+            "    }",
+            "",
+            "    @Override",
+            "    public final Inducer inducer() {",
+            "      return AncestorModule_InducerFactory.proxyInducer(getSetOfObject());",
+            "    }",
+            "",
+            "    protected abstract class InducedSubcomponentImpl extends",
+            "        DaggerInducedSubcomponent {",
+            //       ^ Note that this is DaggerInducedSubcomponent, not
+            //         DaggerMaybeLeaf.InducedSubcomponentImpl
+            "      protected InducedSubcomponentImpl() {}",
+            "    }",
+            "  }",
+            "}");
+    compilation = compile(filesToCompile.build());
+    assertThat(compilation).succeededWithoutWarnings();
+    assertThat(compilation)
+        .generatedSourceFile("test.DaggerAncestor")
+        .hasSourceEquivalentTo(generatedAncestor);
+  }
+
   private void createAncillaryClasses(
       ImmutableList.Builder<JavaFileObject> filesBuilder, String... ancillaryClasses) {
     for (String className : ancillaryClasses) {