src/main/java/com/android/tools/r8/optimize/proto/ProtoNormalizer.java

// Copyright (c) 2022, 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.optimize.proto;

import static com.android.tools.r8.utils.MapUtils.ignoreKey;

import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexMethodSignature;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexTypeList;
import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.graph.proto.RewrittenPrototypeDescription;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.shaking.KeepMethodInfo;
import com.android.tools.r8.utils.DepthFirstSearchWorkListBase.StatefulDepthFirstSearchWorkList;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.MapUtils;
import com.android.tools.r8.utils.ThreadUtils;
import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.WorkList;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
import com.android.tools.r8.utils.collections.DexMethodSignatureSet;
import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.function.Function;

public class ProtoNormalizer {

  private final AppView<AppInfoWithLiveness> appView;
  private final DexItemFactory dexItemFactory;
  private final InternalOptions options;

  public ProtoNormalizer(AppView<AppInfoWithLiveness> appView) {
    this.appView = appView;
    this.dexItemFactory = appView.dexItemFactory();
    this.options = appView.options();
  }

  public void run(ExecutorService executorService, Timing timing) throws ExecutionException {
    timing.time("Proto normalization", () -> run(executorService));
  }

  private void run(ExecutorService executorService) throws ExecutionException {
    GlobalReservationState globalReservationState = computeGlobalReservationState(executorService);

    // To ensure we do not add collisions of method signatures when creating the new method
    // signatures we keep a map of methods in the type hierarchy, similar to what we do for
    // minification.
    ProtoNormalizerGraphLens.Builder lensBuilder = ProtoNormalizerGraphLens.builder(appView);
    new StatefulDepthFirstSearchWorkList<DexClass, LocalReservationState, Void>() {

      @Override
      @SuppressWarnings("ReturnValueIgnored")
      protected TraversalContinuation<Void, LocalReservationState> process(
          DFSNodeWithState<DexClass, LocalReservationState> node,
          Function<DexClass, DFSNodeWithState<DexClass, LocalReservationState>> childNodeConsumer) {
        DexClass clazz = node.getNode();
        node.setState(new LocalReservationState());
        if (clazz.getSuperType() != null) {
          appView
              .contextIndependentDefinitionForWithResolutionResult(clazz.getSuperType())
              .forEachClassResolutionResult(childNodeConsumer::apply);
        }
        return TraversalContinuation.doContinue();
      }

      @Override
      protected TraversalContinuation<Void, LocalReservationState> joiner(
          DFSNodeWithState<DexClass, LocalReservationState> node,
          List<DFSNodeWithState<DexClass, LocalReservationState>> childStates) {
        DexClass clazz = node.getNode();
        assert childStates.size() >= 1
            || clazz.getType() == dexItemFactory.objectType
            || clazz.hasMissingSuperType(appView.appInfo());
        // We can have multiple child states if there are multiple definitions of a class.
        assert childStates.size() <= 1 || options.loadAllClassDefinitions;
        LocalReservationState localReservationState = node.getState();
        if (!childStates.isEmpty()) {
          localReservationState.linkParent(childStates.get(0).getState());
        }
        Map<DexMethodSignature, DexMethodSignature> newInstanceInitializerSignatures =
            clazz.isProgramClass()
                ? computeNewInstanceInitializerSignatures(
                    clazz.asProgramClass(), localReservationState, globalReservationState)
                : null;
        clazz
            .getMethodCollection()
            .replaceMethods(
                method -> {
                  DexMethodSignature methodSignature = method.getSignature();
                  if (!clazz.isProgramClass()) {
                    // We cannot change the signature of the method. Record it to ensure we do not
                    // change a program signature in a sub class to override this.
                    localReservationState.recordNoSignatureChange(methodSignature, dexItemFactory);
                    return method;
                  } else {
                    assert newInstanceInitializerSignatures != null;
                    DexMethodSignature newMethodSignature =
                        method.isInstanceInitializer()
                            ? newInstanceInitializerSignatures.get(methodSignature)
                            : localReservationState.getAndReserveNewMethodSignature(
                                methodSignature, dexItemFactory, globalReservationState);
                    if (methodSignature.equals(newMethodSignature)) {
                      // This method could not be optimized, record it as identity mapping to ensure
                      // we keep it going forward.
                      localReservationState.recordNoSignatureChange(
                          methodSignature, dexItemFactory);
                      return method;
                    }
                    DexMethod newMethodReference =
                        newMethodSignature.withHolder(clazz.asProgramClass(), dexItemFactory);
                    RewrittenPrototypeDescription prototypeChanges =
                        lensBuilder.recordNewMethodSignature(method, newMethodReference);
                    // TODO(b/195112263): Assert that the method does not have optimization info.
                    // If/when enabling proto normalization after the final round of tree shaking,
                    // this should simply clear the optimization info, or replace it by a
                    // ThrowingMethodOptimizationInfo since we should never use the optimization
                    // info after this point.
                    return method.toTypeSubstitutedMethod(
                        newMethodReference,
                        builder -> {
                          if (!prototypeChanges.isEmpty()) {
                            builder
                                .apply(prototypeChanges.createParameterAnnotationsRemover(method))
                                .setGenericSignature(MethodTypeSignature.noSignature());
                          }
                        });
                  }
                });
        return TraversalContinuation.doContinue(localReservationState);
      }
    }.run(appView.appInfo().classesWithDeterministicOrder());

    if (!lensBuilder.isEmpty()) {
      appView.rewriteWithLens(lensBuilder.build());
    }
  }

