src/main/java/com/android/tools/r8/naming/InterfaceMethodNameMinifier.java

// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.naming;

import static com.android.tools.r8.naming.MethodNameMinifier.shuffleMethods;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexCallSite;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexProto;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.naming.MethodNameMinifier.FrontierState;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.Timing;
import com.google.common.base.Equivalence;
import com.google.common.base.Equivalence.Wrapper;
import com.google.common.collect.Sets;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Objects;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;

public class InterfaceMethodNameMinifier {

  /**
   * Capture a (name, proto)-pair for a {@link MethodNamingState}. Each method
   * methodState.METHOD(...) simply defers to parent.METHOD(name, proto, ...). This allows R8 to
   * assign the same name to methods with different prototypes, which is needed for multi-interface
   * lambdas.
   */
  static class InterfaceMethodNamingState {

    private final MethodNamingState<?> parent;
    private final DexString name;
    private final DexProto proto;
    private final DexMethod method;

    InterfaceMethodNamingState(
        MethodNamingState<?> parent, DexMethod method, DexString name, DexProto proto) {
      this.method = method;
      assert parent != null;
      this.parent = parent;
      this.name = name;
      this.proto = proto;
    }

    DexString assignNewName() {
      return parent.assignNewNameFor(method, name, proto);
    }

    boolean isReserved() {
      return parent.isReserved(name, proto);
    }

    boolean isAvailable(DexString candidate) {
      return parent.isAvailable(proto, candidate);
    }

    void addRenaming(DexString newName) {
      parent.addRenaming(name, proto, newName);
    }

    DexString getName() {
      return name;
    }

    DexProto getProto() {
      return proto;
    }

    void print(
        String indentation,
        Function<MethodNamingState<?>, DexType> stateKeyGetter,
        PrintStream out) {
      DexType stateKey = stateKeyGetter.apply(parent);
      out.print(indentation);
      out.print(stateKey != null ? stateKey.toSourceString() : "<?>");
      out.print(".");
      out.print(name.toSourceString());
      out.println(proto.toSmaliString());
      parent.printState(proto, stateKeyGetter, indentation + "  ", out);
    }
  }

  private final AppView<AppInfoWithLiveness> appView;
  private final Set<DexCallSite> desugaredCallSites;
  private final Equivalence<DexMethod> equivalence;
  private final FrontierState frontierState;
  private final MethodNameMinifier.State minifierState;

  private final Map<DexCallSite, DexString> callSiteRenamings = new IdentityHashMap<>();

  /** A map from DexMethods to all the states linked to interfaces they appear in. */
  private final Map<Wrapper<DexMethod>, Set<MethodNamingState<?>>> globalStateMap = new HashMap<>();

  /** A map from DexMethods to the first interface state it was seen in. Used to pick good names. */
  private final Map<Wrapper<DexMethod>, MethodNamingState<?>> originStates = new HashMap<>();

  /**
   * A map from DexMethods to all the definitions seen. Needed as the Wrapper equalizes them all.
   */
  private final Map<Wrapper<DexMethod>, Set<DexMethod>> sourceMethodsMap = new HashMap<>();

  InterfaceMethodNameMinifier(
      AppView<AppInfoWithLiveness> appView,
      Set<DexCallSite> desugaredCallSites,
      Equivalence<DexMethod> equivalence,
      FrontierState frontierState,
      MethodNameMinifier.State minifierState) {
    this.appView = appView;
    this.desugaredCallSites = desugaredCallSites;
    this.equivalence = equivalence;
    this.frontierState = frontierState;
    this.minifierState = minifierState;
  }

  public Comparator<Wrapper<DexMethod>> createDefaultInterfaceMethodOrdering() {
    return (a, b) -> globalStateMap.get(b).size() - globalStateMap.get(a).size();
  }

  Map<DexCallSite, DexString> getCallSiteRenamings() {
    return callSiteRenamings;
  }

  private void reserveNamesInInterfaces(Collection<DexClass> interfaces) {
    for (DexClass iface : interfaces) {
      assert iface.isInterface();
      frontierState.allocateNamingStateAndReserve(iface.type, iface.type, null);
    }
  }

