blob: dd6af4aac62f5bbf27ea1f28a105067147b935a2 [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.repackaging;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexDefinition;
import com.android.tools.r8.graph.DexEncodedMember;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.ProgramField;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.graph.ProgramPackage;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.ThreadUtils;
import com.android.tools.r8.utils.WorkList;
import com.google.common.collect.Sets;
import java.util.ArrayList;
import java.util.Collection;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
/**
* An undirected graph that contains a node for each class, field, and method in a given package.
*
* <p>An edge X <-> Y is added if X contains a reference to Y and Y is only accessible to X if X and
* Y are in the same package.
*
* <p>Once the graph is populated, we compute the set of reachable nodes from the set of root nodes
* that cannot be repackaged due to a -keep rule. The remaining nodes in the graph can all be
* repackaged.
*/
public class RepackagingConstraintGraph {
private final AppView<AppInfoWithLiveness> appView;
private final ProgramPackage pkg;
private final Map<DexDefinition, Node> nodes = new IdentityHashMap<>();
private final Set<Node> pinnedNodes = Sets.newIdentityHashSet();
private final Node libraryBoundaryNode;
public RepackagingConstraintGraph(AppView<AppInfoWithLiveness> appView, ProgramPackage pkg) {
this.appView = appView;
this.pkg = pkg;
libraryBoundaryNode = createNode(appView.definitionFor(appView.dexItemFactory().objectType));
pinnedNodes.add(libraryBoundaryNode);
}
/** Returns true if all classes in the package can be repackaged. */
public boolean initializeGraph() {
// Add all the items in the package into the graph. This way we know which items belong to the
// package without having to extract package descriptor strings and comparing them with the
// package descriptor.
boolean hasPinnedItem = false;
for (DexProgramClass clazz : pkg) {
boolean isPinned = !appView.appInfo().isRepackagingAllowed(clazz);
Node classNode = createNode(clazz);
if (isPinned) {
pinnedNodes.add(classNode);
}
for (DexEncodedMember<?, ?> member : clazz.members()) {
Node memberNode = createNode(member);
classNode.addNeighbor(memberNode);
}
hasPinnedItem |= isPinned;
}
return !hasPinnedItem;
}
private Node createNode(DexDefinition definition) {
Node node = new Node(definition);
nodes.put(definition, node);
return node;
}
Node getNode(DexDefinition definition) {
if (definition.isNotProgramDefinition(appView)) {
String packageDescriptor = definition.getContextType().getPackageDescriptor();
if (packageDescriptor.equals(pkg.getPackageDescriptor())) {
return libraryBoundaryNode;
}
return null;
}
return nodes.get(definition);
}
public void populateConstraints(ExecutorService executorService) throws ExecutionException {
// Concurrently add references from methods to the graph.
ThreadUtils.processItems(
pkg::forEachMethod, this::registerReferencesFromMethod, executorService);
// TODO(b/165783399): Evaluate if it is worth to parallelize this. The work per field and class
// should be little, so it may not be.
pkg.forEachClass(this::registerReferencesFromClass);
pkg.forEachField(this::registerReferencesFromField);
}
private void registerReferencesFromClass(DexProgramClass clazz) {
RepackagingUseRegistry registry =
new RepackagingUseRegistry(appView, this, clazz, libraryBoundaryNode);
// Trace the references to the immediate super types.
registry.registerTypeReference(clazz.getSuperType());
clazz.interfaces.forEach(registry::registerTypeReference);
// Trace the references from the class annotations.
new RepackagingAnnotationTracer(appView, registry).trace(clazz.annotations());
// Trace the references in the nest host and/or members.
if (clazz.isInANest()) {
if (clazz.isNestHost()) {
clazz.forEachNestMember(registry::registerTypeReference);
} else {
assert clazz.isNestMember();
registry.registerTypeReference(clazz.getNestHost());
}
}
// Trace the references to the inner and outer classes.
clazz
.getInnerClasses()
.forEach(
innerClassAttribute ->
registry.registerInnerClassAttribute(clazz, innerClassAttribute));
// Trace the references from the enclosing method and nest attributes.
registry.registerEnclosingMethodAttribute(clazz.getEnclosingMethodAttribute());
registry.registerNestHostAttribute(clazz.getNestHostClassAttribute());
registry.registerNestMemberClassAttributes(clazz.getNestMembersClassAttributes());
}
private void registerReferencesFromField(ProgramField field) {
RepackagingUseRegistry registry =
new RepackagingUseRegistry(appView, this, field, libraryBoundaryNode);
// Trace the type of the field.
registry.registerTypeReference(field.getReference().getType());
// Trace the references in the field annotations.
new RepackagingAnnotationTracer(appView, registry).trace(field.getDefinition().annotations());
}
private void registerReferencesFromMethod(ProgramMethod method) {
DexEncodedMethod definition = method.getDefinition();
RepackagingUseRegistry registry =
new RepackagingUseRegistry(appView, this, method, libraryBoundaryNode);
// Trace the type references in the method signature.
definition.getProto().forEachType(registry::registerTypeReference);
// Check if this overrides a package-private method.
DexClass superClass =
appView.definitionFor(method.getHolder().getSuperType(), method.getHolder());
if (superClass != null) {
registry.registerMemberAccess(
appView.appInfo().resolveMethodOn(superClass, method.getReference()));
}
// Trace the references in the method and method parameter annotations.
RepackagingAnnotationTracer annotationTracer =
new RepackagingAnnotationTracer(appView, registry);
annotationTracer.trace(definition.annotations());
annotationTracer.trace(definition.getParameterAnnotations());
// Trace the references from the code.
if (definition.hasCode()) {
definition.getCode().registerCodeReferences(method, registry);
}
}
public Collection<DexProgramClass> computeClassesToRepackage() {
WorkList<Node> worklist = WorkList.newIdentityWorkList(pinnedNodes);
while (worklist.hasNext()) {
Node pinnedNode = worklist.next();
for (Node neighbor : pinnedNode.getNeighbors()) {
// Mark all the immediate neighbors as ineligible for repackaging and continue the tracing
// from the neighbors.
worklist.addIfNotSeen(neighbor);
}
}
Set<Node> pinnedNodes = worklist.getSeenSet();
List<DexProgramClass> classesToRepackage = new ArrayList<>();
for (DexProgramClass clazz : pkg) {
if (!pinnedNodes.contains(getNode(clazz))) {
classesToRepackage.add(clazz);
}
}
return classesToRepackage;
}
static class Node {
private final DexDefinition definitionForDebugging;
private final Set<Node> neighbors = Sets.newConcurrentHashSet();
Node(DexDefinition definitionForDebugging) {
this.definitionForDebugging = definitionForDebugging;
}
public void addNeighbor(Node neighbor) {
neighbors.add(neighbor);
neighbor.neighbors.add(this);
}
public Set<Node> getNeighbors() {
return neighbors;
}
@Override
public String toString() {
return "Node(" + definitionForDebugging.getReference().toSourceString() + ")";
}
}
}