1/* 2 * Copyright (C) 2007 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.android.dx.cf.code; 18 19import com.android.dx.rop.code.LocalItem; 20import com.android.dx.rop.cst.Constant; 21import com.android.dx.rop.cst.CstFieldRef; 22import com.android.dx.rop.cst.CstInteger; 23import com.android.dx.rop.cst.CstInterfaceMethodRef; 24import com.android.dx.rop.cst.CstMethodRef; 25import com.android.dx.rop.cst.CstType; 26import com.android.dx.rop.type.Prototype; 27import com.android.dx.rop.type.Type; 28import com.android.dx.util.Hex; 29import java.util.ArrayList; 30 31/** 32 * Class which knows how to simulate the effects of executing bytecode. 33 * 34 * <p><b>Note:</b> This class is not thread-safe. If multiple threads 35 * need to use a single instance, they must synchronize access explicitly 36 * between themselves.</p> 37 */ 38public class Simulator { 39 /** 40 * {@code non-null;} canned error message for local variable 41 * table mismatches 42 */ 43 private static final String LOCAL_MISMATCH_ERROR = 44 "This is symptomatic of .class transformation tools that ignore " + 45 "local variable information."; 46 47 /** {@code non-null;} machine to use when simulating */ 48 private final Machine machine; 49 50 /** {@code non-null;} array of bytecode */ 51 private final BytecodeArray code; 52 53 /** {@code non-null;} local variable information */ 54 private final LocalVariableList localVariables; 55 56 /** {@code non-null;} visitor instance to use */ 57 private final SimVisitor visitor; 58 59 /** 60 * Constructs an instance. 61 * 62 * @param machine {@code non-null;} machine to use when simulating 63 * @param method {@code non-null;} method data to use 64 */ 65 public Simulator(Machine machine, ConcreteMethod method) { 66 if (machine == null) { 67 throw new NullPointerException("machine == null"); 68 } 69 70 if (method == null) { 71 throw new NullPointerException("method == null"); 72 } 73 74 this.machine = machine; 75 this.code = method.getCode(); 76 this.localVariables = method.getLocalVariables(); 77 this.visitor = new SimVisitor(); 78 } 79 80 /** 81 * Simulates the effect of executing the given basic block. This modifies 82 * the passed-in frame to represent the end result. 83 * 84 * @param bb {@code non-null;} the basic block 85 * @param frame {@code non-null;} frame to operate on 86 */ 87 public void simulate(ByteBlock bb, Frame frame) { 88 int end = bb.getEnd(); 89 90 visitor.setFrame(frame); 91 92 try { 93 for (int off = bb.getStart(); off < end; /*off*/) { 94 int length = code.parseInstruction(off, visitor); 95 visitor.setPreviousOffset(off); 96 off += length; 97 } 98 } catch (SimException ex) { 99 frame.annotate(ex); 100 throw ex; 101 } 102 } 103 104 /** 105 * Simulates the effect of the instruction at the given offset, by 106 * making appropriate calls on the given frame. 107 * 108 * @param offset {@code >= 0;} offset of the instruction to simulate 109 * @param frame {@code non-null;} frame to operate on 110 * @return the length of the instruction, in bytes 111 */ 112 public int simulate(int offset, Frame frame) { 113 visitor.setFrame(frame); 114 return code.parseInstruction(offset, visitor); 115 } 116 117 /** 118 * Constructs an "illegal top-of-stack" exception, for the stack 119 * manipulation opcodes. 120 */ 121 private static SimException illegalTos() { 122 return new SimException("stack mismatch: illegal " + 123 "top-of-stack for opcode"); 124 } 125 126 /** 127 * Returns the required array type for an array load or store 128 * instruction, based on a given implied type and an observed 129 * actual array type. 130 * 131 * <p>The interesting cases here have to do with object arrays, 132 * <code>byte[]</code>s, <code>boolean[]</code>s, and 133 * known-nulls.</p> 134 * 135 * <p>In the case of arrays of objects, we want to narrow the type 136 * to the actual array present on the stack, as long as what is 137 * present is an object type. Similarly, due to a quirk of the 138 * original bytecode representation, the instructions for dealing 139 * with <code>byte[]</code> and <code>boolean[]</code> are 140 * undifferentiated, and we aim here to return whichever one was 141 * actually present on the stack.</p> 142 * 143 * <p>In the case where there is a known-null on the stack where 144 * an array is expected, we just fall back to the implied type of 145 * the instruction. Due to the quirk described above, this means 146 * that source code that uses <code>boolean[]</code> might get 147 * translated surprisingly -- but correctly -- into an instruction 148 * that specifies a <code>byte[]</code>. It will be correct, 149 * because should the code actually execute, it will necessarily 150 * throw a <code>NullPointerException</code>, and it won't matter 151 * what opcode variant is used to achieve that result.</p> 152 * 153 * @param impliedType {@code non-null;} type implied by the 154 * instruction; is <i>not</i> an array type 155 * @param foundArrayType {@code non-null;} type found on the 156 * stack; is either an array type or a known-null 157 * @return {@code non-null;} the array type that should be 158 * required in this context 159 */ 160 private static Type requiredArrayTypeFor(Type impliedType, 161 Type foundArrayType) { 162 if (foundArrayType == Type.KNOWN_NULL) { 163 return impliedType.getArrayType(); 164 } 165 166 if ((impliedType == Type.OBJECT) 167 && foundArrayType.isArray() 168 && foundArrayType.getComponentType().isReference()) { 169 return foundArrayType; 170 } 171 172 if ((impliedType == Type.BYTE) 173 && (foundArrayType == Type.BOOLEAN_ARRAY)) { 174 /* 175 * Per above, an instruction with implied byte[] is also 176 * allowed to be used on boolean[]. 177 */ 178 return Type.BOOLEAN_ARRAY; 179 } 180 181 return impliedType.getArrayType(); 182 } 183 184 /** 185 * Bytecode visitor used during simulation. 186 */ 187 private class SimVisitor implements BytecodeArray.Visitor { 188 /** 189 * {@code non-null;} machine instance to use (just to avoid excessive 190 * cross-object field access) 191 */ 192 private final Machine machine; 193 194 /** 195 * {@code null-ok;} frame to use; set with each call to 196 * {@link Simulator#simulate} 197 */ 198 private Frame frame; 199 200 /** offset of the previous bytecode */ 201 private int previousOffset; 202 203 /** 204 * Constructs an instance. 205 */ 206 public SimVisitor() { 207 this.machine = Simulator.this.machine; 208 this.frame = null; 209 } 210 211 /** 212 * Sets the frame to act on. 213 * 214 * @param frame {@code non-null;} the frame 215 */ 216 public void setFrame(Frame frame) { 217 if (frame == null) { 218 throw new NullPointerException("frame == null"); 219 } 220 221 this.frame = frame; 222 } 223 224 /** {@inheritDoc} */ 225 public void visitInvalid(int opcode, int offset, int length) { 226 throw new SimException("invalid opcode " + Hex.u1(opcode)); 227 } 228 229 /** {@inheritDoc} */ 230 public void visitNoArgs(int opcode, int offset, int length, 231 Type type) { 232 switch (opcode) { 233 case ByteOps.NOP: { 234 machine.clearArgs(); 235 break; 236 } 237 case ByteOps.INEG: { 238 machine.popArgs(frame, type); 239 break; 240 } 241 case ByteOps.I2L: 242 case ByteOps.I2F: 243 case ByteOps.I2D: 244 case ByteOps.I2B: 245 case ByteOps.I2C: 246 case ByteOps.I2S: { 247 machine.popArgs(frame, Type.INT); 248 break; 249 } 250 case ByteOps.L2I: 251 case ByteOps.L2F: 252 case ByteOps.L2D: { 253 machine.popArgs(frame, Type.LONG); 254 break; 255 } 256 case ByteOps.F2I: 257 case ByteOps.F2L: 258 case ByteOps.F2D: { 259 machine.popArgs(frame, Type.FLOAT); 260 break; 261 } 262 case ByteOps.D2I: 263 case ByteOps.D2L: 264 case ByteOps.D2F: { 265 machine.popArgs(frame, Type.DOUBLE); 266 break; 267 } 268 case ByteOps.RETURN: { 269 machine.clearArgs(); 270 checkReturnType(Type.VOID); 271 break; 272 } 273 case ByteOps.IRETURN: { 274 Type checkType = type; 275 if (type == Type.OBJECT) { 276 /* 277 * For an object return, use the best-known 278 * type of the popped value. 279 */ 280 checkType = frame.getStack().peekType(0); 281 } 282 machine.popArgs(frame, type); 283 checkReturnType(checkType); 284 break; 285 } 286 case ByteOps.POP: { 287 Type peekType = frame.getStack().peekType(0); 288 if (peekType.isCategory2()) { 289 throw illegalTos(); 290 } 291 machine.popArgs(frame, 1); 292 break; 293 } 294 case ByteOps.ARRAYLENGTH: { 295 Type arrayType = frame.getStack().peekType(0); 296 if (!arrayType.isArrayOrKnownNull()) { 297 throw new SimException("type mismatch: expected " + 298 "array type but encountered " + 299 arrayType.toHuman()); 300 } 301 machine.popArgs(frame, Type.OBJECT); 302 break; 303 } 304 case ByteOps.ATHROW: 305 case ByteOps.MONITORENTER: 306 case ByteOps.MONITOREXIT: { 307 machine.popArgs(frame, Type.OBJECT); 308 break; 309 } 310 case ByteOps.IALOAD: { 311 /* 312 * See comment on requiredArrayTypeFor() for explanation 313 * about what's going on here. 314 */ 315 Type foundArrayType = frame.getStack().peekType(1); 316 Type requiredArrayType = 317 requiredArrayTypeFor(type, foundArrayType); 318 319 // Make type agree with the discovered requiredArrayType. 320 type = requiredArrayType.getComponentType(); 321 322 machine.popArgs(frame, requiredArrayType, Type.INT); 323 break; 324 } 325 case ByteOps.IADD: 326 case ByteOps.ISUB: 327 case ByteOps.IMUL: 328 case ByteOps.IDIV: 329 case ByteOps.IREM: 330 case ByteOps.IAND: 331 case ByteOps.IOR: 332 case ByteOps.IXOR: { 333 machine.popArgs(frame, type, type); 334 break; 335 } 336 case ByteOps.ISHL: 337 case ByteOps.ISHR: 338 case ByteOps.IUSHR: { 339 machine.popArgs(frame, type, Type.INT); 340 break; 341 } 342 case ByteOps.LCMP: { 343 machine.popArgs(frame, Type.LONG, Type.LONG); 344 break; 345 } 346 case ByteOps.FCMPL: 347 case ByteOps.FCMPG: { 348 machine.popArgs(frame, Type.FLOAT, Type.FLOAT); 349 break; 350 } 351 case ByteOps.DCMPL: 352 case ByteOps.DCMPG: { 353 machine.popArgs(frame, Type.DOUBLE, Type.DOUBLE); 354 break; 355 } 356 case ByteOps.IASTORE: { 357 /* 358 * See comment on requiredArrayTypeFor() for 359 * explanation about what's going on here. In 360 * addition to that, the category 1 vs. 2 thing 361 * below is to deal with the fact that, if the 362 * element type is category 2, we have to skip 363 * over one extra stack slot to find the array. 364 */ 365 ExecutionStack stack = frame.getStack(); 366 int peekDepth = type.isCategory1() ? 2 : 3; 367 Type foundArrayType = stack.peekType(peekDepth); 368 boolean foundArrayLocal = stack.peekLocal(peekDepth); 369 370 Type requiredArrayType = 371 requiredArrayTypeFor(type, foundArrayType); 372 373 /* 374 * Make type agree with the discovered requiredArrayType 375 * if it has local info. 376 */ 377 if (foundArrayLocal) { 378 type = requiredArrayType.getComponentType(); 379 } 380 381 machine.popArgs(frame, requiredArrayType, Type.INT, type); 382 break; 383 } 384 case ByteOps.POP2: 385 case ByteOps.DUP2: { 386 ExecutionStack stack = frame.getStack(); 387 int pattern; 388 389 if (stack.peekType(0).isCategory2()) { 390 // "form 2" in vmspec-2 391 machine.popArgs(frame, 1); 392 pattern = 0x11; 393 } else if (stack.peekType(1).isCategory1()) { 394 // "form 1" 395 machine.popArgs(frame, 2); 396 pattern = 0x2121; 397 } else { 398 throw illegalTos(); 399 } 400 401 if (opcode == ByteOps.DUP2) { 402 machine.auxIntArg(pattern); 403 } 404 break; 405 } 406 case ByteOps.DUP: { 407 Type peekType = frame.getStack().peekType(0); 408 409 if (peekType.isCategory2()) { 410 throw illegalTos(); 411 } 412 413 machine.popArgs(frame, 1); 414 machine.auxIntArg(0x11); 415 break; 416 } 417 case ByteOps.DUP_X1: { 418 ExecutionStack stack = frame.getStack(); 419 420 if (!(stack.peekType(0).isCategory1() && 421 stack.peekType(1).isCategory1())) { 422 throw illegalTos(); 423 } 424 425 machine.popArgs(frame, 2); 426 machine.auxIntArg(0x212); 427 break; 428 } 429 case ByteOps.DUP_X2: { 430 ExecutionStack stack = frame.getStack(); 431 432 if (stack.peekType(0).isCategory2()) { 433 throw illegalTos(); 434 } 435 436 if (stack.peekType(1).isCategory2()) { 437 // "form 2" in vmspec-2 438 machine.popArgs(frame, 2); 439 machine.auxIntArg(0x212); 440 } else if (stack.peekType(2).isCategory1()) { 441 // "form 1" 442 machine.popArgs(frame, 3); 443 machine.auxIntArg(0x3213); 444 } else { 445 throw illegalTos(); 446 } 447 break; 448 } 449 case ByteOps.DUP2_X1: { 450 ExecutionStack stack = frame.getStack(); 451 452 if (stack.peekType(0).isCategory2()) { 453 // "form 2" in vmspec-2 454 if (stack.peekType(2).isCategory2()) { 455 throw illegalTos(); 456 } 457 machine.popArgs(frame, 2); 458 machine.auxIntArg(0x212); 459 } else { 460 // "form 1" 461 if (stack.peekType(1).isCategory2() || 462 stack.peekType(2).isCategory2()) { 463 throw illegalTos(); 464 } 465 machine.popArgs(frame, 3); 466 machine.auxIntArg(0x32132); 467 } 468 break; 469 } 470 case ByteOps.DUP2_X2: { 471 ExecutionStack stack = frame.getStack(); 472 473 if (stack.peekType(0).isCategory2()) { 474 if (stack.peekType(2).isCategory2()) { 475 // "form 4" in vmspec-2 476 machine.popArgs(frame, 2); 477 machine.auxIntArg(0x212); 478 } else if (stack.peekType(3).isCategory1()) { 479 // "form 2" 480 machine.popArgs(frame, 3); 481 machine.auxIntArg(0x3213); 482 } else { 483 throw illegalTos(); 484 } 485 } else if (stack.peekType(1).isCategory1()) { 486 if (stack.peekType(2).isCategory2()) { 487 // "form 3" 488 machine.popArgs(frame, 3); 489 machine.auxIntArg(0x32132); 490 } else if (stack.peekType(3).isCategory1()) { 491 // "form 1" 492 machine.popArgs(frame, 4); 493 machine.auxIntArg(0x432143); 494 } else { 495 throw illegalTos(); 496 } 497 } else { 498 throw illegalTos(); 499 } 500 break; 501 } 502 case ByteOps.SWAP: { 503 ExecutionStack stack = frame.getStack(); 504 505 if (!(stack.peekType(0).isCategory1() && 506 stack.peekType(1).isCategory1())) { 507 throw illegalTos(); 508 } 509 510 machine.popArgs(frame, 2); 511 machine.auxIntArg(0x12); 512 break; 513 } 514 default: { 515 visitInvalid(opcode, offset, length); 516 return; 517 } 518 } 519 520 machine.auxType(type); 521 machine.run(frame, offset, opcode); 522 } 523 524 /** 525 * Checks whether the prototype is compatible with returning the 526 * given type, and throws if not. 527 * 528 * @param encountered {@code non-null;} the encountered return type 529 */ 530 private void checkReturnType(Type encountered) { 531 Type returnType = machine.getPrototype().getReturnType(); 532 533 /* 534 * Check to see if the prototype's return type is 535 * possibly assignable from the type we encountered. This 536 * takes care of all the salient cases (types are the same, 537 * they're compatible primitive types, etc.). 538 */ 539 if (!Merger.isPossiblyAssignableFrom(returnType, encountered)) { 540 throw new SimException("return type mismatch: prototype " + 541 "indicates " + returnType.toHuman() + 542 ", but encountered type " + encountered.toHuman()); 543 } 544 } 545 546 /** {@inheritDoc} */ 547 public void visitLocal(int opcode, int offset, int length, 548 int idx, Type type, int value) { 549 /* 550 * Note that the "type" parameter is always the simplest 551 * type based on the original opcode, e.g., "int" for 552 * "iload" (per se) and "Object" for "aload". So, when 553 * possible, we replace the type with the one indicated in 554 * the local variable table, though we still need to check 555 * to make sure it's valid for the opcode. 556 * 557 * The reason we use (offset + length) for the localOffset 558 * for a store is because it is only after the store that 559 * the local type becomes valid. On the other hand, the 560 * type associated with a load is valid at the start of 561 * the instruction. 562 */ 563 int localOffset = 564 (opcode == ByteOps.ISTORE) ? (offset + length) : offset; 565 LocalVariableList.Item local = 566 localVariables.pcAndIndexToLocal(localOffset, idx); 567 Type localType; 568 569 if (local != null) { 570 localType = local.getType(); 571 if (localType.getBasicFrameType() != 572 type.getBasicFrameType()) { 573 BaseMachine.throwLocalMismatch(type, localType); 574 return; 575 } 576 } else { 577 localType = type; 578 } 579 580 switch (opcode) { 581 case ByteOps.ILOAD: 582 case ByteOps.RET: { 583 machine.localArg(frame, idx); 584 machine.localInfo(local != null); 585 machine.auxType(type); 586 break; 587 } 588 case ByteOps.ISTORE: { 589 LocalItem item 590 = (local == null) ? null : local.getLocalItem(); 591 machine.popArgs(frame, type); 592 machine.auxType(type); 593 machine.localTarget(idx, localType, item); 594 break; 595 } 596 case ByteOps.IINC: { 597 LocalItem item 598 = (local == null) ? null : local.getLocalItem(); 599 machine.localArg(frame, idx); 600 machine.localTarget(idx, localType, item); 601 machine.auxType(type); 602 machine.auxIntArg(value); 603 machine.auxCstArg(CstInteger.make(value)); 604 break; 605 } 606 default: { 607 visitInvalid(opcode, offset, length); 608 return; 609 } 610 } 611 612 machine.run(frame, offset, opcode); 613 } 614 615 /** {@inheritDoc} */ 616 public void visitConstant(int opcode, int offset, int length, 617 Constant cst, int value) { 618 switch (opcode) { 619 case ByteOps.ANEWARRAY: { 620 machine.popArgs(frame, Type.INT); 621 break; 622 } 623 case ByteOps.PUTSTATIC: { 624 Type fieldType = ((CstFieldRef) cst).getType(); 625 machine.popArgs(frame, fieldType); 626 break; 627 } 628 case ByteOps.GETFIELD: 629 case ByteOps.CHECKCAST: 630 case ByteOps.INSTANCEOF: { 631 machine.popArgs(frame, Type.OBJECT); 632 break; 633 } 634 case ByteOps.PUTFIELD: { 635 Type fieldType = ((CstFieldRef) cst).getType(); 636 machine.popArgs(frame, Type.OBJECT, fieldType); 637 break; 638 } 639 case ByteOps.INVOKEINTERFACE: { 640 /* 641 * Convert the interface method ref into a normal 642 * method ref. 643 */ 644 cst = ((CstInterfaceMethodRef) cst).toMethodRef(); 645 // and fall through... 646 } 647 case ByteOps.INVOKEVIRTUAL: 648 case ByteOps.INVOKESPECIAL: { 649 /* 650 * Get the instance prototype, and use it to direct 651 * the machine. 652 */ 653 Prototype prototype = 654 ((CstMethodRef) cst).getPrototype(false); 655 machine.popArgs(frame, prototype); 656 break; 657 } 658 case ByteOps.INVOKESTATIC: { 659 /* 660 * Get the static prototype, and use it to direct 661 * the machine. 662 */ 663 Prototype prototype = 664 ((CstMethodRef) cst).getPrototype(true); 665 machine.popArgs(frame, prototype); 666 break; 667 } 668 case ByteOps.MULTIANEWARRAY: { 669 /* 670 * The "value" here is the count of dimensions to 671 * create. Make a prototype of that many "int" 672 * types, and tell the machine to pop them. This 673 * isn't the most efficient way in the world to do 674 * this, but then again, multianewarray is pretty 675 * darn rare and so not worth much effort 676 * optimizing for. 677 */ 678 Prototype prototype = 679 Prototype.internInts(Type.VOID, value); 680 machine.popArgs(frame, prototype); 681 break; 682 } 683 default: { 684 machine.clearArgs(); 685 break; 686 } 687 } 688 689 machine.auxIntArg(value); 690 machine.auxCstArg(cst); 691 machine.run(frame, offset, opcode); 692 } 693 694 /** {@inheritDoc} */ 695 public void visitBranch(int opcode, int offset, int length, 696 int target) { 697 switch (opcode) { 698 case ByteOps.IFEQ: 699 case ByteOps.IFNE: 700 case ByteOps.IFLT: 701 case ByteOps.IFGE: 702 case ByteOps.IFGT: 703 case ByteOps.IFLE: { 704 machine.popArgs(frame, Type.INT); 705 break; 706 } 707 case ByteOps.IFNULL: 708 case ByteOps.IFNONNULL: { 709 machine.popArgs(frame, Type.OBJECT); 710 break; 711 } 712 case ByteOps.IF_ICMPEQ: 713 case ByteOps.IF_ICMPNE: 714 case ByteOps.IF_ICMPLT: 715 case ByteOps.IF_ICMPGE: 716 case ByteOps.IF_ICMPGT: 717 case ByteOps.IF_ICMPLE: { 718 machine.popArgs(frame, Type.INT, Type.INT); 719 break; 720 } 721 case ByteOps.IF_ACMPEQ: 722 case ByteOps.IF_ACMPNE: { 723 machine.popArgs(frame, Type.OBJECT, Type.OBJECT); 724 break; 725 } 726 case ByteOps.GOTO: 727 case ByteOps.JSR: 728 case ByteOps.GOTO_W: 729 case ByteOps.JSR_W: { 730 machine.clearArgs(); 731 break; 732 } 733 default: { 734 visitInvalid(opcode, offset, length); 735 return; 736 } 737 } 738 739 machine.auxTargetArg(target); 740 machine.run(frame, offset, opcode); 741 } 742 743 /** {@inheritDoc} */ 744 public void visitSwitch(int opcode, int offset, int length, 745 SwitchList cases, int padding) { 746 machine.popArgs(frame, Type.INT); 747 machine.auxIntArg(padding); 748 machine.auxSwitchArg(cases); 749 machine.run(frame, offset, opcode); 750 } 751 752 /** {@inheritDoc} */ 753 public void visitNewarray(int offset, int length, CstType type, 754 ArrayList<Constant> initValues) { 755 machine.popArgs(frame, Type.INT); 756 machine.auxInitValues(initValues); 757 machine.auxCstArg(type); 758 machine.run(frame, offset, ByteOps.NEWARRAY); 759 } 760 761 /** {@inheritDoc} */ 762 public void setPreviousOffset(int offset) { 763 previousOffset = offset; 764 } 765 766 /** {@inheritDoc} */ 767 public int getPreviousOffset() { 768 return previousOffset; 769 } 770 } 771} 772