1// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4package com.android.tools.r8.optimize;
5
6import com.android.tools.r8.errors.Unreachable;
7import com.android.tools.r8.graph.DexClass;
8import com.android.tools.r8.graph.DexEncodedField;
9import com.android.tools.r8.graph.DexEncodedMethod;
10import com.android.tools.r8.graph.DexField;
11import com.android.tools.r8.graph.DexMethod;
12import com.android.tools.r8.graph.DexProgramClass;
13import com.android.tools.r8.graph.DexType;
14import com.android.tools.r8.graph.GraphLense;
15import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
16import com.google.common.collect.Sets;
17import java.util.Set;
18import java.util.function.BiConsumer;
19import java.util.function.BiFunction;
20import java.util.function.Function;
21
22public class MemberRebindingAnalysis {
23
24  private final AppInfoWithLiveness appInfo;
25  private final GraphLense lense;
26  private final GraphLense.Builder builder = GraphLense.builder();
27
28  public MemberRebindingAnalysis(AppInfoWithLiveness appInfo, GraphLense lense) {
29    assert lense.isContextFree();
30    this.appInfo = appInfo;
31    this.lense = lense;
32  }
33
34  private DexMethod validTargetFor(DexMethod target, DexMethod original,
35      BiFunction<DexClass, DexMethod, DexEncodedMethod> lookup) {
36    DexClass clazz = appInfo.definitionFor(target.getHolder());
37    assert clazz != null;
38    if (!clazz.isLibraryClass()) {
39      return target;
40    }
41    DexType newHolder;
42    if (clazz.isInterface()) {
43      newHolder = firstLibraryClassForInterfaceTarget(target, original.getHolder(), lookup);
44    } else {
45      newHolder = firstLibraryClass(target.getHolder(), original.getHolder());
46    }
47    return appInfo.dexItemFactory.createMethod(newHolder, original.proto, original.name);
48  }
49
50  private DexField validTargetFor(DexField target, DexField original,
51      BiFunction<DexClass, DexField, DexEncodedField> lookup) {
52    DexClass clazz = appInfo.definitionFor(target.getHolder());
53    assert clazz != null;
54    if (!clazz.isLibraryClass()) {
55      return target;
56    }
57    DexType newHolder;
58    if (clazz.isInterface()) {
59      newHolder = firstLibraryClassForInterfaceTarget(target, original.getHolder(), lookup);
60    } else {
61      newHolder = firstLibraryClass(target.getHolder(), original.getHolder());
62    }
63    return appInfo.dexItemFactory.createField(newHolder, original.type, original.name);
64  }
65
66  private <T> DexType firstLibraryClassForInterfaceTarget(T target, DexType current,
67      BiFunction<DexClass, T, ?> lookup) {
68    DexClass clazz = appInfo.definitionFor(current);
69    Object potential = lookup.apply(clazz, target);
70    if (potential != null) {
71      // Found, return type.
72      return current;
73    }
74    if (clazz.superType != null) {
75      DexType matchingSuper = firstLibraryClassForInterfaceTarget(target, clazz.superType, lookup);
76      if (matchingSuper != null) {
77        // Found in supertype, return first libray class.
78        return clazz.isLibraryClass() ? current : matchingSuper;
79      }
80    }
81    for (DexType iface : clazz.interfaces.values) {
82      DexType matchingIface = firstLibraryClassForInterfaceTarget(target, iface, lookup);
83      if (matchingIface != null) {
84        // Found in interface, return first library class.
85        return clazz.isLibraryClass() ? current : matchingIface;
86      }
87    }
88    return null;
89  }
90
91  private DexType firstLibraryClass(DexType top, DexType bottom) {
92    assert appInfo.definitionFor(top).isLibraryClass();
93    DexClass searchClass = appInfo.definitionFor(bottom);
94    while (!searchClass.isLibraryClass()) {
95      searchClass = appInfo.definitionFor(searchClass.superType);
96    }
97    return searchClass.type;
98  }
99
100  private DexEncodedMethod virtualLookup(DexMethod method) {
101    return appInfo.lookupVirtualDefinition(method.getHolder(), method);
102  }
103
104  private DexEncodedMethod superLookup(DexMethod method) {
105    return appInfo.lookupVirtualTarget(method.getHolder(), method);
106  }
107
108  private void computeMethodRebinding(Set<DexMethod> methods,
109      Function<DexMethod, DexEncodedMethod> lookupTarget,
110      BiFunction<DexClass, DexMethod, DexEncodedMethod> lookupTargetOnClass,
111      BiConsumer<DexProgramClass, DexEncodedMethod> addMethod) {
112    for (DexMethod method : methods) {
113      method = lense.lookupMethod(method, null);
114      // We can safely ignore array types, as the corresponding methods are defined in a library.
115      if (!method.getHolder().isClassType()) {
116        continue;
117      }
118      DexClass originalClass = appInfo.definitionFor(method.holder);
119      // We can safely ignore calls to library classes, as those cannot be rebound.
120      if (originalClass == null || originalClass.isLibraryClass()) {
121        continue;
122      }
123      DexEncodedMethod target = lookupTarget.apply(method);
124      // Rebind to the lowest library class or program class.
125      if (target != null && target.method != method) {
126        DexClass targetClass = appInfo.definitionFor(target.method.holder);
127        // If the targetclass is not public but the targeted method is, we might run into
128        // visibility problems when rebinding.
129        if (!targetClass.accessFlags.isPublic() && target.accessFlags.isPublic()) {
130          // If the original class is public and this method is public, it might have been called
131          // from anywhere, so we need a bridge. Likewise, if the original is in a different
132          // package, we might need a bridge, too.
133          String packageDescriptor =
134              originalClass.accessFlags.isPublic() ? null : method.holder.getPackageDescriptor();
135          if (packageDescriptor == null
136              || !packageDescriptor.equals(targetClass.type.getPackageDescriptor())) {
137            DexProgramClass bridgeHolder = findBridgeMethodHolder(originalClass, targetClass,
138                packageDescriptor);
139            assert bridgeHolder != null;
140            DexEncodedMethod bridgeMethod = target
141                .toForwardingMethod(bridgeHolder, appInfo.dexItemFactory);
142            addMethod.accept(bridgeHolder, bridgeMethod);
143            assert lookupTarget.apply(method) == bridgeMethod;
144            target = bridgeMethod;
145          }
146        }
147        builder.map(method, validTargetFor(target.method, method, lookupTargetOnClass));
148      }
149    }
150  }
151
152  private DexProgramClass findBridgeMethodHolder(DexClass originalClass, DexClass targetClass,
153      String packageDescriptor) {
154    if (originalClass == targetClass || originalClass.isLibraryClass()) {
155      return null;
156    }
157    DexProgramClass newHolder = null;
158    // Recurse through supertype chain.
159    if (originalClass.superType.isSubtypeOf(targetClass.type, appInfo)) {
160      DexClass superClass = appInfo.definitionFor(originalClass.superType);
161      newHolder = findBridgeMethodHolder(superClass, targetClass, packageDescriptor);
162    } else {
163      for (DexType iface : originalClass.interfaces.values) {
164        if (iface.isSubtypeOf(targetClass.type, appInfo)) {
165          DexClass interfaceClass = appInfo.definitionFor(iface);
166          newHolder = findBridgeMethodHolder(interfaceClass, targetClass, packageDescriptor);
167        }
168      }
169    }
170    if (newHolder != null) {
171      // A supertype fulfills the visibility requirements.
172      return newHolder;
173    } else if (originalClass.accessFlags.isPublic()
174        || originalClass.type.getPackageDescriptor().equals(packageDescriptor)) {
175      // This class is visible. Return it if it is a program class, otherwise null.
176      return originalClass.asProgramClass();
177    }
178    return null;
179  }
180
181  private void computeFieldRebinding(Set<DexField> fields,
182      BiFunction<DexType, DexField, DexEncodedField> lookup,
183      BiFunction<DexClass, DexField, DexEncodedField> lookupTargetOnClass) {
184    for (DexField field : fields) {
185      field = lense.lookupField(field, null);
186      DexEncodedField target = lookup.apply(field.getHolder(), field);
187      // Rebind to the lowest library class or program class. Do not rebind accesses to fields that
188      // are not public, as this might lead to access violation errors.
189      if (target != null && target.field != field && isVisibleFromOtherClasses(target)) {
190        builder.map(field, validTargetFor(target.field, field, lookupTargetOnClass));
191      }
192    }
193  }
194
195  private boolean isVisibleFromOtherClasses(DexEncodedField field) {
196    // If the field is not public, the visibility on the class can not be a further constraint.
197    if (!field.accessFlags.isPublic()) {
198      return true;
199    }
200    // If the field is public, then a non-public holder class will further constrain visibility.
201    return appInfo.definitionFor(field.field.getHolder()).accessFlags.isPublic();
202  }
203
204  private static void privateMethodsCheck(DexProgramClass clazz, DexEncodedMethod method) {
205    throw new Unreachable("Direct invokes should not require forwarding.");
206  }
207
208  public GraphLense run() {
209    computeMethodRebinding(appInfo.virtualInvokes, this::virtualLookup,
210        DexClass::findVirtualTarget, DexProgramClass::addVirtualMethod);
211    computeMethodRebinding(appInfo.superInvokes, this::superLookup, DexClass::findVirtualTarget,
212        DexProgramClass::addVirtualMethod);
213    computeMethodRebinding(appInfo.directInvokes, appInfo::lookupDirectTarget,
214        DexClass::findDirectTarget, MemberRebindingAnalysis::privateMethodsCheck);
215    computeMethodRebinding(appInfo.staticInvokes, appInfo::lookupStaticTarget,
216        DexClass::findDirectTarget, DexProgramClass::addStaticMethod);
217
218    computeFieldRebinding(Sets.union(appInfo.staticFieldReads, appInfo.staticFieldWrites),
219        appInfo::lookupStaticTarget, DexClass::findStaticTarget);
220    computeFieldRebinding(Sets.union(appInfo.instanceFieldReads, appInfo.instanceFieldWrites),
221        appInfo::lookupInstanceTarget, DexClass::findInstanceTarget);
222    return builder.build(lense, appInfo.dexItemFactory);
223  }
224}
225