  private GlobalReservationState computeGlobalReservationState(ExecutorService executorService)
      throws ExecutionException {
    // Tracks how many different parameter lists can be optimized into the same parameter list.
    // If only (B, A) can be rewritten into (A, B), then there is no need to rewrite parameter lists
    // on the form (B, A) into (A, B), as that won't lead to any sharing of parameter lists.
    Map<DexTypeList, Set<DexTypeList>> optimizableParameterLists = new ConcurrentHashMap<>();

    // Used to track if a given parameter list should be mapped to a specific permutation instead of
    // just sorting the parameter list. This is used to ensure that we will rewrite parameter lists
    // such as (A, B) into (B, A) if there is an unoptimizable method with parameter list (B, A).
    Map<DexTypeList, Set<DexTypeList>> reservedParameterLists = new ConcurrentHashMap<>();

    // Tracks the set of unoptimizable method signatures. These must remain as-is.
    DexMethodSignatureSet unoptimizableSignatures = DexMethodSignatureSet.createConcurrent();

    ThreadUtils.processItems(
        appView.appInfo().classes(),
        clazz -> {
          Map<DexMethodSignature, DexMethodSignatureSet> collisions = new HashMap<>();
          clazz.forEachProgramMethod(
              method -> {
                DexTypeList methodParametersSorted = method.getParameters().getSorted();
                computeReservationsFromMethod(
                    method,
                    methodParametersSorted,
                    optimizableParameterLists,
                    reservedParameterLists,
                    unoptimizableSignatures);

                DexMethodSignature methodSignature = method.getMethodSignature();
                DexMethodSignature methodSignatureWithSortedParameters =
                    methodSignature.withParameters(methodParametersSorted, dexItemFactory);
                collisions
                    .computeIfAbsent(
                        methodSignatureWithSortedParameters,
                        ignoreKey(DexMethodSignatureSet::createLinked))
                    .add(methodSignature);
              });
          collisions.forEach(
              (methodSignatureWithSortedParameters, methodSignatures) -> {
                if (methodSignatures.size() > 1) {
                  methodSignatures.forEach(
                      methodSignature ->
                          addUnoptimizableMethod(
                              methodSignature,
                              methodSignatureWithSortedParameters.getParameters(),
                              reservedParameterLists,
                              unoptimizableSignatures));
                }
              });
        },
        executorService);

    // Reserve parameter lists that won't lead to any sharing after normalization. Any method with
    // such a parameter list must remain as-is.
    Set<DexTypeList> unoptimizableParameterLists = new HashSet<>();
    optimizableParameterLists.forEach(
        (sortedParameters, parameterListsBeforeNormalization) -> {
          int size = parameterListsBeforeNormalization.size();
          if (size != 1) {
            // There are multiple optimizable methods with different parameter lists that can be
            // rewritten into having the same parameter list.
            assert size > 1;
            return;
          }
          DexTypeList parameters = parameterListsBeforeNormalization.iterator().next();
          Set<DexTypeList> reservedParameters =
              reservedParameterLists.getOrDefault(sortedParameters, Collections.emptySet());
          if (!reservedParameters.isEmpty() && !reservedParameters.contains(parameters)) {
            // There is at least one optimizable method that can be rewritten into having the same
            // parameter list as an unoptimizable method.
            return;
          }
          unoptimizableParameterLists.add(parameters);
        });

    ThreadUtils.processMethods(
        appView,
        method ->
            computeExtraReservationsFromMethod(
                method, unoptimizableParameterLists, unoptimizableSignatures),
        executorService);

    return new GlobalReservationState(reservedParameterLists, unoptimizableSignatures);
  }

