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

import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
import static com.android.tools.r8.graph.FieldAccessInfoImpl.MISSING_FIELD_ACCESS_INFO;
import static com.android.tools.r8.naming.IdentifierNameStringUtils.identifyIdentifier;
import static com.android.tools.r8.naming.IdentifierNameStringUtils.isReflectionMethod;
import static com.android.tools.r8.shaking.AnnotationRemover.shouldKeepAnnotation;
import static com.android.tools.r8.shaking.EnqueuerUtils.toImmutableSortedMap;

import com.android.tools.r8.Diagnostic;
import com.android.tools.r8.cf.code.CfFieldInstruction;
import com.android.tools.r8.cf.code.CfInstruction;
import com.android.tools.r8.cf.code.CfInvoke;
import com.android.tools.r8.cf.code.CfInvokeDynamic;
import com.android.tools.r8.cf.code.CfLoad;
import com.android.tools.r8.cf.code.CfNew;
import com.android.tools.r8.cf.code.CfStackInstruction;
import com.android.tools.r8.cf.code.CfStackInstruction.Opcode;
import com.android.tools.r8.cf.code.CfStore;
import com.android.tools.r8.dex.IndexedItemCollection;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.experimental.graphinfo.GraphConsumer;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.CfCode;
import com.android.tools.r8.graph.DexAnnotation;
import com.android.tools.r8.graph.DexAnnotationSet;
import com.android.tools.r8.graph.DexApplication;
import com.android.tools.r8.graph.DexCallSite;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexClassAndMethod;
import com.android.tools.r8.graph.DexClasspathClass;
import com.android.tools.r8.graph.DexDefinition;
import com.android.tools.r8.graph.DexEncodedField;
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.DexItem;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexLibraryClass;
import com.android.tools.r8.graph.DexMember;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexMethodHandle;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexProto;
import com.android.tools.r8.graph.DexReference;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.DirectMappedDexApplication;
import com.android.tools.r8.graph.DirectMappedDexApplication.Builder;
import com.android.tools.r8.graph.EnclosingMethodAttribute;
import com.android.tools.r8.graph.EnumValueInfoMapCollection;
import com.android.tools.r8.graph.FieldAccessInfoCollectionImpl;
import com.android.tools.r8.graph.FieldAccessInfoImpl;
import com.android.tools.r8.graph.InnerClassAttribute;
import com.android.tools.r8.graph.LookupLambdaTarget;
import com.android.tools.r8.graph.LookupTarget;
import com.android.tools.r8.graph.ObjectAllocationInfoCollectionImpl;
import com.android.tools.r8.graph.PresortedComparable;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.graph.ResolutionResult;
import com.android.tools.r8.graph.ResolutionResult.FailedResolutionResult;
import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
import com.android.tools.r8.graph.SubtypingInfo;
import com.android.tools.r8.graph.UseRegistry.MethodHandleUse;
import com.android.tools.r8.graph.analysis.DesugaredLibraryConversionWrapperAnalysis;
import com.android.tools.r8.graph.analysis.EnqueuerAnalysis;
import com.android.tools.r8.graph.analysis.EnqueuerInvokeAnalysis;
import com.android.tools.r8.ir.analysis.proto.ProtoEnqueuerUseRegistry;
import com.android.tools.r8.ir.analysis.proto.schema.ProtoEnqueuerExtension;
import com.android.tools.r8.ir.code.ArrayPut;
import com.android.tools.r8.ir.code.ConstantValueUtils;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.InvokeMethod;
import com.android.tools.r8.ir.code.InvokeVirtual;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.code.ValueType;
import com.android.tools.r8.ir.desugar.DesugaredLibraryAPIConverter;
import com.android.tools.r8.ir.desugar.LambdaClass;
import com.android.tools.r8.ir.desugar.LambdaDescriptor;
import com.android.tools.r8.ir.desugar.LambdaRewriter;
import com.android.tools.r8.logging.Log;
import com.android.tools.r8.origin.Origin;
import com.android.tools.r8.shaking.DelayedRootSetActionItem.InterfaceMethodSyntheticBridgeAction;
import com.android.tools.r8.shaking.EnqueuerWorklist.EnqueuerAction;
import com.android.tools.r8.shaking.GraphReporter.KeepReasonWitness;
import com.android.tools.r8.shaking.RootSetBuilder.ConsequentRootSet;
import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
import com.android.tools.r8.shaking.ScopedDexMethodSet.AddMethodIfMoreVisibleResult;
import com.android.tools.r8.utils.Action;
import com.android.tools.r8.utils.DequeUtils;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.InternalOptions.DesugarState;
import com.android.tools.r8.utils.MethodSignatureEquivalence;
import com.android.tools.r8.utils.OptionalBool;
import com.android.tools.r8.utils.Pair;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.StringDiagnostic;
import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.Visibility;
import com.android.tools.r8.utils.WorkList;
import com.google.common.base.Equivalence.Wrapper;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ImmutableSortedSet;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.common.collect.Sets.SetView;
import it.unimi.dsi.fastutil.objects.Object2BooleanArrayMap;
import it.unimi.dsi.fastutil.objects.Object2BooleanMap;
import java.lang.reflect.InvocationHandler;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.SortedSet;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.function.BiConsumer;
import java.util.function.Function;
import java.util.function.Predicate;
import org.objectweb.asm.Opcodes;

/**
 * Approximates the runtime dependencies for the given set of roots.
 * <p>
 * <p>The implementation filters the static call-graph with liveness information on classes to
 * remove virtual methods that are reachable by their static type but are unreachable at runtime as
 * they are not visible from any instance.
 * <p>
 * <p>As result of the analysis, an instance of {@link AppInfoWithLiveness} is returned. See the
 * field descriptions for details.
 */
public class Enqueuer {

  public enum Mode {
    INITIAL_TREE_SHAKING,
    FINAL_TREE_SHAKING,
    MAIN_DEX_TRACING,
    WHY_ARE_YOU_KEEPING;

    public boolean isInitialTreeShaking() {
      return this == INITIAL_TREE_SHAKING;
    }

    public boolean isFinalTreeShaking() {
      return this == FINAL_TREE_SHAKING;
    }

    public boolean isInitialOrFinalTreeShaking() {
      return isInitialTreeShaking() || isFinalTreeShaking();
    }

    public boolean isTracingMainDex() {
      return this == MAIN_DEX_TRACING;
    }
  }

  private final boolean forceProguardCompatibility;
  private final Mode mode;

  private Set<EnqueuerAnalysis> analyses = Sets.newIdentityHashSet();
  private Set<EnqueuerInvokeAnalysis> invokeAnalyses = Sets.newIdentityHashSet();

  // Don't hold a direct pointer to app info (use appView).
  private AppInfoWithClassHierarchy appInfo;
  private final AppView<AppInfoWithClassHierarchy> appView;
  private SubtypingInfo subtypingInfo;
  private final InternalOptions options;
  private RootSet rootSet;
  private ProguardClassFilter dontWarnPatterns;
  private final EnqueuerUseRegistryFactory useRegistryFactory;
  private AnnotationRemover.Builder annotationRemoverBuilder;

  private final Map<DexMethod, Set<DexEncodedMethod>> virtualInvokes = new IdentityHashMap<>();
  private final Map<DexMethod, Set<DexEncodedMethod>> interfaceInvokes = new IdentityHashMap<>();
  private final Map<DexMethod, Set<DexEncodedMethod>> superInvokes = new IdentityHashMap<>();
  private final Map<DexMethod, Set<DexEncodedMethod>> directInvokes = new IdentityHashMap<>();
  private final Map<DexMethod, Set<DexEncodedMethod>> staticInvokes = new IdentityHashMap<>();
  private final FieldAccessInfoCollectionImpl fieldAccessInfoCollection =
      new FieldAccessInfoCollectionImpl();
  private final ObjectAllocationInfoCollectionImpl.Builder objectAllocationInfoCollection;
  private final Set<DexCallSite> callSites = Sets.newIdentityHashSet();

  private final Set<DexReference> identifierNameStrings = Sets.newIdentityHashSet();

  /**
   * Tracks the dependency between a method and the super-method it calls, if any. Used to make
   * super methods become live when they become reachable from a live sub-method.
   */
  private final Map<DexEncodedMethod, Set<DexEncodedMethod>> superInvokeDependencies = Maps
      .newIdentityHashMap();
  /** Set of instance fields that can be reached by read/write operations. */
  private final Map<DexProgramClass, SetWithReason<DexEncodedField>> reachableInstanceFields =
      Maps.newIdentityHashMap();

  /**
   * Set of types that are mentioned in the program. We at least need an empty abstract class item
   * for these.
   */
  private final SetWithReportedReason<DexProgramClass> liveTypes;

  /** Set of types whose class initializer may execute. */
  private final SetWithReportedReason<DexProgramClass> initializedTypes;

  /**
   * Set of live types defined in the library and classpath.
   *
   * <p>Used to build a new app of just referenced types and avoid duplicate tracing.
   */
  private final Set<DexClass> liveNonProgramTypes = Sets.newIdentityHashSet();

  /** Set of reachable proto types that will be dead code eliminated. */
  private final Set<DexProgramClass> deadProtoTypeCandidates = Sets.newIdentityHashSet();

  /** Set of missing types. */
  private final Set<DexType> missingTypes = Sets.newIdentityHashSet();

  /** Set of proto types that were found to be dead during the first round of tree shaking. */
  private Set<DexType> initialDeadProtoTypes;

  /** Set of types that were found to be missing during the first round of tree shaking. */
  private Set<DexType> initialMissingTypes;

  /** Mapping from each unused interface to the set of live types that implements the interface. */
  private final Map<DexProgramClass, Set<DexProgramClass>> unusedInterfaceTypes =
      new IdentityHashMap<>();

  /**
   * Set of methods that are the immediate target of an invoke. They might not actually be live but
   * are required so that invokes can find the method. If a method is only a target but not live,
   * its implementation may be removed and it may be marked abstract.
   */
  private final SetWithReason<DexEncodedMethod> targetedMethods;

  /** Set of methods that have invalid resolutions or lookups. */
  private final Set<DexMethod> failedResolutionTargets;

  /**
   * Set of program methods that are used as the bootstrap method for an invoke-dynamic instruction.
   */
  private final Set<DexMethod> bootstrapMethods = Sets.newIdentityHashSet();
  /**
   * Set of direct methods that are the immediate target of an invoke-dynamic.
   */
  private final Set<DexMethod> methodsTargetedByInvokeDynamic = Sets.newIdentityHashSet();
  /** Set of direct lambda implementation methods that have been desugared, thus they may move. */
  private final Set<DexMethod> desugaredLambdaImplementationMethods = Sets.newIdentityHashSet();
  /**
   * Set of virtual methods that are the immediate target of an invoke-direct.
   */
  private final Set<DexMethod> virtualMethodsTargetedByInvokeDirect = Sets.newIdentityHashSet();
  /**
   * Set of methods that belong to live classes and can be reached by invokes. These need to be
   * kept.
   */
  private final LiveMethodsSet liveMethods;

  /**
   * Set of fields that belong to live classes and can be reached by invokes. These need to be kept.
   */
  private final SetWithReason<DexEncodedField> liveFields;

  /**
   * Set of service types (from META-INF/services/) that may have been instantiated reflectively via
   * ServiceLoader.load() or ServiceLoader.loadInstalled().
   */
  private final Set<DexType> instantiatedAppServices = Sets.newIdentityHashSet();

  /** A queue of items that need processing. Different items trigger different actions. */
  private final EnqueuerWorklist workList;

  /**
   * A set of methods that need code inspection for Java reflection in use.
   */
  private final Set<DexEncodedMethod> pendingReflectiveUses = Sets.newLinkedHashSet();

  /** Mapping of types to the methods reachable at that type. */
  private final Map<DexProgramClass, Set<DexMethod>> reachableVirtualTargets =
      new IdentityHashMap<>();

  /**
   * A set of references we have reported missing to dedupe warnings.
   */
  private final Set<DexReference> reportedMissing = Sets.newIdentityHashSet();

  /**
   * A set of references that we are keeping due to keep rules. This may differ from the root set
   * due to dependent keep rules.
   */
  private final Set<DexReference> pinnedItems = Sets.newIdentityHashSet();

  /**
   * A set of seen const-class references that both serve as an initial lock-candidate set and will
   * prevent statically merging the classes referenced.
   */
  private final Set<DexType> constClassReferences = Sets.newIdentityHashSet();

  /**
   * A map from seen init-class references to the minimum required visibility of the corresponding
   * static field.
   */
  private final Map<DexType, Visibility> initClassReferences = new IdentityHashMap<>();

  /**
   * A map from annotation classes to annotations that need to be processed should the classes ever
   * become live.
   */
  private final Map<DexType, Set<DexAnnotation>> deferredAnnotations = new IdentityHashMap<>();

  /** Map of active if rules to speed up aapt2 generated keep rules. */
  private Map<Wrapper<ProguardIfRule>, Set<ProguardIfRule>> activeIfRules;

  /**
   * A cache of ScopedDexMethodSet for each live type used for determining that virtual methods that
   * cannot be removed because they are widening access for another virtual method defined earlier
   * in the type hierarchy. See b/136698023 for more information.
   */
  private final Map<DexType, ScopedDexMethodSet> scopedMethodsForLiveTypes =
      new IdentityHashMap<>();

  private final GraphReporter graphReporter;

  private final LambdaRewriter lambdaRewriter;
  private final DesugaredLibraryConversionWrapperAnalysis desugaredLibraryWrapperAnalysis;
  private final Map<DexType, Pair<LambdaClass, DexEncodedMethod>> lambdaClasses =
      new IdentityHashMap<>();
  private final Map<DexEncodedMethod, Map<DexCallSite, LambdaClass>> lambdaCallSites =
      new IdentityHashMap<>();
  private final Set<DexProgramClass> classesWithSerializableLambdas = Sets.newIdentityHashSet();

  Enqueuer(
      AppView<? extends AppInfoWithClassHierarchy> appView,
      SubtypingInfo subtypingInfo,
      GraphConsumer keptGraphConsumer,
      Mode mode) {
    assert appView.appServices() != null;
    InternalOptions options = appView.options();
    this.appInfo = appView.appInfo();
    this.appView = appView.withClassHierarchy();
    this.subtypingInfo = subtypingInfo;
    assert subtypingInfo.verifyEquals(appView.appInfo().app().asDirect().allClasses(), appView);
    this.forceProguardCompatibility = options.forceProguardCompatibility;
    this.graphReporter = new GraphReporter(appView, keptGraphConsumer);
    this.mode = mode;
    this.options = options;
    this.useRegistryFactory = createUseRegistryFactory();
    this.workList = EnqueuerWorklist.createWorklist(appView);

    if (options.protoShrinking().enableGeneratedMessageLiteShrinking
        && mode.isInitialOrFinalTreeShaking()) {
      registerAnalysis(new ProtoEnqueuerExtension(appView));
    }

    liveTypes = new SetWithReportedReason<>();
    initializedTypes = new SetWithReportedReason<>();
    targetedMethods = new SetWithReason<>(graphReporter::registerMethod);
    // This set is only populated in edge cases due to multiple default interface methods.
    // The set is generally expected to be empty and in the unlikely chance it is not, it will
    // likely contain two methods. Thus the default capacity of 2.
    failedResolutionTargets = SetUtils.newIdentityHashSet(2);
    liveMethods = new LiveMethodsSet(graphReporter::registerMethod);
    liveFields = new SetWithReason<>(graphReporter::registerField);
    lambdaRewriter = options.desugarState == DesugarState.ON ? new LambdaRewriter(appView) : null;

    objectAllocationInfoCollection =
        ObjectAllocationInfoCollectionImpl.builder(mode.isInitialTreeShaking(), graphReporter);

    if (appView.rewritePrefix.isRewriting() && mode.isInitialTreeShaking()) {
      desugaredLibraryWrapperAnalysis = new DesugaredLibraryConversionWrapperAnalysis(appView);
      registerAnalysis(desugaredLibraryWrapperAnalysis);
      registerInvokeAnalysis(desugaredLibraryWrapperAnalysis);
    } else {
      desugaredLibraryWrapperAnalysis = null;
    }
  }

  private AppInfoWithClassHierarchy appInfo() {
    return appView.appInfo();
  }

  public Mode getMode() {
    return mode;
  }

  public GraphReporter getGraphReporter() {
    return graphReporter;
  }

  private EnqueuerUseRegistryFactory createUseRegistryFactory() {
    if (mode.isFinalTreeShaking()) {
      return appView.withGeneratedMessageLiteShrinker(
          ignore -> ProtoEnqueuerUseRegistry.getFactory(), DefaultEnqueuerUseRegistry::new);
    }
    return DefaultEnqueuerUseRegistry::new;
  }

  public EnqueuerUseRegistryFactory getUseRegistryFactory() {
    return useRegistryFactory;
  }

  public Enqueuer registerAnalysis(EnqueuerAnalysis analysis) {
    analyses.add(analysis);
    return this;
  }

  private Enqueuer registerInvokeAnalysis(EnqueuerInvokeAnalysis analysis) {
    invokeAnalyses.add(analysis);
    return this;
  }

  public void setAnnotationRemoverBuilder(AnnotationRemover.Builder annotationRemoverBuilder) {
    this.annotationRemoverBuilder = annotationRemoverBuilder;
  }

  public void setInitialDeadProtoTypes(Set<DexType> initialDeadProtoTypes) {
    assert mode.isFinalTreeShaking();
    this.initialDeadProtoTypes = initialDeadProtoTypes;
  }

  public void setInitialMissingTypes(Set<DexType> initialMissingTypes) {
    assert mode.isFinalTreeShaking();
    this.initialMissingTypes = initialMissingTypes;
  }

  public void addDeadProtoTypeCandidate(DexType type) {
    assert type.isProgramType(appView);
    addDeadProtoTypeCandidate(appView.definitionFor(type).asProgramClass());
  }

  public void addDeadProtoTypeCandidate(DexProgramClass clazz) {
    deadProtoTypeCandidates.add(clazz);
  }

  private boolean isProgramClass(DexType type) {
    return getProgramClassOrNull(type) != null;
  }

  private void recordReference(DexReference r) {
    if (r.isDexType()) {
      recordTypeReference(r.asDexType());
    } else if (r.isDexField()) {
      recordFieldReference(r.asDexField());
    } else {
      assert r.isDexMethod();
      recordMethodReference(r.asDexMethod());
    }
  }

  private void recordTypeReference(DexType type) {
    if (type == null) {
      return;
    }
    if (type.isArrayType()) {
      type = type.toBaseType(appView.dexItemFactory());
    }
    if (!type.isClassType()) {
      return;
    }
    // Lookup the definition, ignoring the result. This populates the missing and referenced sets.
    definitionFor(type);
  }

  private void recordMethodReference(DexMethod method) {
    recordTypeReference(method.holder);
    recordTypeReference(method.proto.returnType);
    for (DexType type : method.proto.parameters.values) {
      recordTypeReference(type);
    }
  }

  private void recordFieldReference(DexField field) {
    recordTypeReference(field.holder);
    recordTypeReference(field.type);
  }

  private DexClass definitionFor(DexType type) {
    DexClass clazz = appView.definitionFor(type);
    if (clazz == null) {
      reportMissingClass(type);
      return null;
    }
    if (clazz.isNotProgramClass()) {
      addLiveNonProgramType(clazz);
    }
    return clazz;
  }

  private void addLiveNonProgramType(DexClass clazz) {
    assert clazz.isNotProgramClass();
    // Fast path to avoid the worklist when the class is already seen.
    if (!liveNonProgramTypes.add(clazz)) {
      return;
    }
    Deque<DexClass> worklist = new ArrayDeque<>();
    worklist.addLast(clazz);
    while (!worklist.isEmpty()) {
      DexClass definition = worklist.removeFirst();
      processNewLiveNonProgramType(definition, worklist);
    }
  }

