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