// Copyright (c) 2020, 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.synthesis;

import static com.google.common.base.Predicates.alwaysTrue;

import com.android.tools.r8.features.ClassToFeatureSplitMap;
import com.android.tools.r8.graph.AppInfo;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexApplication;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedMember;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.GraphLens;
import com.android.tools.r8.graph.GraphLens.NonIdentityGraphLens;
import com.android.tools.r8.graph.NestedGraphLens;
import com.android.tools.r8.graph.PrunedItems;
import com.android.tools.r8.graph.TreeFixerBase;
import com.android.tools.r8.ir.code.NumberGenerator;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.shaking.KeepInfoCollection;
import com.android.tools.r8.shaking.MainDexInfo;
import com.android.tools.r8.synthesis.SyntheticItems.State;
import com.android.tools.r8.synthesis.SyntheticNaming.Phase;
import com.android.tools.r8.synthesis.SyntheticNaming.SyntheticKind;
import com.android.tools.r8.utils.DescriptorUtils;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.OptionalBool;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
import com.android.tools.r8.utils.structural.RepresentativeMap;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
import com.google.common.hash.HashCode;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.function.BiConsumer;
import java.util.function.Consumer;
import java.util.function.Predicate;

public class SyntheticFinalization {

  // TODO(b/237413146): Implement a non-quadratic grouping algorithm.
  private static final int GROUP_COUNT_THRESHOLD = 10;

  public static class Result {
    public final CommittedItems commit;
    public final NonIdentityGraphLens lens;
    public final PrunedItems prunedItems;
    public final MainDexInfo mainDexInfo;

    public Result(
        CommittedItems commit,
        SyntheticFinalizationGraphLens lens,
        PrunedItems prunedItems,
        MainDexInfo mainDexInfo) {
      this.commit = commit;
      this.lens = lens;
      this.prunedItems = prunedItems;
      this.mainDexInfo = mainDexInfo;
    }
  }

  public static class SyntheticFinalizationGraphLens extends NestedGraphLens {

    private SyntheticFinalizationGraphLens(
        AppView<?> appView,
        BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap,
        BidirectionalManyToOneRepresentativeMap<DexMethod, DexMethod> methodMap,
        Map<DexType, DexType> typeMap) {
      super(appView, fieldMap, methodMap, typeMap);
    }

    @Override
    public boolean isSyntheticFinalizationGraphLens() {
      return true;
    }

    @Override
    public boolean isSimpleRenamingLens() {
      return true;
    }
  }

  private static class Builder {

    private final BidirectionalManyToOneRepresentativeHashMap<DexField, DexField> fieldMap =
        BidirectionalManyToOneRepresentativeHashMap.newIdentityHashMap();
    private final MutableBidirectionalManyToOneRepresentativeMap<DexMethod, DexMethod> methodMap =
        BidirectionalManyToOneRepresentativeHashMap.newIdentityHashMap();
    private final Map<DexType, DexType> typeMap = new IdentityHashMap<>();

    boolean isEmpty() {
      if (typeMap.isEmpty()) {
        assert fieldMap.isEmpty();
        assert methodMap.isEmpty();
        return true;
      }
      return false;
    }

    void move(DexType from, DexType to) {
      DexType old = typeMap.put(from, to);
      assert old == null || old == to;
    }

    void move(DexField from, DexField to) {
      DexField old = fieldMap.put(from, to);
      assert old == null || old == to;
    }

    void move(DexMethod from, DexMethod to) {
      methodMap.put(from, to);
    }

    void setRepresentative(DexField field, DexField representative) {
      fieldMap.setRepresentative(field, representative);
    }

    void setRepresentative(DexMethod method, DexMethod representative) {
      methodMap.setRepresentative(method, representative);
    }

    SyntheticFinalizationGraphLens build(AppView<?> appView) {
      if (typeMap.isEmpty() && fieldMap.isEmpty() && methodMap.isEmpty()) {
        return null;
      }
      return new SyntheticFinalizationGraphLens(appView, fieldMap, methodMap, typeMap);
    }
  }

  private final InternalOptions options;
  private final SyntheticItems synthetics;
  private final CommittedSyntheticsCollection committed;

  SyntheticFinalization(
      InternalOptions options, SyntheticItems synthetics, CommittedSyntheticsCollection committed) {
    this.options = options;
    this.synthetics = synthetics;
    this.committed = committed;
  }

