// Copyright 2017 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.android.desugar;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSortedSet;
import com.google.devtools.build.android.desugar.io.BitFlags;
import java.lang.reflect.Method;
import java.lang.reflect.Modifier;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.TreeMap;
import javax.annotation.Nullable;
import org.objectweb.asm.ClassReader;
import org.objectweb.asm.ClassVisitor;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
import org.objectweb.asm.Type;
import org.objectweb.asm.tree.AbstractInsnNode;
import org.objectweb.asm.tree.InsnList;
import org.objectweb.asm.tree.InsnNode;
import org.objectweb.asm.tree.MethodInsnNode;
import org.objectweb.asm.tree.MethodNode;

/**
 * Fixer of classes that extend interfaces with default methods to declare any missing methods
 * explicitly and call the corresponding companion method generated by {@link InterfaceDesugaring}.
 */
public class DefaultMethodClassFixer extends ClassVisitor {

  private final boolean useGeneratedBaseClasses;
  private final ClassReaderFactory classpath;
  private final ClassReaderFactory bootclasspath;
  private final ClassLoader targetLoader;
  private final DependencyCollector depsCollector;
  @Nullable private final CoreLibrarySupport coreLibrarySupport;
  private final LinkedHashSet<String> instanceMethods = new LinkedHashSet<>();

  private boolean isInterface;
  private String internalName;
  private ImmutableList<String> directInterfaces;
  private String superName;
  /** Interface whose companion was chosen as base class, if any. */
  @Nullable private Class<?> newSuperName;
  /** This method node caches <clinit>, and flushes out in {@code visitEnd()}; */
  private MethodNode clInitMethodNode;

  private ImmutableSortedSet<Class<?>> interfacesToStub;

  public DefaultMethodClassFixer(
      ClassVisitor dest,
      boolean useGeneratedBaseClasses,
      ClassReaderFactory classpath,
      DependencyCollector depsCollector,
      @Nullable CoreLibrarySupport coreLibrarySupport,
      ClassReaderFactory bootclasspath,
      ClassLoader targetLoader) {
    super(Opcodes.ASM7, dest);
    this.useGeneratedBaseClasses = useGeneratedBaseClasses;
    this.classpath = classpath;
    this.coreLibrarySupport = coreLibrarySupport;
    this.bootclasspath = bootclasspath;
    this.targetLoader = targetLoader;
    this.depsCollector = depsCollector;
  }

  @Override
  public void visit(
      int version,
      int access,
      String name,
      String signature,
      String superName,
      String[] interfaces) {
    checkState(this.directInterfaces == null);
    isInterface = BitFlags.isSet(access, Opcodes.ACC_INTERFACE);
    internalName = name;
    checkArgument(
        superName != null || "java/lang/Object".equals(name), // ASM promises this
        "Type without superclass: %s",
        name);
    this.directInterfaces = ImmutableList.copyOf(interfaces);
    this.superName = superName;

    if (!isInterface
        && (mayNeedInterfaceStubsForEmulatedSuperclass()
            || defaultMethodsDefined(directInterfaces))) {
      TreeMap<Class<?>, Long> allInterfaces = new TreeMap<>(SubtypeComparator.INSTANCE);
      for (String direct : interfaces) {
        if (InterfaceDesugaring.getCompanionClassName(direct).equals(name)) {
          checkState(useGeneratedBaseClasses, "%s shouldn't implement %s", name, direct);
          continue; // InterfaceDesugaring already made stubs for this interface
        }
        // Loading ensures all transitively implemented interfaces can be loaded, which is necessary
        // to produce correct default method stubs in all cases.  We could do without classloading
        // but it's convenient to rely on Class.isAssignableFrom to compute subtype relationships,
        // and we'd still have to insist that all transitively implemented interfaces can be loaded.
        // We don't load the visited class, however, in case it's generated.
        Class<?> itf = loadFromInternal(direct);
        collectInterfaces(itf, allInterfaces);
      }
      if (mayNeedInterfaceStubsForEmulatedSuperclass()) {
        // Collect interfaces inherited from emulated superclasses as well, to handle things like
        // extending AbstractList without explicitly implementing List.
        for (Class<?> clazz = loadFromInternal(superName);
            clazz != null;
            clazz = clazz.getSuperclass()) {
          for (Class<?> itf : clazz.getInterfaces()) {
            collectInterfaces(itf, allInterfaces);
          }
        }
      }

      if (useGeneratedBaseClasses && "java/lang/Object".equals(superName)) {
        // If the class directly extends Object, use the generated base class for the interface with
        // the most default methods instead.  This can help avoid stubbed default methods when
        // they're already defined in the base class.
        // This is an imperfect heuristic, not least b/c we don't know yet what methods would need
        // to be stubbed, but we decide this here up-front b/c that lets us fix up the class's
        // constructors' super calls when we see them.
        // Note inherited default methods are included in the count, so we will choose subtypes over
        // supertypes, which is desirable.
        long maxBaseMethodCount = 0;
        for (Map.Entry<Class<?>, Long> itf : allInterfaces.entrySet()) {
          if (itf.getValue() > maxBaseMethodCount) {
            maxBaseMethodCount = itf.getValue();
            newSuperName = itf.getKey();
            superName = InterfaceDesugaring.getCompanionClassName(internalName(itf.getKey()));
            signature = null; // Changing superclass invalidates signature
          }
        }
        if (newSuperName != null && !bootclasspath.isKnown(internalName(newSuperName))) {
          // Record dependency on the chosen companion class
          depsCollector.assumeCompanionClass(
              internalName, InterfaceDesugaring.getCompanionClassName(internalName(newSuperName)));
        }
      }
      interfacesToStub = ImmutableSortedSet.copyOfSorted(allInterfaces.navigableKeySet());
    } else {
      interfacesToStub = ImmutableSortedSet.of();
    }
    super.visit(version, access, name, signature, superName, interfaces);
  }