  private void processNewLiveNonProgramType(DexClass clazz, Deque<DexClass> worklist) {
    assert clazz.isNotProgramClass();
    if (clazz.isLibraryClass()) {
      // TODO(b/149201735): This likely needs to apply to classpath too.
      ensureMethodsContinueToWidenAccess(clazz);
      // Only libraries must not derive program. Classpath classes can, assuming correct keep rules.
      warnIfLibraryTypeInheritsFromProgramType(clazz.asLibraryClass());
    }
    for (DexEncodedField field : clazz.fields()) {
      addNonProgramClassToWorklist(field.field.type, worklist);
    }
    for (DexEncodedMethod method : clazz.methods()) {
      addNonProgramClassToWorklist(method.method.proto.returnType, worklist);
      for (DexType param : method.method.proto.parameters.values) {
        addNonProgramClassToWorklist(param, worklist);
      }
    }
    for (DexType supertype : clazz.allImmediateSupertypes()) {
      addNonProgramClassToWorklist(supertype, worklist);
    }
  }

  private void addNonProgramClassToWorklist(DexType type, Deque<DexClass> worklist) {
    if (type.isArrayType()) {
      type = type.toBaseType(appView.dexItemFactory());
    }
    if (!type.isClassType()) {
      return;
    }
    DexClass definition = appView.definitionFor(type);
    if (definition == null) {
      reportMissingClass(type);
      return;
    }
    if (definition.isProgramClass() || !liveNonProgramTypes.add(definition)) {
      return;
    }
    worklist.addLast(definition);
  }

  private DexProgramClass getProgramClassOrNull(DexType type) {
    DexClass clazz = definitionFor(type);
    return clazz != null && clazz.isProgramClass() ? clazz.asProgramClass() : null;
  }

  private void warnIfLibraryTypeInheritsFromProgramType(DexLibraryClass clazz) {
    if (clazz.superType != null) {
      ensureFromLibraryOrThrow(clazz.superType, clazz);
    }
    for (DexType iface : clazz.interfaces.values) {
      ensureFromLibraryOrThrow(iface, clazz);
    }
  }

  private static <T> SetWithReason<T> newSetWithoutReasonReporter() {
    return new SetWithReason<>((f, r) -> {});
  }

  private void enqueueRootItems(Map<DexReference, Set<ProguardKeepRuleBase>> items) {
    items.entrySet().forEach(this::enqueueRootItem);
  }

  private void enqueueRootItem(Entry<DexReference, Set<ProguardKeepRuleBase>> root) {
    DexDefinition item = appView.definitionFor(root.getKey());
    if (item != null) {
      enqueueRootItem(item, root.getValue());
    } else {
      // TODO(b/123923324): Verify that root items are present.
      // assert false : "Expected root item `" + root.getKey().toSourceString() + "` to be present";
    }
  }

  private void enqueueRootItem(DexDefinition item, Set<ProguardKeepRuleBase> rules) {
    internalEnqueueRootItem(item, rules, null);
  }

  private void internalEnqueueRootItem(
      DexDefinition item, Set<ProguardKeepRuleBase> rules, DexDefinition precondition) {
    if (item.isDexClass()) {
      DexProgramClass clazz = item.asDexClass().asProgramClass();
      KeepReasonWitness witness = graphReporter.reportKeepClass(precondition, rules, clazz);
      if (clazz.isAnnotation()) {
        workList.enqueueMarkAnnotationInstantiatedAction(clazz, witness);
      } else if (clazz.isInterface()) {
        workList.enqueueMarkInterfaceInstantiatedAction(clazz, witness);
      } else {
        workList.enqueueMarkInstantiatedAction(clazz, null, InstantiationReason.KEEP_RULE, witness);
        if (clazz.hasDefaultInitializer()) {
          DexEncodedMethod defaultInitializer = clazz.getDefaultInitializer();
          if (forceProguardCompatibility) {
            workList.enqueueMarkMethodKeptAction(
                clazz,
                defaultInitializer,
                graphReporter.reportCompatKeepDefaultInitializer(clazz, defaultInitializer));
          }
          if (clazz.isExternalizable(appView)) {
            enqueueMarkMethodLiveAction(clazz, defaultInitializer, witness);
          }
        }
      }
    } else if (item.isDexEncodedField()) {
      DexEncodedField dexEncodedField = item.asDexEncodedField();
      DexProgramClass holder = getProgramClassOrNull(dexEncodedField.holder());
      if (holder != null) {
        workList.enqueueMarkFieldKeptAction(
            holder,
            dexEncodedField,
            graphReporter.reportKeepField(precondition, rules, dexEncodedField));
      }
    } else if (item.isDexEncodedMethod()) {
      DexEncodedMethod encodedMethod = item.asDexEncodedMethod();
      DexProgramClass holder = getProgramClassOrNull(encodedMethod.holder());
      if (holder != null) {
        workList.enqueueMarkMethodKeptAction(
            holder,
            encodedMethod,
            graphReporter.reportKeepMethod(precondition, rules, encodedMethod));
      }
    } else {
      throw new IllegalArgumentException(item.toString());
    }
    pinnedItems.add(item.toReference());
  }

  private void enqueueFirstNonSerializableClassInitializer(
      DexProgramClass clazz, KeepReason reason) {
    assert clazz.isSerializable(appView);
    // Climb up the class hierarchy. Break out if the definition is not found, or hit the library
    // classes which are kept by definition, or encounter the first non-serializable class.
    while (clazz.isSerializable(appView)) {
      DexProgramClass superClass = getProgramClassOrNull(clazz.superType);
      if (superClass == null) {
        return;
      }
      clazz = superClass;
    }
    if (clazz.hasDefaultInitializer()) {
      enqueueMarkMethodLiveAction(clazz, clazz.getDefaultInitializer(), reason);
    }
  }

  // Utility to avoid adding to the worklist if already live.
  private boolean enqueueMarkMethodLiveAction(
      DexProgramClass clazz, DexEncodedMethod method, KeepReason reason) {
    assert method.holder() == clazz.type;
    if (liveMethods.add(clazz, method, reason)) {
      workList.enqueueMarkMethodLiveAction(clazz, method, reason);
      return true;
    }
    return false;
  }

  private void compatEnqueueHolderIfDependentNonStaticMember(
      DexClass holder, Set<ProguardKeepRuleBase> compatRules) {
    if (!forceProguardCompatibility || compatRules == null) {
      return;
    }
    enqueueRootItem(holder, compatRules);
  }

  //
  // Things to do with registering events. This is essentially the interface for byte-code
  // traversals.
  //

  private boolean registerMethodWithTargetAndContext(
      Map<DexMethod, Set<DexEncodedMethod>> seen, DexMethod method, DexEncodedMethod context) {
    DexType baseHolder = method.holder.toBaseType(appView.dexItemFactory());
    if (baseHolder.isClassType()) {
      markTypeAsLive(baseHolder, clazz -> graphReporter.reportClassReferencedFrom(clazz, context));
      return seen.computeIfAbsent(method, ignore -> Sets.newIdentityHashSet()).add(context);
    }
    return false;
  }

  public boolean registerFieldRead(DexField field, DexEncodedMethod context) {
    return registerFieldAccess(field, context, true, false);
  }

  public boolean registerReflectiveFieldRead(DexField field, DexEncodedMethod context) {
    return registerFieldAccess(field, context, true, true);
  }

  public boolean registerFieldWrite(DexField field, DexEncodedMethod context) {
    return registerFieldAccess(field, context, false, false);
  }

  public boolean registerReflectiveFieldWrite(DexField field, DexEncodedMethod context) {
    return registerFieldAccess(field, context, false, true);
  }

  public boolean registerReflectiveFieldAccess(DexField field, DexEncodedMethod context) {
    boolean changed = registerFieldAccess(field, context, true, true);
    changed |= registerFieldAccess(field, context, false, true);
    return changed;
  }

  private boolean registerFieldAccess(
      DexField field, DexEncodedMethod context, boolean isRead, boolean isReflective) {
    FieldAccessInfoImpl info = fieldAccessInfoCollection.get(field);
    if (info == null) {
      DexEncodedField encodedField = resolveField(field);

      // If the field does not exist, then record this in the mapping, such that we don't have to
      // resolve the field the next time.
      if (encodedField == null) {
        fieldAccessInfoCollection.extend(field, MISSING_FIELD_ACCESS_INFO);
        return true;
      }

      // Check if we have previously created a FieldAccessInfo object for the field definition.
      info = fieldAccessInfoCollection.get(encodedField.field);

      // If not, we must create one.
      if (info == null) {
        info = new FieldAccessInfoImpl(encodedField.field);
        fieldAccessInfoCollection.extend(encodedField.field, info);
      }

      // If `field` is an indirect reference, then create a mapping for it, such that we don't have
      // to resolve the field the next time we see the reference.
      if (field != encodedField.field) {
        fieldAccessInfoCollection.extend(field, info);
      }
    } else if (info == MISSING_FIELD_ACCESS_INFO) {
      return false;
    }
    if (isReflective) {
      info.setHasReflectiveAccess();
    }
    return isRead ? info.recordRead(field, context) : info.recordWrite(field, context);
  }

  private boolean isStringConcat(DexMethodHandle bootstrapMethod) {
    return bootstrapMethod.type.isInvokeStatic()
        && (bootstrapMethod.asMethod() == appView.dexItemFactory().stringConcatWithConstantsMethod
            || bootstrapMethod.asMethod() == appView.dexItemFactory().stringConcatMethod);
  }

  void traceCallSite(DexCallSite callSite, ProgramMethod context) {
    DexProgramClass bootstrapClass =
        getProgramClassOrNull(callSite.bootstrapMethod.asMethod().holder);
    if (bootstrapClass != null) {
      bootstrapMethods.add(callSite.bootstrapMethod.asMethod());
    }

    DexProgramClass contextHolder = context.getHolder();
    LambdaDescriptor descriptor = LambdaDescriptor.tryInfer(callSite, appInfo, contextHolder);
    if (descriptor == null) {
      return;
    }

    DexEncodedMethod contextMethod = context.getMethod();
    if (lambdaRewriter != null) {
      assert contextMethod.getCode().isCfCode() : "Unexpected input type with lambdas";
      CfCode code = contextMethod.getCode().asCfCode();
      if (code != null) {
        LambdaClass lambdaClass =
            lambdaRewriter.getOrCreateLambdaClass(descriptor, contextMethod.holder());
        lambdaClasses.put(lambdaClass.type, new Pair<>(lambdaClass, contextMethod));
        lambdaCallSites
            .computeIfAbsent(contextMethod, k -> new IdentityHashMap<>())
            .put(callSite, lambdaClass);
        if (lambdaClass.descriptor.interfaces.contains(appView.dexItemFactory().serializableType)) {
          classesWithSerializableLambdas.add(contextHolder);
        }
      }
      if (descriptor.delegatesToLambdaImplMethod()) {
        desugaredLambdaImplementationMethods.add(descriptor.implHandle.asMethod());
      }
    } else {
      markLambdaAsInstantiated(descriptor, contextMethod);
      transitionMethodsForInstantiatedLambda(descriptor);
      callSites.add(callSite);
    }

    // For call sites representing a lambda, we link the targeted method
    // or field as if it were referenced from the current method.

    DexMethodHandle implHandle = descriptor.implHandle;
    assert implHandle != null;

    DexMethod method = implHandle.asMethod();
    if (!methodsTargetedByInvokeDynamic.add(method)) {
      return;
    }

    switch (implHandle.type) {
      case INVOKE_STATIC:
        traceInvokeStaticFromLambda(method, context);
        break;
      case INVOKE_INTERFACE:
        traceInvokeInterfaceFromLambda(method, context);
        break;
      case INVOKE_INSTANCE:
        traceInvokeVirtualFromLambda(method, context);
        break;
      case INVOKE_DIRECT:
        traceInvokeDirectFromLambda(method, context);
        break;
      case INVOKE_CONSTRUCTOR:
        traceNewInstanceFromLambda(method.holder, context);
        break;
      default:
        throw new Unreachable();
    }
  }

  boolean traceCheckCast(DexType type, DexEncodedMethod currentMethod) {
    return traceConstClassOrCheckCast(type, currentMethod);
  }

  boolean traceConstClass(DexType type, DexEncodedMethod currentMethod) {
    // We conservatively group T.class and T[].class to ensure that we do not merge T with S if
    // potential locks on T[].class and S[].class exists.
    DexType baseType = type.toBaseType(appView.dexItemFactory());
    if (baseType.isClassType()) {
      DexProgramClass baseClass = getProgramClassOrNull(baseType);
      if (baseClass != null) {
        constClassReferences.add(baseType);
      }
    }
    return traceConstClassOrCheckCast(type, currentMethod);
  }

  private boolean traceConstClassOrCheckCast(DexType type, DexEncodedMethod currentMethod) {
    if (!forceProguardCompatibility) {
      return traceTypeReference(type, currentMethod);
    }
    DexType baseType = type.toBaseType(appView.dexItemFactory());
    if (baseType.isClassType()) {
      DexProgramClass baseClass = getProgramClassOrNull(baseType);
      if (baseClass != null) {
        // Don't require any constructor, see b/112386012.
        markClassAsInstantiatedWithCompatRule(
            baseClass, graphReporter.reportCompatInstantiated(baseClass, currentMethod));
      }
      return true;
    }
    return false;
  }

  boolean traceInitClass(DexType type, ProgramMethod currentMethod) {
    assert type.isClassType();

    Visibility oldMinimumRequiredVisibility = initClassReferences.get(type);
    if (oldMinimumRequiredVisibility == null) {
      DexProgramClass clazz = getProgramClassOrNull(type);
      if (clazz == null) {
        assert false;
        return false;
      }

      initClassReferences.put(
          type, computeMinimumRequiredVisibilityForInitClassField(type, currentMethod.getHolder()));

      markTypeAsLive(type, classReferencedFromReporter(currentMethod.getMethod()));
      markDirectAndIndirectClassInitializersAsLive(clazz);
      return true;
    }

    if (oldMinimumRequiredVisibility.isPublic()) {
      return false;
    }

    Visibility minimumRequiredVisibilityForCurrentMethod =
        computeMinimumRequiredVisibilityForInitClassField(type, currentMethod.getHolder());

    // There should never be a need to have an InitClass instruction for the enclosing class.
    assert !minimumRequiredVisibilityForCurrentMethod.isPrivate();

    if (minimumRequiredVisibilityForCurrentMethod.isPublic()) {
      initClassReferences.put(type, minimumRequiredVisibilityForCurrentMethod);
      return true;
    }

    if (oldMinimumRequiredVisibility.isProtected()) {
      return false;
    }

    if (minimumRequiredVisibilityForCurrentMethod.isProtected()) {
      initClassReferences.put(type, minimumRequiredVisibilityForCurrentMethod);
      return true;
    }

    assert oldMinimumRequiredVisibility.isPackagePrivate();
    assert minimumRequiredVisibilityForCurrentMethod.isPackagePrivate();
    return false;
  }

  private Visibility computeMinimumRequiredVisibilityForInitClassField(
      DexType clazz, DexProgramClass context) {
    if (clazz.isSamePackage(context.type)) {
      return Visibility.PACKAGE_PRIVATE;
    }
    if (appInfo.isStrictSubtypeOf(context.type, clazz)) {
      return Visibility.PROTECTED;
    }
    return Visibility.PUBLIC;
  }

  void traceMethodHandle(
      DexMethodHandle methodHandle, MethodHandleUse use, DexEncodedMethod currentMethod) {
    // If a method handle is not an argument to a lambda metafactory it could flow to a
    // MethodHandle.invokeExact invocation. For that to work, the receiver type cannot have
    // changed and therefore we cannot perform member rebinding. For these handles, we maintain
    // the receiver for the method handle. Therefore, we have to make sure that the receiver
    // stays in the output (and is not class merged). To ensure that we treat the receiver
    // as instantiated.
    if (methodHandle.isMethodHandle() && use != MethodHandleUse.ARGUMENT_TO_LAMBDA_METAFACTORY) {
      DexType type = methodHandle.asMethod().holder;
      DexProgramClass clazz = getProgramClassOrNull(type);
      if (clazz != null) {
        KeepReason reason = KeepReason.methodHandleReferencedIn(currentMethod);
        if (clazz.isAnnotation()) {
          markTypeAsLive(clazz, graphReporter.registerClass(clazz, reason));
        } else if (clazz.isInterface()) {
          markInterfaceAsInstantiated(clazz, graphReporter.registerInterface(clazz, reason));
        } else {
          workList.enqueueMarkInstantiatedAction(
              clazz, null, InstantiationReason.REFERENCED_IN_METHOD_HANDLE, reason);
        }
      }
    }
  }

  boolean traceTypeReference(DexType type, DexEncodedMethod currentMethod) {
    markTypeAsLive(type, classReferencedFromReporter(currentMethod));
    return true;
  }

  boolean traceInvokeDirect(DexMethod invokedMethod, ProgramMethod context) {
    DexProgramClass currentHolder = context.getHolder();
    DexEncodedMethod currentMethod = context.getMethod();
    boolean skipTracing =
        registerDeferredActionForDeadProtoBuilder(
            invokedMethod.holder,
            currentMethod,
            () ->
                workList.enqueueTraceInvokeDirectAction(
                    invokedMethod, currentHolder, currentMethod));
    if (skipTracing) {
      addDeadProtoTypeCandidate(invokedMethod.holder);
      return false;
    }

    return traceInvokeDirect(
        invokedMethod, context, KeepReason.invokedFrom(currentHolder, currentMethod));
  }

  /** Returns true if a deferred action was registered. */
  private boolean registerDeferredActionForDeadProtoBuilder(
      DexType type, DexEncodedMethod currentMethod, Action action) {
    DexProgramClass clazz = getProgramClassOrNull(type);
    if (clazz != null) {
      return appView.withGeneratedMessageLiteBuilderShrinker(
          shrinker ->
              shrinker.deferDeadProtoBuilders(
                  clazz, currentMethod, () -> liveTypes.registerDeferredAction(clazz, action)),
          false);
    }
    return false;
  }

  boolean traceInvokeDirectFromLambda(DexMethod invokedMethod, ProgramMethod context) {
    return traceInvokeDirect(
        invokedMethod, context, KeepReason.invokedFromLambdaCreatedIn(context.getMethod()));
  }

  private boolean traceInvokeDirect(
      DexMethod invokedMethod, ProgramMethod context, KeepReason reason) {
    DexEncodedMethod currentMethod = context.getMethod();
    if (!registerMethodWithTargetAndContext(directInvokes, invokedMethod, currentMethod)) {
      return false;
    }
    if (Log.ENABLED) {
      Log.verbose(getClass(), "Register invokeDirect `%s`.", invokedMethod);
    }
    handleInvokeOfDirectTarget(invokedMethod, reason);
    invokeAnalyses.forEach(analysis -> analysis.traceInvokeDirect(invokedMethod, context));
    return true;
  }

  boolean traceInvokeInterface(DexMethod invokedMethod, ProgramMethod context) {
    return traceInvokeInterface(invokedMethod, context, KeepReason.invokedFrom(context));
  }

  boolean traceInvokeInterfaceFromLambda(DexMethod invokedMethod, ProgramMethod context) {
    return traceInvokeInterface(
        invokedMethod, context, KeepReason.invokedFromLambdaCreatedIn(context.getMethod()));
  }