  public static void finalize(
      AppView<AppInfo> appView, Timing timing, ExecutorService executorService)
      throws ExecutionException {
    assert !appView.appInfo().hasClassHierarchy();
    assert !appView.appInfo().hasLiveness();
    appView.options().testing.checkDeterminism(appView);
    Result result = appView.getSyntheticItems().computeFinalSynthetics(appView, timing);
    appView.setAppInfo(new AppInfo(result.commit, result.mainDexInfo));
    if (result.lens != null) {
      appView.setAppInfo(
          appView
              .appInfo()
              .rebuildWithMainDexInfo(
                  appView
                      .appInfo()
                      .getMainDexInfo()
                      .rewrittenWithLens(appView.getSyntheticItems(), result.lens)));
      appView.setGraphLens(result.lens);
    }
    appView.pruneItems(result.prunedItems, executorService);
  }

  public static void finalizeWithClassHierarchy(
      AppView<AppInfoWithClassHierarchy> appView, ExecutorService executorService, Timing timing)
      throws ExecutionException {
    assert !appView.appInfo().hasLiveness();
    appView.options().testing.checkDeterminism(appView);
    Result result = appView.getSyntheticItems().computeFinalSynthetics(appView, timing);
    appView.setAppInfo(appView.appInfo().rebuildWithClassHierarchy(result.commit));
    appView.setAppInfo(appView.appInfo().rebuildWithMainDexInfo(result.mainDexInfo));
    if (result.lens != null) {
      appView.setGraphLens(result.lens);
      appView.setAppInfo(
          appView
              .appInfo()
              .rebuildWithMainDexInfo(
                  appView
                      .appInfo()
                      .getMainDexInfo()
                      .rewrittenWithLens(appView.getSyntheticItems(), result.lens)));
    }
    appView.pruneItems(result.prunedItems, executorService);
  }

  public static void finalizeWithLiveness(
      AppView<AppInfoWithLiveness> appView, ExecutorService executorService, Timing timing)
      throws ExecutionException {
    appView.options().testing.checkDeterminism(appView);
    Result result = appView.getSyntheticItems().computeFinalSynthetics(appView, timing);
    appView.setAppInfo(appView.appInfo().rebuildWithMainDexInfo(result.mainDexInfo));
    if (result.lens != null) {
      appView.rewriteWithLensAndApplication(result.lens, result.commit.getApplication().asDirect());
    } else {
      assert result.commit.getApplication() == appView.appInfo().app();
    }
    appView.setAppInfo(appView.appInfo().rebuildWithLiveness(result.commit));
    appView.pruneItems(result.prunedItems, executorService);
  }

  Result computeFinalSynthetics(AppView<?> appView, Timing timing) {
    assert verifyNoNestedSynthetics(appView.dexItemFactory());
    assert verifyOneSyntheticPerSyntheticClass();
    DexApplication application;
    Builder lensBuilder = new Builder();
    ImmutableMap.Builder<DexType, List<SyntheticMethodReference>> finalMethodsBuilder =
        ImmutableMap.builder();
    ImmutableMap.Builder<DexType, List<SyntheticProgramClassReference>> finalClassesBuilder =
        ImmutableMap.builder();
    Set<DexType> derivedMainDexTypes = Sets.newIdentityHashSet();
    {
      Map<String, NumberGenerator> generators = new HashMap<>();
      application =
          buildLensAndProgram(
              timing,
              appView,
              timing.time(
                  "Method equivalence",
                  () ->
                      computeEquivalences(
                          appView, committed.getMethods(), generators, lensBuilder, timing)),
              timing.time(
                  "Class equivalence",
                  () ->
                      computeEquivalences(
                          appView, committed.getClasses(), generators, lensBuilder, timing)),
              lensBuilder,
              (clazz, reference) ->
                  finalClassesBuilder.put(clazz.getType(), ImmutableList.of(reference)),
              (clazz, reference) ->
                  finalMethodsBuilder.put(clazz.getType(), ImmutableList.of(reference)),
              derivedMainDexTypes);
    }
    ImmutableMap<DexType, List<SyntheticMethodReference>> finalMethods =
        finalMethodsBuilder.build();
    ImmutableMap<DexType, List<SyntheticProgramClassReference>> finalClasses =
        finalClassesBuilder.build();

    Set<DexType> prunedSynthetics = Sets.newIdentityHashSet();
    committed.forEachItem(
        reference -> {
          DexType type = reference.getHolder();
          if (!finalMethods.containsKey(type) && !finalClasses.containsKey(type)) {
            prunedSynthetics.add(type);
          }
        });

    SyntheticFinalizationGraphLens syntheticFinalizationGraphLens = lensBuilder.build(appView);

    ImmutableSet<DexType> finalInputSynthetics =
        syntheticFinalizationGraphLens != null
            ? SetUtils.newImmutableSet(
                builder ->
                    committed.forEachSyntheticInput(
                        syntheticInputType ->
                            builder.accept(
                                syntheticFinalizationGraphLens.lookupType(syntheticInputType))))
            : committed.syntheticInputs;

    // TODO(b/181858113): Remove once deprecated main-dex-list is removed.
    MainDexInfo.Builder mainDexInfoBuilder = appView.appInfo().getMainDexInfo().builderFromCopy();
    derivedMainDexTypes.forEach(mainDexInfoBuilder::addList);

    return new Result(
        new CommittedItems(
            State.FINALIZED,
            application,
            new CommittedSyntheticsCollection(
                synthetics.getNaming(),
                finalMethods,
                finalClasses,
                committed.getGlobalContexts(),
                finalInputSynthetics),
            ImmutableList.of(),
            synthetics.getGlobalSyntheticsStrategy()),
        syntheticFinalizationGraphLens,
        PrunedItems.builder().setPrunedApp(application).addRemovedClasses(prunedSynthetics).build(),
        mainDexInfoBuilder.build());
  }

