ClassPath.java revision db385ec3fd0c4f0de00ec3a17b6565d2a6c60e61
1package org.jf.dexlib.Code.Analysis; 2 3import org.jf.dexlib.*; 4import static org.jf.dexlib.ClassDataItem.EncodedMethod; 5import static org.jf.dexlib.ClassDataItem.EncodedField; 6 7import org.jf.dexlib.Util.AccessFlags; 8import org.jf.dexlib.Util.ExceptionWithContext; 9import org.jf.dexlib.Util.SparseArray; 10 11import java.io.File; 12import java.util.*; 13 14public class ClassPath { 15 private static ClassPath theClassPath = null; 16 17 private final HashMap<String, ClassDef> classDefs; 18 protected ClassDef javaLangObjectClassDef; //Ljava/lang/Object; 19 20 public static void InitializeClassPath(String[] bootClassPath, DexFile dexFile) { 21 if (theClassPath != null) { 22 throw new ExceptionWithContext("Cannot initialize ClassPath multiple times"); 23 } 24 25 theClassPath = new ClassPath(); 26 theClassPath.initClassPath(bootClassPath, dexFile); 27 } 28 29 private ClassPath() { 30 classDefs = new HashMap<String, ClassDef>(); 31 } 32 33 private void initClassPath(String[] bootClassPath, DexFile dexFile) { 34 if (bootClassPath != null) { 35 for (String bootClassPathEntry: bootClassPath) { 36 loadBootClassPath(bootClassPathEntry); 37 } 38 } 39 40 loadDexFile(dexFile); 41 42 for (String primitiveType: new String[]{"Z", "B", "S", "C", "I", "J", "F", "D"}) { 43 ClassDef classDef = new PrimitiveClassDef(primitiveType); 44 classDefs.put(primitiveType, classDef); 45 } 46 } 47 48 private void loadBootClassPath(String bootClassPathEntry) { 49 File file = new File(bootClassPathEntry); 50 51 if (!file.exists()) { 52 throw new ExceptionWithContext("ClassPath entry \"" + bootClassPathEntry + "\" does not exist."); 53 } 54 55 if (!file.canRead()) { 56 throw new ExceptionWithContext("Cannot read ClassPath entry \"" + bootClassPathEntry + "\"."); 57 } 58 59 DexFile dexFile; 60 try { 61 dexFile = new DexFile(file, false, true); 62 } catch (Exception ex) { 63 throw ExceptionWithContext.withContext(ex, "Error while reading ClassPath entry \"" + 64 bootClassPathEntry + "\"."); 65 } 66 67 loadDexFile(dexFile); 68 } 69 70 private void loadDexFile(DexFile dexFile) { 71 for (ClassDefItem classDefItem: dexFile.ClassDefsSection.getItems()) { 72 //TODO: need to check if the class already exists. (and if so, what to do about it?) 73 ClassDef classDef = new ClassDef(classDefItem); 74 classDefs.put(classDef.getClassType(), classDef); 75 76 if (classDefItem.getClassType().getTypeDescriptor().equals("Ljava/lang/Object;")) { 77 theClassPath.javaLangObjectClassDef = classDef; 78 } 79 /*classDef.dumpVtable(); 80 classDef.dumpFields();*/ 81 } 82 } 83 84 private static class ClassNotFoundException extends ExceptionWithContext { 85 public ClassNotFoundException(String message) { 86 super(message); 87 } 88 } 89 90 public static ClassDef getClassDef(String classType) { 91 ClassDef classDef = theClassPath.classDefs.get(classType); 92 if (classDef == null) { 93 //if it's an array class, try to create it 94 if (classType.charAt(0) == '[') { 95 return theClassPath.createArrayClassDef(classType); 96 } else { 97 //TODO: we should output a warning 98 return theClassPath.createUnresolvedClassDef(classType); 99 } 100 } 101 return classDef; 102 } 103 104 public static ClassDef getClassDef(TypeIdItem classType) { 105 return getClassDef(classType.getTypeDescriptor()); 106 } 107 108 //256 [ characters 109 private static final String arrayPrefix = "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[" + 110 "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[" + 111 "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[["; 112 private static ClassDef getArrayClassDefByElementClassAndDimension(ClassDef classDef, int arrayDimension) { 113 return getClassDef(arrayPrefix.substring(256 - arrayDimension) + classDef.classType); 114 } 115 116 private ClassDef createUnresolvedClassDef(String classType) { 117 assert classType.charAt(0) == 'L'; 118 119 UnresolvedClassDef unresolvedClassDef = new UnresolvedClassDef(classType); 120 classDefs.put(classType, unresolvedClassDef); 121 return unresolvedClassDef; 122 } 123 124 private ClassDef createArrayClassDef(String arrayClassName) { 125 assert arrayClassName != null; 126 assert arrayClassName.charAt(0) == '['; 127 128 ArrayClassDef arrayClassDef = new ArrayClassDef(arrayClassName); 129 if (arrayClassDef.elementClass == null) { 130 return null; 131 } 132 133 classDefs.put(arrayClassName, arrayClassDef); 134 return arrayClassDef; 135 } 136 137 public static ClassDef getCommonSuperclass(ClassDef class1, ClassDef class2) { 138 if (class1 == class2) { 139 return class1; 140 } 141 142 if (class1 == null) { 143 return class2; 144 } 145 146 if (class2 == null) { 147 return class1; 148 } 149 150 //TODO: do we want to handle primitive types here? I don't think so.. (if not, add assert) 151 152 if (!class1.isInterface && class2.isInterface) { 153 if (class1.implementsInterface(class2)) { 154 return class2; 155 } 156 return theClassPath.javaLangObjectClassDef; 157 } 158 159 if (!class2.isInterface && class1.isInterface) { 160 if (class2.implementsInterface(class1)) { 161 return class1; 162 } 163 return theClassPath.javaLangObjectClassDef; 164 } 165 166 if (class1 instanceof ArrayClassDef && class2 instanceof ArrayClassDef) { 167 return getCommonArraySuperclass((ArrayClassDef)class1, (ArrayClassDef)class2); 168 } 169 170 //we've got two non-array reference types. Find the class depth of each, and then move up the longer one 171 //so that both classes are at the same class depth, and then move each class up until they match 172 173 //we don't strictly need to keep track of the class depth separately, but it's probably slightly faster 174 //to do so, rather than calling getClassDepth() many times 175 int class1Depth = class1.getClassDepth(); 176 int class2Depth = class2.getClassDepth(); 177 178 while (class1Depth > class2Depth) { 179 class1 = class1.superclass; 180 class1Depth--; 181 } 182 183 while (class2Depth > class1Depth) { 184 class2 = class2.superclass; 185 class2Depth--; 186 } 187 188 while (class1Depth > 0) { 189 if (class1 == class2) { 190 return class1; 191 } 192 class1 = class1.superclass; 193 class1Depth--; 194 class2 = class2.superclass; 195 class2Depth--; 196 } 197 198 return class1; 199 } 200 201 private static ClassDef getCommonArraySuperclass(ArrayClassDef class1, ArrayClassDef class2) { 202 assert class1 != class2; 203 204 //If one of the arrays is a primitive array, then the only option is to return java.lang.Object 205 //TODO: might it be possible to merge something like int[] and short[] into int[]? (I don't think so..) 206 if (class1.elementClass instanceof PrimitiveClassDef || class2.elementClass instanceof PrimitiveClassDef) { 207 return theClassPath.javaLangObjectClassDef; 208 } 209 210 //if the two arrays have the same number of dimensions, then we should return an array class with the 211 //same number of dimensions, for the common superclass of the 2 element classes 212 if (class1.arrayDimensions == class2.arrayDimensions) { 213 ClassDef commonElementClass = getCommonSuperclass(class1.elementClass, class2.elementClass); 214 return getArrayClassDefByElementClassAndDimension(commonElementClass, class1.arrayDimensions); 215 } 216 217 //something like String[][][] and String[][] should be merged to Object[][] 218 //this also holds when the element classes aren't the same (but are both reference types) 219 int dimensions = Math.min(class1.arrayDimensions, class2.arrayDimensions); 220 return getArrayClassDefByElementClassAndDimension(theClassPath.javaLangObjectClassDef, dimensions); 221 } 222 223 public static class ArrayClassDef extends ClassDef { 224 private final ClassDef elementClass; 225 private final int arrayDimensions; 226 227 protected ArrayClassDef(String arrayClassType) { 228 super(arrayClassType, ClassDef.ArrayClassDef); 229 assert arrayClassType.charAt(0) == '['; 230 231 int i=0; 232 while (arrayClassType.charAt(i) == '[') i++; 233 234 String elementClassType = arrayClassType.substring(i); 235 236 if (i>256) { 237 throw new ExceptionWithContext("Error while creating array class for element type " + elementClassType + 238 " with " + i + " dimensions. The maximum number of dimensions is 256"); 239 } 240 241 try { 242 elementClass = ClassPath.getClassDef(arrayClassType.substring(i)); 243 } catch (ClassNotFoundException ex) { 244 throw ExceptionWithContext.withContext(ex, "Error while creating array class " + arrayClassType); 245 } 246 arrayDimensions = i; 247 } 248 249 /** 250 * Returns the "base" element class of the array. 251 * 252 * For example, for a multi-dimensional array of strings ([[Ljava/lang/String;), this method would return 253 * Ljava/lang/String; 254 * @return 255 */ 256 public ClassDef getBaseElementClass() { 257 return elementClass; 258 } 259 260 /** 261 * Returns the "immediate" element class of the array. 262 * 263 * For example, for a multi-dimensional array of stings with 2 dimensions ([[Ljava/lang/String;), this method 264 * would return [Ljava/lang/String; 265 * @return 266 */ 267 public ClassDef getImmediateElementClass() { 268 if (arrayDimensions == 1) { 269 return elementClass; 270 } 271 return getArrayClassDefByElementClassAndDimension(elementClass, arrayDimensions - 1); 272 } 273 274 public int getArrayDimensions() { 275 return arrayDimensions; 276 } 277 278 @Override 279 public boolean extendsClass(ClassDef superclassDef) { 280 if (!(superclassDef instanceof ArrayClassDef)) { 281 if (superclassDef == ClassPath.theClassPath.javaLangObjectClassDef) { 282 return true; 283 } else if (superclassDef.isInterface) { 284 return this.implementsInterface(superclassDef); 285 } 286 return false; 287 } 288 289 ArrayClassDef arraySuperclassDef = (ArrayClassDef)superclassDef; 290 if (this.arrayDimensions == arraySuperclassDef.arrayDimensions) { 291 ClassDef baseElementClass = arraySuperclassDef.getBaseElementClass(); 292 293 if (baseElementClass.isInterface) { 294 return true; 295 } 296 297 return baseElementClass.extendsClass(arraySuperclassDef.getBaseElementClass()); 298 } else if (this.arrayDimensions > arraySuperclassDef.arrayDimensions) { 299 ClassDef baseElementClass = arraySuperclassDef.getBaseElementClass(); 300 if (baseElementClass.isInterface) { 301 return true; 302 } 303 304 if (baseElementClass == ClassPath.theClassPath.javaLangObjectClassDef) { 305 return true; 306 } 307 return false; 308 } 309 return false; 310 } 311 } 312 313 public static class PrimitiveClassDef extends ClassDef { 314 protected PrimitiveClassDef(String primitiveClassType) { 315 super(primitiveClassType, ClassDef.PrimitiveClassDef); 316 assert primitiveClassType.charAt(0) != 'L' && primitiveClassType.charAt(0) != '['; 317 } 318 } 319 320 public static class UnresolvedClassDef extends ClassDef { 321 protected UnresolvedClassDef(String unresolvedClassDef) { 322 super(unresolvedClassDef, ClassDef.UnresolvedClassDef); 323 assert unresolvedClassDef.charAt(0) == 'L'; 324 } 325 326 protected ValidationException unresolvedValidationException() { 327 return new ValidationException(String.format("class %s cannot be resolved.", this.getClassType())); 328 } 329 330 public ClassDef getSuperclass() { 331 throw unresolvedValidationException(); 332 } 333 334 public int getClassDepth() { 335 throw unresolvedValidationException(); 336 } 337 338 public boolean isInterface() { 339 throw unresolvedValidationException(); 340 } 341 342 public boolean extendsClass(ClassDef superclassDef) { 343 if (superclassDef != theClassPath.javaLangObjectClassDef && superclassDef != this) { 344 throw unresolvedValidationException(); 345 } 346 return true; 347 } 348 349 public boolean implementsInterface(ClassDef interfaceDef) { 350 throw unresolvedValidationException(); 351 } 352 353 public boolean hasVirtualMethod(String method) { 354 if (!super.hasVirtualMethod(method)) { 355 throw unresolvedValidationException(); 356 } 357 return true; 358 } 359 } 360 361 public static class ClassDef implements Comparable<ClassDef> { 362 private final String classType; 363 private final ClassDef superclass; 364 /** 365 * This is a list of all of the interfaces that a class implements, either directly or indirectly. It includes 366 * all interfaces implemented by the superclass, and all super-interfaces of any implemented interface. The 367 * intention is to make it easier to determine whether the class implements a given interface or not. 368 */ 369 private final TreeSet<ClassDef> implementedInterfaces; 370 371 private final boolean isInterface; 372 373 private final int classDepth; 374 375 private final String[] vtable; 376 private final HashMap<String, Integer> virtualMethodLookup; 377 378 private final SparseArray<String> instanceFields; 379 private final HashMap<String, Integer> instanceFieldLookup; 380 381 public final static int ArrayClassDef = 0; 382 public final static int PrimitiveClassDef = 1; 383 public final static int UnresolvedClassDef = 2; 384 385 /** 386 * This constructor is used for the ArrayClassDef, PrimitiveClassDef and UnresolvedClassDef subclasses 387 * @param classType the class type 388 * @param classFlavor one of ArrayClassDef, PrimitiveClassDef or UnresolvedClassDef 389 */ 390 protected ClassDef(String classType, int classFlavor) { 391 if (classFlavor == ArrayClassDef) { 392 assert classType.charAt(0) == '['; 393 this.classType = classType; 394 this.superclass = ClassPath.theClassPath.javaLangObjectClassDef; 395 implementedInterfaces = new TreeSet<ClassDef>(); 396 implementedInterfaces.add(ClassPath.getClassDef("Ljava/lang/Cloneable;")); 397 implementedInterfaces.add(ClassPath.getClassDef("Ljava/io/Serializable;")); 398 isInterface = false; 399 400 vtable = superclass.vtable; 401 virtualMethodLookup = superclass.virtualMethodLookup; 402 403 instanceFields = superclass.instanceFields; 404 instanceFieldLookup = superclass.instanceFieldLookup; 405 classDepth = 1; //1 off from java.lang.Object 406 } else if (classFlavor == PrimitiveClassDef) { 407 //primitive type 408 assert classType.charAt(0) != '[' && classType.charAt(0) != 'L'; 409 410 this.classType = classType; 411 this.superclass = null; 412 implementedInterfaces = null; 413 isInterface = false; 414 vtable = null; 415 virtualMethodLookup = null; 416 instanceFields = null; 417 instanceFieldLookup = null; 418 classDepth = 0; //TODO: maybe use -1 to indicate not applicable? 419 } else /*if (classFlavor == UnresolvedClassDef)*/ { 420 assert classType.charAt(0) == 'L'; 421 this.classType = classType; 422 this.superclass = ClassPath.theClassPath.javaLangObjectClassDef; 423 implementedInterfaces = new TreeSet<ClassDef>(); 424 isInterface = false; 425 426 vtable = superclass.vtable; 427 virtualMethodLookup = superclass.virtualMethodLookup; 428 429 instanceFields = superclass.instanceFields; 430 instanceFieldLookup = superclass.instanceFieldLookup; 431 classDepth = 1; //1 off from java.lang.Object 432 } 433 } 434 435 protected ClassDef(ClassDefItem classDefItem) { 436 classType = classDefItem.getClassType().getTypeDescriptor(); 437 438 isInterface = (classDefItem.getAccessFlags() & AccessFlags.INTERFACE.getValue()) != 0; 439 440 superclass = loadSuperclass(classDefItem); 441 if (superclass == null) { 442 classDepth = 0; 443 } else { 444 classDepth = superclass.classDepth + 1; 445 } 446 447 implementedInterfaces = loadAllImplementedInterfaces(classDefItem); 448 449 vtable = loadVtable(classDefItem); 450 virtualMethodLookup = new HashMap<String, Integer>((int)Math.ceil(vtable.length / .7f), .75f); 451 for (int i=0; i<vtable.length; i++) { 452 virtualMethodLookup.put(vtable[i], i); 453 } 454 455 instanceFields = loadFields(classDefItem); 456 instanceFieldLookup = new HashMap<String, Integer>((int)Math.ceil(instanceFields.size() / .7f), .75f); 457 for (int i=0; i<instanceFields.size(); i++) { 458 instanceFieldLookup.put(instanceFields.get(i), i); 459 } 460 } 461 462 public String getClassType() { 463 return classType; 464 } 465 466 public ClassDef getSuperclass() { 467 return superclass; 468 } 469 470 public int getClassDepth() { 471 return classDepth; 472 } 473 474 public boolean isInterface() { 475 return this.isInterface; 476 } 477 478 public boolean extendsClass(ClassDef superclassDef) { 479 if (superclassDef == null) { 480 return false; 481 } 482 483 if (this == superclassDef) { 484 return true; 485 } 486 487 if (superclassDef instanceof UnresolvedClassDef) { 488 throw ((UnresolvedClassDef)superclassDef).unresolvedValidationException(); 489 } 490 491 int superclassDepth = superclassDef.classDepth; 492 ClassDef ancestor = this; 493 while (ancestor.classDepth > superclassDepth) { 494 ancestor = ancestor.getSuperclass(); 495 } 496 497 return ancestor == superclassDef; 498 } 499 500 /** 501 * Returns true if this class implements the given interface. This searches the interfaces that this class 502 * directly implements, any interface implemented by this class's superclasses, and any super-interface of 503 * any of these interfaces. 504 * @param interfaceDef the interface 505 * @return true if this class implements the given interface 506 */ 507 public boolean implementsInterface(ClassDef interfaceDef) { 508 assert !(interfaceDef instanceof UnresolvedClassDef); 509 return implementedInterfaces.contains(interfaceDef); 510 } 511 512 public boolean hasVirtualMethod(String method) { 513 return virtualMethodLookup.containsKey(method); 514 } 515 516 private void swap(byte[] fieldTypes, String[] fields, int position1, int position2) { 517 byte tempType = fieldTypes[position1]; 518 fieldTypes[position1] = fieldTypes[position2]; 519 fieldTypes[position2] = tempType; 520 521 String tempField = fields[position1]; 522 fields[position1] = fields[position2]; 523 fields[position2] = tempField; 524 } 525 526 private ClassDef loadSuperclass(ClassDefItem classDefItem) { 527 if (classDefItem.getClassType().getTypeDescriptor().equals("Ljava/lang/Object;")) { 528 if (classDefItem.getSuperclass() != null) { 529 throw new ExceptionWithContext("Invalid superclass " + 530 classDefItem.getSuperclass().getTypeDescriptor() + " for Ljava/lang/Object;. " + 531 "The Object class cannot have a superclass"); 532 } 533 return null; 534 } else { 535 TypeIdItem superClass = classDefItem.getSuperclass(); 536 if (superClass == null) { 537 throw new ExceptionWithContext(classDefItem.getClassType().getTypeDescriptor() + 538 " has no superclass"); 539 } 540 541 ClassDef superclass = ClassPath.getClassDef(superClass.getTypeDescriptor()); 542 543 if (!isInterface && superclass.isInterface) { 544 throw new ValidationException("Class " + classType + " has the interface " + superclass.classType + 545 " as its superclass"); 546 } 547 if (isInterface && !superclass.isInterface && superclass != 548 ClassPath.theClassPath.javaLangObjectClassDef) { 549 throw new ValidationException("Interface " + classType + " has the non-interface class " + 550 superclass.classType + " as its superclass"); 551 } 552 553 return superclass; 554 } 555 } 556 557 private TreeSet<ClassDef> loadAllImplementedInterfaces(ClassDefItem classDefItem) { 558 assert classType != null; 559 assert classType.equals("Ljava/lang/Object;") || superclass != null; 560 assert classDefItem != null; 561 562 TreeSet<ClassDef> implementedInterfaceSet = new TreeSet<ClassDef>(); 563 564 if (superclass != null) { 565 for (ClassDef interfaceDef: superclass.implementedInterfaces) { 566 implementedInterfaceSet.add(interfaceDef); 567 } 568 } 569 570 TypeListItem interfaces = classDefItem.getInterfaces(); 571 if (interfaces != null) { 572 for (TypeIdItem interfaceType: interfaces.getTypes()) { 573 ClassDef interfaceDef = ClassPath.getClassDef(interfaceType.getTypeDescriptor()); 574 assert interfaceDef.isInterface; 575 implementedInterfaceSet.add(interfaceDef); 576 577 interfaceDef = interfaceDef.getSuperclass(); 578 while (!interfaceDef.getClassType().equals("Ljava/lang/Object;")) { 579 assert interfaceDef.isInterface; 580 implementedInterfaceSet.add(interfaceDef); 581 interfaceDef = interfaceDef.getSuperclass(); 582 } 583 } 584 } 585 586 return implementedInterfaceSet; 587 } 588 589 private String[] loadVtable(ClassDefItem classDefItem) { 590 //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 591 List<String> virtualMethodList = new LinkedList<String>(); 592 //use a temp hash table, so that we can construct the final lookup with an appropriate 593 //capacity, based on the number of virtual methods 594 HashMap<String, Integer> tempVirtualMethodLookup = new HashMap<String, Integer>(); 595 596 //copy the virtual methods from the superclass 597 int methodIndex = 0; 598 if (superclass != null) { 599 for (String method: superclass.vtable) { 600 virtualMethodList.add(method); 601 tempVirtualMethodLookup.put(method, methodIndex++); 602 } 603 604 assert superclass.instanceFields != null; 605 } 606 607 608 //iterate over the virtual methods in the current class, and only add them when we don't already have the 609 //method (i.e. if it was implemented by the superclass) 610 ClassDataItem classDataItem = classDefItem.getClassData(); 611 if (classDataItem != null) { 612 EncodedMethod[] virtualMethods = classDataItem.getVirtualMethods(); 613 if (virtualMethods != null) { 614 for (EncodedMethod virtualMethod: virtualMethods) { 615 String methodString = virtualMethod.method.getVirtualMethodString(); 616 if (tempVirtualMethodLookup.get(methodString) == null) { 617 virtualMethodList.add(methodString); 618 } 619 } 620 } 621 } 622 623 String[] vtable = new String[virtualMethodList.size()]; 624 for (int i=0; i<virtualMethodList.size(); i++) { 625 vtable[i] = virtualMethodList.get(i); 626 } 627 628 return vtable; 629 } 630 631 private SparseArray<String> loadFields(ClassDefItem classDefItem) { 632 //This is a bit of an "involved" operation. We need to follow the same algorithm that dalvik uses to 633 //arrange fields, so that we end up with the same field offsets (which is needed for deodexing). 634 635 final byte REFERENCE = 0; 636 final byte WIDE = 1; 637 final byte OTHER = 2; 638 639 ClassDataItem classDataItem = classDefItem.getClassData(); 640 641 String[] fields = null; 642 //the "type" for each field in fields. 0=reference,1=wide,2=other 643 byte[] fieldTypes = null; 644 645 if (classDataItem != null) { 646 EncodedField[] encodedFields = classDataItem.getInstanceFields(); 647 if (encodedFields != null) { 648 fields = new String[encodedFields.length]; 649 fieldTypes = new byte[encodedFields.length]; 650 651 for (int i=0; i<encodedFields.length; i++) { 652 EncodedField encodedField = encodedFields[i]; 653 String fieldType = encodedField.field.getFieldType().getTypeDescriptor(); 654 String field = String.format("%s:%s", encodedField.field.getFieldName().getStringValue(), 655 fieldType); 656 fieldTypes[i] = getFieldType(field); 657 fields[i] = field; 658 } 659 } 660 } 661 662 if (fields == null) { 663 fields = new String[0]; 664 fieldTypes = new byte[0]; 665 } 666 667 //The first operation is to move all of the reference fields to the front. To do this, find the first 668 //non-reference field, then find the last reference field, swap them and repeat 669 int back = fields.length - 1; 670 int front; 671 for (front = 0; front<fields.length; front++) { 672 if (fieldTypes[front] != REFERENCE) { 673 while (back > front) { 674 if (fieldTypes[back] == REFERENCE) { 675 swap(fieldTypes, fields, front, back--); 676 break; 677 } 678 back--; 679 } 680 } 681 682 if (fieldTypes[front] != REFERENCE) { 683 break; 684 } 685 } 686 687 //next, we need to group all the wide fields after the reference fields. But the wide fields have to be 688 //8-byte aligned. If we're on an odd field index, we need to insert a 32-bit field. If the next field 689 //is already a 32-bit field, use that. Otherwise, find the first 32-bit field from the end and swap it in. 690 //If there are no 32-bit fields, do nothing for now. We'll add padding when calculating the field offsets 691 if (front < fields.length && (front % 2) != 0) { 692 if (fieldTypes[front] == WIDE) { 693 //we need to swap in a 32-bit field, so the wide fields will be correctly aligned 694 back = fields.length - 1; 695 while (back > front) { 696 if (fieldTypes[back] == OTHER) { 697 swap(fieldTypes, fields, front++, back); 698 break; 699 } 700 back--; 701 } 702 } else { 703 //there's already a 32-bit field here that we can use 704 front++; 705 } 706 } 707 708 //do the swap thing for wide fields 709 back = fields.length - 1; 710 for (; front<fields.length; front++) { 711 if (fieldTypes[front] != WIDE) { 712 while (back > front) { 713 if (fieldTypes[back] == WIDE) { 714 swap(fieldTypes, fields, front, back--); 715 break; 716 } 717 back--; 718 } 719 } 720 721 if (fieldTypes[front] != WIDE) { 722 break; 723 } 724 } 725 726 int superFieldCount = 0; 727 if (superclass != null) { 728 superclass.instanceFields.size(); 729 } 730 731 //now the fields are in the correct order. Add them to the SparseArray and lookup, and calculate the offsets 732 int totalFieldCount = superFieldCount + fields.length; 733 SparseArray<String> instanceFields = new SparseArray<String>(totalFieldCount); 734 735 int fieldOffset; 736 737 if (superclass != null && superFieldCount > 0) { 738 for (int i=0; i<superFieldCount; i++) { 739 instanceFields.append(superclass.instanceFields.keyAt(i), superclass.instanceFields.valueAt(i)); 740 } 741 742 fieldOffset = instanceFields.keyAt(superFieldCount-1); 743 744 String lastSuperField = superclass.instanceFields.valueAt(superFieldCount-1); 745 assert lastSuperField.indexOf(':') >= 0; 746 assert lastSuperField.indexOf(':') < superFieldCount-1; //the ':' shouldn't be the last char 747 char fieldType = lastSuperField.charAt(lastSuperField.indexOf(':') + 1); 748 if (fieldType == 'J' || fieldType == 'D') { 749 fieldOffset += 8; 750 } else { 751 fieldOffset += 4; 752 } 753 } else { 754 //the field values start at 8 bytes into the DataObject dalvik structure 755 fieldOffset = 8; 756 } 757 758 boolean gotDouble = false; 759 for (int i=0; i<fields.length; i++) { 760 String field = fields[i]; 761 762 //add padding to align the wide fields, if needed 763 if (fieldTypes[i] == WIDE && !gotDouble) { 764 if (!gotDouble) { 765 if (fieldOffset % 8 != 0) { 766 assert fieldOffset % 8 == 4; 767 fieldOffset += 4; 768 } 769 gotDouble = true; 770 } 771 } 772 773 instanceFields.append(fieldOffset, field); 774 if (fieldTypes[i] == WIDE) { 775 fieldOffset += 8; 776 } else { 777 fieldOffset += 4; 778 } 779 } 780 return instanceFields; 781 } 782 783 private byte getFieldType(String field) { 784 int sepIndex = field.indexOf(':'); 785 786 //we could use sepIndex >= field.length()-1 instead, but that's too easy to mistake for an off-by-one error 787 if (sepIndex < 0 || sepIndex == field.length()-1 || sepIndex >= field.length()) { 788 assert false; 789 throw new ExceptionWithContext("Invalid field format: " + field); 790 } 791 switch (field.charAt(sepIndex+1)) { 792 case '[': 793 case 'L': 794 return 0; //REFERENCE 795 case 'J': 796 case 'D': 797 return 1; //WIDE 798 default: 799 return 2; //OTHER 800 } 801 } 802 803 @Override 804 public boolean equals(Object o) { 805 if (this == o) return true; 806 if (!(o instanceof ClassDef)) return false; 807 808 ClassDef classDef = (ClassDef) o; 809 810 return classType.equals(classDef.classType); 811 } 812 813 @Override 814 public int hashCode() { 815 return classType.hashCode(); 816 } 817 818 public int compareTo(ClassDef classDef) { 819 return classType.compareTo(classDef.classType); 820 } 821 } 822} 823