  private boolean traceInvokeInterface(
      DexMethod method, ProgramMethod context, KeepReason keepReason) {
    DexEncodedMethod currentMethod = context.getMethod();
    if (!registerMethodWithTargetAndContext(interfaceInvokes, method, currentMethod)) {
      return false;
    }
    if (Log.ENABLED) {
      Log.verbose(getClass(), "Register invokeInterface `%s`.", method);
    }
    markVirtualMethodAsReachable(method, true, context, keepReason);
    invokeAnalyses.forEach(analysis -> analysis.traceInvokeInterface(method, context));
    return true;
  }

  boolean traceInvokeStatic(DexMethod invokedMethod, ProgramMethod context) {
    return traceInvokeStatic(invokedMethod, context, KeepReason.invokedFrom(context));
  }

  boolean traceInvokeStaticFromLambda(DexMethod invokedMethod, ProgramMethod context) {
    return traceInvokeStatic(
        invokedMethod, context, KeepReason.invokedFromLambdaCreatedIn(context.getMethod()));
  }

  private boolean traceInvokeStatic(
      DexMethod invokedMethod, ProgramMethod context, KeepReason reason) {
    DexEncodedMethod currentMethod = context.getMethod();
    DexItemFactory dexItemFactory = appView.dexItemFactory();
    if (dexItemFactory.classMethods.isReflectiveClassLookup(invokedMethod)
        || dexItemFactory.atomicFieldUpdaterMethods.isFieldUpdater(invokedMethod)) {
      // Implicitly add -identifiernamestring rule for the Java reflection in use.
      identifierNameStrings.add(invokedMethod);
      // Revisit the current method to implicitly add -keep rule for items with reflective access.
      pendingReflectiveUses.add(currentMethod);
    }
    // See comment in handleJavaLangEnumValueOf.
    if (invokedMethod == dexItemFactory.enumMethods.valueOf) {
      pendingReflectiveUses.add(currentMethod);
    }
    // Handling of application services.
    if (dexItemFactory.serviceLoaderMethods.isLoadMethod(invokedMethod)) {
      pendingReflectiveUses.add(currentMethod);
    }
    if (invokedMethod == dexItemFactory.proxyMethods.newProxyInstance) {
      pendingReflectiveUses.add(currentMethod);
    }
    if (!registerMethodWithTargetAndContext(staticInvokes, invokedMethod, currentMethod)) {
      return false;
    }
    if (Log.ENABLED) {
      Log.verbose(getClass(), "Register invokeStatic `%s`.", invokedMethod);
    }
    handleInvokeOfStaticTarget(invokedMethod, reason);
    invokeAnalyses.forEach(analysis -> analysis.traceInvokeStatic(invokedMethod, context));
    return true;
  }

  boolean traceInvokeSuper(DexMethod invokedMethod, ProgramMethod context) {
    DexEncodedMethod currentMethod = context.getMethod();
    // We have to revisit super invokes based on the context they are found in. The same
    // method descriptor will hit different targets, depending on the context it is used in.
    DexMethod actualTarget = getInvokeSuperTarget(invokedMethod, currentMethod);
    if (!registerMethodWithTargetAndContext(superInvokes, invokedMethod, currentMethod)) {
      return false;
    }
    if (Log.ENABLED) {
      Log.verbose(getClass(), "Register invokeSuper `%s`.", actualTarget);
    }
    workList.enqueueMarkReachableSuperAction(invokedMethod, currentMethod);
    invokeAnalyses.forEach(analysis -> analysis.traceInvokeSuper(invokedMethod, context));
    return true;
  }

  boolean traceInvokeVirtual(DexMethod invokedMethod, ProgramMethod context) {
    return traceInvokeVirtual(invokedMethod, context, KeepReason.invokedFrom(context));
  }

  boolean traceInvokeVirtualFromLambda(DexMethod invokedMethod, ProgramMethod context) {
    return traceInvokeVirtual(
        invokedMethod, context, KeepReason.invokedFromLambdaCreatedIn(context.getMethod()));
  }

  private boolean traceInvokeVirtual(
      DexMethod invokedMethod, ProgramMethod context, KeepReason reason) {
    if (invokedMethod == appView.dexItemFactory().classMethods.newInstance
        || invokedMethod == appView.dexItemFactory().constructorMethods.newInstance) {
      pendingReflectiveUses.add(context.getMethod());
    } else if (appView.dexItemFactory().classMethods.isReflectiveMemberLookup(invokedMethod)) {
      // Implicitly add -identifiernamestring rule for the Java reflection in use.
      identifierNameStrings.add(invokedMethod);
      // Revisit the current method to implicitly add -keep rule for items with reflective access.
      pendingReflectiveUses.add(context.getMethod());
    }
    if (!registerMethodWithTargetAndContext(virtualInvokes, invokedMethod, context.getMethod())) {
      return false;
    }
    if (Log.ENABLED) {
      Log.verbose(getClass(), "Register invokeVirtual `%s`.", invokedMethod);
    }
    markVirtualMethodAsReachable(invokedMethod, false, context, reason);
    invokeAnalyses.forEach(analysis -> analysis.traceInvokeVirtual(invokedMethod, context));
    return true;
  }

  boolean traceNewInstance(DexType type, ProgramMethod context) {
    DexEncodedMethod currentMethod = context.getMethod();
    boolean skipTracing =
        registerDeferredActionForDeadProtoBuilder(
            type, currentMethod, () -> workList.enqueueTraceNewInstanceAction(type, context));
    if (skipTracing) {
      addDeadProtoTypeCandidate(type);
      return false;
    }

    return traceNewInstance(
        type,
        context,
        InstantiationReason.NEW_INSTANCE_INSTRUCTION,
        KeepReason.instantiatedIn(currentMethod));
  }

  boolean traceNewInstanceFromLambda(DexType type, ProgramMethod context) {
    return traceNewInstance(
        type,
        context,
        InstantiationReason.LAMBDA,
        KeepReason.invokedFromLambdaCreatedIn(context.getMethod()));
  }

  private boolean traceNewInstance(
      DexType type,
      ProgramMethod context,
      InstantiationReason instantiationReason,
      KeepReason keepReason) {
    DexEncodedMethod currentMethod = context.getMethod();
    DexProgramClass clazz = getProgramClassOrNull(type);
    if (clazz != null) {
      if (clazz.isAnnotation() || clazz.isInterface()) {
        markTypeAsLive(clazz, graphReporter.registerClass(clazz, keepReason));
      } else {
        workList.enqueueMarkInstantiatedAction(
            clazz, currentMethod, instantiationReason, keepReason);
      }
    }
    return true;
  }

  boolean traceInstanceFieldRead(DexField field, DexEncodedMethod currentMethod) {
    return traceInstanceFieldRead(field, currentMethod, false);
  }

  boolean traceInstanceFieldReadFromMethodHandle(DexField field, DexEncodedMethod currentMethod) {
    return traceInstanceFieldRead(field, currentMethod, true);
  }

  private boolean traceInstanceFieldRead(
      DexField field, DexEncodedMethod currentMethod, boolean fromMethodHandle) {
    if (!registerFieldRead(field, currentMethod)) {
      return false;
    }

    // Must mark the field as targeted even if it does not exist.
    markFieldAsTargeted(field, currentMethod);

    DexEncodedField encodedField = resolveField(field);
    if (encodedField == null) {
      return false;
    }

    if (fromMethodHandle) {
      fieldAccessInfoCollection.get(encodedField.field).setReadFromMethodHandle();
    }

    DexProgramClass clazz = getProgramClassOrNull(encodedField.holder());
    if (clazz == null) {
      return false;
    }

    if (Log.ENABLED) {
      Log.verbose(getClass(), "Register Iget `%s`.", field);
    }

    // If unused interface removal is enabled, then we won't necessarily mark the actual holder of
    // the field as live, if the holder is an interface.
    if (appView.options().enableUnusedInterfaceRemoval) {
      if (encodedField.field != field) {
        markTypeAsLive(clazz, graphReporter.reportClassReferencedFrom(clazz, currentMethod));
        markTypeAsLive(encodedField.field.type, classReferencedFromReporter(currentMethod));
      }
    }

    workList.enqueueMarkReachableFieldAction(
        clazz, encodedField, KeepReason.fieldReferencedIn(currentMethod));
    return true;
  }

  boolean traceInstanceFieldWrite(DexField field, DexEncodedMethod currentMethod) {
    return traceInstanceFieldWrite(field, currentMethod, false);
  }

  boolean traceInstanceFieldWriteFromMethodHandle(DexField field, DexEncodedMethod currentMethod) {
    return traceInstanceFieldWrite(field, currentMethod, true);
  }

  private boolean traceInstanceFieldWrite(
      DexField field, DexEncodedMethod currentMethod, boolean fromMethodHandle) {
    if (!registerFieldWrite(field, currentMethod)) {
      return false;
    }

    // Must mark the field as targeted even if it does not exist.
    markFieldAsTargeted(field, currentMethod);

    DexEncodedField encodedField = resolveField(field);
    if (encodedField == null) {
      return false;
    }

    if (fromMethodHandle) {
      fieldAccessInfoCollection.get(encodedField.field).setWrittenFromMethodHandle();
    }

    DexProgramClass clazz = getProgramClassOrNull(encodedField.holder());
    if (clazz == null) {
      return false;
    }

    if (Log.ENABLED) {
      Log.verbose(getClass(), "Register Iput `%s`.", field);
    }

    // If unused interface removal is enabled, then we won't necessarily mark the actual holder of
    // the field as live, if the holder is an interface.
    if (appView.options().enableUnusedInterfaceRemoval) {
      if (encodedField.field != field) {
        markTypeAsLive(clazz, graphReporter.reportClassReferencedFrom(clazz, currentMethod));
        markTypeAsLive(encodedField.field.type, classReferencedFromReporter(currentMethod));
      }
    }

    KeepReason reason = KeepReason.fieldReferencedIn(currentMethod);
    workList.enqueueMarkReachableFieldAction(clazz, encodedField, reason);
    return true;
  }

  boolean traceStaticFieldRead(DexField field, DexEncodedMethod currentMethod) {
    return traceStaticFieldRead(field, currentMethod, false);
  }

  boolean traceStaticFieldReadFromMethodHandle(DexField field, DexEncodedMethod currentMethod) {
    return traceStaticFieldRead(field, currentMethod, true);
  }

  private boolean traceStaticFieldRead(
      DexField field, DexEncodedMethod currentMethod, boolean fromMethodHandle) {
    if (!registerFieldRead(field, currentMethod)) {
      return false;
    }

    DexEncodedField encodedField = resolveField(field);
    if (encodedField == null) {
      // Must mark the field as targeted even if it does not exist.
      markFieldAsTargeted(field, currentMethod);
      return false;
    }

    if (fromMethodHandle) {
      fieldAccessInfoCollection.get(encodedField.field).setReadFromMethodHandle();
    }

    DexProgramClass holder = getProgramClassOrNull(encodedField.holder());
    if (holder == null) {
      // No need to trace into the non-program code.
      return false;
    }

    if (Log.ENABLED) {
      Log.verbose(getClass(), "Register Sget `%s`.", field);
    }

    if (appView.options().protoShrinking().enableGeneratedExtensionRegistryShrinking) {
      // If it is a dead proto extension field, don't trace onwards.
      boolean skipTracing =
          appView.withGeneratedExtensionRegistryShrinker(
              shrinker ->
                  shrinker.isDeadProtoExtensionField(
                      encodedField, fieldAccessInfoCollection, pinnedItems),
              false);
      if (skipTracing) {
        addDeadProtoTypeCandidate(holder);
        return false;
      }
    }

    if (encodedField.field != field) {
      // Mark the non-rebound field access as targeted. Note that this should only be done if the
      // field is not a dead proto field (in which case we bail-out above).
      markFieldAsTargeted(field, currentMethod);
    }

    markStaticFieldAsLive(encodedField, KeepReason.fieldReferencedIn(currentMethod));
    return true;
  }

  boolean traceStaticFieldWrite(DexField field, DexEncodedMethod currentMethod) {
    return traceStaticFieldWrite(field, currentMethod, false);
  }

  boolean traceStaticFieldWriteFromMethodHandle(DexField field, DexEncodedMethod currentMethod) {
    return traceStaticFieldWrite(field, currentMethod, true);
  }

  private boolean traceStaticFieldWrite(
      DexField field, DexEncodedMethod currentMethod, boolean fromMethodHandle) {
    if (!registerFieldWrite(field, currentMethod)) {
      return false;
    }

    DexEncodedField encodedField = resolveField(field);
    if (encodedField == null) {
      // Must mark the field as targeted even if it does not exist.
      markFieldAsTargeted(field, currentMethod);
      return false;
    }

    if (fromMethodHandle) {
      fieldAccessInfoCollection.get(encodedField.field).setWrittenFromMethodHandle();
    }

    DexProgramClass holder = getProgramClassOrNull(encodedField.holder());
    if (holder == null) {
      // No need to trace into the non-program code.
      return false;
    }

    if (Log.ENABLED) {
      Log.verbose(getClass(), "Register Sput `%s`.", field);
    }

    if (appView.options().protoShrinking().enableGeneratedExtensionRegistryShrinking) {
      // If it is a dead proto extension field, don't trace onwards.
      boolean skipTracing =
          appView.withGeneratedExtensionRegistryShrinker(
              shrinker ->
                  shrinker.isDeadProtoExtensionField(
                      encodedField, fieldAccessInfoCollection, pinnedItems),
              false);
      if (skipTracing) {
        addDeadProtoTypeCandidate(holder);
        return false;
      }
    }

    if (encodedField.field != field) {
      // Mark the non-rebound field access as targeted. Note that this should only be done if the
      // field is not a dead proto field (in which case we bail-out above).
      markFieldAsTargeted(field, currentMethod);
    }

    markStaticFieldAsLive(encodedField, KeepReason.fieldReferencedIn(currentMethod));
    return true;
  }

  private Function<DexProgramClass, KeepReasonWitness> classReferencedFromReporter(
      DexEncodedMethod currentMethod) {
    return clazz -> graphReporter.reportClassReferencedFrom(clazz, currentMethod);
  }

  private DexMethod getInvokeSuperTarget(DexMethod method, DexEncodedMethod currentMethod) {
    DexClass methodHolderClass = appView.definitionFor(method.holder);
    if (methodHolderClass != null && methodHolderClass.isInterface()) {
      return method;
    }
    DexClass holderClass = appView.definitionFor(currentMethod.holder());
    if (holderClass == null || holderClass.superType == null || holderClass.isInterface()) {
      // We do not know better or this call is made from an interface.
      return method;
    }
    // Return the invoked method on the supertype.
    return appView.dexItemFactory().createMethod(holderClass.superType, method.proto, method.name);
  }

  //
  // Actual actions performed.
  //

  private boolean verifyMethodIsTargeted(DexEncodedMethod method) {
    assert !method.isClassInitializer() : "Class initializers are never targeted";
    assert targetedMethods.contains(method);
    return true;
  }

  private boolean verifyTypeIsLive(DexProgramClass clazz) {
    assert liveTypes.contains(clazz);
    return true;
  }

  private void markTypeAsLive(DexType type, KeepReason reason) {
    if (type.isArrayType()) {
      markTypeAsLive(type.toBaseType(appView.dexItemFactory()), reason);
      return;
    }
    if (!type.isClassType()) {
      // Ignore primitive types.
      return;
    }
    DexProgramClass holder = getProgramClassOrNull(type);
    if (holder == null) {
      return;
    }
    markTypeAsLive(
        holder,
        scopedMethodsForLiveTypes.computeIfAbsent(type, ignore -> new ScopedDexMethodSet()),
        graphReporter.registerClass(holder, reason));
  }

  private void markTypeAsLive(DexType type, Function<DexProgramClass, KeepReasonWitness> reason) {
    if (type.isArrayType()) {
      markTypeAsLive(type.toBaseType(appView.dexItemFactory()), reason);
      return;
    }
    if (!type.isClassType()) {
      // Ignore primitive types.
      return;
    }
    DexProgramClass holder = getProgramClassOrNull(type);
    if (holder == null) {
      return;
    }
    markTypeAsLive(
        holder,
        scopedMethodsForLiveTypes.computeIfAbsent(type, ignore -> new ScopedDexMethodSet()),
        reason.apply(holder));
  }

  void markTypeAsLive(DexProgramClass clazz, KeepReasonWitness witness) {
    markTypeAsLive(
        clazz,
        scopedMethodsForLiveTypes.computeIfAbsent(clazz.type, ignore -> new ScopedDexMethodSet()),
        witness);
  }

  private void markTypeAsLive(
      DexProgramClass holder, ScopedDexMethodSet seen, KeepReasonWitness witness) {
    if (!liveTypes.add(holder, witness)) {
      return;
    }

    // Mark types in inner-class attributes referenced.
    for (InnerClassAttribute innerClassAttribute : holder.getInnerClasses()) {
      recordTypeReference(innerClassAttribute.getInner());
      recordTypeReference(innerClassAttribute.getOuter());
    }
    EnclosingMethodAttribute enclosingMethodAttribute = holder.getEnclosingMethod();
    if (enclosingMethodAttribute != null) {
      DexMethod enclosingMethod = enclosingMethodAttribute.getEnclosingMethod();
      if (enclosingMethod != null) {
        recordMethodReference(enclosingMethod);
      } else {
        recordTypeReference(enclosingMethodAttribute.getEnclosingClass());
      }
    }

    if (Log.ENABLED) {
      Log.verbose(getClass(), "Type `%s` has become live.", holder.type);
    }

    KeepReason reason = KeepReason.reachableFromLiveType(holder.type);

    for (DexType iface : holder.interfaces.values) {
      markInterfaceTypeAsLiveViaInheritanceClause(iface, holder);
    }

    if (holder.superType != null) {
      ScopedDexMethodSet seenForSuper =
          scopedMethodsForLiveTypes.computeIfAbsent(
              holder.superType, ignore -> new ScopedDexMethodSet());
      seen.setParent(seenForSuper);
      markTypeAsLive(holder.superType, reason);
    }

    // If this is an interface that has just become live, then report previously seen but unreported
    // implemented-by edges.
    transitionUnusedInterfaceToLive(holder);

    // We cannot remove virtual methods defined earlier in the type hierarchy if it is widening
    // access and is defined in an interface:
    //
    // public interface I {
    //   void clone();
    // }
    //
    // class Model implements I {
    //   public void clone() { ... } <-- this cannot be removed
    // }
    //
    // Any class loading of Model with Model.clone() removed will result in an illegal access
    // error because their exists an existing implementation (here it is Object.clone()). This is
    // only a problem in the DEX VM. We have to make this check no matter the output because
    // CF libraries can be used by Android apps. See b/136698023 for more information.
    ensureMethodsContinueToWidenAccess(holder, seen, reason);

    if (holder.isSerializable(appView)) {
      enqueueFirstNonSerializableClassInitializer(holder, reason);
    }

    processAnnotations(holder, holder);

    // If this type has deferred annotations, we have to process those now, too.
    if (holder.isAnnotation()) {
      Set<DexAnnotation> annotations = deferredAnnotations.remove(holder.type);
      if (annotations != null && !annotations.isEmpty()) {
        assert annotations.stream().allMatch(a -> a.annotation.type == holder.type);
        annotations.forEach(annotation -> processAnnotation(holder, holder, annotation));
      }
    }

    rootSet.forEachDependentInstanceConstructor(
        holder, appView, this::enqueueHolderWithDependentInstanceConstructor);
    rootSet.forEachDependentStaticMember(holder, appView, this::enqueueDependentItem);
    compatEnqueueHolderIfDependentNonStaticMember(
        holder, rootSet.getDependentKeepClassCompatRule(holder.getType()));

    analyses.forEach(analysis -> analysis.processNewlyLiveClass(holder, workList));
  }

