// Copyright (c) 2017, 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.graph.DexProgramClass.asProgramClassOrNull;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexField;
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.FieldAccessInfo;
import com.android.tools.r8.graph.FieldAccessInfoCollection;
import com.android.tools.r8.graph.ProgramField;
import com.android.tools.r8.graph.SubtypingInfo;
import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.TraversalContinuation;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Sets;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.Deque;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

class FieldNameMinifier {

  private final AppView<AppInfoWithLiveness> appView;
  private final SubtypingInfo subtypingInfo;
  private final Map<DexField, DexString> renaming = new IdentityHashMap<>();
  private final Map<DexType, ReservedFieldNamingState> reservedNamingStates =
      new IdentityHashMap<>();
  private final MemberNamingStrategy strategy;
  private final Map<DexType, DexType> frontiers = new IdentityHashMap<>();
  private final Map<DexType, Set<ReservedFieldNamingState>> frontierStatesForInterfaces =
      new IdentityHashMap<>();

  FieldNameMinifier(
      AppView<AppInfoWithLiveness> appView,
      SubtypingInfo subtypingInfo,
      MemberNamingStrategy strategy) {
    this.appView = appView;
    this.subtypingInfo = subtypingInfo;
    this.strategy = strategy;
  }

  FieldRenaming computeRenaming(Collection<DexClass> interfaces, Timing timing) {
    // Reserve names in all classes first. We do this in subtyping order so we do not
    // shadow a reserved field in subclasses. While there is no concept of virtual field
    // dispatch in Java, field resolution still traverses the super type chain and external
    // code might use a subtype to reference the field.
    timing.begin("reserve-names");
    reserveFieldNames();
    timing.end();
    // Rename the definitions.
    timing.begin("rename-definitions");
    renameFieldsInInterfaces(interfaces);
    renameFieldsInClasses();
    renameFieldsInUnrelatedClasspathClasses();
    timing.end();
    // Rename the references that are not rebound to definitions for some reasons.
    timing.begin("rename-references");
    renameNonReboundReferences();
    timing.end();
    return new FieldRenaming(renaming);
  }

  static class FieldRenaming {

    final Map<DexField, DexString> renaming;

    private FieldRenaming(Map<DexField, DexString> renaming) {
      this.renaming = renaming;
    }

    public static FieldRenaming empty() {
      return new FieldRenaming(ImmutableMap.of());
    }
  }

  private ReservedFieldNamingState getReservedFieldNamingState(DexType type) {
    return reservedNamingStates.get(type);
  }

  private ReservedFieldNamingState getOrCreateReservedFieldNamingState(DexType type) {
    return reservedNamingStates.computeIfAbsent(
        type, ignore -> new ReservedFieldNamingState(appView));
  }

  private void reserveFieldNames() {
    // Build up all reservations in the class hierarchy such that all reserved names are placed
    // at the boundary between a library class and a program class - referred to as the frontier.
    // Special handling is done for interfaces by always considering them to be roots. When
    // traversing down the hierarchy we built up a map from interface to reservation states:
    // - when we reach a frontier find all directly and indirectly implemented interfaces and
    //   add the current reservation state
    // - when we see a program class that implements a direct super type that is an interface also
    //   add the current reservation state. Note that even though we do not visit super interfaces
    //   here, this still works because a super interface will be in the same partition.
    // For an in depth description see MethodNameMinifier.
    TopDownClassHierarchyTraversal.forAllClasses(appView)
        .visit(
            appView.appInfo().classes(),
            clazz -> {
              DexType frontier =
                  clazz.superType == null
                      ? appView.dexItemFactory().objectType
                      : frontiers.getOrDefault(clazz.superType, clazz.type);
              // If frontier != clazz.type we have seen a program class that is on the boundary.
              // Otherwise, if we are visiting a program class then that is the frontier.
              if (frontier != clazz.type || clazz.isProgramClass()) {
                DexType existingValue = frontiers.put(clazz.type, frontier);
                assert existingValue == null;
              }
              ReservedFieldNamingState reservationState =
                  getOrCreateReservedFieldNamingState(frontier);
              for (DexEncodedField field : clazz.fields()) {
                DexString reservedName = strategy.getReservedName(field, clazz);
                if (reservedName != null) {
                  reservationState.markReserved(
                      reservedName, field.getReference().name, field.getReference().type);
                  // TODO(b/148846065): Consider lazily computing the renaming on actual lookups.
                  if (reservedName != field.getReference().name) {
                    renaming.put(field.getReference(), reservedName);
                  }
                }
              }
              if (clazz.isInterface()) {
                frontierStatesForInterfaces.put(
                    clazz.type, SetUtils.newIdentityHashSet(reservationState));
              }
              // Include all reservations from super frontier states. This will propagate reserved
              // names for interfaces down to implementing subtypes.
              for (DexType superType : clazz.allImmediateSupertypes()) {
                // No need to visit object since there are no fields there.
                if (superType != appView.dexItemFactory().objectType) {
                  ReservedFieldNamingState superReservationState =
                      getOrCreateReservedFieldNamingState(
                          frontiers.getOrDefault(superType, superType));
                  if (superReservationState != reservationState) {
                    reservationState.includeReservations(superReservationState);
                  }
                  if (clazz.isProgramClass()) {
                    DexClass superClass = appView.definitionFor(superType, clazz.asProgramClass());
                    if (superClass != null && superClass.isInterface()) {
                      frontierStatesForInterfaces.get(superType).add(reservationState);
                    }
                  }
                }
              }
              if (frontier == clazz.type && clazz.isProgramClass()) {
                patchUpAllIndirectlyImplementingInterfacesFromLibraryAndClassPath(
                    clazz.asProgramClass(), reservationState);
              }
            });
  }