  private <R extends SyntheticReference<R, D, ?>, D extends SyntheticDefinition<R, D, ?>>
      Map<DexType, EquivalenceGroup<D>> computeEquivalences(
          AppView<?> appView,
          ImmutableMap<DexType, List<R>> references,
          Map<String, NumberGenerator> generators,
          Builder lensBuilder,
          Timing timing) {
    boolean intermediate = appView.options().intermediate;
    Map<DexType, D> definitions = lookupDefinitions(appView, references);
    ClassToFeatureSplitMap classToFeatureSplitMap =
        appView.appInfo().hasClassHierarchy()
            ? appView.appInfo().withClassHierarchy().getClassToFeatureSplitMap()
            : ClassToFeatureSplitMap.createEmptyClassToFeatureSplitMap();
    timing.begin("Potential equivalences");
    Collection<List<D>> potentialEquivalences =
        computePotentialEquivalences(
            definitions,
            intermediate,
            appView.dexItemFactory(),
            appView.graphLens(),
            classToFeatureSplitMap,
            synthetics);
    timing.end();
    return computeActualEquivalences(
        potentialEquivalences,
        generators,
        appView,
        intermediate,
        classToFeatureSplitMap,
        lensBuilder,
        timing);
  }

  private boolean isNotSyntheticType(DexType type) {
    return !committed.containsType(type);
  }

  private boolean verifyNoNestedSynthetics(DexItemFactory dexItemFactory) {
    // Check that the prefix of each synthetic is never itself synthetic.
    committed.forEachItem(
        item -> {
          if (item.getKind().isGlobal()) {
            return;
          }
          String prefix =
              SyntheticNaming.getPrefixForExternalSyntheticType(item.getKind(), item.getHolder());
          assert !prefix.contains(SyntheticNaming.getPhaseSeparator(Phase.INTERNAL));
          DexType context =
              dexItemFactory.createType(DescriptorUtils.getDescriptorFromClassBinaryName(prefix));
          assert isNotSyntheticType(context) || synthetics.isGlobalSyntheticClass(context);
        });
    return true;
  }

  private boolean verifyOneSyntheticPerSyntheticClass() {
    Set<DexType> seen = Sets.newIdentityHashSet();
    committed
        .getClasses()
        .forEach(
            (type, references) -> {
              assert seen.add(type);
              assert references.size() == 1;
            });
    committed
        .getMethods()
        .forEach(
            (type, references) -> {
              assert seen.add(type);
              assert references.size() == 1;
            });
    return true;
  }

  private static void ensureSourceFile(
      DexProgramClass externalSyntheticClass, DexString syntheticSourceFileName) {
    if (externalSyntheticClass.getSourceFile() == null) {
      externalSyntheticClass.setSourceFile(syntheticSourceFileName);
    }
  }