  @Override
  public void visitEnd() {
    if (!interfacesToStub.isEmpty()) {
      // Inherited methods take precedence over default methods, so visit all superclasses and
      // figure out what methods they declare before stubbing in any missing default methods.
      recordInheritedMethods();
      stubMissingDefaultAndBridgeMethods();
      // Check whether there are interfaces with default methods and <clinit>. If yes, the following
      // method call will return a list of interface fields to access in the <clinit> to trigger
      // the initialization of these interfaces.
      ImmutableList<String> companionsToTriggerInterfaceClinit =
          collectOrderedCompanionsToTriggerInterfaceClinit(directInterfaces);
      if (!companionsToTriggerInterfaceClinit.isEmpty()) {
        if (clInitMethodNode == null) {
          clInitMethodNode = new MethodNode(Opcodes.ACC_STATIC, "<clinit>", "()V", null, null);
        }
        desugarClinitToTriggerInterfaceInitializers(companionsToTriggerInterfaceClinit);
      }
    }
    if (clInitMethodNode != null && super.cv != null) { // Write <clinit> to the chained visitor.
      clInitMethodNode.accept(super.cv);
    }
    super.visitEnd();
  }

  private boolean isClinitAlreadyDesugared(
      ImmutableList<String> companionsToAccessToTriggerInterfaceClinit) {
    InsnList instructions = clInitMethodNode.instructions;
    if (instructions.size() <= companionsToAccessToTriggerInterfaceClinit.size()) {
      // The <clinit> must end with RETURN, so if the instruction count is less than or equal to
      // the companion class count, this <clinit> has not been desugared.
      return false;
    }
    Iterator<AbstractInsnNode> iterator = instructions.iterator();
    for (String companion : companionsToAccessToTriggerInterfaceClinit) {
      if (!iterator.hasNext()) {
        return false;
      }
      AbstractInsnNode insn = iterator.next();
      if (!(insn instanceof MethodInsnNode)) {
        return false;
      }
      MethodInsnNode methodInsnNode = (MethodInsnNode) insn;
      if (methodInsnNode.getOpcode() != Opcodes.INVOKESTATIC
          || !methodInsnNode.owner.equals(companion)
          || !methodInsnNode.name.equals(
              InterfaceDesugaring.COMPANION_METHOD_TO_TRIGGER_INTERFACE_CLINIT_NAME)) {
        return false;
      }
      checkState(
          methodInsnNode.desc.equals(
              InterfaceDesugaring.COMPANION_METHOD_TO_TRIGGER_INTERFACE_CLINIT_DESC),
          "Inconsistent method desc: %s vs %s",
          methodInsnNode.desc,
          InterfaceDesugaring.COMPANION_METHOD_TO_TRIGGER_INTERFACE_CLINIT_DESC);
    }
    return true;
  }

  private void desugarClinitToTriggerInterfaceInitializers(
      ImmutableList<String> companionsToTriggerInterfaceClinit) {
    if (isClinitAlreadyDesugared(companionsToTriggerInterfaceClinit)) {
      return;
    }
    InsnList desugarInsts = new InsnList();
    for (String companionClass : companionsToTriggerInterfaceClinit) {
      desugarInsts.add(
          new MethodInsnNode(
              Opcodes.INVOKESTATIC,
              companionClass,
              InterfaceDesugaring.COMPANION_METHOD_TO_TRIGGER_INTERFACE_CLINIT_NAME,
              InterfaceDesugaring.COMPANION_METHOD_TO_TRIGGER_INTERFACE_CLINIT_DESC,
              false));
    }
    if (clInitMethodNode.instructions.size() == 0) {
      clInitMethodNode.instructions.insert(new InsnNode(Opcodes.RETURN));
    }
    clInitMethodNode.instructions.insertBefore(
        clInitMethodNode.instructions.getFirst(), desugarInsts);
  }