  private void ensureMethodsContinueToWidenAccess(DexClass clazz) {
    assert !clazz.isProgramClass();
    ScopedDexMethodSet seen =
        scopedMethodsForLiveTypes.computeIfAbsent(clazz.type, ignore -> new ScopedDexMethodSet());
    clazz.virtualMethods().forEach(seen::addMethodIfMoreVisible);
  }

  private void ensureMethodsContinueToWidenAccess(
      DexProgramClass clazz, ScopedDexMethodSet seen, KeepReason reason) {
    for (DexEncodedMethod method : clazz.virtualMethods()) {
      if (seen.addMethodIfMoreVisible(method) == AddMethodIfMoreVisibleResult.ADDED_MORE_VISIBLE
          && clazz.isProgramClass()
          && appView.appInfo().methodDefinedInInterfaces(method, clazz.type)) {
        markMethodAsTargeted(clazz, method, reason);
      }
    }
  }

  private void markInterfaceTypeAsLiveViaInheritanceClause(
      DexType type, DexProgramClass implementer) {
    DexProgramClass clazz = getProgramClassOrNull(type);
    if (clazz == null) {
      return;
    }

    if (!appView.options().enableUnusedInterfaceRemoval || mode.isTracingMainDex()) {
      markTypeAsLive(clazz, graphReporter.reportClassReferencedFrom(clazz, implementer));
    } else {
      if (liveTypes.contains(clazz)) {
        // The interface is already live, so make sure to report this implements-edge.
        graphReporter.reportClassReferencedFrom(clazz, implementer);
      } else {
        // No need to mark the type as live. If an interface type is only reachable via the
        // inheritance clause of another type it can simply be removed from the inheritance clause.
        // The interface is needed if it has a live default interface method or field, though.
        // Therefore, we record that this implemented-by edge has not been reported, such that we
        // can report it in the future if one its members becomes live.
        WorkList<DexProgramClass> worklist = WorkList.newIdentityWorkList();
        worklist.addIfNotSeen(clazz);
        while (worklist.hasNext()) {
          DexProgramClass current = worklist.next();
          if (liveTypes.contains(current)) {
            continue;
          }
          Set<DexProgramClass> implementors =
              unusedInterfaceTypes.computeIfAbsent(current, ignore -> Sets.newIdentityHashSet());
          if (implementors.add(implementer)) {
            for (DexType iface : current.interfaces.values) {
              DexProgramClass definition = getProgramClassOrNull(iface);
              if (definition != null) {
                worklist.addIfNotSeen(definition);
              }
            }
          }
        }
      }
    }
  }

  private void enqueueDependentItem(
      DexDefinition precondition, DexDefinition consequent, Set<ProguardKeepRuleBase> reasons) {
    internalEnqueueRootItem(consequent, reasons, precondition);
  }

  private void enqueueHolderWithDependentInstanceConstructor(
      DexProgramClass clazz,
      DexEncodedMethod instanceInitializer,
      Set<ProguardKeepRuleBase> reasons) {
    enqueueRootItem(clazz, reasons);
  }

  private void processAnnotations(DexProgramClass holder, DexDefinition annotatedItem) {
    processAnnotations(holder, annotatedItem, annotatedItem.annotations());
  }

  private void processAnnotations(
      DexProgramClass holder, DexDefinition annotatedItem, DexAnnotationSet annotations) {
    processAnnotations(holder, annotatedItem, annotations.annotations);
  }

  private void processAnnotations(
      DexProgramClass holder, DexDefinition annotatedItem, DexAnnotation[] annotations) {
    for (DexAnnotation annotation : annotations) {
      processAnnotation(holder, annotatedItem, annotation);
    }
  }

  private void processAnnotation(
      DexProgramClass holder, DexDefinition annotatedItem, DexAnnotation annotation) {
    assert annotatedItem == holder
        || annotatedItem.asDexEncodedMember().toReference().holder == holder.type;
    assert !holder.isDexClass() || holder.asDexClass().isProgramClass();
    DexType type = annotation.annotation.type;
    recordTypeReference(type);
    DexClass clazz = appView.definitionFor(type);
    boolean annotationTypeIsLibraryClass = clazz == null || clazz.isNotProgramClass();
    boolean isLive = annotationTypeIsLibraryClass || liveTypes.contains(clazz.asProgramClass());
    if (!shouldKeepAnnotation(appView, annotatedItem, annotation, isLive)) {
      // Remember this annotation for later.
      if (!annotationTypeIsLibraryClass) {
        deferredAnnotations.computeIfAbsent(type, ignore -> new HashSet<>()).add(annotation);
      }
      return;
    }
    KeepReason reason = KeepReason.annotatedOn(annotatedItem);
    graphReporter.registerAnnotation(annotation, reason);
    AnnotationReferenceMarker referenceMarker =
        new AnnotationReferenceMarker(annotation.annotation.type, appView.dexItemFactory(), reason);
    annotation.annotation.collectIndexedItems(referenceMarker);
  }

  private DexEncodedField resolveField(DexField field) {
    // Record the references in case they are not program types.
    recordTypeReference(field.holder);
    recordTypeReference(field.type);
    DexEncodedField encodedField = appInfo.resolveField(field);
    if (encodedField == null) {
      reportMissingField(field);
      return null;
    }
    return encodedField;
  }

  private SingleResolutionResult resolveMethod(DexMethod method, KeepReason reason) {
    // Record the references in case they are not program types.
    recordMethodReference(method);
    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
    if (resolutionResult.isFailedResolution()) {
      reportMissingMethod(method);
      markFailedResolutionTargets(method, resolutionResult.asFailedResolution(), reason);
    }
    return resolutionResult.asSingleResolution();
  }

  private SingleResolutionResult resolveMethod(
      DexMethod method, KeepReason reason, boolean interfaceInvoke) {
    // Record the references in case they are not program types.
    recordMethodReference(method);
    ResolutionResult resolutionResult =
        appInfo.resolveMethod(method.holder, method, interfaceInvoke);
    if (resolutionResult.isFailedResolution()) {
      reportMissingMethod(method);
      markFailedResolutionTargets(method, resolutionResult.asFailedResolution(), reason);
    }
    return resolutionResult.asSingleResolution();
  }

  private void handleInvokeOfStaticTarget(DexMethod method, KeepReason reason) {
    SingleResolutionResult resolution = resolveMethod(method, reason);
    if (resolution == null || resolution.getResolvedHolder().isNotProgramClass()) {
      return;
    }
    DexProgramClass clazz = resolution.getResolvedHolder().asProgramClass();
    DexEncodedMethod encodedMethod = resolution.getResolvedMethod();

    // We have to mark the resolved method as targeted even if it cannot actually be invoked
    // to make sure the invocation will keep failing in the appropriate way.
    markMethodAsTargeted(clazz, encodedMethod, reason);

    // Only mark methods for which invocation will succeed at runtime live.
    if (encodedMethod.isStatic()) {
      markDirectAndIndirectClassInitializersAsLive(clazz);
      markDirectStaticOrConstructorMethodAsLive(clazz, encodedMethod, reason);
    }
  }

  private void markDirectAndIndirectClassInitializersAsLive(DexProgramClass clazz) {
    Deque<DexProgramClass> worklist = DequeUtils.newArrayDeque(clazz);
    Set<DexProgramClass> visited = SetUtils.newIdentityHashSet(clazz);
    while (!worklist.isEmpty()) {
      DexProgramClass current = worklist.removeFirst();
      assert visited.contains(current);

      if (!markDirectClassInitializerAsLive(current)) {
        continue;
      }

      // Mark all class initializers in all super types as live.
      for (DexType superType : clazz.allImmediateSupertypes()) {
        DexProgramClass superClass = getProgramClassOrNull(superType);
        if (superClass != null && visited.add(superClass)) {
          worklist.add(superClass);
        }
      }
    }
  }

  /** Returns true if the class initializer became live for the first time. */
  private boolean markDirectClassInitializerAsLive(DexProgramClass clazz) {
    DexEncodedMethod clinit = clazz.getClassInitializer();
    KeepReasonWitness witness = graphReporter.reportReachableClassInitializer(clazz, clinit);
    if (!initializedTypes.add(clazz, witness)) {
      return false;
    }
    if (clinit != null && clinit.getOptimizationInfo().mayHaveSideEffects()) {
      markDirectStaticOrConstructorMethodAsLive(clazz, clinit, witness);
    }
    return true;
  }

  // Package protected due to entry point from worklist.
  void markNonStaticDirectMethodAsReachable(DexMethod method, KeepReason reason) {
    handleInvokeOfDirectTarget(method, reason);
  }

  private void handleInvokeOfDirectTarget(DexMethod method, KeepReason reason) {
    DexType holder = method.holder;
    DexProgramClass clazz = getProgramClassOrNull(holder);
    if (clazz == null) {
      recordMethodReference(method);
      return;
    }
    // TODO(zerny): Is it ok that we lookup in both the direct and virtual pool here?
    DexEncodedMethod encodedMethod = clazz.lookupMethod(method);
    if (encodedMethod == null) {
      reportMissingMethod(method);
      return;
    }

    // We have to mark the resolved method as targeted even if it cannot actually be invoked
    // to make sure the invocation will keep failing in the appropriate way.
    markMethodAsTargeted(clazz, encodedMethod, reason);

    // Only mark methods for which invocation will succeed at runtime live.
    if (encodedMethod.isStatic()) {
      return;
    }

    markDirectStaticOrConstructorMethodAsLive(clazz, encodedMethod, reason);

    // It is valid to have an invoke-direct instruction in a default interface method that
    // targets another default method in the same interface (see testInvokeSpecialToDefault-
    // Method). In a class, that would lead to a verification error.
    if (encodedMethod.isNonPrivateVirtualMethod()
        && virtualMethodsTargetedByInvokeDirect.add(encodedMethod.method)) {
      enqueueMarkMethodLiveAction(clazz, encodedMethod, reason);
    }
  }

  private void ensureFromLibraryOrThrow(DexType type, DexClass context) {
    if (!mode.isInitialTreeShaking()) {
      // b/72312389: android.jar contains parts of JUnit and most developers include JUnit in
      // their programs. This leads to library classes extending program classes. When tracing
      // main dex lists we allow this.
      return;
    }
    DexClass holder = appView.definitionFor(type);
    if (holder != null && !holder.isLibraryClass()) {
      if (forceProguardCompatibility) {
        // To ensure that the program works correctly we have to pin all super types and members
        // in the tree.
        appInfo.forEachSuperType(
            holder,
            (dexType, ignored) -> {
              if (holder.isProgramClass()) {
                DexReference holderReference = holder.toReference();
                pinnedItems.add(holderReference);
                rootSet.shouldNotBeMinified(holderReference);
                for (DexEncodedMember<?, ?> member : holder.members()) {
                  DexMember<?, ?> memberReference = member.toReference();
                  pinnedItems.add(memberReference);
                  rootSet.shouldNotBeMinified(memberReference);
                }
              }
            });
      }
      if (dontWarnPatterns.matches(context.type)) {
        // Ignore.
        return;
      }
      Diagnostic message =
          new StringDiagnostic(
              "Library class "
                  + context.type.toSourceString()
                  + (holder.isInterface() ? " implements " : " extends ")
                  + "program class "
                  + type.toSourceString());
      if (forceProguardCompatibility) {
        options.reporter.warning(message);
      } else {
        options.reporter.error(message);
      }
    }
  }

  private void reportMissingClass(DexType clazz) {
    assert !mode.isFinalTreeShaking()
            || appView.dexItemFactory().isPossiblyCompilerSynthesizedType(clazz)
            || (initialDeadProtoTypes != null && initialDeadProtoTypes.contains(clazz))
            || initialMissingTypes.contains(clazz)
        : "Unexpected missing class `" + clazz.toSourceString() + "`";
    boolean newReport = missingTypes.add(clazz);
    if (Log.ENABLED && newReport) {
      Log.verbose(Enqueuer.class, "Class `%s` is missing.", clazz);
    }
  }

  private void reportMissingMethod(DexMethod method) {
    if (Log.ENABLED && reportedMissing.add(method)) {
      Log.verbose(Enqueuer.class, "Method `%s` is missing.", method);
    }
  }

  private void reportMissingField(DexField field) {
    if (Log.ENABLED && reportedMissing.add(field)) {
      Log.verbose(Enqueuer.class, "Field `%s` is missing.", field);
    }
  }

  private void markMethodAsTargeted(
      DexProgramClass clazz, DexEncodedMethod method, KeepReason reason) {
    assert method.holder() == clazz.type;
    if (!targetedMethods.add(method, reason)) {
      // Already targeted.
      return;
    }
    markReferencedTypesAsLive(method);
    processAnnotations(clazz, method);
    method.parameterAnnotationsList.forEachAnnotation(
        annotation -> processAnnotation(clazz, method, annotation));

    if (Log.ENABLED) {
      Log.verbose(getClass(), "Method `%s` is targeted.", method.method);
    }
    if (forceProguardCompatibility) {
      // Keep targeted default methods in compatibility mode. The tree pruner will otherwise make
      // these methods abstract, whereas Proguard does not (seem to) touch their code.
      if (!method.accessFlags.isAbstract() && clazz.isInterface()) {
        markMethodAsLiveWithCompatRule(clazz, method);
      }
    }
  }

  /**
   * Adds the class to the set of instantiated classes and marks its fields and methods live
   * depending on the currently seen invokes and field reads.
   */
  // Package protected due to entry point from worklist.
  void processNewlyInstantiatedClass(
      DexProgramClass clazz,
      DexEncodedMethod context,
      InstantiationReason instantiationReason,
      KeepReason keepReason) {
    assert !clazz.isAnnotation();
    assert !clazz.isInterface();

    // Notify analyses. This is done even if `clazz` has already been marked as instantiated,
    // because each analysis may depend on seeing all the (clazz, reason) pairs. Thus, not doing so
    // could lead to nondeterminism.
    analyses.forEach(
        analysis -> analysis.processNewlyInstantiatedClass(clazz.asProgramClass(), context));

    if (!markInstantiatedClass(clazz, context, instantiationReason, keepReason)) {
      return;
    }

    if (Log.ENABLED) {
      Log.verbose(getClass(), "Class `%s` is instantiated, processing...", clazz);
    }
    // This class becomes live, so it and all its supertypes become live types.
    markTypeAsLive(clazz, graphReporter.registerClass(clazz, keepReason));
    // Instantiation triggers class initialization.
    markDirectAndIndirectClassInitializersAsLive(clazz);
    // For all methods of the class, if we have seen a call, mark the method live.
    // We only do this for virtual calls, as the other ones will be done directly.
    transitionMethodsForInstantiatedClass(clazz);
    // For all instance fields visible from the class, mark them live if we have seen a read.
    transitionFieldsForInstantiatedClass(clazz);
    // Add all dependent instance members to the workqueue.
    transitionDependentItemsForInstantiatedClass(clazz);
  }

  // TODO(b/146016987): Make this the single instantiation entry rather than the worklist action.
  private boolean markInstantiatedClass(
      DexProgramClass clazz,
      DexEncodedMethod context,
      InstantiationReason instantiationReason,
      KeepReason keepReason) {
    assert !clazz.isInterface();
    return objectAllocationInfoCollection.recordDirectAllocationSite(
        clazz, context, instantiationReason, keepReason, appInfo);
  }

  void markInterfaceAsInstantiated(DexProgramClass clazz, KeepReasonWitness witness) {
    assert !clazz.isAnnotation();
    assert clazz.isInterface();
    if (!objectAllocationInfoCollection.recordInstantiatedInterface(clazz, appInfo)) {
      return;
    }
    markTypeAsLive(clazz, witness);
    transitionDependentItemsForInstantiatedInterface(clazz);
  }

  private void markLambdaAsInstantiated(LambdaDescriptor descriptor, DexEncodedMethod context) {
    // Each descriptor is unique, so there is no check for already marking the lambda.
    for (DexType iface : descriptor.interfaces) {
      checkLambdaInterface(iface, context);
      objectAllocationInfoCollection.recordInstantiatedLambdaInterface(iface, descriptor, appInfo);
    }
  }

  private void checkLambdaInterface(DexType itf, DexEncodedMethod context) {
    DexClass clazz = definitionFor(itf);
    if (clazz == null) {
      StringDiagnostic message =
          new StringDiagnostic(
              "Lambda expression implements missing interface `" + itf.toSourceString() + "`",
              appInfo.originFor(context.holder()));
      options.reporter.warning(message);
    } else if (!clazz.isInterface()) {
      StringDiagnostic message =
          new StringDiagnostic(
              "Lambda expression expected to implement an interface, but found "
                  + "`"
                  + itf.toSourceString()
                  + "`",
              appInfo.originFor(context.holder()));
      options.reporter.warning(message);
    }
  }

  private void transitionMethodsForInstantiatedLambda(LambdaDescriptor lambda) {
    transitionMethodsForInstantiatedObject(
        InstantiatedObject.of(lambda),
        definitionFor(appInfo.dexItemFactory().objectType),
        lambda.interfaces);
  }

  private void transitionMethodsForInstantiatedClass(DexProgramClass clazz) {
    assert !clazz.isAnnotation();
    assert !clazz.isInterface();
    transitionMethodsForInstantiatedObject(
        InstantiatedObject.of(clazz), clazz, Collections.emptyList());
  }

  /**
   * Marks all methods live that are overrides of reachable methods for a given instantiation.
   *
   * <p>Only reachable methods in the hierarchy of the given instantiation and above are considered,
   * and only the lowest such reachable target (ie, mirroring resolution). All library and classpath
   * methods are considered reachable.
   */
  private void transitionMethodsForInstantiatedObject(
      InstantiatedObject instantiation, DexClass clazz, List<DexType> interfaces) {
    Set<Wrapper<DexMethod>> seen = new HashSet<>();
    WorkList<DexType> worklist = WorkList.newIdentityWorkList();
    worklist.addIfNotSeen(interfaces);
    // First we lookup and mark all targets on the instantiated class for each reachable method in
    // the super chain (inclusive).
    while (clazz != null) {
      if (clazz.isProgramClass()) {
        markProgramMethodOverridesAsLive(instantiation, clazz.asProgramClass(), seen);
      } else {
        markLibraryAndClasspathMethodOverridesAsLive(instantiation, clazz);
      }
      worklist.addIfNotSeen(Arrays.asList(clazz.interfaces.values));
      clazz = clazz.superType != null ? definitionFor(clazz.superType) : null;
    }
    // The targets for methods on the type and its supertype that are reachable are now marked.
    // In a second step, we look at interfaces. We order the search this way such that a
    // method reachable on a class takes precedence when reporting edges. That order mirrors JVM
    // resolution/dispatch.
    while (worklist.hasNext()) {
      DexType type = worklist.next();
      DexClass iface = definitionFor(type);
      if (iface == null) {
        continue;
      }
      assert iface.superType == appInfo.dexItemFactory().objectType;
      if (iface.isNotProgramClass()) {
        markLibraryAndClasspathMethodOverridesAsLive(instantiation, iface);
      } else {
        markProgramMethodOverridesAsLive(instantiation, iface.asProgramClass(), seen);
      }
      worklist.addIfNotSeen(Arrays.asList(iface.interfaces.values));
    }
  }

  private Set<DexMethod> getReachableVirtualTargets(DexProgramClass clazz) {
    return reachableVirtualTargets.getOrDefault(clazz, Collections.emptySet());
  }