  private void patchUpAllIndirectlyImplementingInterfacesFromLibraryAndClassPath(
      DexProgramClass clazz, ReservedFieldNamingState reservationState) {
    appView
        .appInfo()
        .traverseSuperTypes(
            clazz,
            (superType, superClass, isInterface) -> {
              if (isInterface && superClass.isNotProgramClass()) {
                Set<ReservedFieldNamingState> reservedNamingState =
                    frontierStatesForInterfaces.get(superType);
                if (reservedNamingState != null) {
                  reservedNamingState.add(reservationState);
                }
              }
              return TraversalContinuation.doContinue();
            });
  }

  private void renameFieldsInClasses() {
    Map<DexType, FieldNamingState> states = new IdentityHashMap<>();
    TopDownClassHierarchyTraversal.forAllClasses(appView)
        .excludeInterfaces()
        .visit(
            appView.appInfo().classes(),
            clazz -> {
              assert !clazz.isInterface();

              FieldNamingState parentState =
                  clazz.superType == null
                      ? new FieldNamingState(appView, strategy)
                      : states
                          .computeIfAbsent(
                              clazz.superType, key -> new FieldNamingState(appView, strategy))
                          .clone();

              ReservedFieldNamingState reservedNames =
                  getReservedFieldNamingState(frontiers.getOrDefault(clazz.type, clazz.type));
              FieldNamingState state = parentState.createChildState(reservedNames);
              if (clazz.isProgramClass()) {
                clazz.asProgramClass().forEachProgramField(field -> renameField(field, state));
              }

              assert !states.containsKey(clazz.type);
              states.put(clazz.type, state);
            });
  }

  private void renameFieldsInUnrelatedClasspathClasses() {
    if (appView.options().getProguardConfiguration().hasApplyMappingFile()) {
      appView
          .appInfo()
          .forEachReferencedClasspathClass(
              clazz -> {
                for (DexEncodedField field : clazz.fields()) {
                  DexString reservedName = strategy.getReservedName(field, clazz);
                  if (reservedName != null && reservedName != field.getReference().name) {
                    renaming.put(field.getReference(), reservedName);
                  }
                }
              });
    }
  }

  private void renameFieldsInInterfaces(Collection<DexClass> interfaces) {
    // TODO(b/213415674): Only consider interfaces in the hierarchy of classes.
    InterfacePartitioning partitioning = new InterfacePartitioning(this);
    for (Set<DexClass> partition : partitioning.sortedPartitions(interfaces)) {
      renameFieldsInInterfacePartition(partition);
    }
  }