  private void computeReservationsFromMethod(
      ProgramMethod method,
      DexTypeList methodParametersSorted,
      Map<DexTypeList, Set<DexTypeList>> optimizableParameterLists,
      Map<DexTypeList, Set<DexTypeList>> reservedParameterLists,
      DexMethodSignatureSet unoptimizableSignatures) {
    if (isUnoptimizable(method)) {
      addUnoptimizableMethod(
          method.getMethodSignature(),
          methodParametersSorted,
          reservedParameterLists,
          unoptimizableSignatures);
    } else {
      // Record that the method's parameter list can be rewritten into any permutation.
      optimizableParameterLists
          .computeIfAbsent(methodParametersSorted, ignoreKey(Sets::newConcurrentHashSet))
          .add(method.getParameters());
    }
  }

  private void addUnoptimizableMethod(
      DexMethodSignature method,
      DexTypeList methodParametersSorted,
      Map<DexTypeList, Set<DexTypeList>> reservedParameterLists,
      DexMethodSignatureSet unoptimizableSignatures) {
    // Record that other optimizable methods with the same set of parameter types should be
    // rewritten to have the same parameter list as this method.
    reservedParameterLists
        .computeIfAbsent(methodParametersSorted, ignoreKey(Sets::newConcurrentHashSet))
        .add(method.getParameters());

    // Mark signature as unoptimizable.
    unoptimizableSignatures.add(method);
  }

  private void computeExtraReservationsFromMethod(
      ProgramMethod method,
      Set<DexTypeList> unoptimizableParameterLists,
      DexMethodSignatureSet unoptimizableSignatures) {
    if (unoptimizableParameterLists.contains(method.getParameters())) {
      unoptimizableSignatures.add(method.getMethodSignature());
    }
  }

  Map<DexMethodSignature, DexMethodSignature> computeNewInstanceInitializerSignatures(
      DexProgramClass clazz,
      LocalReservationState localReservationState,
      GlobalReservationState globalReservationState) {
    // Create a map from new method signatures to old method signatures. This produces a one-to-many
    // mapping since multiple instance initializers may normalize to the same signature.
    Map<DexMethodSignature, DexMethodSignatureSet> instanceInitializerCollisions =
        computeInstanceInitializerCollisions(clazz, localReservationState, globalReservationState);

    // Resolve each collision to ensure that the mapping is one-to-one.
    resolveInstanceInitializerCollisions(instanceInitializerCollisions);

    // Inverse the one-to-one map to produce a mapping from old method signatures to new method
    // signatures.
    return MapUtils.transform(
        instanceInitializerCollisions,
        HashMap::new,
        (newMethodSignature, methodSignatures) -> Iterables.getFirst(methodSignatures, null),
        (newMethodSignature, methodSignatures) -> newMethodSignature,
        (newMethodSignature, methodSignature, otherMethodSignature) -> {
          throw new Unreachable();
        });
  }

  private Map<DexMethodSignature, DexMethodSignatureSet> computeInstanceInitializerCollisions(
      DexProgramClass clazz,
      LocalReservationState localReservationState,
      GlobalReservationState globalReservationState) {
    Map<DexMethodSignature, DexMethodSignatureSet> instanceInitializerCollisions = new HashMap<>();
    clazz.forEachProgramInstanceInitializer(
        method -> {
          DexMethodSignature methodSignature = method.getMethodSignature();
          DexMethodSignature newMethodSignature =
              localReservationState.getNewMethodSignature(
                  methodSignature, dexItemFactory, globalReservationState);
          instanceInitializerCollisions
              .computeIfAbsent(newMethodSignature, ignoreKey(DexMethodSignatureSet::create))
              .add(methodSignature);
        });
    return instanceInitializerCollisions;
  }

