ClassProto.java revision 2206c7638b318e6c9aa7aa7dc58e64ce2254a9df
1/* 2 * Copyright 2013, Google Inc. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above 12 * copyright notice, this list of conditions and the following disclaimer 13 * in the documentation and/or other materials provided with the 14 * distribution. 15 * * Neither the name of Google Inc. nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32package org.jf.dexlib2.analysis; 33 34import com.google.common.collect.Iterables; 35import com.google.common.collect.Lists; 36import com.google.common.collect.Maps; 37import org.jf.dexlib2.AccessFlags; 38import org.jf.dexlib2.analysis.util.TypeProtoUtils; 39import org.jf.dexlib2.iface.ClassDef; 40import org.jf.dexlib2.iface.Field; 41import org.jf.dexlib2.iface.Method; 42import org.jf.dexlib2.iface.reference.FieldReference; 43import org.jf.dexlib2.iface.reference.MethodReference; 44import org.jf.dexlib2.util.FieldUtil; 45import org.jf.util.ExceptionWithContext; 46import org.jf.util.SparseArray; 47 48import javax.annotation.Nonnull; 49import javax.annotation.Nullable; 50import java.util.*; 51 52/** 53 * A class "prototype". This contains things like the interfaces, the superclass, the vtable and the instance fields 54 * and their offsets. 55 */ 56public class ClassProto implements TypeProto { 57 @Nonnull protected final ClassPath classPath; 58 @Nonnull protected final String type; 59 @Nullable protected ClassDef classDef; 60 @Nullable protected LinkedHashMap<String, ClassDef> interfaces; 61 @Nullable protected Method[] vtable; 62 @Nullable protected SparseArray<FieldReference> instanceFields; 63 protected boolean interfacesFullyResolved = true; 64 65 public ClassProto(@Nonnull ClassPath classPath, @Nonnull String type) { 66 if (type.charAt(0) != 'L') { 67 throw new ExceptionWithContext("Cannot construct ClassProto for non reference type: %s", type); 68 } 69 this.classPath = classPath; 70 this.type = type; 71 } 72 73 @Override public String toString() { return type; } 74 @Nonnull @Override public ClassPath getClassPath() { return classPath; } 75 @Nonnull @Override public String getType() { return type; } 76 77 @Nonnull 78 public ClassDef getClassDef() { 79 if (classDef == null) { 80 classDef = classPath.getClassDef(type); 81 } 82 return classDef; 83 } 84 85 @Nonnull 86 Method[] getVtable() { 87 if (vtable == null) { 88 vtable = loadVtable(); 89 } 90 return vtable; 91 } 92 93 @Nonnull 94 SparseArray<FieldReference> getInstanceFields() { 95 if (instanceFields == null) { 96 instanceFields = loadFields(); 97 } 98 return instanceFields; 99 } 100 101 /** 102 * Returns true if this class is an interface. 103 * 104 * If this class is not defined, then this will throw an UnresolvedClassException 105 * 106 * @return True if this class is an interface 107 */ 108 public boolean isInterface() { 109 ClassDef classDef = getClassDef(); 110 return (classDef.getAccessFlags() & AccessFlags.INTERFACE.getValue()) != 0; 111 } 112 113 @Nonnull 114 protected LinkedHashMap<String, ClassDef> getInterfaces() { 115 if (interfaces != null) { 116 return interfaces; 117 } 118 119 interfaces = Maps.newLinkedHashMap(); 120 121 try { 122 for (String interfaceType: getClassDef().getInterfaces()) { 123 if (!interfaces.containsKey(interfaceType)) { 124 ClassDef interfaceDef; 125 try { 126 interfaceDef = classPath.getClassDef(interfaceType); 127 interfaces.put(interfaceType, interfaceDef); 128 } catch (UnresolvedClassException ex) { 129 interfacesFullyResolved = false; 130 } 131 132 ClassProto interfaceProto = (ClassProto) classPath.getClass(interfaceType); 133 for (ClassDef superInterface: interfaceProto.getInterfaces().values()) { 134 if (!interfaces.containsKey(superInterface.getType())) { 135 interfaces.put(superInterface.getType(), superInterface); 136 } 137 } 138 } 139 } 140 } catch (UnresolvedClassException ex) { 141 interfacesFullyResolved = false; 142 } 143 144 return interfaces; 145 } 146 147 /** 148 * Checks if this class implements the given interface. 149 * 150 * If the interfaces of this class cannot be fully resolved then this 151 * method will either return true or throw an UnresolvedClassException 152 * 153 * @param iface The interface to check for 154 * @return true if this class implements the given interface, otherwise false 155 */ 156 @Override 157 public boolean implementsInterface(@Nonnull String iface) { 158 if (getInterfaces().containsKey(iface)) { 159 return true; 160 } 161 if (!interfacesFullyResolved) { 162 throw new UnresolvedClassException("Interfaces for class %s not fully resolved", getType()); 163 } 164 return false; 165 } 166 167 @Nullable @Override 168 public String getSuperclass() { 169 return getClassDef().getSuperclass(); 170 } 171 172 /** 173 * This is a helper method for getCommonSuperclass 174 * 175 * It checks if this class is an interface, and if so, if other implements it. 176 * 177 * If this class is undefined, we go ahead and check if it is listed in other's interfaces. If not, we throw an 178 * UndefinedClassException 179 * 180 * If the interfaces of other cannot be fully resolved, we check the interfaces that can be resolved. If not found, 181 * we throw an UndefinedClassException 182 * 183 * @param other The class to check the interfaces of 184 * @return true if this class is an interface (or is undefined) other implements this class 185 * 186 */ 187 private boolean checkInterface(@Nonnull ClassProto other) { 188 boolean isResolved = true; 189 boolean isInterface = true; 190 try { 191 isInterface = isInterface(); 192 } catch (UnresolvedClassException ex) { 193 isResolved = false; 194 // if we don't know if this class is an interface or not, 195 // we can still try to call other.implementsInterface(this) 196 } 197 if (isInterface) { 198 try { 199 if (other.implementsInterface(getType())) { 200 return true; 201 } 202 } catch (UnresolvedClassException ex) { 203 // There are 2 possibilities here, depending on whether we were able to resolve this class. 204 // 1. If this class is resolved, then we know it is an interface class. The other class either 205 // isn't defined, or its interfaces couldn't be fully resolved. 206 // In this case, we throw an UnresolvedClassException 207 // 2. If this class is not resolved, we had tried to call implementsInterface anyway. We don't 208 // know for sure if this class is an interface or not. We return false, and let processing 209 // continue in getCommonSuperclass 210 if (isResolved) { 211 throw ex; 212 } 213 } 214 } 215 return false; 216 } 217 218 @Override @Nonnull 219 public TypeProto getCommonSuperclass(@Nonnull TypeProto other) { 220 // use the other type's more specific implementation 221 if (!(other instanceof ClassProto)) { 222 return other.getCommonSuperclass(this); 223 } 224 225 if (this == other || getType().equals(other.getType())) { 226 return this; 227 } 228 229 if (this.getType().equals("Ljava/lang/Object;")) { 230 return this; 231 } 232 233 if (other.getType().equals("Ljava/lang/Object;")) { 234 return other; 235 } 236 237 boolean gotException = false; 238 try { 239 if (checkInterface((ClassProto)other)) { 240 return this; 241 } 242 } catch (UnresolvedClassException ex) { 243 gotException = true; 244 } 245 246 try { 247 if (((ClassProto)other).checkInterface(this)) { 248 return other; 249 } 250 } catch (UnresolvedClassException ex) { 251 gotException = true; 252 } 253 if (gotException) { 254 return classPath.getUnknownClass(); 255 } 256 257 List<TypeProto> thisChain = Lists.<TypeProto>newArrayList(this); 258 Iterables.addAll(thisChain, TypeProtoUtils.getSuperclassChain(this)); 259 260 List<TypeProto> otherChain = Lists.newArrayList(other); 261 Iterables.addAll(otherChain, TypeProtoUtils.getSuperclassChain(other)); 262 263 // reverse them, so that the first entry is either Ljava/lang/Object; or Ujava/lang/Object; 264 thisChain = Lists.reverse(thisChain); 265 otherChain = Lists.reverse(otherChain); 266 267 for (int i=Math.min(thisChain.size(), otherChain.size())-1; i>=0; i--) { 268 TypeProto typeProto = thisChain.get(i); 269 if (typeProto.getType().equals(otherChain.get(i).getType())) { 270 return typeProto; 271 } 272 } 273 274 return classPath.getUnknownClass(); 275 } 276 277 @Override 278 @Nullable 279 public FieldReference getFieldByOffset(int fieldOffset) { 280 if (getInstanceFields().size() == 0) { 281 return null; 282 } 283 return getInstanceFields().get(fieldOffset); 284 } 285 286 @Override 287 @Nullable 288 public MethodReference getMethodByVtableIndex(int vtableIndex) { 289 if (vtableIndex < 0 || vtableIndex >= getVtable().length) { 290 return null; 291 } 292 return getVtable()[vtableIndex]; 293 } 294 295 @Nonnull 296 private SparseArray<FieldReference> loadFields() { 297 //This is a bit of an "involved" operation. We need to follow the same algorithm that dalvik uses to 298 //arrange fields, so that we end up with the same field offsets (which is needed for deodexing). 299 //See mydroid/dalvik/vm/oo/Class.c - computeFieldOffsets() 300 301 final byte REFERENCE = 0; 302 final byte WIDE = 1; 303 final byte OTHER = 2; 304 305 ArrayList<Field> loadedFields = getInstanceFields(getClassDef()); 306 Field[] fields = new Field[loadedFields.size()]; 307 //the "type" for each field in fields. 0=reference,1=wide,2=other 308 byte[] fieldTypes = new byte[fields.length]; 309 for (int i=0;i<fields.length;i++) { 310 fields[i] = loadedFields.get(i); 311 fieldTypes[i] = getFieldType(fields[i].getType()); 312 } 313 314 //The first operation is to move all of the reference fields to the front. To do this, find the first 315 //non-reference field, then find the last reference field, swap them and repeat 316 int back = fields.length - 1; 317 int front; 318 for (front = 0; front<fields.length; front++) { 319 if (fieldTypes[front] != REFERENCE) { 320 while (back > front) { 321 if (fieldTypes[back] == REFERENCE) { 322 swap(fieldTypes, fields, front, back--); 323 break; 324 } 325 back--; 326 } 327 } 328 329 if (fieldTypes[front] != REFERENCE) { 330 break; 331 } 332 } 333 334 int startFieldOffset = 8; 335 String superclassType = getSuperclass(); 336 ClassProto superclass = null; 337 if (superclassType != null) { 338 superclass = (ClassProto) classPath.getClass(superclassType); 339 if (superclass != null) { 340 startFieldOffset = superclass.getNextFieldOffset(); 341 } 342 } 343 344 int fieldIndexMod; 345 if ((startFieldOffset % 8) == 0) { 346 fieldIndexMod = 0; 347 } else { 348 fieldIndexMod = 1; 349 } 350 351 //next, we need to group all the wide fields after the reference fields. But the wide fields have to be 352 //8-byte aligned. If we're on an odd field index, we need to insert a 32-bit field. If the next field 353 //is already a 32-bit field, use that. Otherwise, find the first 32-bit field from the end and swap it in. 354 //If there are no 32-bit fields, do nothing for now. We'll add padding when calculating the field offsets 355 if (front < fields.length && (front % 2) != fieldIndexMod) { 356 if (fieldTypes[front] == WIDE) { 357 //we need to swap in a 32-bit field, so the wide fields will be correctly aligned 358 back = fields.length - 1; 359 while (back > front) { 360 if (fieldTypes[back] == OTHER) { 361 swap(fieldTypes, fields, front++, back); 362 break; 363 } 364 back--; 365 } 366 } else { 367 //there's already a 32-bit field here that we can use 368 front++; 369 } 370 } 371 372 //do the swap thing for wide fields 373 back = fields.length - 1; 374 for (; front<fields.length; front++) { 375 if (fieldTypes[front] != WIDE) { 376 while (back > front) { 377 if (fieldTypes[back] == WIDE) { 378 swap(fieldTypes, fields, front, back--); 379 break; 380 } 381 back--; 382 } 383 } 384 385 if (fieldTypes[front] != WIDE) { 386 break; 387 } 388 } 389 390 int superFieldCount = 0; 391 if (superclass != null) { 392 superFieldCount = superclass.instanceFields.size(); 393 } 394 395 //now the fields are in the correct order. Add them to the SparseArray and lookup, and calculate the offsets 396 int totalFieldCount = superFieldCount + fields.length; 397 SparseArray<FieldReference> instanceFields = new SparseArray<FieldReference>(totalFieldCount); 398 399 int fieldOffset; 400 401 if (superclass != null && superFieldCount > 0) { 402 for (int i=0; i<superFieldCount; i++) { 403 instanceFields.append(superclass.instanceFields.keyAt(i), superclass.instanceFields.valueAt(i)); 404 } 405 406 fieldOffset = instanceFields.keyAt(superFieldCount-1); 407 408 FieldReference lastSuperField = superclass.instanceFields.valueAt(superFieldCount-1); 409 char fieldType = lastSuperField.getType().charAt(0); 410 if (fieldType == 'J' || fieldType == 'D') { 411 fieldOffset += 8; 412 } else { 413 fieldOffset += 4; 414 } 415 } else { 416 //the field values start at 8 bytes into the DataObject dalvik structure 417 fieldOffset = 8; 418 } 419 420 boolean gotDouble = false; 421 for (int i=0; i<fields.length; i++) { 422 FieldReference field = fields[i]; 423 424 //add padding to align the wide fields, if needed 425 if (fieldTypes[i] == WIDE && !gotDouble) { 426 if (!gotDouble) { 427 if (fieldOffset % 8 != 0) { 428 assert fieldOffset % 8 == 4; 429 fieldOffset += 4; 430 } 431 gotDouble = true; 432 } 433 } 434 435 instanceFields.append(fieldOffset, field); 436 if (fieldTypes[i] == WIDE) { 437 fieldOffset += 8; 438 } else { 439 fieldOffset += 4; 440 } 441 } 442 443 return instanceFields; 444 } 445 446 private ArrayList<Field> getInstanceFields(ClassDef classDef) { 447 ArrayList<Field> instanceFields = Lists.newArrayList(); 448 for (Field field: classDef.getFields()) { 449 if (!FieldUtil.isStatic(field)) { 450 instanceFields.add(field); 451 } 452 } 453 return instanceFields; 454 } 455 456 private byte getFieldType(String fieldType) { 457 switch (fieldType.charAt(0)) { 458 case '[': 459 case 'L': 460 return 0; //REFERENCE 461 case 'J': 462 case 'D': 463 return 1; //WIDE 464 default: 465 return 2; //OTHER 466 } 467 } 468 469 private void swap(byte[] fieldTypes, FieldReference[] fields, int position1, int position2) { 470 byte tempType = fieldTypes[position1]; 471 fieldTypes[position1] = fieldTypes[position2]; 472 fieldTypes[position2] = tempType; 473 474 FieldReference tempField = fields[position1]; 475 fields[position1] = fields[position2]; 476 fields[position2] = tempField; 477 } 478 479 private int getNextFieldOffset() { 480 SparseArray<FieldReference> instanceFields = getInstanceFields(); 481 if (instanceFields.size() == 0) { 482 return 8; 483 } 484 485 int lastItemIndex = instanceFields.size()-1; 486 int fieldOffset = instanceFields.keyAt(lastItemIndex); 487 FieldReference lastField = instanceFields.valueAt(lastItemIndex); 488 489 switch (lastField.getType().charAt(0)) { 490 case 'J': 491 case 'D': 492 return fieldOffset + 8; 493 default: 494 return fieldOffset + 4; 495 } 496 } 497 498 //TODO: check the case when we have a package private method that overrides an interface method 499 @Nonnull 500 private Method[] loadVtable() { 501 //TODO: it might be useful to keep track of which class's implementation is used for each virtual method. In other words, associate the implementing class type with each vtable entry 502 List<Method> virtualMethodList = Lists.newLinkedList(); 503 504 //copy the virtual methods from the superclass 505 String superclassType = getSuperclass(); 506 if (superclassType != null) { 507 ClassProto superclass = (ClassProto) classPath.getClass(superclassType); 508 for (int i=0; i<superclass.getVtable().length; i++) { 509 virtualMethodList.add(superclass.getVtable()[i]); 510 } 511 } 512 513 //iterate over the virtual methods in the current class, and only add them when we don't already have the 514 //method (i.e. if it was implemented by the superclass) 515 if (!isInterface()) { 516 addToVtable(getClassDef().getVirtualMethods(), virtualMethodList); 517 518 for (ClassDef interfaceDef: getInterfaces().values()) { 519 addToVtable(interfaceDef.getVirtualMethods(), virtualMethodList); 520 } 521 } 522 523 Method[] vtable = new Method[virtualMethodList.size()]; 524 for (int i=0; i<virtualMethodList.size(); i++) { 525 vtable[i] = virtualMethodList.get(i); 526 } 527 528 return vtable; 529 } 530 531 private void addToVtable(@Nonnull Iterable<? extends Method> localMethods, @Nonnull List<Method> vtable) { 532 for (Method virtualMethod: localMethods) { 533 boolean found = false; 534 for (int i=0; i<vtable.size(); i++) { 535 Method superMethod = vtable.get(i); 536 if (methodSignaturesMatch(superMethod, virtualMethod)) { 537 if (canAccess(superMethod)) { 538 found = true; 539 vtable.set(i, virtualMethod); 540 break; 541 } 542 } 543 } 544 if (!found) { 545 vtable.add(virtualMethod); 546 } 547 } 548 } 549 550 private boolean methodSignaturesMatch(Method a, Method b) { 551 return (a.getName().equals(b.getName()) 552 && a.getReturnType().equals(b.getReturnType()) 553 && a.getParameters().equals(b.getParameters())); 554 } 555 556 private boolean canAccess(Method virtualMethod) { 557 if (!methodIsPackagePrivate(virtualMethod.getAccessFlags())) { 558 return true; 559 } 560 561 String otherPackage = getPackage(virtualMethod.getDefiningClass()); 562 String ourPackage = getPackage(getClassDef().getType()); 563 return otherPackage.equals(ourPackage); 564 } 565 566 private String getPackage(String classType) { 567 int lastSlash = classType.lastIndexOf('/'); 568 if (lastSlash < 0) { 569 return ""; 570 } 571 return classType.substring(1, lastSlash); 572 } 573 574 private static boolean methodIsPackagePrivate(int accessFlags) { 575 return (accessFlags & (AccessFlags.PRIVATE.getValue() | 576 AccessFlags.PROTECTED.getValue() | 577 AccessFlags.PUBLIC.getValue())) == 0; 578 } 579} 580