  void assignNamesToInterfaceMethods(Timing timing, Collection<DexClass> interfaces) {
    // Reserve all the names that are required for interfaces.
    reserveNamesInInterfaces(interfaces);

    // First compute a map from method signatures to a set of naming states for interfaces and
    // frontier states of classes that implement them. We add the frontier states so that we can
    // reserve the names for later method naming.
    timing.begin("Compute map");
    Set<DexType> allInterfaceTypes = new HashSet<>(interfaces.size());
    for (DexClass iface : interfaces) {
      allInterfaceTypes.add(iface.type);
    }
    for (DexClass iface : interfaces) {
      Set<MethodNamingState<?>> collectedStates = getReachableStates(iface.type, allInterfaceTypes);
      for (DexEncodedMethod method : shuffleMethods(iface.methods(), appView.options())) {
        addStatesToGlobalMapForMethod(method.method, collectedStates, iface.type);
      }
    }

    // Collect the live call sites for multi-interface lambda expression renaming. For code with
    // desugared lambdas this is a conservative estimate, as we don't track if the generated
    // lambda classes survive into the output. As multi-interface lambda expressions are rare
    // this is not a big deal.
    Set<DexCallSite> liveCallSites = Sets.union(desugaredCallSites, appView.appInfo().callSites);
    // If the input program contains a multi-interface lambda expression that implements
    // interface methods with different protos, we need to make sure that
    // the implemented lambda methods are renamed to the same name.
    // To achieve this, we map each DexCallSite that corresponds to a lambda expression to one of
    // the DexMethods it implements, and we unify the DexMethods that need to be renamed together.
    Map<DexCallSite, DexMethod> callSites = new IdentityHashMap<>();
    // Union-find structure to keep track of methods that must be renamed together.
    // Note that if the input does not use multi-interface lambdas,
    // unificationParent will remain empty.
    Map<Wrapper<DexMethod>, Wrapper<DexMethod>> unificationParent = new HashMap<>();
    liveCallSites.forEach(
        callSite -> {
          Set<Wrapper<DexMethod>> callSiteMethods = new HashSet<>();
          // Don't report errors, as the set of call sites is a conservative estimate, and can
          // refer to interfaces which has been removed.
          Set<DexEncodedMethod> implementedMethods =
              appView.appInfo().lookupLambdaImplementedMethods(callSite);
          if (implementedMethods.isEmpty()) {
            return;
          }
          callSites.put(callSite, implementedMethods.iterator().next().method);
          for (DexEncodedMethod method : implementedMethods) {
            DexType iface = method.method.holder;
            Set<MethodNamingState<?>> collectedStates =
                getReachableStates(iface, allInterfaceTypes);
            addStatesToGlobalMapForMethod(method.method, collectedStates, iface);
            callSiteMethods.add(equivalence.wrap(method.method));
          }
          if (callSiteMethods.size() > 1) {
            // Implemented interfaces have different return types. Unify them.
            Wrapper<DexMethod> mainKey = callSiteMethods.iterator().next();
            mainKey = unificationParent.getOrDefault(mainKey, mainKey);
            for (Wrapper<DexMethod> key : callSiteMethods) {
              unificationParent.put(key, mainKey);
            }
          }
        });
    Map<Wrapper<DexMethod>, Set<Wrapper<DexMethod>>> unification = new HashMap<>();
    for (Wrapper<DexMethod> key : unificationParent.keySet()) {
      // Find root with path-compression.
      Wrapper<DexMethod> root = unificationParent.get(key);
      while (unificationParent.get(root) != root) {
        Wrapper<DexMethod> k = unificationParent.get(unificationParent.get(root));
        unificationParent.put(root, k);
        root = k;
      }
      unification.computeIfAbsent(root, k -> new HashSet<>()).add(key);
    }
    timing.end();
    // Go over every method and assign a name.
    timing.begin("Allocate names");

    timing.begin("sort");
    // Sort the methods by the number of dependent states, so that we use short names for methods
    // that are referenced in many places.
    List<Wrapper<DexMethod>> interfaceMethods =
        globalStateMap.keySet().stream()
            .filter(wrapper -> unificationParent.getOrDefault(wrapper, wrapper).equals(wrapper))
            .sorted(appView.options().testing.minifier.createInterfaceMethodOrdering(this))
            .collect(Collectors.toList());
    timing.end();

    timing.begin("propogate");
    // Propagate reserved names to all states.
    List<Wrapper<DexMethod>> reservedInterfaceMethods =
        interfaceMethods.stream()
            .filter(wrapper -> anyIsReserved(wrapper, unification))
            .collect(Collectors.toList());
    for (Wrapper<DexMethod> key : reservedInterfaceMethods) {
      propagateReservedNames(key, unification);
    }
    timing.end();

    timing.begin("assert");
    // Verify that there is no more to propagate.
    assert reservedInterfaceMethods.stream()
        .noneMatch(key -> propagateReservedNames(key, unification));
    timing.end();

    timing.begin("assing interface");
    // Assign names to unreserved interface methods.
    for (Wrapper<DexMethod> key : interfaceMethods) {
      if (!reservedInterfaceMethods.contains(key)) {
        assignNameToInterfaceMethod(key, unification);
      }
    }
    timing.end();

    timing.begin("callsites");
    for (Entry<DexCallSite, DexMethod> entry : callSites.entrySet()) {
      DexMethod method = entry.getValue();
      DexString renamed = minifierState.getRenaming(method);
      if (originStates.get(equivalence.wrap(method)).isReserved(method.name, method.proto)) {
        assert renamed == null;
        callSiteRenamings.put(entry.getKey(), method.name);
      } else {
        assert renamed != null;
        callSiteRenamings.put(entry.getKey(), renamed);
      }
    }
    timing.end();
    timing.end(); // end compute map timing
  }

