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 */ 30 package 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 */ 37 final 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 */ get(final int local)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 */ set(final int local, final int type)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 */ push(final int type)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 */ push(final ClassWriter cw, final String desc)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 */ type(final ClassWriter cw, final String desc)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 */ pop()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 */ pop(final int elements)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 */ pop(final String desc)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 */ init(final int var)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 */ init(final ClassWriter cw, final int t)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 */ initInputFrame( final ClassWriter cw, final int access, final Type[] args, final int maxLocals)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 */ execute( final int opcode, final int arg, final ClassWriter cw, final Item item)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 */ merge(final ClassWriter cw, final Frame frame, final int edge)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 */ merge( final ClassWriter cw, int t, final int[] types, final int index)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