  private void markProgramMethodOverridesAsLive(
      InstantiatedObject instantiation,
      DexProgramClass superClass,
      Set<Wrapper<DexMethod>> seenMethods) {
    for (DexMethod method : getReachableVirtualTargets(superClass)) {
      assert method.holder == superClass.type;
      if (seenMethods.add(MethodSignatureEquivalence.get().wrap(method))) {
        SingleResolutionResult resolution =
            appInfo.resolveMethod(superClass, method).asSingleResolution();
        assert resolution != null;
        assert resolution.getResolvedHolder().isProgramClass();
        if (resolution != null && resolution.getResolvedHolder().isProgramClass()) {
          markLiveOverrides(
              instantiation, superClass, resolution.getResolutionPair().asProgramMethod());
        }
      }
    }
  }

  private void markLiveOverrides(
      InstantiatedObject instantiation,
      DexProgramClass initialHolder,
      ProgramMethod resolutionMethod) {
    // The validity of the reachable method is checked at the point it becomes "reachable" and is
    // resolved. If the method is private, then the dispatch is not "virtual" and the method is
    // simply marked live on its holder.
    if (resolutionMethod.getMethod().isPrivateMethod()) {
      markVirtualMethodAsLive(
          resolutionMethod.getHolder(),
          resolutionMethod.getMethod(),
          graphReporter.reportReachableMethodAsLive(
              resolutionMethod.getMethod().method, resolutionMethod));
      return;
    }
    // Otherwise, we set the initial holder type to be the holder of the reachable method, which
    // ensures that access will be generally valid.
    SingleResolutionResult resolution =
        new SingleResolutionResult(
            initialHolder, resolutionMethod.getHolder(), resolutionMethod.getMethod());
    LookupTarget lookup = resolution.lookupVirtualDispatchTarget(instantiation, appInfo);
    if (lookup != null) {
      markVirtualDispatchTargetAsLive(
          lookup,
          programMethod ->
              graphReporter.reportReachableMethodAsLive(
                  resolutionMethod.getMethod().method, programMethod));
    }
  }

  private void markLibraryAndClasspathMethodOverridesAsLive(
      InstantiatedObject instantiation, DexClass libraryClass) {
    assert libraryClass.isNotProgramClass();
    if (mode.isTracingMainDex()) {
      // Library roots must be specified for tracing of library methods. For classpath the expected
      // use case is that the classes will be classloaded, thus they should have no bearing on the
      // content of the main dex file.
      return;
    }
    for (DexEncodedMethod method : libraryClass.virtualMethods()) {
      assert !method.isPrivateMethod();
      // Note: It would be reasonable to not process methods already seen during the marking of
      // program usages, but that would cause the methods to not be marked as library overrides.
      markLibraryOrClasspathOverrideLive(
          instantiation, libraryClass, appInfo.resolveMethod(libraryClass, method.method));

      // Due to API conversion, some overrides can be hidden since they will be rewritten. See
      // class comment of DesugaredLibraryAPIConverter and vivifiedType logic.
      // In the first enqueuer phase, the signature has not been desugared, so firstResolution
      // maintains the library override. In the second enqueuer phase, the signature has been
      // desugared, and the second resolution maintains the the library override.
      if (instantiation.isClass()
          && appView.rewritePrefix.hasRewrittenTypeInSignature(method.method.proto, appView)) {
        DexMethod methodToResolve =
            DesugaredLibraryAPIConverter.methodWithVivifiedTypeInSignature(
                method.method, method.holder(), appView);
        assert methodToResolve != method.method;
        markLibraryOrClasspathOverrideLive(
            instantiation,
            libraryClass,
            appInfo.resolveMethod(instantiation.asClass(), methodToResolve));
      }
    }
  }

  private void markLibraryOrClasspathOverrideLive(
      InstantiatedObject instantiation,
      DexClass libraryOrClasspathClass,
      ResolutionResult resolution) {
    LookupTarget lookup = resolution.lookupVirtualDispatchTarget(instantiation, appInfo);
    if (lookup == null) {
      return;
    }
    if (!shouldMarkLibraryMethodOverrideAsReachable(lookup)) {
      return;
    }
    markVirtualDispatchTargetAsLive(
        lookup,
        method ->
            graphReporter.reportLibraryMethodAsLive(
                instantiation, method, libraryOrClasspathClass));
    if (instantiation.isClass()) {
      // TODO(b/149976493): We need to mark these for lambdas too!
      markOverridesAsLibraryMethodOverrides(
          instantiation.asClass(), lookup.asMethodTarget().getMethod().method);
    }
  }

  private void markOverridesAsLibraryMethodOverrides(
      DexProgramClass instantiatedClass, DexMethod libraryMethodOverride) {
    WorkList<DexType> worklist = WorkList.newIdentityWorkList();
    worklist.addIfNotSeen(instantiatedClass.type);
    while (worklist.hasNext()) {
      DexType type = worklist.next();
      DexProgramClass clazz = getProgramClassOrNull(type);
      if (clazz == null) {
        continue;
      }
      DexEncodedMethod override = clazz.lookupVirtualMethod(libraryMethodOverride);
      if (override != null) {
        if (override.isLibraryMethodOverride().isTrue()) {
          continue;
        }
        override.setLibraryMethodOverride(OptionalBool.TRUE);
      }
      clazz.forEachImmediateSupertype(worklist::addIfNotSeen);
    }
  }

  /**
   * Marks all fields live that can be reached by a read assuming that the given type or one of its
   * subtypes is instantiated.
   */
  private void transitionFieldsForInstantiatedClass(DexProgramClass clazz) {
    do {
      SetWithReason<DexEncodedField> reachableFields = reachableInstanceFields.get(clazz);
      if (reachableFields != null) {
        for (DexEncodedField field : reachableFields.getItems()) {
          // TODO(b/120959039): Should the reason this field is reachable come from the set?
          markInstanceFieldAsLive(clazz, field, KeepReason.reachableFromLiveType(clazz.type));
        }
      }
      clazz = getProgramClassOrNull(clazz.superType);
    } while (clazz != null && !objectAllocationInfoCollection.isInstantiatedDirectly(clazz));
  }

  private void transitionDependentItemsForInstantiatedClass(DexProgramClass clazz) {
    assert !clazz.isAnnotation();
    assert !clazz.isInterface();
    transitionDependentItemsForInstantiatedItem(clazz);
  }

  private void transitionDependentItemsForInstantiatedInterface(DexProgramClass clazz) {
    assert clazz.isInterface();
    transitionDependentItemsForInstantiatedItem(clazz);
  }

  private void transitionDependentItemsForInstantiatedItem(DexProgramClass clazz) {
    do {
      // Handle keep rules that are dependent on the class being instantiated.
      rootSet.forEachDependentNonStaticMember(clazz, appView, this::enqueueDependentItem);

      // Visit the super type.
      clazz =
          clazz.superType != null
              ? asProgramClassOrNull(appView.definitionFor(clazz.superType))
              : null;
    } while (clazz != null && !objectAllocationInfoCollection.isInstantiatedDirectly(clazz));
  }

  private void transitionUnusedInterfaceToLive(DexProgramClass clazz) {
    if (clazz.isInterface()) {
      Set<DexProgramClass> implementedBy = unusedInterfaceTypes.remove(clazz);
      if (implementedBy != null) {
        for (DexProgramClass implementer : implementedBy) {
          markTypeAsLive(clazz, graphReporter.reportClassReferencedFrom(clazz, implementer));
        }
      }
    } else {
      assert !unusedInterfaceTypes.containsKey(clazz);
    }
  }

  private void markFieldAsTargeted(DexField field, DexEncodedMethod context) {
    markTypeAsLive(field.type, clazz -> graphReporter.reportClassReferencedFrom(clazz, context));
    markTypeAsLive(field.holder, clazz -> graphReporter.reportClassReferencedFrom(clazz, context));
  }

  private void markStaticFieldAsLive(DexEncodedField encodedField, KeepReason reason) {
    // Mark the type live here, so that the class exists at runtime.
    DexField field = encodedField.field;
    markTypeAsLive(
        field.holder, clazz -> graphReporter.reportClassReferencedFrom(clazz, encodedField));
    markTypeAsLive(
        field.type, clazz -> graphReporter.reportClassReferencedFrom(clazz, encodedField));

    DexProgramClass clazz = getProgramClassOrNull(field.holder);
    if (clazz == null) {
      return;
    }

    markDirectAndIndirectClassInitializersAsLive(clazz);

    // This field might be an instance field reachable from a static context, e.g. a getStatic that
    // resolves to an instance field. We have to keep the instance field nonetheless, as otherwise
    // we might unmask a shadowed static field and hence change semantics.
    if (encodedField.accessFlags.isStatic()) {
      if (Log.ENABLED) {
        Log.verbose(getClass(), "Adding static field `%s` to live set.", encodedField.field);
      }
    } else {
      if (Log.ENABLED) {
        Log.verbose(getClass(), "Adding instance field `%s` to live set (static context).",
            encodedField.field);
      }
    }
    processAnnotations(clazz, encodedField);
    liveFields.add(encodedField, reason);

    // Add all dependent members to the workqueue.
    enqueueRootItems(rootSet.getDependentItems(encodedField));

    // Notify analyses.
    analyses.forEach(analysis -> analysis.processNewlyLiveField(encodedField));
  }

  private void markInstanceFieldAsLive(
      DexProgramClass holder, DexEncodedField field, KeepReason reason) {
    assert field != null;
    assert field.isProgramField(appView);
    markTypeAsLive(field.holder(), reason);
    markTypeAsLive(field.field.type, reason);
    if (Log.ENABLED) {
      Log.verbose(getClass(), "Adding instance field `%s` to live set.", field.field);
    }
    processAnnotations(holder, field);
    liveFields.add(field, reason);

    // Add all dependent members to the workqueue.
    enqueueRootItems(rootSet.getDependentItems(field));

    // Notify analyses.
    analyses.forEach(analysis -> analysis.processNewlyLiveField(field));
  }

  private void markDirectStaticOrConstructorMethodAsLive(
      DexProgramClass clazz, DexEncodedMethod encodedMethod, KeepReason reason) {
    assert encodedMethod.holder() == clazz.type;

    if (!enqueueMarkMethodLiveAction(clazz, encodedMethod, reason)) {
      // Already marked live.
      return;
    }
    // Should already have marked the type live previously.
    DexMethod method = encodedMethod.method;
    assert encodedMethod.isClassInitializer() || verifyMethodIsTargeted(encodedMethod);
    assert verifyTypeIsLive(clazz);
    if (Log.ENABLED) {
      Log.verbose(
          getClass(), "Method `%s` has become live due to direct invoke", encodedMethod.method);
    }
  }

  private void markVirtualMethodAsLive(
      DexProgramClass clazz, DexEncodedMethod method, KeepReason reason) {
    assert method != null;
    // Only explicit keep rules or reflective use should make abstract methods live.
    assert !method.accessFlags.isAbstract()
        || reason.isDueToKeepRule()
        || reason.isDueToReflectiveUse();
    if (enqueueMarkMethodLiveAction(clazz, method, reason)) {
      if (Log.ENABLED) {
        Log.verbose(getClass(), "Adding virtual method `%s` to live set.", method.method);
      }
    }
  }

  public boolean isFieldReferenced(DexEncodedField field) {
    FieldAccessInfoImpl info = fieldAccessInfoCollection.get(field.field);
    return info != null;
  }

  public boolean isFieldLive(DexEncodedField field) {
    return liveFields.contains(field);
  }

  public boolean isFieldRead(DexEncodedField field) {
    FieldAccessInfoImpl info = fieldAccessInfoCollection.get(field.field);
    return info != null && info.isRead();
  }

  public boolean isFieldWrittenInMethodSatisfying(
      DexEncodedField field, Predicate<DexEncodedMethod> predicate) {
    FieldAccessInfoImpl info = fieldAccessInfoCollection.get(field.field);
    return info != null && info.isWrittenInMethodSatisfying(predicate);
  }

  public boolean isFieldWrittenOutsideDefaultConstructor(DexEncodedField field) {
    FieldAccessInfoImpl info = fieldAccessInfoCollection.get(field.field);
    if (info == null) {
      return false;
    }
    DexClass clazz = appView.definitionFor(field.holder());
    DexEncodedMethod defaultInitializer = clazz.getDefaultInitializer();
    return defaultInitializer != null
        ? info.isWrittenOutside(defaultInitializer)
        : info.isWritten();
  }

  public boolean isMemberLive(DexEncodedMember<?, ?> member) {
    assert member != null;
    return member.isDexEncodedField()
        ? liveFields.contains(member.asDexEncodedField())
        : liveMethods.contains(member.asDexEncodedMethod());
  }

  public boolean isMethodLive(DexEncodedMethod method) {
    return liveMethods.contains(method);
  }

  public boolean isMethodTargeted(DexEncodedMethod method) {
    return targetedMethods.contains(method);
  }

  public boolean isTypeLive(DexClass clazz) {
    return clazz.isProgramClass()
        ? isTypeLive(clazz.asProgramClass())
        : isNonProgramTypeLive(clazz);
  }

  public boolean isTypeLive(DexProgramClass clazz) {
    return liveTypes.contains(clazz);
  }

  public boolean isNonProgramTypeLive(DexClass clazz) {
    assert !clazz.isProgramClass();
    return liveNonProgramTypes.contains(clazz);
  }

  // Package protected due to entry point from worklist.
  void markInstanceFieldAsReachable(DexEncodedField encodedField, KeepReason reason) {
    DexField field = encodedField.field;
    if (Log.ENABLED) {
      Log.verbose(getClass(), "Marking instance field `%s` as reachable.", field);
    }

    markTypeAsLive(
        field.holder, clazz -> graphReporter.reportClassReferencedFrom(clazz, encodedField));
    markTypeAsLive(
        field.type, clazz -> graphReporter.reportClassReferencedFrom(clazz, encodedField));

    DexProgramClass clazz = getProgramClassOrNull(field.holder);
    if (clazz == null) {
      return;
    }

    // We might have a instance field access that is dispatched to a static field. In such case,
    // we have to keep the static field, so that the dispatch fails at runtime in the same way that
    // it did before. We have to keep the field even if the receiver has no live inhabitants, as
    // field resolution happens before the receiver is inspected.
    if (encodedField.accessFlags.isStatic()) {
      markStaticFieldAsLive(encodedField, reason);
    } else {
      if (objectAllocationInfoCollection.isInstantiatedDirectlyOrHasInstantiatedSubtype(clazz)) {
        markInstanceFieldAsLive(clazz, encodedField, reason);
      } else {
        // Add the field to the reachable set if the type later becomes instantiated.
        reachableInstanceFields
            .computeIfAbsent(clazz, ignore -> newSetWithoutReasonReporter())
            .add(encodedField, reason);
      }
    }
  }

  private void markVirtualMethodAsReachable(
      DexMethod method, boolean interfaceInvoke, ProgramMethod contextOrNull, KeepReason reason) {
    if (method.holder.isArrayType()) {
      // This is an array type, so the actual class will be generated at runtime. We treat this
      // like an invoke on a direct subtype of java.lang.Object that has no further subtypes.
      // As it has no subtypes, it cannot affect liveness of the program we are processing.
      // Ergo, we can ignore it. We need to make sure that the element type is available, though.
      markTypeAsLive(method.holder, reason);
      return;
    }

    // Note that all virtual methods derived from library methods are kept regardless of being
    // reachable, so the following only needs to consider reachable targets in the program.
    // TODO(b/70160030): Revise this to support tree shaking library methods on non-escaping types.
    DexProgramClass holder = getProgramClassOrNull(method.holder);
    if (holder == null) {
      // TODO(b/139464956): clean this.
      // Ensure that the full proto of the targeted method is referenced.
      recordMethodReference(method);
      return;
    }

    SingleResolutionResult resolution = resolveMethod(method, reason, interfaceInvoke);
    if (resolution == null) {
      return;
    }

    if (resolution.getResolvedHolder().isNotProgramClass()) {
      // TODO(b/70160030): If the resolution is on a library method, then the keep edge needs to go
      // directly to the target method in the program. Thus this method will need to ensure that
      // 'reason' is not already reported (eg, must be delayed / non-witness) and report that for
      // each possible target edge below.
      return;
    }

    // If the method has already been marked, just report the new reason for the resolved target.
    if (getReachableVirtualTargets(holder).contains(method)) {
      graphReporter.registerMethod(resolution.getResolvedMethod(), reason);
      return;
    }

    if (Log.ENABLED) {
      Log.verbose(getClass(), "Marking virtual method `%s` as reachable.", method);
    }

    // We have to mark the resolution targeted, even if it does not become live, we
    // need at least an abstract version of it so that it can be targeted.
    DexProgramClass resolvedHolder = resolution.getResolvedHolder().asProgramClass();
    DexEncodedMethod resolvedMethod = resolution.getResolvedMethod();
    markMethodAsTargeted(resolvedHolder, resolvedMethod, reason);

    DexProgramClass context = contextOrNull == null ? null : contextOrNull.getHolder();
    if (contextOrNull != null && !resolution.isAccessibleForVirtualDispatchFrom(context, appInfo)) {
      // Not accessible from this context, so this call will cause a runtime exception.
      return;
    }

    // If the resolved method is not a virtual target, eg, is static, dispatch will fail too.
    if (!resolvedMethod.isVirtualMethod()) {
      // This can only happen when context is null, otherwise the access check above will fail.
      assert context == null;
      return;
    }

    // The method resolved and is accessible, so currently live overrides become live.
    reachableVirtualTargets.computeIfAbsent(holder, k -> Sets.newIdentityHashSet()).add(method);

    resolution
        .lookupVirtualDispatchTargets(
            context,
            appInfo,
            (type, subTypeConsumer, lambdaConsumer) ->
                objectAllocationInfoCollection.forEachInstantiatedSubType(
                    type, subTypeConsumer, lambdaConsumer, appInfo),
            pinnedItems::contains)
        .forEach(
            target ->
                markVirtualDispatchTargetAsLive(
                    target,
                    programMethod ->
                        graphReporter.reportReachableMethodAsLive(
                            resolvedMethod.method, programMethod)));
  }

  private void markVirtualDispatchTargetAsLive(
      LookupTarget target, Function<ProgramMethod, KeepReasonWitness> reason) {
    if (target.isMethodTarget()) {
      markVirtualDispatchTargetAsLive(target.asMethodTarget(), reason);
    } else {
      assert target.isLambdaTarget();
      markVirtualDispatchTargetAsLive(target.asLambdaTarget(), reason);
    }
  }

  private void markVirtualDispatchTargetAsLive(
      DexClassAndMethod target, Function<ProgramMethod, KeepReasonWitness> reason) {
    ProgramMethod programMethod = target.asProgramMethod();
    if (programMethod != null && !programMethod.getMethod().isAbstract()) {
      markVirtualMethodAsLive(
          programMethod.getHolder(), programMethod.getMethod(), reason.apply(programMethod));
    }
  }

  private void markVirtualDispatchTargetAsLive(
      LookupLambdaTarget target, Function<ProgramMethod, KeepReasonWitness> reason) {
    ProgramMethod implementationMethod = target.getImplementationMethod().asProgramMethod();
    if (implementationMethod != null) {
      enqueueMarkMethodLiveAction(
          implementationMethod.getHolder(),
          implementationMethod.getMethod(),
          reason.apply(implementationMethod));
    }
  }

  private void markFailedResolutionTargets(
      DexMethod symbolicMethod, FailedResolutionResult failedResolution, KeepReason reason) {
    failedResolutionTargets.add(symbolicMethod);
    failedResolution.forEachFailureDependency(
        method -> {
          DexProgramClass clazz = getProgramClassOrNull(method.holder());
          if (clazz != null) {
            failedResolutionTargets.add(method.method);
            markMethodAsTargeted(clazz, method, reason);
          }
        });
  }

