blob: 065841893f4339701766adcc7bc39bd871d72cef [file] [log] [blame]
// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.shaking;
import static com.android.tools.r8.graph.GraphLense.rewriteReferenceKeys;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
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.DexEncodedMethod;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexReference;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.DexTypeList;
import com.android.tools.r8.graph.DirectMappedDexApplication;
import com.android.tools.r8.graph.GraphLense;
import com.android.tools.r8.graph.PresortedComparable;
import com.android.tools.r8.ir.code.Invoke.Type;
import com.android.tools.r8.utils.CollectionUtils;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ImmutableSortedSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.objects.Object2BooleanMap;
import it.unimi.dsi.fastutil.objects.Reference2IntMap;
import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.IdentityHashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.stream.Collectors;
/** Encapsulates liveness and reachability information for an application. */
public class AppInfoWithLiveness extends AppInfoWithSubtyping {
/**
* Set of types that are mentioned in the program. We at least need an empty abstract classitem
* for these.
*/
public final SortedSet<DexType> liveTypes;
/** Set of annotation types that are instantiated. */
final SortedSet<DexType> instantiatedAnnotationTypes;
/**
* Set of service types (from META-INF/services/) that may have been instantiated reflectively via
* ServiceLoader.load() or ServiceLoader.loadInstalled().
*/
public final SortedSet<DexType> instantiatedAppServices;
/** Set of types that are actually instantiated. These cannot be abstract. */
final SortedSet<DexType> instantiatedTypes;
/** Cache for {@link #isInstantiatedDirectlyOrIndirectly(DexType)}. */
private final IdentityHashMap<DexType, Boolean> indirectlyInstantiatedTypes =
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 such a method is not live (i.e. not
* contained in {@link #liveMethods}, it may be marked as abstract and its implementation may be
* removed.
*/
final SortedSet<DexMethod> targetedMethods;
/**
* Set of program methods that are used as the bootstrap method for an invoke-dynamic instruction.
*/
public final SortedSet<DexMethod> bootstrapMethods;
/** Set of methods that are the immediate target of an invoke-dynamic. */
public final SortedSet<DexMethod> methodsTargetedByInvokeDynamic;
/** Set of virtual methods that are the immediate target of an invoke-direct. */
final SortedSet<DexMethod> virtualMethodsTargetedByInvokeDirect;
/**
* Set of methods that belong to live classes and can be reached by invokes. These need to be
* kept.
*/
final SortedSet<DexMethod> liveMethods;
/**
* Set of all fields which may be touched by a get operation. This is actual field definitions.
* The set does not include kept fields nor library fields, since these are read by definition.
*/
private final SortedSet<DexField> fieldsRead;
/**
* Set of all fields which may be touched by a put operation. This is actual field definitions.
* The set does not include kept fields nor library fields, since these are written by definition.
*/
private SortedSet<DexField> fieldsWritten;
/**
* Set of all static fields that are only written inside the <clinit>() method of their enclosing
* class.
*/
private SortedSet<DexField> staticFieldsWrittenOnlyInEnclosingStaticInitializer;
/** Set of all field ids used in instance field reads, along with access context. */
public final SortedMap<DexField, Set<DexEncodedMethod>> instanceFieldReads;
/** Set of all field ids used in instance field writes, along with access context. */
public final SortedMap<DexField, Set<DexEncodedMethod>> instanceFieldWrites;
/** Set of all field ids used in static field reads, along with access context. */
public final SortedMap<DexField, Set<DexEncodedMethod>> staticFieldReads;
/** Set of all field ids used in static field writes, along with access context. */
public final SortedMap<DexField, Set<DexEncodedMethod>> staticFieldWrites;
/** Set of all methods referenced in virtual invokes, along with calling context. */
public final SortedMap<DexMethod, Set<DexEncodedMethod>> virtualInvokes;
/** Set of all methods referenced in interface invokes, along with calling context. */
public final SortedMap<DexMethod, Set<DexEncodedMethod>> interfaceInvokes;
/** Set of all methods referenced in super invokes, along with calling context. */
public final SortedMap<DexMethod, Set<DexEncodedMethod>> superInvokes;
/** Set of all methods referenced in direct invokes, along with calling context. */
public final SortedMap<DexMethod, Set<DexEncodedMethod>> directInvokes;
/** Set of all methods referenced in static invokes, along with calling context. */
public final SortedMap<DexMethod, Set<DexEncodedMethod>> staticInvokes;
/**
* Set of live call sites in the code. Note that if desugaring has taken place call site objects
* will have been removed from the code.
*/
public final Set<DexCallSite> callSites;
/**
* Set of method signatures used in invoke-super instructions that either cannot be resolved or
* resolve to a private method (leading to an IllegalAccessError).
*/
public final SortedSet<DexMethod> brokenSuperInvokes;
/** Set of all items that have to be kept independent of whether they are used. */
final Set<DexReference> pinnedItems;
/** All items with assumemayhavesideeffects rule. */
public final Map<DexReference, ProguardMemberRule> mayHaveSideEffects;
/** All items with assumenosideeffects rule. */
public final Map<DexReference, ProguardMemberRule> noSideEffects;
/** All items with assumevalues rule. */
public final Map<DexReference, ProguardMemberRule> assumedValues;
/** All methods that should be inlined if possible due to a configuration directive. */
public final Set<DexMethod> alwaysInline;
/** All methods that *must* be inlined due to a configuration directive (testing only). */
public final Set<DexMethod> forceInline;
/** All methods that *must* never be inlined due to a configuration directive (testing only). */
public final Set<DexMethod> neverInline;
/** All methods that may not have any parameters with a constant value removed. */
public final Set<DexMethod> keepConstantArguments;
/** All methods that may not have any unused arguments removed. */
public final Set<DexMethod> keepUnusedArguments;
/** All types that *must* never be inlined due to a configuration directive (testing only). */
public final Set<DexType> neverClassInline;
/** All types that *must* never be merged due to a configuration directive (testing only). */
public final Set<DexType> neverMerge;
/**
* All methods and fields whose value *must* never be propagated due to a configuration directive.
* (testing only).
*/
private final Set<DexReference> neverPropagateValue;
/**
* All items with -identifiernamestring rule. Bound boolean value indicates the rule is explicitly
* specified by users (<code>true</code>) or not, i.e., implicitly added by R8 (<code>false</code>
* ).
*/
public final Object2BooleanMap<DexReference> identifierNameStrings;
/** A set of types that have been removed by the {@link TreePruner}. */
final Set<DexType> prunedTypes;
/** A map from switchmap class types to their corresponding switchmaps. */
final Map<DexField, Int2ReferenceMap<DexField>> switchMaps;
/** A map from enum types to their ordinal values. */
final Map<DexType, Reference2IntMap<DexField>> ordinalsMaps;
final ImmutableSortedSet<DexType> instantiatedLambdas;
// TODO(zerny): Clean up the constructors so we have just one.
private AppInfoWithLiveness(
DexApplication application,
SortedSet<DexType> liveTypes,
SortedSet<DexType> instantiatedAnnotationTypes,
SortedSet<DexType> instantiatedAppServices,
SortedSet<DexType> instantiatedTypes,
SortedSet<DexMethod> targetedMethods,
SortedSet<DexMethod> bootstrapMethods,
SortedSet<DexMethod> methodsTargetedByInvokeDynamic,
SortedSet<DexMethod> virtualMethodsTargetedByInvokeDirect,
SortedSet<DexMethod> liveMethods,
SortedSet<DexField> fieldsRead,
SortedSet<DexField> fieldsWritten,
SortedSet<DexField> staticFieldsWrittenOnlyInEnclosingStaticInitializer,
SortedMap<DexField, Set<DexEncodedMethod>> instanceFieldReads,
SortedMap<DexField, Set<DexEncodedMethod>> instanceFieldWrites,
SortedMap<DexField, Set<DexEncodedMethod>> staticFieldReads,
SortedMap<DexField, Set<DexEncodedMethod>> staticFieldWrites,
SortedMap<DexMethod, Set<DexEncodedMethod>> virtualInvokes,
SortedMap<DexMethod, Set<DexEncodedMethod>> interfaceInvokes,
SortedMap<DexMethod, Set<DexEncodedMethod>> superInvokes,
SortedMap<DexMethod, Set<DexEncodedMethod>> directInvokes,
SortedMap<DexMethod, Set<DexEncodedMethod>> staticInvokes,
Set<DexCallSite> callSites,
SortedSet<DexMethod> brokenSuperInvokes,
Set<DexReference> pinnedItems,
Map<DexReference, ProguardMemberRule> mayHaveSideEffects,
Map<DexReference, ProguardMemberRule> noSideEffects,
Map<DexReference, ProguardMemberRule> assumedValues,
Set<DexMethod> alwaysInline,
Set<DexMethod> forceInline,
Set<DexMethod> neverInline,
Set<DexMethod> keepConstantArguments,
Set<DexMethod> keepUnusedArguments,
Set<DexType> neverClassInline,
Set<DexType> neverMerge,
Set<DexReference> neverPropagateValue,
Object2BooleanMap<DexReference> identifierNameStrings,
Set<DexType> prunedTypes,
Map<DexField, Int2ReferenceMap<DexField>> switchMaps,
Map<DexType, Reference2IntMap<DexField>> ordinalsMaps,
ImmutableSortedSet<DexType> instantiatedLambdas) {
super(application);
this.liveTypes = liveTypes;
this.instantiatedAnnotationTypes = instantiatedAnnotationTypes;
this.instantiatedAppServices = instantiatedAppServices;
this.instantiatedTypes = instantiatedTypes;
this.targetedMethods = targetedMethods;
this.bootstrapMethods = bootstrapMethods;
this.methodsTargetedByInvokeDynamic = methodsTargetedByInvokeDynamic;
this.virtualMethodsTargetedByInvokeDirect = virtualMethodsTargetedByInvokeDirect;
this.liveMethods = liveMethods;
this.instanceFieldReads = instanceFieldReads;
this.instanceFieldWrites = instanceFieldWrites;
this.staticFieldReads = staticFieldReads;
this.staticFieldWrites = staticFieldWrites;
this.fieldsRead = fieldsRead;
this.fieldsWritten = fieldsWritten;
this.staticFieldsWrittenOnlyInEnclosingStaticInitializer =
staticFieldsWrittenOnlyInEnclosingStaticInitializer;
this.pinnedItems = pinnedItems;
this.mayHaveSideEffects = mayHaveSideEffects;
this.noSideEffects = noSideEffects;
this.assumedValues = assumedValues;
this.virtualInvokes = virtualInvokes;
this.interfaceInvokes = interfaceInvokes;
this.superInvokes = superInvokes;
this.directInvokes = directInvokes;
this.staticInvokes = staticInvokes;
this.callSites = callSites;
this.brokenSuperInvokes = brokenSuperInvokes;
this.alwaysInline = alwaysInline;
this.forceInline = forceInline;
this.neverInline = neverInline;
this.keepConstantArguments = keepConstantArguments;
this.keepUnusedArguments = keepUnusedArguments;
this.neverClassInline = neverClassInline;
this.neverMerge = neverMerge;
this.neverPropagateValue = neverPropagateValue;
this.identifierNameStrings = identifierNameStrings;
this.prunedTypes = prunedTypes;
this.switchMaps = switchMaps;
this.ordinalsMaps = ordinalsMaps;
this.instantiatedLambdas = instantiatedLambdas;
assert Sets.intersection(instanceFieldReads.keySet(), staticFieldReads.keySet()).isEmpty();
assert Sets.intersection(instanceFieldWrites.keySet(), staticFieldWrites.keySet()).isEmpty();
}
public AppInfoWithLiveness(
AppInfoWithSubtyping appInfoWithSubtyping,
SortedSet<DexType> liveTypes,
SortedSet<DexType> instantiatedAnnotationTypes,
SortedSet<DexType> instantiatedAppServices,
SortedSet<DexType> instantiatedTypes,
SortedSet<DexMethod> targetedMethods,
SortedSet<DexMethod> bootstrapMethods,
SortedSet<DexMethod> methodsTargetedByInvokeDynamic,
SortedSet<DexMethod> virtualMethodsTargetedByInvokeDirect,
SortedSet<DexMethod> liveMethods,
SortedSet<DexField> fieldsRead,
SortedSet<DexField> fieldsWritten,
SortedSet<DexField> staticFieldsWrittenOnlyInEnclosingStaticInitializer,
SortedMap<DexField, Set<DexEncodedMethod>> instanceFieldReads,
SortedMap<DexField, Set<DexEncodedMethod>> instanceFieldWrites,
SortedMap<DexField, Set<DexEncodedMethod>> staticFieldReads,
SortedMap<DexField, Set<DexEncodedMethod>> staticFieldWrites,
SortedMap<DexMethod, Set<DexEncodedMethod>> virtualInvokes,
SortedMap<DexMethod, Set<DexEncodedMethod>> interfaceInvokes,
SortedMap<DexMethod, Set<DexEncodedMethod>> superInvokes,
SortedMap<DexMethod, Set<DexEncodedMethod>> directInvokes,
SortedMap<DexMethod, Set<DexEncodedMethod>> staticInvokes,
Set<DexCallSite> callSites,
SortedSet<DexMethod> brokenSuperInvokes,
Set<DexReference> pinnedItems,
Map<DexReference, ProguardMemberRule> mayHaveSideEffects,
Map<DexReference, ProguardMemberRule> noSideEffects,
Map<DexReference, ProguardMemberRule> assumedValues,
Set<DexMethod> alwaysInline,
Set<DexMethod> forceInline,
Set<DexMethod> neverInline,
Set<DexMethod> keepConstantArguments,
Set<DexMethod> keepUnusedArguments,
Set<DexType> neverClassInline,
Set<DexType> neverMerge,
Set<DexReference> neverPropagateValue,
Object2BooleanMap<DexReference> identifierNameStrings,
Set<DexType> prunedTypes,
Map<DexField, Int2ReferenceMap<DexField>> switchMaps,
Map<DexType, Reference2IntMap<DexField>> ordinalsMaps,
ImmutableSortedSet<DexType> instantiatedLambdas) {
super(appInfoWithSubtyping);
this.liveTypes = liveTypes;
this.instantiatedAnnotationTypes = instantiatedAnnotationTypes;
this.instantiatedAppServices = instantiatedAppServices;
this.instantiatedTypes = instantiatedTypes;
this.targetedMethods = targetedMethods;
this.bootstrapMethods = bootstrapMethods;
this.methodsTargetedByInvokeDynamic = methodsTargetedByInvokeDynamic;
this.virtualMethodsTargetedByInvokeDirect = virtualMethodsTargetedByInvokeDirect;
this.liveMethods = liveMethods;
this.instanceFieldReads = instanceFieldReads;
this.instanceFieldWrites = instanceFieldWrites;
this.staticFieldReads = staticFieldReads;
this.staticFieldWrites = staticFieldWrites;
this.fieldsRead = fieldsRead;
this.fieldsWritten = fieldsWritten;
this.staticFieldsWrittenOnlyInEnclosingStaticInitializer =
staticFieldsWrittenOnlyInEnclosingStaticInitializer;
this.pinnedItems = pinnedItems;
this.mayHaveSideEffects = mayHaveSideEffects;
this.noSideEffects = noSideEffects;
this.assumedValues = assumedValues;
this.virtualInvokes = virtualInvokes;
this.interfaceInvokes = interfaceInvokes;
this.superInvokes = superInvokes;
this.directInvokes = directInvokes;
this.staticInvokes = staticInvokes;
this.callSites = callSites;
this.brokenSuperInvokes = brokenSuperInvokes;
this.alwaysInline = alwaysInline;
this.forceInline = forceInline;
this.neverInline = neverInline;
this.keepConstantArguments = keepConstantArguments;
this.keepUnusedArguments = keepUnusedArguments;
this.neverClassInline = neverClassInline;
this.neverMerge = neverMerge;
this.neverPropagateValue = neverPropagateValue;
this.identifierNameStrings = identifierNameStrings;
this.prunedTypes = prunedTypes;
this.switchMaps = switchMaps;
this.ordinalsMaps = ordinalsMaps;
this.instantiatedLambdas = instantiatedLambdas;
assert Sets.intersection(instanceFieldReads.keySet(), staticFieldReads.keySet()).isEmpty();
assert Sets.intersection(instanceFieldWrites.keySet(), staticFieldWrites.keySet()).isEmpty();
}
private AppInfoWithLiveness(AppInfoWithLiveness previous) {
this(previous, previous.app(), null);
}
private AppInfoWithLiveness(
AppInfoWithLiveness previous,
DexApplication application,
Collection<DexType> removedClasses) {
this(
application,
previous.liveTypes,
previous.instantiatedAnnotationTypes,
previous.instantiatedAppServices,
previous.instantiatedTypes,
previous.targetedMethods,
previous.bootstrapMethods,
previous.methodsTargetedByInvokeDynamic,
previous.virtualMethodsTargetedByInvokeDirect,
previous.liveMethods,
previous.fieldsRead,
previous.fieldsWritten,
previous.staticFieldsWrittenOnlyInEnclosingStaticInitializer,
previous.instanceFieldReads,
previous.instanceFieldWrites,
previous.staticFieldReads,
previous.staticFieldWrites,
previous.virtualInvokes,
previous.interfaceInvokes,
previous.superInvokes,
previous.directInvokes,
previous.staticInvokes,
previous.callSites,
previous.brokenSuperInvokes,
previous.pinnedItems,
previous.mayHaveSideEffects,
previous.noSideEffects,
previous.assumedValues,
previous.alwaysInline,
previous.forceInline,
previous.neverInline,
previous.keepConstantArguments,
previous.keepUnusedArguments,
previous.neverClassInline,
previous.neverMerge,
previous.neverPropagateValue,
previous.identifierNameStrings,
removedClasses == null
? previous.prunedTypes
: CollectionUtils.mergeSets(previous.prunedTypes, removedClasses),
previous.switchMaps,
previous.ordinalsMaps,
previous.instantiatedLambdas);
copyMetadataFromPrevious(previous);
assert removedClasses == null || assertNoItemRemoved(previous.pinnedItems, removedClasses);
assert Sets.intersection(instanceFieldReads.keySet(), staticFieldReads.keySet()).isEmpty();
assert Sets.intersection(instanceFieldWrites.keySet(), staticFieldWrites.keySet()).isEmpty();
}
private AppInfoWithLiveness(
AppInfoWithLiveness previous, DirectMappedDexApplication application, GraphLense lense) {
super(application);
this.liveTypes = rewriteItems(previous.liveTypes, lense::lookupType);
this.instantiatedAnnotationTypes =
rewriteItems(previous.instantiatedAnnotationTypes, lense::lookupType);
this.instantiatedAppServices =
rewriteItems(previous.instantiatedAppServices, lense::lookupType);
this.instantiatedTypes = rewriteItems(previous.instantiatedTypes, lense::lookupType);
this.instantiatedLambdas = rewriteItems(previous.instantiatedLambdas, lense::lookupType);
this.targetedMethods = lense.rewriteMethodsConservatively(previous.targetedMethods);
this.bootstrapMethods = lense.rewriteMethodsConservatively(previous.bootstrapMethods);
this.methodsTargetedByInvokeDynamic =
lense.rewriteMethodsConservatively(previous.methodsTargetedByInvokeDynamic);
this.virtualMethodsTargetedByInvokeDirect =
lense.rewriteMethodsConservatively(previous.virtualMethodsTargetedByInvokeDirect);
this.liveMethods = lense.rewriteMethodsConservatively(previous.liveMethods);
this.instanceFieldReads =
rewriteKeysWhileMergingValues(previous.instanceFieldReads, lense::lookupField);
this.instanceFieldWrites =
rewriteKeysWhileMergingValues(previous.instanceFieldWrites, lense::lookupField);
this.staticFieldReads =
rewriteKeysWhileMergingValues(previous.staticFieldReads, lense::lookupField);
this.staticFieldWrites =
rewriteKeysWhileMergingValues(previous.staticFieldWrites, lense::lookupField);
this.fieldsRead = rewriteItems(previous.fieldsRead, lense::lookupField);
this.fieldsWritten = rewriteItems(previous.fieldsWritten, lense::lookupField);
this.staticFieldsWrittenOnlyInEnclosingStaticInitializer =
rewriteItems(
previous.staticFieldsWrittenOnlyInEnclosingStaticInitializer, lense::lookupField);
this.pinnedItems = lense.rewriteReferencesConservatively(previous.pinnedItems);
this.virtualInvokes =
rewriteKeysConservativelyWhileMergingValues(
previous.virtualInvokes, lense::lookupMethodInAllContexts);
this.interfaceInvokes =
rewriteKeysConservativelyWhileMergingValues(
previous.interfaceInvokes, lense::lookupMethodInAllContexts);
this.superInvokes =
rewriteKeysConservativelyWhileMergingValues(
previous.superInvokes, lense::lookupMethodInAllContexts);
this.directInvokes =
rewriteKeysConservativelyWhileMergingValues(
previous.directInvokes, lense::lookupMethodInAllContexts);
this.staticInvokes =
rewriteKeysConservativelyWhileMergingValues(
previous.staticInvokes, lense::lookupMethodInAllContexts);
// TODO(sgjesse): Rewrite call sites as well? Right now they are only used by minification
// after second tree shaking.
this.callSites = previous.callSites;
this.brokenSuperInvokes = lense.rewriteMethodsConservatively(previous.brokenSuperInvokes);
// Don't rewrite pruned types - the removed types are identified by their original name.
this.prunedTypes = previous.prunedTypes;
this.mayHaveSideEffects =
rewriteReferenceKeys(previous.mayHaveSideEffects, lense::lookupReference);
this.noSideEffects = rewriteReferenceKeys(previous.noSideEffects, lense::lookupReference);
this.assumedValues = rewriteReferenceKeys(previous.assumedValues, lense::lookupReference);
assert lense.assertDefinitionsNotModified(
previous.alwaysInline.stream()
.map(this::definitionFor)
.filter(Objects::nonNull)
.collect(Collectors.toList()));
this.alwaysInline = lense.rewriteMethodsWithRenamedSignature(previous.alwaysInline);
this.forceInline = lense.rewriteMethodsWithRenamedSignature(previous.forceInline);
this.neverInline = lense.rewriteMethodsWithRenamedSignature(previous.neverInline);
this.keepConstantArguments =
lense.rewriteMethodsWithRenamedSignature(previous.keepConstantArguments);
this.keepUnusedArguments =
lense.rewriteMethodsWithRenamedSignature(previous.keepUnusedArguments);
assert lense.assertDefinitionsNotModified(
previous.neverMerge.stream()
.map(this::definitionFor)
.filter(Objects::nonNull)
.collect(Collectors.toList()));
this.neverClassInline = rewriteItems(previous.neverClassInline, lense::lookupType);
this.neverMerge = rewriteItems(previous.neverMerge, lense::lookupType);
this.neverPropagateValue = lense.rewriteReferencesConservatively(previous.neverPropagateValue);
this.identifierNameStrings =
lense.rewriteReferencesConservatively(previous.identifierNameStrings);
// Switchmap classes should never be affected by renaming.
assert lense.assertDefinitionsNotModified(
previous.switchMaps.keySet().stream()
.map(this::definitionFor)
.filter(Objects::nonNull)
.collect(Collectors.toList()));
this.switchMaps = rewriteReferenceKeys(previous.switchMaps, lense::lookupField);
this.ordinalsMaps = rewriteReferenceKeys(previous.ordinalsMaps, lense::lookupType);
// Sanity check sets after rewriting.
assert Sets.intersection(instanceFieldReads.keySet(), staticFieldReads.keySet()).isEmpty();
assert Sets.intersection(instanceFieldWrites.keySet(), staticFieldWrites.keySet()).isEmpty();
}
public AppInfoWithLiveness(
AppInfoWithLiveness previous,
Map<DexField, Int2ReferenceMap<DexField>> switchMaps,
Map<DexType, Reference2IntMap<DexField>> ordinalsMaps) {
super(previous);
this.liveTypes = previous.liveTypes;
this.instantiatedAnnotationTypes = previous.instantiatedAnnotationTypes;
this.instantiatedAppServices = previous.instantiatedAppServices;
this.instantiatedTypes = previous.instantiatedTypes;
this.instantiatedLambdas = previous.instantiatedLambdas;
this.targetedMethods = previous.targetedMethods;
this.bootstrapMethods = previous.bootstrapMethods;
this.methodsTargetedByInvokeDynamic = previous.methodsTargetedByInvokeDynamic;
this.virtualMethodsTargetedByInvokeDirect = previous.virtualMethodsTargetedByInvokeDirect;
this.liveMethods = previous.liveMethods;
this.instanceFieldReads = previous.instanceFieldReads;
this.instanceFieldWrites = previous.instanceFieldWrites;
this.staticFieldReads = previous.staticFieldReads;
this.staticFieldWrites = previous.staticFieldWrites;
this.fieldsRead = previous.fieldsRead;
this.fieldsWritten = previous.fieldsWritten;
this.staticFieldsWrittenOnlyInEnclosingStaticInitializer =
previous.staticFieldsWrittenOnlyInEnclosingStaticInitializer;
this.pinnedItems = previous.pinnedItems;
this.mayHaveSideEffects = previous.mayHaveSideEffects;
this.noSideEffects = previous.noSideEffects;
this.assumedValues = previous.assumedValues;
this.virtualInvokes = previous.virtualInvokes;
this.interfaceInvokes = previous.interfaceInvokes;
this.superInvokes = previous.superInvokes;
this.directInvokes = previous.directInvokes;
this.staticInvokes = previous.staticInvokes;
this.callSites = previous.callSites;
this.brokenSuperInvokes = previous.brokenSuperInvokes;
this.alwaysInline = previous.alwaysInline;
this.forceInline = previous.forceInline;
this.neverInline = previous.neverInline;
this.keepConstantArguments = previous.keepConstantArguments;
this.keepUnusedArguments = previous.keepUnusedArguments;
this.neverClassInline = previous.neverClassInline;
this.neverMerge = previous.neverMerge;
this.neverPropagateValue = previous.neverPropagateValue;
this.identifierNameStrings = previous.identifierNameStrings;
this.prunedTypes = previous.prunedTypes;
this.switchMaps = switchMaps;
this.ordinalsMaps = ordinalsMaps;
previous.markObsolete();
}
public Collection<DexClass> computeReachableInterfaces(Set<DexCallSite> desugaredCallSites) {
Set<DexClass> interfaces = Sets.newIdentityHashSet();
Set<DexType> seen = Sets.newIdentityHashSet();
Deque<DexType> worklist = new ArrayDeque<>();
for (DexProgramClass clazz : classes()) {
worklist.add(clazz.type);
}
// TODO(b/129458850): Remove this once desugared classes are made part of the program classes.
for (DexCallSite callSite : desugaredCallSites) {
for (DexEncodedMethod method : lookupLambdaImplementedMethods(callSite)) {
worklist.add(method.method.holder);
}
}
for (DexCallSite callSite : callSites) {
for (DexEncodedMethod method : lookupLambdaImplementedMethods(callSite)) {
worklist.add(method.method.holder);
}
}
while (!worklist.isEmpty()) {
DexType type = worklist.pop();
if (!seen.add(type)) {
continue;
}
DexClass definition = definitionFor(type);
if (definition == null) {
continue;
}
if (definition.isInterface()) {
interfaces.add(definition);
}
if (definition.superType != null) {
worklist.add(definition.superType);
}
Collections.addAll(worklist, definition.interfaces.values);
}
return interfaces;
}
public AppInfoWithLiveness withoutStaticFieldsWrites(Set<DexField> noLongerWrittenFields) {
assert checkIfObsolete();
if (noLongerWrittenFields.isEmpty()) {
return this;
}
AppInfoWithLiveness result = new AppInfoWithLiveness(this);
Predicate<DexField> isFieldWritten = field -> !noLongerWrittenFields.contains(field);
result.fieldsWritten = filter(fieldsWritten, isFieldWritten);
result.staticFieldsWrittenOnlyInEnclosingStaticInitializer =
filter(staticFieldsWrittenOnlyInEnclosingStaticInitializer, isFieldWritten);
return result;
}
private <T extends PresortedComparable<T>> SortedSet<T> filter(
Set<T> items, Predicate<T> predicate) {
return ImmutableSortedSet.copyOf(
PresortedComparable::slowCompareTo,
items.stream().filter(predicate).collect(Collectors.toList()));
}
public Reference2IntMap<DexField> getOrdinalsMapFor(DexType enumClass) {
assert checkIfObsolete();
return ordinalsMaps.get(enumClass);
}
public Int2ReferenceMap<DexField> getSwitchMapFor(DexField field) {
assert checkIfObsolete();
return switchMaps.get(field);
}
private boolean assertNoItemRemoved(Collection<DexReference> items, Collection<DexType> types) {
Set<DexType> typeSet = ImmutableSet.copyOf(types);
for (DexReference item : items) {
DexType typeToCheck;
if (item.isDexType()) {
typeToCheck = item.asDexType();
} else if (item.isDexMethod()) {
typeToCheck = item.asDexMethod().holder;
} else {
assert item.isDexField();
typeToCheck = item.asDexField().holder;
}
assert !typeSet.contains(typeToCheck);
}
return true;
}
public boolean isInstantiatedDirectly(DexType type) {
assert checkIfObsolete();
assert type.isClassType();
return type.isD8R8SynthesizedClassType()
|| instantiatedTypes.contains(type)
|| instantiatedLambdas.contains(type)
|| instantiatedAnnotationTypes.contains(type);
}
public boolean isInstantiatedIndirectly(DexType type) {
assert checkIfObsolete();
assert type.isClassType();
synchronized (indirectlyInstantiatedTypes) {
if (indirectlyInstantiatedTypes.containsKey(type)) {
return indirectlyInstantiatedTypes.get(type).booleanValue();
}
for (DexType directSubtype : allImmediateSubtypes(type)) {
if (isInstantiatedDirectlyOrIndirectly(directSubtype)) {
indirectlyInstantiatedTypes.put(type, Boolean.TRUE);
return true;
}
}
indirectlyInstantiatedTypes.put(type, Boolean.FALSE);
return false;
}
}
public boolean isInstantiatedDirectlyOrIndirectly(DexType type) {
assert checkIfObsolete();
assert type.isClassType();
return isInstantiatedDirectly(type) || isInstantiatedIndirectly(type);
}
public boolean isFieldRead(DexField field) {
assert checkIfObsolete();
return fieldsRead.contains(field)
|| isPinned(field)
// Fields in the class that is synthesized by D8/R8 would be used soon.
|| field.holder.isD8R8SynthesizedClassType()
// For library classes we don't know whether a field is read.
|| isLibraryOrClasspathField(field);
}
public boolean isFieldWritten(DexField field) {
assert checkIfObsolete();
return fieldsWritten.contains(field)
|| isPinned(field)
// Fields in the class that is synthesized by D8/R8 would be used soon.
|| field.holder.isD8R8SynthesizedClassType()
// For library classes we don't know whether a field is rewritten.
|| isLibraryOrClasspathField(field);
}
public boolean isStaticFieldWrittenOnlyInEnclosingStaticInitializer(DexField field) {
assert checkIfObsolete();
assert isFieldWritten(field);
return staticFieldsWrittenOnlyInEnclosingStaticInitializer.contains(field);
}
public boolean mayPropagateValueFor(DexReference reference) {
assert checkIfObsolete();
return !neverPropagateValue.contains(reference);
}
private boolean isLibraryOrClasspathField(DexField field) {
DexClass holder = definitionFor(field.holder);
return holder == null || holder.isLibraryClass() || holder.isClasspathClass();
}
private static <T extends PresortedComparable<T>> ImmutableSortedSet<T> rewriteItems(
Set<T> original, Function<T, T> rewrite) {
ImmutableSortedSet.Builder<T> builder =
new ImmutableSortedSet.Builder<>(PresortedComparable::slowCompare);
for (T item : original) {
builder.add(rewrite.apply(item));
}
return builder.build();
}
private static <T extends PresortedComparable<T>, S>
SortedMap<T, Set<S>> rewriteKeysWhileMergingValues(
Map<T, Set<S>> original, Function<T, T> rewrite) {
SortedMap<T, Set<S>> result = new TreeMap<>(PresortedComparable::slowCompare);
for (T item : original.keySet()) {
T rewrittenKey = rewrite.apply(item);
result
.computeIfAbsent(rewrittenKey, k -> Sets.newIdentityHashSet())
.addAll(original.get(item));
}
return Collections.unmodifiableSortedMap(result);
}
private static <T extends PresortedComparable<T>, S>
SortedMap<T, Set<S>> rewriteKeysConservativelyWhileMergingValues(
Map<T, Set<S>> original, Function<T, Set<T>> rewrite) {
SortedMap<T, Set<S>> result = new TreeMap<>(PresortedComparable::slowCompare);
for (T item : original.keySet()) {
Set<T> rewrittenKeys = rewrite.apply(item);
for (T rewrittenKey : rewrittenKeys) {
result
.computeIfAbsent(rewrittenKey, k -> Sets.newIdentityHashSet())
.addAll(original.get(item));
}
}
return Collections.unmodifiableSortedMap(result);
}
@Override
protected boolean hasAnyInstantiatedLambdas(DexType type) {
assert checkIfObsolete();
return instantiatedLambdas.contains(type);
}
@Override
public boolean hasLiveness() {
assert checkIfObsolete();
return true;
}
@Override
public AppInfoWithLiveness withLiveness() {
assert checkIfObsolete();
return this;
}
public boolean isPinned(DexReference reference) {
assert checkIfObsolete();
return pinnedItems.contains(reference);
}
public Iterable<DexReference> getPinnedItems() {
assert checkIfObsolete();
return pinnedItems;
}
/**
* Returns a copy of this AppInfoWithLiveness where the set of classes is pruned using the given
* DexApplication object.
*/
public AppInfoWithLiveness prunedCopyFrom(
DexApplication application, Collection<DexType> removedClasses) {
assert checkIfObsolete();
return new AppInfoWithLiveness(this, application, removedClasses);
}
public AppInfoWithLiveness rewrittenWithLense(
DirectMappedDexApplication application, GraphLense lense) {
assert checkIfObsolete();
return new AppInfoWithLiveness(this, application, lense);
}
/**
* Returns true if the given type was part of the original program but has been removed during
* tree shaking.
*/
public boolean wasPruned(DexType type) {
assert checkIfObsolete();
return prunedTypes.contains(type);
}
public Set<DexType> getPrunedTypes() {
assert checkIfObsolete();
return prunedTypes;
}
public DexEncodedMethod lookup(Type type, DexMethod target, DexType invocationContext) {
assert checkIfObsolete();
DexType holder = target.holder;
if (!holder.isClassType()) {
return null;
}
switch (type) {
case VIRTUAL:
return lookupSingleVirtualTarget(target);
case INTERFACE:
return lookupSingleInterfaceTarget(target);
case DIRECT:
return lookupDirectTarget(target);
case STATIC:
return lookupStaticTarget(target);
case SUPER:
return lookupSuperTarget(target, invocationContext);
default:
return null;
}
}
/** For mapping invoke virtual instruction to single target method. */
public DexEncodedMethod lookupSingleVirtualTarget(DexMethod method) {
assert checkIfObsolete();
return lookupSingleVirtualTarget(method, method.holder);
}
public DexEncodedMethod lookupSingleVirtualTarget(DexMethod method, DexType refinedReceiverType) {
assert checkIfObsolete();
// This implements the logic from
// https://docs.oracle.com/javase/specs/jvms/se9/html/jvms-6.html#jvms-6.5.invokevirtual
assert method != null;
assert isSubtype(refinedReceiverType, method.holder);
if (method.holder.isArrayType()) {
// For javac output this will only be clone(), but in general the methods from Object can
// be invoked with an array type holder.
return null;
}
DexClass holder = definitionFor(method.holder);
if (holder == null || holder.isNotProgramClass() || holder.isInterface()) {
return null;
}
boolean refinedReceiverIsStrictSubType = refinedReceiverType != method.holder;
DexClass refinedHolder =
refinedReceiverIsStrictSubType ? definitionFor(refinedReceiverType) : holder;
assert refinedHolder != null;
assert refinedHolder.isProgramClass();
if (method.isSingleVirtualMethodCached(refinedReceiverType)) {
return method.getSingleVirtualMethodCache(refinedReceiverType);
}
// For kept types we cannot ensure a single target.
if (pinnedItems.contains(method.holder)) {
method.setSingleVirtualMethodCache(refinedReceiverType, null);
return null;
}
// First get the target for the holder type.
ResolutionResult topMethod = resolveMethod(method.holder, method);
// We might hit none or multiple targets. Both make this fail at runtime.
if (!topMethod.hasSingleTarget() || !topMethod.asSingleTarget().isVirtualMethod()) {
method.setSingleVirtualMethodCache(refinedReceiverType, null);
return null;
}
// Now, resolve the target with the refined receiver type.
if (refinedReceiverIsStrictSubType) {
topMethod = resolveMethod(refinedReceiverType, method);
}
DexEncodedMethod topSingleTarget = topMethod.asSingleTarget();
DexClass topHolder = definitionFor(topSingleTarget.method.holder);
// We need to know whether the top method is from an interface, as that would allow it to be
// shadowed by a default method from an interface further down.
boolean topIsFromInterface = topHolder.isInterface();
// Now look at all subtypes and search for overrides.
DexEncodedMethod result =
findSingleTargetFromSubtypes(
refinedReceiverType,
method,
topSingleTarget,
!refinedHolder.accessFlags.isAbstract(),
topIsFromInterface);
// Map the failure case of SENTINEL to null.
result = result == DexEncodedMethod.SENTINEL ? null : result;
method.setSingleVirtualMethodCache(refinedReceiverType, result);
return result;
}
/**
* Computes which methods overriding <code>method</code> are visible for the subtypes of type.
*
* <p><code>candidate</code> is the definition further up the hierarchy that is visible from the
* subtypes. If <code>candidateIsReachable</code> is true, the provided candidate is already a
* target for a type further up the chain, so anything found in subtypes is a conflict. If it is
* false, the target exists but is not reachable from a live type.
*
* <p>Returns <code>null</code> if the given type has no subtypes or all subtypes are abstract.
* Returns {@link DexEncodedMethod#SENTINEL} if multiple live overrides were found. Returns the
* single virtual target otherwise.
*/
private DexEncodedMethod findSingleTargetFromSubtypes(
DexType type,
DexMethod method,
DexEncodedMethod candidate,
boolean candidateIsReachable,
boolean checkForInterfaceConflicts) {
// If the candidate is reachable, we already have a previous result.
DexEncodedMethod result = candidateIsReachable ? candidate : null;
if (pinnedItems.contains(type)) {
// For kept types we do not know all subtypes, so abort.
return DexEncodedMethod.SENTINEL;
}
for (DexType subtype : allExtendsSubtypes(type)) {
DexClass clazz = definitionFor(subtype);
DexEncodedMethod target = clazz.lookupVirtualMethod(method);
if (target != null && !target.isPrivateMethod()) {
// We found a method on this class. If this class is not abstract it is a runtime
// reachable override and hence a conflict.
if (!clazz.accessFlags.isAbstract()) {
if (result != null && result != target) {
// We found a new target on this subtype that does not match the previous one. Fail.
return DexEncodedMethod.SENTINEL;
}
// Add the first or matching target.
result = target;
}
}
if (checkForInterfaceConflicts) {
// We have to check whether there are any default methods in implemented interfaces.
if (interfacesMayHaveDefaultFor(clazz.interfaces, method)) {
return DexEncodedMethod.SENTINEL;
}
}
DexEncodedMethod newCandidate = target == null ? candidate : target;
// If we have a new target and did not fail, it is not an override of a reachable method.
// Whether the target is actually reachable depends on whether this class is abstract.
// If we did not find a new target, the candidate is reachable if it was before, or if this
// class is not abstract.
boolean newCandidateIsReachable =
!clazz.accessFlags.isAbstract() || ((target == null) && candidateIsReachable);
DexEncodedMethod subtypeTarget =
findSingleTargetFromSubtypes(
subtype, method, newCandidate, newCandidateIsReachable, checkForInterfaceConflicts);
if (subtypeTarget != null) {
// We found a target in the subclasses. If we already have a different result, fail.
if (result != null && result != subtypeTarget) {
return DexEncodedMethod.SENTINEL;
}
// Remember this new result.
result = subtypeTarget;
}
}
return result;
}
/**
* Checks whether any interface in the given list or their super interfaces implement a default
* method.
*
* <p>This method is conservative for unknown interfaces and interfaces from the library.
*/
private boolean interfacesMayHaveDefaultFor(DexTypeList ifaces, DexMethod method) {
for (DexType iface : ifaces.values) {
DexClass clazz = definitionFor(iface);
if (clazz == null || clazz.isNotProgramClass()) {
return true;
}
DexEncodedMethod candidate = clazz.lookupMethod(method);
if (candidate != null && !candidate.accessFlags.isAbstract()) {
return true;
}
if (interfacesMayHaveDefaultFor(clazz.interfaces, method)) {
return true;
}
}
return false;
}
public DexEncodedMethod lookupSingleInterfaceTarget(DexMethod method) {
assert checkIfObsolete();
return lookupSingleInterfaceTarget(method, method.holder);
}
public DexEncodedMethod lookupSingleInterfaceTarget(
DexMethod method, DexType refinedReceiverType) {
assert checkIfObsolete();
if (instantiatedLambdas.contains(method.holder)) {
return null;
}
DexClass holder = definitionFor(method.holder);
if ((holder == null) || holder.isNotProgramClass() || !holder.accessFlags.isInterface()) {
return null;
}
// First check that there is a target for this invoke-interface to hit. If there is none,
// this will fail at runtime.
ResolutionResult topTarget = resolveMethodOnInterface(method.holder, method);
if (topTarget.asResultOfResolve() == null) {
return null;
}
// For kept types we cannot ensure a single target.
if (pinnedItems.contains(method.holder)) {
return null;
}
DexEncodedMethod result = null;
// The loop will ignore abstract classes that are not kept as they should not be a target
// at runtime.
Iterable<DexType> subTypesToExplore =
refinedReceiverType == method.holder
? subtypes(method.holder)
: Iterables.concat(
ImmutableList.of(refinedReceiverType), subtypes(refinedReceiverType));
for (DexType type : subTypesToExplore) {
if (instantiatedLambdas.contains(type)) {
return null;
}
if (pinnedItems.contains(type)) {
// For kept classes we cannot ensure a single target.
return null;
}
DexClass clazz = definitionFor(type);
if (clazz.isInterface()) {
// Default methods are looked up when looking at a specific subtype that does not
// override them, so we ignore interface methods here. Otherwise, we would look up
// default methods that are factually never used.
} else if (!clazz.accessFlags.isAbstract()) {
ResolutionResult resolutionResult = resolveMethodOnClass(type, method);
if (resolutionResult.hasSingleTarget()) {
if ((result != null) && (result != resolutionResult.asSingleTarget())) {
return null;
} else {
result = resolutionResult.asSingleTarget();
}
} else {
// This will fail at runtime.
return null;
}
}
}
return result == null || !result.isVirtualMethod() ? null : result;
}
public AppInfoWithLiveness addSwitchMaps(Map<DexField, Int2ReferenceMap<DexField>> switchMaps) {
assert checkIfObsolete();
assert this.switchMaps.isEmpty();
return new AppInfoWithLiveness(this, switchMaps, ordinalsMaps);
}
public AppInfoWithLiveness addEnumOrdinalMaps(
Map<DexType, Reference2IntMap<DexField>> ordinalsMaps) {
assert checkIfObsolete();
assert this.ordinalsMaps.isEmpty();
return new AppInfoWithLiveness(this, switchMaps, ordinalsMaps);
}
}