  private void resolveInstanceInitializerCollisions(
      Map<DexMethodSignature, DexMethodSignatureSet> instanceInitializerCollisions) {
    WorkList<DexMethodSignature> worklist = WorkList.newEqualityWorkList();
    instanceInitializerCollisions.forEach(
        (newMethodSignature, methodSignatures) -> {
          if (methodSignatures.size() > 1) {
            worklist.addIfNotSeen(newMethodSignature);
          }
        });

    while (worklist.hasNext()) {
      DexMethodSignature newMethodSignature = worklist.removeSeen();
      DexMethodSignatureSet methodSignatures =
          instanceInitializerCollisions.get(newMethodSignature);
      assert methodSignatures.size() > 1;

      // Resolve this conflict in a deterministic way.
      DexMethodSignature survivor =
          methodSignatures.contains(newMethodSignature)
              ? newMethodSignature
              : IterableUtils.min(methodSignatures, DexMethodSignature::compareTo);

      // Disallow optimizations of all other methods than the `survivor`.
      for (DexMethodSignature methodSignature : methodSignatures) {
        if (!methodSignature.equals(survivor)) {
          DexMethodSignatureSet originalMethodSignaturesForMethodSignature =
              instanceInitializerCollisions.computeIfAbsent(
                  methodSignature, ignoreKey(DexMethodSignatureSet::create));
          originalMethodSignaturesForMethodSignature.add(methodSignature);
          if (originalMethodSignaturesForMethodSignature.size() > 1) {
            worklist.addIfNotSeen(methodSignature);
          }
        }
      }

      // Remove all pinned methods from the set of original method signatures stored at
      // instanceInitializerCollisions.get(newMethodSignature).
      methodSignatures.clear();
      methodSignatures.add(survivor);
    }
  }

  private boolean isUnoptimizable(ProgramMethod method) {
    KeepMethodInfo keepInfo = appView.getKeepInfo(method);
    if (!keepInfo.isParameterReorderingAllowed(options)
        || method.getDefinition().isLibraryMethodOverride().isPossiblyTrue()) {
      return true;
    }
    AppInfoWithLiveness appInfo = appView.appInfo();
    if (appInfo.isBootstrapMethod(method)) {
      return true;
    }
    // As long as we do not consider interface method and overrides as optimizable we can change
    // method signatures in a top-down traversal.
    return method.getHolder().isInterface()
        && method.getDefinition().isAbstract()
        && appInfo
            .getObjectAllocationInfoCollection()
            .isImmediateInterfaceOfInstantiatedLambda(method.getHolder());
  }

  static class GlobalReservationState {

    // Used to track if a given parameter list should be mapped to a specific permutation instead of
    // just sorting the parameter list. This is used to ensure that we will rewrite parameter lists
    // such as (A, B) into (B, A) if there is an unoptimizable method with parameter list (B, A).
    Map<DexTypeList, DexTypeList> reservedParameters;

    // Tracks the set of unoptimizable method signatures. These must remain as-is.
    DexMethodSignatureSet unoptimizableSignatures;

    GlobalReservationState(
        Map<DexTypeList, Set<DexTypeList>> reservedParameterLists,
        DexMethodSignatureSet unoptimizableSignatures) {
      this.reservedParameters = selectDeterministicTarget(reservedParameterLists);
      this.unoptimizableSignatures = unoptimizableSignatures;
    }

    private static Map<DexTypeList, DexTypeList> selectDeterministicTarget(
        Map<DexTypeList, Set<DexTypeList>> reservedParameterLists) {
      Map<DexTypeList, DexTypeList> result = new HashMap<>();
      reservedParameterLists.forEach(
          (sortedParameters, candidates) -> {
            Iterator<DexTypeList> iterator = candidates.iterator();
            DexTypeList smallestCandidate = iterator.next();
            while (iterator.hasNext()) {
              DexTypeList candidate = iterator.next();
              if (candidate.compareTo(smallestCandidate) < 0) {
                smallestCandidate = candidate;
              }
            }
            result.put(sortedParameters, smallestCandidate);
          });
      return result;
    }