  private DexMethod generatedEnumValuesMethod(DexClass enumClass) {
    DexType arrayOfEnumClass =
        appView
            .dexItemFactory()
            .createType(
                appView.dexItemFactory().createString("[" + enumClass.type.toDescriptorString()));
    DexProto proto = appView.dexItemFactory().createProto(arrayOfEnumClass);
    return appView
        .dexItemFactory()
        .createMethod(enumClass.type, proto, appView.dexItemFactory().createString("values"));
  }

  private void markEnumValuesAsReachable(DexProgramClass clazz, KeepReason reason) {
    DexEncodedMethod valuesMethod = clazz.lookupMethod(generatedEnumValuesMethod(clazz));
    if (valuesMethod != null) {
      // TODO(sgjesse): Does this have to be enqueued as a root item? Right now it is done as the
      // marking for not renaming it is in the root set.
      workList.enqueueMarkMethodKeptAction(clazz, valuesMethod, reason);
      pinnedItems.add(valuesMethod.toReference());
      rootSet.shouldNotBeMinified(valuesMethod.toReference());
    }
  }

  // Package protected due to entry point from worklist.
  void markSuperMethodAsReachable(DexMethod method, DexEncodedMethod from) {
    KeepReason reason = KeepReason.targetedBySuperFrom(from);
    SingleResolutionResult resolution = resolveMethod(method, reason);
    if (resolution == null) {
      return;
    }
    // If the resolution is in the program, mark it targeted.
    if (resolution.getResolvedHolder().isProgramClass()) {
      markMethodAsTargeted(
          resolution.getResolvedHolder().asProgramClass(), resolution.getResolvedMethod(), reason);
    }
    // If invoke target is invalid (inaccessible or not an instance-method) record it and stop.
    // TODO(b/146016987): We should be passing the full program context and not looking it up again.
    DexProgramClass fromHolder = appInfo.definitionFor(from.holder()).asProgramClass();
    DexEncodedMethod target = resolution.lookupInvokeSuperTarget(fromHolder, appInfo);
    if (target == null) {
      failedResolutionTargets.add(resolution.getResolvedMethod().method);
      return;
    }

    DexProgramClass clazz = getProgramClassOrNull(target.holder());
    if (clazz == null) {
      return;
    }
    if (Log.ENABLED) {
      Log.verbose(getClass(), "Adding super constraint from `%s` to `%s`", from.method,
          target.method);
    }
    if (superInvokeDependencies.computeIfAbsent(
        from, ignore -> Sets.newIdentityHashSet()).add(target)) {
      if (liveMethods.contains(from)) {
        markMethodAsTargeted(clazz, target, KeepReason.invokedViaSuperFrom(from));
        if (!target.accessFlags.isAbstract()) {
          markVirtualMethodAsLive(clazz, target, KeepReason.invokedViaSuperFrom(from));
        }
      }
    }
  }

  // Returns the set of live types.
  public Set<DexProgramClass> traceMainDex(
      RootSet rootSet, ExecutorService executorService, Timing timing) throws ExecutionException {
    assert analyses.isEmpty();
    assert mode.isTracingMainDex();
    this.rootSet = rootSet;
    // Translate the result of root-set computation into enqueuer actions.
    enqueueRootItems(rootSet.noShrinking);
    trace(executorService, timing);
    options.reporter.failIfPendingErrors();
    return liveTypes.getItems();
  }

  public AppInfoWithLiveness traceApplication(
      RootSet rootSet,
      ProguardClassFilter dontWarnPatterns,
      ExecutorService executorService,
      Timing timing)
      throws ExecutionException {
    this.rootSet = rootSet;
    this.dontWarnPatterns = dontWarnPatterns;
    // Translate the result of root-set computation into enqueuer actions.
    if (appView.options().isShrinking() || appView.options().getProguardConfiguration() == null) {
      enqueueRootItems(rootSet.noShrinking);
    } else {
      // Add everything if we are not shrinking.
      assert appView.options().getProguardConfiguration().getKeepAllRule() != null;
      ImmutableSet<ProguardKeepRuleBase> keepAllSet =
          ImmutableSet.of(appView.options().getProguardConfiguration().getKeepAllRule());
      for (DexProgramClass dexProgramClass : appView.appInfo().classes()) {
        for (DexEncodedMethod method : dexProgramClass.methods()) {
          this.enqueueRootItem(method, keepAllSet);
        }
        for (DexEncodedField field : dexProgramClass.fields()) {
          this.enqueueRootItem(field, keepAllSet);
        }
        this.enqueueRootItem(dexProgramClass, keepAllSet);
      }
    }
    trace(executorService, timing);
    options.reporter.failIfPendingErrors();
    finalizeLibraryMethodOverrideInformation();
    analyses.forEach(EnqueuerAnalysis::done);
    assert verifyKeptGraph();
    AppInfoWithLiveness appInfoWithLiveness = createAppInfo(appInfo);
    if (options.testing.enqueuerInspector != null) {
      options.testing.enqueuerInspector.accept(appInfoWithLiveness, mode);
    }
    return appInfoWithLiveness;
  }

  private static class SyntheticAdditions {

    Map<DexType, Pair<DexProgramClass, DexEncodedMethod>> syntheticInstantiations =
        new IdentityHashMap<>();

    Map<DexMethod, ProgramMethod> liveMethods = new IdentityHashMap<>();

    Map<DexType, DexClasspathClass> syntheticClasspathClasses = new IdentityHashMap<>();

    // Subset of live methods that need to be pinned.
    Set<DexMethod> pinnedMethods = Sets.newIdentityHashSet();

    // Subset of synthesized classes that need to be added to the main-dex file.
    Set<DexType> mainDexTypes = Sets.newIdentityHashSet();

    boolean isEmpty() {
      boolean empty = syntheticInstantiations.isEmpty() && liveMethods.isEmpty();
      assert !empty || (pinnedMethods.isEmpty() && mainDexTypes.isEmpty());
      return empty;
    }

    void addInstantiatedClass(
        DexProgramClass clazz, DexEncodedMethod context, boolean isMainDexClass) {
      assert !syntheticInstantiations.containsKey(clazz.type);
      syntheticInstantiations.put(clazz.type, new Pair<>(clazz, context));
      if (isMainDexClass) {
        mainDexTypes.add(clazz.type);
      }
    }

    void addClasspathClass(DexClasspathClass clazz) {
      DexClasspathClass old = syntheticClasspathClasses.put(clazz.type, clazz);
      assert old == null;
    }

    void addLiveMethod(ProgramMethod method) {
      DexMethod signature = method.getMethod().method;
      assert !liveMethods.containsKey(signature);
      liveMethods.put(signature, method);
    }

    void addLiveAndPinnedMethod(ProgramMethod method) {
      addLiveMethod(method);
      pinnedMethods.add(method.getMethod().method);
    }

    void amendApplication(Builder appBuilder) {
      assert !isEmpty();
      for (Pair<DexProgramClass, DexEncodedMethod> clazzAndContext :
          syntheticInstantiations.values()) {
        appBuilder.addProgramClass(clazzAndContext.getFirst());
      }
      appBuilder.addClasspathClasses(syntheticClasspathClasses.values());
      appBuilder.addToMainDexList(mainDexTypes);
    }

    void enqueueWorkItems(Enqueuer enqueuer) {
      assert !isEmpty();
      assert enqueuer.mode.isInitialTreeShaking();
      // All synthetic additions are initial tree shaking only. No need to track keep reasons.
      KeepReasonWitness fakeReason = enqueuer.graphReporter.fakeReportShouldNotBeUsed();

      enqueuer.pinnedItems.addAll(pinnedMethods);
      for (Pair<DexProgramClass, DexEncodedMethod> clazzAndContext :
          syntheticInstantiations.values()) {
        enqueuer.workList.enqueueMarkInstantiatedAction(
            clazzAndContext.getFirst(),
            clazzAndContext.getSecond(),
            InstantiationReason.SYNTHESIZED_CLASS,
            fakeReason);
      }
      for (ProgramMethod liveMethod : liveMethods.values()) {
        assert !enqueuer.targetedMethods.contains(liveMethod.getMethod());
        DexProgramClass holder = liveMethod.getHolder();
        DexEncodedMethod method = liveMethod.getMethod();
        enqueuer.markMethodAsTargeted(holder, method, fakeReason);
        enqueuer.enqueueMarkMethodLiveAction(holder, method, fakeReason);
      }
    }
  }

  private void synthesize() {
    if (!mode.isInitialTreeShaking()) {
      return;
    }
    // First part of synthesis is to create and register all reachable synthetic additions.
    // In particular these additions are order independent, i.e., it does not matter which are
    // registered first and no dependencies may exist among them.
    SyntheticAdditions additions = new SyntheticAdditions();
    synthesizeInterfaceMethodBridges(additions);
    synthesizeLambdas(additions);
    synthesizeLibraryConversionWrappers(additions);
    if (additions.isEmpty()) {
      return;
    }

    // Now all additions are computed, the application is atomically extended with those additions.
    Builder appBuilder = appInfo.app().asDirect().builder();
    additions.amendApplication(appBuilder);
    DirectMappedDexApplication app = appBuilder.build();
    appInfo = new AppInfoWithClassHierarchy(app);
    appView.setAppInfo(appInfo);
    subtypingInfo = new SubtypingInfo(app.allClasses(), app);

    // Finally once all synthesized items "exist" it is now safe to continue tracing. The new work
    // items are enqueued and the fixed point will continue once this subroutine returns.
    additions.enqueueWorkItems(this);
  }

  private void synthesizeInterfaceMethodBridges(SyntheticAdditions additions) {
    for (ProgramMethod bridge : syntheticInterfaceMethodBridges.values()) {
      DexProgramClass holder = bridge.getHolder();
      DexEncodedMethod method = bridge.getMethod();
      holder.addVirtualMethod(method);
      additions.addLiveAndPinnedMethod(bridge);
    }
    syntheticInterfaceMethodBridges.clear();
  }

  private void synthesizeLambdas(SyntheticAdditions additions) {
    if (lambdaRewriter == null || lambdaClasses.isEmpty()) {
      assert lambdaCallSites.isEmpty();
      assert classesWithSerializableLambdas.isEmpty();
      return;
    }
    for (Pair<LambdaClass, DexEncodedMethod> lambdaClassAndContext : lambdaClasses.values()) {
      // Add all desugared classes to the application, main-dex list, and mark them instantiated.
      LambdaClass lambdaClass = lambdaClassAndContext.getFirst();
      DexEncodedMethod context = lambdaClassAndContext.getSecond();
      DexProgramClass programClass = lambdaClass.getOrCreateLambdaClass();
      additions.addInstantiatedClass(programClass, context, lambdaClass.addToMainDexList.get());
      // Mark the instance constructor targeted and live.
      DexEncodedMethod constructor = programClass.lookupDirectMethod(lambdaClass.constructor);
      KeepReason reason = KeepReason.instantiatedIn(context);
      markMethodAsTargeted(programClass, constructor, reason);
      markDirectStaticOrConstructorMethodAsLive(programClass, constructor, reason);
    }

    // Rewrite all of the invoke-dynamic instructions to lambda class instantiations.
    lambdaCallSites.forEach(this::rewriteLambdaCallSites);

    // Remove all '$deserializeLambda$' methods which are not supported by desugaring.
    for (DexProgramClass clazz : classesWithSerializableLambdas) {
      clazz.removeMethod(appView.dexItemFactory().deserializeLambdaMethod);
    }

    // Clear state before next fixed point iteration.
    lambdaClasses.clear();
    lambdaCallSites.clear();
    classesWithSerializableLambdas.clear();
  }

  private void finalizeLibraryMethodOverrideInformation() {
    for (DexProgramClass liveType : liveTypes.getItems()) {
      for (DexEncodedMethod method : liveType.virtualMethods()) {
        if (method.isLibraryMethodOverride().isUnknown()) {
          method.setLibraryMethodOverride(OptionalBool.FALSE);
        }
      }
    }
  }

  private boolean verifyKeptGraph() {
    if (appView.options().testing.verifyKeptGraphInfo) {
      for (DexProgramClass liveType : liveTypes.getItems()) {
        assert graphReporter.verifyRootedPath(liveType);
      }
    }
    return true;
  }

  private AppInfoWithLiveness createAppInfo(AppInfoWithClassHierarchy appInfo) {
    // Once all tracing is done, we generate accessor methods for lambdas.
    // These are assumed to be simple forwarding or access flag updates, thus no further tracing
    // is needed. These cannot be generated as part of lambda synthesis as changing a direct method
    // to a static method will invalidate the reachable method sets for tracing methods.
    ensureLambdaAccessibility();

    // Compute the set of dead proto types.
    deadProtoTypeCandidates.removeIf(this::isTypeLive);

    // Remove the temporary mappings that have been inserted into the field access info collection
    // and verify that the mapping is then one-to-one.
    fieldAccessInfoCollection.removeIf(
        (field, info) -> field != info.getField() || info == MISSING_FIELD_ACCESS_INFO);
    assert fieldAccessInfoCollection.verifyMappingIsOneToOne();

    // Verify all references on the input app before synthesizing definitions.
    assert verifyReferences(appInfo.app());

    // Prune the root set items that turned out to be dead.
    // TODO(b/150736225): Pruning of dead root set items is still incomplete.
    rootSet.pruneDeadItems(appView, this);

    // Ensure references from all hard coded factory items.
    appView.dexItemFactory().forEachPossiblyCompilerSynthesizedType(this::recordTypeReference);

    // Rebuild a new app only containing referenced types.
    Set<DexLibraryClass> libraryClasses = Sets.newIdentityHashSet();
    Set<DexClasspathClass> classpathClasses = Sets.newIdentityHashSet();
    for (DexClass clazz : liveNonProgramTypes) {
      if (clazz.isLibraryClass()) {
        libraryClasses.add(clazz.asLibraryClass());
      } else if (clazz.isClasspathClass()) {
        classpathClasses.add(clazz.asClasspathClass());
      } else {
        assert false;
      }
    }

    // Add just referenced non-program types. We can't replace the program classes at this point as
    // they are needed in tree pruning.
    Builder appBuilder = appInfo.app().asDirect().builder();
    appBuilder.replaceLibraryClasses(libraryClasses);
    appBuilder.replaceClasspathClasses(classpathClasses);
    DirectMappedDexApplication app = appBuilder.build();

    // Verify the references on the pruned application after type synthesis.
    assert verifyReferences(app);

    AppInfoWithLiveness appInfoWithLiveness =
        new AppInfoWithLiveness(
            app,
            SetUtils.mapIdentityHashSet(deadProtoTypeCandidates, DexProgramClass::getType),
            missingTypes,
            SetUtils.mapIdentityHashSet(liveTypes.getItems(), DexProgramClass::getType),
            Collections.unmodifiableSet(instantiatedAppServices),
            Enqueuer.toSortedDescriptorSet(targetedMethods.getItems()),
            Collections.unmodifiableSet(failedResolutionTargets),
            ImmutableSortedSet.copyOf(DexMethod::slowCompareTo, bootstrapMethods),
            ImmutableSortedSet.copyOf(DexMethod::slowCompareTo, methodsTargetedByInvokeDynamic),
            ImmutableSortedSet.copyOf(
                DexMethod::slowCompareTo, virtualMethodsTargetedByInvokeDirect),
            toSortedDescriptorSet(liveMethods.getItems()),
            // Filter out library fields and pinned fields, because these are read by default.
            fieldAccessInfoCollection,
            objectAllocationInfoCollection.build(appInfo),
            // TODO(b/132593519): Do we require these sets to be sorted for determinism?
            toImmutableSortedMap(virtualInvokes, PresortedComparable::slowCompare),
            toImmutableSortedMap(interfaceInvokes, PresortedComparable::slowCompare),
            toImmutableSortedMap(superInvokes, PresortedComparable::slowCompare),
            toImmutableSortedMap(directInvokes, PresortedComparable::slowCompare),
            toImmutableSortedMap(staticInvokes, PresortedComparable::slowCompare),
            callSites,
            pinnedItems,
            rootSet.mayHaveSideEffects,
            rootSet.noSideEffects,
            rootSet.assumedValues,
            rootSet.alwaysInline,
            rootSet.forceInline,
            rootSet.neverInline,
            rootSet.whyAreYouNotInlining,
            rootSet.keepConstantArguments,
            rootSet.keepUnusedArguments,
            rootSet.reprocess,
            rootSet.neverReprocess,
            rootSet.alwaysClassInline,
            rootSet.neverClassInline,
            rootSet.neverMerge,
            rootSet.neverPropagateValue,
            joinIdentifierNameStrings(rootSet.identifierNameStrings, identifierNameStrings),
            Collections.emptySet(),
            Collections.emptyMap(),
            EnumValueInfoMapCollection.empty(),
            constClassReferences,
            initClassReferences);
    appInfo.markObsolete();
    return appInfoWithLiveness;
  }

  private void ensureLambdaAccessibility() {
    if (lambdaRewriter == null) {
      return;
    }
    lambdaRewriter
        .getKnownLambdaClasses()
        .forEach(
            (type, lambda) -> {
              DexProgramClass synthesizedClass = getProgramClassOrNull(type);
              assert synthesizedClass != null;
              assert liveTypes.contains(synthesizedClass);
              if (synthesizedClass == null) {
                return;
              }
              DexMethod method = lambda.descriptor.getMainMethod();
              if (!liveMethods.contains(synthesizedClass.lookupMethod(method))) {
                return;
              }
              DexEncodedMethod accessor = lambda.target.ensureAccessibilityIfNeeded(false);
              if (accessor == null) {
                return;
              }
              DexProgramClass accessorClass = getProgramClassOrNull(accessor.holder());
              assert accessorClass != null;
              if (accessorClass != null) {
                liveMethods.add(accessorClass, accessor, graphReporter.fakeReportShouldNotBeUsed());
              }
            });
  }

  private boolean verifyReferences(DexApplication app) {
    WorkList<DexClass> worklist = WorkList.newIdentityWorkList();
    for (DexProgramClass clazz : liveTypes.getItems()) {
      worklist.addIfNotSeen(clazz);
    }
    while (worklist.hasNext()) {
      DexClass clazz = worklist.next();
      assert verifyReferencedType(clazz, worklist, app);
    }
    return true;
  }

  private boolean verifyReferencedType(
      DexType type, WorkList<DexClass> worklist, DexApplication app) {
    if (type.isArrayType()) {
      type = type.toBaseType(appView.dexItemFactory());
    }
    if (!type.isClassType()) {
      return true;
    }
    DexClass clazz = app.definitionFor(type);
    if (clazz == null) {
      assert missingTypes.contains(type) : "Expected type to be in missing types': " + type;
    } else {
      assert !missingTypes.contains(type) : "Type with definition also in missing types: " + type;
      // Eager assert while the context is still present.
      assert clazz.isProgramClass() || liveNonProgramTypes.contains(clazz)
          : "Expected type to be in live non-program types: " + clazz;
      worklist.addIfNotSeen(clazz);
    }
    return true;
  }

  private boolean verifyReferencedType(
      DexClass clazz, WorkList<DexClass> worklist, DexApplication app) {
    for (DexType supertype : clazz.allImmediateSupertypes()) {
      assert verifyReferencedType(supertype, worklist, app);
    }
    assert clazz.isProgramClass() || liveNonProgramTypes.contains(clazz)
        : "Expected type to be in live non-program types: " + clazz;
    for (DexEncodedField field : clazz.fields()) {
      if (clazz.isNotProgramClass() || isFieldReferenced(field)) {
        assert verifyReferencedType(field.field.type, worklist, app);
      }
    }
    for (DexEncodedMethod method : clazz.methods()) {
      if (clazz.isNotProgramClass() || isMethodTargeted(method)) {
        assert verifyReferencedMethod(method, worklist, app);
      }
    }
    return true;
  }

