blob: 442489d6caac994cc03468c46a926f9804bbecea [file] [log] [blame]
// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.horizontalclassmerging;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClass.FieldSetter;
import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexMethodSignature;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.DexTypeList;
import com.android.tools.r8.graph.EnclosingMethodAttribute;
import com.android.tools.r8.graph.TreeFixerBase;
import com.android.tools.r8.ir.conversion.ExtraUnusedNullParameter;
import com.android.tools.r8.shaking.AnnotationFixer;
import com.android.tools.r8.utils.OptionalBool;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Optional;
import java.util.Set;
/**
* The tree fixer traverses all program classes and finds and fixes references to old classes which
* have been remapped to new classes by the class merger. While doing so, all updated changes are
* tracked in {@link TreeFixer#lensBuilder}.
*/
class TreeFixer extends TreeFixerBase {
private final AppView<? extends AppInfoWithClassHierarchy> appView;
private final HorizontallyMergedClasses mergedClasses;
private final HorizontalClassMergerGraphLens.Builder lensBuilder;
private final DexItemFactory dexItemFactory;
private final SyntheticArgumentClass syntheticArgumentClass;
private final BiMap<DexMethodSignature, DexMethodSignature> reservedInterfaceSignatures =
HashBiMap.create();
public TreeFixer(
AppView<? extends AppInfoWithClassHierarchy> appView,
HorizontallyMergedClasses mergedClasses,
HorizontalClassMergerGraphLens.Builder lensBuilder,
SyntheticArgumentClass syntheticArgumentClass) {
super(appView);
this.appView = appView;
this.mergedClasses = mergedClasses;
this.lensBuilder = lensBuilder;
this.syntheticArgumentClass = syntheticArgumentClass;
this.dexItemFactory = appView.dexItemFactory();
}
/**
* Lets assume the following initial classes, where the class B should be merged into A: <code>
* class A {
* public A(A a) { ... }
* public A(A a, int v) { ... }
* public A(B b) { ... }
* public A(B b, int v) { ... }
* }
*
* class B {
* public B(A a) { ... }
* public B(B b) { ... }
* }
* </code>
*
* <p>The {@link ClassMerger} merges the constructors {@code A.<init>(B)} and {@code B.<init>(B)}
* into the constructor {@code A.<init>(B, int)} to prevent any collisions when merging the
* constructor into A. The extra integer argument determines which class' constructor is called.
* The SynthArg is used to prevent a collision with the existing {@code A.<init>(B, int)}
* constructor. All constructors {@code A.<init>(A, ...)} generate a constructor {@code
* A.<init>(A, int, SynthClass)} but are otherwise ignored. During ClassMerging the constructor
* produces the following mappings in the graph lens builder:
*
* <ul>
* <li>{@code B.<init>(B) <--> A.<init>(B, int, SynthArg)}
* <li>{@code A.<init>(B) <--> A.<init>(B, int, SynthArg)} (This mapping is representative)
* <li>{@code A.constructor$B(B) ---> A.constructor$B(B)}
* <li>{@code B.<init>(B) <--- A.constructor$B(B)}
* </ul>
*
* <p>Note: The identity mapping is needed so that the method is remapped in the forward direction
* if there are changes in the tree fixer. Otherwise, methods are only remapped in directions they
* are already mapped in.
*
* <p>During the fixup, all type references to B are changed into A. This causes a collision
* between {@code A.<init>(A, int, SynthClass)} and {@code A.<init>(B, int, SynthClass)}. This
* collision should be fixed by adding an extra argument to {@code A.<init>(B, int, SynthClass)}.
* The TreeFixer generates the following mapping of renamed methods:
*
* <ul>
* <li>{@code A.<init>(B, int, SynthArg) <--> A.<init>(A, int, SynthArg, ExtraArg)}
* <li>{@code A.constructor$B(B) <--> A.constructor$B(A)}
* </ul>
*
* <p>This rewrites the previous method mappings to:
*
* <ul>
* <li>{@code B.<init>(B) <--- A.constructor$B(A)}
* <li>{@code A.constructor$B(B) ---> A.constructor$B(A)}
* <li>{@code B.<init>(B) <--> A.<init>(A, int, SynthArg, ExtraArg)}
* <li>{@code A.<init>(B) <--> A.<init>(A, int, SynthArg, ExtraArg)} (including represents)
* </ul>
*/
public HorizontalClassMergerGraphLens fixupTypeReferences() {
List<DexProgramClass> classes = appView.appInfo().classesWithDeterministicOrder();
Iterables.filter(classes, DexProgramClass::isInterface).forEach(this::fixupInterfaceClass);
classes.forEach(this::fixupAttributes);
classes.forEach(this::fixupProgramClassSuperTypes);
SubtypingForrestForClasses subtypingForrest = new SubtypingForrestForClasses(appView);
// TODO(b/170078037): parallelize this code segment.
for (DexProgramClass root : subtypingForrest.getProgramRoots()) {
subtypingForrest.traverseNodeDepthFirst(root, HashBiMap.create(), this::fixupProgramClass);
}
HorizontalClassMergerGraphLens lens = lensBuilder.build(appView, mergedClasses);
new AnnotationFixer(lens).run(appView.appInfo().classes());
return lens;
}
private void fixupAttributes(DexProgramClass clazz) {
if (clazz.hasEnclosingMethodAttribute()) {
EnclosingMethodAttribute enclosingMethodAttribute = clazz.getEnclosingMethodAttribute();
if (mergedClasses.hasBeenMergedIntoDifferentType(
enclosingMethodAttribute.getEnclosingType())) {
clazz.clearEnclosingMethodAttribute();
} else {
clazz.setEnclosingMethodAttribute(fixupEnclosingMethodAttribute(enclosingMethodAttribute));
}
}
clazz.setInnerClasses(fixupInnerClassAttributes(clazz.getInnerClasses()));
clazz.setNestHostAttribute(fixupNestHost(clazz.getNestHostClassAttribute()));
clazz.setNestMemberAttributes(fixupNestMemberAttributes(clazz.getNestMembersClassAttributes()));
}
private void fixupProgramClassSuperTypes(DexProgramClass clazz) {
clazz.superType = fixupType(clazz.superType);
clazz.setInterfaces(fixupInterfaces(clazz, clazz.getInterfaces()));
}
private BiMap<DexMethodSignature, DexMethodSignature> fixupProgramClass(
DexProgramClass clazz, BiMap<DexMethodSignature, DexMethodSignature> remappedVirtualMethods) {
assert !clazz.isInterface();
// TODO(b/169395592): ensure merged classes have been removed using:
// assert !mergedClasses.hasBeenMergedIntoDifferentType(clazz.type);
BiMap<DexMethodSignature, DexMethodSignature> remappedClassVirtualMethods =
HashBiMap.create(remappedVirtualMethods);
Set<DexMethodSignature> newMethodReferences = Sets.newHashSet();
clazz
.getMethodCollection()
.replaceAllVirtualMethods(
method -> fixupVirtualMethod(remappedClassVirtualMethods, newMethodReferences, method));
clazz
.getMethodCollection()
.replaceAllDirectMethods(method -> fixupDirectMethod(newMethodReferences, method));
fixupFields(clazz.staticFields(), clazz::setStaticField);
fixupFields(clazz.instanceFields(), clazz::setInstanceField);
lensBuilder.commitPendingUpdates();
return remappedClassVirtualMethods;
}
private DexEncodedMethod fixupVirtualInterfaceMethod(DexEncodedMethod method) {
DexMethod originalMethodReference = method.getReference();
// Don't process this method if it does not refer to a merge class type.
boolean referencesMergeClass =
Iterables.any(
originalMethodReference.getProto().getBaseTypes(dexItemFactory),
mergedClasses::hasBeenMergedOrIsMergeTarget);
if (!referencesMergeClass) {
return method;
}
DexMethodSignature originalMethodSignature = originalMethodReference.getSignature();
DexMethodSignature newMethodSignature =
reservedInterfaceSignatures.get(originalMethodSignature);
if (newMethodSignature == null) {
newMethodSignature = fixupMethodReference(originalMethodReference).getSignature();
// If the signature is already reserved by another interface, find a fresh one.
if (reservedInterfaceSignatures.containsValue(newMethodSignature)) {
DexString name =
dexItemFactory.createGloballyFreshMemberString(
originalMethodReference.getName().toSourceString());
newMethodSignature = newMethodSignature.withName(name);
}
assert !reservedInterfaceSignatures.containsValue(newMethodSignature);
reservedInterfaceSignatures.put(originalMethodSignature, newMethodSignature);
}
DexMethod newMethodReference =
newMethodSignature.withHolder(originalMethodReference, dexItemFactory);
lensBuilder.fixupMethod(originalMethodReference, newMethodReference);
return method.toTypeSubstitutedMethod(newMethodReference);
}
private void fixupInterfaceClass(DexProgramClass iface) {
Set<DexMethodSignature> newDirectMethods = new LinkedHashSet<>();
iface
.getMethodCollection()
.replaceDirectMethods(method -> fixupDirectMethod(newDirectMethods, method));
iface.getMethodCollection().replaceVirtualMethods(this::fixupVirtualInterfaceMethod);
fixupFields(iface.staticFields(), iface::setStaticField);
fixupFields(iface.instanceFields(), iface::setInstanceField);
lensBuilder.commitPendingUpdates();
}
private DexTypeList fixupInterfaces(DexProgramClass clazz, DexTypeList interfaceTypes) {
Set<DexType> seen = Sets.newIdentityHashSet();
return interfaceTypes.map(
interfaceType -> {
DexType rewrittenInterfaceType = mapClassType(interfaceType);
assert rewrittenInterfaceType != clazz.getType();
return seen.add(rewrittenInterfaceType) ? rewrittenInterfaceType : null;
});
}
private DexEncodedMethod fixupProgramMethod(
DexMethod newMethodReference, DexEncodedMethod method) {
DexMethod originalMethodReference = method.getReference();
if (newMethodReference == originalMethodReference) {
return method;
}
lensBuilder.fixupMethod(originalMethodReference, newMethodReference);
DexEncodedMethod newMethod = method.toTypeSubstitutedMethod(newMethodReference);
if (newMethod.isNonPrivateVirtualMethod()) {
// Since we changed the return type or one of the parameters, this method cannot be a
// classpath or library method override, since we only class merge program classes.
assert !method.isLibraryMethodOverride().isTrue();
newMethod.setLibraryMethodOverride(OptionalBool.FALSE);
}
return newMethod;
}
private DexEncodedMethod fixupDirectMethod(
Set<DexMethodSignature> newMethods, DexEncodedMethod method) {
DexMethod originalMethodReference = method.getReference();
// Fix all type references in the method prototype.
DexMethod newMethodReference = fixupMethodReference(originalMethodReference);
if (newMethods.contains(newMethodReference.getSignature())) {
// If the method collides with a direct method on the same class then rename it to a globally
// fresh name and record the signature.
if (method.isInstanceInitializer()) {
// If the method is an instance initializer, then add extra nulls.
newMethodReference =
dexItemFactory.createInstanceInitializerWithFreshProto(
newMethodReference,
syntheticArgumentClass.getArgumentClasses(),
tryMethod -> !newMethods.contains(tryMethod.getSignature()));
int extraNulls = newMethodReference.getArity() - originalMethodReference.getArity();
lensBuilder.addExtraParameters(
originalMethodReference,
Collections.nCopies(extraNulls, new ExtraUnusedNullParameter()));
} else {
newMethodReference =
dexItemFactory.createFreshMethodNameWithoutHolder(
newMethodReference.getName().toSourceString(),
newMethodReference.proto,
newMethodReference.holder,
tryMethod ->
!reservedInterfaceSignatures.containsValue(tryMethod.getSignature())
&& !newMethods.contains(tryMethod.getSignature()));
}
}
boolean changed = newMethods.add(newMethodReference.getSignature());
assert changed;
return fixupProgramMethod(newMethodReference, method);
}
private DexMethodSignature lookupReservedVirtualName(
DexMethod originalMethodReference,
BiMap<DexMethodSignature, DexMethodSignature> renamedClassVirtualMethods) {
DexMethodSignature originalSignature = originalMethodReference.getSignature();
// Determine if the original method has been rewritten by a parent class
DexMethodSignature renamedVirtualName = renamedClassVirtualMethods.get(originalSignature);
if (renamedVirtualName == null) {
// Determine if there is a signature mapping.
DexMethodSignature mappedInterfaceSignature =
reservedInterfaceSignatures.get(originalSignature);
if (mappedInterfaceSignature != null) {
renamedVirtualName = mappedInterfaceSignature;
}
} else {
assert !reservedInterfaceSignatures.containsKey(originalSignature);
}
return renamedVirtualName;
}
private DexEncodedMethod fixupVirtualMethod(
BiMap<DexMethodSignature, DexMethodSignature> renamedClassVirtualMethods,
Set<DexMethodSignature> newMethods,
DexEncodedMethod method) {
DexMethod originalMethodReference = method.getReference();
DexMethodSignature originalSignature = originalMethodReference.getSignature();
DexMethodSignature renamedVirtualName =
lookupReservedVirtualName(originalMethodReference, renamedClassVirtualMethods);
// Fix all type references in the method prototype.
DexMethodSignature newSignature = fixupMethodSignature(originalSignature);
if (renamedVirtualName != null) {
// If the method was renamed in a parent, rename it in the child.
newSignature = renamedVirtualName;
assert !newMethods.contains(newSignature);
} else if (reservedInterfaceSignatures.containsValue(newSignature)
|| newMethods.contains(newSignature)
|| renamedClassVirtualMethods.containsValue(newSignature)) {
// If the method potentially collides with an interface method or with another virtual method
// rename it to a globally fresh name and record the name.
newSignature =
dexItemFactory.createFreshMethodSignatureName(
originalMethodReference.getName().toSourceString(),
null,
newSignature.getProto(),
trySignature ->
!reservedInterfaceSignatures.containsValue(trySignature)
&& !newMethods.contains(trySignature)
&& !renamedClassVirtualMethods.containsValue(trySignature));
// Record signature renaming so that subclasses perform the identical rename.
renamedClassVirtualMethods.put(originalSignature, newSignature);
} else {
// There was no reserved name and the new signature is available.
if (Iterables.any(
newSignature.getProto().getParameterBaseTypes(dexItemFactory),
mergedClasses::isMergeTarget)) {
// If any of the parameter types have been merged, record the signature mapping.
renamedClassVirtualMethods.put(originalSignature, newSignature);
}
}
boolean changed = newMethods.add(newSignature);
assert changed;
DexMethod newMethodReference =
newSignature.withHolder(fixupType(originalMethodReference.holder), dexItemFactory);
return fixupProgramMethod(newMethodReference, method);
}
private void fixupFields(List<DexEncodedField> fields, FieldSetter setter) {
if (fields == null) {
return;
}
Set<DexField> existingFields = Sets.newIdentityHashSet();
for (int i = 0; i < fields.size(); i++) {
DexEncodedField oldField = fields.get(i);
DexField oldFieldReference = oldField.getReference();
DexField newFieldReference = fixupFieldReference(oldFieldReference);
// Rename the field if it already exists.
if (!existingFields.add(newFieldReference)) {
DexField template = newFieldReference;
newFieldReference =
dexItemFactory.createFreshMember(
tryName ->
Optional.of(template.withName(tryName, dexItemFactory))
.filter(tryMethod -> !existingFields.contains(tryMethod)),
newFieldReference.name.toSourceString());
boolean added = existingFields.add(newFieldReference);
assert added;
}
if (newFieldReference != oldFieldReference) {
lensBuilder.fixupField(oldFieldReference, newFieldReference);
setter.setField(i, oldField.toTypeSubstitutedField(newFieldReference));
}
}
}
@Override
public DexType mapClassType(DexType type) {
return mergedClasses.getMergeTargetOrDefault(type);
}
@Override
public void recordClassChange(DexType from, DexType to) {
// Classes are not changed but in-place updated.
throw new Unreachable();
}
@Override
public void recordFieldChange(DexField from, DexField to) {
// Fields are manually changed in 'fixupFields' above.
throw new Unreachable();
}
@Override
public void recordMethodChange(DexMethod from, DexMethod to) {
// Methods are manually changed in 'fixupMethods' above.
throw new Unreachable();
}
}