  @Override
  public MethodVisitor visitMethod(
      int access, String name, String desc, String signature, String[] exceptions) {
    // Keep track of instance methods implemented in this class for later.
    if (!isInterface) {
      recordIfInstanceMethod(access, name, desc);
    }
    if ("<clinit>".equals(name)) {
      checkState(clInitMethodNode == null, "This class fixer has been used. ");
      clInitMethodNode = new MethodNode(access, name, desc, signature, exceptions);
      return clInitMethodNode;
    }

    MethodVisitor dest = super.visitMethod(access, name, desc, signature, exceptions);
    if (newSuperName != null && "<init>".equals(name)) {
      // Since we changed the base class we need to fix up super constructor calls.
      return new ConstructorFixer(
          dest, InterfaceDesugaring.getCompanionClassName(internalName(newSuperName)));
    }
    return dest;
  }

  private boolean mayNeedInterfaceStubsForEmulatedSuperclass() {
    return coreLibrarySupport != null
        && !coreLibrarySupport.isEmulatedCoreClassOrInterface(internalName)
        && coreLibrarySupport.isEmulatedCoreClassOrInterface(superName);
  }

  private void stubMissingDefaultAndBridgeMethods() {
    Class<?> superclass = loadFromInternal(superName);
    boolean mayNeedStubsForSuperclass = mayNeedInterfaceStubsForEmulatedSuperclass();
    for (Class<?> interfaceToVisit : interfacesToStub) {
      // if J extends I, J is allowed to redefine I's default methods.  The comparator we used
      // above makes sure we visit J before I in that case so we can use J's definition.
      if (!mayNeedStubsForSuperclass && interfaceToVisit.isAssignableFrom(superclass)) {
        // superclass is also rewritten and already implements this interface, so we _must_ skip it.
        continue;
      }
      stubMissingDefaultAndBridgeMethods(internalName(interfaceToVisit), mayNeedStubsForSuperclass);
    }
  }

  private void stubMissingDefaultAndBridgeMethods(
      String implemented, boolean mayNeedStubsForSuperclass) {
    ClassReader bytecode;
    boolean isBootclasspath;
    if (bootclasspath.isKnown(implemented)) {
      if (coreLibrarySupport != null
          && (coreLibrarySupport.isRenamedCoreLibrary(implemented)
              || coreLibrarySupport.isEmulatedCoreClassOrInterface(implemented))) {
        bytecode = checkNotNull(bootclasspath.readIfKnown(implemented), implemented);
        isBootclasspath = true;
      } else {
        // Default methods from interfaces on the bootclasspath that we're not renaming or emulating
        // are assumed available at runtime, so just ignore them.
        return;
      }
    } else {
      bytecode =
          checkNotNull(
              classpath.readIfKnown(implemented),
              "Couldn't find interface %s implemented by %s",
              implemented,
              internalName);
      isBootclasspath = false;
    }
    bytecode.accept(
        new DefaultMethodStubber(isBootclasspath, mayNeedStubsForSuperclass),
        ClassReader.SKIP_DEBUG);
  }

  private Class<?> loadFromInternal(String internalName) {
    try {
      return targetLoader.loadClass(internalName.replace('/', '.'));
    } catch (ClassNotFoundException | NoClassDefFoundError e) {
      throw new IllegalStateException(
          "Couldn't load " + internalName + " to stub default methods for " + this.internalName, e);
    }
  }

  /** Returns the internal name used for this class in bytecode. */
  static String internalName(Class<?> clazz) {
    return clazz.getName().replace('.', '/');
  }

  private void collectInterfaces(Class<?> itf, Map<Class<?>, Long> dest) {
    checkArgument(itf.isInterface());
    if (dest.containsKey(itf)) {
      return;
    }
    if (useGeneratedBaseClasses && hasCompanionClass(itf)) {
      // Count inherited and declared default methods
      long defaultMethodCount = Arrays.stream(itf.getMethods()).filter(Method::isDefault).count();
      dest.put(itf, defaultMethodCount);
    } else {
      // Use -1 if there's no base class we could use.  This makes sure we don't try to use a
      // companion class as base class that doesn't exist.
      dest.put(itf, -1L);
    }
    for (Class<?> implemented : itf.getInterfaces()) {
      collectInterfaces(implemented, dest);
    }
  }

  private boolean hasCompanionClass(Class<?> itf) {
    checkArgument(itf.isInterface());
    if (Arrays.stream(itf.getDeclaredMethods()).noneMatch(m -> m.isDefault() && !m.isBridge())) {
      return false;
    }
    String implemented = internalName(itf);
    if (implemented.startsWith("java/") || implemented.startsWith("__desugar__/java/")) {
      return coreLibrarySupport != null
          && (coreLibrarySupport.isRenamedCoreLibrary(implemented)
              || coreLibrarySupport.isEmulatedCoreClassOrInterface(implemented));
    } else {
      return !bootclasspath.isKnown(implemented);
    }
  }