  private boolean propagateReservedNames(
      Wrapper<DexMethod> key, Map<Wrapper<DexMethod>, Set<Wrapper<DexMethod>>> unification) {
    Set<Wrapper<DexMethod>> unifiedMethods =
        unification.getOrDefault(key, Collections.singleton(key));
    boolean changed = false;
    for (Wrapper<DexMethod> wrapper : unifiedMethods) {
      DexMethod unifiedMethod = wrapper.get();
      assert unifiedMethod != null;
      assert globalStateMap.containsKey(wrapper)
          : "Expected globalStateMap to contain " + unifiedMethod.toSourceStringWithoutHolder();
      assert globalStateMap.get(wrapper) != null
          : "Expected globalStateMap to map "
              + unifiedMethod.toSourceStringWithoutHolder()
              + " to a non-null MethodNamingState.";

      for (MethodNamingState<?> namingState : globalStateMap.get(wrapper)) {
        if (!namingState.isReserved(unifiedMethod.name, unifiedMethod.proto)) {
          namingState.reserveName(unifiedMethod.name, unifiedMethod.proto);
          changed = true;
        }
      }
    }
    return changed;
  }

  private void assignNameToInterfaceMethod(
      Wrapper<DexMethod> key, Map<Wrapper<DexMethod>, Set<Wrapper<DexMethod>>> unification) {
    List<InterfaceMethodNamingState> collectedStates = new ArrayList<>();
    Set<DexMethod> sourceMethods = Sets.newIdentityHashSet();
    for (Wrapper<DexMethod> k : unification.getOrDefault(key, Collections.singleton(key))) {
      DexMethod unifiedMethod = k.get();
      assert unifiedMethod != null;
      sourceMethods.addAll(sourceMethodsMap.get(k));
      for (MethodNamingState<?> namingState : globalStateMap.get(k)) {
        collectedStates.add(
            new InterfaceMethodNamingState(
                namingState, unifiedMethod, unifiedMethod.name, unifiedMethod.proto));
      }
    }

    DexMethod method = key.get();
    assert method != null;

    Set<String> loggingFilter = appView.options().extensiveInterfaceMethodMinifierLoggingFilter;
    if (!loggingFilter.isEmpty()) {
      if (sourceMethods.stream().map(DexMethod::toSourceString).anyMatch(loggingFilter::contains)) {
        print(method, sourceMethods, collectedStates, System.out);
      }
    }

    InterfaceMethodNamingState originState =
        new InterfaceMethodNamingState(originStates.get(key), method, method.name, method.proto);
    assignNameForInterfaceMethodInAllStates(collectedStates, sourceMethods, originState);
  }

  private void assignNameForInterfaceMethodInAllStates(
      List<InterfaceMethodNamingState> collectedStates,
      Set<DexMethod> sourceMethods,
      InterfaceMethodNamingState originState) {
    assert !anyIsReserved(collectedStates);

    // We use the origin state to allocate a name here so that we can reuse names between different
    // unrelated interfaces. This saves some space. The alternative would be to use a global state
    // for allocating names, which would save the work to search here.
    DexString candidate;
    do {
      candidate = originState.assignNewName();
      for (InterfaceMethodNamingState state : collectedStates) {
        if (!state.isAvailable(candidate)) {
          candidate = null;
          break;
        }
      }
    } while (candidate == null);
    for (InterfaceMethodNamingState state : collectedStates) {
      state.addRenaming(candidate);
    }
    // Rename all methods in interfaces that gave rise to this renaming.
    for (DexMethod sourceMethod : sourceMethods) {
      minifierState.putRenaming(sourceMethod, candidate);
    }
  }

  private void addStatesToGlobalMapForMethod(
      DexMethod method, Set<MethodNamingState<?>> collectedStates, DexType originInterface) {
    assert collectedStates.stream().noneMatch(Objects::isNull);
    Wrapper<DexMethod> key = equivalence.wrap(method);
    globalStateMap.computeIfAbsent(key, k -> new HashSet<>()).addAll(collectedStates);
    sourceMethodsMap.computeIfAbsent(key, k -> new HashSet<>()).add(method);
    originStates.putIfAbsent(key, minifierState.getState(originInterface));
  }

