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; 31 32/** 33 * Information about the input and output stack map frames of a basic block. 34 * 35 * @author Eric Bruneton 36 */ 37final class Frame { 38 39 /* 40 * Frames are computed in a two steps process: during the visit of each 41 * instruction, the state of the frame at the end of current basic block is 42 * updated by simulating the action of the instruction on the previous state 43 * of this so called "output frame". In visitMaxs, a fix point algorithm is 44 * used to compute the "input frame" of each basic block, i.e. the stack map 45 * frame at the begining of the basic block, starting from the input frame 46 * of the first basic block (which is computed from the method descriptor), 47 * and by using the previously computed output frames to compute the input 48 * state of the other blocks. 49 * 50 * All output and input frames are stored as arrays of integers. Reference 51 * and array types are represented by an index into a type table (which is 52 * not the same as the constant pool of the class, in order to avoid adding 53 * unnecessary constants in the pool - not all computed frames will end up 54 * being stored in the stack map table). This allows very fast type 55 * comparisons. 56 * 57 * Output stack map frames are computed relatively to the input frame of the 58 * basic block, which is not yet known when output frames are computed. It 59 * is therefore necessary to be able to represent abstract types such as 60 * "the type at position x in the input frame locals" or "the type at 61 * position x from the top of the input frame stack" or even "the type at 62 * position x in the input frame, with y more (or less) array dimensions". 63 * This explains the rather complicated type format used in output frames. 64 * 65 * This format is the following: DIM KIND VALUE (4, 4 and 24 bits). DIM is a 66 * signed number of array dimensions (from -8 to 7). KIND is either BASE, 67 * LOCAL or STACK. BASE is used for types that are not relative to the input 68 * frame. LOCAL is used for types that are relative to the input local 69 * variable types. STACK is used for types that are relative to the input 70 * stack types. VALUE depends on KIND. For LOCAL types, it is an index in 71 * the input local variable types. For STACK types, it is a position 72 * relatively to the top of input frame stack. For BASE types, it is either 73 * one of the constants defined in FrameVisitor, or for OBJECT and 74 * UNINITIALIZED types, a tag and an index in the type table. 75 * 76 * Output frames can contain types of any kind and with a positive or 77 * negative dimension (and even unassigned types, represented by 0 - which 78 * does not correspond to any valid type value). Input frames can only 79 * contain BASE types of positive or null dimension. In all cases the type 80 * table contains only internal type names (array type descriptors are 81 * forbidden - dimensions must be represented through the DIM field). 82 * 83 * The LONG and DOUBLE types are always represented by using two slots (LONG + 84 * TOP or DOUBLE + TOP), for local variable types as well as in the operand 85 * stack. This is necessary to be able to simulate DUPx_y instructions, 86 * whose effect would be dependent on the actual type values if types were 87 * always represented by a single slot in the stack (and this is not 88 * possible, since actual type values are not always known - cf LOCAL and 89 * STACK type kinds). 90 */ 91 92 /** 93 * Mask to get the dimension of a frame type. This dimension is a signed 94 * integer between -8 and 7. 95 */ 96 static final int DIM = 0xF0000000; 97 98 /** 99 * Constant to be added to a type to get a type with one more dimension. 100 */ 101 static final int ARRAY_OF = 0x10000000; 102 103 /** 104 * Constant to be added to a type to get a type with one less dimension. 105 */ 106 static final int ELEMENT_OF = 0xF0000000; 107 108 /** 109 * Mask to get the kind of a frame type. 110 * 111 * @see #BASE 112 * @see #LOCAL 113 * @see #STACK 114 */ 115 static final int KIND = 0xF000000; 116 117 /** 118 * Mask to get the value of a frame type. 119 */ 120 static final int VALUE = 0xFFFFFF; 121 122 /** 123 * Mask to get the kind of base types. 124 */ 125 static final int BASE_KIND = 0xFF00000; 126 127 /** 128 * Mask to get the value of base types. 129 */ 130 static final int BASE_VALUE = 0xFFFFF; 131 132 /** 133 * Kind of the types that are not relative to an input stack map frame. 134 */ 135 static final int BASE = 0x1000000; 136 137 /** 138 * Base kind of the base reference types. The BASE_VALUE of such types is an 139 * index into the type table. 140 */ 141 static final int OBJECT = BASE | 0x700000; 142 143 /** 144 * Base kind of the uninitialized base types. The BASE_VALUE of such types 145 * in an index into the type table (the Item at that index contains both an 146 * instruction offset and an internal class name). 147 */ 148 static final int UNINITIALIZED = BASE | 0x800000; 149 150 /** 151 * Kind of the types that are relative to the local variable types of an 152 * input stack map frame. The value of such types is a local variable index. 153 */ 154 private static final int LOCAL = 0x2000000; 155 156 /** 157 * Kind of the the types that are relative to the stack of an input stack 158 * map frame. The value of such types is a position relatively to the top of 159 * this stack. 160 */ 161 private static final int STACK = 0x3000000; 162 163 /** 164 * The TOP type. This is a BASE type. 165 */ 166 static final int TOP = BASE | 0; 167 168 /** 169 * The BOOLEAN type. This is a BASE type mainly used for array types. 170 */ 171 static final int BOOLEAN = BASE | 9; 172 173 /** 174 * The BYTE type. This is a BASE type mainly used for array types. 175 */ 176 static final int BYTE = BASE | 10; 177 178 /** 179 * The CHAR type. This is a BASE type mainly used for array types. 180 */ 181 static final int CHAR = BASE | 11; 182 183 /** 184 * The SHORT type. This is a BASE type mainly used for array types. 185 */ 186 static final int SHORT = BASE | 12; 187 188 /** 189 * The INTEGER type. This is a BASE type. 190 */ 191 static final int INTEGER = BASE | 1; 192 193 /** 194 * The FLOAT type. This is a BASE type. 195 */ 196 static final int FLOAT = BASE | 2; 197 198 /** 199 * The DOUBLE type. This is a BASE type. 200 */ 201 static final int DOUBLE = BASE | 3; 202 203 /** 204 * The LONG type. This is a BASE type. 205 */ 206 static final int LONG = BASE | 4; 207 208 /** 209 * The NULL type. This is a BASE type. 210 */ 211 static final int NULL = BASE | 5; 212 213 /** 214 * The UNINITIALIZED_THIS type. This is a BASE type. 215 */ 216 static final int UNINITIALIZED_THIS = BASE | 6; 217 218 /** 219 * The stack size variation corresponding to each JVM instruction. This 220 * stack variation is equal to the size of the values produced by an 221 * instruction, minus the size of the values consumed by this instruction. 222 */ 223 static final int[] SIZE; 224 225 /** 226 * Computes the stack size variation corresponding to each JVM instruction. 227 */ 228 static { 229 int i; 230 int[] b = new int[202]; 231 String s = "EFFFFFFFFGGFFFGGFFFEEFGFGFEEEEEEEEEEEEEEEEEEEEDEDEDDDDD" 232 + "CDCDEEEEEEEEEEEEEEEEEEEEBABABBBBDCFFFGGGEDCDCDCDCDCDCDCDCD" 233 + "CDCEEEEDDDDDDDCDCDCEFEFDDEEFFDEDEEEBDDBBDDDDDDCCCCCCCCEFED" 234 + "DDCDCDEEEEEEEEEEFEEEEEEDDEEDDEE"; 235 for (i = 0; i < b.length; ++i) { 236 b[i] = s.charAt(i) - 'E'; 237 } 238 SIZE = b; 239 240 // code to generate the above string 241 // 242 // int NA = 0; // not applicable (unused opcode or variable size opcode) 243 // 244 // b = new int[] { 245 // 0, //NOP, // visitInsn 246 // 1, //ACONST_NULL, // - 247 // 1, //ICONST_M1, // - 248 // 1, //ICONST_0, // - 249 // 1, //ICONST_1, // - 250 // 1, //ICONST_2, // - 251 // 1, //ICONST_3, // - 252 // 1, //ICONST_4, // - 253 // 1, //ICONST_5, // - 254 // 2, //LCONST_0, // - 255 // 2, //LCONST_1, // - 256 // 1, //FCONST_0, // - 257 // 1, //FCONST_1, // - 258 // 1, //FCONST_2, // - 259 // 2, //DCONST_0, // - 260 // 2, //DCONST_1, // - 261 // 1, //BIPUSH, // visitIntInsn 262 // 1, //SIPUSH, // - 263 // 1, //LDC, // visitLdcInsn 264 // NA, //LDC_W, // - 265 // NA, //LDC2_W, // - 266 // 1, //ILOAD, // visitVarInsn 267 // 2, //LLOAD, // - 268 // 1, //FLOAD, // - 269 // 2, //DLOAD, // - 270 // 1, //ALOAD, // - 271 // NA, //ILOAD_0, // - 272 // NA, //ILOAD_1, // - 273 // NA, //ILOAD_2, // - 274 // NA, //ILOAD_3, // - 275 // NA, //LLOAD_0, // - 276 // NA, //LLOAD_1, // - 277 // NA, //LLOAD_2, // - 278 // NA, //LLOAD_3, // - 279 // NA, //FLOAD_0, // - 280 // NA, //FLOAD_1, // - 281 // NA, //FLOAD_2, // - 282 // NA, //FLOAD_3, // - 283 // NA, //DLOAD_0, // - 284 // NA, //DLOAD_1, // - 285 // NA, //DLOAD_2, // - 286 // NA, //DLOAD_3, // - 287 // NA, //ALOAD_0, // - 288 // NA, //ALOAD_1, // - 289 // NA, //ALOAD_2, // - 290 // NA, //ALOAD_3, // - 291 // -1, //IALOAD, // visitInsn 292 // 0, //LALOAD, // - 293 // -1, //FALOAD, // - 294 // 0, //DALOAD, // - 295 // -1, //AALOAD, // - 296 // -1, //BALOAD, // - 297 // -1, //CALOAD, // - 298 // -1, //SALOAD, // - 299 // -1, //ISTORE, // visitVarInsn 300 // -2, //LSTORE, // - 301 // -1, //FSTORE, // - 302 // -2, //DSTORE, // - 303 // -1, //ASTORE, // - 304 // NA, //ISTORE_0, // - 305 // NA, //ISTORE_1, // - 306 // NA, //ISTORE_2, // - 307 // NA, //ISTORE_3, // - 308 // NA, //LSTORE_0, // - 309 // NA, //LSTORE_1, // - 310 // NA, //LSTORE_2, // - 311 // NA, //LSTORE_3, // - 312 // NA, //FSTORE_0, // - 313 // NA, //FSTORE_1, // - 314 // NA, //FSTORE_2, // - 315 // NA, //FSTORE_3, // - 316 // NA, //DSTORE_0, // - 317 // NA, //DSTORE_1, // - 318 // NA, //DSTORE_2, // - 319 // NA, //DSTORE_3, // - 320 // NA, //ASTORE_0, // - 321 // NA, //ASTORE_1, // - 322 // NA, //ASTORE_2, // - 323 // NA, //ASTORE_3, // - 324 // -3, //IASTORE, // visitInsn 325 // -4, //LASTORE, // - 326 // -3, //FASTORE, // - 327 // -4, //DASTORE, // - 328 // -3, //AASTORE, // - 329 // -3, //BASTORE, // - 330 // -3, //CASTORE, // - 331 // -3, //SASTORE, // - 332 // -1, //POP, // - 333 // -2, //POP2, // - 334 // 1, //DUP, // - 335 // 1, //DUP_X1, // - 336 // 1, //DUP_X2, // - 337 // 2, //DUP2, // - 338 // 2, //DUP2_X1, // - 339 // 2, //DUP2_X2, // - 340 // 0, //SWAP, // - 341 // -1, //IADD, // - 342 // -2, //LADD, // - 343 // -1, //FADD, // - 344 // -2, //DADD, // - 345 // -1, //ISUB, // - 346 // -2, //LSUB, // - 347 // -1, //FSUB, // - 348 // -2, //DSUB, // - 349 // -1, //IMUL, // - 350 // -2, //LMUL, // - 351 // -1, //FMUL, // - 352 // -2, //DMUL, // - 353 // -1, //IDIV, // - 354 // -2, //LDIV, // - 355 // -1, //FDIV, // - 356 // -2, //DDIV, // - 357 // -1, //IREM, // - 358 // -2, //LREM, // - 359 // -1, //FREM, // - 360 // -2, //DREM, // - 361 // 0, //INEG, // - 362 // 0, //LNEG, // - 363 // 0, //FNEG, // - 364 // 0, //DNEG, // - 365 // -1, //ISHL, // - 366 // -1, //LSHL, // - 367 // -1, //ISHR, // - 368 // -1, //LSHR, // - 369 // -1, //IUSHR, // - 370 // -1, //LUSHR, // - 371 // -1, //IAND, // - 372 // -2, //LAND, // - 373 // -1, //IOR, // - 374 // -2, //LOR, // - 375 // -1, //IXOR, // - 376 // -2, //LXOR, // - 377 // 0, //IINC, // visitIincInsn 378 // 1, //I2L, // visitInsn 379 // 0, //I2F, // - 380 // 1, //I2D, // - 381 // -1, //L2I, // - 382 // -1, //L2F, // - 383 // 0, //L2D, // - 384 // 0, //F2I, // - 385 // 1, //F2L, // - 386 // 1, //F2D, // - 387 // -1, //D2I, // - 388 // 0, //D2L, // - 389 // -1, //D2F, // - 390 // 0, //I2B, // - 391 // 0, //I2C, // - 392 // 0, //I2S, // - 393 // -3, //LCMP, // - 394 // -1, //FCMPL, // - 395 // -1, //FCMPG, // - 396 // -3, //DCMPL, // - 397 // -3, //DCMPG, // - 398 // -1, //IFEQ, // visitJumpInsn 399 // -1, //IFNE, // - 400 // -1, //IFLT, // - 401 // -1, //IFGE, // - 402 // -1, //IFGT, // - 403 // -1, //IFLE, // - 404 // -2, //IF_ICMPEQ, // - 405 // -2, //IF_ICMPNE, // - 406 // -2, //IF_ICMPLT, // - 407 // -2, //IF_ICMPGE, // - 408 // -2, //IF_ICMPGT, // - 409 // -2, //IF_ICMPLE, // - 410 // -2, //IF_ACMPEQ, // - 411 // -2, //IF_ACMPNE, // - 412 // 0, //GOTO, // - 413 // 1, //JSR, // - 414 // 0, //RET, // visitVarInsn 415 // -1, //TABLESWITCH, // visiTableSwitchInsn 416 // -1, //LOOKUPSWITCH, // visitLookupSwitch 417 // -1, //IRETURN, // visitInsn 418 // -2, //LRETURN, // - 419 // -1, //FRETURN, // - 420 // -2, //DRETURN, // - 421 // -1, //ARETURN, // - 422 // 0, //RETURN, // - 423 // NA, //GETSTATIC, // visitFieldInsn 424 // NA, //PUTSTATIC, // - 425 // NA, //GETFIELD, // - 426 // NA, //PUTFIELD, // - 427 // NA, //INVOKEVIRTUAL, // visitMethodInsn 428 // NA, //INVOKESPECIAL, // - 429 // NA, //INVOKESTATIC, // - 430 // NA, //INVOKEINTERFACE, // - 431 // NA, //UNUSED, // NOT VISITED 432 // 1, //NEW, // visitTypeInsn 433 // 0, //NEWARRAY, // visitIntInsn 434 // 0, //ANEWARRAY, // visitTypeInsn 435 // 0, //ARRAYLENGTH, // visitInsn 436 // NA, //ATHROW, // - 437 // 0, //CHECKCAST, // visitTypeInsn 438 // 0, //INSTANCEOF, // - 439 // -1, //MONITORENTER, // visitInsn 440 // -1, //MONITOREXIT, // - 441 // NA, //WIDE, // NOT VISITED 442 // NA, //MULTIANEWARRAY, // visitMultiANewArrayInsn 443 // -1, //IFNULL, // visitJumpInsn 444 // -1, //IFNONNULL, // - 445 // NA, //GOTO_W, // - 446 // NA, //JSR_W, // - 447 // }; 448 // for (i = 0; i < b.length; ++i) { 449 // System.err.print((char)('E' + b[i])); 450 // } 451 // System.err.println(); 452 } 453 454 /** 455 * The label (i.e. basic block) to which these input and output stack map 456 * frames correspond. 457 */ 458 Label owner; 459 460 /** 461 * The input stack map frame locals. 462 */ 463 int[] inputLocals; 464 465 /** 466 * The input stack map frame stack. 467 */ 468 int[] inputStack; 469 470 /** 471 * The output stack map frame locals. 472 */ 473 private int[] outputLocals; 474 475 /** 476 * The output stack map frame stack. 477 */ 478 private int[] outputStack; 479 480 /** 481 * Relative size of the output stack. The exact semantics of this field 482 * depends on the algorithm that is used. 483 * 484 * When only the maximum stack size is computed, this field is the size of 485 * the output stack relatively to the top of the input stack. 486 * 487 * When the stack map frames are completely computed, this field is the 488 * actual number of types in {@link #outputStack}. 489 */ 490 private int outputStackTop; 491 492 /** 493 * Number of types that are initialized in the basic block. 494 * 495 * @see #initializations 496 */ 497 private int initializationCount; 498 499 /** 500 * The types that are initialized in the basic block. A constructor 501 * invocation on an UNINITIALIZED or UNINITIALIZED_THIS type must replace 502 * <i>every occurence</i> of this type in the local variables and in the 503 * operand stack. This cannot be done during the first phase of the 504 * algorithm since, during this phase, the local variables and the operand 505 * stack are not completely computed. It is therefore necessary to store the 506 * types on which constructors are invoked in the basic block, in order to 507 * do this replacement during the second phase of the algorithm, where the 508 * frames are fully computed. Note that this array can contain types that 509 * are relative to input locals or to the input stack (see below for the 510 * description of the algorithm). 511 */ 512 private int[] initializations; 513 514 /** 515 * Returns the output frame local variable type at the given index. 516 * 517 * @param local the index of the local that must be returned. 518 * @return the output frame local variable type at the given index. 519 */ 520 private int get(final int local) { 521 if (outputLocals == null || local >= outputLocals.length) { 522 // this local has never been assigned in this basic block, 523 // so it is still equal to its value in the input frame 524 return LOCAL | local; 525 } else { 526 int type = outputLocals[local]; 527 if (type == 0) { 528 // this local has never been assigned in this basic block, 529 // so it is still equal to its value in the input frame 530 type = outputLocals[local] = LOCAL | local; 531 } 532 return type; 533 } 534 } 535 536 /** 537 * Sets the output frame local variable type at the given index. 538 * 539 * @param local the index of the local that must be set. 540 * @param type the value of the local that must be set. 541 */ 542 private void set(final int local, final int type) { 543 // creates and/or resizes the output local variables array if necessary 544 if (outputLocals == null) { 545 outputLocals = new int[10]; 546 } 547 int n = outputLocals.length; 548 if (local >= n) { 549 int[] t = new int[Math.max(local + 1, 2 * n)]; 550 System.arraycopy(outputLocals, 0, t, 0, n); 551 outputLocals = t; 552 } 553 // sets the local variable 554 outputLocals[local] = type; 555 } 556 557 /** 558 * Pushes a new type onto the output frame stack. 559 * 560 * @param type the type that must be pushed. 561 */ 562 private void push(final int type) { 563 // creates and/or resizes the output stack array if necessary 564 if (outputStack == null) { 565 outputStack = new int[10]; 566 } 567 int n = outputStack.length; 568 if (outputStackTop >= n) { 569 int[] t = new int[Math.max(outputStackTop + 1, 2 * n)]; 570 System.arraycopy(outputStack, 0, t, 0, n); 571 outputStack = t; 572 } 573 // pushes the type on the output stack 574 outputStack[outputStackTop++] = type; 575 // updates the maximun height reached by the output stack, if needed 576 int top = owner.inputStackTop + outputStackTop; 577 if (top > owner.outputStackMax) { 578 owner.outputStackMax = top; 579 } 580 } 581 582 /** 583 * Pushes a new type onto the output frame stack. 584 * 585 * @param cw the ClassWriter to which this label belongs. 586 * @param desc the descriptor of the type to be pushed. Can also be a method 587 * descriptor (in this case this method pushes its return type onto 588 * the output frame stack). 589 */ 590 private void push(final ClassWriter cw, final String desc) { 591 int type = type(cw, desc); 592 if (type != 0) { 593 push(type); 594 if (type == LONG || type == DOUBLE) { 595 push(TOP); 596 } 597 } 598 } 599 600 /** 601 * Returns the int encoding of the given type. 602 * 603 * @param cw the ClassWriter to which this label belongs. 604 * @param desc a type descriptor. 605 * @return the int encoding of the given type. 606 */ 607 private static int type(final ClassWriter cw, final String desc) { 608 String t; 609 int index = desc.charAt(0) == '(' ? desc.indexOf(')') + 1 : 0; 610 switch (desc.charAt(index)) { 611 case 'V': 612 return 0; 613 case 'Z': 614 case 'C': 615 case 'B': 616 case 'S': 617 case 'I': 618 return INTEGER; 619 case 'F': 620 return FLOAT; 621 case 'J': 622 return LONG; 623 case 'D': 624 return DOUBLE; 625 case 'L': 626 // stores the internal name, not the descriptor! 627 t = desc.substring(index + 1, desc.length() - 1); 628 return OBJECT | cw.addType(t); 629 // case '[': 630 default: 631 // extracts the dimensions and the element type 632 int data; 633 int dims = index + 1; 634 while (desc.charAt(dims) == '[') { 635 ++dims; 636 } 637 switch (desc.charAt(dims)) { 638 case 'Z': 639 data = BOOLEAN; 640 break; 641 case 'C': 642 data = CHAR; 643 break; 644 case 'B': 645 data = BYTE; 646 break; 647 case 'S': 648 data = SHORT; 649 break; 650 case 'I': 651 data = INTEGER; 652 break; 653 case 'F': 654 data = FLOAT; 655 break; 656 case 'J': 657 data = LONG; 658 break; 659 case 'D': 660 data = DOUBLE; 661 break; 662 // case 'L': 663 default: 664 // stores the internal name, not the descriptor 665 t = desc.substring(dims + 1, desc.length() - 1); 666 data = OBJECT | cw.addType(t); 667 } 668 return (dims - index) << 28 | data; 669 } 670 } 671 672 /** 673 * Pops a type from the output frame stack and returns its value. 674 * 675 * @return the type that has been popped from the output frame stack. 676 */ 677 private int pop() { 678 if (outputStackTop > 0) { 679 return outputStack[--outputStackTop]; 680 } else { 681 // if the output frame stack is empty, pops from the input stack 682 return STACK | -(--owner.inputStackTop); 683 } 684 } 685 686 /** 687 * Pops the given number of types from the output frame stack. 688 * 689 * @param elements the number of types that must be popped. 690 */ 691 private void pop(final int elements) { 692 if (outputStackTop >= elements) { 693 outputStackTop -= elements; 694 } else { 695 // if the number of elements to be popped is greater than the number 696 // of elements in the output stack, clear it, and pops the remaining 697 // elements from the input stack. 698 owner.inputStackTop -= elements - outputStackTop; 699 outputStackTop = 0; 700 } 701 } 702 703 /** 704 * Pops a type from the output frame stack. 705 * 706 * @param desc the descriptor of the type to be popped. Can also be a method 707 * descriptor (in this case this method pops the types corresponding 708 * to the method arguments). 709 */ 710 private void pop(final String desc) { 711 char c = desc.charAt(0); 712 if (c == '(') { 713 pop((MethodWriter.getArgumentsAndReturnSizes(desc) >> 2) - 1); 714 } else if (c == 'J' || c == 'D') { 715 pop(2); 716 } else { 717 pop(1); 718 } 719 } 720 721 /** 722 * Adds a new type to the list of types on which a constructor is invoked in 723 * the basic block. 724 * 725 * @param var a type on a which a constructor is invoked. 726 */ 727 private void init(final int var) { 728 // creates and/or resizes the initializations array if necessary 729 if (initializations == null) { 730 initializations = new int[2]; 731 } 732 int n = initializations.length; 733 if (initializationCount >= n) { 734 int[] t = new int[Math.max(initializationCount + 1, 2 * n)]; 735 System.arraycopy(initializations, 0, t, 0, n); 736 initializations = t; 737 } 738 // stores the type to be initialized 739 initializations[initializationCount++] = var; 740 } 741 742 /** 743 * Replaces the given type with the appropriate type if it is one of the 744 * types on which a constructor is invoked in the basic block. 745 * 746 * @param cw the ClassWriter to which this label belongs. 747 * @param t a type 748 * @return t or, if t is one of the types on which a constructor is invoked 749 * in the basic block, the type corresponding to this constructor. 750 */ 751 private int init(final ClassWriter cw, final int t) { 752 int s; 753 if (t == UNINITIALIZED_THIS) { 754 s = OBJECT | cw.addType(cw.thisName); 755 } else if ((t & (DIM | BASE_KIND)) == UNINITIALIZED) { 756 String type = cw.typeTable[t & BASE_VALUE].strVal1; 757 s = OBJECT | cw.addType(type); 758 } else { 759 return t; 760 } 761 for (int j = 0; j < initializationCount; ++j) { 762 int u = initializations[j]; 763 int dim = u & DIM; 764 int kind = u & KIND; 765 if (kind == LOCAL) { 766 u = dim + inputLocals[u & VALUE]; 767 } else if (kind == STACK) { 768 u = dim + inputStack[inputStack.length - (u & VALUE)]; 769 } 770 if (t == u) { 771 return s; 772 } 773 } 774 return t; 775 } 776 777 /** 778 * Initializes the input frame of the first basic block from the method 779 * descriptor. 780 * 781 * @param cw the ClassWriter to which this label belongs. 782 * @param access the access flags of the method to which this label belongs. 783 * @param args the formal parameter types of this method. 784 * @param maxLocals the maximum number of local variables of this method. 785 */ 786 void initInputFrame( 787 final ClassWriter cw, 788 final int access, 789 final Type[] args, 790 final int maxLocals) 791 { 792 inputLocals = new int[maxLocals]; 793 inputStack = new int[0]; 794 int i = 0; 795 if ((access & Opcodes.ACC_STATIC) == 0) { 796 if ((access & MethodWriter.ACC_CONSTRUCTOR) == 0) { 797 inputLocals[i++] = OBJECT | cw.addType(cw.thisName); 798 } else { 799 inputLocals[i++] = UNINITIALIZED_THIS; 800 } 801 } 802 for (int j = 0; j < args.length; ++j) { 803 int t = type(cw, args[j].getDescriptor()); 804 inputLocals[i++] = t; 805 if (t == LONG || t == DOUBLE) { 806 inputLocals[i++] = TOP; 807 } 808 } 809 while (i < maxLocals) { 810 inputLocals[i++] = TOP; 811 } 812 } 813 814 /** 815 * Simulates the action of the given instruction on the output stack frame. 816 * 817 * @param opcode the opcode of the instruction. 818 * @param arg the operand of the instruction, if any. 819 * @param cw the class writer to which this label belongs. 820 * @param item the operand of the instructions, if any. 821 */ 822 void execute( 823 final int opcode, 824 final int arg, 825 final ClassWriter cw, 826 final Item item) 827 { 828 int t1, t2, t3, t4; 829 switch (opcode) { 830 case Opcodes.NOP: 831 case Opcodes.INEG: 832 case Opcodes.LNEG: 833 case Opcodes.FNEG: 834 case Opcodes.DNEG: 835 case Opcodes.I2B: 836 case Opcodes.I2C: 837 case Opcodes.I2S: 838 case Opcodes.GOTO: 839 case Opcodes.RETURN: 840 break; 841 case Opcodes.ACONST_NULL: 842 push(NULL); 843 break; 844 case Opcodes.ICONST_M1: 845 case Opcodes.ICONST_0: 846 case Opcodes.ICONST_1: 847 case Opcodes.ICONST_2: 848 case Opcodes.ICONST_3: 849 case Opcodes.ICONST_4: 850 case Opcodes.ICONST_5: 851 case Opcodes.BIPUSH: 852 case Opcodes.SIPUSH: 853 case Opcodes.ILOAD: 854 push(INTEGER); 855 break; 856 case Opcodes.LCONST_0: 857 case Opcodes.LCONST_1: 858 case Opcodes.LLOAD: 859 push(LONG); 860 push(TOP); 861 break; 862 case Opcodes.FCONST_0: 863 case Opcodes.FCONST_1: 864 case Opcodes.FCONST_2: 865 case Opcodes.FLOAD: 866 push(FLOAT); 867 break; 868 case Opcodes.DCONST_0: 869 case Opcodes.DCONST_1: 870 case Opcodes.DLOAD: 871 push(DOUBLE); 872 push(TOP); 873 break; 874 case Opcodes.LDC: 875 switch (item.type) { 876 case ClassWriter.INT: 877 push(INTEGER); 878 break; 879 case ClassWriter.LONG: 880 push(LONG); 881 push(TOP); 882 break; 883 case ClassWriter.FLOAT: 884 push(FLOAT); 885 break; 886 case ClassWriter.DOUBLE: 887 push(DOUBLE); 888 push(TOP); 889 break; 890 case ClassWriter.CLASS: 891 push(OBJECT | cw.addType("java/lang/Class")); 892 break; 893 // case ClassWriter.STR: 894 default: 895 push(OBJECT | cw.addType("java/lang/String")); 896 } 897 break; 898 case Opcodes.ALOAD: 899 push(get(arg)); 900 break; 901 case Opcodes.IALOAD: 902 case Opcodes.BALOAD: 903 case Opcodes.CALOAD: 904 case Opcodes.SALOAD: 905 pop(2); 906 push(INTEGER); 907 break; 908 case Opcodes.LALOAD: 909 case Opcodes.D2L: 910 pop(2); 911 push(LONG); 912 push(TOP); 913 break; 914 case Opcodes.FALOAD: 915 pop(2); 916 push(FLOAT); 917 break; 918 case Opcodes.DALOAD: 919 case Opcodes.L2D: 920 pop(2); 921 push(DOUBLE); 922 push(TOP); 923 break; 924 case Opcodes.AALOAD: 925 pop(1); 926 t1 = pop(); 927 push(ELEMENT_OF + t1); 928 break; 929 case Opcodes.ISTORE: 930 case Opcodes.FSTORE: 931 case Opcodes.ASTORE: 932 t1 = pop(); 933 set(arg, t1); 934 if (arg > 0) { 935 t2 = get(arg - 1); 936 // if t2 is of kind STACK or LOCAL we cannot know its size! 937 if (t2 == LONG || t2 == DOUBLE) { 938 set(arg - 1, TOP); 939 } 940 } 941 break; 942 case Opcodes.LSTORE: 943 case Opcodes.DSTORE: 944 pop(1); 945 t1 = pop(); 946 set(arg, t1); 947 set(arg + 1, TOP); 948 if (arg > 0) { 949 t2 = get(arg - 1); 950 // if t2 is of kind STACK or LOCAL we cannot know its size! 951 if (t2 == LONG || t2 == DOUBLE) { 952 set(arg - 1, TOP); 953 } 954 } 955 break; 956 case Opcodes.IASTORE: 957 case Opcodes.BASTORE: 958 case Opcodes.CASTORE: 959 case Opcodes.SASTORE: 960 case Opcodes.FASTORE: 961 case Opcodes.AASTORE: 962 pop(3); 963 break; 964 case Opcodes.LASTORE: 965 case Opcodes.DASTORE: 966 pop(4); 967 break; 968 case Opcodes.POP: 969 case Opcodes.IFEQ: 970 case Opcodes.IFNE: 971 case Opcodes.IFLT: 972 case Opcodes.IFGE: 973 case Opcodes.IFGT: 974 case Opcodes.IFLE: 975 case Opcodes.IRETURN: 976 case Opcodes.FRETURN: 977 case Opcodes.ARETURN: 978 case Opcodes.TABLESWITCH: 979 case Opcodes.LOOKUPSWITCH: 980 case Opcodes.ATHROW: 981 case Opcodes.MONITORENTER: 982 case Opcodes.MONITOREXIT: 983 case Opcodes.IFNULL: 984 case Opcodes.IFNONNULL: 985 pop(1); 986 break; 987 case Opcodes.POP2: 988 case Opcodes.IF_ICMPEQ: 989 case Opcodes.IF_ICMPNE: 990 case Opcodes.IF_ICMPLT: 991 case Opcodes.IF_ICMPGE: 992 case Opcodes.IF_ICMPGT: 993 case Opcodes.IF_ICMPLE: 994 case Opcodes.IF_ACMPEQ: 995 case Opcodes.IF_ACMPNE: 996 case Opcodes.LRETURN: 997 case Opcodes.DRETURN: 998 pop(2); 999 break; 1000 case Opcodes.DUP: 1001 t1 = pop(); 1002 push(t1); 1003 push(t1); 1004 break; 1005 case Opcodes.DUP_X1: 1006 t1 = pop(); 1007 t2 = pop(); 1008 push(t1); 1009 push(t2); 1010 push(t1); 1011 break; 1012 case Opcodes.DUP_X2: 1013 t1 = pop(); 1014 t2 = pop(); 1015 t3 = pop(); 1016 push(t1); 1017 push(t3); 1018 push(t2); 1019 push(t1); 1020 break; 1021 case Opcodes.DUP2: 1022 t1 = pop(); 1023 t2 = pop(); 1024 push(t2); 1025 push(t1); 1026 push(t2); 1027 push(t1); 1028 break; 1029 case Opcodes.DUP2_X1: 1030 t1 = pop(); 1031 t2 = pop(); 1032 t3 = pop(); 1033 push(t2); 1034 push(t1); 1035 push(t3); 1036 push(t2); 1037 push(t1); 1038 break; 1039 case Opcodes.DUP2_X2: 1040 t1 = pop(); 1041 t2 = pop(); 1042 t3 = pop(); 1043 t4 = pop(); 1044 push(t2); 1045 push(t1); 1046 push(t4); 1047 push(t3); 1048 push(t2); 1049 push(t1); 1050 break; 1051 case Opcodes.SWAP: 1052 t1 = pop(); 1053 t2 = pop(); 1054 push(t1); 1055 push(t2); 1056 break; 1057 case Opcodes.IADD: 1058 case Opcodes.ISUB: 1059 case Opcodes.IMUL: 1060 case Opcodes.IDIV: 1061 case Opcodes.IREM: 1062 case Opcodes.IAND: 1063 case Opcodes.IOR: 1064 case Opcodes.IXOR: 1065 case Opcodes.ISHL: 1066 case Opcodes.ISHR: 1067 case Opcodes.IUSHR: 1068 case Opcodes.L2I: 1069 case Opcodes.D2I: 1070 case Opcodes.FCMPL: 1071 case Opcodes.FCMPG: 1072 pop(2); 1073 push(INTEGER); 1074 break; 1075 case Opcodes.LADD: 1076 case Opcodes.LSUB: 1077 case Opcodes.LMUL: 1078 case Opcodes.LDIV: 1079 case Opcodes.LREM: 1080 case Opcodes.LAND: 1081 case Opcodes.LOR: 1082 case Opcodes.LXOR: 1083 pop(4); 1084 push(LONG); 1085 push(TOP); 1086 break; 1087 case Opcodes.FADD: 1088 case Opcodes.FSUB: 1089 case Opcodes.FMUL: 1090 case Opcodes.FDIV: 1091 case Opcodes.FREM: 1092 case Opcodes.L2F: 1093 case Opcodes.D2F: 1094 pop(2); 1095 push(FLOAT); 1096 break; 1097 case Opcodes.DADD: 1098 case Opcodes.DSUB: 1099 case Opcodes.DMUL: 1100 case Opcodes.DDIV: 1101 case Opcodes.DREM: 1102 pop(4); 1103 push(DOUBLE); 1104 push(TOP); 1105 break; 1106 case Opcodes.LSHL: 1107 case Opcodes.LSHR: 1108 case Opcodes.LUSHR: 1109 pop(3); 1110 push(LONG); 1111 push(TOP); 1112 break; 1113 case Opcodes.IINC: 1114 set(arg, INTEGER); 1115 break; 1116 case Opcodes.I2L: 1117 case Opcodes.F2L: 1118 pop(1); 1119 push(LONG); 1120 push(TOP); 1121 break; 1122 case Opcodes.I2F: 1123 pop(1); 1124 push(FLOAT); 1125 break; 1126 case Opcodes.I2D: 1127 case Opcodes.F2D: 1128 pop(1); 1129 push(DOUBLE); 1130 push(TOP); 1131 break; 1132 case Opcodes.F2I: 1133 case Opcodes.ARRAYLENGTH: 1134 case Opcodes.INSTANCEOF: 1135 pop(1); 1136 push(INTEGER); 1137 break; 1138 case Opcodes.LCMP: 1139 case Opcodes.DCMPL: 1140 case Opcodes.DCMPG: 1141 pop(4); 1142 push(INTEGER); 1143 break; 1144 case Opcodes.JSR: 1145 case Opcodes.RET: 1146 throw new RuntimeException("JSR/RET are not supported with computeFrames option"); 1147 case Opcodes.GETSTATIC: 1148 push(cw, item.strVal3); 1149 break; 1150 case Opcodes.PUTSTATIC: 1151 pop(item.strVal3); 1152 break; 1153 case Opcodes.GETFIELD: 1154 pop(1); 1155 push(cw, item.strVal3); 1156 break; 1157 case Opcodes.PUTFIELD: 1158 pop(item.strVal3); 1159 pop(); 1160 break; 1161 case Opcodes.INVOKEVIRTUAL: 1162 case Opcodes.INVOKESPECIAL: 1163 case Opcodes.INVOKESTATIC: 1164 case Opcodes.INVOKEINTERFACE: 1165 pop(item.strVal3); 1166 if (opcode != Opcodes.INVOKESTATIC) { 1167 t1 = pop(); 1168 if (opcode == Opcodes.INVOKESPECIAL 1169 && item.strVal2.charAt(0) == '<') 1170 { 1171 init(t1); 1172 } 1173 } 1174 push(cw, item.strVal3); 1175 break; 1176 case Opcodes.NEW: 1177 push(UNINITIALIZED | cw.addUninitializedType(item.strVal1, arg)); 1178 break; 1179 case Opcodes.NEWARRAY: 1180 pop(); 1181 switch (arg) { 1182 case Opcodes.T_BOOLEAN: 1183 push(ARRAY_OF | BOOLEAN); 1184 break; 1185 case Opcodes.T_CHAR: 1186 push(ARRAY_OF | CHAR); 1187 break; 1188 case Opcodes.T_BYTE: 1189 push(ARRAY_OF | BYTE); 1190 break; 1191 case Opcodes.T_SHORT: 1192 push(ARRAY_OF | SHORT); 1193 break; 1194 case Opcodes.T_INT: 1195 push(ARRAY_OF | INTEGER); 1196 break; 1197 case Opcodes.T_FLOAT: 1198 push(ARRAY_OF | FLOAT); 1199 break; 1200 case Opcodes.T_DOUBLE: 1201 push(ARRAY_OF | DOUBLE); 1202 break; 1203 // case Opcodes.T_LONG: 1204 default: 1205 push(ARRAY_OF | LONG); 1206 break; 1207 } 1208 break; 1209 case Opcodes.ANEWARRAY: 1210 String s = item.strVal1; 1211 pop(); 1212 if (s.charAt(0) == '[') { 1213 push(cw, '[' + s); 1214 } else { 1215 push(ARRAY_OF | OBJECT | cw.addType(s)); 1216 } 1217 break; 1218 case Opcodes.CHECKCAST: 1219 s = item.strVal1; 1220 pop(); 1221 if (s.charAt(0) == '[') { 1222 push(cw, s); 1223 } else { 1224 push(OBJECT | cw.addType(s)); 1225 } 1226 break; 1227 // case Opcodes.MULTIANEWARRAY: 1228 default: 1229 pop(arg); 1230 push(cw, item.strVal1); 1231 break; 1232 } 1233 } 1234 1235 /** 1236 * Merges the input frame of the given basic block with the input and output 1237 * frames of this basic block. Returns <tt>true</tt> if the input frame of 1238 * the given label has been changed by this operation. 1239 * 1240 * @param cw the ClassWriter to which this label belongs. 1241 * @param frame the basic block whose input frame must be updated. 1242 * @param edge the kind of the {@link Edge} between this label and 'label'. 1243 * See {@link Edge#info}. 1244 * @return <tt>true</tt> if the input frame of the given label has been 1245 * changed by this operation. 1246 */ 1247 boolean merge(final ClassWriter cw, final Frame frame, final int edge) { 1248 boolean changed = false; 1249 int i, s, dim, kind, t; 1250 1251 int nLocal = inputLocals.length; 1252 int nStack = inputStack.length; 1253 if (frame.inputLocals == null) { 1254 frame.inputLocals = new int[nLocal]; 1255 changed = true; 1256 } 1257 1258 for (i = 0; i < nLocal; ++i) { 1259 if (outputLocals != null && i < outputLocals.length) { 1260 s = outputLocals[i]; 1261 if (s == 0) { 1262 t = inputLocals[i]; 1263 } else { 1264 dim = s & DIM; 1265 kind = s & KIND; 1266 if (kind == LOCAL) { 1267 t = dim + inputLocals[s & VALUE]; 1268 } else if (kind == STACK) { 1269 t = dim + inputStack[nStack - (s & VALUE)]; 1270 } else { 1271 t = s; 1272 } 1273 } 1274 } else { 1275 t = inputLocals[i]; 1276 } 1277 if (initializations != null) { 1278 t = init(cw, t); 1279 } 1280 changed |= merge(cw, t, frame.inputLocals, i); 1281 } 1282 1283 if (edge > 0) { 1284 for (i = 0; i < nLocal; ++i) { 1285 t = inputLocals[i]; 1286 changed |= merge(cw, t, frame.inputLocals, i); 1287 } 1288 if (frame.inputStack == null) { 1289 frame.inputStack = new int[1]; 1290 changed = true; 1291 } 1292 changed |= merge(cw, edge, frame.inputStack, 0); 1293 return changed; 1294 } 1295 1296 int nInputStack = inputStack.length + owner.inputStackTop; 1297 if (frame.inputStack == null) { 1298 frame.inputStack = new int[nInputStack + outputStackTop]; 1299 changed = true; 1300 } 1301 1302 for (i = 0; i < nInputStack; ++i) { 1303 t = inputStack[i]; 1304 if (initializations != null) { 1305 t = init(cw, t); 1306 } 1307 changed |= merge(cw, t, frame.inputStack, i); 1308 } 1309 for (i = 0; i < outputStackTop; ++i) { 1310 s = outputStack[i]; 1311 dim = s & DIM; 1312 kind = s & KIND; 1313 if (kind == LOCAL) { 1314 t = dim + inputLocals[s & VALUE]; 1315 } else if (kind == STACK) { 1316 t = dim + inputStack[nStack - (s & VALUE)]; 1317 } else { 1318 t = s; 1319 } 1320 if (initializations != null) { 1321 t = init(cw, t); 1322 } 1323 changed |= merge(cw, t, frame.inputStack, nInputStack + i); 1324 } 1325 return changed; 1326 } 1327 1328 /** 1329 * Merges the type at the given index in the given type array with the given 1330 * type. Returns <tt>true</tt> if the type array has been modified by this 1331 * operation. 1332 * 1333 * @param cw the ClassWriter to which this label belongs. 1334 * @param t the type with which the type array element must be merged. 1335 * @param types an array of types. 1336 * @param index the index of the type that must be merged in 'types'. 1337 * @return <tt>true</tt> if the type array has been modified by this 1338 * operation. 1339 */ 1340 private static boolean merge( 1341 final ClassWriter cw, 1342 int t, 1343 final int[] types, 1344 final int index) 1345 { 1346 int u = types[index]; 1347 if (u == t) { 1348 // if the types are equal, merge(u,t)=u, so there is no change 1349 return false; 1350 } 1351 if ((t & ~DIM) == NULL) { 1352 if (u == NULL) { 1353 return false; 1354 } 1355 t = NULL; 1356 } 1357 if (u == 0) { 1358 // if types[index] has never been assigned, merge(u,t)=t 1359 types[index] = t; 1360 return true; 1361 } 1362 int v; 1363 if ((u & BASE_KIND) == OBJECT || (u & DIM) != 0) { 1364 // if u is a reference type of any dimension 1365 if (t == NULL) { 1366 // if t is the NULL type, merge(u,t)=u, so there is no change 1367 return false; 1368 } else if ((t & (DIM | BASE_KIND)) == (u & (DIM | BASE_KIND))) { 1369 if ((u & BASE_KIND) == OBJECT) { 1370 // if t is also a reference type, and if u and t have the 1371 // same dimension merge(u,t) = dim(t) | common parent of the 1372 // element types of u and t 1373 v = (t & DIM) | OBJECT 1374 | cw.getMergedType(t & BASE_VALUE, u & BASE_VALUE); 1375 } else { 1376 // if u and t are array types, but not with the same element 1377 // type, merge(u,t)=java/lang/Object 1378 v = OBJECT | cw.addType("java/lang/Object"); 1379 } 1380 } else if ((t & BASE_KIND) == OBJECT || (t & DIM) != 0) { 1381 // if t is any other reference or array type, 1382 // merge(u,t)=java/lang/Object 1383 v = OBJECT | cw.addType("java/lang/Object"); 1384 } else { 1385 // if t is any other type, merge(u,t)=TOP 1386 v = TOP; 1387 } 1388 } else if (u == NULL) { 1389 // if u is the NULL type, merge(u,t)=t, 1390 // or TOP if t is not a reference type 1391 v = (t & BASE_KIND) == OBJECT || (t & DIM) != 0 ? t : TOP; 1392 } else { 1393 // if u is any other type, merge(u,t)=TOP whatever t 1394 v = TOP; 1395 } 1396 if (u != v) { 1397 types[index] = v; 1398 return true; 1399 } 1400 return false; 1401 } 1402} 1403