  private void recordInheritedMethods() {
    InstanceMethodRecorder recorder =
        new InstanceMethodRecorder(mayNeedInterfaceStubsForEmulatedSuperclass());
    if (newSuperName != null) {
      checkState(useGeneratedBaseClasses);
      // If we're using a generated base class, walk the implemented interfaces and record default
      // methods we won't need to stub.  That reflects the methods that will be in the generated
      // base class (and its superclasses, if applicable), without looking at the generated class.
      // We go through sub-interfaces before their super-interfaces (same order as when we stub)
      // to encounter overriding before overridden default methods.  We don't record methods from
      // interfaces the chosen base class doesn't implement, even if those methods also appear in
      // interfaces we would normally record later.  That ensures we generate a stub when a default
      // method is available in the base class but needs to be overridden due to an overriding
      // default method in a sub-interface not implemented by the base class.
      LinkedHashSet<String> allSeen = new LinkedHashSet<>();
      for (Class<?> itf : interfacesToStub) {
        boolean willBeInBaseClass = itf.isAssignableFrom(newSuperName);
        for (Method m : itf.getDeclaredMethods()) {
          if (!m.isDefault()) {
            continue;
          }
          String desc = Type.getMethodDescriptor(m);
          if (coreLibrarySupport != null) {
            // Foreshadow any type renaming to avoid issues with double-desugaring (b/111447199)
            desc = coreLibrarySupport.getRemapper().mapMethodDesc(desc);
          }
          String methodKey = m.getName() + ":" + desc;
          if (allSeen.add(methodKey) && willBeInBaseClass) {
            // Only record never-seen methods, and only for super-types of newSuperName (see longer
            // explanation above)
            instanceMethods.add(methodKey);
          }
        }
      }

      // Fall through to the logic below to record j.l.Object's methods.
      checkState(superName.equals("java/lang/Object"));
    }

    // Walk superclasses
    String internalName = superName;
    while (internalName != null) {
      ClassReader bytecode = bootclasspath.readIfKnown(internalName);
      if (bytecode == null) {
        bytecode =
            checkNotNull(
                classpath.readIfKnown(internalName), "Superclass not found: %s", internalName);
      }
      bytecode.accept(recorder, ClassReader.SKIP_CODE | ClassReader.SKIP_DEBUG);
      internalName = bytecode.getSuperName();
    }
  }

  /**
   * Starting from the given interfaces, this method scans the interface hierarchy, finds the
   * interfaces that have default methods and <clinit>, and returns the companion class names of
   * these interfaces.
   *
   * <p>Note that the returned companion classes are ordered in the order of the interface
   * initialization, which is consistent with the JVM behavior. For example, "class A implements I1,
   * I2", the returned list would be [I1$$CC, I2$$CC], not [I2$$CC, I1$$CC].
   */
  private ImmutableList<String> collectOrderedCompanionsToTriggerInterfaceClinit(
      ImmutableList<String> interfaces) {
    ImmutableList.Builder<String> companionCollector = ImmutableList.builder();
    LinkedHashSet<String> visitedInterfaces = new LinkedHashSet<>();
    for (String anInterface : interfaces) {
      collectOrderedCompanionsToTriggerInterfaceClinit(
          anInterface, visitedInterfaces, companionCollector);
    }
    return companionCollector.build();
  }

  private void collectOrderedCompanionsToTriggerInterfaceClinit(
      String anInterface,
      LinkedHashSet<String> visitedInterfaces,
      ImmutableList.Builder<String> companionCollector) {
    if (!visitedInterfaces.add(anInterface)) {
      return;
    }
    ClassReader bytecode = classpath.readIfKnown(anInterface);
    if (bytecode == null || bootclasspath.isKnown(anInterface)) {
      return;
    }
    String[] parentInterfaces = bytecode.getInterfaces();
    if (parentInterfaces != null && parentInterfaces.length > 0) {
      for (String parentInterface : parentInterfaces) {
        collectOrderedCompanionsToTriggerInterfaceClinit(
            parentInterface, visitedInterfaces, companionCollector);
      }
    }
    InterfaceInitializationNecessityDetector necessityDetector =
        new InterfaceInitializationNecessityDetector(bytecode.getClassName());
    bytecode.accept(necessityDetector, ClassReader.SKIP_DEBUG);
    if (necessityDetector.needsToInitialize()) {
      // If we need to initialize this interface, we initialize its companion class, and its
      // companion class will initialize the interface then. This desigin decision is made to avoid
      // access issue, e.g., package-private interfaces.
      companionCollector.add(InterfaceDesugaring.getCompanionClassName(anInterface));
    }
  }

