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.Joiner; 35 import com.google.common.base.Predicates; 36 import com.google.common.base.Supplier; 37 import com.google.common.base.Suppliers; 38 import com.google.common.collect.*; 39 import com.google.common.primitives.Ints; 40 import org.jf.dexlib2.AccessFlags; 41 import org.jf.dexlib2.analysis.util.TypeProtoUtils; 42 import org.jf.dexlib2.base.reference.BaseMethodReference; 43 import org.jf.dexlib2.iface.*; 44 import org.jf.dexlib2.iface.reference.FieldReference; 45 import org.jf.dexlib2.iface.reference.MethodReference; 46 import org.jf.dexlib2.util.MethodUtil; 47 import org.jf.util.AlignmentUtils; 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.*; 54 import java.util.Map.Entry; 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 */ 60 public 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 ClassProto(@onnull ClassPath classPath, @Nonnull String type)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 toString()81 @Override public String toString() { return type; } getClassPath()82 @Nonnull @Override public ClassPath getClassPath() { return classPath; } getType()83 @Nonnull @Override public String getType() { return type; } 84 85 @Nonnull getClassDef()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 */ isInterface()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 getInterfaces()124 protected LinkedHashMap<String, ClassDef> getInterfaces() { 125 if (!classPath.isArt() || classPath.oatVersion < 72) { 126 return preDefaultMethodInterfaceSupplier.get(); 127 } else { 128 return postDefaultMethodInterfaceSupplier.get(); 129 } 130 } 131 132 /** 133 * This calculates the interfaces in the order required for vtable generation for dalvik and pre-default method ART 134 */ 135 @Nonnull 136 private final Supplier<LinkedHashMap<String, ClassDef>> preDefaultMethodInterfaceSupplier = 137 Suppliers.memoize(new Supplier<LinkedHashMap<String, ClassDef>>() { 138 @Override public LinkedHashMap<String, ClassDef> get() { 139 Set<String> unresolvedInterfaces = new HashSet<String>(0); 140 LinkedHashMap<String, ClassDef> interfaces = Maps.newLinkedHashMap(); 141 142 try { 143 for (String interfaceType: getClassDef().getInterfaces()) { 144 if (!interfaces.containsKey(interfaceType)) { 145 ClassDef interfaceDef; 146 try { 147 interfaceDef = classPath.getClassDef(interfaceType); 148 interfaces.put(interfaceType, interfaceDef); 149 } catch (UnresolvedClassException ex) { 150 interfaces.put(interfaceType, null); 151 unresolvedInterfaces.add(interfaceType); 152 interfacesFullyResolved = false; 153 } 154 155 ClassProto interfaceProto = (ClassProto) classPath.getClass(interfaceType); 156 for (String superInterface: interfaceProto.getInterfaces().keySet()) { 157 if (!interfaces.containsKey(superInterface)) { 158 interfaces.put(superInterface, 159 interfaceProto.getInterfaces().get(superInterface)); 160 } 161 } 162 if (!interfaceProto.interfacesFullyResolved) { 163 unresolvedInterfaces.addAll(interfaceProto.getUnresolvedInterfaces()); 164 interfacesFullyResolved = false; 165 } 166 } 167 } 168 } catch (UnresolvedClassException ex) { 169 interfaces.put(type, null); 170 unresolvedInterfaces.add(type); 171 interfacesFullyResolved = false; 172 } 173 174 // now add self and super class interfaces, required for common super class lookup 175 // we don't really need ClassDef's for that, so let's just use null 176 177 if (isInterface() && !interfaces.containsKey(getType())) { 178 interfaces.put(getType(), null); 179 } 180 181 String superclass = getSuperclass(); 182 try { 183 if (superclass != null) { 184 ClassProto superclassProto = (ClassProto) classPath.getClass(superclass); 185 for (String superclassInterface: superclassProto.getInterfaces().keySet()) { 186 if (!interfaces.containsKey(superclassInterface)) { 187 interfaces.put(superclassInterface, null); 188 } 189 } 190 if (!superclassProto.interfacesFullyResolved) { 191 unresolvedInterfaces.addAll(superclassProto.getUnresolvedInterfaces()); 192 interfacesFullyResolved = false; 193 } 194 } 195 } catch (UnresolvedClassException ex) { 196 unresolvedInterfaces.add(superclass); 197 interfacesFullyResolved = false; 198 } 199 200 if (unresolvedInterfaces.size() > 0) { 201 ClassProto.this.unresolvedInterfaces = unresolvedInterfaces; 202 } 203 204 return interfaces; 205 } 206 }); 207 208 /** 209 * This calculates the interfaces in the order required for vtable generation for post-default method ART 210 */ 211 @Nonnull 212 private final Supplier<LinkedHashMap<String, ClassDef>> postDefaultMethodInterfaceSupplier = 213 Suppliers.memoize(new Supplier<LinkedHashMap<String, ClassDef>>() { 214 @Override public LinkedHashMap<String, ClassDef> get() { 215 Set<String> unresolvedInterfaces = new HashSet<String>(0); 216 LinkedHashMap<String, ClassDef> interfaces = Maps.newLinkedHashMap(); 217 218 String superclass = getSuperclass(); 219 if (superclass != null) { 220 ClassProto superclassProto = (ClassProto) classPath.getClass(superclass); 221 for (String superclassInterface: superclassProto.getInterfaces().keySet()) { 222 interfaces.put(superclassInterface, null); 223 } 224 if (!superclassProto.interfacesFullyResolved) { 225 unresolvedInterfaces.addAll(superclassProto.getUnresolvedInterfaces()); 226 interfacesFullyResolved = false; 227 } 228 } 229 230 try { 231 for (String interfaceType: getClassDef().getInterfaces()) { 232 if (!interfaces.containsKey(interfaceType)) { 233 ClassProto interfaceProto = (ClassProto)classPath.getClass(interfaceType); 234 try { 235 for (Entry<String, ClassDef> entry: interfaceProto.getInterfaces().entrySet()) { 236 if (!interfaces.containsKey(entry.getKey())) { 237 interfaces.put(entry.getKey(), entry.getValue()); 238 } 239 } 240 } catch (UnresolvedClassException ex) { 241 interfaces.put(interfaceType, null); 242 unresolvedInterfaces.add(interfaceType); 243 interfacesFullyResolved = false; 244 } 245 if (!interfaceProto.interfacesFullyResolved) { 246 unresolvedInterfaces.addAll(interfaceProto.getUnresolvedInterfaces()); 247 interfacesFullyResolved = false; 248 } 249 try { 250 ClassDef interfaceDef = classPath.getClassDef(interfaceType); 251 interfaces.put(interfaceType, interfaceDef); 252 } catch (UnresolvedClassException ex) { 253 interfaces.put(interfaceType, null); 254 unresolvedInterfaces.add(interfaceType); 255 interfacesFullyResolved = false; 256 } 257 } 258 } 259 } catch (UnresolvedClassException ex) { 260 interfaces.put(type, null); 261 unresolvedInterfaces.add(type); 262 interfacesFullyResolved = false; 263 } 264 265 if (unresolvedInterfaces.size() > 0) { 266 ClassProto.this.unresolvedInterfaces = unresolvedInterfaces; 267 } 268 269 return interfaces; 270 } 271 }); 272 273 @Nonnull getUnresolvedInterfaces()274 protected Set<String> getUnresolvedInterfaces() { 275 if (unresolvedInterfaces == null) { 276 return ImmutableSet.of(); 277 } 278 return unresolvedInterfaces; 279 } 280 281 /** 282 * Gets the interfaces directly implemented by this class, or the interfaces they transitively implement. 283 * 284 * This does not include any interfaces that are only implemented by a superclass 285 * 286 * @return An iterables of ClassDefs representing the directly or transitively implemented interfaces 287 * @throws UnresolvedClassException if interfaces could not be fully resolved 288 */ 289 @Nonnull getDirectInterfaces()290 protected Iterable<ClassDef> getDirectInterfaces() { 291 Iterable<ClassDef> directInterfaces = 292 Iterables.filter(getInterfaces().values(), Predicates.notNull()); 293 294 if (!interfacesFullyResolved) { 295 throw new UnresolvedClassException("Interfaces for class %s not fully resolved: %s", getType(), 296 Joiner.on(',').join(getUnresolvedInterfaces())); 297 } 298 299 return directInterfaces; 300 } 301 302 /** 303 * Checks if this class implements the given interface. 304 * 305 * If the interfaces of this class cannot be fully resolved then this 306 * method will either return true or throw an UnresolvedClassException 307 * 308 * @param iface The interface to check for 309 * @return true if this class implements the given interface, otherwise false 310 * @throws UnresolvedClassException if the interfaces for this class could not be fully resolved, and the interface 311 * is not one of the interfaces that were successfully resolved 312 */ 313 @Override implementsInterface(@onnull String iface)314 public boolean implementsInterface(@Nonnull String iface) { 315 if (getInterfaces().containsKey(iface)) { 316 return true; 317 } 318 if (!interfacesFullyResolved) { 319 throw new UnresolvedClassException("Interfaces for class %s not fully resolved", getType()); 320 } 321 return false; 322 } 323 324 @Nullable @Override getSuperclass()325 public String getSuperclass() { 326 return getClassDef().getSuperclass(); 327 } 328 329 /** 330 * This is a helper method for getCommonSuperclass 331 * 332 * It checks if this class is an interface, and if so, if other implements it. 333 * 334 * If this class is undefined, we go ahead and check if it is listed in other's interfaces. If not, we throw an 335 * UndefinedClassException 336 * 337 * If the interfaces of other cannot be fully resolved, we check the interfaces that can be resolved. If not found, 338 * we throw an UndefinedClassException 339 * 340 * @param other The class to check the interfaces of 341 * @return true if this class is an interface (or is undefined) other implements this class 342 * 343 */ checkInterface(@onnull ClassProto other)344 private boolean checkInterface(@Nonnull ClassProto other) { 345 boolean isResolved = true; 346 boolean isInterface = true; 347 try { 348 isInterface = isInterface(); 349 } catch (UnresolvedClassException ex) { 350 isResolved = false; 351 // if we don't know if this class is an interface or not, 352 // we can still try to call other.implementsInterface(this) 353 } 354 if (isInterface) { 355 try { 356 if (other.implementsInterface(getType())) { 357 return true; 358 } 359 } catch (UnresolvedClassException ex) { 360 // There are 2 possibilities here, depending on whether we were able to resolve this class. 361 // 1. If this class is resolved, then we know it is an interface class. The other class either 362 // isn't defined, or its interfaces couldn't be fully resolved. 363 // In this case, we throw an UnresolvedClassException 364 // 2. If this class is not resolved, we had tried to call implementsInterface anyway. We don't 365 // know for sure if this class is an interface or not. We return false, and let processing 366 // continue in getCommonSuperclass 367 if (isResolved) { 368 throw ex; 369 } 370 } 371 } 372 return false; 373 } 374 375 @Override @Nonnull getCommonSuperclass(@onnull TypeProto other)376 public TypeProto getCommonSuperclass(@Nonnull TypeProto other) { 377 // use the other type's more specific implementation 378 if (!(other instanceof ClassProto)) { 379 return other.getCommonSuperclass(this); 380 } 381 382 if (this == other || getType().equals(other.getType())) { 383 return this; 384 } 385 386 if (this.getType().equals("Ljava/lang/Object;")) { 387 return this; 388 } 389 390 if (other.getType().equals("Ljava/lang/Object;")) { 391 return other; 392 } 393 394 boolean gotException = false; 395 try { 396 if (checkInterface((ClassProto)other)) { 397 return this; 398 } 399 } catch (UnresolvedClassException ex) { 400 gotException = true; 401 } 402 403 try { 404 if (((ClassProto)other).checkInterface(this)) { 405 return other; 406 } 407 } catch (UnresolvedClassException ex) { 408 gotException = true; 409 } 410 if (gotException) { 411 return classPath.getUnknownClass(); 412 } 413 414 List<TypeProto> thisChain = Lists.<TypeProto>newArrayList(this); 415 Iterables.addAll(thisChain, TypeProtoUtils.getSuperclassChain(this)); 416 417 List<TypeProto> otherChain = Lists.newArrayList(other); 418 Iterables.addAll(otherChain, TypeProtoUtils.getSuperclassChain(other)); 419 420 // reverse them, so that the first entry is either Ljava/lang/Object; or Ujava/lang/Object; 421 thisChain = Lists.reverse(thisChain); 422 otherChain = Lists.reverse(otherChain); 423 424 for (int i=Math.min(thisChain.size(), otherChain.size())-1; i>=0; i--) { 425 TypeProto typeProto = thisChain.get(i); 426 if (typeProto.getType().equals(otherChain.get(i).getType())) { 427 return typeProto; 428 } 429 } 430 431 return classPath.getUnknownClass(); 432 } 433 434 @Override 435 @Nullable getFieldByOffset(int fieldOffset)436 public FieldReference getFieldByOffset(int fieldOffset) { 437 if (getInstanceFields().size() == 0) { 438 return null; 439 } 440 return getInstanceFields().get(fieldOffset); 441 } 442 443 @Override 444 @Nullable getMethodByVtableIndex(int vtableIndex)445 public Method getMethodByVtableIndex(int vtableIndex) { 446 List<Method> vtable = getVtable(); 447 if (vtableIndex < 0 || vtableIndex >= vtable.size()) { 448 return null; 449 } 450 451 return vtable.get(vtableIndex); 452 } 453 findMethodIndexInVtable(@onnull MethodReference method)454 public int findMethodIndexInVtable(@Nonnull MethodReference method) { 455 return findMethodIndexInVtable(getVtable(), method); 456 } 457 findMethodIndexInVtable(@onnull List<Method> vtable, MethodReference method)458 private int findMethodIndexInVtable(@Nonnull List<Method> vtable, MethodReference method) { 459 for (int i=0; i<vtable.size(); i++) { 460 Method candidate = vtable.get(i); 461 if (MethodUtil.methodSignaturesMatch(candidate, method)) { 462 if (!classPath.shouldCheckPackagePrivateAccess() || 463 AnalyzedMethodUtil.canAccess(this, candidate, true, false, false)) { 464 return i; 465 } 466 } 467 } 468 return -1; 469 } 470 findMethodIndexInVtableReverse(@onnull List<Method> vtable, MethodReference method)471 private int findMethodIndexInVtableReverse(@Nonnull List<Method> vtable, MethodReference method) { 472 for (int i=vtable.size() - 1; i>=0; i--) { 473 Method candidate = vtable.get(i); 474 if (MethodUtil.methodSignaturesMatch(candidate, method)) { 475 if (!classPath.shouldCheckPackagePrivateAccess() || 476 AnalyzedMethodUtil.canAccess(this, candidate, true, false, false)) { 477 return i; 478 } 479 } 480 } 481 return -1; 482 } 483 getInstanceFields()484 @Nonnull public SparseArray<FieldReference> getInstanceFields() { 485 if (classPath.isArt()) { 486 return artInstanceFieldsSupplier.get(); 487 } else { 488 return dalvikInstanceFieldsSupplier.get(); 489 } 490 } 491 492 @Nonnull private final Supplier<SparseArray<FieldReference>> dalvikInstanceFieldsSupplier = 493 Suppliers.memoize(new Supplier<SparseArray<FieldReference>>() { 494 @Override public SparseArray<FieldReference> get() { 495 //This is a bit of an "involved" operation. We need to follow the same algorithm that dalvik uses to 496 //arrange fields, so that we end up with the same field offsets (which is needed for deodexing). 497 //See mydroid/dalvik/vm/oo/Class.c - computeFieldOffsets() 498 499 ArrayList<Field> fields = getSortedInstanceFields(getClassDef()); 500 final int fieldCount = fields.size(); 501 //the "type" for each field in fields. 0=reference,1=wide,2=other 502 byte[] fieldTypes = new byte[fields.size()]; 503 for (int i=0; i<fieldCount; i++) { 504 fieldTypes[i] = getFieldType(fields.get(i)); 505 } 506 507 //The first operation is to move all of the reference fields to the front. To do this, find the first 508 //non-reference field, then find the last reference field, swap them and repeat 509 int back = fields.size() - 1; 510 int front; 511 for (front = 0; front<fieldCount; front++) { 512 if (fieldTypes[front] != REFERENCE) { 513 while (back > front) { 514 if (fieldTypes[back] == REFERENCE) { 515 swap(fieldTypes, fields, front, back--); 516 break; 517 } 518 back--; 519 } 520 } 521 522 if (fieldTypes[front] != REFERENCE) { 523 break; 524 } 525 } 526 527 int startFieldOffset = 8; 528 String superclassType = getSuperclass(); 529 ClassProto superclass = null; 530 if (superclassType != null) { 531 superclass = (ClassProto) classPath.getClass(superclassType); 532 startFieldOffset = superclass.getNextFieldOffset(); 533 } 534 535 int fieldIndexMod; 536 if ((startFieldOffset % 8) == 0) { 537 fieldIndexMod = 0; 538 } else { 539 fieldIndexMod = 1; 540 } 541 542 //next, we need to group all the wide fields after the reference fields. But the wide fields have to be 543 //8-byte aligned. If we're on an odd field index, we need to insert a 32-bit field. If the next field 544 //is already a 32-bit field, use that. Otherwise, find the first 32-bit field from the end and swap it in. 545 //If there are no 32-bit fields, do nothing for now. We'll add padding when calculating the field offsets 546 if (front < fieldCount && (front % 2) != fieldIndexMod) { 547 if (fieldTypes[front] == WIDE) { 548 //we need to swap in a 32-bit field, so the wide fields will be correctly aligned 549 back = fieldCount - 1; 550 while (back > front) { 551 if (fieldTypes[back] == OTHER) { 552 swap(fieldTypes, fields, front++, back); 553 break; 554 } 555 back--; 556 } 557 } else { 558 //there's already a 32-bit field here that we can use 559 front++; 560 } 561 } 562 563 //do the swap thing for wide fields 564 back = fieldCount - 1; 565 for (; front<fieldCount; front++) { 566 if (fieldTypes[front] != WIDE) { 567 while (back > front) { 568 if (fieldTypes[back] == WIDE) { 569 swap(fieldTypes, fields, front, back--); 570 break; 571 } 572 back--; 573 } 574 } 575 576 if (fieldTypes[front] != WIDE) { 577 break; 578 } 579 } 580 581 SparseArray<FieldReference> superFields; 582 if (superclass != null) { 583 superFields = superclass.getInstanceFields(); 584 } else { 585 superFields = new SparseArray<FieldReference>(); 586 } 587 int superFieldCount = superFields.size(); 588 589 //now the fields are in the correct order. Add them to the SparseArray and lookup, and calculate the offsets 590 int totalFieldCount = superFieldCount + fieldCount; 591 SparseArray<FieldReference> instanceFields = new SparseArray<FieldReference>(totalFieldCount); 592 593 int fieldOffset; 594 595 if (superclass != null && superFieldCount > 0) { 596 for (int i=0; i<superFieldCount; i++) { 597 instanceFields.append(superFields.keyAt(i), superFields.valueAt(i)); 598 } 599 600 fieldOffset = instanceFields.keyAt(superFieldCount-1); 601 602 FieldReference lastSuperField = superFields.valueAt(superFieldCount-1); 603 char fieldType = lastSuperField.getType().charAt(0); 604 if (fieldType == 'J' || fieldType == 'D') { 605 fieldOffset += 8; 606 } else { 607 fieldOffset += 4; 608 } 609 } else { 610 //the field values start at 8 bytes into the DataObject dalvik structure 611 fieldOffset = 8; 612 } 613 614 boolean gotDouble = false; 615 for (int i=0; i<fieldCount; i++) { 616 FieldReference field = fields.get(i); 617 618 //add padding to align the wide fields, if needed 619 if (fieldTypes[i] == WIDE && !gotDouble) { 620 if (fieldOffset % 8 != 0) { 621 assert fieldOffset % 8 == 4; 622 fieldOffset += 4; 623 } 624 gotDouble = true; 625 } 626 627 instanceFields.append(fieldOffset, field); 628 if (fieldTypes[i] == WIDE) { 629 fieldOffset += 8; 630 } else { 631 fieldOffset += 4; 632 } 633 } 634 635 return instanceFields; 636 } 637 638 @Nonnull 639 private ArrayList<Field> getSortedInstanceFields(@Nonnull ClassDef classDef) { 640 ArrayList<Field> fields = Lists.newArrayList(classDef.getInstanceFields()); 641 Collections.sort(fields); 642 return fields; 643 } 644 645 private void swap(byte[] fieldTypes, List<Field> fields, int position1, int position2) { 646 byte tempType = fieldTypes[position1]; 647 fieldTypes[position1] = fieldTypes[position2]; 648 fieldTypes[position2] = tempType; 649 650 Field tempField = fields.set(position1, fields.get(position2)); 651 fields.set(position2, tempField); 652 } 653 }); 654 655 private static abstract class FieldGap implements Comparable<FieldGap> { 656 public final int offset; 657 public final int size; 658 newFieldGap(int offset, int size, int oatVersion)659 public static FieldGap newFieldGap(int offset, int size, int oatVersion) { 660 if (oatVersion >= 67) { 661 return new FieldGap(offset, size) { 662 @Override public int compareTo(@Nonnull FieldGap o) { 663 int result = Ints.compare(o.size, size); 664 if (result != 0) { 665 return result; 666 } 667 return Ints.compare(offset, o.offset); 668 } 669 }; 670 } else { 671 return new FieldGap(offset, size) { 672 @Override public int compareTo(@Nonnull FieldGap o) { 673 int result = Ints.compare(size, o.size); 674 if (result != 0) { 675 return result; 676 } 677 return Ints.compare(o.offset, offset); 678 } 679 }; 680 } 681 } 682 683 private FieldGap(int offset, int size) { 684 this.offset = offset; 685 this.size = size; 686 } 687 } 688 689 @Nonnull private final Supplier<SparseArray<FieldReference>> artInstanceFieldsSupplier = 690 Suppliers.memoize(new Supplier<SparseArray<FieldReference>>() { 691 692 @Override public SparseArray<FieldReference> get() { 693 // We need to follow the same algorithm that art uses to arrange fields, so that we end up with the 694 // same field offsets, which is needed for deodexing. 695 // See LinkFields() in art/runtime/class_linker.cc 696 697 PriorityQueue<FieldGap> gaps = new PriorityQueue<FieldGap>(); 698 699 SparseArray<FieldReference> linkedFields = new SparseArray<FieldReference>(); 700 ArrayList<Field> fields = getSortedInstanceFields(getClassDef()); 701 702 int fieldOffset = 0; 703 String superclassType = getSuperclass(); 704 if (superclassType != null) { 705 // TODO: what to do if superclass doesn't exist? 706 ClassProto superclass = (ClassProto) classPath.getClass(superclassType); 707 SparseArray<FieldReference> superFields = superclass.getInstanceFields(); 708 FieldReference field = null; 709 int lastOffset = 0; 710 for (int i=0; i<superFields.size(); i++) { 711 int offset = superFields.keyAt(i); 712 field = superFields.valueAt(i); 713 linkedFields.put(offset, field); 714 lastOffset = offset; 715 } 716 if (field != null) { 717 fieldOffset = lastOffset + getFieldSize(field); 718 } 719 } 720 721 for (Field field: fields) { 722 int fieldSize = getFieldSize(field); 723 724 if (!AlignmentUtils.isAligned(fieldOffset, fieldSize)) { 725 int oldOffset = fieldOffset; 726 fieldOffset = AlignmentUtils.alignOffset(fieldOffset, fieldSize); 727 addFieldGap(oldOffset, fieldOffset, gaps); 728 } 729 730 FieldGap gap = gaps.peek(); 731 if (gap != null && gap.size >= fieldSize) { 732 gaps.poll(); 733 linkedFields.put(gap.offset, field); 734 if (gap.size > fieldSize) { 735 addFieldGap(gap.offset + fieldSize, gap.offset + gap.size, gaps); 736 } 737 } else { 738 linkedFields.append(fieldOffset, field); 739 fieldOffset += fieldSize; 740 } 741 } 742 743 return linkedFields; 744 } 745 746 private void addFieldGap(int gapStart, int gapEnd, @Nonnull PriorityQueue<FieldGap> gaps) { 747 int offset = gapStart; 748 749 while (offset < gapEnd) { 750 int remaining = gapEnd - offset; 751 752 if ((remaining >= 4) && (offset % 4 == 0)) { 753 gaps.add(FieldGap.newFieldGap(offset, 4, classPath.oatVersion)); 754 offset += 4; 755 } else if (remaining >= 2 && (offset % 2 == 0)) { 756 gaps.add(FieldGap.newFieldGap(offset, 2, classPath.oatVersion)); 757 offset += 2; 758 } else { 759 gaps.add(FieldGap.newFieldGap(offset, 1, classPath.oatVersion)); 760 offset += 1; 761 } 762 } 763 } 764 765 @Nonnull 766 private ArrayList<Field> getSortedInstanceFields(@Nonnull ClassDef classDef) { 767 ArrayList<Field> fields = Lists.newArrayList(classDef.getInstanceFields()); 768 Collections.sort(fields, new Comparator<Field>() { 769 @Override public int compare(Field field1, Field field2) { 770 int result = Ints.compare(getFieldSortOrder(field1), getFieldSortOrder(field2)); 771 if (result != 0) { 772 return result; 773 } 774 775 result = field1.getName().compareTo(field2.getName()); 776 if (result != 0) { 777 return result; 778 } 779 return field1.getType().compareTo(field2.getType()); 780 } 781 }); 782 return fields; 783 } 784 785 private int getFieldSortOrder(@Nonnull FieldReference field) { 786 // The sort order is based on type size (except references are first), and then based on the 787 // enum value of the primitive type for types of equal size. See: Primitive::Type enum 788 // in art/runtime/primitive.h 789 switch (field.getType().charAt(0)) { 790 /* reference */ 791 case '[': 792 case 'L': 793 return 0; 794 /* 64 bit */ 795 case 'J': 796 return 1; 797 case 'D': 798 return 2; 799 /* 32 bit */ 800 case 'I': 801 return 3; 802 case 'F': 803 return 4; 804 /* 16 bit */ 805 case 'C': 806 return 5; 807 case 'S': 808 return 6; 809 /* 8 bit */ 810 case 'Z': 811 return 7; 812 case 'B': 813 return 8; 814 } 815 throw new ExceptionWithContext("Invalid field type: %s", field.getType()); 816 } 817 818 private int getFieldSize(@Nonnull FieldReference field) { 819 return getTypeSize(field.getType().charAt(0)); 820 } 821 }); 822 823 private int getNextFieldOffset() { 824 SparseArray<FieldReference> instanceFields = getInstanceFields(); 825 if (instanceFields.size() == 0) { 826 return classPath.isArt() ? 0 : 8; 827 } 828 829 int lastItemIndex = instanceFields.size()-1; 830 int fieldOffset = instanceFields.keyAt(lastItemIndex); 831 FieldReference lastField = instanceFields.valueAt(lastItemIndex); 832 833 if (classPath.isArt()) { 834 return fieldOffset + getTypeSize(lastField.getType().charAt(0)); 835 } else { 836 switch (lastField.getType().charAt(0)) { 837 case 'J': 838 case 'D': 839 return fieldOffset + 8; 840 default: 841 return fieldOffset + 4; 842 } 843 } 844 } 845 846 private static int getTypeSize(char type) { 847 switch (type) { 848 case 'J': 849 case 'D': 850 return 8; 851 case '[': 852 case 'L': 853 case 'I': 854 case 'F': 855 return 4; 856 case 'C': 857 case 'S': 858 return 2; 859 case 'B': 860 case 'Z': 861 return 1; 862 } 863 throw new ExceptionWithContext("Invalid type: %s", type); 864 } 865 866 @Nonnull public List<Method> getVtable() { 867 if (!classPath.isArt() || classPath.oatVersion < 72) { 868 return preDefaultMethodVtableSupplier.get(); 869 } else if (classPath.oatVersion < 87) { 870 return buggyPostDefaultMethodVtableSupplier.get(); 871 } else { 872 return postDefaultMethodVtableSupplier.get(); 873 } 874 } 875 876 //TODO: check the case when we have a package private method that overrides an interface method 877 @Nonnull private final Supplier<List<Method>> preDefaultMethodVtableSupplier = Suppliers.memoize(new Supplier<List<Method>>() { 878 @Override public List<Method> get() { 879 List<Method> vtable = Lists.newArrayList(); 880 881 //copy the virtual methods from the superclass 882 String superclassType; 883 try { 884 superclassType = getSuperclass(); 885 } catch (UnresolvedClassException ex) { 886 vtable.addAll(((ClassProto)classPath.getClass("Ljava/lang/Object;")).getVtable()); 887 vtableFullyResolved = false; 888 return vtable; 889 } 890 891 if (superclassType != null) { 892 ClassProto superclass = (ClassProto) classPath.getClass(superclassType); 893 vtable.addAll(superclass.getVtable()); 894 895 // if the superclass's vtable wasn't fully resolved, then we can't know where the new methods added by this 896 // class should start, so we just propagate what we can from the parent and hope for the best. 897 if (!superclass.vtableFullyResolved) { 898 vtableFullyResolved = false; 899 return vtable; 900 } 901 } 902 903 //iterate over the virtual methods in the current class, and only add them when we don't already have the 904 //method (i.e. if it was implemented by the superclass) 905 if (!isInterface()) { 906 addToVtable(getClassDef().getVirtualMethods(), vtable, true, true); 907 908 // We use the current class for any vtable method references that we add, rather than the interface, so 909 // we don't end up trying to call invoke-virtual using an interface, which will fail verification 910 Iterable<ClassDef> interfaces = getDirectInterfaces(); 911 for (ClassDef interfaceDef: interfaces) { 912 List<Method> interfaceMethods = Lists.newArrayList(); 913 for (Method interfaceMethod: interfaceDef.getVirtualMethods()) { 914 interfaceMethods.add(new ReparentedMethod(interfaceMethod, type)); 915 } 916 addToVtable(interfaceMethods, vtable, false, true); 917 } 918 } 919 return vtable; 920 } 921 }); 922 923 /** 924 * This is the vtable supplier for a version of art that had buggy vtable calculation logic. In some cases it can 925 * produce multiple vtable entries for a given virtual method. This supplier duplicates this buggy logic in order to 926 * generate an identical vtable 927 */ 928 @Nonnull private final Supplier<List<Method>> buggyPostDefaultMethodVtableSupplier = Suppliers.memoize(new Supplier<List<Method>>() { 929 @Override public List<Method> get() { 930 List<Method> vtable = Lists.newArrayList(); 931 932 //copy the virtual methods from the superclass 933 String superclassType; 934 try { 935 superclassType = getSuperclass(); 936 } catch (UnresolvedClassException ex) { 937 vtable.addAll(((ClassProto)classPath.getClass("Ljava/lang/Object;")).getVtable()); 938 vtableFullyResolved = false; 939 return vtable; 940 } 941 942 if (superclassType != null) { 943 ClassProto superclass = (ClassProto) classPath.getClass(superclassType); 944 vtable.addAll(superclass.getVtable()); 945 946 // if the superclass's vtable wasn't fully resolved, then we can't know where the new methods added by 947 // this class should start, so we just propagate what we can from the parent and hope for the best. 948 if (!superclass.vtableFullyResolved) { 949 vtableFullyResolved = false; 950 return vtable; 951 } 952 } 953 954 //iterate over the virtual methods in the current class, and only add them when we don't already have the 955 //method (i.e. if it was implemented by the superclass) 956 if (!isInterface()) { 957 addToVtable(getClassDef().getVirtualMethods(), vtable, true, true); 958 959 List<String> interfaces = Lists.newArrayList(getInterfaces().keySet()); 960 961 List<Method> defaultMethods = Lists.newArrayList(); 962 List<Method> defaultConflictMethods = Lists.newArrayList(); 963 List<Method> mirandaMethods = Lists.newArrayList(); 964 965 final HashMap<MethodReference, Integer> methodOrder = Maps.newHashMap(); 966 967 for (int i=interfaces.size()-1; i>=0; i--) { 968 String interfaceType = interfaces.get(i); 969 ClassDef interfaceDef = classPath.getClassDef(interfaceType); 970 971 for (Method interfaceMethod : interfaceDef.getVirtualMethods()) { 972 973 int vtableIndex = findMethodIndexInVtableReverse(vtable, interfaceMethod); 974 Method oldVtableMethod = null; 975 if (vtableIndex >= 0) { 976 oldVtableMethod = vtable.get(vtableIndex); 977 } 978 979 for (int j=0; j<vtable.size(); j++) { 980 Method candidate = vtable.get(j); 981 if (MethodUtil.methodSignaturesMatch(candidate, interfaceMethod)) { 982 if (!classPath.shouldCheckPackagePrivateAccess() || 983 AnalyzedMethodUtil.canAccess(ClassProto.this, candidate, true, false, false)) { 984 if (interfaceMethodOverrides(interfaceMethod, candidate)) { 985 vtable.set(j, interfaceMethod); 986 } 987 } 988 } 989 } 990 991 if (vtableIndex >= 0) { 992 if (!isOverridableByDefaultMethod(vtable.get(vtableIndex))) { 993 continue; 994 } 995 } 996 997 int defaultMethodIndex = findMethodIndexInVtable(defaultMethods, interfaceMethod); 998 999 if (defaultMethodIndex >= 0) { 1000 if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) { 1001 ClassProto existingInterface = (ClassProto)classPath.getClass( 1002 defaultMethods.get(defaultMethodIndex).getDefiningClass()); 1003 if (!existingInterface.implementsInterface(interfaceMethod.getDefiningClass())) { 1004 Method removedMethod = defaultMethods.remove(defaultMethodIndex); 1005 defaultConflictMethods.add(removedMethod); 1006 } 1007 } 1008 continue; 1009 } 1010 1011 int defaultConflictMethodIndex = findMethodIndexInVtable( 1012 defaultConflictMethods, interfaceMethod); 1013 if (defaultConflictMethodIndex >= 0) { 1014 // There's already a matching method in the conflict list, we don't need to do 1015 // anything else 1016 continue; 1017 } 1018 1019 int mirandaMethodIndex = findMethodIndexInVtable(mirandaMethods, interfaceMethod); 1020 1021 if (mirandaMethodIndex >= 0) { 1022 if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) { 1023 1024 ClassProto existingInterface = (ClassProto)classPath.getClass( 1025 mirandaMethods.get(mirandaMethodIndex).getDefiningClass()); 1026 if (!existingInterface.implementsInterface(interfaceMethod.getDefiningClass())) { 1027 Method oldMethod = mirandaMethods.remove(mirandaMethodIndex); 1028 int methodOrderValue = methodOrder.get(oldMethod); 1029 methodOrder.put(interfaceMethod, methodOrderValue); 1030 defaultMethods.add(interfaceMethod); 1031 } 1032 } 1033 continue; 1034 } 1035 1036 if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) { 1037 if (oldVtableMethod != null) { 1038 if (!interfaceMethodOverrides(interfaceMethod, oldVtableMethod)) { 1039 continue; 1040 } 1041 } 1042 defaultMethods.add(interfaceMethod); 1043 methodOrder.put(interfaceMethod, methodOrder.size()); 1044 } else { 1045 // TODO: do we need to check interfaceMethodOverrides here? 1046 if (oldVtableMethod == null) { 1047 mirandaMethods.add(interfaceMethod); 1048 methodOrder.put(interfaceMethod, methodOrder.size()); 1049 } 1050 } 1051 } 1052 } 1053 1054 Comparator<MethodReference> comparator = new Comparator<MethodReference>() { 1055 @Override public int compare(MethodReference o1, MethodReference o2) { 1056 return Ints.compare(methodOrder.get(o1), methodOrder.get(o2)); 1057 } 1058 }; 1059 1060 // The methods should be in the same order within each list as they were iterated over. 1061 // They can be misordered if, e.g. a method was originally added to the default list, but then moved 1062 // to the conflict list. 1063 Collections.sort(mirandaMethods, comparator); 1064 Collections.sort(defaultMethods, comparator); 1065 Collections.sort(defaultConflictMethods, comparator); 1066 1067 vtable.addAll(mirandaMethods); 1068 vtable.addAll(defaultMethods); 1069 vtable.addAll(defaultConflictMethods); 1070 } 1071 return vtable; 1072 } 1073 }); 1074 1075 @Nonnull private final Supplier<List<Method>> postDefaultMethodVtableSupplier = Suppliers.memoize(new Supplier<List<Method>>() { 1076 @Override public List<Method> get() { 1077 List<Method> vtable = Lists.newArrayList(); 1078 1079 //copy the virtual methods from the superclass 1080 String superclassType; 1081 try { 1082 superclassType = getSuperclass(); 1083 } catch (UnresolvedClassException ex) { 1084 vtable.addAll(((ClassProto)classPath.getClass("Ljava/lang/Object;")).getVtable()); 1085 vtableFullyResolved = false; 1086 return vtable; 1087 } 1088 1089 if (superclassType != null) { 1090 ClassProto superclass = (ClassProto) classPath.getClass(superclassType); 1091 vtable.addAll(superclass.getVtable()); 1092 1093 // if the superclass's vtable wasn't fully resolved, then we can't know where the new methods added by 1094 // this class should start, so we just propagate what we can from the parent and hope for the best. 1095 if (!superclass.vtableFullyResolved) { 1096 vtableFullyResolved = false; 1097 return vtable; 1098 } 1099 } 1100 1101 //iterate over the virtual methods in the current class, and only add them when we don't already have the 1102 //method (i.e. if it was implemented by the superclass) 1103 if (!isInterface()) { 1104 addToVtable(getClassDef().getVirtualMethods(), vtable, true, true); 1105 1106 Iterable<ClassDef> interfaces = Lists.reverse(Lists.newArrayList(getDirectInterfaces())); 1107 1108 List<Method> defaultMethods = Lists.newArrayList(); 1109 List<Method> defaultConflictMethods = Lists.newArrayList(); 1110 List<Method> mirandaMethods = Lists.newArrayList(); 1111 1112 final HashMap<MethodReference, Integer> methodOrder = Maps.newHashMap(); 1113 1114 for (ClassDef interfaceDef: interfaces) { 1115 for (Method interfaceMethod : interfaceDef.getVirtualMethods()) { 1116 1117 int vtableIndex = findMethodIndexInVtable(vtable, interfaceMethod); 1118 1119 if (vtableIndex >= 0) { 1120 if (interfaceMethodOverrides(interfaceMethod, vtable.get(vtableIndex))) { 1121 vtable.set(vtableIndex, interfaceMethod); 1122 } 1123 } else { 1124 int defaultMethodIndex = findMethodIndexInVtable(defaultMethods, interfaceMethod); 1125 1126 if (defaultMethodIndex >= 0) { 1127 if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) { 1128 ClassProto existingInterface = (ClassProto)classPath.getClass( 1129 defaultMethods.get(defaultMethodIndex).getDefiningClass()); 1130 if (!existingInterface.implementsInterface(interfaceMethod.getDefiningClass())) { 1131 Method removedMethod = defaultMethods.remove(defaultMethodIndex); 1132 defaultConflictMethods.add(removedMethod); 1133 } 1134 } 1135 continue; 1136 } 1137 1138 int defaultConflictMethodIndex = findMethodIndexInVtable( 1139 defaultConflictMethods, interfaceMethod); 1140 if (defaultConflictMethodIndex >= 0) { 1141 // There's already a matching method in the conflict list, we don't need to do 1142 // anything else 1143 continue; 1144 } 1145 1146 int mirandaMethodIndex = findMethodIndexInVtable(mirandaMethods, interfaceMethod); 1147 1148 if (mirandaMethodIndex >= 0) { 1149 if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) { 1150 1151 ClassProto existingInterface = (ClassProto)classPath.getClass( 1152 mirandaMethods.get(mirandaMethodIndex).getDefiningClass()); 1153 if (!existingInterface.implementsInterface(interfaceMethod.getDefiningClass())) { 1154 Method oldMethod = mirandaMethods.remove(mirandaMethodIndex); 1155 int methodOrderValue = methodOrder.get(oldMethod); 1156 methodOrder.put(interfaceMethod, methodOrderValue); 1157 defaultMethods.add(interfaceMethod); 1158 } 1159 } 1160 continue; 1161 } 1162 1163 if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) { 1164 defaultMethods.add(interfaceMethod); 1165 methodOrder.put(interfaceMethod, methodOrder.size()); 1166 } else { 1167 mirandaMethods.add(interfaceMethod); 1168 methodOrder.put(interfaceMethod, methodOrder.size()); 1169 } 1170 } 1171 } 1172 } 1173 1174 Comparator<MethodReference> comparator = new Comparator<MethodReference>() { 1175 @Override public int compare(MethodReference o1, MethodReference o2) { 1176 return Ints.compare(methodOrder.get(o1), methodOrder.get(o2)); 1177 } 1178 }; 1179 1180 // The methods should be in the same order within each list as they were iterated over. 1181 // They can be misordered if, e.g. a method was originally added to the default list, but then moved 1182 // to the conflict list. 1183 Collections.sort(defaultMethods, comparator); 1184 Collections.sort(defaultConflictMethods, comparator); 1185 Collections.sort(mirandaMethods, comparator); 1186 addToVtable(defaultMethods, vtable, false, false); 1187 addToVtable(defaultConflictMethods, vtable, false, false); 1188 addToVtable(mirandaMethods, vtable, false, false); 1189 } 1190 return vtable; 1191 } 1192 }); 1193 1194 private void addToVtable(@Nonnull Iterable<? extends Method> localMethods, @Nonnull List<Method> vtable, 1195 boolean replaceExisting, boolean sort) { 1196 if (sort) { 1197 ArrayList<Method> methods = Lists.newArrayList(localMethods); 1198 Collections.sort(methods); 1199 localMethods = methods; 1200 } 1201 1202 for (Method virtualMethod: localMethods) { 1203 int vtableIndex = findMethodIndexInVtable(vtable, virtualMethod); 1204 1205 if (vtableIndex >= 0) { 1206 if (replaceExisting) { 1207 vtable.set(vtableIndex, virtualMethod); 1208 } 1209 } else { 1210 // we didn't find an equivalent method, so add it as a new entry 1211 vtable.add(virtualMethod); 1212 } 1213 } 1214 } 1215 1216 private static byte getFieldType(@Nonnull FieldReference field) { 1217 switch (field.getType().charAt(0)) { 1218 case '[': 1219 case 'L': 1220 return 0; //REFERENCE 1221 case 'J': 1222 case 'D': 1223 return 1; //WIDE 1224 default: 1225 return 2; //OTHER 1226 } 1227 } 1228 1229 private boolean isOverridableByDefaultMethod(@Nonnull Method method) { 1230 ClassProto classProto = (ClassProto)classPath.getClass(method.getDefiningClass()); 1231 return classProto.isInterface(); 1232 } 1233 1234 /** 1235 * Checks if the interface method overrides the virtual or interface method2 1236 * @param method A Method from an interface 1237 * @param method2 A Method from an interface or a class 1238 * @return true if the interface method overrides the virtual or interface method2 1239 */ 1240 private boolean interfaceMethodOverrides(@Nonnull Method method, @Nonnull Method method2) { 1241 ClassProto classProto = (ClassProto)classPath.getClass(method2.getDefiningClass()); 1242 1243 if (classProto.isInterface()) { 1244 ClassProto targetClassProto = (ClassProto)classPath.getClass(method.getDefiningClass()); 1245 return targetClassProto.implementsInterface(method2.getDefiningClass()); 1246 } else { 1247 return false; 1248 } 1249 } 1250 1251 static class ReparentedMethod extends BaseMethodReference implements Method { 1252 private final Method method; 1253 private final String definingClass; 1254 1255 public ReparentedMethod(Method method, String definingClass) { 1256 this.method = method; 1257 this.definingClass = definingClass; 1258 } 1259 1260 @Nonnull @Override public String getDefiningClass() { 1261 return definingClass; 1262 } 1263 1264 @Nonnull @Override public String getName() { 1265 return method.getName(); 1266 } 1267 1268 @Nonnull @Override public List<? extends CharSequence> getParameterTypes() { 1269 return method.getParameterTypes(); 1270 } 1271 1272 @Nonnull @Override public String getReturnType() { 1273 return method.getReturnType(); 1274 } 1275 1276 @Nonnull @Override public List<? extends MethodParameter> getParameters() { 1277 return method.getParameters(); 1278 } 1279 1280 @Override public int getAccessFlags() { 1281 return method.getAccessFlags(); 1282 } 1283 1284 @Nonnull @Override public Set<? extends Annotation> getAnnotations() { 1285 return method.getAnnotations(); 1286 } 1287 1288 @Nullable @Override public MethodImplementation getImplementation() { 1289 return method.getImplementation(); 1290 } 1291 } 1292 } 1293