  private static DexApplication buildLensAndProgram(
      Timing timing,
      AppView<?> appView,
      Map<DexType, EquivalenceGroup<SyntheticMethodDefinition>> syntheticMethodGroups,
      Map<DexType, EquivalenceGroup<SyntheticProgramClassDefinition>> syntheticClassGroups,
      Builder lensBuilder,
      BiConsumer<DexProgramClass, SyntheticProgramClassReference> addFinalSyntheticClass,
      BiConsumer<DexProgramClass, SyntheticMethodReference> addFinalSyntheticMethod,
      Set<DexType> derivedMainDexSynthetics) {
    DexApplication application = appView.appInfo().app();
    MainDexInfo mainDexInfo = appView.appInfo().getMainDexInfo();
    Set<DexProgramClass> pruned = Sets.newIdentityHashSet();

    TreeFixerBase treeFixer =
        new TreeFixerBase(appView) {
          @Override
          public DexType mapClassType(DexType type) {
            return lensBuilder.typeMap.getOrDefault(type, type);
          }

          @Override
          public void recordFieldChange(DexField from, DexField to) {
            lensBuilder.move(from, to);
          }

          @Override
          public void recordMethodChange(DexMethod from, DexMethod to) {
            lensBuilder.move(from, to);
          }

          @Override
          public void recordClassChange(DexType from, DexType to) {
            lensBuilder.move(from, to);
          }
        };

    List<DexProgramClass> deduplicatedClasses = new ArrayList<>();
    syntheticMethodGroups.forEach(
        (syntheticType, syntheticGroup) -> {
          SyntheticMethodDefinition representative = syntheticGroup.getRepresentative();
          SynthesizingContext context = representative.getContext();
          context.registerPrefixRewriting(syntheticType, appView);
          addSyntheticMarker(representative.getKind(), representative.getHolder(), appView);
          if (syntheticGroup.isDerivedFromMainDexList(mainDexInfo)) {
            derivedMainDexSynthetics.add(syntheticType);
          }
          syntheticGroup.forEachNonRepresentativeMember(
              member -> {
                pruned.add(member.getHolder());
                deduplicatedClasses.add(member.getHolder());
              });
        });

    syntheticClassGroups.forEach(
        (syntheticType, syntheticGroup) -> {
          SyntheticProgramClassDefinition representative = syntheticGroup.getRepresentative();
          SynthesizingContext context = representative.getContext();
          context.registerPrefixRewriting(syntheticType, appView);
          addSyntheticMarker(representative.getKind(), representative.getHolder(), appView);
          if (syntheticGroup.isDerivedFromMainDexList(mainDexInfo)) {
            derivedMainDexSynthetics.add(syntheticType);
          }
          syntheticGroup.forEachNonRepresentativeMember(
              member -> {
                pruned.add(member.getHolder());
                deduplicatedClasses.add(member.getHolder());
              });
        });

    // Only create a new application if anything changed.
    if (lensBuilder.isEmpty()) {
      assert deduplicatedClasses.isEmpty();
      assert pruned.isEmpty();
    } else {
      if (!pruned.isEmpty()) {
        List<DexProgramClass> newProgramClasses = new ArrayList<>();
        for (DexProgramClass clazz : application.classes()) {
          if (!pruned.contains(clazz)) {
            newProgramClasses.add(clazz);
          }
        }
        assert newProgramClasses.size() < application.classes().size();
        application = application.builder().replaceProgramClasses(newProgramClasses).build();
      }

      // Assert that the non-representatives have been removed from the app.
      assert verifyNonRepresentativesRemovedFromApplication(application, syntheticClassGroups);
      assert verifyNonRepresentativesRemovedFromApplication(application, syntheticMethodGroups);

      timing.begin("Tree fixing");
      DexApplication.Builder<?> builder = application.builder();
      treeFixer.fixupClasses(deduplicatedClasses);
      builder.replaceProgramClasses(treeFixer.fixupClasses(application.classes()));
      application = builder.build();
      timing.end();
    }

    DexString syntheticSourceFileName =
        appView.enableWholeProgramOptimizations()
            ? appView.dexItemFactory().createString("R8$$SyntheticClass")
            : appView.dexItemFactory().createString("D8$$SyntheticClass");

    timing.begin("Add final synthetics");
    // Add the synthesized from after repackaging which changed class definitions.
    final DexApplication appForLookup = application;
    syntheticClassGroups.forEach(
        (syntheticType, syntheticGroup) -> {
          DexProgramClass externalSyntheticClass = appForLookup.programDefinitionFor(syntheticType);
          assert externalSyntheticClass != null
              : "Expected definition for " + syntheticType.getTypeName();
          ensureSourceFile(externalSyntheticClass, syntheticSourceFileName);
          SyntheticProgramClassDefinition representative = syntheticGroup.getRepresentative();
          addFinalSyntheticClass.accept(
              externalSyntheticClass,
              new SyntheticProgramClassReference(
                  representative.getKind(),
                  representative.getContext(),
                  externalSyntheticClass.type));
        });
    syntheticMethodGroups.forEach(
        (syntheticType, syntheticGroup) -> {
          DexProgramClass externalSyntheticClass = appForLookup.programDefinitionFor(syntheticType);
          ensureSourceFile(externalSyntheticClass, syntheticSourceFileName);
          SyntheticMethodDefinition representative = syntheticGroup.getRepresentative();
          assert externalSyntheticClass.getMethodCollection().size() == 1;
          assert externalSyntheticClass.getMethodCollection().hasDirectMethods();
          DexEncodedMethod syntheticMethodDefinition =
              externalSyntheticClass.getMethodCollection().getDirectMethod(alwaysTrue());
          addFinalSyntheticMethod.accept(
              externalSyntheticClass,
              new SyntheticMethodReference(
                  representative.getKind(),
                  representative.getContext(),
                  syntheticMethodDefinition.getReference()));
        });
    timing.end();

    timing.begin("Finish lens");
    Iterables.<EquivalenceGroup<? extends SyntheticDefinition<?, ?, DexProgramClass>>>concat(
            syntheticClassGroups.values(), syntheticMethodGroups.values())
        .forEach(
            syntheticGroup ->
                syntheticGroup
                    .getRepresentative()
                    .getHolder()
                    .forEachProgramMember(
                        member -> {
                          if (member.isProgramField()) {
                            DexField field = member.asProgramField().getReference();
                            DexField rewrittenField = treeFixer.fixupFieldReference(field);
                            lensBuilder.setRepresentative(rewrittenField, field);
                          } else {
                            DexMethod method = member.asProgramMethod().getReference();
                            DexMethod rewrittenMethod = treeFixer.fixupMethodReference(method);
                            lensBuilder.setRepresentative(rewrittenMethod, method);
                          }
                        }));
    timing.end();

    for (DexType key : syntheticMethodGroups.keySet()) {
      assert application.definitionFor(key) != null;
    }

    for (DexType key : syntheticClassGroups.keySet()) {
      assert application.definitionFor(key) != null;
    }

    return application;
  }

