| // Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file | |
| // for details. All rights reserved. Use of this source code is governed by a | |
| // BSD-style license that can be found in the LICENSE file. | |
| package com.android.tools.r8.graph; | |
| import static com.android.tools.r8.graph.MethodResolution.UniquePathOracle.SplitToken.NO_SPLIT_TOKEN; | |
| import static com.android.tools.r8.utils.internal.MapUtils.ignoreKey; | |
| import com.android.tools.r8.graph.MethodResolutionResult.ArrayCloneMethodResult; | |
| import com.android.tools.r8.graph.MethodResolutionResult.ClassNotFoundResult; | |
| import com.android.tools.r8.graph.MethodResolutionResult.IllegalAccessOrNoSuchMethodResult; | |
| import com.android.tools.r8.graph.MethodResolutionResult.IncompatibleClassResult; | |
| import com.android.tools.r8.graph.MethodResolutionResult.NoSuchMethodResult; | |
| import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult; | |
| import com.android.tools.r8.ir.desugar.LambdaDescriptor; | |
| import com.android.tools.r8.utils.internal.ListUtils; | |
| import com.android.tools.r8.utils.internal.SetUtils; | |
| import com.google.common.collect.Sets; | |
| import java.util.ArrayList; | |
| import java.util.Arrays; | |
| import java.util.Collections; | |
| import java.util.IdentityHashMap; | |
| import java.util.LinkedHashMap; | |
| import java.util.List; | |
| import java.util.Map; | |
| import java.util.Map.Entry; | |
| import java.util.Set; | |
| import java.util.function.Function; | |
| /** | |
| * Implements resolution of a method descriptor against a type. | |
| * | |
| * <p>See <a href="https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3"> | |
| * Section 5.4.3.3 of the JVM Spec</a>. | |
| */ | |
| public class MethodResolution { | |
| private final Function<DexType, ClassResolutionResult> definitionFor; | |
| private final DexItemFactory factory; | |
| private final boolean escapeIfLibraryHasProgramSuperType; | |
| private final boolean canHaveIncompletePaths; | |
| protected MethodResolution( | |
| Function<DexType, ClassResolutionResult> definitionFor, DexItemFactory factory) { | |
| this(definitionFor, factory, true, true); | |
| } | |
| protected MethodResolution( | |
| Function<DexType, ClassResolutionResult> definitionFor, | |
| DexItemFactory factory, | |
| boolean escapeIfLibraryHasProgramSuperType, | |
| boolean canHaveIncompletePaths) { | |
| this.definitionFor = definitionFor; | |
| this.factory = factory; | |
| this.escapeIfLibraryHasProgramSuperType = escapeIfLibraryHasProgramSuperType; | |
| this.canHaveIncompletePaths = canHaveIncompletePaths; | |
| } | |
| @Deprecated | |
| public static MethodResolution createLegacy( | |
| Function<DexType, DexClass> definitionFor, DexItemFactory factory) { | |
| // TODO(b/230289235): Remove this when R8/D8 can handle multiple definitions. | |
| return new MethodResolution( | |
| type -> { | |
| DexClass clazz = definitionFor.apply(type); | |
| return clazz == null ? ClassResolutionResult.NoResolutionResult.noResult() : clazz; | |
| }, | |
| factory, | |
| false, | |
| false); | |
| } | |
| public static MethodResolution create( | |
| Function<DexType, ClassResolutionResult> definitionFor, DexItemFactory factory) { | |
| return new MethodResolution(definitionFor, factory); | |
| } | |
| private ClassResolutionResult definitionFor(DexType type) { | |
| return definitionFor.apply(type); | |
| } | |
| /** | |
| * This method will query the definition of the holder to decide on which resolution to use. If | |
| * the holder is an interface, it delegates to {@link #resolveMethodOnInterface(DexClass, | |
| * DexProto, DexString)}, otherwise {@link #resolveMethodOnClass(DexClass, DexProto, DexString)} | |
| * is used. | |
| * | |
| * <p>This is to overcome the shortcoming of the DEX file format that does not allow to encode the | |
| * kind of a method reference. | |
| */ | |
| public MethodResolutionResult unsafeResolveMethodDueToDexFormat(DexMethod method) { | |
| DexType holder = method.holder; | |
| if (holder.isArrayType()) { | |
| return resolveMethodOnArray(holder, method.getProto(), method.getName()); | |
| } | |
| MethodResolutionResult.Builder builder = MethodResolutionResult.builder(); | |
| definitionFor(holder) | |
| .forEachClassResolutionResult( | |
| clazz -> | |
| builder.addResolutionResult( | |
| clazz.isInterface() | |
| ? resolveMethodOnInterface(clazz, method.getProto(), method.getName()) | |
| : resolveMethodOnClass(clazz, method.getProto(), method.getName()))); | |
| return builder.buildOrIfEmpty(ClassNotFoundResult.INSTANCE, holder); | |
| } | |
| /** | |
| * Implements resolution of a method descriptor against an array type. | |
| * | |
| * <p>See <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-10.html#jls-10.7">Section | |
| * 10.7 of the Java Language Specification</a>. All invokations will have target java.lang.Object | |
| * except clone which has no target. | |
| */ | |
| private MethodResolutionResult resolveMethodOnArray( | |
| DexType holder, DexProto methodProto, DexString methodName) { | |
| assert holder.isArrayType(); | |
| if (factory.isObjectCloneWithoutHolderCheck(methodProto, methodName)) { | |
| return ArrayCloneMethodResult.INSTANCE; | |
| } else { | |
| return resolveMethodOnClass(factory.objectType, methodProto, methodName); | |
| } | |
| } | |
| /** | |
| * Implements resolution of a method descriptor against a class type. | |
| * | |
| * <p>See <a href="https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3"> | |
| * Section 5.4.3.3 of the JVM Spec</a>. | |
| * | |
| * <p>The resolved method is not the method that will actually be invoked. Which methods gets | |
| * invoked depends on the invoke instruction used. However, it is always safe to rewrite any | |
| * invoke on the given descriptor to a corresponding invoke on the resolved descriptor, as the | |
| * resolved method is used as basis for dispatch. | |
| */ | |
| public MethodResolutionResult resolveMethodOnClass( | |
| DexType holder, DexProto methodProto, DexString methodName) { | |
| if (holder.isArrayType()) { | |
| return resolveMethodOnArray(holder, methodProto, methodName); | |
| } | |
| MethodResolutionResult.Builder builder = MethodResolutionResult.builder(); | |
| definitionFor(holder) | |
| .forEachClassResolutionResult( | |
| clazz -> { | |
| // Step 1: If holder is an interface, resolution fails with an ICCE. | |
| if (clazz.isInterface()) { | |
| builder.addResolutionResult(IncompatibleClassResult.INSTANCE); | |
| } else { | |
| builder.addResolutionResult(resolveMethodOnClass(clazz, methodProto, methodName)); | |
| } | |
| }); | |
| return builder.buildOrIfEmpty(ClassNotFoundResult.INSTANCE, holder); | |
| } | |
| public MethodResolutionResult resolveMethodOnClass( | |
| DexClass clazz, DexProto methodProto, DexString methodName) { | |
| assert !clazz.isInterface(); | |
| // Step 2: | |
| MethodResolutionResult result = | |
| resolveMethodOnClassStep2(clazz, methodProto, methodName, clazz); | |
| if (result != null) { | |
| return result; | |
| } | |
| // Finally Step 3: | |
| return resolveMethodStep3(clazz, methodProto, methodName); | |
| } | |
| /** | |
| * Implements step 2 of method resolution on classes as per <a | |
| * href="https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3">Section | |
| * 5.4.3.3 of the JVM Spec</a>. | |
| */ | |
| private MethodResolutionResult resolveMethodOnClassStep2( | |
| DexClass clazz, | |
| DexProto methodProto, | |
| DexString methodName, | |
| DexClass initialResolutionHolder) { | |
| // Pt. 1: Signature polymorphic method check. | |
| // See also <a href="https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-2.html#jvms-2.9"> | |
| // Section 2.9 of the JVM Spec</a>. | |
| DexEncodedMethod result = clazz.lookupSignaturePolymorphicMethod(methodName, factory); | |
| if (result != null) { | |
| return MethodResolutionResult.createSingleResolutionResult( | |
| initialResolutionHolder, clazz, result); | |
| } | |
| // Pt 2: Find a method that matches the descriptor. | |
| result = lookupMethod(clazz, methodProto, methodName); | |
| if (result != null) { | |
| // If the resolved method is private, then it can only be accessed if the symbolic reference | |
| // that initiated the resolution was the type at which the method resolved on. If that is not | |
| // the case, then the error is either an IllegalAccessError, or in the case where access is | |
| // allowed because of nests, a NoSuchMethodError. Which error cannot be determined without | |
| // knowing the calling context. | |
| if (result.isPrivateMethod() && clazz != initialResolutionHolder) { | |
| return new IllegalAccessOrNoSuchMethodResult(initialResolutionHolder, result); | |
| } | |
| return MethodResolutionResult.createSingleResolutionResult( | |
| initialResolutionHolder, clazz, result); | |
| } | |
| // Pt 3: Apply step two to direct superclass of holder. | |
| if (clazz.superType != null) { | |
| MethodResolutionResult.Builder builder = MethodResolutionResult.builder(); | |
| definitionFor(clazz.superType) | |
| .forEachClassResolutionResult( | |
| superClass -> { | |
| // Guard against going back into the program for resolution. | |
| if (escapeIfLibraryHasProgramSuperType | |
| && clazz.isLibraryClass() | |
| && !superClass.isLibraryClass()) { | |
| return; | |
| } | |
| MethodResolutionResult superTypeResult = | |
| resolveMethodOnClassStep2( | |
| superClass, methodProto, methodName, initialResolutionHolder); | |
| if (superTypeResult != null) { | |
| builder.addResolutionResult(superTypeResult); | |
| } | |
| }); | |
| return builder.buildOrIfEmpty(null, clazz.superType); | |
| } | |
| return null; | |
| } | |
| /** | |
| * Implements step 3 of <a | |
| * href="https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3">Section | |
| * 5.4.3.3 of the JVM Spec</a>. As this is the same for interfaces and classes, we share one | |
| * implementation. | |
| */ | |
| private MethodResolutionResult resolveMethodStep3( | |
| DexClass clazz, DexProto methodProto, DexString methodName) { | |
| MaximallySpecificMethodsBuilder builder = new MaximallySpecificMethodsBuilder(); | |
| resolveMethodStep3Helper(methodProto, methodName, clazz, builder); | |
| return builder.resolve(clazz); | |
| } | |
| MethodResolutionResult resolveMaximallySpecificTarget(DexClass clazz, DexMethod method) { | |
| return resolveMaximallySpecificTargetHelper(clazz, method).resolve(clazz); | |
| } | |
| MethodResolutionResult resolveMaximallySpecificTarget(LambdaDescriptor lambda, DexMethod method) { | |
| return resolveMaximallySpecificTargetHelper(lambda, method).internalResolve(null); | |
| } | |
| // Non-private lookup (ie, not resolution) to find interface targets. | |
| DexClassAndMethod lookupMaximallySpecificTarget(DexClass clazz, DexMethod method) { | |
| return resolveMaximallySpecificTargetHelper(clazz, method).lookup(); | |
| } | |
| // Non-private method used for emulated interface only. | |
| List<Entry<DexClass, DexEncodedMethod>> getAbstractInterfaceMethods( | |
| DexClass clazz, DexMethod method) { | |
| return resolveMaximallySpecificTargetHelper(clazz, method).getAbstractMethods(); | |
| } | |
| private MaximallySpecificMethodsBuilder resolveMaximallySpecificTargetHelper( | |
| DexClass clazz, DexMethod method) { | |
| MaximallySpecificMethodsBuilder builder = new MaximallySpecificMethodsBuilder(); | |
| resolveMethodStep3Helper(method.getProto(), method.getName(), clazz, builder); | |
| return builder; | |
| } | |
| private MaximallySpecificMethodsBuilder resolveMaximallySpecificTargetHelper( | |
| LambdaDescriptor lambda, DexMethod method) { | |
| MaximallySpecificMethodsBuilder builder = new MaximallySpecificMethodsBuilder(); | |
| resolveMethodStep3Helper( | |
| method.getProto(), method.getName(), null, builder, factory.objectType, lambda.interfaces); | |
| return builder; | |
| } | |
| /** | |
| * UniquePathOracle will compute for all parent definitions in the hierarchy if a class is visited | |
| * by all paths or not depending on class resolution resolving a type to either library or | |
| * program/classpath definitions. It does so by visiting all paths upwards in the hierarchy and | |
| * when a split point is seen it will create a "left" and "right" half rooted by the split type. | |
| * If a definition is only seen by a single token it will always be on an incomplete path | |
| * otherwise if the class is seen by both the left and right token it is visited by all: | |
| * | |
| * <pre> | |
| * C_Library { left_B, right_B } | |
| * / \ | |
| * B_Program extends C { left_B } B_Library extends C { right_B } | |
| * \ / | |
| * A_Program extends B { } | |
| * </pre> | |
| */ | |
| static class UniquePathOracle { | |
| static class SplitToken { | |
| static final SplitToken NO_SPLIT_TOKEN = new SplitToken(null); | |
| private final DexType split; | |
| private SplitToken(DexType split) { | |
| this.split = split; | |
| } | |
| boolean isSplitToken() { | |
| return this != NO_SPLIT_TOKEN; | |
| } | |
| } | |
| private final MethodResolution methodResolution; | |
| private final boolean escapeIfLibraryHasProgramSuperType; | |
| private final Map<DexClass, Map<DexType, SplitToken>> incompletePaths = new IdentityHashMap<>(); | |
| private final Set<DexType> seenTypes = Sets.newIdentityHashSet(); | |
| public UniquePathOracle( | |
| MethodResolution methodResolution, boolean escapeIfLibraryHasProgramSuperType) { | |
| this.methodResolution = methodResolution; | |
| this.escapeIfLibraryHasProgramSuperType = escapeIfLibraryHasProgramSuperType; | |
| } | |
| public boolean onIncompletePath(DexClass definition) { | |
| Map<DexType, SplitToken> tokenMap = incompletePaths.get(definition); | |
| assert tokenMap != null; | |
| for (SplitToken value : tokenMap.values()) { | |
| if (value.isSplitToken()) { | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| void lookupPath(DexType type, DexClass previousClass) { | |
| lookupPath(type, previousClass, Collections.emptySet()); | |
| } | |
| private void lookupPath(DexType type, DexClass previousClass, Set<SplitToken> splitTokens) { | |
| if (splitTokens.isEmpty() && !seenTypes.add(type)) { | |
| return; | |
| } | |
| ClassResolutionResult resolutionResult = methodResolution.definitionFor.apply(type); | |
| resolutionResult.forEachClassResolutionResult( | |
| clazz -> { | |
| if (escapeIfLibraryHasProgramSuperType | |
| && previousClass.isLibraryClass() | |
| && !clazz.isLibraryClass()) { | |
| return; | |
| } | |
| Set<SplitToken> currentSplitTokens; | |
| if (resolutionResult.isMultipleClassResolutionResult()) { | |
| currentSplitTokens = SetUtils.newIdentityHashSet(splitTokens); | |
| currentSplitTokens.add(new SplitToken(type)); | |
| } else { | |
| currentSplitTokens = splitTokens; | |
| } | |
| Map<DexType, SplitToken> paths = | |
| incompletePaths.computeIfAbsent(clazz, ignoreKey(IdentityHashMap::new)); | |
| currentSplitTokens.forEach( | |
| splitToken -> { | |
| SplitToken otherSplitToken = paths.get(splitToken.split); | |
| if (otherSplitToken == null) { | |
| paths.put(splitToken.split, splitToken); | |
| } else if (otherSplitToken != splitToken && otherSplitToken.isSplitToken()) { | |
| // We have not seen this half of the split token, so it is visited on all paths. | |
| paths.put(splitToken.split, NO_SPLIT_TOKEN); | |
| } | |
| }); | |
| methodResolution | |
| .getInterfaces(clazz) | |
| .forEach(iface -> lookupPath(iface, clazz, currentSplitTokens)); | |
| if (clazz.superType != null) { | |
| lookupPath(clazz.superType, clazz, currentSplitTokens); | |
| } | |
| }); | |
| } | |
| } | |
| static class AllUniquePathsOracle extends UniquePathOracle { | |
| private static final AllUniquePathsOracle INSTANCE = new AllUniquePathsOracle(); | |
| static AllUniquePathsOracle getInstance() { | |
| return INSTANCE; | |
| } | |
| private AllUniquePathsOracle() { | |
| super(null, false); | |
| } | |
| @Override | |
| void lookupPath(DexType type, DexClass previousClass) { | |
| // Intentionally empty | |
| } | |
| @Override | |
| public boolean onIncompletePath(DexClass definition) { | |
| return false; | |
| } | |
| } | |
| /** Helper method that builds the set of maximally specific methods. */ | |
| private void resolveMethodStep3Helper( | |
| DexProto methodProto, | |
| DexString methodName, | |
| DexClass clazz, | |
| MaximallySpecificMethodsBuilder builder) { | |
| resolveMethodStep3Helper( | |
| methodProto, | |
| methodName, | |
| clazz, | |
| builder, | |
| clazz.superType, | |
| Arrays.asList(getInterfaces(clazz).values)); | |
| } | |
| private void resolveMethodStep3Helper( | |
| DexProto methodProto, | |
| DexString methodName, | |
| DexClass clazz, | |
| MaximallySpecificMethodsBuilder builder, | |
| DexType superType, | |
| List<DexType> interfaces) { | |
| UniquePathOracle uniquePathOracle; | |
| if (canHaveIncompletePaths) { | |
| uniquePathOracle = new UniquePathOracle(this, escapeIfLibraryHasProgramSuperType); | |
| interfaces.forEach(iFace -> uniquePathOracle.lookupPath(iFace, clazz)); | |
| if (superType != null) { | |
| uniquePathOracle.lookupPath(superType, clazz); | |
| } | |
| } else { | |
| uniquePathOracle = AllUniquePathsOracle.getInstance(); | |
| } | |
| resolveMethodStep3Helper( | |
| methodProto, methodName, clazz, builder, superType, interfaces, uniquePathOracle); | |
| } | |
| private void resolveMethodStep3Helper( | |
| DexProto methodProto, | |
| DexString methodName, | |
| DexClass clazz, | |
| MaximallySpecificMethodsBuilder builder, | |
| DexType superType, | |
| List<DexType> interfaces, | |
| UniquePathOracle uniquePathOracle) { | |
| for (DexType iface : interfaces) { | |
| ClassResolutionResult classResolutionResult = definitionFor(iface); | |
| classResolutionResult.forEachClassResolutionResult( | |
| definition -> { | |
| // Guard against going back into the program for resolution. | |
| if (escapeIfLibraryHasProgramSuperType | |
| && clazz != null | |
| && clazz.isLibraryClass() | |
| && !definition.isLibraryClass()) { | |
| return; | |
| } | |
| if (classResolutionResult.isMultipleClassResolutionResult()) { | |
| builder.addTypeWithMultipleDefinitions(iface); | |
| } | |
| assert definition.isInterface(); | |
| DexEncodedMethod result = lookupMethod(definition, methodProto, methodName); | |
| if (isMaximallySpecificCandidate(result)) { | |
| // The candidate is added and doing so will prohibit shadowed methods from being | |
| // in the set. | |
| builder.addCandidate( | |
| definition, result, uniquePathOracle.onIncompletePath(definition)); | |
| } else { | |
| // Look at the super-interfaces of this class and keep searching. | |
| resolveMethodStep3Helper( | |
| methodProto, | |
| methodName, | |
| definition, | |
| builder, | |
| definition.superType, | |
| Arrays.asList(getInterfaces(definition).values), | |
| uniquePathOracle); | |
| } | |
| }); | |
| } | |
| // Now look at indirect super interfaces. | |
| if (superType != null) { | |
| definitionFor(superType) | |
| .forEachClassResolutionResult( | |
| superClass -> { | |
| // Guard against going back into the program for resolution. | |
| if (escapeIfLibraryHasProgramSuperType | |
| && clazz != null | |
| && clazz.isLibraryClass() | |
| && !superClass.isLibraryClass()) { | |
| return; | |
| } | |
| resolveMethodStep3Helper( | |
| methodProto, | |
| methodName, | |
| superClass, | |
| builder, | |
| superClass.superType, | |
| Arrays.asList(getInterfaces(superClass).values), | |
| uniquePathOracle); | |
| }); | |
| } | |
| } | |
| /** | |
| * A candidate for being a maximally specific method must have neither its private, nor its static | |
| * flag set. A candidate may still not be maximally specific, which entails that no subinterfaces | |
| * from also contribute with a candidate to the type. That is not determined by this method. | |
| */ | |
| private boolean isMaximallySpecificCandidate(DexEncodedMethod method) { | |
| return method != null && !method.isPrivate() && !method.isStatic(); | |
| } | |
| /** | |
| * Implements resolution of a method descriptor against an interface type. | |
| * | |
| * <p>See <a href="https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3"> | |
| * Section 5.4.3.4 of the JVM Spec</a>. | |
| * | |
| * <p>The resolved method is not the method that will actually be invoked. Which methods gets | |
| * invoked depends on the invoke instruction used. However, it is always safe to rewrite any | |
| * invoke on the given descriptor to a corresponding invoke on the resolved descriptor, as the | |
| * resolved method is used as basis for dispatch. | |
| */ | |
| public MethodResolutionResult resolveMethodOnInterface( | |
| DexType holder, DexProto proto, DexString methodName) { | |
| if (holder.isArrayType()) { | |
| return IncompatibleClassResult.INSTANCE; | |
| } | |
| MethodResolutionResult.Builder builder = MethodResolutionResult.builder(); | |
| // Step 1: Lookup interface. | |
| definitionFor(holder) | |
| .forEachClassResolutionResult( | |
| definition -> { | |
| // If the definition is not an interface, resolution fails with an ICCE. | |
| if (!definition.isInterface()) { | |
| builder.addResolutionResult(IncompatibleClassResult.INSTANCE); | |
| } else { | |
| builder.addResolutionResult( | |
| resolveMethodOnInterface(definition, proto, methodName)); | |
| } | |
| }); | |
| return builder.buildOrIfEmpty(ClassNotFoundResult.INSTANCE, holder); | |
| } | |
| public MethodResolutionResult resolveMethodOnInterface( | |
| DexClass definition, DexProto methodProto, DexString methodName) { | |
| assert definition.isInterface(); | |
| // Step 2: Look for exact method on interface. | |
| DexEncodedMethod result = lookupMethod(definition, methodProto, methodName); | |
| if (result != null) { | |
| return MethodResolutionResult.createSingleResolutionResult(definition, definition, result); | |
| } | |
| // Step 3: Look for matching method on object class. | |
| MethodResolutionResult.Builder builder = MethodResolutionResult.builder(); | |
| definitionFor(factory.objectType) | |
| .forEachClassResolutionResult( | |
| objectClass -> { | |
| DexEncodedMethod objectResult = lookupMethod(objectClass, methodProto, methodName); | |
| if (objectResult != null && objectResult.isPublic() && !objectResult.isAbstract()) { | |
| builder.addResolutionResult( | |
| MethodResolutionResult.createSingleResolutionResult( | |
| definition, objectClass, objectResult)); | |
| } else { | |
| // Step 3: Look for maximally-specific superinterface methods or any interface | |
| // definition. This is the same for classes and interfaces. | |
| builder.addResolutionResult( | |
| resolveMethodStep3(definition, methodProto, methodName)); | |
| } | |
| }); | |
| return builder.buildOrIfEmpty(ClassNotFoundResult.INSTANCE, Collections.emptySet()); | |
| } | |
| class MaximallySpecificMethodsBuilder { | |
| // The set of actual maximally specific methods. | |
| // This set is linked map so that in the case where a number of methods remain a deterministic | |
| // choice can be made. The map is from definition classes to their maximally specific method, or | |
| // in the case that a type has a candidate which is shadowed by a subinterface, the map will | |
| // map the class to a null entry, thus any addition to the map must check for key containment | |
| // prior to writing. | |
| private final LinkedHashMap<DexClass, DexEncodedMethod> | |
| maximallySpecificMethodsOnCompletePaths = new LinkedHashMap<>(); | |
| private final LinkedHashMap<DexClass, DexEncodedMethod> | |
| maximallySpecificMethodsOnIncompletePaths = new LinkedHashMap<>(); | |
| private final Set<DexType> typesWithMultipleDefinitions = Sets.newIdentityHashSet(); | |
| private MaximallySpecificMethodsBuilder() {} | |
| void addTypeWithMultipleDefinitions(DexType type) { | |
| typesWithMultipleDefinitions.add(type); | |
| } | |
| @SuppressWarnings("ReferenceEquality") | |
| void addCandidate(DexClass holder, DexEncodedMethod method, boolean isIncompletePath) { | |
| // If this candidate is already a candidate or it is shadowed, then no need to continue. | |
| if (isIncompletePath) { | |
| if (!maximallySpecificMethodsOnIncompletePaths.containsKey(holder)) { | |
| maximallySpecificMethodsOnIncompletePaths.put(holder, method); | |
| } | |
| // Incomplete paths can shadow complete path results if all partial paths is | |
| // shadowing. | |
| // I_L { f(); } | |
| // / \ | |
| // J_L { f(); } // J_P { f(); } | |
| // One way to track them is to count all coverings are equal to the splits. For now | |
| // we bail out. | |
| return; | |
| } else if (maximallySpecificMethodsOnCompletePaths.containsKey(holder)) { | |
| return; | |
| } | |
| maximallySpecificMethodsOnCompletePaths.put(holder, method); | |
| // Prune exiting candidates and prohibit future candidates in the super hierarchy. | |
| assert holder.isInterface(); | |
| assert holder.superType == factory.objectType; | |
| for (DexType iface : getInterfaces(holder).values) { | |
| markShadowed(iface); | |
| } | |
| } | |
| @SuppressWarnings("ReferenceEquality") | |
| private void markShadowed(DexType type) { | |
| if (type == null) { | |
| return; | |
| } | |
| definitionFor | |
| .apply(type) | |
| .forEachClassResolutionResult( | |
| clazz -> { | |
| assert clazz.isInterface(); | |
| assert clazz.superType == factory.objectType; | |
| // A null entry signifies that the candidate is shadowed blocking future candidates. | |
| // If the candidate is already shadowed at this type there is no need to shadow | |
| // further up. | |
| if (maximallySpecificMethodsOnCompletePaths.getOrDefault( | |
| clazz, DexEncodedMethod.SENTINEL) | |
| == null) { | |
| return; | |
| } | |
| maximallySpecificMethodsOnCompletePaths.put(clazz, null); | |
| maximallySpecificMethodsOnIncompletePaths.put(clazz, null); | |
| for (DexType iface : getInterfaces(clazz).values) { | |
| markShadowed(iface); | |
| } | |
| }); | |
| } | |
| DexClassAndMethod lookup() { | |
| return internalResolve(null).getResolutionPair(); | |
| } | |
| MethodResolutionResult resolve(DexClass initialResolutionHolder) { | |
| assert initialResolutionHolder != null; | |
| return internalResolve(initialResolutionHolder); | |
| } | |
| private MethodResolutionResult internalResolve(DexClass initialResolutionHolder) { | |
| if (maximallySpecificMethodsOnCompletePaths.isEmpty() | |
| && maximallySpecificMethodsOnIncompletePaths.isEmpty()) { | |
| return NoSuchMethodResult.INSTANCE; | |
| } | |
| List<Entry<DexClass, DexEncodedMethod>> nonAbstractOnComplete = | |
| getNonAbstractMethods(maximallySpecificMethodsOnCompletePaths); | |
| if (nonAbstractOnComplete.size() > 1) { | |
| return IncompatibleClassResult.create( | |
| ListUtils.map(nonAbstractOnComplete, Entry::getValue)); | |
| } | |
| List<Entry<DexClass, DexEncodedMethod>> nonAbstractOnIncomplete = | |
| getNonAbstractMethods(maximallySpecificMethodsOnIncompletePaths); | |
| if (nonAbstractOnIncomplete.isEmpty()) { | |
| // If there are no non-abstract methods, then any candidate on a complete path will suffice | |
| // as a target. For deterministic resolution, we return the first mapped method (of the | |
| // linked map). | |
| if (nonAbstractOnComplete.isEmpty()) { | |
| Entry<DexClass, DexEncodedMethod> abstractMethod = | |
| firstNonNullEntry(maximallySpecificMethodsOnCompletePaths); | |
| if (abstractMethod == null) { | |
| abstractMethod = firstNonNullEntry(maximallySpecificMethodsOnIncompletePaths); | |
| } | |
| assert abstractMethod != null && abstractMethod.getValue().isAbstract(); | |
| return singleResultHelper(initialResolutionHolder, abstractMethod); | |
| } else { | |
| // If there is exactly one non-abstract method (a default method) it is the resolution | |
| // target. | |
| return singleResultHelper(initialResolutionHolder, nonAbstractOnComplete.get(0)); | |
| } | |
| } else { | |
| // We cannot guarantee a single target or an error, so we have to report all on incomplete | |
| // paths. | |
| MethodResolutionResult.Builder builder = | |
| MethodResolutionResult.builder().allowMultipleProgramResults(); | |
| if (nonAbstractOnComplete.isEmpty()) { | |
| assert !typesWithMultipleDefinitions.isEmpty(); | |
| builder.addResolutionResult(NoSuchMethodResult.INSTANCE); | |
| } else { | |
| nonAbstractOnComplete.forEach( | |
| entry -> | |
| builder.addResolutionResult(singleResultHelper(initialResolutionHolder, entry))); | |
| } | |
| nonAbstractOnIncomplete.forEach( | |
| entry -> | |
| builder.addResolutionResult(singleResultHelper(initialResolutionHolder, entry))); | |
| return builder.buildOrIfEmpty(NoSuchMethodResult.INSTANCE, typesWithMultipleDefinitions); | |
| } | |
| } | |
| private List<Entry<DexClass, DexEncodedMethod>> getNonAbstractMethods( | |
| Map<DexClass, DexEncodedMethod> candidates) { | |
| List<Entry<DexClass, DexEncodedMethod>> nonAbstractMethods = new ArrayList<>(); | |
| for (Entry<DexClass, DexEncodedMethod> entry : candidates.entrySet()) { | |
| DexEncodedMethod method = entry.getValue(); | |
| if (method == null) { | |
| // Ignore shadowed candidates. | |
| continue; | |
| } | |
| if (method.isNonAbstractVirtualMethod()) { | |
| nonAbstractMethods.add(entry); | |
| } | |
| } | |
| return nonAbstractMethods; | |
| } | |
| List<Entry<DexClass, DexEncodedMethod>> getAbstractMethods() { | |
| List<Entry<DexClass, DexEncodedMethod>> abstractMethods = new ArrayList<>(); | |
| addAbstractMethods(abstractMethods, maximallySpecificMethodsOnCompletePaths); | |
| addAbstractMethods(abstractMethods, maximallySpecificMethodsOnIncompletePaths); | |
| return abstractMethods; | |
| } | |
| private void addAbstractMethods( | |
| List<Entry<DexClass, DexEncodedMethod>> abstractMethods, | |
| Map<DexClass, DexEncodedMethod> candidates) { | |
| for (Entry<DexClass, DexEncodedMethod> entry : candidates.entrySet()) { | |
| DexEncodedMethod method = entry.getValue(); | |
| if (method == null) { | |
| // Ignore shadowed candidates. | |
| continue; | |
| } | |
| if (method.isAbstract()) { | |
| abstractMethods.add(entry); | |
| } | |
| } | |
| } | |
| } | |
| protected DexTypeList getInterfaces(DexClass clazz) { | |
| return clazz.getInterfaces(); | |
| } | |
| protected DexEncodedMethod lookupMethod( | |
| DexClass clazz, DexProto methodProto, DexString methodName) { | |
| return clazz.lookupMethod(methodProto, methodName); | |
| } | |
| private static SingleResolutionResult<?> singleResultHelper( | |
| DexClass initialResolutionResult, Entry<DexClass, DexEncodedMethod> entry) { | |
| return MethodResolutionResult.createSingleResolutionResult( | |
| initialResolutionResult != null ? initialResolutionResult : entry.getKey(), | |
| entry.getKey(), | |
| entry.getValue()); | |
| } | |
| private static Entry<DexClass, DexEncodedMethod> firstNonNullEntry( | |
| Map<DexClass, DexEncodedMethod> candidates) { | |
| for (Entry<DexClass, DexEncodedMethod> entry : candidates.entrySet()) { | |
| DexEncodedMethod method = entry.getValue(); | |
| if (method != null) { | |
| return entry; | |
| } | |
| } | |
| return null; | |
| } | |
| } |