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