  private static <T extends SyntheticDefinition<?, T, ?>>
      boolean verifyNonRepresentativesRemovedFromApplication(
          DexApplication application, Map<DexType, EquivalenceGroup<T>> syntheticGroups) {
    for (EquivalenceGroup<?> syntheticGroup : syntheticGroups.values()) {
      syntheticGroup.forEachNonRepresentativeMember(
          member -> {
            assert application.definitionFor(member.getHolder().getType()) == null;
          });
    }
    return true;
  }

  private static void addSyntheticMarker(
      SyntheticKind kind,
      DexProgramClass externalSyntheticClass,
      AppView<?> appView) {
    if (shouldAnnotateSynthetics(appView.options())) {
      SyntheticMarker.addMarkerToClass(externalSyntheticClass, kind, appView.options());
    }
  }

  private static boolean shouldAnnotateSynthetics(InternalOptions options) {
    // Only intermediate builds have annotated synthetics to allow later sharing.
    // Also, CF builds are marked in the writer using an attribute.
    return options.intermediate && options.isGeneratingDex();
  }

  private <T extends SyntheticDefinition<?, T, ?>>
      Map<DexType, EquivalenceGroup<T>> computeActualEquivalences(
          Collection<List<T>> potentialEquivalences,
          Map<String, NumberGenerator> generators,
          AppView<?> appView,
          boolean intermediate,
          ClassToFeatureSplitMap classToFeatureSplitMap,
          Builder lensBuilder,
          Timing timing) {
    Map<String, List<EquivalenceGroup<T>>> groupsPerPrefix = new HashMap<>();
    Map<DexType, EquivalenceGroup<T>> equivalences = new IdentityHashMap<>();
    timing.begin("Groups");
    potentialEquivalences.forEach(
        members -> {
          List<EquivalenceGroup<T>> groups =
              groupEquivalent(appView, members, intermediate, classToFeatureSplitMap);
          for (EquivalenceGroup<T> group : groups) {
            // If the group has a pinned representative don't construct an external type.
            if (group.isPinned(appView)) {
              EquivalenceGroup<T> previous =
                  equivalences.put(group.getRepresentative().getHolder().getType(), group);
              assert previous == null;
            } else {
              groupsPerPrefix
                  .computeIfAbsent(
                      group.getRepresentative().getPrefixForExternalSyntheticType(),
                      k -> new ArrayList<>())
                  .add(group);
            }
          }
        });
    timing.end();
    timing.begin("External creation");
    groupsPerPrefix.forEach(
        (externalSyntheticTypePrefix, groups) -> {
          Comparator<EquivalenceGroup<T>> comparator = this::compareForFinalGroupSorting;
          ListUtils.destructiveSort(groups, comparator);
          for (int i = 0; i < groups.size(); i++) {
            EquivalenceGroup<T> group = groups.get(i);
            assert group
                .getRepresentative()
                .getPrefixForExternalSyntheticType()
                .equals(externalSyntheticTypePrefix);
            // Two equivalence groups in same context type must be distinct otherwise the assignment
            // of the synthetic name will be non-deterministic between the two.
            assert i == 0 || checkGroupsAreDistinct(groups.get(i - 1), group, comparator);
            SyntheticKind kind = group.getRepresentative().getKind();
            DexType representativeType =
                intermediate
                        && synthetics.isSyntheticInput(
                            group.getRepresentative().getHolder().asProgramClass())
                    ? group.getRepresentative().getHolder().getType()
                    : createExternalType(
                        kind,
                        externalSyntheticTypePrefix,
                        generators,
                        appView,
                        candidateType ->
                            equivalences.containsKey(candidateType)
                                || appView
                                    .horizontallyMergedClasses()
                                    .hasBeenMergedIntoDifferentType(candidateType));
            equivalences.put(representativeType, group);
          }
        });
    timing.end();
    equivalences.forEach(
        (representativeType, group) ->
            group.forEach(
                member -> lensBuilder.move(member.getHolder().getType(), representativeType)));
    return equivalences;
  }