  /**
   * Recursively searches the given interfaces for default methods not implemented by this class
   * directly. If this method returns true we need to think about stubbing missing default methods.
   */
  private boolean defaultMethodsDefined(ImmutableList<String> interfaces) {
    for (String implemented : interfaces) {
      if (useGeneratedBaseClasses
          && InterfaceDesugaring.getCompanionClassName(implemented).equals(internalName)) {
        continue; // InterfaceDesugaring already made stubs for this interface
      }
      ClassReader bytecode;
      if (bootclasspath.isKnown(implemented)) {
        if (coreLibrarySupport != null
            && coreLibrarySupport.isEmulatedCoreClassOrInterface(implemented)) {
          return true; // need to stub in emulated interface methods such as Collection.stream()
        } else if (coreLibrarySupport != null
            && coreLibrarySupport.isRenamedCoreLibrary(implemented)) {
          // Check default methods of renamed interfaces
          bytecode = checkNotNull(bootclasspath.readIfKnown(implemented), implemented);
        } else {
          continue;
        }
      } else {
        bytecode = classpath.readIfKnown(implemented);
        if (bytecode == null) {
          // Interface isn't on the classpath, which indicates incomplete classpaths. Record missing
          // dependency so we can check it later.  If we don't check then we may get runtime
          // failures or wrong behavior from default methods that should've been stubbed in.
          // TODO(kmb): Print a warning so people can start fixing their deps?
          depsCollector.missingImplementedInterface(internalName, implemented);
          continue;
        }
      }

      // Class in classpath and bootclasspath is a bad idea but in any event, assume the
      // bootclasspath will take precedence like in a classloader.
      // We can skip code attributes as we just need to find default methods to stub.
      DefaultMethodFinder finder = new DefaultMethodFinder();
      bytecode.accept(finder, ClassReader.SKIP_CODE | ClassReader.SKIP_DEBUG);
      if (finder.foundDefaultMethods()) {
        return true;
      }
    }
    return false;
  }

  /** Returns {@code true} for non-bridge default methods not in {@link #instanceMethods}. */
  private boolean shouldStubAsDefaultMethod(int access, String name, String desc) {
    // Ignore private methods, which technically aren't default methods and can only be called from
    // other methods defined in the interface.  This also ignores lambda body methods, which is fine
    // as we don't want or need to stub those.  Also ignore bridge methods as javac adds them to
    // concrete classes as needed anyway and we handle them separately for generated lambda classes.
    // Note that an exception is that, if a bridge method is for a default interface method, javac
    // will NOT generate the bridge method in the implementing class. So we need extra logic to
    // handle these bridge methods.
    return isNonBridgeDefaultMethod(access) && !recordedInstanceMethod(name, desc);
  }

  private static boolean isNonBridgeDefaultMethod(int access) {
    return BitFlags.noneSet(
        access,
        Opcodes.ACC_ABSTRACT | Opcodes.ACC_STATIC | Opcodes.ACC_BRIDGE | Opcodes.ACC_PRIVATE);
  }

  /**
   * Check whether an interface method is a bridge method for a default interface method. This type
   * of bridge methods is special, as they are not put in the implementing classes by javac.
   */
  private boolean shouldStubAsBridgeDefaultMethod(int access, String name, String desc) {
    return BitFlags.isSet(access, Opcodes.ACC_BRIDGE | Opcodes.ACC_PUBLIC)
        && BitFlags.noneSet(access, Opcodes.ACC_ABSTRACT | Opcodes.ACC_STATIC)
        && !recordedInstanceMethod(name, desc);
  }

  private void recordIfInstanceMethod(int access, String name, String desc) {
    if (BitFlags.noneSet(access, Opcodes.ACC_STATIC)) {
      // Record all declared instance methods, including abstract, bridge, and native methods, as
      // they all take precedence over default methods.
      if (coreLibrarySupport != null) {
        // Foreshadow any type renaming to avoid issues with double-desugaring (b/111447199)
        desc = coreLibrarySupport.getRemapper().mapMethodDesc(desc);
      }
      instanceMethods.add(name + ":" + desc);
    }
  }

  private boolean recordedInstanceMethod(String name, String desc) {
    if (coreLibrarySupport != null) {
      // Foreshadow any type renaming to avoid issues with double-desugaring (b/111447199)
      desc = coreLibrarySupport.getRemapper().mapMethodDesc(desc);
    }
    return instanceMethods.contains(name + ":" + desc);
  }

  /**
   * Visitor for interfaces that produces delegates in the class visited by the outer {@link
   * DefaultMethodClassFixer} for every default method encountered.
   */
  private class DefaultMethodStubber extends ClassVisitor {

    private final boolean isBootclasspathInterface;
    private final boolean mayNeedStubsForSuperclass;

    private String stubbedInterfaceName;

    public DefaultMethodStubber(
        boolean isBootclasspathInterface, boolean mayNeedStubsForSuperclass) {
      super(Opcodes.ASM7);
      this.isBootclasspathInterface = isBootclasspathInterface;
      this.mayNeedStubsForSuperclass = mayNeedStubsForSuperclass;
    }

    @Override
    public void visit(
        int version,
        int access,
        String name,
        String signature,
        String superName,
        String[] interfaces) {
      checkArgument(BitFlags.isSet(access, Opcodes.ACC_INTERFACE));
      checkState(stubbedInterfaceName == null);
      stubbedInterfaceName = name;
    }

