001/*** 002 * ASM: a very small and fast Java bytecode manipulation framework 003 * Copyright (c) 2000-2011 INRIA, France Telecom 004 * All rights reserved. 005 * 006 * Redistribution and use in source and binary forms, with or without 007 * modification, are permitted provided that the following conditions 008 * are met: 009 * 1. Redistributions of source code must retain the above copyright 010 * notice, this list of conditions and the following disclaimer. 011 * 2. Redistributions in binary form must reproduce the above copyright 012 * notice, this list of conditions and the following disclaimer in the 013 * documentation and/or other materials provided with the distribution. 014 * 3. Neither the name of the copyright holders nor the names of its 015 * contributors may be used to endorse or promote products derived from 016 * this software without specific prior written permission. 017 * 018 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 019 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 020 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 021 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 022 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 023 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 024 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 025 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 026 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 027 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 028 * THE POSSIBILITY OF SUCH DAMAGE. 029 */ 030package io.ebean.enhance.asm.tree.analysis; 031 032import io.ebean.enhance.asm.Opcodes; 033import io.ebean.enhance.asm.Type; 034import io.ebean.enhance.asm.tree.AbstractInsnNode; 035import io.ebean.enhance.asm.tree.IincInsnNode; 036import io.ebean.enhance.asm.tree.InvokeDynamicInsnNode; 037import io.ebean.enhance.asm.tree.MethodInsnNode; 038import io.ebean.enhance.asm.tree.MultiANewArrayInsnNode; 039import io.ebean.enhance.asm.tree.VarInsnNode; 040 041import java.util.ArrayList; 042import java.util.List; 043 044/** 045 * A symbolic execution stack frame. A stack frame contains a set of local 046 * variable slots, and an operand stack. Warning: long and double values are 047 * represented by <i>two</i> slots in local variables, and by <i>one</i> slot in 048 * the operand stack. 049 * 050 * @param <V> 051 * type of the Value used for the analysis. 052 * 053 * @author Eric Bruneton 054 */ 055public class Frame<V extends Value> { 056 057 /** 058 * The expected return type of the analyzed method, or <tt>null</tt> if the 059 * method returns void. 060 */ 061 private V returnValue; 062 063 /** 064 * The local variables and operand stack of this frame. 065 */ 066 private V[] values; 067 068 /** 069 * The number of local variables of this frame. 070 */ 071 private int locals; 072 073 /** 074 * The number of elements in the operand stack. 075 */ 076 private int top; 077 078 /** 079 * Constructs a new frame with the given size. 080 * 081 * @param nLocals 082 * the maximum number of local variables of the frame. 083 * @param nStack 084 * the maximum stack size of the frame. 085 */ 086 @SuppressWarnings("unchecked") 087 public Frame(final int nLocals, final int nStack) { 088 this.values = (V[]) new Value[nLocals + nStack]; 089 this.locals = nLocals; 090 } 091 092 /** 093 * Constructs a new frame that is identical to the given frame. 094 * 095 * @param src 096 * a frame. 097 */ 098 public Frame(final Frame<? extends V> src) { 099 this(src.locals, src.values.length - src.locals); 100 init(src); 101 } 102 103 /** 104 * Copies the state of the given frame into this frame. 105 * 106 * @param src 107 * a frame. 108 * @return this frame. 109 */ 110 public Frame<V> init(final Frame<? extends V> src) { 111 returnValue = src.returnValue; 112 System.arraycopy(src.values, 0, values, 0, values.length); 113 top = src.top; 114 return this; 115 } 116 117 /** 118 * Sets the expected return type of the analyzed method. 119 * 120 * @param v 121 * the expected return type of the analyzed method, or 122 * <tt>null</tt> if the method returns void. 123 */ 124 public void setReturn(final V v) { 125 returnValue = v; 126 } 127 128 /** 129 * Returns the maximum number of local variables of this frame. 130 * 131 * @return the maximum number of local variables of this frame. 132 */ 133 public int getLocals() { 134 return locals; 135 } 136 137 /** 138 * Returns the maximum stack size of this frame. 139 * 140 * @return the maximum stack size of this frame. 141 */ 142 public int getMaxStackSize() { 143 return values.length - locals; 144 } 145 146 /** 147 * Returns the value of the given local variable. 148 * 149 * @param i 150 * a local variable index. 151 * @return the value of the given local variable. 152 * @throws IndexOutOfBoundsException 153 * if the variable does not exist. 154 */ 155 public V getLocal(final int i) throws IndexOutOfBoundsException { 156 if (i >= locals) { 157 throw new IndexOutOfBoundsException( 158 "Trying to access an inexistant local variable"); 159 } 160 return values[i]; 161 } 162 163 /** 164 * Sets the value of the given local variable. 165 * 166 * @param i 167 * a local variable index. 168 * @param value 169 * the new value of this local variable. 170 * @throws IndexOutOfBoundsException 171 * if the variable does not exist. 172 */ 173 public void setLocal(final int i, final V value) 174 throws IndexOutOfBoundsException { 175 if (i >= locals) { 176 throw new IndexOutOfBoundsException( 177 "Trying to access an inexistant local variable " + i); 178 } 179 values[i] = value; 180 } 181 182 /** 183 * Returns the number of values in the operand stack of this frame. Long and 184 * double values are treated as single values. 185 * 186 * @return the number of values in the operand stack of this frame. 187 */ 188 public int getStackSize() { 189 return top; 190 } 191 192 /** 193 * Returns the value of the given operand stack slot. 194 * 195 * @param i 196 * the index of an operand stack slot. 197 * @return the value of the given operand stack slot. 198 * @throws IndexOutOfBoundsException 199 * if the operand stack slot does not exist. 200 */ 201 public V getStack(final int i) throws IndexOutOfBoundsException { 202 return values[i + locals]; 203 } 204 205 /** 206 * Clears the operand stack of this frame. 207 */ 208 public void clearStack() { 209 top = 0; 210 } 211 212 /** 213 * Pops a value from the operand stack of this frame. 214 * 215 * @return the value that has been popped from the stack. 216 * @throws IndexOutOfBoundsException 217 * if the operand stack is empty. 218 */ 219 public V pop() throws IndexOutOfBoundsException { 220 if (top == 0) { 221 throw new IndexOutOfBoundsException( 222 "Cannot pop operand off an empty stack."); 223 } 224 return values[--top + locals]; 225 } 226 227 /** 228 * Pushes a value into the operand stack of this frame. 229 * 230 * @param value 231 * the value that must be pushed into the stack. 232 * @throws IndexOutOfBoundsException 233 * if the operand stack is full. 234 */ 235 public void push(final V value) throws IndexOutOfBoundsException { 236 if (top + locals >= values.length) { 237 throw new IndexOutOfBoundsException( 238 "Insufficient maximum stack size."); 239 } 240 values[top++ + locals] = value; 241 } 242 243 public void execute(final AbstractInsnNode insn, 244 final Interpreter<V> interpreter) throws AnalyzerException { 245 V value1, value2, value3, value4; 246 List<V> values; 247 int var; 248 249 switch (insn.getOpcode()) { 250 case Opcodes.NOP: 251 break; 252 case Opcodes.ACONST_NULL: 253 case Opcodes.ICONST_M1: 254 case Opcodes.ICONST_0: 255 case Opcodes.ICONST_1: 256 case Opcodes.ICONST_2: 257 case Opcodes.ICONST_3: 258 case Opcodes.ICONST_4: 259 case Opcodes.ICONST_5: 260 case Opcodes.LCONST_0: 261 case Opcodes.LCONST_1: 262 case Opcodes.FCONST_0: 263 case Opcodes.FCONST_1: 264 case Opcodes.FCONST_2: 265 case Opcodes.DCONST_0: 266 case Opcodes.DCONST_1: 267 case Opcodes.BIPUSH: 268 case Opcodes.SIPUSH: 269 case Opcodes.LDC: 270 push(interpreter.newOperation(insn)); 271 break; 272 case Opcodes.ILOAD: 273 case Opcodes.LLOAD: 274 case Opcodes.FLOAD: 275 case Opcodes.DLOAD: 276 case Opcodes.ALOAD: 277 push(interpreter.copyOperation(insn, 278 getLocal(((VarInsnNode) insn).var))); 279 break; 280 case Opcodes.IALOAD: 281 case Opcodes.LALOAD: 282 case Opcodes.FALOAD: 283 case Opcodes.DALOAD: 284 case Opcodes.AALOAD: 285 case Opcodes.BALOAD: 286 case Opcodes.CALOAD: 287 case Opcodes.SALOAD: 288 value2 = pop(); 289 value1 = pop(); 290 push(interpreter.binaryOperation(insn, value1, value2)); 291 break; 292 case Opcodes.ISTORE: 293 case Opcodes.LSTORE: 294 case Opcodes.FSTORE: 295 case Opcodes.DSTORE: 296 case Opcodes.ASTORE: 297 value1 = interpreter.copyOperation(insn, pop()); 298 var = ((VarInsnNode) insn).var; 299 setLocal(var, value1); 300 if (value1.getSize() == 2) { 301 setLocal(var + 1, interpreter.newValue(null)); 302 } 303 if (var > 0) { 304 Value local = getLocal(var - 1); 305 if (local != null && local.getSize() == 2) { 306 setLocal(var - 1, interpreter.newValue(null)); 307 } 308 } 309 break; 310 case Opcodes.IASTORE: 311 case Opcodes.LASTORE: 312 case Opcodes.FASTORE: 313 case Opcodes.DASTORE: 314 case Opcodes.AASTORE: 315 case Opcodes.BASTORE: 316 case Opcodes.CASTORE: 317 case Opcodes.SASTORE: 318 value3 = pop(); 319 value2 = pop(); 320 value1 = pop(); 321 interpreter.ternaryOperation(insn, value1, value2, value3); 322 break; 323 case Opcodes.POP: 324 if (pop().getSize() == 2) { 325 throw new AnalyzerException(insn, "Illegal use of POP"); 326 } 327 break; 328 case Opcodes.POP2: 329 if (pop().getSize() == 1) { 330 if (pop().getSize() != 1) { 331 throw new AnalyzerException(insn, "Illegal use of POP2"); 332 } 333 } 334 break; 335 case Opcodes.DUP: 336 value1 = pop(); 337 if (value1.getSize() != 1) { 338 throw new AnalyzerException(insn, "Illegal use of DUP"); 339 } 340 push(value1); 341 push(interpreter.copyOperation(insn, value1)); 342 break; 343 case Opcodes.DUP_X1: 344 value1 = pop(); 345 value2 = pop(); 346 if (value1.getSize() != 1 || value2.getSize() != 1) { 347 throw new AnalyzerException(insn, "Illegal use of DUP_X1"); 348 } 349 push(interpreter.copyOperation(insn, value1)); 350 push(value2); 351 push(value1); 352 break; 353 case Opcodes.DUP_X2: 354 value1 = pop(); 355 if (value1.getSize() == 1) { 356 value2 = pop(); 357 if (value2.getSize() == 1) { 358 value3 = pop(); 359 if (value3.getSize() == 1) { 360 push(interpreter.copyOperation(insn, value1)); 361 push(value3); 362 push(value2); 363 push(value1); 364 break; 365 } 366 } else { 367 push(interpreter.copyOperation(insn, value1)); 368 push(value2); 369 push(value1); 370 break; 371 } 372 } 373 throw new AnalyzerException(insn, "Illegal use of DUP_X2"); 374 case Opcodes.DUP2: 375 value1 = pop(); 376 if (value1.getSize() == 1) { 377 value2 = pop(); 378 if (value2.getSize() == 1) { 379 push(value2); 380 push(value1); 381 push(interpreter.copyOperation(insn, value2)); 382 push(interpreter.copyOperation(insn, value1)); 383 break; 384 } 385 } else { 386 push(value1); 387 push(interpreter.copyOperation(insn, value1)); 388 break; 389 } 390 throw new AnalyzerException(insn, "Illegal use of DUP2"); 391 case Opcodes.DUP2_X1: 392 value1 = pop(); 393 if (value1.getSize() == 1) { 394 value2 = pop(); 395 if (value2.getSize() == 1) { 396 value3 = pop(); 397 if (value3.getSize() == 1) { 398 push(interpreter.copyOperation(insn, value2)); 399 push(interpreter.copyOperation(insn, value1)); 400 push(value3); 401 push(value2); 402 push(value1); 403 break; 404 } 405 } 406 } else { 407 value2 = pop(); 408 if (value2.getSize() == 1) { 409 push(interpreter.copyOperation(insn, value1)); 410 push(value2); 411 push(value1); 412 break; 413 } 414 } 415 throw new AnalyzerException(insn, "Illegal use of DUP2_X1"); 416 case Opcodes.DUP2_X2: 417 value1 = pop(); 418 if (value1.getSize() == 1) { 419 value2 = pop(); 420 if (value2.getSize() == 1) { 421 value3 = pop(); 422 if (value3.getSize() == 1) { 423 value4 = pop(); 424 if (value4.getSize() == 1) { 425 push(interpreter.copyOperation(insn, value2)); 426 push(interpreter.copyOperation(insn, value1)); 427 push(value4); 428 push(value3); 429 push(value2); 430 push(value1); 431 break; 432 } 433 } else { 434 push(interpreter.copyOperation(insn, value2)); 435 push(interpreter.copyOperation(insn, value1)); 436 push(value3); 437 push(value2); 438 push(value1); 439 break; 440 } 441 } 442 } else { 443 value2 = pop(); 444 if (value2.getSize() == 1) { 445 value3 = pop(); 446 if (value3.getSize() == 1) { 447 push(interpreter.copyOperation(insn, value1)); 448 push(value3); 449 push(value2); 450 push(value1); 451 break; 452 } 453 } else { 454 push(interpreter.copyOperation(insn, value1)); 455 push(value2); 456 push(value1); 457 break; 458 } 459 } 460 throw new AnalyzerException(insn, "Illegal use of DUP2_X2"); 461 case Opcodes.SWAP: 462 value2 = pop(); 463 value1 = pop(); 464 if (value1.getSize() != 1 || value2.getSize() != 1) { 465 throw new AnalyzerException(insn, "Illegal use of SWAP"); 466 } 467 push(interpreter.copyOperation(insn, value2)); 468 push(interpreter.copyOperation(insn, value1)); 469 break; 470 case Opcodes.IADD: 471 case Opcodes.LADD: 472 case Opcodes.FADD: 473 case Opcodes.DADD: 474 case Opcodes.ISUB: 475 case Opcodes.LSUB: 476 case Opcodes.FSUB: 477 case Opcodes.DSUB: 478 case Opcodes.IMUL: 479 case Opcodes.LMUL: 480 case Opcodes.FMUL: 481 case Opcodes.DMUL: 482 case Opcodes.IDIV: 483 case Opcodes.LDIV: 484 case Opcodes.FDIV: 485 case Opcodes.DDIV: 486 case Opcodes.IREM: 487 case Opcodes.LREM: 488 case Opcodes.FREM: 489 case Opcodes.DREM: 490 value2 = pop(); 491 value1 = pop(); 492 push(interpreter.binaryOperation(insn, value1, value2)); 493 break; 494 case Opcodes.INEG: 495 case Opcodes.LNEG: 496 case Opcodes.FNEG: 497 case Opcodes.DNEG: 498 push(interpreter.unaryOperation(insn, pop())); 499 break; 500 case Opcodes.ISHL: 501 case Opcodes.LSHL: 502 case Opcodes.ISHR: 503 case Opcodes.LSHR: 504 case Opcodes.IUSHR: 505 case Opcodes.LUSHR: 506 case Opcodes.IAND: 507 case Opcodes.LAND: 508 case Opcodes.IOR: 509 case Opcodes.LOR: 510 case Opcodes.IXOR: 511 case Opcodes.LXOR: 512 value2 = pop(); 513 value1 = pop(); 514 push(interpreter.binaryOperation(insn, value1, value2)); 515 break; 516 case Opcodes.IINC: 517 var = ((IincInsnNode) insn).var; 518 setLocal(var, interpreter.unaryOperation(insn, getLocal(var))); 519 break; 520 case Opcodes.I2L: 521 case Opcodes.I2F: 522 case Opcodes.I2D: 523 case Opcodes.L2I: 524 case Opcodes.L2F: 525 case Opcodes.L2D: 526 case Opcodes.F2I: 527 case Opcodes.F2L: 528 case Opcodes.F2D: 529 case Opcodes.D2I: 530 case Opcodes.D2L: 531 case Opcodes.D2F: 532 case Opcodes.I2B: 533 case Opcodes.I2C: 534 case Opcodes.I2S: 535 push(interpreter.unaryOperation(insn, pop())); 536 break; 537 case Opcodes.LCMP: 538 case Opcodes.FCMPL: 539 case Opcodes.FCMPG: 540 case Opcodes.DCMPL: 541 case Opcodes.DCMPG: 542 value2 = pop(); 543 value1 = pop(); 544 push(interpreter.binaryOperation(insn, value1, value2)); 545 break; 546 case Opcodes.IFEQ: 547 case Opcodes.IFNE: 548 case Opcodes.IFLT: 549 case Opcodes.IFGE: 550 case Opcodes.IFGT: 551 case Opcodes.IFLE: 552 interpreter.unaryOperation(insn, pop()); 553 break; 554 case Opcodes.IF_ICMPEQ: 555 case Opcodes.IF_ICMPNE: 556 case Opcodes.IF_ICMPLT: 557 case Opcodes.IF_ICMPGE: 558 case Opcodes.IF_ICMPGT: 559 case Opcodes.IF_ICMPLE: 560 case Opcodes.IF_ACMPEQ: 561 case Opcodes.IF_ACMPNE: 562 value2 = pop(); 563 value1 = pop(); 564 interpreter.binaryOperation(insn, value1, value2); 565 break; 566 case Opcodes.GOTO: 567 break; 568 case Opcodes.JSR: 569 push(interpreter.newOperation(insn)); 570 break; 571 case Opcodes.RET: 572 break; 573 case Opcodes.TABLESWITCH: 574 case Opcodes.LOOKUPSWITCH: 575 interpreter.unaryOperation(insn, pop()); 576 break; 577 case Opcodes.IRETURN: 578 case Opcodes.LRETURN: 579 case Opcodes.FRETURN: 580 case Opcodes.DRETURN: 581 case Opcodes.ARETURN: 582 value1 = pop(); 583 interpreter.unaryOperation(insn, value1); 584 interpreter.returnOperation(insn, value1, returnValue); 585 break; 586 case Opcodes.RETURN: 587 if (returnValue != null) { 588 throw new AnalyzerException(insn, "Incompatible return type"); 589 } 590 break; 591 case Opcodes.GETSTATIC: 592 push(interpreter.newOperation(insn)); 593 break; 594 case Opcodes.PUTSTATIC: 595 interpreter.unaryOperation(insn, pop()); 596 break; 597 case Opcodes.GETFIELD: 598 push(interpreter.unaryOperation(insn, pop())); 599 break; 600 case Opcodes.PUTFIELD: 601 value2 = pop(); 602 value1 = pop(); 603 interpreter.binaryOperation(insn, value1, value2); 604 break; 605 case Opcodes.INVOKEVIRTUAL: 606 case Opcodes.INVOKESPECIAL: 607 case Opcodes.INVOKESTATIC: 608 case Opcodes.INVOKEINTERFACE: { 609 values = new ArrayList<V>(); 610 String desc = ((MethodInsnNode) insn).desc; 611 for (int i = Type.getArgumentTypes(desc).length; i > 0; --i) { 612 values.add(0, pop()); 613 } 614 if (insn.getOpcode() != Opcodes.INVOKESTATIC) { 615 values.add(0, pop()); 616 } 617 if (Type.getReturnType(desc) == Type.VOID_TYPE) { 618 interpreter.naryOperation(insn, values); 619 } else { 620 push(interpreter.naryOperation(insn, values)); 621 } 622 break; 623 } 624 case Opcodes.INVOKEDYNAMIC: { 625 values = new ArrayList<V>(); 626 String desc = ((InvokeDynamicInsnNode) insn).desc; 627 for (int i = Type.getArgumentTypes(desc).length; i > 0; --i) { 628 values.add(0, pop()); 629 } 630 if (Type.getReturnType(desc) == Type.VOID_TYPE) { 631 interpreter.naryOperation(insn, values); 632 } else { 633 push(interpreter.naryOperation(insn, values)); 634 } 635 break; 636 } 637 case Opcodes.NEW: 638 push(interpreter.newOperation(insn)); 639 break; 640 case Opcodes.NEWARRAY: 641 case Opcodes.ANEWARRAY: 642 case Opcodes.ARRAYLENGTH: 643 push(interpreter.unaryOperation(insn, pop())); 644 break; 645 case Opcodes.ATHROW: 646 interpreter.unaryOperation(insn, pop()); 647 break; 648 case Opcodes.CHECKCAST: 649 case Opcodes.INSTANCEOF: 650 push(interpreter.unaryOperation(insn, pop())); 651 break; 652 case Opcodes.MONITORENTER: 653 case Opcodes.MONITOREXIT: 654 interpreter.unaryOperation(insn, pop()); 655 break; 656 case Opcodes.MULTIANEWARRAY: 657 values = new ArrayList<V>(); 658 for (int i = ((MultiANewArrayInsnNode) insn).dims; i > 0; --i) { 659 values.add(0, pop()); 660 } 661 push(interpreter.naryOperation(insn, values)); 662 break; 663 case Opcodes.IFNULL: 664 case Opcodes.IFNONNULL: 665 interpreter.unaryOperation(insn, pop()); 666 break; 667 default: 668 throw new RuntimeException("Illegal opcode " + insn.getOpcode()); 669 } 670 } 671 672 /** 673 * Merges this frame with the given frame. 674 * 675 * @param frame 676 * a frame. 677 * @param interpreter 678 * the interpreter used to merge values. 679 * @return <tt>true</tt> if this frame has been changed as a result of the 680 * merge operation, or <tt>false</tt> otherwise. 681 * @throws AnalyzerException 682 * if the frames have incompatible sizes. 683 */ 684 public boolean merge(final Frame<? extends V> frame, 685 final Interpreter<V> interpreter) throws AnalyzerException { 686 if (top != frame.top) { 687 throw new AnalyzerException(null, "Incompatible stack heights"); 688 } 689 boolean changes = false; 690 for (int i = 0; i < locals + top; ++i) { 691 V v = interpreter.merge(values[i], frame.values[i]); 692 if (!v.equals(values[i])) { 693 values[i] = v; 694 changes = true; 695 } 696 } 697 return changes; 698 } 699 700 /** 701 * Merges this frame with the given frame (case of a RET instruction). 702 * 703 * @param frame 704 * a frame 705 * @param access 706 * the local variables that have been accessed by the subroutine 707 * to which the RET instruction corresponds. 708 * @return <tt>true</tt> if this frame has been changed as a result of the 709 * merge operation, or <tt>false</tt> otherwise. 710 */ 711 public boolean merge(final Frame<? extends V> frame, final boolean[] access) { 712 boolean changes = false; 713 for (int i = 0; i < locals; ++i) { 714 if (!access[i] && !values[i].equals(frame.values[i])) { 715 values[i] = frame.values[i]; 716 changes = true; 717 } 718 } 719 return changes; 720 } 721 722 /** 723 * Returns a string representation of this frame. 724 * 725 * @return a string representation of this frame. 726 */ 727 @Override 728 public String toString() { 729 StringBuilder sb = new StringBuilder(); 730 for (int i = 0; i < getLocals(); ++i) { 731 sb.append(getLocal(i)); 732 } 733 sb.append(' '); 734 for (int i = 0; i < getStackSize(); ++i) { 735 sb.append(getStack(i).toString()); 736 } 737 return sb.toString(); 738 } 739}