  private <T extends SyntheticDefinition<?, T, ?>> int compareForFinalGroupSorting(
      EquivalenceGroup<T> a, EquivalenceGroup<T> b) {
    // Sort the equivalence groups based on the representative types. The representatives are
    // deterministically chosen and the internal synthetics deterministically named so using
    // the internal type as the order is deterministic.
    return a.getRepresentative()
        .getHolder()
        .getType()
        .compareTo(b.getRepresentative().getHolder().getType());
  }

  private static <T extends SyntheticDefinition<?, T, ?>> List<EquivalenceGroup<T>> groupEquivalent(
      AppView<?> appView,
      List<T> potentialEquivalence,
      boolean intermediate,
      ClassToFeatureSplitMap classToFeatureSplitMap) {
    // Fast path the singleton groups.
    if (potentialEquivalence.size() == 1) {
      return ImmutableList.of(EquivalenceGroup.singleton(potentialEquivalence.get(0)));
    }
    assert !potentialEquivalence.isEmpty();

    // Sort the potential members and split them up into potential groups of members that are
    // actually equal.
    GraphLens graphLens = appView.graphLens();
    boolean includeContext =
        intermediate
            || appView
                .options()
                .getStartupInstrumentationOptions()
                .isStartupInstrumentationEnabled();
    List<T> sortedPotentialMembers =
        ListUtils.sort(
            potentialEquivalence,
            (a, b) -> a.compareTo(b, includeContext, graphLens, classToFeatureSplitMap));
    List<List<T>> potentialGroups = new ArrayList<>();
    {
      List<T> currentGroup = new ArrayList<>();
      T currentRepresentative = sortedPotentialMembers.get(0);
      currentGroup.add(currentRepresentative);
      for (int i = 1; i < sortedPotentialMembers.size(); i++) {
        T member = sortedPotentialMembers.get(i);
        if (!currentRepresentative.isEquivalentTo(
            member, includeContext, graphLens, classToFeatureSplitMap)) {
          potentialGroups.add(currentGroup);
          currentGroup = new ArrayList<>();
          currentRepresentative = member;
        }
        currentGroup.add(member);
      }
      potentialGroups.add(currentGroup);
    }

    // Compute the actual groups by picking the group representatives. In cases of pinned members
    // this may need to split out representatives into their own singleton groups.
    List<EquivalenceGroup<T>> actualGroups = new ArrayList<>();
    for (List<T> potentialGroup : potentialGroups) {
      assert !potentialGroup.isEmpty();
      if (potentialGroup.size() == 1) {
        actualGroups.add(EquivalenceGroup.singleton(potentialGroup.get(0)));
        continue;
      }
      List<T> forcedRepresentatives = null;
      if (appView.enableWholeProgramOptimizations()) {
        Iterator<T> it = potentialGroup.iterator();
        while (it.hasNext()) {
          T member = it.next();
          boolean mustBeRepresentative = isPinned(appView, member);
          if (mustBeRepresentative) {
            if (forcedRepresentatives == null) {
              forcedRepresentatives = new ArrayList<>();
            }
            forcedRepresentatives.add(member);
            it.remove();
          }
        }
      }
      if (forcedRepresentatives != null) {
        assert appView.enableWholeProgramOptimizations();
        T representative =
            findSmallestMember(
                forcedRepresentatives,
                other -> actualGroups.add(EquivalenceGroup.pinnedSingleton(other)));
        actualGroups.add(EquivalenceGroup.pinnedGroup(representative, potentialGroup));
      } else {
        List<T> members = new ArrayList<>(potentialGroup.size() - 1);
        T representative = findSmallestMember(potentialGroup, members::add);
        actualGroups.add(EquivalenceGroup.unpinnedGroup(representative, members));
      }
    }
    return actualGroups;
  }

