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.base.Supplier; 36import com.google.common.base.Suppliers; 37import com.google.common.collect.*; 38import com.google.common.primitives.Ints; 39import org.jf.dexlib2.AccessFlags; 40import org.jf.dexlib2.analysis.util.TypeProtoUtils; 41import org.jf.dexlib2.iface.ClassDef; 42import org.jf.dexlib2.iface.Field; 43import org.jf.dexlib2.iface.Method; 44import org.jf.dexlib2.iface.reference.FieldReference; 45import org.jf.dexlib2.iface.reference.MethodReference; 46import org.jf.dexlib2.immutable.ImmutableMethod; 47import org.jf.dexlib2.util.MethodUtil; 48import org.jf.util.AlignmentUtils; 49import org.jf.util.ExceptionWithContext; 50import org.jf.util.SparseArray; 51 52import javax.annotation.Nonnull; 53import javax.annotation.Nullable; 54import java.util.*; 55 56/** 57 * A class "prototype". This contains things like the interfaces, the superclass, the vtable and the instance fields 58 * and their offsets. 59 */ 60public class ClassProto implements TypeProto { 61 private static final byte REFERENCE = 0; 62 private static final byte WIDE = 1; 63 private static final byte OTHER = 2; 64 65 @Nonnull protected final ClassPath classPath; 66 @Nonnull protected final String type; 67 68 protected boolean vtableFullyResolved = true; 69 protected boolean interfacesFullyResolved = true; 70 71 protected Set<String> unresolvedInterfaces = null; 72 73 public ClassProto(@Nonnull ClassPath classPath, @Nonnull String type) { 74 if (type.charAt(0) != 'L') { 75 throw new ExceptionWithContext("Cannot construct ClassProto for non reference type: %s", type); 76 } 77 this.classPath = classPath; 78 this.type = type; 79 } 80 81 @Override public String toString() { return type; } 82 @Nonnull @Override public ClassPath getClassPath() { return classPath; } 83 @Nonnull @Override public String getType() { return type; } 84 85 @Nonnull 86 public ClassDef getClassDef() { 87 return classDefSupplier.get(); 88 } 89 90 91 @Nonnull private final Supplier<ClassDef> classDefSupplier = Suppliers.memoize(new Supplier<ClassDef>() { 92 @Override public ClassDef get() { 93 return classPath.getClassDef(type); 94 } 95 }); 96 97 /** 98 * Returns true if this class is an interface. 99 * 100 * If this class is not defined, then this will throw an UnresolvedClassException 101 * 102 * @return True if this class is an interface 103 */ 104 public boolean isInterface() { 105 ClassDef classDef = getClassDef(); 106 return (classDef.getAccessFlags() & AccessFlags.INTERFACE.getValue()) != 0; 107 } 108 109 /** 110 * Returns the set of interfaces that this class implements as a Map<String, ClassDef>. 111 * 112 * The ClassDef value will be present only for the interfaces that this class directly implements (including any 113 * interfaces transitively implemented), but not for any interfaces that are only implemented by a superclass of 114 * this class 115 * 116 * For any interfaces that are only implemented by a superclass (or the class itself, if the class is an interface), 117 * the value will be null. 118 * 119 * If any interface couldn't be resolved, then the interfacesFullyResolved field will be set to false upon return. 120 * 121 * @return the set of interfaces that this class implements as a Map<String, ClassDef>. 122 */ 123 @Nonnull 124 protected LinkedHashMap<String, ClassDef> getInterfaces() { 125 return interfacesSupplier.get(); 126 } 127 128 @Nonnull 129 private final Supplier<LinkedHashMap<String, ClassDef>> interfacesSupplier = 130 Suppliers.memoize(new Supplier<LinkedHashMap<String, ClassDef>>() { 131 @Override public LinkedHashMap<String, ClassDef> get() { 132 Set<String> unresolvedInterfaces = new HashSet<String>(0); 133 LinkedHashMap<String, ClassDef> interfaces = Maps.newLinkedHashMap(); 134 135 try { 136 for (String interfaceType: getClassDef().getInterfaces()) { 137 if (!interfaces.containsKey(interfaceType)) { 138 ClassDef interfaceDef; 139 try { 140 interfaceDef = classPath.getClassDef(interfaceType); 141 interfaces.put(interfaceType, interfaceDef); 142 } catch (UnresolvedClassException ex) { 143 interfaces.put(interfaceType, null); 144 unresolvedInterfaces.add(interfaceType); 145 interfacesFullyResolved = false; 146 } 147 148 ClassProto interfaceProto = (ClassProto) classPath.getClass(interfaceType); 149 for (String superInterface: interfaceProto.getInterfaces().keySet()) { 150 if (!interfaces.containsKey(superInterface)) { 151 interfaces.put(superInterface, interfaceProto.getInterfaces().get(superInterface)); 152 } 153 } 154 if (!interfaceProto.interfacesFullyResolved) { 155 unresolvedInterfaces.addAll(interfaceProto.getUnresolvedInterfaces()); 156 interfacesFullyResolved = false; 157 } 158 } 159 } 160 } catch (UnresolvedClassException ex) { 161 unresolvedInterfaces.add(type); 162 interfacesFullyResolved = false; 163 } 164 165 // now add self and super class interfaces, required for common super class lookup 166 // we don't really need ClassDef's for that, so let's just use null 167 168 if (isInterface() && !interfaces.containsKey(getType())) { 169 interfaces.put(getType(), null); 170 } 171 172 String superclass = getSuperclass(); 173 try { 174 if (superclass != null) { 175 ClassProto superclassProto = (ClassProto) classPath.getClass(superclass); 176 for (String superclassInterface: superclassProto.getInterfaces().keySet()) { 177 if (!interfaces.containsKey(superclassInterface)) { 178 interfaces.put(superclassInterface, null); 179 } 180 } 181 if (!superclassProto.interfacesFullyResolved) { 182 unresolvedInterfaces.addAll(superclassProto.getUnresolvedInterfaces()); 183 interfacesFullyResolved = false; 184 } 185 } 186 } catch (UnresolvedClassException ex) { 187 unresolvedInterfaces.add(superclass); 188 interfacesFullyResolved = false; 189 } 190 191 if (unresolvedInterfaces.size() > 0) { 192 ClassProto.this.unresolvedInterfaces = unresolvedInterfaces; 193 } 194 195 return interfaces; 196 } 197 }); 198 199 @Nonnull 200 protected Set<String> getUnresolvedInterfaces() { 201 if (unresolvedInterfaces == null) { 202 return ImmutableSet.of(); 203 } 204 return unresolvedInterfaces; 205 } 206 207 /** 208 * Gets the interfaces directly implemented by this class, or the interfaces they transitively implement. 209 * 210 * This does not include any interfaces that are only implemented by a superclass 211 * 212 * @return An iterables of ClassDefs representing the directly or transitively implemented interfaces 213 * @throws UnresolvedClassException if interfaces could not be fully resolved 214 */ 215 @Nonnull 216 protected Iterable<ClassDef> getDirectInterfaces() { 217 Iterable<ClassDef> directInterfaces = 218 Iterables.filter(getInterfaces().values(), Predicates.notNull()); 219 220 if (!interfacesFullyResolved) { 221 throw new UnresolvedClassException("Interfaces for class %s not fully resolved: %s", getType(), 222 getUnresolvedInterfaces()); 223 } 224 225 return directInterfaces; 226 } 227 228 /** 229 * Checks if this class implements the given interface. 230 * 231 * If the interfaces of this class cannot be fully resolved then this 232 * method will either return true or throw an UnresolvedClassException 233 * 234 * @param iface The interface to check for 235 * @return true if this class implements the given interface, otherwise false 236 * @throws UnresolvedClassException if the interfaces for this class could not be fully resolved, and the interface 237 * is not one of the interfaces that were successfully resolved 238 */ 239 @Override 240 public boolean implementsInterface(@Nonnull String iface) { 241 if (getInterfaces().containsKey(iface)) { 242 return true; 243 } 244 if (!interfacesFullyResolved) { 245 throw new UnresolvedClassException("Interfaces for class %s not fully resolved", getType()); 246 } 247 return false; 248 } 249 250 @Nullable @Override 251 public String getSuperclass() { 252 return getClassDef().getSuperclass(); 253 } 254 255 /** 256 * This is a helper method for getCommonSuperclass 257 * 258 * It checks if this class is an interface, and if so, if other implements it. 259 * 260 * If this class is undefined, we go ahead and check if it is listed in other's interfaces. If not, we throw an 261 * UndefinedClassException 262 * 263 * If the interfaces of other cannot be fully resolved, we check the interfaces that can be resolved. If not found, 264 * we throw an UndefinedClassException 265 * 266 * @param other The class to check the interfaces of 267 * @return true if this class is an interface (or is undefined) other implements this class 268 * 269 */ 270 private boolean checkInterface(@Nonnull ClassProto other) { 271 boolean isResolved = true; 272 boolean isInterface = true; 273 try { 274 isInterface = isInterface(); 275 } catch (UnresolvedClassException ex) { 276 isResolved = false; 277 // if we don't know if this class is an interface or not, 278 // we can still try to call other.implementsInterface(this) 279 } 280 if (isInterface) { 281 try { 282 if (other.implementsInterface(getType())) { 283 return true; 284 } 285 } catch (UnresolvedClassException ex) { 286 // There are 2 possibilities here, depending on whether we were able to resolve this class. 287 // 1. If this class is resolved, then we know it is an interface class. The other class either 288 // isn't defined, or its interfaces couldn't be fully resolved. 289 // In this case, we throw an UnresolvedClassException 290 // 2. If this class is not resolved, we had tried to call implementsInterface anyway. We don't 291 // know for sure if this class is an interface or not. We return false, and let processing 292 // continue in getCommonSuperclass 293 if (isResolved) { 294 throw ex; 295 } 296 } 297 } 298 return false; 299 } 300 301 @Override @Nonnull 302 public TypeProto getCommonSuperclass(@Nonnull TypeProto other) { 303 // use the other type's more specific implementation 304 if (!(other instanceof ClassProto)) { 305 return other.getCommonSuperclass(this); 306 } 307 308 if (this == other || getType().equals(other.getType())) { 309 return this; 310 } 311 312 if (this.getType().equals("Ljava/lang/Object;")) { 313 return this; 314 } 315 316 if (other.getType().equals("Ljava/lang/Object;")) { 317 return other; 318 } 319 320 boolean gotException = false; 321 try { 322 if (checkInterface((ClassProto)other)) { 323 return this; 324 } 325 } catch (UnresolvedClassException ex) { 326 gotException = true; 327 } 328 329 try { 330 if (((ClassProto)other).checkInterface(this)) { 331 return other; 332 } 333 } catch (UnresolvedClassException ex) { 334 gotException = true; 335 } 336 if (gotException) { 337 return classPath.getUnknownClass(); 338 } 339 340 List<TypeProto> thisChain = Lists.<TypeProto>newArrayList(this); 341 Iterables.addAll(thisChain, TypeProtoUtils.getSuperclassChain(this)); 342 343 List<TypeProto> otherChain = Lists.newArrayList(other); 344 Iterables.addAll(otherChain, TypeProtoUtils.getSuperclassChain(other)); 345 346 // reverse them, so that the first entry is either Ljava/lang/Object; or Ujava/lang/Object; 347 thisChain = Lists.reverse(thisChain); 348 otherChain = Lists.reverse(otherChain); 349 350 for (int i=Math.min(thisChain.size(), otherChain.size())-1; i>=0; i--) { 351 TypeProto typeProto = thisChain.get(i); 352 if (typeProto.getType().equals(otherChain.get(i).getType())) { 353 return typeProto; 354 } 355 } 356 357 return classPath.getUnknownClass(); 358 } 359 360 @Override 361 @Nullable 362 public FieldReference getFieldByOffset(int fieldOffset) { 363 if (getInstanceFields().size() == 0) { 364 return null; 365 } 366 return getInstanceFields().get(fieldOffset); 367 } 368 369 @Override 370 @Nullable 371 public Method getMethodByVtableIndex(int vtableIndex) { 372 List<Method> vtable = getVtable(); 373 if (vtableIndex < 0 || vtableIndex >= vtable.size()) { 374 return null; 375 } 376 377 return vtable.get(vtableIndex); 378 } 379 380 public int findMethodIndexInVtable(@Nonnull MethodReference method) { 381 List<Method> vtable = getVtable(); 382 for (int i=0; i<vtable.size(); i++) { 383 Method candidate = vtable.get(i); 384 if (MethodUtil.methodSignaturesMatch(candidate, method)) { 385 if (!classPath.shouldCheckPackagePrivateAccess() || 386 AnalyzedMethodUtil.canAccess(this, candidate, true, false, false)) { 387 return i; 388 } 389 } 390 } 391 return -1; 392 } 393 394 @Nonnull SparseArray<FieldReference> getInstanceFields() { 395 if (classPath.isArt()) { 396 return artInstanceFieldsSupplier.get(); 397 } else { 398 return dalvikInstanceFieldsSupplier.get(); 399 } 400 } 401 402 @Nonnull private final Supplier<SparseArray<FieldReference>> dalvikInstanceFieldsSupplier = 403 Suppliers.memoize(new Supplier<SparseArray<FieldReference>>() { 404 @Override public SparseArray<FieldReference> get() { 405 //This is a bit of an "involved" operation. We need to follow the same algorithm that dalvik uses to 406 //arrange fields, so that we end up with the same field offsets (which is needed for deodexing). 407 //See mydroid/dalvik/vm/oo/Class.c - computeFieldOffsets() 408 409 ArrayList<Field> fields = getSortedInstanceFields(getClassDef()); 410 final int fieldCount = fields.size(); 411 //the "type" for each field in fields. 0=reference,1=wide,2=other 412 byte[] fieldTypes = new byte[fields.size()]; 413 for (int i=0; i<fieldCount; i++) { 414 fieldTypes[i] = getFieldType(fields.get(i)); 415 } 416 417 //The first operation is to move all of the reference fields to the front. To do this, find the first 418 //non-reference field, then find the last reference field, swap them and repeat 419 int back = fields.size() - 1; 420 int front; 421 for (front = 0; front<fieldCount; front++) { 422 if (fieldTypes[front] != REFERENCE) { 423 while (back > front) { 424 if (fieldTypes[back] == REFERENCE) { 425 swap(fieldTypes, fields, front, back--); 426 break; 427 } 428 back--; 429 } 430 } 431 432 if (fieldTypes[front] != REFERENCE) { 433 break; 434 } 435 } 436 437 int startFieldOffset = 8; 438 String superclassType = getSuperclass(); 439 ClassProto superclass = null; 440 if (superclassType != null) { 441 superclass = (ClassProto) classPath.getClass(superclassType); 442 if (superclass != null) { 443 startFieldOffset = superclass.getNextFieldOffset(); 444 } 445 } 446 447 int fieldIndexMod; 448 if ((startFieldOffset % 8) == 0) { 449 fieldIndexMod = 0; 450 } else { 451 fieldIndexMod = 1; 452 } 453 454 //next, we need to group all the wide fields after the reference fields. But the wide fields have to be 455 //8-byte aligned. If we're on an odd field index, we need to insert a 32-bit field. If the next field 456 //is already a 32-bit field, use that. Otherwise, find the first 32-bit field from the end and swap it in. 457 //If there are no 32-bit fields, do nothing for now. We'll add padding when calculating the field offsets 458 if (front < fieldCount && (front % 2) != fieldIndexMod) { 459 if (fieldTypes[front] == WIDE) { 460 //we need to swap in a 32-bit field, so the wide fields will be correctly aligned 461 back = fieldCount - 1; 462 while (back > front) { 463 if (fieldTypes[back] == OTHER) { 464 swap(fieldTypes, fields, front++, back); 465 break; 466 } 467 back--; 468 } 469 } else { 470 //there's already a 32-bit field here that we can use 471 front++; 472 } 473 } 474 475 //do the swap thing for wide fields 476 back = fieldCount - 1; 477 for (; front<fieldCount; front++) { 478 if (fieldTypes[front] != WIDE) { 479 while (back > front) { 480 if (fieldTypes[back] == WIDE) { 481 swap(fieldTypes, fields, front, back--); 482 break; 483 } 484 back--; 485 } 486 } 487 488 if (fieldTypes[front] != WIDE) { 489 break; 490 } 491 } 492 493 SparseArray<FieldReference> superFields; 494 if (superclass != null) { 495 superFields = superclass.getInstanceFields(); 496 } else { 497 superFields = new SparseArray<FieldReference>(); 498 } 499 int superFieldCount = superFields.size(); 500 501 //now the fields are in the correct order. Add them to the SparseArray and lookup, and calculate the offsets 502 int totalFieldCount = superFieldCount + fieldCount; 503 SparseArray<FieldReference> instanceFields = new SparseArray<FieldReference>(totalFieldCount); 504 505 int fieldOffset; 506 507 if (superclass != null && superFieldCount > 0) { 508 for (int i=0; i<superFieldCount; i++) { 509 instanceFields.append(superFields.keyAt(i), superFields.valueAt(i)); 510 } 511 512 fieldOffset = instanceFields.keyAt(superFieldCount-1); 513 514 FieldReference lastSuperField = superFields.valueAt(superFieldCount-1); 515 char fieldType = lastSuperField.getType().charAt(0); 516 if (fieldType == 'J' || fieldType == 'D') { 517 fieldOffset += 8; 518 } else { 519 fieldOffset += 4; 520 } 521 } else { 522 //the field values start at 8 bytes into the DataObject dalvik structure 523 fieldOffset = 8; 524 } 525 526 boolean gotDouble = false; 527 for (int i=0; i<fieldCount; i++) { 528 FieldReference field = fields.get(i); 529 530 //add padding to align the wide fields, if needed 531 if (fieldTypes[i] == WIDE && !gotDouble) { 532 if (!gotDouble) { 533 if (fieldOffset % 8 != 0) { 534 assert fieldOffset % 8 == 4; 535 fieldOffset += 4; 536 } 537 gotDouble = true; 538 } 539 } 540 541 instanceFields.append(fieldOffset, field); 542 if (fieldTypes[i] == WIDE) { 543 fieldOffset += 8; 544 } else { 545 fieldOffset += 4; 546 } 547 } 548 549 return instanceFields; 550 } 551 552 @Nonnull 553 private ArrayList<Field> getSortedInstanceFields(@Nonnull ClassDef classDef) { 554 ArrayList<Field> fields = Lists.newArrayList(classDef.getInstanceFields()); 555 Collections.sort(fields); 556 return fields; 557 } 558 559 private void swap(byte[] fieldTypes, List<Field> fields, int position1, int position2) { 560 byte tempType = fieldTypes[position1]; 561 fieldTypes[position1] = fieldTypes[position2]; 562 fieldTypes[position2] = tempType; 563 564 Field tempField = fields.set(position1, fields.get(position2)); 565 fields.set(position2, tempField); 566 } 567 }); 568 569 private static abstract class FieldGap implements Comparable<FieldGap> { 570 public final int offset; 571 public final int size; 572 573 public static FieldGap newFieldGap(int offset, int size, int oatVersion) { 574 if (oatVersion >= 67) { 575 return new FieldGap(offset, size) { 576 @Override public int compareTo(FieldGap o) { 577 int result = Ints.compare(o.size, size); 578 if (result != 0) { 579 return result; 580 } 581 return Ints.compare(offset, o.offset); 582 } 583 }; 584 } else { 585 return new FieldGap(offset, size) { 586 @Override public int compareTo(FieldGap o) { 587 int result = Ints.compare(size, o.size); 588 if (result != 0) { 589 return result; 590 } 591 return Ints.compare(o.offset, offset); 592 } 593 }; 594 } 595 } 596 597 private FieldGap(int offset, int size) { 598 this.offset = offset; 599 this.size = size; 600 } 601 } 602 603 @Nonnull private final Supplier<SparseArray<FieldReference>> artInstanceFieldsSupplier = 604 Suppliers.memoize(new Supplier<SparseArray<FieldReference>>() { 605 606 @Override public SparseArray<FieldReference> get() { 607 // We need to follow the same algorithm that art uses to arrange fields, so that we end up with the 608 // same field offsets, which is needed for deodexing. 609 // See LinkFields() in art/runtime/class_linker.cc 610 611 PriorityQueue<FieldGap> gaps = new PriorityQueue<FieldGap>(); 612 613 SparseArray<FieldReference> linkedFields = new SparseArray<FieldReference>(); 614 ArrayList<Field> fields = getSortedInstanceFields(getClassDef()); 615 616 int fieldOffset = 0; 617 String superclassType = getSuperclass(); 618 if (superclassType != null) { 619 // TODO: what to do if superclass doesn't exist? 620 ClassProto superclass = (ClassProto) classPath.getClass(superclassType); 621 SparseArray<FieldReference> superFields = superclass.getInstanceFields(); 622 FieldReference field = null; 623 int lastOffset = 0; 624 for (int i=0; i<superFields.size(); i++) { 625 int offset = superFields.keyAt(i); 626 field = superFields.valueAt(i); 627 linkedFields.put(offset, field); 628 lastOffset = offset; 629 } 630 if (field != null) { 631 fieldOffset = lastOffset + getFieldSize(field); 632 } 633 } 634 635 for (Field field: fields) { 636 int fieldSize = getFieldSize(field); 637 638 if (!AlignmentUtils.isAligned(fieldOffset, fieldSize)) { 639 int oldOffset = fieldOffset; 640 fieldOffset = AlignmentUtils.alignOffset(fieldOffset, fieldSize); 641 addFieldGap(oldOffset, fieldOffset, gaps); 642 } 643 644 FieldGap gap = gaps.peek(); 645 if (gap != null && gap.size >= fieldSize) { 646 gaps.poll(); 647 linkedFields.put(gap.offset, field); 648 if (gap.size > fieldSize) { 649 addFieldGap(gap.offset + fieldSize, gap.offset + gap.size, gaps); 650 } 651 } else { 652 linkedFields.append(fieldOffset, field); 653 fieldOffset += fieldSize; 654 } 655 } 656 657 return linkedFields; 658 } 659 660 private void addFieldGap(int gapStart, int gapEnd, @Nonnull PriorityQueue<FieldGap> gaps) { 661 int offset = gapStart; 662 663 while (offset < gapEnd) { 664 int remaining = gapEnd - offset; 665 666 if ((remaining >= 4) && (offset % 4 == 0)) { 667 gaps.add(FieldGap.newFieldGap(offset, 4, classPath.oatVersion)); 668 offset += 4; 669 } else if (remaining >= 2 && (offset % 2 == 0)) { 670 gaps.add(FieldGap.newFieldGap(offset, 2, classPath.oatVersion)); 671 offset += 2; 672 } else { 673 gaps.add(FieldGap.newFieldGap(offset, 1, classPath.oatVersion)); 674 offset += 1; 675 } 676 } 677 } 678 679 @Nonnull 680 private ArrayList<Field> getSortedInstanceFields(@Nonnull ClassDef classDef) { 681 ArrayList<Field> fields = Lists.newArrayList(classDef.getInstanceFields()); 682 Collections.sort(fields, new Comparator<Field>() { 683 @Override public int compare(Field field1, Field field2) { 684 int result = Ints.compare(getFieldSortOrder(field1), getFieldSortOrder(field2)); 685 if (result != 0) { 686 return result; 687 } 688 689 result = field1.getName().compareTo(field2.getName()); 690 if (result != 0) { 691 return result; 692 } 693 return field1.getType().compareTo(field2.getType()); 694 } 695 }); 696 return fields; 697 } 698 699 private int getFieldSortOrder(@Nonnull FieldReference field) { 700 // The sort order is based on type size (except references are first), and then based on the 701 // enum value of the primitive type for types of equal size. See: Primitive::Type enum 702 // in art/runtime/primitive.h 703 switch (field.getType().charAt(0)) { 704 /* reference */ 705 case '[': 706 case 'L': 707 return 0; 708 /* 64 bit */ 709 case 'J': 710 return 1; 711 case 'D': 712 return 2; 713 /* 32 bit */ 714 case 'I': 715 return 3; 716 case 'F': 717 return 4; 718 /* 16 bit */ 719 case 'C': 720 return 5; 721 case 'S': 722 return 6; 723 /* 8 bit */ 724 case 'Z': 725 return 7; 726 case 'B': 727 return 8; 728 } 729 throw new ExceptionWithContext("Invalid field type: %s", field.getType()); 730 } 731 732 private int getFieldSize(@Nonnull FieldReference field) { 733 return getTypeSize(field.getType().charAt(0)); 734 } 735 }); 736 737 private int getNextFieldOffset() { 738 SparseArray<FieldReference> instanceFields = getInstanceFields(); 739 if (instanceFields.size() == 0) { 740 return classPath.isArt() ? 0 : 8; 741 } 742 743 int lastItemIndex = instanceFields.size()-1; 744 int fieldOffset = instanceFields.keyAt(lastItemIndex); 745 FieldReference lastField = instanceFields.valueAt(lastItemIndex); 746 747 if (classPath.isArt()) { 748 return fieldOffset + getTypeSize(lastField.getType().charAt(0)); 749 } else { 750 switch (lastField.getType().charAt(0)) { 751 case 'J': 752 case 'D': 753 return fieldOffset + 8; 754 default: 755 return fieldOffset + 4; 756 } 757 } 758 } 759 760 private static int getTypeSize(char type) { 761 switch (type) { 762 case 'J': 763 case 'D': 764 return 8; 765 case '[': 766 case 'L': 767 case 'I': 768 case 'F': 769 return 4; 770 case 'C': 771 case 'S': 772 return 2; 773 case 'B': 774 case 'Z': 775 return 1; 776 } 777 throw new ExceptionWithContext("Invalid type: %s", type); 778 } 779 780 @Nonnull List<Method> getVtable() { 781 return vtableSupplier.get(); 782 } 783 784 //TODO: check the case when we have a package private method that overrides an interface method 785 @Nonnull private final Supplier<List<Method>> vtableSupplier = Suppliers.memoize(new Supplier<List<Method>>() { 786 @Override public List<Method> get() { 787 List<Method> vtable = Lists.newArrayList(); 788 789 //copy the virtual methods from the superclass 790 String superclassType; 791 try { 792 superclassType = getSuperclass(); 793 } catch (UnresolvedClassException ex) { 794 vtable.addAll(((ClassProto)classPath.getClass("Ljava/lang/Object;")).getVtable()); 795 vtableFullyResolved = false; 796 return vtable; 797 } 798 799 if (superclassType != null) { 800 ClassProto superclass = (ClassProto) classPath.getClass(superclassType); 801 vtable.addAll(superclass.getVtable()); 802 803 // if the superclass's vtable wasn't fully resolved, then we can't know where the new methods added by this 804 // class should start, so we just propagate what we can from the parent and hope for the best. 805 if (!superclass.vtableFullyResolved) { 806 vtableFullyResolved = false; 807 return vtable; 808 } 809 } 810 811 //iterate over the virtual methods in the current class, and only add them when we don't already have the 812 //method (i.e. if it was implemented by the superclass) 813 if (!isInterface()) { 814 addToVtable(getClassDef().getVirtualMethods(), vtable, true); 815 816 // assume that interface method is implemented in the current class, when adding it to vtable 817 // otherwise it looks like that method is invoked on an interface, which fails Dalvik's optimization checks 818 for (ClassDef interfaceDef: getDirectInterfaces()) { 819 List<Method> interfaceMethods = Lists.newArrayList(); 820 for (Method interfaceMethod: interfaceDef.getVirtualMethods()) { 821 ImmutableMethod method = new ImmutableMethod( 822 type, 823 interfaceMethod.getName(), 824 interfaceMethod.getParameters(), 825 interfaceMethod.getReturnType(), 826 interfaceMethod.getAccessFlags(), 827 interfaceMethod.getAnnotations(), 828 interfaceMethod.getImplementation()); 829 interfaceMethods.add(method); 830 } 831 addToVtable(interfaceMethods, vtable, false); 832 } 833 } 834 return vtable; 835 } 836 837 private void addToVtable(@Nonnull Iterable<? extends Method> localMethods, 838 @Nonnull List<Method> vtable, boolean replaceExisting) { 839 List<? extends Method> methods = Lists.newArrayList(localMethods); 840 Collections.sort(methods); 841 842 outer: for (Method virtualMethod: methods) { 843 for (int i=0; i<vtable.size(); i++) { 844 Method superMethod = vtable.get(i); 845 if (MethodUtil.methodSignaturesMatch(superMethod, virtualMethod)) { 846 if (!classPath.shouldCheckPackagePrivateAccess() || 847 AnalyzedMethodUtil.canAccess(ClassProto.this, superMethod, true, false, false)) { 848 if (replaceExisting) { 849 vtable.set(i, virtualMethod); 850 } 851 continue outer; 852 } 853 } 854 } 855 // we didn't find an equivalent method, so add it as a new entry 856 vtable.add(virtualMethod); 857 } 858 } 859 }); 860 861 private static byte getFieldType(@Nonnull FieldReference field) { 862 switch (field.getType().charAt(0)) { 863 case '[': 864 case 'L': 865 return 0; //REFERENCE 866 case 'J': 867 case 'D': 868 return 1; //WIDE 869 default: 870 return 2; //OTHER 871 } 872 } 873} 874