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. 4 package com.android.tools.r8.graph; 5 6 import com.google.common.collect.ImmutableSet; 7 import com.google.common.collect.Sets; 8 import java.util.Collections; 9 import java.util.HashSet; 10 import java.util.Hashtable; 11 import java.util.Map; 12 import java.util.Set; 13 import java.util.function.Function; 14 15 public class AppInfoWithSubtyping extends AppInfo { 16 17 // Set of missing classes, discovered during subtypeMap computation. 18 private Set<DexType> missingClasses = Sets.newIdentityHashSet(); 19 // Map from types to their subtypes. 20 private final Hashtable<DexType, ImmutableSet<DexType>> subtypeMap = new Hashtable<>(); 21 AppInfoWithSubtyping(DexApplication application)22 public AppInfoWithSubtyping(DexApplication application) { 23 super(application); 24 populateSubtypeMap(application.getFullClassMap(), application.dexItemFactory); 25 } 26 AppInfoWithSubtyping(AppInfoWithSubtyping previous)27 protected AppInfoWithSubtyping(AppInfoWithSubtyping previous) { 28 super(previous); 29 missingClasses.addAll(previous.missingClasses); 30 subtypeMap.putAll(previous.subtypeMap); 31 } 32 AppInfoWithSubtyping(AppInfoWithSubtyping previous, GraphLense lense)33 protected AppInfoWithSubtyping(AppInfoWithSubtyping previous, GraphLense lense) { 34 super(previous, lense); 35 // Recompute subtype map if we have modified the graph. 36 populateSubtypeMap(previous.app.getFullClassMap(), dexItemFactory); 37 } 38 getMissingClasses()39 public Set<DexType> getMissingClasses() { 40 return Collections.unmodifiableSet(missingClasses); 41 } 42 subtypes(DexType type)43 public ImmutableSet<DexType> subtypes(DexType type) { 44 assert type.isClassType(); 45 ImmutableSet<DexType> subtypes = subtypeMap.get(type); 46 return subtypes == null ? ImmutableSet.of() : subtypes; 47 } 48 populateSuperType(Hashtable<DexType, Set<DexType>> map, DexType superType, DexClass baseClass, Function<DexType, DexClass> definitions)49 private void populateSuperType(Hashtable<DexType, Set<DexType>> map, DexType superType, 50 DexClass baseClass, Function<DexType, DexClass> definitions) { 51 if (superType != null) { 52 Set<DexType> set = map.computeIfAbsent(superType, ignore -> new HashSet<>()); 53 if (set.add(baseClass.type)) { 54 // Only continue recursion if type has been added to set. 55 populateAllSuperTypes(map, superType, baseClass, definitions); 56 } 57 } 58 } 59 populateAllSuperTypes(Hashtable<DexType, Set<DexType>> map, DexType holder, DexClass baseClass, Function<DexType, DexClass> definitions)60 private void populateAllSuperTypes(Hashtable<DexType, Set<DexType>> map, DexType holder, 61 DexClass baseClass, Function<DexType, DexClass> definitions) { 62 DexClass holderClass = definitions.apply(holder); 63 // Skip if no corresponding class is found. 64 if (holderClass != null) { 65 populateSuperType(map, holderClass.superType, baseClass, definitions); 66 if (holderClass.superType != null) { 67 holderClass.superType.addDirectSubtype(holder); 68 } else { 69 // We found java.lang.Object 70 assert dexItemFactory.objectType == holder; 71 } 72 for (DexType inter : holderClass.interfaces.values) { 73 populateSuperType(map, inter, baseClass, definitions); 74 inter.addInterfaceSubtype(holder); 75 } 76 } else { 77 if (!baseClass.isLibraryClass()) { 78 missingClasses.add(holder); 79 } 80 // The subtype chain is broken, at least make this type a subtype of Object. 81 if (holder != dexItemFactory.objectType) { 82 dexItemFactory.objectType.addDirectSubtype(holder); 83 } 84 } 85 } 86 populateSubtypeMap(Map<DexType, DexClass> classes, DexItemFactory dexItemFactory)87 private void populateSubtypeMap(Map<DexType, DexClass> classes, DexItemFactory dexItemFactory) { 88 dexItemFactory.clearSubtypeInformation(); 89 dexItemFactory.objectType.tagAsSubtypeRoot(); 90 Hashtable<DexType, Set<DexType>> map = new Hashtable<>(); 91 for (Map.Entry<DexType, DexClass> entry : classes.entrySet()) { 92 populateAllSuperTypes(map, entry.getKey(), entry.getValue(), classes::get); 93 } 94 for (Map.Entry<DexType, Set<DexType>> entry : map.entrySet()) { 95 subtypeMap.put(entry.getKey(), ImmutableSet.copyOf(entry.getValue())); 96 } 97 assert DexType.validateLevelsAreCorrect(classes::get, dexItemFactory); 98 } 99 100 // For mapping invoke virtual instruction to target methods. lookupVirtualTargets(DexMethod method)101 public Set<DexEncodedMethod> lookupVirtualTargets(DexMethod method) { 102 Set<DexEncodedMethod> result = new HashSet<>(); 103 // First add the target for receiver type method.type. 104 DexClass root = definitionFor(method.holder); 105 if (root == null) { 106 // type specified in method does not have a materialized class. 107 return null; 108 } 109 DexEncodedMethod topMethod = lookupVirtualTarget(method.holder, method); 110 // The top method might be absent if this is an abstract class. 111 if (topMethod != null) { 112 result.add(topMethod); 113 } else { 114 if (!holderIsAbstract(method)) { 115 // This method is missing and the program we have is invalid. 116 // TODO(herhut): Find a better way to handle missing targets. 117 return Collections.emptySet(); 118 } 119 } 120 // Add all matching targets from the subclass hierarchy. 121 Set<DexType> set = subtypes(method.holder); 122 if (set != null) { 123 for (DexType type : set) { 124 DexClass clazz = definitionFor(type); 125 if (!clazz.isInterface()) { 126 DexEncodedMethod t = clazz.findVirtualTarget(method); 127 if (t != null) { 128 result.add(t); 129 } 130 } 131 } 132 } 133 return result; 134 } 135 136 /** 137 * For mapping invoke virtual instruction to single target method. 138 */ lookupSingleVirtualTarget(DexMethod method)139 public DexEncodedMethod lookupSingleVirtualTarget(DexMethod method) { 140 assert method != null; 141 DexClass holder = definitionFor(method.holder); 142 if ((holder == null) || holder.isLibraryClass()) { 143 return null; 144 } 145 if (method.isSingleVirtualMethodCached()) { 146 return method.getSingleVirtualMethodCache(); 147 } 148 DexEncodedMethod result = null; 149 // First add the target for receiver type method.type. 150 DexEncodedMethod topMethod = lookupVirtualTarget(method.holder, method); 151 // The top method might be absent if this is an abstract class. 152 if (topMethod != null) { 153 result = topMethod; 154 } else { 155 if (!holderIsAbstract(method)) { 156 return null; 157 } 158 } 159 // Search for matching target in subtype hierarchy. 160 Set<DexType> set = subtypes(method.holder); 161 if (set != null) { 162 for (DexType type : set) { 163 DexClass clazz = definitionFor(type); 164 if (!clazz.isInterface()) { 165 DexEncodedMethod t = clazz.findVirtualTarget(method); 166 if (t != null) { 167 if (result != null) { 168 return null; // We have more than one target method. 169 } else { 170 result = t; 171 } 172 } 173 } 174 } 175 } 176 method.setSingleVirtualMethodCache(result); 177 return result; 178 } 179 holderIsAbstract(Descriptor desc)180 private boolean holderIsAbstract(Descriptor desc) { 181 DexClass holder = definitionFor(desc.getHolder()); 182 return holder.accessFlags.isAbstract(); 183 } 184 185 // For mapping invoke interface instruction to target methods. lookupInterfaceTargets(DexMethod method)186 public Set<DexEncodedMethod> lookupInterfaceTargets(DexMethod method) { 187 Set<DexEncodedMethod> result = new HashSet<>(); 188 Set<DexType> set = subtypes(method.holder); 189 if (set != null) { 190 for (DexType type : set) { 191 DexClass clazz = definitionFor(type); 192 if (!clazz.isInterface()) { 193 DexEncodedMethod targetMethod = lookupVirtualTarget(type, method); 194 if (targetMethod != null) { 195 result.add(targetMethod); 196 } 197 } 198 } 199 } 200 return result; 201 } 202 lookupSingleInterfaceTarget(DexMethod method)203 public DexEncodedMethod lookupSingleInterfaceTarget(DexMethod method) { 204 assert method != null; 205 DexClass holder = definitionFor(method.holder); 206 if ((holder == null) || holder.isLibraryClass()) { 207 return null; 208 } 209 DexEncodedMethod result = null; 210 Set<DexType> set = subtypes(method.holder); 211 if (set != null) { 212 for (DexType type : set) { 213 DexClass clazz = definitionFor(type); 214 if (!clazz.isInterface()) { 215 DexEncodedMethod t = lookupVirtualTarget(type, method); 216 if (t != null) { 217 if (result != null) { 218 return null; 219 } else { 220 result = t; 221 } 222 } 223 } 224 } 225 } 226 return result; 227 } 228 229 @Override hasSubtyping()230 public boolean hasSubtyping() { 231 return true; 232 } 233 234 @Override withSubtyping()235 public AppInfoWithSubtyping withSubtyping() { 236 return this; 237 } 238 } 239