  private boolean anyIsReserved(
      Wrapper<DexMethod> key, Map<Wrapper<DexMethod>, Set<Wrapper<DexMethod>>> unification) {
    Set<Wrapper<DexMethod>> unifiedMethods =
        unification.getOrDefault(key, Collections.singleton(key));
    for (Wrapper<DexMethod> wrapper : unifiedMethods) {
      DexMethod unifiedMethod = wrapper.get();
      assert unifiedMethod != null;
      assert globalStateMap.containsKey(wrapper)
          : "Expected globalStateMap to contain " + unifiedMethod.toSourceStringWithoutHolder();
      assert globalStateMap.get(wrapper) != null
          : "Expected globalStateMap to map "
              + unifiedMethod.toSourceStringWithoutHolder()
              + " to a non-null MethodNamingState.";

      for (MethodNamingState<?> namingState : globalStateMap.get(wrapper)) {
        if (namingState.isReserved(unifiedMethod.name, unifiedMethod.proto)) {
          return true;
        }
      }
    }
    return false;
  }

  private boolean anyIsReserved(List<InterfaceMethodNamingState> collectedStates) {
    DexString name = collectedStates.get(0).getName();
    Map<DexProto, Boolean> globalStateCache = new IdentityHashMap<>();
    for (InterfaceMethodNamingState state : collectedStates) {
      assert state.getName() == name;
      boolean isReservedInGlobalState =
          globalStateCache.computeIfAbsent(
              state.getProto(), proto -> minifierState.isReservedInGlobalState(name, proto));
      // TODO(christofferqa): Should this be using logical OR instead?
      if (isReservedInGlobalState && state.isReserved()) {
        return true;
      }
    }
    return false;
  }

  private Set<MethodNamingState<?>> getReachableStates(DexType type, Set<DexType> allInterfaces) {
    Set<DexType> reachableInterfaces = getReachableInterfaces(type, allInterfaces);
    Set<MethodNamingState<?>> reachableStates = new HashSet<>();
    for (DexType reachableInterface : reachableInterfaces) {
      // Add the interface itself.
      MethodNamingState<?> ifaceState = minifierState.getState(reachableInterface);
      assert ifaceState != null;
      reachableStates.add(ifaceState);

      // And the frontiers that correspond to the classes that implement the interface.
      for (DexType frontier : appView.appInfo().allImplementsSubtypes(reachableInterface)) {
        MethodNamingState<?> state = minifierState.getState(frontierState.get(frontier));
        assert state != null;
        reachableStates.add(state);
      }
    }
    return reachableStates;
  }

  private Set<DexType> getReachableInterfaces(DexType type, Set<DexType> allInterfaces) {
    if (!allInterfaces.contains(type)) {
      return Collections.emptySet();
    }
    Set<DexType> reachableInterfaces = Sets.newIdentityHashSet();
    reachableInterfaces.add(type);
    collectSuperInterfaces(type, reachableInterfaces, allInterfaces);
    collectSubInterfaces(type, reachableInterfaces, allInterfaces);
    return reachableInterfaces;
  }

  private void collectSuperInterfaces(
      DexType iface, Set<DexType> reachable, Set<DexType> allInterfaces) {
    DexClass clazz = appView.definitionFor(iface);
    if (clazz != null) {
      for (DexType type : clazz.interfaces.values) {
        if (allInterfaces.contains(type) && reachable.add(type)) {
          collectSuperInterfaces(type, reachable, allInterfaces);
        }
      }
    }
  }

  private void collectSubInterfaces(
      DexType iface, Set<DexType> reachableInterfaces, Set<DexType> allInterfaces) {
    // In cases where we lack the interface's definition, we can at least look at subtypes and
    // tie those up to get proper naming.
    for (DexType subtype : appView.appInfo().allExtendsSubtypes(iface)) {
      if (allInterfaces.contains(subtype) && reachableInterfaces.add(subtype)) {
        collectSubInterfaces(subtype, reachableInterfaces, allInterfaces);
      }
    }
  }

  private void print(
      DexMethod method,
      Set<DexMethod> sourceMethods,
      List<InterfaceMethodNamingState> collectedStates,
      PrintStream out) {
    out.println("-----------------------------------------------------------------------");
    out.println("assignNameToInterfaceMethod(`" + method.toSourceString() + "`)");
    out.println("-----------------------------------------------------------------------");
    out.println("Source methods:");
    for (DexMethod sourceMethod : sourceMethods) {
      out.println("  " + sourceMethod.toSourceString());
    }
    out.println("States:");
    collectedStates.forEach(state -> state.print("  ", minifierState::getStateKey, out));
    out.println();
  }
}