    @Override
    public MethodVisitor visitMethod(
        int access, String name, String desc, String signature, String[] exceptions) {
      if (shouldStubAsDefaultMethod(access, name, desc)) {
        // Remember we stubbed this method in case it's also defined by subsequently visited
        // interfaces.  javac would force the method to be defined explicitly if there any two
        // definitions conflict, but see stubMissingDefaultMethods() for how we deal with default
        // methods redefined in interfaces extending another.
        recordIfInstanceMethod(access, name, desc);
        String owner = InterfaceDesugaring.getCompanionClassName(stubbedInterfaceName);
        if (!isBootclasspathInterface) {
          // Don't record these dependencies, as we can't check them
          depsCollector.assumeCompanionClass(internalName, owner);
        }

        // Add this method to the class we're desugaring and stub in a body to call the default
        // implementation in the interface's companion class. ijar omits these methods when setting
        // ACC_SYNTHETIC modifier, so don't.
        // Signatures can be wrong, e.g., when type variables are introduced, instantiated, or
        // refined in the class we're processing, so drop them.
        MethodVisitor stubMethod =
            DefaultMethodClassFixer.this.visitMethod(access, name, desc, (String) null, exceptions);

        String receiverName = stubbedInterfaceName;
        String calledMethodName = name + InterfaceDesugaring.DEFAULT_COMPANION_METHOD_SUFFIX;
        if (mayNeedStubsForSuperclass) {
          // Reflect what CoreLibraryInvocationRewriter would do if it encountered a super-call to a
          // moved implementation of an emulated method.  Equivalent to emitting the invokespecial
          // super call here and relying on CoreLibraryInvocationRewriter for the rest
          Class<?> emulatedImplementation =
              coreLibrarySupport.getCoreInterfaceRewritingTarget(
                  Opcodes.INVOKESPECIAL, superName, name, desc, /*itf=*/ false);
          if (emulatedImplementation != null && !emulatedImplementation.isInterface()) {
            receiverName = internalName(emulatedImplementation);
            owner = checkNotNull(coreLibrarySupport.getMoveTarget(receiverName, name));
            calledMethodName = name;
          }
        }

        int slot = 0;
        stubMethod.visitVarInsn(Opcodes.ALOAD, slot++); // load the receiver
        Type neededType = Type.getMethodType(desc);
        for (Type arg : neededType.getArgumentTypes()) {
          stubMethod.visitVarInsn(arg.getOpcode(Opcodes.ILOAD), slot);
          slot += arg.getSize();
        }
        stubMethod.visitMethodInsn(
            Opcodes.INVOKESTATIC,
            owner,
            calledMethodName,
            InterfaceDesugaring.companionDefaultMethodDescriptor(receiverName, desc),
            /*isInterface=*/ false);
        stubMethod.visitInsn(neededType.getReturnType().getOpcode(Opcodes.IRETURN));

        stubMethod.visitMaxs(0, 0); // rely on class writer to compute these
        stubMethod.visitEnd();
        return null; // don't visit the visited interface's default method
      } else if (shouldStubAsBridgeDefaultMethod(access, name, desc)) {
        recordIfInstanceMethod(access, name, desc);
        MethodVisitor stubMethod =
            DefaultMethodClassFixer.this.visitMethod(access, name, desc, (String) null, exceptions);
        // If we're visiting a bootclasspath interface then we most likely don't have the code.
        // That means we can't just copy the method bodies as we're trying to do below.
        if (isBootclasspathInterface) {
          // Synthesize a "bridge" method that calls the true implementation
          Method bridged = findBridgedMethod(name, desc);
          checkState(
              bridged != null,
              "TODO: Can't stub core interface bridge method %s.%s %s in %s",
              stubbedInterfaceName,
              name,
              desc,
              internalName);

          int slot = 0;
          stubMethod.visitVarInsn(Opcodes.ALOAD, slot++); // load the receiver
          Type neededType = Type.getType(bridged);
          Type[] neededArgTypes = neededType.getArgumentTypes();
          Type[] parameterTypes = Type.getArgumentTypes(desc);
          for (int i = 0; i < neededArgTypes.length; ++i) {
            Type arg = neededArgTypes[i];
            stubMethod.visitVarInsn(arg.getOpcode(Opcodes.ILOAD), slot);
            if (!arg.equals(parameterTypes[i])) {
              checkState(
                  arg.getSort() == Type.ARRAY || arg.getSort() == Type.OBJECT,
                  "Can't cast parameter %s from in bridge for %s.%s%s to %s",
                  i,
                  stubbedInterfaceName,
                  name,
                  desc,
                  arg.getClassName());
              stubMethod.visitTypeInsn(Opcodes.CHECKCAST, arg.getInternalName());
            }
            slot += arg.getSize();
          }
          // Just call the bridged method directly on the visited class using invokevirtual
          stubMethod.visitMethodInsn(
              Opcodes.INVOKEVIRTUAL,
              internalName,
              name,
              neededType.getDescriptor(),
              /*isInterface=*/ false);
          stubMethod.visitInsn(neededType.getReturnType().getOpcode(Opcodes.IRETURN));

          stubMethod.visitMaxs(0, 0); // rely on class writer to compute these
          stubMethod.visitEnd();
          return null; // don't visit the visited interface's bridge method
        } else {
          // For bridges we just copy their bodies instead of going through the companion class.
          // Meanwhile, we also need to desugar the copied method bodies, so that any calls to
          // interface methods are correctly handled.
          return new InterfaceDesugaring.InterfaceInvocationRewriter(
              stubMethod,
              stubbedInterfaceName,
              bootclasspath,
              targetLoader,
              depsCollector,
              internalName);
        }
      } else {
        return null; // not a default or bridge method or the class already defines this method.
      }
    }