    DexTypeList getReservedParameters(DexMethodSignature methodSignature) {
      DexTypeList sortedParameters = methodSignature.getParameters().getSorted();
      return reservedParameters.getOrDefault(sortedParameters, sortedParameters);
    }

    boolean isUnoptimizable(DexMethodSignature methodSignature) {
      return unoptimizableSignatures.contains(methodSignature);
    }
  }

  static class LocalReservationState {

    private final List<LocalReservationState> parents = new ArrayList<>(2);

    private final MutableBidirectionalOneToOneMap<DexMethodSignature, DexMethodSignature>
        newMethodSignatures = new BidirectionalOneToOneHashMap<>();

    DexMethodSignature getNewMethodSignature(
        DexMethodSignature methodSignature,
        DexItemFactory dexItemFactory,
        GlobalReservationState globalReservationState) {
      return internalGetAndReserveNewMethodSignature(
          methodSignature, dexItemFactory, globalReservationState, false);
    }

    DexMethodSignature getAndReserveNewMethodSignature(
        DexMethodSignature methodSignature,
        DexItemFactory dexItemFactory,
        GlobalReservationState globalReservationState) {
      return internalGetAndReserveNewMethodSignature(
          methodSignature, dexItemFactory, globalReservationState, true);
    }

    private DexMethodSignature internalGetAndReserveNewMethodSignature(
        DexMethodSignature methodSignature,
        DexItemFactory dexItemFactory,
        GlobalReservationState globalReservationState,
        boolean reserve) {
      if (globalReservationState.isUnoptimizable(methodSignature)) {
        assert getReserved(methodSignature) == null
            || methodSignature.equals(getReserved(methodSignature));
        return methodSignature;
      }
      DexMethodSignature reservedSignature = getReserved(methodSignature);
      if (reservedSignature != null) {
        return reservedSignature;
      }
      DexTypeList reservedParameters =
          globalReservationState.getReservedParameters(methodSignature);
      DexMethodSignature newMethodSignature =
          methodSignature.withParameters(reservedParameters, dexItemFactory);
      if (isDestinationTaken(newMethodSignature)) {
        int index = 1;
        String newMethodBaseName = methodSignature.getName().toString();
        do {
          DexString newMethodName = dexItemFactory.createString(newMethodBaseName + "$" + index);
          newMethodSignature = newMethodSignature.withName(newMethodName);
          index++;
        } while (isDestinationTaken(newMethodSignature));
      }
      if (reserve) {
        newMethodSignatures.put(methodSignature, newMethodSignature);
      }
      return newMethodSignature;
    }

    private void linkParent(LocalReservationState parent) {
      this.parents.add(parent);
    }

    private DexMethodSignature getReserved(DexMethodSignature signature) {
      WorkList<LocalReservationState> workList = WorkList.newIdentityWorkList(this);
      while (workList.hasNext()) {
        LocalReservationState localReservationState = workList.next();
        DexMethodSignature reservedSignature =
            localReservationState.newMethodSignatures.get(signature);
        if (reservedSignature != null) {
          return reservedSignature;
        }
        workList.addIfNotSeen(localReservationState.parents);
      }
      return null;
    }

    private boolean isDestinationTaken(DexMethodSignature signature) {
      WorkList<LocalReservationState> workList = WorkList.newIdentityWorkList(this);
      while (workList.hasNext()) {
        LocalReservationState localReservationState = workList.next();
        if (localReservationState.newMethodSignatures.containsValue(signature)) {
          return true;
        }
        workList.addIfNotSeen(localReservationState.parents);
      }
      return false;
    }

    public void recordNoSignatureChange(
        DexMethodSignature methodSignature, DexItemFactory factory) {
      if (!methodSignature.getName().equals(factory.constructorMethodName)) {
        newMethodSignatures.put(methodSignature, methodSignature);
      }
    }
  }
}