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