  private boolean verifyReferencedMethod(
      DexEncodedMethod method, WorkList<DexClass> worklist, DexApplication app) {
    assert verifyReferencedType(method.method.proto.returnType, worklist, app);
    for (DexType param : method.method.proto.parameters.values) {
      assert verifyReferencedType(param, worklist, app);
    }
    return true;
  }

  private void synthesizeLibraryConversionWrappers(SyntheticAdditions additions) {
    if (desugaredLibraryWrapperAnalysis == null) {
      return;
    }

    // Generate first the callbacks since they may require extra wrappers.
    List<DexEncodedMethod> callbacks = desugaredLibraryWrapperAnalysis.generateCallbackMethods();
    for (DexEncodedMethod callback : callbacks) {
      DexProgramClass clazz = getProgramClassOrNull(callback.holder());
      additions.addLiveMethod(new ProgramMethod(clazz, callback));
    }

    // Generate the wrappers.
    List<DexProgramClass> wrappers = desugaredLibraryWrapperAnalysis.generateWrappers();
    for (DexProgramClass wrapper : wrappers) {
      additions.addInstantiatedClass(wrapper, null, false);
      // Mark all methods on the wrapper as live and targeted.
      for (DexEncodedMethod method : wrapper.methods()) {
        additions.addLiveMethod(new ProgramMethod(wrapper, method));
      }
    }

    // Add all vivified types as classpath classes.
    // They will be available at runtime in the desugared library dex file.
    desugaredLibraryWrapperAnalysis
        .generateWrappersSuperTypeMock(wrappers)
        .forEach(additions::addClasspathClass);
  }

  private void rewriteLambdaCallSites(
      DexEncodedMethod method, Map<DexCallSite, LambdaClass> callSites) {
    assert !callSites.isEmpty();
    CfCode code = method.getCode().asCfCode();
    List<CfInstruction> instructions = code.instructions;
    int replaced = 0;
    int maxTemp = 0;
    for (int i = 0; i < instructions.size(); i++) {
      CfInstruction instruction = instructions.get(i);
      if (instruction instanceof CfInvokeDynamic) {
        LambdaClass lambdaClass = callSites.get(((CfInvokeDynamic) instruction).getCallSite());
        if (lambdaClass == null) {
          continue;
        }
        if (lambdaClass.isStateless()) {
          CfFieldInstruction getStaticLambdaInstance =
              new CfFieldInstruction(
                  Opcodes.GETSTATIC, lambdaClass.lambdaField, lambdaClass.lambdaField);
          instructions.set(i, getStaticLambdaInstance);
        } else {
          List<CfInstruction> replacement = new ArrayList<>();
          int arguments = lambdaClass.descriptor.captures.size();
          int temp = code.getMaxLocals();
          for (int j = arguments - 1; j >= 0; j--) {
            ValueType type = ValueType.fromDexType(lambdaClass.descriptor.captures.values[j]);
            replacement.add(new CfStore(type, temp));
            temp += type.requiredRegisters();
          }
          maxTemp = Math.max(temp, maxTemp);
          replacement.add(new CfNew(lambdaClass.type));
          replacement.add(new CfStackInstruction(Opcode.Dup));
          for (int j = 0; j < arguments; j++) {
            ValueType type = ValueType.fromDexType(lambdaClass.descriptor.captures.values[j]);
            temp -= type.requiredRegisters();
            replacement.add(new CfLoad(type, temp));
          }
          replacement.add(new CfInvoke(Opcodes.INVOKESPECIAL, lambdaClass.constructor, false));
          instructions.remove(i);
          instructions.addAll(i, replacement);
        }
        ++replaced;
      }
    }
    if (maxTemp > 0) {
      assert maxTemp > code.getMaxLocals();
      code.setMaxLocals(maxTemp);
    }
    assert replaced == callSites.size();
  }

  private static <D extends DexEncodedMember<D, R>, R extends DexMember<D, R>>
      SortedSet<R> toSortedDescriptorSet(Set<D> set) {
    ImmutableSortedSet.Builder<R> builder =
        new ImmutableSortedSet.Builder<>(PresortedComparable::slowCompareTo);
    for (D item : set) {
      builder.add(item.toReference());
    }
    return builder.build();
  }

  private static Object2BooleanMap<DexReference> joinIdentifierNameStrings(
      Set<DexReference> explicit, Set<DexReference> implicit) {
    Object2BooleanMap<DexReference> result = new Object2BooleanArrayMap<>();
    for (DexReference e : explicit) {
      result.putIfAbsent(e, true);
    }
    for (DexReference i : implicit) {
      result.putIfAbsent(i, false);
    }
    return result;
  }

  private void trace(ExecutorService executorService, Timing timing) throws ExecutionException {
    timing.begin("Grow the tree.");
    try {
      while (true) {
        long numberOfLiveItems = getNumberOfLiveItems();
        while (!workList.isEmpty()) {
          EnqueuerAction action = workList.poll();
          action.run(this);
        }

        // Continue fix-point processing if -if rules are enabled by items that newly became live.
        long numberOfLiveItemsAfterProcessing = getNumberOfLiveItems();
        if (numberOfLiveItemsAfterProcessing > numberOfLiveItems) {
          // Build the mapping of active if rules. We use a single collection of if-rules to allow
          // removing if rules that have a constant sequent keep rule when they materialize.
          if (activeIfRules == null) {
            activeIfRules = new HashMap<>();
            IfRuleClassPartEquivalence equivalence = new IfRuleClassPartEquivalence();
            for (ProguardIfRule ifRule : rootSet.ifRules) {
              Wrapper<ProguardIfRule> wrap = equivalence.wrap(ifRule);
              activeIfRules.computeIfAbsent(wrap, ignore -> new LinkedHashSet<>()).add(ifRule);
            }
          }
          ConsequentRootSetBuilder consequentSetBuilder =
              new ConsequentRootSetBuilder(appView, subtypingInfo, this);
          IfRuleEvaluator ifRuleEvaluator =
              new IfRuleEvaluator(
                  appView,
                  subtypingInfo,
                  this,
                  executorService,
                  activeIfRules,
                  consequentSetBuilder);
          addConsequentRootSet(ifRuleEvaluator.run(), false);
          assert getNumberOfLiveItems() == numberOfLiveItemsAfterProcessing;
          if (!workList.isEmpty()) {
            continue;
          }
        }

        // Continue fix-point processing while there are additional work items to ensure items that
        // are passed to Java reflections are traced.
        if (!pendingReflectiveUses.isEmpty()) {
          pendingReflectiveUses.forEach(this::handleReflectiveBehavior);
          pendingReflectiveUses.clear();
        }
        if (!workList.isEmpty()) {
          continue;
        }

        // Notify each analysis that a fixpoint has been reached, and give each analysis an
        // opportunity to add items to the worklist.
        analyses.forEach(analysis -> analysis.notifyFixpoint(this, workList, timing));
        if (!workList.isEmpty()) {
          continue;
        }

        addConsequentRootSet(computeDelayedInterfaceMethodSyntheticBridges(), true);
        rootSet.delayedRootSetActionItems.clear();

        if (!workList.isEmpty()) {
          continue;
        }

        synthesize();
        if (!workList.isEmpty()) {
          continue;
        }

        // Reached the fixpoint.
        break;
      }

      if (Log.ENABLED) {
        Set<DexEncodedMethod> allLive = Sets.newIdentityHashSet();
        Set<DexEncodedMethod> reachableNotLive = Sets.difference(allLive, liveMethods.getItems());
        Log.debug(getClass(), "%s methods are reachable but not live", reachableNotLive.size());
        Log.info(getClass(), "Only reachable: %s", reachableNotLive);
        SetView<DexEncodedMethod> targetedButNotLive = Sets
            .difference(targetedMethods.getItems(), liveMethods.getItems());
        Log.debug(getClass(), "%s methods are targeted but not live", targetedButNotLive.size());
        Log.info(getClass(), "Targeted but not live: %s", targetedButNotLive);
      }
    } finally {
      timing.end();
    }
    unpinLambdaMethods();
  }

  private long getNumberOfLiveItems() {
    long result = liveTypes.items.size();
    result += liveMethods.items.size();
    result += liveFields.items.size();
    return result;
  }

  private void addConsequentRootSet(ConsequentRootSet consequentRootSet, boolean addNoShrinking) {
    consequentRootSet.forEachClassWithDependentItems(
        appView,
        clazz -> {
          if (isTypeLive(clazz)) {
            consequentRootSet.forEachDependentInstanceConstructor(
                clazz, appView, this::enqueueHolderWithDependentInstanceConstructor);
            consequentRootSet.forEachDependentStaticMember(
                clazz, appView, this::enqueueDependentItem);
            if (objectAllocationInfoCollection.isInstantiatedDirectlyOrHasInstantiatedSubtype(
                clazz)) {
              consequentRootSet.forEachDependentNonStaticMember(
                  clazz, appView, this::enqueueDependentItem);
            }
            compatEnqueueHolderIfDependentNonStaticMember(
                clazz, consequentRootSet.getDependentKeepClassCompatRule(clazz.type));
          }
        });
    consequentRootSet.forEachMemberWithDependentItems(
        appView,
        member -> {
          if (isMemberLive(member)) {
            enqueueRootItems(consequentRootSet.getDependentItems(member));
          }
        });
    // TODO(b/132600955): This modifies the root set. Should the consequent be persistent?
    rootSet.addConsequentRootSet(consequentRootSet, addNoShrinking);
    enqueueRootItems(consequentRootSet.noShrinking);
    // Check for compatibility rules indicating that the holder must be implicitly kept.
    if (forceProguardCompatibility) {
      consequentRootSet.dependentKeepClassCompatRule.forEach(
          (precondition, compatRules) -> {
            assert precondition.isDexType();
            DexClass preconditionHolder = appView.definitionFor(precondition.asDexType());
            compatEnqueueHolderIfDependentNonStaticMember(preconditionHolder, compatRules);
          });
    }
  }

  private ConsequentRootSet computeDelayedInterfaceMethodSyntheticBridges() {
    RootSetBuilder builder = new RootSetBuilder(appView, subtypingInfo);
    for (DelayedRootSetActionItem delayedRootSetActionItem : rootSet.delayedRootSetActionItems) {
      if (delayedRootSetActionItem.isInterfaceMethodSyntheticBridgeAction()) {
        handleInterfaceMethodSyntheticBridgeAction(
            delayedRootSetActionItem.asInterfaceMethodSyntheticBridgeAction(), builder);
      }
    }
    return builder.buildConsequentRootSet();
  }

  private Map<DexMethod, ProgramMethod> syntheticInterfaceMethodBridges = new IdentityHashMap<>();

  private void handleInterfaceMethodSyntheticBridgeAction(
      InterfaceMethodSyntheticBridgeAction action, RootSetBuilder builder) {
    ProgramMethod methodToKeep = action.getMethodToKeep();
    ProgramMethod singleTarget = action.getSingleTarget();
    DexEncodedMethod singleTargetMethod = singleTarget.getMethod();
    if (rootSet.noShrinking.containsKey(singleTargetMethod.method)) {
      return;
    }
    if (methodToKeep != singleTarget) {
      assert null == methodToKeep.getHolder().lookupMethod(methodToKeep.getMethod().method);
      ProgramMethod old =
          syntheticInterfaceMethodBridges.put(methodToKeep.getMethod().method, methodToKeep);
      if (old == null) {
        if (singleTargetMethod.isLibraryMethodOverride().isTrue()) {
          methodToKeep.getMethod().setLibraryMethodOverride(OptionalBool.TRUE);
        }
        DexProgramClass singleTargetHolder = singleTarget.getHolder();
        assert singleTargetHolder.isInterface();
        markVirtualMethodAsReachable(
            singleTargetMethod.method,
            singleTargetHolder.isInterface(),
            null,
            graphReporter.fakeReportShouldNotBeUsed());
        enqueueMarkMethodLiveAction(
            singleTargetHolder, singleTargetMethod, graphReporter.fakeReportShouldNotBeUsed());
      }
    }
    action.getAction().accept(builder);
  }

  private void unpinLambdaMethods() {
    assert desugaredLambdaImplementationMethods.isEmpty()
        || options.desugarState == DesugarState.ON;
    for (DexMethod method : desugaredLambdaImplementationMethods) {
      pinnedItems.remove(method);
      rootSet.prune(method);
    }
    desugaredLambdaImplementationMethods.clear();
  }

  void retainAnnotationForFinalTreeShaking(DexAnnotation annotation) {
    assert mode.isInitialTreeShaking();
    if (annotationRemoverBuilder != null) {
      annotationRemoverBuilder.retainAnnotation(annotation);
    }
  }

  // Package protected due to entry point from worklist.
  void markMethodAsKept(DexProgramClass holder, DexEncodedMethod target, KeepReason reason) {
    DexMethod method = target.method;
    if (target.isVirtualMethod()) {
      // A virtual method. Mark it as reachable so that subclasses, if instantiated, keep
      // their overrides. However, we don't mark it live, as a keep rule might not imply that
      // the corresponding class is live.
      markVirtualMethodAsReachable(method, holder.isInterface(), null, reason);
      if (holder.isInterface()) {
        // Reachability for default methods is based on live subtypes in general. For keep rules,
        // we need special handling as we essentially might have live subtypes that are outside of
        // the current compilation unit. Keep either the default-method or its implementation
        // method.
        // TODO(b/120959039): Codify the kept-graph expectations for these cases in tests.
        if (target.isNonAbstractVirtualMethod()) {
          markVirtualMethodAsLive(holder, target, reason);
        } else {
          DexEncodedMethod implementation = target.getDefaultInterfaceMethodImplementation();
          if (implementation != null) {
            DexProgramClass companion = getProgramClassOrNull(implementation.holder());
            markTypeAsLive(companion, graphReporter.reportCompanionClass(holder, companion));
            markVirtualMethodAsLive(
                companion,
                implementation,
                graphReporter.reportCompanionMethod(target, implementation));
          }
        }
      }
    } else {
      markMethodAsTargeted(holder, target, reason);
      markDirectStaticOrConstructorMethodAsLive(holder, target, reason);
    }
  }

  // Package protected due to entry point from worklist.
  void markFieldAsKept(DexProgramClass holder, DexEncodedField target, KeepReason reason) {
    assert holder.type == target.holder();
    if (target.accessFlags.isStatic()) {
      markStaticFieldAsLive(target, reason);
    } else {
      markInstanceFieldAsReachable(target, reason);
    }
  }

  private boolean shouldMarkLibraryMethodOverrideAsReachable(LookupTarget override) {
    if (override.isLambdaTarget()) {
      return true;
    }
    ProgramMethod programMethod = override.asMethodTarget().asProgramMethod();
    if (programMethod == null) {
      return false;
    }
    DexProgramClass clazz = programMethod.getHolder();
    DexEncodedMethod method = programMethod.getMethod();
    assert method.isVirtualMethod();

    if (method.isAbstract() || method.isPrivateMethod()) {
      return false;
    }

    if (appView.isClassEscapingIntoLibrary(clazz.type)) {
      return true;
    }

    // If there is an instantiated subtype of `clazz` that escapes into the library and does not
    // override `method` then we need to mark the method as being reachable.
    Set<DexProgramClass> immediateSubtypes = getImmediateSubtypesInInstantiatedHierarchy(clazz);
    if (immediateSubtypes.isEmpty()) {
      return false;
    }
    Deque<DexProgramClass> worklist = new ArrayDeque<>(immediateSubtypes);
    Set<DexProgramClass> visited = SetUtils.newIdentityHashSet(immediateSubtypes);

    while (!worklist.isEmpty()) {
      DexProgramClass current = worklist.removeFirst();
      assert visited.contains(current);

      if (current.lookupVirtualMethod(method.method) != null) {
        continue;
      }

      if (appView.isClassEscapingIntoLibrary(current.type)) {
        return true;
      }

      for (DexProgramClass subtype : getImmediateSubtypesInInstantiatedHierarchy(current)) {
        if (visited.add(subtype)) {
          worklist.add(subtype);
        }
      }
    }

    return false;
  }

  private Set<DexProgramClass> getImmediateSubtypesInInstantiatedHierarchy(DexProgramClass clazz) {
    Set<DexClass> subtypes =
        objectAllocationInfoCollection.getImmediateSubtypesInInstantiatedHierarchy(clazz.type);
    if (subtypes == null) {
      return Collections.emptySet();
    }
    Set<DexProgramClass> programClasses = SetUtils.newIdentityHashSet(subtypes.size());
    for (DexClass subtype : subtypes) {
      if (subtype.isProgramClass()) {
        programClasses.add(subtype.asProgramClass());
      }
    }
    return programClasses;
  }

  // Package protected due to entry point from worklist.
  void markMethodAsLive(DexEncodedMethod method, KeepReason reason) {
    assert liveMethods.contains(method);

    DexProgramClass clazz = getProgramClassOrNull(method.holder());
    if (clazz == null) {
      return;
    }

    if (method.isStatic()) {
      markDirectAndIndirectClassInitializersAsLive(clazz);
    }

    Set<DexEncodedMethod> superCallTargets = superInvokeDependencies.get(method);
    if (superCallTargets != null) {
      for (DexEncodedMethod superCallTarget : superCallTargets) {
        if (Log.ENABLED) {
          Log.verbose(getClass(), "Found super invoke constraint on `%s`.", superCallTarget.method);
        }
        DexProgramClass targetClass = getProgramClassOrNull(superCallTarget.holder());
        assert targetClass != null;
        if (targetClass != null) {
          markMethodAsTargeted(
              targetClass, superCallTarget, KeepReason.invokedViaSuperFrom(method));
          markVirtualMethodAsLive(
              targetClass, superCallTarget, KeepReason.invokedViaSuperFrom(method));
        }
      }
    }
    markParameterAndReturnTypesAsLive(method);
    processAnnotations(clazz, method);
    method.parameterAnnotationsList.forEachAnnotation(
        annotation -> processAnnotation(clazz, method, annotation));
    method.registerCodeReferences(useRegistryFactory.create(appView, clazz, method, this));

    // Add all dependent members to the workqueue.
    enqueueRootItems(rootSet.getDependentItems(method));

    // Notify analyses.
    analyses.forEach(analysis -> analysis.processNewlyLiveMethod(method));
  }

  private void markReferencedTypesAsLive(DexEncodedMethod method) {
    markTypeAsLive(
        method.holder(), clazz -> graphReporter.reportClassReferencedFrom(clazz, method));
    markParameterAndReturnTypesAsLive(method);
  }


  private void markParameterAndReturnTypesAsLive(DexEncodedMethod method) {
    for (DexType parameterType : method.method.proto.parameters.values) {
      markTypeAsLive(
          parameterType, clazz -> graphReporter.reportClassReferencedFrom(clazz, method));
    }
    markTypeAsLive(
        method.method.proto.returnType,
        clazz -> graphReporter.reportClassReferencedFrom(clazz, method));
  }

  private void markClassAsInstantiatedWithReason(DexProgramClass clazz, KeepReason reason) {
    workList.enqueueMarkInstantiatedAction(clazz, null, InstantiationReason.REFLECTION, reason);
    if (clazz.hasDefaultInitializer()) {
      workList.enqueueMarkReachableDirectAction(clazz.getDefaultInitializer().method, reason);
    }
  }