    /**
     * Returns a non-bridge interface method with given name that a method with the given descriptor
     * can bridge to, if any such method can be found.
     */
    @Nullable
    private Method findBridgedMethod(String name, String desc) {
      Type[] paramTypes = Type.getArgumentTypes(desc);
      Type returnType = Type.getReturnType(desc);
      Class<?> itf = loadFromInternal(stubbedInterfaceName);
      checkArgument(itf.isInterface(), "Should be an interface: %s", stubbedInterfaceName);

      // 1. Find the bridge method we're trying to implement
      Method bridge = null;
      for (Method m : itf.getDeclaredMethods()) {
        if (m.isBridge()
            && m.getName().equals(name)
            && Arrays.equals(paramTypes, Type.getArgumentTypes(m))
            && returnType.equals(Type.getReturnType(m))) {
          bridge = m;
          break;
        }
      }
      checkState(bridge != null, "Couldn't find bridge %s.%s %s", stubbedInterfaceName, name, desc);
      checkState(bridge.getParameterCount() == paramTypes.length);

      // 2. Try to find the method being bridged
      Method result = null;
      next_method:
      for (Method m : itf.getDeclaredMethods()) {
        if (m.isBridge() || Modifier.isStatic(m.getModifiers())) {
          continue;
        }
        if (!m.getName().equals(name)) {
          continue;
        }

        if (Arrays.equals(paramTypes, Type.getArgumentTypes(m))) {
          // All argument types match, only return type will differ: this is the method we want
          return m;
        } else if (m.getParameterCount() == bridge.getParameterCount()) {
          for (int i = 0; i < m.getParameterCount(); ++i) {
            if (!bridge.getParameterTypes()[i].isAssignableFrom(m.getParameterTypes()[i])) {
              continue next_method;
            }
          }

          // All of m's parameter types are subtypes of the bridge's parameter types (or primitives)
          if (result == null) {
            result = m;
          } else {
            // Bail if we find multiple methods that could be bridged
            return null;
          }
        }
      }
      return result;
    }
  }

  /**
   * Visitor for interfaces that recursively searches interfaces for default method declarations.
   */
  private class DefaultMethodFinder extends ClassVisitor {
    @SuppressWarnings("hiding")
    private ImmutableList<String> interfaces;

    private boolean found;

    public DefaultMethodFinder() {
      super(Opcodes.ASM7);
    }

    @Override
    public void visit(
        int version,
        int access,
        String name,
        String signature,
        String superName,
        String[] interfaces) {
      checkArgument(BitFlags.isSet(access, Opcodes.ACC_INTERFACE));
      checkState(this.interfaces == null);
      this.interfaces = ImmutableList.copyOf(interfaces);
    }

    public boolean foundDefaultMethods() {
      return found;
    }

    @Override
    public void visitEnd() {
      if (!found) {
        found = defaultMethodsDefined(this.interfaces);
      }
    }

    @Override
    public MethodVisitor visitMethod(
        int access, String name, String desc, String signature, String[] exceptions) {
      if (!found && shouldStubAsDefaultMethod(access, name, desc)) {
        // Found a default method we're not ignoring (instanceMethods at this point contains methods
        // the top-level visited class implements itself).
        found = true;
      }
      return null; // we don't care about the actual code in these methods
    }
  }

  private class InstanceMethodRecorder extends ClassVisitor {

    private final boolean ignoreEmulatedMethods;

    private String className;

    public InstanceMethodRecorder(boolean ignoreEmulatedMethods) {
      super(Opcodes.ASM7);
      this.ignoreEmulatedMethods = ignoreEmulatedMethods;
    }

    @Override
    public void visit(
        int version,
        int access,
        String name,
        String signature,
        String superName,
        String[] interfaces) {
      checkArgument(!BitFlags.isInterface(access));
      className = name; // updated every time we start visiting another superclass
      super.visit(version, access, name, signature, superName, interfaces);
    }

    @Override
    public MethodVisitor visitMethod(
        int access, String name, String desc, String signature, String[] exceptions) {
      if (ignoreEmulatedMethods
          && !BitFlags.isStatic(access) // short-circuit
          && coreLibrarySupport.getCoreInterfaceRewritingTarget(
                  Opcodes.INVOKEVIRTUAL, className, name, desc, /*itf=*/ false)
              != null) {
        // *don't* record emulated core library method implementations in immediate subclasses of
        // emulated core library clasess so that they can be stubbed (since the inherited
        // implementation may be missing at runtime).
        return null;
      }
      recordIfInstanceMethod(access, name, desc);
      return null;
    }
  }

