Frame.java revision 674060f01e9090cd21b3c5656cc3204912ad17a6
1/*** 2 * ASM: a very small and fast Java bytecode manipulation framework 3 * Copyright (c) 2000-2007 INRIA, France Telecom 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. Neither the name of the copyright holders nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 28 * THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30package org.mockito.asm.tree.analysis; 31 32import java.util.ArrayList; 33import java.util.List; 34 35import org.mockito.asm.Opcodes; 36import org.mockito.asm.Type; 37import org.mockito.asm.tree.AbstractInsnNode; 38import org.mockito.asm.tree.IincInsnNode; 39import org.mockito.asm.tree.MethodInsnNode; 40import org.mockito.asm.tree.MultiANewArrayInsnNode; 41import org.mockito.asm.tree.VarInsnNode; 42 43/** 44 * A symbolic execution stack frame. A stack frame contains a set of local 45 * variable slots, and an operand stack. Warning: long and double values are 46 * represented by <i>two</i> slots in local variables, and by <i>one</i> slot 47 * in the operand stack. 48 * 49 * @author Eric Bruneton 50 */ 51public class Frame { 52 53 /** 54 * The local variables and operand stack of this frame. 55 */ 56 private Value[] values; 57 58 /** 59 * The number of local variables of this frame. 60 */ 61 private int locals; 62 63 /** 64 * The number of elements in the operand stack. 65 */ 66 private int top; 67 68 /** 69 * Constructs a new frame with the given size. 70 * 71 * @param nLocals the maximum number of local variables of the frame. 72 * @param nStack the maximum stack size of the frame. 73 */ 74 public Frame(final int nLocals, final int nStack) { 75 this.values = new Value[nLocals + nStack]; 76 this.locals = nLocals; 77 } 78 79 /** 80 * Constructs a new frame that is identical to the given frame. 81 * 82 * @param src a frame. 83 */ 84 public Frame(final Frame src) { 85 this(src.locals, src.values.length - src.locals); 86 init(src); 87 } 88 89 /** 90 * Copies the state of the given frame into this frame. 91 * 92 * @param src a frame. 93 * @return this frame. 94 */ 95 public Frame init(final Frame src) { 96 System.arraycopy(src.values, 0, values, 0, values.length); 97 top = src.top; 98 return this; 99 } 100 101 /** 102 * Returns the maximum number of local variables of this frame. 103 * 104 * @return the maximum number of local variables of this frame. 105 */ 106 public int getLocals() { 107 return locals; 108 } 109 110 /** 111 * Returns the value of the given local variable. 112 * 113 * @param i a local variable index. 114 * @return the value of the given local variable. 115 * @throws IndexOutOfBoundsException if the variable does not exist. 116 */ 117 public Value getLocal(final int i) throws IndexOutOfBoundsException { 118 if (i >= locals) { 119 throw new IndexOutOfBoundsException("Trying to access an inexistant local variable"); 120 } 121 return values[i]; 122 } 123 124 /** 125 * Sets the value of the given local variable. 126 * 127 * @param i a local variable index. 128 * @param value the new value of this local variable. 129 * @throws IndexOutOfBoundsException if the variable does not exist. 130 */ 131 public void setLocal(final int i, final Value value) 132 throws IndexOutOfBoundsException 133 { 134 if (i >= locals) { 135 throw new IndexOutOfBoundsException("Trying to access an inexistant local variable"); 136 } 137 values[i] = value; 138 } 139 140 /** 141 * Returns the number of values in the operand stack of this frame. Long and 142 * double values are treated as single values. 143 * 144 * @return the number of values in the operand stack of this frame. 145 */ 146 public int getStackSize() { 147 return top; 148 } 149 150 /** 151 * Returns the value of the given operand stack slot. 152 * 153 * @param i the index of an operand stack slot. 154 * @return the value of the given operand stack slot. 155 * @throws IndexOutOfBoundsException if the operand stack slot does not 156 * exist. 157 */ 158 public Value getStack(final int i) throws IndexOutOfBoundsException { 159 return values[i + locals]; 160 } 161 162 /** 163 * Clears the operand stack of this frame. 164 */ 165 public void clearStack() { 166 top = 0; 167 } 168 169 /** 170 * Pops a value from the operand stack of this frame. 171 * 172 * @return the value that has been popped from the stack. 173 * @throws IndexOutOfBoundsException if the operand stack is empty. 174 */ 175 public Value pop() throws IndexOutOfBoundsException { 176 if (top == 0) { 177 throw new IndexOutOfBoundsException("Cannot pop operand off an empty stack."); 178 } 179 return values[--top + locals]; 180 } 181 182 /** 183 * Pushes a value into the operand stack of this frame. 184 * 185 * @param value the value that must be pushed into the stack. 186 * @throws IndexOutOfBoundsException if the operand stack is full. 187 */ 188 public void push(final Value value) throws IndexOutOfBoundsException { 189 if (top + locals >= values.length) { 190 throw new IndexOutOfBoundsException("Insufficient maximum stack size."); 191 } 192 values[top++ + locals] = value; 193 } 194 195 public void execute( 196 final AbstractInsnNode insn, 197 final Interpreter interpreter) throws AnalyzerException 198 { 199 Value value1, value2, value3, value4; 200 List values; 201 int var; 202 203 switch (insn.getOpcode()) { 204 case Opcodes.NOP: 205 break; 206 case Opcodes.ACONST_NULL: 207 case Opcodes.ICONST_M1: 208 case Opcodes.ICONST_0: 209 case Opcodes.ICONST_1: 210 case Opcodes.ICONST_2: 211 case Opcodes.ICONST_3: 212 case Opcodes.ICONST_4: 213 case Opcodes.ICONST_5: 214 case Opcodes.LCONST_0: 215 case Opcodes.LCONST_1: 216 case Opcodes.FCONST_0: 217 case Opcodes.FCONST_1: 218 case Opcodes.FCONST_2: 219 case Opcodes.DCONST_0: 220 case Opcodes.DCONST_1: 221 case Opcodes.BIPUSH: 222 case Opcodes.SIPUSH: 223 case Opcodes.LDC: 224 push(interpreter.newOperation(insn)); 225 break; 226 case Opcodes.ILOAD: 227 case Opcodes.LLOAD: 228 case Opcodes.FLOAD: 229 case Opcodes.DLOAD: 230 case Opcodes.ALOAD: 231 push(interpreter.copyOperation(insn, 232 getLocal(((VarInsnNode) insn).var))); 233 break; 234 case Opcodes.IALOAD: 235 case Opcodes.LALOAD: 236 case Opcodes.FALOAD: 237 case Opcodes.DALOAD: 238 case Opcodes.AALOAD: 239 case Opcodes.BALOAD: 240 case Opcodes.CALOAD: 241 case Opcodes.SALOAD: 242 value2 = pop(); 243 value1 = pop(); 244 push(interpreter.binaryOperation(insn, value1, value2)); 245 break; 246 case Opcodes.ISTORE: 247 case Opcodes.LSTORE: 248 case Opcodes.FSTORE: 249 case Opcodes.DSTORE: 250 case Opcodes.ASTORE: 251 value1 = interpreter.copyOperation(insn, pop()); 252 var = ((VarInsnNode) insn).var; 253 setLocal(var, value1); 254 if (value1.getSize() == 2) { 255 setLocal(var + 1, interpreter.newValue(null)); 256 } 257 if (var > 0) { 258 Value local = getLocal(var - 1); 259 if (local != null && local.getSize() == 2) { 260 setLocal(var - 1, interpreter.newValue(null)); 261 } 262 } 263 break; 264 case Opcodes.IASTORE: 265 case Opcodes.LASTORE: 266 case Opcodes.FASTORE: 267 case Opcodes.DASTORE: 268 case Opcodes.AASTORE: 269 case Opcodes.BASTORE: 270 case Opcodes.CASTORE: 271 case Opcodes.SASTORE: 272 value3 = pop(); 273 value2 = pop(); 274 value1 = pop(); 275 interpreter.ternaryOperation(insn, value1, value2, value3); 276 break; 277 case Opcodes.POP: 278 if (pop().getSize() == 2) { 279 throw new AnalyzerException("Illegal use of POP"); 280 } 281 break; 282 case Opcodes.POP2: 283 if (pop().getSize() == 1) { 284 if (pop().getSize() != 1) { 285 throw new AnalyzerException("Illegal use of POP2"); 286 } 287 } 288 break; 289 case Opcodes.DUP: 290 value1 = pop(); 291 if (value1.getSize() != 1) { 292 throw new AnalyzerException("Illegal use of DUP"); 293 } 294 push(interpreter.copyOperation(insn, value1)); 295 push(interpreter.copyOperation(insn, value1)); 296 break; 297 case Opcodes.DUP_X1: 298 value1 = pop(); 299 value2 = pop(); 300 if (value1.getSize() != 1 || value2.getSize() != 1) { 301 throw new AnalyzerException("Illegal use of DUP_X1"); 302 } 303 push(interpreter.copyOperation(insn, value1)); 304 push(interpreter.copyOperation(insn, value2)); 305 push(interpreter.copyOperation(insn, value1)); 306 break; 307 case Opcodes.DUP_X2: 308 value1 = pop(); 309 if (value1.getSize() == 1) { 310 value2 = pop(); 311 if (value2.getSize() == 1) { 312 value3 = pop(); 313 if (value3.getSize() == 1) { 314 push(interpreter.copyOperation(insn, value1)); 315 push(interpreter.copyOperation(insn, value3)); 316 push(interpreter.copyOperation(insn, value2)); 317 push(interpreter.copyOperation(insn, value1)); 318 break; 319 } 320 } else { 321 push(interpreter.copyOperation(insn, value1)); 322 push(interpreter.copyOperation(insn, value2)); 323 push(interpreter.copyOperation(insn, value1)); 324 break; 325 } 326 } 327 throw new AnalyzerException("Illegal use of DUP_X2"); 328 case Opcodes.DUP2: 329 value1 = pop(); 330 if (value1.getSize() == 1) { 331 value2 = pop(); 332 if (value2.getSize() == 1) { 333 push(interpreter.copyOperation(insn, value2)); 334 push(interpreter.copyOperation(insn, value1)); 335 push(interpreter.copyOperation(insn, value2)); 336 push(interpreter.copyOperation(insn, value1)); 337 break; 338 } 339 } else { 340 push(interpreter.copyOperation(insn, value1)); 341 push(interpreter.copyOperation(insn, value1)); 342 break; 343 } 344 throw new AnalyzerException("Illegal use of DUP2"); 345 case Opcodes.DUP2_X1: 346 value1 = pop(); 347 if (value1.getSize() == 1) { 348 value2 = pop(); 349 if (value2.getSize() == 1) { 350 value3 = pop(); 351 if (value3.getSize() == 1) { 352 push(interpreter.copyOperation(insn, value2)); 353 push(interpreter.copyOperation(insn, value1)); 354 push(interpreter.copyOperation(insn, value3)); 355 push(interpreter.copyOperation(insn, value2)); 356 push(interpreter.copyOperation(insn, value1)); 357 break; 358 } 359 } 360 } else { 361 value2 = pop(); 362 if (value2.getSize() == 1) { 363 push(interpreter.copyOperation(insn, value1)); 364 push(interpreter.copyOperation(insn, value2)); 365 push(interpreter.copyOperation(insn, value1)); 366 break; 367 } 368 } 369 throw new AnalyzerException("Illegal use of DUP2_X1"); 370 case Opcodes.DUP2_X2: 371 value1 = pop(); 372 if (value1.getSize() == 1) { 373 value2 = pop(); 374 if (value2.getSize() == 1) { 375 value3 = pop(); 376 if (value3.getSize() == 1) { 377 value4 = pop(); 378 if (value4.getSize() == 1) { 379 push(interpreter.copyOperation(insn, value2)); 380 push(interpreter.copyOperation(insn, value1)); 381 push(interpreter.copyOperation(insn, value4)); 382 push(interpreter.copyOperation(insn, value3)); 383 push(interpreter.copyOperation(insn, value2)); 384 push(interpreter.copyOperation(insn, value1)); 385 break; 386 } 387 } else { 388 push(interpreter.copyOperation(insn, value2)); 389 push(interpreter.copyOperation(insn, value1)); 390 push(interpreter.copyOperation(insn, value3)); 391 push(interpreter.copyOperation(insn, value2)); 392 push(interpreter.copyOperation(insn, value1)); 393 break; 394 } 395 } 396 } else { 397 value2 = pop(); 398 if (value2.getSize() == 1) { 399 value3 = pop(); 400 if (value3.getSize() == 1) { 401 push(interpreter.copyOperation(insn, value1)); 402 push(interpreter.copyOperation(insn, value3)); 403 push(interpreter.copyOperation(insn, value2)); 404 push(interpreter.copyOperation(insn, value1)); 405 break; 406 } 407 } else { 408 push(interpreter.copyOperation(insn, value1)); 409 push(interpreter.copyOperation(insn, value2)); 410 push(interpreter.copyOperation(insn, value1)); 411 break; 412 } 413 } 414 throw new AnalyzerException("Illegal use of DUP2_X2"); 415 case Opcodes.SWAP: 416 value2 = pop(); 417 value1 = pop(); 418 if (value1.getSize() != 1 || value2.getSize() != 1) { 419 throw new AnalyzerException("Illegal use of SWAP"); 420 } 421 push(interpreter.copyOperation(insn, value2)); 422 push(interpreter.copyOperation(insn, value1)); 423 break; 424 case Opcodes.IADD: 425 case Opcodes.LADD: 426 case Opcodes.FADD: 427 case Opcodes.DADD: 428 case Opcodes.ISUB: 429 case Opcodes.LSUB: 430 case Opcodes.FSUB: 431 case Opcodes.DSUB: 432 case Opcodes.IMUL: 433 case Opcodes.LMUL: 434 case Opcodes.FMUL: 435 case Opcodes.DMUL: 436 case Opcodes.IDIV: 437 case Opcodes.LDIV: 438 case Opcodes.FDIV: 439 case Opcodes.DDIV: 440 case Opcodes.IREM: 441 case Opcodes.LREM: 442 case Opcodes.FREM: 443 case Opcodes.DREM: 444 value2 = pop(); 445 value1 = pop(); 446 push(interpreter.binaryOperation(insn, value1, value2)); 447 break; 448 case Opcodes.INEG: 449 case Opcodes.LNEG: 450 case Opcodes.FNEG: 451 case Opcodes.DNEG: 452 push(interpreter.unaryOperation(insn, pop())); 453 break; 454 case Opcodes.ISHL: 455 case Opcodes.LSHL: 456 case Opcodes.ISHR: 457 case Opcodes.LSHR: 458 case Opcodes.IUSHR: 459 case Opcodes.LUSHR: 460 case Opcodes.IAND: 461 case Opcodes.LAND: 462 case Opcodes.IOR: 463 case Opcodes.LOR: 464 case Opcodes.IXOR: 465 case Opcodes.LXOR: 466 value2 = pop(); 467 value1 = pop(); 468 push(interpreter.binaryOperation(insn, value1, value2)); 469 break; 470 case Opcodes.IINC: 471 var = ((IincInsnNode) insn).var; 472 setLocal(var, interpreter.unaryOperation(insn, getLocal(var))); 473 break; 474 case Opcodes.I2L: 475 case Opcodes.I2F: 476 case Opcodes.I2D: 477 case Opcodes.L2I: 478 case Opcodes.L2F: 479 case Opcodes.L2D: 480 case Opcodes.F2I: 481 case Opcodes.F2L: 482 case Opcodes.F2D: 483 case Opcodes.D2I: 484 case Opcodes.D2L: 485 case Opcodes.D2F: 486 case Opcodes.I2B: 487 case Opcodes.I2C: 488 case Opcodes.I2S: 489 push(interpreter.unaryOperation(insn, pop())); 490 break; 491 case Opcodes.LCMP: 492 case Opcodes.FCMPL: 493 case Opcodes.FCMPG: 494 case Opcodes.DCMPL: 495 case Opcodes.DCMPG: 496 value2 = pop(); 497 value1 = pop(); 498 push(interpreter.binaryOperation(insn, value1, value2)); 499 break; 500 case Opcodes.IFEQ: 501 case Opcodes.IFNE: 502 case Opcodes.IFLT: 503 case Opcodes.IFGE: 504 case Opcodes.IFGT: 505 case Opcodes.IFLE: 506 interpreter.unaryOperation(insn, pop()); 507 break; 508 case Opcodes.IF_ICMPEQ: 509 case Opcodes.IF_ICMPNE: 510 case Opcodes.IF_ICMPLT: 511 case Opcodes.IF_ICMPGE: 512 case Opcodes.IF_ICMPGT: 513 case Opcodes.IF_ICMPLE: 514 case Opcodes.IF_ACMPEQ: 515 case Opcodes.IF_ACMPNE: 516 value2 = pop(); 517 value1 = pop(); 518 interpreter.binaryOperation(insn, value1, value2); 519 break; 520 case Opcodes.GOTO: 521 break; 522 case Opcodes.JSR: 523 push(interpreter.newOperation(insn)); 524 break; 525 case Opcodes.RET: 526 break; 527 case Opcodes.TABLESWITCH: 528 case Opcodes.LOOKUPSWITCH: 529 case Opcodes.IRETURN: 530 case Opcodes.LRETURN: 531 case Opcodes.FRETURN: 532 case Opcodes.DRETURN: 533 case Opcodes.ARETURN: 534 interpreter.unaryOperation(insn, pop()); 535 break; 536 case Opcodes.RETURN: 537 break; 538 case Opcodes.GETSTATIC: 539 push(interpreter.newOperation(insn)); 540 break; 541 case Opcodes.PUTSTATIC: 542 interpreter.unaryOperation(insn, pop()); 543 break; 544 case Opcodes.GETFIELD: 545 push(interpreter.unaryOperation(insn, pop())); 546 break; 547 case Opcodes.PUTFIELD: 548 value2 = pop(); 549 value1 = pop(); 550 interpreter.binaryOperation(insn, value1, value2); 551 break; 552 case Opcodes.INVOKEVIRTUAL: 553 case Opcodes.INVOKESPECIAL: 554 case Opcodes.INVOKESTATIC: 555 case Opcodes.INVOKEINTERFACE: 556 values = new ArrayList(); 557 String desc = ((MethodInsnNode) insn).desc; 558 for (int i = Type.getArgumentTypes(desc).length; i > 0; --i) { 559 values.add(0, pop()); 560 } 561 if (insn.getOpcode() != Opcodes.INVOKESTATIC) { 562 values.add(0, pop()); 563 } 564 if (Type.getReturnType(desc) == Type.VOID_TYPE) { 565 interpreter.naryOperation(insn, values); 566 } else { 567 push(interpreter.naryOperation(insn, values)); 568 } 569 break; 570 case Opcodes.NEW: 571 push(interpreter.newOperation(insn)); 572 break; 573 case Opcodes.NEWARRAY: 574 case Opcodes.ANEWARRAY: 575 case Opcodes.ARRAYLENGTH: 576 push(interpreter.unaryOperation(insn, pop())); 577 break; 578 case Opcodes.ATHROW: 579 interpreter.unaryOperation(insn, pop()); 580 break; 581 case Opcodes.CHECKCAST: 582 case Opcodes.INSTANCEOF: 583 push(interpreter.unaryOperation(insn, pop())); 584 break; 585 case Opcodes.MONITORENTER: 586 case Opcodes.MONITOREXIT: 587 interpreter.unaryOperation(insn, pop()); 588 break; 589 case Opcodes.MULTIANEWARRAY: 590 values = new ArrayList(); 591 for (int i = ((MultiANewArrayInsnNode) insn).dims; i > 0; --i) { 592 values.add(0, pop()); 593 } 594 push(interpreter.naryOperation(insn, values)); 595 break; 596 case Opcodes.IFNULL: 597 case Opcodes.IFNONNULL: 598 interpreter.unaryOperation(insn, pop()); 599 break; 600 default: 601 throw new RuntimeException("Illegal opcode"); 602 } 603 } 604 605 /** 606 * Merges this frame with the given frame. 607 * 608 * @param frame a frame. 609 * @param interpreter the interpreter used to merge values. 610 * @return <tt>true</tt> if this frame has been changed as a result of the 611 * merge operation, or <tt>false</tt> otherwise. 612 * @throws AnalyzerException if the frames have incompatible sizes. 613 */ 614 public boolean merge(final Frame frame, final Interpreter interpreter) 615 throws AnalyzerException 616 { 617 if (top != frame.top) { 618 throw new AnalyzerException("Incompatible stack heights"); 619 } 620 boolean changes = false; 621 for (int i = 0; i < locals + top; ++i) { 622 Value v = interpreter.merge(values[i], frame.values[i]); 623 if (v != values[i]) { 624 values[i] = v; 625 changes |= true; 626 } 627 } 628 return changes; 629 } 630 631 /** 632 * Merges this frame with the given frame (case of a RET instruction). 633 * 634 * @param frame a frame 635 * @param access the local variables that have been accessed by the 636 * subroutine to which the RET instruction corresponds. 637 * @return <tt>true</tt> if this frame has been changed as a result of the 638 * merge operation, or <tt>false</tt> otherwise. 639 */ 640 public boolean merge(final Frame frame, final boolean[] access) { 641 boolean changes = false; 642 for (int i = 0; i < locals; ++i) { 643 if (!access[i] && !values[i].equals(frame.values[i])) { 644 values[i] = frame.values[i]; 645 changes = true; 646 } 647 } 648 return changes; 649 } 650 651 /** 652 * Returns a string representation of this frame. 653 * 654 * @return a string representation of this frame. 655 */ 656 public String toString() { 657 StringBuffer b = new StringBuffer(); 658 for (int i = 0; i < getLocals(); ++i) { 659 b.append(getLocal(i)); 660 } 661 b.append(' '); 662 for (int i = 0; i < getStackSize(); ++i) { 663 b.append(getStack(i).toString()); 664 } 665 return b.toString(); 666 } 667} 668