  private static <T extends SyntheticDefinition<?, T, ?>> T findSmallestMember(
      List<T> members, Consumer<T> notSmallestCallback) {
    assert !members.isEmpty();
    T smallest = members.get(0);
    for (int i = 1; i < members.size(); i++) {
      T member = members.get(i);
      if (member.toReference().getReference().compareTo(smallest.toReference().getReference())
          < 0) {
        notSmallestCallback.accept(smallest);
        smallest = member;
      } else {
        notSmallestCallback.accept(member);
      }
    }
    return smallest;
  }

  /**
   * In R8, keep rules may apply to synthetics from the input, if the input has been compiled using
   * intermediate mode.
   */
  private static <D extends SyntheticDefinition<?, D, ?>> boolean isPinned(
      AppView<?> appView, D definition) {
    if (!appView.enableWholeProgramOptimizations()) {
      return false;
    }
    if (!definition.getHolder().isProgramClass()) {
      return true;
    }
    DexProgramClass holder = definition.getHolder().asProgramClass();
    // TODO(b/192924387): Change such that the keep info for internal synthetics is always bottom.
    if (!appView.getSyntheticItems().isSubjectToKeepRules(holder)) {
      return false;
    }
    KeepInfoCollection keepInfo = appView.getKeepInfo();
    InternalOptions options = appView.options();
    if (keepInfo.getClassInfo(holder).isPinned(options)) {
      return true;
    }
    for (DexEncodedMember<?, ?> member : holder.members()) {
      if (keepInfo.getMemberInfo(member, holder).isPinned(options)) {
        return true;
      }
    }
    return false;
  }

  private static <T extends SyntheticDefinition<?, T, ?>> boolean checkGroupsAreDistinct(
      EquivalenceGroup<T> g1, EquivalenceGroup<T> g2, Comparator<EquivalenceGroup<T>> comparator) {
    int smaller = comparator.compare(g1, g2);
    assert smaller < 0;
    int bigger = comparator.compare(g2, g1);
    assert bigger > 0;
    return true;
  }

  private DexType createExternalType(
      SyntheticKind kind,
      String externalSyntheticTypePrefix,
      Map<String, NumberGenerator> generators,
      AppView<?> appView,
      Predicate<DexType> reserved) {
    DexItemFactory factory = appView.dexItemFactory();
    if (kind.isFixedSuffixSynthetic()) {
      return SyntheticNaming.createExternalType(kind, externalSyntheticTypePrefix, "", factory);
    }
    NumberGenerator generator =
        generators.computeIfAbsent(externalSyntheticTypePrefix, k -> new NumberGenerator());
    DexType externalType;
    do {
      externalType =
          SyntheticNaming.createExternalType(
              kind, externalSyntheticTypePrefix, Integer.toString(generator.next()), factory);
      // If the generated external type matches an external synthetic from the input, which is kept,
      // then continue.
      if (reserved.test(externalType)) {
        externalType = null;
        continue;
      }
      DexClass clazz = appView.appInfo().definitionForWithoutExistenceAssert(externalType);
      if (clazz != null && isNotSyntheticType(clazz.type)) {
        externalType = null;
      }
    } while (externalType == null);
    return externalType;
  }