  private void markClassAsInstantiatedWithCompatRule(
      DexProgramClass clazz, KeepReasonWitness witness) {
    if (clazz.isAnnotation()) {
      markTypeAsLive(clazz, witness);
    } else if (clazz.isInterface()) {
      markInterfaceAsInstantiated(clazz, witness);
    } else {
      workList.enqueueMarkInstantiatedAction(clazz, null, InstantiationReason.KEEP_RULE, witness);
      if (clazz.hasDefaultInitializer()) {
        DexEncodedMethod defaultInitializer = clazz.getDefaultInitializer();
        workList.enqueueMarkReachableDirectAction(
            defaultInitializer.method,
            graphReporter.reportCompatKeepDefaultInitializer(clazz, defaultInitializer));
      }
    }
  }

  private void markMethodAsLiveWithCompatRule(DexProgramClass clazz, DexEncodedMethod method) {
    enqueueMarkMethodLiveAction(clazz, method, graphReporter.reportCompatKeepMethod(clazz, method));
  }

  private void handleReflectiveBehavior(DexEncodedMethod method) {
    DexType originHolder = method.holder();
    Origin origin = appInfo.originFor(originHolder);
    IRCode code = method.buildIR(appView, origin);
    InstructionIterator iterator = code.instructionIterator();
    while (iterator.hasNext()) {
      Instruction instruction = iterator.next();
      handleReflectiveBehavior(method, instruction);
    }
  }

  private void handleReflectiveBehavior(DexEncodedMethod method, Instruction instruction) {
    if (!instruction.isInvokeMethod()) {
      return;
    }
    InvokeMethod invoke = instruction.asInvokeMethod();
    DexMethod invokedMethod = invoke.getInvokedMethod();
    DexItemFactory dexItemFactory = appView.dexItemFactory();
    if (invokedMethod == dexItemFactory.classMethods.newInstance) {
      handleJavaLangClassNewInstance(method, invoke);
      return;
    }
    if (invokedMethod == dexItemFactory.constructorMethods.newInstance) {
      handleJavaLangReflectConstructorNewInstance(method, invoke);
      return;
    }
    if (invokedMethod == dexItemFactory.enumMethods.valueOf) {
      handleJavaLangEnumValueOf(method, invoke);
      return;
    }
    if (invokedMethod == dexItemFactory.proxyMethods.newProxyInstance) {
      handleJavaLangReflectProxyNewProxyInstance(method, invoke);
      return;
    }
    if (dexItemFactory.serviceLoaderMethods.isLoadMethod(invokedMethod)) {
      handleServiceLoaderInvocation(method, invoke);
      return;
    }
    if (!isReflectionMethod(dexItemFactory, invokedMethod)) {
      return;
    }
    DexReference identifierItem = identifyIdentifier(invoke, appView);
    if (identifierItem == null) {
      return;
    }
    if (identifierItem.isDexType()) {
      // This is using appView.definitionFor() to avoid that we report reflectively accessed types
      // as missing.
      DexProgramClass clazz =
          asProgramClassOrNull(
              appInfo().definitionForWithoutExistenceAssert(identifierItem.asDexType()));
      if (clazz == null) {
        return;
      }
      if (clazz.isAnnotation() || clazz.isInterface()) {
        markTypeAsLive(clazz.type, KeepReason.reflectiveUseIn(method));
      } else {
        workList.enqueueMarkInstantiatedAction(
            clazz, null, InstantiationReason.REFLECTION, KeepReason.reflectiveUseIn(method));
        if (clazz.hasDefaultInitializer()) {
          DexEncodedMethod initializer = clazz.getDefaultInitializer();
          KeepReason reason = KeepReason.reflectiveUseIn(method);
          markMethodAsTargeted(clazz, initializer, reason);
          markDirectStaticOrConstructorMethodAsLive(clazz, initializer, reason);
        }
      }
    } else if (identifierItem.isDexField()) {
      DexField field = identifierItem.asDexField();
      DexProgramClass clazz = getProgramClassOrNull(field.holder);
      if (clazz == null) {
        return;
      }
      DexEncodedField encodedField = appView.definitionFor(field);
      if (encodedField == null) {
        return;
      }
      // Normally, we generate a -keepclassmembers rule for the field, such that the field is only
      // kept if it is a static field, or if the holder or one of its subtypes are instantiated.
      // However, if the invoked method is a field updater, then we always need to keep instance
      // fields since the creation of a field updater throws a NoSuchFieldException if the field
      // is not present.
      boolean keepClass =
          !encodedField.accessFlags.isStatic()
              && dexItemFactory.atomicFieldUpdaterMethods.isFieldUpdater(invokedMethod);
      if (keepClass) {
        workList.enqueueMarkInstantiatedAction(
            clazz, null, InstantiationReason.REFLECTION, KeepReason.reflectiveUseIn(method));
      }
      if (pinnedItems.add(encodedField.field)) {
        markFieldAsKept(clazz, encodedField, KeepReason.reflectiveUseIn(method));
      }
    } else {
      assert identifierItem.isDexMethod();
      DexMethod targetedMethod = identifierItem.asDexMethod();
      DexProgramClass clazz = getProgramClassOrNull(targetedMethod.holder);
      if (clazz == null) {
        return;
      }
      DexEncodedMethod encodedMethod = appView.definitionFor(targetedMethod);
      if (encodedMethod == null) {
        return;
      }
      KeepReason reason = KeepReason.reflectiveUseIn(method);
      if (encodedMethod.accessFlags.isStatic() || encodedMethod.accessFlags.isConstructor()) {
        markMethodAsTargeted(clazz, encodedMethod, reason);
        markDirectStaticOrConstructorMethodAsLive(clazz, encodedMethod, reason);
      } else {
        markVirtualMethodAsLive(clazz, encodedMethod, reason);
      }
    }
  }

  /** Handles reflective uses of {@link Class#newInstance()}. */
  private void handleJavaLangClassNewInstance(DexEncodedMethod method, InvokeMethod invoke) {
    if (!invoke.isInvokeVirtual()) {
      assert false;
      return;
    }

    DexType instantiatedType =
        ConstantValueUtils.getDexTypeRepresentedByValue(
            invoke.asInvokeVirtual().getReceiver(), appView);
    if (instantiatedType == null || !instantiatedType.isClassType()) {
      // Give up, we can't tell which class is being instantiated, or the type is not a class type.
      // The latter should not happen in practice.
      return;
    }

    DexProgramClass clazz = getProgramClassOrNull(instantiatedType);
    if (clazz == null) {
      return;
    }
    DexEncodedMethod defaultInitializer = clazz.getDefaultInitializer();
    if (defaultInitializer != null) {
      KeepReason reason = KeepReason.reflectiveUseIn(method);
      markClassAsInstantiatedWithReason(clazz, reason);
      markMethodAsTargeted(clazz, defaultInitializer, reason);
      markDirectStaticOrConstructorMethodAsLive(clazz, defaultInitializer, reason);
    }
  }

  /** Handles reflective uses of {@link java.lang.reflect.Constructor#newInstance(Object...)}. */
  private void handleJavaLangReflectConstructorNewInstance(
      DexEncodedMethod method, InvokeMethod invoke) {
    if (!invoke.isInvokeVirtual()) {
      assert false;
      return;
    }

    Value constructorValue = invoke.asInvokeVirtual().getReceiver().getAliasedValue();
    if (constructorValue.isPhi() || !constructorValue.definition.isInvokeVirtual()) {
      // Give up, we can't tell which class is being instantiated.
      return;
    }

    InvokeVirtual constructorDefinition = constructorValue.definition.asInvokeVirtual();
    if (constructorDefinition.getInvokedMethod()
        != appView.dexItemFactory().classMethods.getDeclaredConstructor) {
      // Give up, we can't tell which constructor is being invoked.
      return;
    }

    DexType instantiatedType =
        ConstantValueUtils.getDexTypeRepresentedByValue(
            constructorDefinition.getReceiver(), appView);
    if (instantiatedType == null || !instantiatedType.isClassType()) {
      // Give up, we can't tell which constructor is being invoked, or the type is not a class type.
      // The latter should not happen in practice.
      return;
    }

    DexProgramClass clazz = getProgramClassOrNull(instantiatedType);
    if (clazz == null) {
      return;
    }
    Value parametersValue = constructorDefinition.inValues().get(1);
    if (parametersValue.isPhi() || !parametersValue.definition.isNewArrayEmpty()) {
      // Give up, we can't tell which constructor is being invoked.
      return;
    }

    Value parametersSizeValue = parametersValue.definition.asNewArrayEmpty().size();
    if (parametersSizeValue.isPhi() || !parametersSizeValue.definition.isConstNumber()) {
      // Give up, we can't tell which constructor is being invoked.
      return;
    }

    DexEncodedMethod initializer = null;

    int parametersSize = parametersSizeValue.definition.asConstNumber().getIntValue();
    if (parametersSize == 0) {
      initializer = clazz.getDefaultInitializer();
    } else {
      DexType[] parameterTypes = new DexType[parametersSize];
      int missingIndices = parametersSize;
      for (Instruction user : parametersValue.uniqueUsers()) {
        if (user.isArrayPut()) {
          ArrayPut arrayPutInstruction = user.asArrayPut();
          if (arrayPutInstruction.array() != parametersValue) {
            return;
          }

          Value indexValue = arrayPutInstruction.index();
          if (indexValue.isPhi() || !indexValue.definition.isConstNumber()) {
            return;
          }
          int index = indexValue.definition.asConstNumber().getIntValue();
          if (index >= parametersSize) {
            return;
          }

          DexType type =
              ConstantValueUtils.getDexTypeRepresentedByValue(arrayPutInstruction.value(), appView);
          if (type == null) {
            return;
          }

          if (parameterTypes[index] == type) {
            continue;
          }
          if (parameterTypes[index] != null) {
            return;
          }
          parameterTypes[index] = type;
          missingIndices--;
        }
      }

      if (missingIndices == 0) {
        initializer = clazz.getInitializer(parameterTypes);
      }
    }

    if (initializer != null) {
      KeepReason reason = KeepReason.reflectiveUseIn(method);
      markClassAsInstantiatedWithReason(clazz, reason);
      markMethodAsTargeted(clazz, initializer, reason);
      markDirectStaticOrConstructorMethodAsLive(clazz, initializer, reason);
    }
  }

  /**
   * Handles reflective uses of {@link java.lang.reflect.Proxy#newProxyInstance(ClassLoader,
   * Class[], InvocationHandler)}.
   */
  private void handleJavaLangReflectProxyNewProxyInstance(
      DexEncodedMethod method, InvokeMethod invoke) {
    if (!invoke.isInvokeStatic()) {
      assert false;
      return;
    }

    Value interfacesValue = invoke.arguments().get(1);
    if (interfacesValue.isPhi() || !interfacesValue.definition.isNewArrayEmpty()) {
      // Give up, we can't tell which interfaces the proxy implements.
      return;
    }

    for (Instruction user : interfacesValue.uniqueUsers()) {
      if (!user.isArrayPut()) {
        continue;
      }

      ArrayPut arrayPut = user.asArrayPut();
      DexType type = ConstantValueUtils.getDexTypeRepresentedByValue(arrayPut.value(), appView);
      if (type == null || !type.isClassType()) {
        continue;
      }

      DexProgramClass clazz = getProgramClassOrNull(type);
      if (clazz != null && clazz.isInterface()) {
        // Add this interface to the set of pinned items to ensure that we do not merge the
        // interface into its unique subtype, if any.
        // TODO(b/145344105): This should be superseded by the unknown interface hierarchy.
        pinnedItems.add(clazz.type);
        KeepReason reason = KeepReason.reflectiveUseIn(method);
        markInterfaceAsInstantiated(clazz, graphReporter.registerClass(clazz, reason));

        // Also pin all of its virtual methods to ensure that the devirtualizer does not perform
        // illegal rewritings of invoke-interface instructions into invoke-virtual instructions.
        for (DexEncodedMethod virtualMethod : clazz.virtualMethods()) {
          pinnedItems.add(virtualMethod.method);
          markVirtualMethodAsReachable(virtualMethod.method, true, null, reason);
        }
      }
    }
  }

  private void handleJavaLangEnumValueOf(DexEncodedMethod method, InvokeMethod invoke) {
    // The use of java.lang.Enum.valueOf(java.lang.Class, java.lang.String) will indirectly
    // access the values() method of the enum class passed as the first argument. The method
    // SomeEnumClass.valueOf(java.lang.String) which is generated by javac for all enums will
    // call this method.
    if (invoke.inValues().get(0).isConstClass()) {
      DexType type = invoke.inValues().get(0).definition.asConstClass().getValue();
      DexProgramClass clazz = getProgramClassOrNull(type);
      if (clazz != null && clazz.accessFlags.isEnum()) {
        DexProgramClass holder = getProgramClassOrNull(method.holder());
        markEnumValuesAsReachable(clazz, KeepReason.invokedFrom(holder, method));
      }
    }
  }

  private void handleServiceLoaderInvocation(DexEncodedMethod method, InvokeMethod invoke) {
    if (invoke.inValues().size() == 0) {
      // Should never happen.
      return;
    }

    Value argument = invoke.inValues().get(0).getAliasedValue();
    if (!argument.isPhi() && argument.definition.isConstClass()) {
      DexType serviceType = argument.definition.asConstClass().getValue();
      if (!appView.appServices().allServiceTypes().contains(serviceType)) {
        // Should never happen.
        if (Log.ENABLED) {
          options.reporter.warning(
              new StringDiagnostic(
                  "The type `"
                      + serviceType.toSourceString()
                      + "` is being passed to the method `"
                      + invoke.getInvokedMethod().toSourceString()
                      + "`, but was not found in `META-INF/services/`.",
                  appInfo.originFor(method.holder())));
        }
        return;
      }

      handleServiceInstantiation(serviceType, KeepReason.reflectiveUseIn(method));
    } else {
      KeepReason reason = KeepReason.reflectiveUseIn(method);
      for (DexType serviceType : appView.appServices().allServiceTypes()) {
        handleServiceInstantiation(serviceType, reason);
      }
    }
  }

  private void handleServiceInstantiation(DexType serviceType, KeepReason reason) {
    instantiatedAppServices.add(serviceType);

    List<DexType> serviceImplementationTypes =
        appView.appServices().serviceImplementationsFor(serviceType);
    for (DexType serviceImplementationType : serviceImplementationTypes) {
      if (!serviceImplementationType.isClassType()) {
        // Should never happen.
        continue;
      }

      DexProgramClass serviceImplementationClass = getProgramClassOrNull(serviceImplementationType);
      if (serviceImplementationClass != null && serviceImplementationClass.isProgramClass()) {
        markClassAsInstantiatedWithReason(serviceImplementationClass, reason);
      }
    }
  }

  private static class SetWithReportedReason<T> {

    private final Set<T> items = Sets.newIdentityHashSet();
    private final Map<T, List<Action>> deferredActions = new IdentityHashMap<>();

    boolean add(T item, KeepReasonWitness witness) {
      assert witness != null;
      if (items.add(item)) {
        deferredActions.getOrDefault(item, Collections.emptyList()).forEach(Action::execute);
        return true;
      }
      return false;
    }

    boolean contains(T item) {
      return items.contains(item);
    }

    boolean registerDeferredAction(T item, Action action) {
      if (!items.contains(item)) {
        deferredActions.computeIfAbsent(item, ignore -> new ArrayList<>()).add(action);
        return true;
      }
      return false;
    }

    Set<T> getItems() {
      return Collections.unmodifiableSet(items);
    }
  }

  private class LiveMethodsSet {

    private final Set<DexEncodedMethod> items = Sets.newIdentityHashSet();

    private final BiConsumer<DexEncodedMethod, KeepReason> register;

    LiveMethodsSet(BiConsumer<DexEncodedMethod, KeepReason> register) {
      this.register = register;
    }

    boolean add(DexProgramClass clazz, DexEncodedMethod method, KeepReason reason) {
      register.accept(method, reason);
      transitionUnusedInterfaceToLive(clazz);
      return items.add(method);
    }

    boolean contains(DexEncodedMethod method) {
      return items.contains(method);
    }

    Set<DexEncodedMethod> getItems() {
      return Collections.unmodifiableSet(items);
    }
  }

  private static class SetWithReason<T> {

    private final Set<T> items = Sets.newIdentityHashSet();

    private final BiConsumer<T, KeepReason> register;

    public SetWithReason(BiConsumer<T, KeepReason> register) {
      this.register = register;
    }

    boolean add(T item, KeepReason reason) {
      register.accept(item, reason);
      return items.add(item);
    }

    boolean contains(T item) {
      return items.contains(item);
    }

    Set<T> getItems() {
      return Collections.unmodifiableSet(items);
    }
  }

  private class AnnotationReferenceMarker implements IndexedItemCollection {

    private final DexItem annotationHolder;
    private final DexItemFactory dexItemFactory;
    private final KeepReason reason;

    private AnnotationReferenceMarker(
        DexItem annotationHolder, DexItemFactory dexItemFactory, KeepReason reason) {
      this.annotationHolder = annotationHolder;
      this.dexItemFactory = dexItemFactory;
      this.reason = reason;
    }

    @Override
    public boolean addClass(DexProgramClass dexProgramClass) {
      return false;
    }

    @Override
    public boolean addField(DexField field) {
      recordTypeReference(field.holder);
      recordTypeReference(field.type);
      DexClass holder = appView.definitionFor(field.holder);
      if (holder == null) {
        return false;
      }
      DexEncodedField target = holder.lookupStaticField(field);
      if (target != null) {
        // There is no dispatch on annotations, so only keep what is directly referenced.
        if (target.field == field) {
          if (!registerFieldRead(field, DexEncodedMethod.ANNOTATION_REFERENCE)) {
            return false;
          }
          markStaticFieldAsLive(target, KeepReason.referencedInAnnotation(annotationHolder));
          // When an annotation has a field of an enum type with a default value then Java VM
          // will use the values() method on that enum class.
          if (options.isGeneratingClassFiles()
              && annotationHolder == dexItemFactory.annotationDefault) {
            DexProgramClass clazz = getProgramClassOrNull(field.type);
            if (clazz != null && clazz.accessFlags.isEnum()) {
              markEnumValuesAsReachable(clazz, KeepReason.referencedInAnnotation(annotationHolder));
            }
          }
        }
      } else {
        target = holder.lookupInstanceField(field);
        // There is no dispatch on annotations, so only keep what is directly referenced.
        if (target != null && target.field != field) {
          markInstanceFieldAsReachable(target, KeepReason.referencedInAnnotation(annotationHolder));
        }
      }
      return false;
    }

    @Override
    public boolean addMethod(DexMethod method) {
      // Record the references in case they are not program types.
      recordMethodReference(method);
      DexProgramClass holder = getProgramClassOrNull(method.holder);
      if (holder == null) {
        return false;
      }
      DexEncodedMethod target = holder.lookupDirectMethod(method);
      if (target != null) {
        // There is no dispatch on annotations, so only keep what is directly referenced.
        if (target.method == method) {
          markDirectStaticOrConstructorMethodAsLive(
              holder, target, KeepReason.referencedInAnnotation(annotationHolder));
        }
      } else {
        target = holder.lookupVirtualMethod(method);
        // There is no dispatch on annotations, so only keep what is directly referenced.
        if (target != null && target.method == method) {
          markMethodAsTargeted(holder, target, KeepReason.referencedInAnnotation(annotationHolder));
        }
      }
      return false;
    }

    @Override
    public boolean addString(DexString string) {
      return false;
    }

    @Override
    public boolean addProto(DexProto proto) {
      return false;
    }

    @Override
    public boolean addCallSite(DexCallSite callSite) {
      return false;
    }

    @Override
    public boolean addMethodHandle(DexMethodHandle methodHandle) {
      return false;
    }

    @Override
    public boolean addType(DexType type) {
      // Annotations can also contain the void type, which is not a class type, so filter it out
      // here.
      if (type != dexItemFactory.voidType) {
        markTypeAsLive(type, reason);
      }
      return false;
    }
  }

}