  /**
   * Detector to determine whether an interface needs to be initialized when it is loaded.
   *
   * <p>If the interface has a default method, and its <clinit> initializes any of its fields, then
   * this interface needs to be initialized.
   */
  private static class InterfaceInitializationNecessityDetector extends ClassVisitor {

    private final String internalName;
    private boolean hasFieldInitializedInClinit;
    private boolean hasDefaultMethods;

    public InterfaceInitializationNecessityDetector(String internalName) {
      super(Opcodes.ASM7);
      this.internalName = internalName;
    }

    public boolean needsToInitialize() {
      return hasDefaultMethods && hasFieldInitializedInClinit;
    }

    @Override
    public void visit(
        int version,
        int access,
        String name,
        String signature,
        String superName,
        String[] interfaces) {
      super.visit(version, access, name, signature, superName, interfaces);
      checkState(
          internalName.equals(name),
          "Inconsistent internal names: expected=%s, real=%s",
          internalName,
          name);
      checkArgument(
          BitFlags.isSet(access, Opcodes.ACC_INTERFACE),
          "This class visitor is only used for interfaces.");
    }

    @Override
    public MethodVisitor visitMethod(
        int access, String name, String desc, String signature, String[] exceptions) {
      if (!hasDefaultMethods) {
        hasDefaultMethods = isNonBridgeDefaultMethod(access);
      }
      if ("<clinit>".equals(name)) {
        return new MethodVisitor(Opcodes.ASM7) {
          @Override
          public void visitFieldInsn(int opcode, String owner, String name, String desc) {
            if (opcode == Opcodes.PUTSTATIC && internalName.equals(owner)) {
              hasFieldInitializedInClinit = true;
            }
          }
        };
      }
      return null; // Do not care about the code.
    }
  }

  /** Method visitor that changes super constructor calls to a new base class. */
  private static class ConstructorFixer extends MethodVisitor {

    private final String newSuperName;

    /**
     * This helps us find the very first constructor invocation we visit. We're looking for a
     * sequence ALOAD_0 ; INVOKESPECIAL java.lang.Object() while avoiding "new Object()" which
     * results in a NEW followed by the same INVOKESPECIAL for Object's constructor that we're
     * looking for. Note that anonymous inner class constructors store captured variables into
     * fields before calling super(), so we have to tolerate some unrelated logic, but since
     * Object's constructor is parameterless we thankfully don't have to worry about handwritten
     * code for constructor arguments.
     */
    private boolean looking = true;

    ConstructorFixer(MethodVisitor dest, String newSuperName) {
      super(Opcodes.ASM7, dest);
      this.newSuperName = newSuperName;
    }

    @Override
    public void visitMethodInsn(
        int opcode, String owner, String name, String descriptor, boolean isInterface) {
      if (looking
          && opcode == Opcodes.INVOKESPECIAL
          && "<init>".equals(name)
          && "java/lang/Object".equals(owner)) {
        // Call new base class's constructor instead of j.l.Object().  Note owner can be the
        // visited class for this() constructor calls, and we don't need to touch those here.
        owner = newSuperName;
      }
      // Since Object's constructor has no arguments it must be the very first INVOKE (because there
      // can't be any preceding logic to set up constructor arguments), so stop looking regardless
      // of whether we rewrote that INVOKE or not (but ignore inserted JaCoCo invocations).
      if (looking && (opcode != Opcodes.INVOKESTATIC || !"$jacocoInit".equals(name))) {
        looking = false;
      }
      super.visitMethodInsn(opcode, owner, name, descriptor, isInterface);
    }

    @Override
    public void visitTypeInsn(int opcode, String type) {
      if (opcode == Opcodes.NEW && "java/lang/Object".equals(type)) {
        // NEW java/lang/Object is followed by the very INVOKESPECIAL we're looking for, but we
        // don't want to rewrite it.  Since there can't be a super() call after this, just stop.
        looking = false;
      }
      super.visitTypeInsn(opcode, type);
    }
  }

  /** Comparator for classes and interfaces that compares by whether subtyping relationship. */
  enum SubtypeComparator implements Comparator<Class<?>> {
    /** Orders subtypes before supertypes and breaks ties lexicographically. */
    INSTANCE;

    @Override
    public int compare(Class<?> o1, Class<?> o2) {
      if (o1 == o2) {
        return 0;
      }
      // order subtypes before supertypes
      if (o1.isAssignableFrom(o2)) { // o1 is supertype of o2
        return 1; // we want o1 to come after o2
      }
      if (o2.isAssignableFrom(o1)) { // o2 is supertype of o1
        return -1; // we want o2 to come after o1
      }
      // o1 and o2 aren't comparable so arbitrarily impose lexicographical ordering
      return o1.getName().compareTo(o2.getName());
    }
  }
}