  private static <T extends SyntheticDefinition<?, T, ?>>
      Collection<List<T>> computePotentialEquivalences(
          Map<DexType, T> definitions,
          boolean intermediate,
          DexItemFactory factory,
          GraphLens graphLens,
          ClassToFeatureSplitMap classToFeatureSplitMap,
          SyntheticItems syntheticItems) {
    if (definitions.isEmpty()) {
      return Collections.emptyList();
    }
    // Map all synthetic types to the java 'void' type. This is not an actual valid type, so it
    // cannot collide with any valid java type providing a good hashing key for the synthetics.
    Set<DexType> syntheticTypes;
    if (graphLens.isIdentityLens()) {
      syntheticTypes = definitions.keySet();
    } else {
      // If the synthetics are renamed include their original names in the equivalence too.
      syntheticTypes = SetUtils.newIdentityHashSet(definitions.size() * 2);
      definitions
          .keySet()
          .forEach(
              t -> {
                syntheticTypes.add(t);
                syntheticTypes.add(graphLens.getOriginalType(t));
              });
    }
    RepresentativeMap map = t -> syntheticTypes.contains(t) ? factory.voidType : t;
    Map<HashCode, List<T>> equivalences = new HashMap<>(definitions.size());
    for (T definition : definitions.values()) {
      HashCode hash =
          definition.computeHash(map, intermediate, classToFeatureSplitMap, syntheticItems);
      equivalences.computeIfAbsent(hash, k -> new ArrayList<>()).add(definition);
    }
    return equivalences.values();
  }

  private <R extends SyntheticReference<R, D, ?>, D extends SyntheticDefinition<R, D, ?>>
      Map<DexType, D> lookupDefinitions(
          AppView<?> appView, ImmutableMap<DexType, List<R>> references) {
    Map<DexType, D> definitions = new IdentityHashMap<>(references.size());
    for (R reference : IterableUtils.flatten(references.values())) {
      D definition = reference.lookupDefinition(appView::definitionFor);
      if (definition == null) {
        // We expect pruned definitions to have been removed.
        assert false;
        continue;
      }
      if (definition.isValid()) {
        definitions.put(reference.getHolder(), definition);
      } else {
        // Failing this check indicates that an optimization has modified the synthetic in a
        // disruptive way.
        assert false;
      }
    }
    return definitions;
  }

  private static class EquivalenceGroup<T extends SyntheticDefinition<?, T, ?>> {

    // The members of the equivalence group, *excluding* the representative.
    private final List<T> members;
    private final T representative;
    private final OptionalBool pinned;

    static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> singleton(T member) {
      return new EquivalenceGroup<>(member, ImmutableList.of(), OptionalBool.UNKNOWN);
    }

    static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> unpinnedGroup(
        T representative, List<T> members) {
      return new EquivalenceGroup<>(
          representative, Collections.unmodifiableList(members), OptionalBool.FALSE);
    }

    static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> pinnedSingleton(T member) {
      return new EquivalenceGroup<>(member, ImmutableList.of(), OptionalBool.TRUE);
    }

    static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> pinnedGroup(
        T representative, List<T> members) {
      return new EquivalenceGroup<>(
          representative, Collections.unmodifiableList(members), OptionalBool.TRUE);
    }

    private EquivalenceGroup(T representative, List<T> members, OptionalBool pinned) {
      assert representative != null;
      assert members != null;
      assert pinned != null;
      this.members = members;
      this.representative = representative;
      this.pinned = pinned;
    }

    public boolean isPinned(AppView<?> appView) {
      if (pinned.isTrue()) {
        return true;
      }
      if (pinned.isFalse()) {
        return false;
      }
      return SyntheticFinalization.isPinned(appView, representative);
    }

    public void forEach(Consumer<T> consumer) {
      consumer.accept(getRepresentative());
      members.forEach(consumer);
    }

    public void forEachNonRepresentativeMember(Consumer<T> consumer) {
      members.forEach(consumer);
    }

    T getRepresentative() {
      return representative;
    }

    boolean isDerivedFromMainDexList(MainDexInfo mainDexInfo) {
      return getRepresentative().getContext().isDerivedFromMainDexList(mainDexInfo)
          || Iterables.any(
              members, member -> member.getContext().isDerivedFromMainDexList(mainDexInfo));
    }

    @Override
    public String toString() {
      return "EquivalenceGroup{ size = "
          + (members.size() + 1)
          + ", repr = "
          + getRepresentative()
          + " }";
    }
  }
}