  private void renameFieldsInInterfacePartition(Set<DexClass> partition) {
    ReservedFieldNamingState namesToBeReservedInImplementsSubclasses =
        new ReservedFieldNamingState(appView);
    ReservedFieldNamingState reservedNamesInPartition = new ReservedFieldNamingState(appView);
    for (DexClass clazz : partition) {
      ReservedFieldNamingState reservedNamesInInterface =
          getReservedFieldNamingState(frontiers.getOrDefault(clazz.type, clazz.type));
      if (reservedNamesInInterface != null) {
        reservedNamesInPartition.includeReservations(reservedNamesInInterface);
        Set<ReservedFieldNamingState> reservedFieldNamingStates =
            frontierStatesForInterfaces.get(clazz.type);
        assert reservedFieldNamingStates != null;
        reservedFieldNamingStates.forEach(
            reservedStates -> {
              reservedNamesInPartition.includeReservations(reservedStates);
              reservedStates.setInterfaceMinificationState(namesToBeReservedInImplementsSubclasses);
            });
      }
    }
    FieldNamingState state = new FieldNamingState(appView, strategy, reservedNamesInPartition);
    for (DexClass clazz : partition) {
      if (clazz.isProgramClass()) {
        assert clazz.isInterface();
        clazz
            .asProgramClass()
            .forEachProgramField(
                field -> {
                  DexString newName = renameField(field, state);
                  namesToBeReservedInImplementsSubclasses.markReserved(
                      newName, field.getReference().name, field.getReference().type);
                });
      }
    }
  }

  private DexString renameField(ProgramField field, FieldNamingState state) {
    DexString newName = state.getOrCreateNameFor(field);
    if (newName != field.getReference().name) {
      renaming.put(field.getReference(), newName);
    }
    return newName;
  }

  private void renameNonReboundReferences() {
    FieldAccessInfoCollection<?> fieldAccessInfoCollection =
        appView.appInfo().getFieldAccessInfoCollection();
    fieldAccessInfoCollection.forEach(this::renameNonReboundAccessesToField);
  }

  private void renameNonReboundAccessesToField(FieldAccessInfo fieldAccessInfo) {
    fieldAccessInfo.forEachIndirectAccess(this::renameNonReboundAccessToField);
  }

  private void renameNonReboundAccessToField(DexField field) {
    // If the given field reference is a non-rebound reference to a program field, then assign the
    // same name as the resolved field.
    if (renaming.containsKey(field)) {
      return;
    }
    DexProgramClass holder = asProgramClassOrNull(appView.definitionForHolder(field));
    if (holder == null) {
      return;
    }
    DexEncodedField definition = appView.appInfo().resolveFieldOn(holder, field).getResolvedField();
    if (definition != null
        && definition.getReference() != field
        && renaming.containsKey(definition.getReference())) {
      renaming.put(field, renaming.get(definition.getReference()));
    }
  }

  static class InterfacePartitioning {

    private final FieldNameMinifier minifier;
    private final AppView<AppInfoWithLiveness> appView;
    private final Set<DexType> visited = Sets.newIdentityHashSet();

    InterfacePartitioning(FieldNameMinifier minifier) {
      this.minifier = minifier;
      appView = minifier.appView;
    }

    private List<Set<DexClass>> sortedPartitions(Collection<DexClass> interfaces) {
      List<Set<DexClass>> partitions = new ArrayList<>();
      for (DexClass clazz : interfaces) {
        if (clazz != null && visited.add(clazz.type)) {
          Set<DexClass> partition = buildSortedPartition(clazz);
          assert !partition.isEmpty();
          assert partition.stream().allMatch(DexClass::isInterface);
          assert partition.stream().map(DexClass::getType).allMatch(visited::contains);
          partitions.add(partition);
        }
      }
      return partitions;
    }

    private Set<DexClass> buildSortedPartition(DexClass src) {
      Set<DexClass> partition = new TreeSet<>(Comparator.comparing(DexClass::getType));

      Deque<DexType> worklist = new ArrayDeque<>();
      worklist.add(src.type);

      while (!worklist.isEmpty()) {
        DexType type = worklist.removeFirst();

        DexClass clazz = appView.definitionFor(type);
        if (clazz == null) {
          continue;
        }

        for (DexType superinterface : clazz.interfaces.values) {
          if (visited.add(superinterface)) {
            worklist.add(superinterface);
          }
        }

        if (clazz.isInterface()) {
          partition.add(clazz);

          for (DexType subtype : minifier.subtypingInfo.allImmediateSubtypes(type)) {
            if (visited.add(subtype)) {
              worklist.add(subtype);
            }
          }
        } else if (clazz.type != appView.dexItemFactory().objectType) {
          if (visited.add(clazz.superType)) {
            worklist.add(clazz.superType);
          }
          for (DexType subclass : minifier.subtypingInfo.allImmediateExtendsSubtypes(type)) {
            if (visited.add(subclass)) {
              worklist.add(subclass);
            }
          }
        }
      }

      return partition;
    }
  }
}