1 // ASM: a very small and fast Java bytecode manipulation framework 2 // Copyright (c) 2000-2011 INRIA, France Telecom 3 // All rights reserved. 4 // 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions 7 // are met: 8 // 1. Redistributions of source code must retain the above copyright 9 // notice, this list of conditions and the following disclaimer. 10 // 2. Redistributions in binary form must reproduce the above copyright 11 // notice, this list of conditions and the following disclaimer in the 12 // documentation and/or other materials provided with the distribution. 13 // 3. Neither the name of the copyright holders nor the names of its 14 // contributors may be used to endorse or promote products derived from 15 // this software without specific prior written permission. 16 // 17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 27 // THE POSSIBILITY OF SUCH DAMAGE. 28 package org.objectweb.asm; 29 30 /** 31 * The input and output stack map frames of a basic block. 32 * 33 * <p>Stack map frames are computed in two steps: 34 * 35 * <ul> 36 * <li>During the visit of each instruction in MethodWriter, the state of the frame at the end of 37 * the current basic block is updated by simulating the action of the instruction on the 38 * previous state of this so called "output frame". 39 * <li>After all instructions have been visited, a fix point algorithm is used in MethodWriter to 40 * compute the "input frame" of each basic block (i.e. the stack map frame at the beginning of 41 * the basic block). See {@link MethodWriter#computeAllFrames}. 42 * </ul> 43 * 44 * <p>Output stack map frames are computed relatively to the input frame of the basic block, which 45 * is not yet known when output frames are computed. It is therefore necessary to be able to 46 * represent abstract types such as "the type at position x in the input frame locals" or "the type 47 * at position x from the top of the input frame stack" or even "the type at position x in the input 48 * frame, with y more (or less) array dimensions". This explains the rather complicated type format 49 * used in this class, explained below. 50 * 51 * <p>The local variables and the operand stack of input and output frames contain values called 52 * "abstract types" hereafter. An abstract type is represented with 4 fields named DIM, KIND, FLAGS 53 * and VALUE, packed in a single int value for better performance and memory efficiency: 54 * 55 * <pre> 56 * ===================================== 57 * |...DIM|KIND|.F|...............VALUE| 58 * ===================================== 59 * </pre> 60 * 61 * <ul> 62 * <li>the DIM field, stored in the 6 most significant bits, is a signed number of array 63 * dimensions (from -32 to 31, included). It can be retrieved with {@link #DIM_MASK} and a 64 * right shift of {@link #DIM_SHIFT}. 65 * <li>the KIND field, stored in 4 bits, indicates the kind of VALUE used. These 4 bits can be 66 * retrieved with {@link #KIND_MASK} and, without any shift, must be equal to {@link 67 * #CONSTANT_KIND}, {@link #REFERENCE_KIND}, {@link #UNINITIALIZED_KIND}, {@link #LOCAL_KIND} 68 * or {@link #STACK_KIND}. 69 * <li>the FLAGS field, stored in 2 bits, contains up to 2 boolean flags. Currently only one flag 70 * is defined, namely {@link #TOP_IF_LONG_OR_DOUBLE_FLAG}. 71 * <li>the VALUE field, stored in the remaining 20 bits, contains either 72 * <ul> 73 * <li>one of the constants {@link #ITEM_TOP}, {@link #ITEM_ASM_BOOLEAN}, {@link 74 * #ITEM_ASM_BYTE}, {@link #ITEM_ASM_CHAR} or {@link #ITEM_ASM_SHORT}, {@link 75 * #ITEM_INTEGER}, {@link #ITEM_FLOAT}, {@link #ITEM_LONG}, {@link #ITEM_DOUBLE}, {@link 76 * #ITEM_NULL} or {@link #ITEM_UNINITIALIZED_THIS}, if KIND is equal to {@link 77 * #CONSTANT_KIND}. 78 * <li>the index of a {@link Symbol#TYPE_TAG} {@link Symbol} in the type table of a {@link 79 * SymbolTable}, if KIND is equal to {@link #REFERENCE_KIND}. 80 * <li>the index of an {@link Symbol#UNINITIALIZED_TYPE_TAG} {@link Symbol} in the type 81 * table of a SymbolTable, if KIND is equal to {@link #UNINITIALIZED_KIND}. 82 * <li>the index of a local variable in the input stack frame, if KIND is equal to {@link 83 * #LOCAL_KIND}. 84 * <li>a position relatively to the top of the stack of the input stack frame, if KIND is 85 * equal to {@link #STACK_KIND}, 86 * </ul> 87 * </ul> 88 * 89 * <p>Output frames can contain abstract types of any kind and with a positive or negative array 90 * dimension (and even unassigned types, represented by 0 - which does not correspond to any valid 91 * abstract type value). Input frames can only contain CONSTANT_KIND, REFERENCE_KIND or 92 * UNINITIALIZED_KIND abstract types of positive or {@literal null} array dimension. In all cases 93 * the type table contains only internal type names (array type descriptors are forbidden - array 94 * dimensions must be represented through the DIM field). 95 * 96 * <p>The LONG and DOUBLE types are always represented by using two slots (LONG + TOP or DOUBLE + 97 * TOP), for local variables as well as in the operand stack. This is necessary to be able to 98 * simulate DUPx_y instructions, whose effect would be dependent on the concrete types represented 99 * by the abstract types in the stack (which are not always known). 100 * 101 * @author Eric Bruneton 102 */ 103 class Frame { 104 105 // Constants used in the StackMapTable attribute. 106 // See https://docs.oracle.com/javase/specs/jvms/se9/html/jvms-4.html#jvms-4.7.4. 107 108 static final int SAME_FRAME = 0; 109 static final int SAME_LOCALS_1_STACK_ITEM_FRAME = 64; 110 static final int RESERVED = 128; 111 static final int SAME_LOCALS_1_STACK_ITEM_FRAME_EXTENDED = 247; 112 static final int CHOP_FRAME = 248; 113 static final int SAME_FRAME_EXTENDED = 251; 114 static final int APPEND_FRAME = 252; 115 static final int FULL_FRAME = 255; 116 117 static final int ITEM_TOP = 0; 118 static final int ITEM_INTEGER = 1; 119 static final int ITEM_FLOAT = 2; 120 static final int ITEM_DOUBLE = 3; 121 static final int ITEM_LONG = 4; 122 static final int ITEM_NULL = 5; 123 static final int ITEM_UNINITIALIZED_THIS = 6; 124 static final int ITEM_OBJECT = 7; 125 static final int ITEM_UNINITIALIZED = 8; 126 // Additional, ASM specific constants used in abstract types below. 127 private static final int ITEM_ASM_BOOLEAN = 9; 128 private static final int ITEM_ASM_BYTE = 10; 129 private static final int ITEM_ASM_CHAR = 11; 130 private static final int ITEM_ASM_SHORT = 12; 131 132 // The size and offset in bits of each field of an abstract type. 133 134 private static final int DIM_SIZE = 6; 135 private static final int KIND_SIZE = 4; 136 private static final int FLAGS_SIZE = 2; 137 private static final int VALUE_SIZE = 32 - DIM_SIZE - KIND_SIZE - FLAGS_SIZE; 138 139 private static final int DIM_SHIFT = KIND_SIZE + FLAGS_SIZE + VALUE_SIZE; 140 private static final int KIND_SHIFT = FLAGS_SIZE + VALUE_SIZE; 141 private static final int FLAGS_SHIFT = VALUE_SIZE; 142 143 // Bitmasks to get each field of an abstract type. 144 145 private static final int DIM_MASK = ((1 << DIM_SIZE) - 1) << DIM_SHIFT; 146 private static final int KIND_MASK = ((1 << KIND_SIZE) - 1) << KIND_SHIFT; 147 private static final int VALUE_MASK = (1 << VALUE_SIZE) - 1; 148 149 // Constants to manipulate the DIM field of an abstract type. 150 151 /** The constant to be added to an abstract type to get one with one more array dimension. */ 152 private static final int ARRAY_OF = +1 << DIM_SHIFT; 153 154 /** The constant to be added to an abstract type to get one with one less array dimension. */ 155 private static final int ELEMENT_OF = -1 << DIM_SHIFT; 156 157 // Possible values for the KIND field of an abstract type. 158 159 private static final int CONSTANT_KIND = 1 << KIND_SHIFT; 160 private static final int REFERENCE_KIND = 2 << KIND_SHIFT; 161 private static final int UNINITIALIZED_KIND = 3 << KIND_SHIFT; 162 private static final int LOCAL_KIND = 4 << KIND_SHIFT; 163 private static final int STACK_KIND = 5 << KIND_SHIFT; 164 165 // Possible flags for the FLAGS field of an abstract type. 166 167 /** 168 * A flag used for LOCAL_KIND and STACK_KIND abstract types, indicating that if the resolved, 169 * concrete type is LONG or DOUBLE, TOP should be used instead (because the value has been 170 * partially overridden with an xSTORE instruction). 171 */ 172 private static final int TOP_IF_LONG_OR_DOUBLE_FLAG = 1 << FLAGS_SHIFT; 173 174 // Useful predefined abstract types (all the possible CONSTANT_KIND types). 175 176 private static final int TOP = CONSTANT_KIND | ITEM_TOP; 177 private static final int BOOLEAN = CONSTANT_KIND | ITEM_ASM_BOOLEAN; 178 private static final int BYTE = CONSTANT_KIND | ITEM_ASM_BYTE; 179 private static final int CHAR = CONSTANT_KIND | ITEM_ASM_CHAR; 180 private static final int SHORT = CONSTANT_KIND | ITEM_ASM_SHORT; 181 private static final int INTEGER = CONSTANT_KIND | ITEM_INTEGER; 182 private static final int FLOAT = CONSTANT_KIND | ITEM_FLOAT; 183 private static final int LONG = CONSTANT_KIND | ITEM_LONG; 184 private static final int DOUBLE = CONSTANT_KIND | ITEM_DOUBLE; 185 private static final int NULL = CONSTANT_KIND | ITEM_NULL; 186 private static final int UNINITIALIZED_THIS = CONSTANT_KIND | ITEM_UNINITIALIZED_THIS; 187 188 // ----------------------------------------------------------------------------------------------- 189 // Instance fields 190 // ----------------------------------------------------------------------------------------------- 191 192 /** The basic block to which these input and output stack map frames correspond. */ 193 Label owner; 194 195 /** The input stack map frame locals. This is an array of abstract types. */ 196 private int[] inputLocals; 197 198 /** The input stack map frame stack. This is an array of abstract types. */ 199 private int[] inputStack; 200 201 /** The output stack map frame locals. This is an array of abstract types. */ 202 private int[] outputLocals; 203 204 /** The output stack map frame stack. This is an array of abstract types. */ 205 private int[] outputStack; 206 207 /** 208 * The start of the output stack, relatively to the input stack. This offset is always negative or 209 * null. A null offset means that the output stack must be appended to the input stack. A -n 210 * offset means that the first n output stack elements must replace the top n input stack 211 * elements, and that the other elements must be appended to the input stack. 212 */ 213 private short outputStackStart; 214 215 /** The index of the top stack element in {@link #outputStack}. */ 216 private short outputStackTop; 217 218 /** The number of types that are initialized in the basic block. See {@link #initializations}. */ 219 private int initializationCount; 220 221 /** 222 * The abstract types that are initialized in the basic block. A constructor invocation on an 223 * UNINITIALIZED or UNINITIALIZED_THIS abstract type must replace <i>every occurrence</i> of this 224 * type in the local variables and in the operand stack. This cannot be done during the first step 225 * of the algorithm since, during this step, the local variables and the operand stack types are 226 * still abstract. It is therefore necessary to store the abstract types of the constructors which 227 * are invoked in the basic block, in order to do this replacement during the second step of the 228 * algorithm, where the frames are fully computed. Note that this array can contain abstract types 229 * that are relative to the input locals or to the input stack. 230 */ 231 private int[] initializations; 232 233 // ----------------------------------------------------------------------------------------------- 234 // Constructor 235 // ----------------------------------------------------------------------------------------------- 236 237 /** 238 * Constructs a new Frame. 239 * 240 * @param owner the basic block to which these input and output stack map frames correspond. 241 */ Frame(final Label owner)242 Frame(final Label owner) { 243 this.owner = owner; 244 } 245 246 /** 247 * Sets this frame to the value of the given frame. 248 * 249 * <p>WARNING: after this method is called the two frames share the same data structures. It is 250 * recommended to discard the given frame to avoid unexpected side effects. 251 * 252 * @param frame The new frame value. 253 */ copyFrom(final Frame frame)254 final void copyFrom(final Frame frame) { 255 inputLocals = frame.inputLocals; 256 inputStack = frame.inputStack; 257 outputStackStart = 0; 258 outputLocals = frame.outputLocals; 259 outputStack = frame.outputStack; 260 outputStackTop = frame.outputStackTop; 261 initializationCount = frame.initializationCount; 262 initializations = frame.initializations; 263 } 264 265 // ----------------------------------------------------------------------------------------------- 266 // Static methods to get abstract types from other type formats 267 // ----------------------------------------------------------------------------------------------- 268 269 /** 270 * Returns the abstract type corresponding to the given public API frame element type. 271 * 272 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 273 * @param type a frame element type described using the same format as in {@link 274 * MethodVisitor#visitFrame}, i.e. either {@link Opcodes#TOP}, {@link Opcodes#INTEGER}, {@link 275 * Opcodes#FLOAT}, {@link Opcodes#LONG}, {@link Opcodes#DOUBLE}, {@link Opcodes#NULL}, or 276 * {@link Opcodes#UNINITIALIZED_THIS}, or the internal name of a class, or a Label designating 277 * a NEW instruction (for uninitialized types). 278 * @return the abstract type corresponding to the given frame element type. 279 */ getAbstractTypeFromApiFormat(final SymbolTable symbolTable, final Object type)280 static int getAbstractTypeFromApiFormat(final SymbolTable symbolTable, final Object type) { 281 if (type instanceof Integer) { 282 return CONSTANT_KIND | ((Integer) type).intValue(); 283 } else if (type instanceof String) { 284 String descriptor = Type.getObjectType((String) type).getDescriptor(); 285 return getAbstractTypeFromDescriptor(symbolTable, descriptor, 0); 286 } else { 287 return UNINITIALIZED_KIND 288 | symbolTable.addUninitializedType("", ((Label) type).bytecodeOffset); 289 } 290 } 291 292 /** 293 * Returns the abstract type corresponding to the internal name of a class. 294 * 295 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 296 * @param internalName the internal name of a class. This must <i>not</i> be an array type 297 * descriptor. 298 * @return the abstract type value corresponding to the given internal name. 299 */ getAbstractTypeFromInternalName( final SymbolTable symbolTable, final String internalName)300 static int getAbstractTypeFromInternalName( 301 final SymbolTable symbolTable, final String internalName) { 302 return REFERENCE_KIND | symbolTable.addType(internalName); 303 } 304 305 /** 306 * Returns the abstract type corresponding to the given type descriptor. 307 * 308 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 309 * @param buffer a string ending with a type descriptor. 310 * @param offset the start offset of the type descriptor in buffer. 311 * @return the abstract type corresponding to the given type descriptor. 312 */ getAbstractTypeFromDescriptor( final SymbolTable symbolTable, final String buffer, final int offset)313 private static int getAbstractTypeFromDescriptor( 314 final SymbolTable symbolTable, final String buffer, final int offset) { 315 String internalName; 316 switch (buffer.charAt(offset)) { 317 case 'V': 318 return 0; 319 case 'Z': 320 case 'C': 321 case 'B': 322 case 'S': 323 case 'I': 324 return INTEGER; 325 case 'F': 326 return FLOAT; 327 case 'J': 328 return LONG; 329 case 'D': 330 return DOUBLE; 331 case 'L': 332 internalName = buffer.substring(offset + 1, buffer.length() - 1); 333 return REFERENCE_KIND | symbolTable.addType(internalName); 334 case '[': 335 int elementDescriptorOffset = offset + 1; 336 while (buffer.charAt(elementDescriptorOffset) == '[') { 337 ++elementDescriptorOffset; 338 } 339 int typeValue; 340 switch (buffer.charAt(elementDescriptorOffset)) { 341 case 'Z': 342 typeValue = BOOLEAN; 343 break; 344 case 'C': 345 typeValue = CHAR; 346 break; 347 case 'B': 348 typeValue = BYTE; 349 break; 350 case 'S': 351 typeValue = SHORT; 352 break; 353 case 'I': 354 typeValue = INTEGER; 355 break; 356 case 'F': 357 typeValue = FLOAT; 358 break; 359 case 'J': 360 typeValue = LONG; 361 break; 362 case 'D': 363 typeValue = DOUBLE; 364 break; 365 case 'L': 366 internalName = buffer.substring(elementDescriptorOffset + 1, buffer.length() - 1); 367 typeValue = REFERENCE_KIND | symbolTable.addType(internalName); 368 break; 369 default: 370 throw new IllegalArgumentException( 371 "Invalid descriptor fragment: " + buffer.substring(elementDescriptorOffset)); 372 } 373 return ((elementDescriptorOffset - offset) << DIM_SHIFT) | typeValue; 374 default: 375 throw new IllegalArgumentException("Invalid descriptor: " + buffer.substring(offset)); 376 } 377 } 378 379 // ----------------------------------------------------------------------------------------------- 380 // Methods related to the input frame 381 // ----------------------------------------------------------------------------------------------- 382 383 /** 384 * Sets the input frame from the given method description. This method is used to initialize the 385 * first frame of a method, which is implicit (i.e. not stored explicitly in the StackMapTable 386 * attribute). 387 * 388 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 389 * @param access the method's access flags. 390 * @param descriptor the method descriptor. 391 * @param maxLocals the maximum number of local variables of the method. 392 */ setInputFrameFromDescriptor( final SymbolTable symbolTable, final int access, final String descriptor, final int maxLocals)393 final void setInputFrameFromDescriptor( 394 final SymbolTable symbolTable, 395 final int access, 396 final String descriptor, 397 final int maxLocals) { 398 inputLocals = new int[maxLocals]; 399 inputStack = new int[0]; 400 int inputLocalIndex = 0; 401 if ((access & Opcodes.ACC_STATIC) == 0) { 402 if ((access & Constants.ACC_CONSTRUCTOR) == 0) { 403 inputLocals[inputLocalIndex++] = 404 REFERENCE_KIND | symbolTable.addType(symbolTable.getClassName()); 405 } else { 406 inputLocals[inputLocalIndex++] = UNINITIALIZED_THIS; 407 } 408 } 409 for (Type argumentType : Type.getArgumentTypes(descriptor)) { 410 int abstractType = 411 getAbstractTypeFromDescriptor(symbolTable, argumentType.getDescriptor(), 0); 412 inputLocals[inputLocalIndex++] = abstractType; 413 if (abstractType == LONG || abstractType == DOUBLE) { 414 inputLocals[inputLocalIndex++] = TOP; 415 } 416 } 417 while (inputLocalIndex < maxLocals) { 418 inputLocals[inputLocalIndex++] = TOP; 419 } 420 } 421 422 /** 423 * Sets the input frame from the given public API frame description. 424 * 425 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 426 * @param numLocal the number of local variables. 427 * @param local the local variable types, described using the same format as in {@link 428 * MethodVisitor#visitFrame}. 429 * @param numStack the number of operand stack elements. 430 * @param stack the operand stack types, described using the same format as in {@link 431 * MethodVisitor#visitFrame}. 432 */ setInputFrameFromApiFormat( final SymbolTable symbolTable, final int numLocal, final Object[] local, final int numStack, final Object[] stack)433 final void setInputFrameFromApiFormat( 434 final SymbolTable symbolTable, 435 final int numLocal, 436 final Object[] local, 437 final int numStack, 438 final Object[] stack) { 439 int inputLocalIndex = 0; 440 for (int i = 0; i < numLocal; ++i) { 441 inputLocals[inputLocalIndex++] = getAbstractTypeFromApiFormat(symbolTable, local[i]); 442 if (local[i] == Opcodes.LONG || local[i] == Opcodes.DOUBLE) { 443 inputLocals[inputLocalIndex++] = TOP; 444 } 445 } 446 while (inputLocalIndex < inputLocals.length) { 447 inputLocals[inputLocalIndex++] = TOP; 448 } 449 int numStackTop = 0; 450 for (int i = 0; i < numStack; ++i) { 451 if (stack[i] == Opcodes.LONG || stack[i] == Opcodes.DOUBLE) { 452 ++numStackTop; 453 } 454 } 455 inputStack = new int[numStack + numStackTop]; 456 int inputStackIndex = 0; 457 for (int i = 0; i < numStack; ++i) { 458 inputStack[inputStackIndex++] = getAbstractTypeFromApiFormat(symbolTable, stack[i]); 459 if (stack[i] == Opcodes.LONG || stack[i] == Opcodes.DOUBLE) { 460 inputStack[inputStackIndex++] = TOP; 461 } 462 } 463 outputStackTop = 0; 464 initializationCount = 0; 465 } 466 getInputStackSize()467 final int getInputStackSize() { 468 return inputStack.length; 469 } 470 471 // ----------------------------------------------------------------------------------------------- 472 // Methods related to the output frame 473 // ----------------------------------------------------------------------------------------------- 474 475 /** 476 * Returns the abstract type stored at the given local variable index in the output frame. 477 * 478 * @param localIndex the index of the local variable whose value must be returned. 479 * @return the abstract type stored at the given local variable index in the output frame. 480 */ getLocal(final int localIndex)481 private int getLocal(final int localIndex) { 482 if (outputLocals == null || localIndex >= outputLocals.length) { 483 // If this local has never been assigned in this basic block, it is still equal to its value 484 // in the input frame. 485 return LOCAL_KIND | localIndex; 486 } else { 487 int abstractType = outputLocals[localIndex]; 488 if (abstractType == 0) { 489 // If this local has never been assigned in this basic block, so it is still equal to its 490 // value in the input frame. 491 abstractType = outputLocals[localIndex] = LOCAL_KIND | localIndex; 492 } 493 return abstractType; 494 } 495 } 496 497 /** 498 * Replaces the abstract type stored at the given local variable index in the output frame. 499 * 500 * @param localIndex the index of the output frame local variable that must be set. 501 * @param abstractType the value that must be set. 502 */ setLocal(final int localIndex, final int abstractType)503 private void setLocal(final int localIndex, final int abstractType) { 504 // Create and/or resize the output local variables array if necessary. 505 if (outputLocals == null) { 506 outputLocals = new int[10]; 507 } 508 int outputLocalsLength = outputLocals.length; 509 if (localIndex >= outputLocalsLength) { 510 int[] newOutputLocals = new int[Math.max(localIndex + 1, 2 * outputLocalsLength)]; 511 System.arraycopy(outputLocals, 0, newOutputLocals, 0, outputLocalsLength); 512 outputLocals = newOutputLocals; 513 } 514 // Set the local variable. 515 outputLocals[localIndex] = abstractType; 516 } 517 518 /** 519 * Pushes the given abstract type on the output frame stack. 520 * 521 * @param abstractType an abstract type. 522 */ push(final int abstractType)523 private void push(final int abstractType) { 524 // Create and/or resize the output stack array if necessary. 525 if (outputStack == null) { 526 outputStack = new int[10]; 527 } 528 int outputStackLength = outputStack.length; 529 if (outputStackTop >= outputStackLength) { 530 int[] newOutputStack = new int[Math.max(outputStackTop + 1, 2 * outputStackLength)]; 531 System.arraycopy(outputStack, 0, newOutputStack, 0, outputStackLength); 532 outputStack = newOutputStack; 533 } 534 // Pushes the abstract type on the output stack. 535 outputStack[outputStackTop++] = abstractType; 536 // Updates the maximum size reached by the output stack, if needed (note that this size is 537 // relative to the input stack size, which is not known yet). 538 short outputStackSize = (short) (outputStackStart + outputStackTop); 539 if (outputStackSize > owner.outputStackMax) { 540 owner.outputStackMax = outputStackSize; 541 } 542 } 543 544 /** 545 * Pushes the abstract type corresponding to the given descriptor on the output frame stack. 546 * 547 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 548 * @param descriptor a type or method descriptor (in which case its return type is pushed). 549 */ push(final SymbolTable symbolTable, final String descriptor)550 private void push(final SymbolTable symbolTable, final String descriptor) { 551 int typeDescriptorOffset = 552 descriptor.charAt(0) == '(' ? Type.getReturnTypeOffset(descriptor) : 0; 553 int abstractType = getAbstractTypeFromDescriptor(symbolTable, descriptor, typeDescriptorOffset); 554 if (abstractType != 0) { 555 push(abstractType); 556 if (abstractType == LONG || abstractType == DOUBLE) { 557 push(TOP); 558 } 559 } 560 } 561 562 /** 563 * Pops an abstract type from the output frame stack and returns its value. 564 * 565 * @return the abstract type that has been popped from the output frame stack. 566 */ pop()567 private int pop() { 568 if (outputStackTop > 0) { 569 return outputStack[--outputStackTop]; 570 } else { 571 // If the output frame stack is empty, pop from the input stack. 572 return STACK_KIND | -(--outputStackStart); 573 } 574 } 575 576 /** 577 * Pops the given number of abstract types from the output frame stack. 578 * 579 * @param elements the number of abstract types that must be popped. 580 */ pop(final int elements)581 private void pop(final int elements) { 582 if (outputStackTop >= elements) { 583 outputStackTop -= elements; 584 } else { 585 // If the number of elements to be popped is greater than the number of elements in the output 586 // stack, clear it, and pop the remaining elements from the input stack. 587 outputStackStart -= elements - outputStackTop; 588 outputStackTop = 0; 589 } 590 } 591 592 /** 593 * Pops as many abstract types from the output frame stack as described by the given descriptor. 594 * 595 * @param descriptor a type or method descriptor (in which case its argument types are popped). 596 */ pop(final String descriptor)597 private void pop(final String descriptor) { 598 char firstDescriptorChar = descriptor.charAt(0); 599 if (firstDescriptorChar == '(') { 600 pop((Type.getArgumentsAndReturnSizes(descriptor) >> 2) - 1); 601 } else if (firstDescriptorChar == 'J' || firstDescriptorChar == 'D') { 602 pop(2); 603 } else { 604 pop(1); 605 } 606 } 607 608 // ----------------------------------------------------------------------------------------------- 609 // Methods to handle uninitialized types 610 // ----------------------------------------------------------------------------------------------- 611 612 /** 613 * Adds an abstract type to the list of types on which a constructor is invoked in the basic 614 * block. 615 * 616 * @param abstractType an abstract type on a which a constructor is invoked. 617 */ addInitializedType(final int abstractType)618 private void addInitializedType(final int abstractType) { 619 // Create and/or resize the initializations array if necessary. 620 if (initializations == null) { 621 initializations = new int[2]; 622 } 623 int initializationsLength = initializations.length; 624 if (initializationCount >= initializationsLength) { 625 int[] newInitializations = 626 new int[Math.max(initializationCount + 1, 2 * initializationsLength)]; 627 System.arraycopy(initializations, 0, newInitializations, 0, initializationsLength); 628 initializations = newInitializations; 629 } 630 // Store the abstract type. 631 initializations[initializationCount++] = abstractType; 632 } 633 634 /** 635 * Returns the "initialized" abstract type corresponding to the given abstract type. 636 * 637 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 638 * @param abstractType an abstract type. 639 * @return the REFERENCE_KIND abstract type corresponding to abstractType if it is 640 * UNINITIALIZED_THIS or an UNINITIALIZED_KIND abstract type for one of the types on which a 641 * constructor is invoked in the basic block. Otherwise returns abstractType. 642 */ getInitializedType(final SymbolTable symbolTable, final int abstractType)643 private int getInitializedType(final SymbolTable symbolTable, final int abstractType) { 644 if (abstractType == UNINITIALIZED_THIS 645 || (abstractType & (DIM_MASK | KIND_MASK)) == UNINITIALIZED_KIND) { 646 for (int i = 0; i < initializationCount; ++i) { 647 int initializedType = initializations[i]; 648 int dim = initializedType & DIM_MASK; 649 int kind = initializedType & KIND_MASK; 650 int value = initializedType & VALUE_MASK; 651 if (kind == LOCAL_KIND) { 652 initializedType = dim + inputLocals[value]; 653 } else if (kind == STACK_KIND) { 654 initializedType = dim + inputStack[inputStack.length - value]; 655 } 656 if (abstractType == initializedType) { 657 if (abstractType == UNINITIALIZED_THIS) { 658 return REFERENCE_KIND | symbolTable.addType(symbolTable.getClassName()); 659 } else { 660 return REFERENCE_KIND 661 | symbolTable.addType(symbolTable.getType(abstractType & VALUE_MASK).value); 662 } 663 } 664 } 665 } 666 return abstractType; 667 } 668 669 // ----------------------------------------------------------------------------------------------- 670 // Main method, to simulate the execution of each instruction on the output frame 671 // ----------------------------------------------------------------------------------------------- 672 673 /** 674 * Simulates the action of the given instruction on the output stack frame. 675 * 676 * @param opcode the opcode of the instruction. 677 * @param arg the numeric operand of the instruction, if any. 678 * @param argSymbol the Symbol operand of the instruction, if any. 679 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 680 */ execute( final int opcode, final int arg, final Symbol argSymbol, final SymbolTable symbolTable)681 void execute( 682 final int opcode, final int arg, final Symbol argSymbol, final SymbolTable symbolTable) { 683 // Abstract types popped from the stack or read from local variables. 684 int abstractType1; 685 int abstractType2; 686 int abstractType3; 687 int abstractType4; 688 switch (opcode) { 689 case Opcodes.NOP: 690 case Opcodes.INEG: 691 case Opcodes.LNEG: 692 case Opcodes.FNEG: 693 case Opcodes.DNEG: 694 case Opcodes.I2B: 695 case Opcodes.I2C: 696 case Opcodes.I2S: 697 case Opcodes.GOTO: 698 case Opcodes.RETURN: 699 break; 700 case Opcodes.ACONST_NULL: 701 push(NULL); 702 break; 703 case Opcodes.ICONST_M1: 704 case Opcodes.ICONST_0: 705 case Opcodes.ICONST_1: 706 case Opcodes.ICONST_2: 707 case Opcodes.ICONST_3: 708 case Opcodes.ICONST_4: 709 case Opcodes.ICONST_5: 710 case Opcodes.BIPUSH: 711 case Opcodes.SIPUSH: 712 case Opcodes.ILOAD: 713 push(INTEGER); 714 break; 715 case Opcodes.LCONST_0: 716 case Opcodes.LCONST_1: 717 case Opcodes.LLOAD: 718 push(LONG); 719 push(TOP); 720 break; 721 case Opcodes.FCONST_0: 722 case Opcodes.FCONST_1: 723 case Opcodes.FCONST_2: 724 case Opcodes.FLOAD: 725 push(FLOAT); 726 break; 727 case Opcodes.DCONST_0: 728 case Opcodes.DCONST_1: 729 case Opcodes.DLOAD: 730 push(DOUBLE); 731 push(TOP); 732 break; 733 case Opcodes.LDC: 734 switch (argSymbol.tag) { 735 case Symbol.CONSTANT_INTEGER_TAG: 736 push(INTEGER); 737 break; 738 case Symbol.CONSTANT_LONG_TAG: 739 push(LONG); 740 push(TOP); 741 break; 742 case Symbol.CONSTANT_FLOAT_TAG: 743 push(FLOAT); 744 break; 745 case Symbol.CONSTANT_DOUBLE_TAG: 746 push(DOUBLE); 747 push(TOP); 748 break; 749 case Symbol.CONSTANT_CLASS_TAG: 750 push(REFERENCE_KIND | symbolTable.addType("java/lang/Class")); 751 break; 752 case Symbol.CONSTANT_STRING_TAG: 753 push(REFERENCE_KIND | symbolTable.addType("java/lang/String")); 754 break; 755 case Symbol.CONSTANT_METHOD_TYPE_TAG: 756 push(REFERENCE_KIND | symbolTable.addType("java/lang/invoke/MethodType")); 757 break; 758 case Symbol.CONSTANT_METHOD_HANDLE_TAG: 759 push(REFERENCE_KIND | symbolTable.addType("java/lang/invoke/MethodHandle")); 760 break; 761 case Symbol.CONSTANT_DYNAMIC_TAG: 762 push(symbolTable, argSymbol.value); 763 break; 764 default: 765 throw new AssertionError(); 766 } 767 break; 768 case Opcodes.ALOAD: 769 push(getLocal(arg)); 770 break; 771 case Opcodes.LALOAD: 772 case Opcodes.D2L: 773 pop(2); 774 push(LONG); 775 push(TOP); 776 break; 777 case Opcodes.DALOAD: 778 case Opcodes.L2D: 779 pop(2); 780 push(DOUBLE); 781 push(TOP); 782 break; 783 case Opcodes.AALOAD: 784 pop(1); 785 abstractType1 = pop(); 786 push(abstractType1 == NULL ? abstractType1 : ELEMENT_OF + abstractType1); 787 break; 788 case Opcodes.ISTORE: 789 case Opcodes.FSTORE: 790 case Opcodes.ASTORE: 791 abstractType1 = pop(); 792 setLocal(arg, abstractType1); 793 if (arg > 0) { 794 int previousLocalType = getLocal(arg - 1); 795 if (previousLocalType == LONG || previousLocalType == DOUBLE) { 796 setLocal(arg - 1, TOP); 797 } else if ((previousLocalType & KIND_MASK) == LOCAL_KIND 798 || (previousLocalType & KIND_MASK) == STACK_KIND) { 799 // The type of the previous local variable is not known yet, but if it later appears 800 // to be LONG or DOUBLE, we should then use TOP instead. 801 setLocal(arg - 1, previousLocalType | TOP_IF_LONG_OR_DOUBLE_FLAG); 802 } 803 } 804 break; 805 case Opcodes.LSTORE: 806 case Opcodes.DSTORE: 807 pop(1); 808 abstractType1 = pop(); 809 setLocal(arg, abstractType1); 810 setLocal(arg + 1, TOP); 811 if (arg > 0) { 812 int previousLocalType = getLocal(arg - 1); 813 if (previousLocalType == LONG || previousLocalType == DOUBLE) { 814 setLocal(arg - 1, TOP); 815 } else if ((previousLocalType & KIND_MASK) == LOCAL_KIND 816 || (previousLocalType & KIND_MASK) == STACK_KIND) { 817 // The type of the previous local variable is not known yet, but if it later appears 818 // to be LONG or DOUBLE, we should then use TOP instead. 819 setLocal(arg - 1, previousLocalType | TOP_IF_LONG_OR_DOUBLE_FLAG); 820 } 821 } 822 break; 823 case Opcodes.IASTORE: 824 case Opcodes.BASTORE: 825 case Opcodes.CASTORE: 826 case Opcodes.SASTORE: 827 case Opcodes.FASTORE: 828 case Opcodes.AASTORE: 829 pop(3); 830 break; 831 case Opcodes.LASTORE: 832 case Opcodes.DASTORE: 833 pop(4); 834 break; 835 case Opcodes.POP: 836 case Opcodes.IFEQ: 837 case Opcodes.IFNE: 838 case Opcodes.IFLT: 839 case Opcodes.IFGE: 840 case Opcodes.IFGT: 841 case Opcodes.IFLE: 842 case Opcodes.IRETURN: 843 case Opcodes.FRETURN: 844 case Opcodes.ARETURN: 845 case Opcodes.TABLESWITCH: 846 case Opcodes.LOOKUPSWITCH: 847 case Opcodes.ATHROW: 848 case Opcodes.MONITORENTER: 849 case Opcodes.MONITOREXIT: 850 case Opcodes.IFNULL: 851 case Opcodes.IFNONNULL: 852 pop(1); 853 break; 854 case Opcodes.POP2: 855 case Opcodes.IF_ICMPEQ: 856 case Opcodes.IF_ICMPNE: 857 case Opcodes.IF_ICMPLT: 858 case Opcodes.IF_ICMPGE: 859 case Opcodes.IF_ICMPGT: 860 case Opcodes.IF_ICMPLE: 861 case Opcodes.IF_ACMPEQ: 862 case Opcodes.IF_ACMPNE: 863 case Opcodes.LRETURN: 864 case Opcodes.DRETURN: 865 pop(2); 866 break; 867 case Opcodes.DUP: 868 abstractType1 = pop(); 869 push(abstractType1); 870 push(abstractType1); 871 break; 872 case Opcodes.DUP_X1: 873 abstractType1 = pop(); 874 abstractType2 = pop(); 875 push(abstractType1); 876 push(abstractType2); 877 push(abstractType1); 878 break; 879 case Opcodes.DUP_X2: 880 abstractType1 = pop(); 881 abstractType2 = pop(); 882 abstractType3 = pop(); 883 push(abstractType1); 884 push(abstractType3); 885 push(abstractType2); 886 push(abstractType1); 887 break; 888 case Opcodes.DUP2: 889 abstractType1 = pop(); 890 abstractType2 = pop(); 891 push(abstractType2); 892 push(abstractType1); 893 push(abstractType2); 894 push(abstractType1); 895 break; 896 case Opcodes.DUP2_X1: 897 abstractType1 = pop(); 898 abstractType2 = pop(); 899 abstractType3 = pop(); 900 push(abstractType2); 901 push(abstractType1); 902 push(abstractType3); 903 push(abstractType2); 904 push(abstractType1); 905 break; 906 case Opcodes.DUP2_X2: 907 abstractType1 = pop(); 908 abstractType2 = pop(); 909 abstractType3 = pop(); 910 abstractType4 = pop(); 911 push(abstractType2); 912 push(abstractType1); 913 push(abstractType4); 914 push(abstractType3); 915 push(abstractType2); 916 push(abstractType1); 917 break; 918 case Opcodes.SWAP: 919 abstractType1 = pop(); 920 abstractType2 = pop(); 921 push(abstractType1); 922 push(abstractType2); 923 break; 924 case Opcodes.IALOAD: 925 case Opcodes.BALOAD: 926 case Opcodes.CALOAD: 927 case Opcodes.SALOAD: 928 case Opcodes.IADD: 929 case Opcodes.ISUB: 930 case Opcodes.IMUL: 931 case Opcodes.IDIV: 932 case Opcodes.IREM: 933 case Opcodes.IAND: 934 case Opcodes.IOR: 935 case Opcodes.IXOR: 936 case Opcodes.ISHL: 937 case Opcodes.ISHR: 938 case Opcodes.IUSHR: 939 case Opcodes.L2I: 940 case Opcodes.D2I: 941 case Opcodes.FCMPL: 942 case Opcodes.FCMPG: 943 pop(2); 944 push(INTEGER); 945 break; 946 case Opcodes.LADD: 947 case Opcodes.LSUB: 948 case Opcodes.LMUL: 949 case Opcodes.LDIV: 950 case Opcodes.LREM: 951 case Opcodes.LAND: 952 case Opcodes.LOR: 953 case Opcodes.LXOR: 954 pop(4); 955 push(LONG); 956 push(TOP); 957 break; 958 case Opcodes.FALOAD: 959 case Opcodes.FADD: 960 case Opcodes.FSUB: 961 case Opcodes.FMUL: 962 case Opcodes.FDIV: 963 case Opcodes.FREM: 964 case Opcodes.L2F: 965 case Opcodes.D2F: 966 pop(2); 967 push(FLOAT); 968 break; 969 case Opcodes.DADD: 970 case Opcodes.DSUB: 971 case Opcodes.DMUL: 972 case Opcodes.DDIV: 973 case Opcodes.DREM: 974 pop(4); 975 push(DOUBLE); 976 push(TOP); 977 break; 978 case Opcodes.LSHL: 979 case Opcodes.LSHR: 980 case Opcodes.LUSHR: 981 pop(3); 982 push(LONG); 983 push(TOP); 984 break; 985 case Opcodes.IINC: 986 setLocal(arg, INTEGER); 987 break; 988 case Opcodes.I2L: 989 case Opcodes.F2L: 990 pop(1); 991 push(LONG); 992 push(TOP); 993 break; 994 case Opcodes.I2F: 995 pop(1); 996 push(FLOAT); 997 break; 998 case Opcodes.I2D: 999 case Opcodes.F2D: 1000 pop(1); 1001 push(DOUBLE); 1002 push(TOP); 1003 break; 1004 case Opcodes.F2I: 1005 case Opcodes.ARRAYLENGTH: 1006 case Opcodes.INSTANCEOF: 1007 pop(1); 1008 push(INTEGER); 1009 break; 1010 case Opcodes.LCMP: 1011 case Opcodes.DCMPL: 1012 case Opcodes.DCMPG: 1013 pop(4); 1014 push(INTEGER); 1015 break; 1016 case Opcodes.JSR: 1017 case Opcodes.RET: 1018 throw new IllegalArgumentException("JSR/RET are not supported with computeFrames option"); 1019 case Opcodes.GETSTATIC: 1020 push(symbolTable, argSymbol.value); 1021 break; 1022 case Opcodes.PUTSTATIC: 1023 pop(argSymbol.value); 1024 break; 1025 case Opcodes.GETFIELD: 1026 pop(1); 1027 push(symbolTable, argSymbol.value); 1028 break; 1029 case Opcodes.PUTFIELD: 1030 pop(argSymbol.value); 1031 pop(); 1032 break; 1033 case Opcodes.INVOKEVIRTUAL: 1034 case Opcodes.INVOKESPECIAL: 1035 case Opcodes.INVOKESTATIC: 1036 case Opcodes.INVOKEINTERFACE: 1037 pop(argSymbol.value); 1038 if (opcode != Opcodes.INVOKESTATIC) { 1039 abstractType1 = pop(); 1040 if (opcode == Opcodes.INVOKESPECIAL && argSymbol.name.charAt(0) == '<') { 1041 addInitializedType(abstractType1); 1042 } 1043 } 1044 push(symbolTable, argSymbol.value); 1045 break; 1046 case Opcodes.INVOKEDYNAMIC: 1047 pop(argSymbol.value); 1048 push(symbolTable, argSymbol.value); 1049 break; 1050 case Opcodes.NEW: 1051 push(UNINITIALIZED_KIND | symbolTable.addUninitializedType(argSymbol.value, arg)); 1052 break; 1053 case Opcodes.NEWARRAY: 1054 pop(); 1055 switch (arg) { 1056 case Opcodes.T_BOOLEAN: 1057 push(ARRAY_OF | BOOLEAN); 1058 break; 1059 case Opcodes.T_CHAR: 1060 push(ARRAY_OF | CHAR); 1061 break; 1062 case Opcodes.T_BYTE: 1063 push(ARRAY_OF | BYTE); 1064 break; 1065 case Opcodes.T_SHORT: 1066 push(ARRAY_OF | SHORT); 1067 break; 1068 case Opcodes.T_INT: 1069 push(ARRAY_OF | INTEGER); 1070 break; 1071 case Opcodes.T_FLOAT: 1072 push(ARRAY_OF | FLOAT); 1073 break; 1074 case Opcodes.T_DOUBLE: 1075 push(ARRAY_OF | DOUBLE); 1076 break; 1077 case Opcodes.T_LONG: 1078 push(ARRAY_OF | LONG); 1079 break; 1080 default: 1081 throw new IllegalArgumentException(); 1082 } 1083 break; 1084 case Opcodes.ANEWARRAY: 1085 String arrayElementType = argSymbol.value; 1086 pop(); 1087 if (arrayElementType.charAt(0) == '[') { 1088 push(symbolTable, '[' + arrayElementType); 1089 } else { 1090 push(ARRAY_OF | REFERENCE_KIND | symbolTable.addType(arrayElementType)); 1091 } 1092 break; 1093 case Opcodes.CHECKCAST: 1094 String castType = argSymbol.value; 1095 pop(); 1096 if (castType.charAt(0) == '[') { 1097 push(symbolTable, castType); 1098 } else { 1099 push(REFERENCE_KIND | symbolTable.addType(castType)); 1100 } 1101 break; 1102 case Opcodes.MULTIANEWARRAY: 1103 pop(arg); 1104 push(symbolTable, argSymbol.value); 1105 break; 1106 default: 1107 throw new IllegalArgumentException(); 1108 } 1109 } 1110 1111 // ----------------------------------------------------------------------------------------------- 1112 // Frame merging methods, used in the second step of the stack map frame computation algorithm 1113 // ----------------------------------------------------------------------------------------------- 1114 1115 /** 1116 * Computes the concrete output type corresponding to a given abstract output type. 1117 * 1118 * @param abstractOutputType an abstract output type. 1119 * @param numStack the size of the input stack, used to resolve abstract output types of 1120 * STACK_KIND kind. 1121 * @return the concrete output type corresponding to 'abstractOutputType'. 1122 */ getConcreteOutputType(final int abstractOutputType, final int numStack)1123 private int getConcreteOutputType(final int abstractOutputType, final int numStack) { 1124 int dim = abstractOutputType & DIM_MASK; 1125 int kind = abstractOutputType & KIND_MASK; 1126 if (kind == LOCAL_KIND) { 1127 // By definition, a LOCAL_KIND type designates the concrete type of a local variable at 1128 // the beginning of the basic block corresponding to this frame (which is known when 1129 // this method is called, but was not when the abstract type was computed). 1130 int concreteOutputType = dim + inputLocals[abstractOutputType & VALUE_MASK]; 1131 if ((abstractOutputType & TOP_IF_LONG_OR_DOUBLE_FLAG) != 0 1132 && (concreteOutputType == LONG || concreteOutputType == DOUBLE)) { 1133 concreteOutputType = TOP; 1134 } 1135 return concreteOutputType; 1136 } else if (kind == STACK_KIND) { 1137 // By definition, a STACK_KIND type designates the concrete type of a local variable at 1138 // the beginning of the basic block corresponding to this frame (which is known when 1139 // this method is called, but was not when the abstract type was computed). 1140 int concreteOutputType = dim + inputStack[numStack - (abstractOutputType & VALUE_MASK)]; 1141 if ((abstractOutputType & TOP_IF_LONG_OR_DOUBLE_FLAG) != 0 1142 && (concreteOutputType == LONG || concreteOutputType == DOUBLE)) { 1143 concreteOutputType = TOP; 1144 } 1145 return concreteOutputType; 1146 } else { 1147 return abstractOutputType; 1148 } 1149 } 1150 1151 /** 1152 * Merges the input frame of the given {@link Frame} with the input and output frames of this 1153 * {@link Frame}. Returns {@literal true} if the given frame has been changed by this operation 1154 * (the input and output frames of this {@link Frame} are never changed). 1155 * 1156 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 1157 * @param dstFrame the {@link Frame} whose input frame must be updated. This should be the frame 1158 * of a successor, in the control flow graph, of the basic block corresponding to this frame. 1159 * @param catchTypeIndex if 'frame' corresponds to an exception handler basic block, the type 1160 * table index of the caught exception type, otherwise 0. 1161 * @return {@literal true} if the input frame of 'frame' has been changed by this operation. 1162 */ merge( final SymbolTable symbolTable, final Frame dstFrame, final int catchTypeIndex)1163 final boolean merge( 1164 final SymbolTable symbolTable, final Frame dstFrame, final int catchTypeIndex) { 1165 boolean frameChanged = false; 1166 1167 // Compute the concrete types of the local variables at the end of the basic block corresponding 1168 // to this frame, by resolving its abstract output types, and merge these concrete types with 1169 // those of the local variables in the input frame of dstFrame. 1170 int numLocal = inputLocals.length; 1171 int numStack = inputStack.length; 1172 if (dstFrame.inputLocals == null) { 1173 dstFrame.inputLocals = new int[numLocal]; 1174 frameChanged = true; 1175 } 1176 for (int i = 0; i < numLocal; ++i) { 1177 int concreteOutputType; 1178 if (outputLocals != null && i < outputLocals.length) { 1179 int abstractOutputType = outputLocals[i]; 1180 if (abstractOutputType == 0) { 1181 // If the local variable has never been assigned in this basic block, it is equal to its 1182 // value at the beginning of the block. 1183 concreteOutputType = inputLocals[i]; 1184 } else { 1185 concreteOutputType = getConcreteOutputType(abstractOutputType, numStack); 1186 } 1187 } else { 1188 // If the local variable has never been assigned in this basic block, it is equal to its 1189 // value at the beginning of the block. 1190 concreteOutputType = inputLocals[i]; 1191 } 1192 // concreteOutputType might be an uninitialized type from the input locals or from the input 1193 // stack. However, if a constructor has been called for this class type in the basic block, 1194 // then this type is no longer uninitialized at the end of basic block. 1195 if (initializations != null) { 1196 concreteOutputType = getInitializedType(symbolTable, concreteOutputType); 1197 } 1198 frameChanged |= merge(symbolTable, concreteOutputType, dstFrame.inputLocals, i); 1199 } 1200 1201 // If dstFrame is an exception handler block, it can be reached from any instruction of the 1202 // basic block corresponding to this frame, in particular from the first one. Therefore, the 1203 // input locals of dstFrame should be compatible (i.e. merged) with the input locals of this 1204 // frame (and the input stack of dstFrame should be compatible, i.e. merged, with a one 1205 // element stack containing the caught exception type). 1206 if (catchTypeIndex > 0) { 1207 for (int i = 0; i < numLocal; ++i) { 1208 frameChanged |= merge(symbolTable, inputLocals[i], dstFrame.inputLocals, i); 1209 } 1210 if (dstFrame.inputStack == null) { 1211 dstFrame.inputStack = new int[1]; 1212 frameChanged = true; 1213 } 1214 frameChanged |= merge(symbolTable, catchTypeIndex, dstFrame.inputStack, 0); 1215 return frameChanged; 1216 } 1217 1218 // Compute the concrete types of the stack operands at the end of the basic block corresponding 1219 // to this frame, by resolving its abstract output types, and merge these concrete types with 1220 // those of the stack operands in the input frame of dstFrame. 1221 int numInputStack = inputStack.length + outputStackStart; 1222 if (dstFrame.inputStack == null) { 1223 dstFrame.inputStack = new int[numInputStack + outputStackTop]; 1224 frameChanged = true; 1225 } 1226 // First, do this for the stack operands that have not been popped in the basic block 1227 // corresponding to this frame, and which are therefore equal to their value in the input 1228 // frame (except for uninitialized types, which may have been initialized). 1229 for (int i = 0; i < numInputStack; ++i) { 1230 int concreteOutputType = inputStack[i]; 1231 if (initializations != null) { 1232 concreteOutputType = getInitializedType(symbolTable, concreteOutputType); 1233 } 1234 frameChanged |= merge(symbolTable, concreteOutputType, dstFrame.inputStack, i); 1235 } 1236 // Then, do this for the stack operands that have pushed in the basic block (this code is the 1237 // same as the one above for local variables). 1238 for (int i = 0; i < outputStackTop; ++i) { 1239 int abstractOutputType = outputStack[i]; 1240 int concreteOutputType = getConcreteOutputType(abstractOutputType, numStack); 1241 if (initializations != null) { 1242 concreteOutputType = getInitializedType(symbolTable, concreteOutputType); 1243 } 1244 frameChanged |= 1245 merge(symbolTable, concreteOutputType, dstFrame.inputStack, numInputStack + i); 1246 } 1247 return frameChanged; 1248 } 1249 1250 /** 1251 * Merges the type at the given index in the given abstract type array with the given type. 1252 * Returns {@literal true} if the type array has been modified by this operation. 1253 * 1254 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 1255 * @param sourceType the abstract type with which the abstract type array element must be merged. 1256 * This type should be of {@link #CONSTANT_KIND}, {@link #REFERENCE_KIND} or {@link 1257 * #UNINITIALIZED_KIND} kind, with positive or {@literal null} array dimensions. 1258 * @param dstTypes an array of abstract types. These types should be of {@link #CONSTANT_KIND}, 1259 * {@link #REFERENCE_KIND} or {@link #UNINITIALIZED_KIND} kind, with positive or {@literal 1260 * null} array dimensions. 1261 * @param dstIndex the index of the type that must be merged in dstTypes. 1262 * @return {@literal true} if the type array has been modified by this operation. 1263 */ merge( final SymbolTable symbolTable, final int sourceType, final int[] dstTypes, final int dstIndex)1264 private static boolean merge( 1265 final SymbolTable symbolTable, 1266 final int sourceType, 1267 final int[] dstTypes, 1268 final int dstIndex) { 1269 int dstType = dstTypes[dstIndex]; 1270 if (dstType == sourceType) { 1271 // If the types are equal, merge(sourceType, dstType) = dstType, so there is no change. 1272 return false; 1273 } 1274 int srcType = sourceType; 1275 if ((sourceType & ~DIM_MASK) == NULL) { 1276 if (dstType == NULL) { 1277 return false; 1278 } 1279 srcType = NULL; 1280 } 1281 if (dstType == 0) { 1282 // If dstTypes[dstIndex] has never been assigned, merge(srcType, dstType) = srcType. 1283 dstTypes[dstIndex] = srcType; 1284 return true; 1285 } 1286 int mergedType; 1287 if ((dstType & DIM_MASK) != 0 || (dstType & KIND_MASK) == REFERENCE_KIND) { 1288 // If dstType is a reference type of any array dimension. 1289 if (srcType == NULL) { 1290 // If srcType is the NULL type, merge(srcType, dstType) = dstType, so there is no change. 1291 return false; 1292 } else if ((srcType & (DIM_MASK | KIND_MASK)) == (dstType & (DIM_MASK | KIND_MASK))) { 1293 // If srcType has the same array dimension and the same kind as dstType. 1294 if ((dstType & KIND_MASK) == REFERENCE_KIND) { 1295 // If srcType and dstType are reference types with the same array dimension, 1296 // merge(srcType, dstType) = dim(srcType) | common super class of srcType and dstType. 1297 mergedType = 1298 (srcType & DIM_MASK) 1299 | REFERENCE_KIND 1300 | symbolTable.addMergedType(srcType & VALUE_MASK, dstType & VALUE_MASK); 1301 } else { 1302 // If srcType and dstType are array types of equal dimension but different element types, 1303 // merge(srcType, dstType) = dim(srcType) - 1 | java/lang/Object. 1304 int mergedDim = ELEMENT_OF + (srcType & DIM_MASK); 1305 mergedType = mergedDim | REFERENCE_KIND | symbolTable.addType("java/lang/Object"); 1306 } 1307 } else if ((srcType & DIM_MASK) != 0 || (srcType & KIND_MASK) == REFERENCE_KIND) { 1308 // If srcType is any other reference or array type, 1309 // merge(srcType, dstType) = min(srcDdim, dstDim) | java/lang/Object 1310 // where srcDim is the array dimension of srcType, minus 1 if srcType is an array type 1311 // with a non reference element type (and similarly for dstDim). 1312 int srcDim = srcType & DIM_MASK; 1313 if (srcDim != 0 && (srcType & KIND_MASK) != REFERENCE_KIND) { 1314 srcDim = ELEMENT_OF + srcDim; 1315 } 1316 int dstDim = dstType & DIM_MASK; 1317 if (dstDim != 0 && (dstType & KIND_MASK) != REFERENCE_KIND) { 1318 dstDim = ELEMENT_OF + dstDim; 1319 } 1320 mergedType = 1321 Math.min(srcDim, dstDim) | REFERENCE_KIND | symbolTable.addType("java/lang/Object"); 1322 } else { 1323 // If srcType is any other type, merge(srcType, dstType) = TOP. 1324 mergedType = TOP; 1325 } 1326 } else if (dstType == NULL) { 1327 // If dstType is the NULL type, merge(srcType, dstType) = srcType, or TOP if srcType is not a 1328 // an array type or a reference type. 1329 mergedType = 1330 (srcType & DIM_MASK) != 0 || (srcType & KIND_MASK) == REFERENCE_KIND ? srcType : TOP; 1331 } else { 1332 // If dstType is any other type, merge(srcType, dstType) = TOP whatever srcType. 1333 mergedType = TOP; 1334 } 1335 if (mergedType != dstType) { 1336 dstTypes[dstIndex] = mergedType; 1337 return true; 1338 } 1339 return false; 1340 } 1341 1342 // ----------------------------------------------------------------------------------------------- 1343 // Frame output methods, to generate StackMapFrame attributes 1344 // ----------------------------------------------------------------------------------------------- 1345 1346 /** 1347 * Makes the given {@link MethodWriter} visit the input frame of this {@link Frame}. The visit is 1348 * done with the {@link MethodWriter#visitFrameStart}, {@link MethodWriter#visitAbstractType} and 1349 * {@link MethodWriter#visitFrameEnd} methods. 1350 * 1351 * @param methodWriter the {@link MethodWriter} that should visit the input frame of this {@link 1352 * Frame}. 1353 */ accept(final MethodWriter methodWriter)1354 final void accept(final MethodWriter methodWriter) { 1355 // Compute the number of locals, ignoring TOP types that are just after a LONG or a DOUBLE, and 1356 // all trailing TOP types. 1357 int[] localTypes = inputLocals; 1358 int numLocal = 0; 1359 int numTrailingTop = 0; 1360 int i = 0; 1361 while (i < localTypes.length) { 1362 int localType = localTypes[i]; 1363 i += (localType == LONG || localType == DOUBLE) ? 2 : 1; 1364 if (localType == TOP) { 1365 numTrailingTop++; 1366 } else { 1367 numLocal += numTrailingTop + 1; 1368 numTrailingTop = 0; 1369 } 1370 } 1371 // Compute the stack size, ignoring TOP types that are just after a LONG or a DOUBLE. 1372 int[] stackTypes = inputStack; 1373 int numStack = 0; 1374 i = 0; 1375 while (i < stackTypes.length) { 1376 int stackType = stackTypes[i]; 1377 i += (stackType == LONG || stackType == DOUBLE) ? 2 : 1; 1378 numStack++; 1379 } 1380 // Visit the frame and its content. 1381 int frameIndex = methodWriter.visitFrameStart(owner.bytecodeOffset, numLocal, numStack); 1382 i = 0; 1383 while (numLocal-- > 0) { 1384 int localType = localTypes[i]; 1385 i += (localType == LONG || localType == DOUBLE) ? 2 : 1; 1386 methodWriter.visitAbstractType(frameIndex++, localType); 1387 } 1388 i = 0; 1389 while (numStack-- > 0) { 1390 int stackType = stackTypes[i]; 1391 i += (stackType == LONG || stackType == DOUBLE) ? 2 : 1; 1392 methodWriter.visitAbstractType(frameIndex++, stackType); 1393 } 1394 methodWriter.visitFrameEnd(); 1395 } 1396 1397 /** 1398 * Put the given abstract type in the given ByteVector, using the JVMS verification_type_info 1399 * format used in StackMapTable attributes. 1400 * 1401 * @param symbolTable the type table to use to lookup and store type {@link Symbol}. 1402 * @param abstractType an abstract type, restricted to {@link Frame#CONSTANT_KIND}, {@link 1403 * Frame#REFERENCE_KIND} or {@link Frame#UNINITIALIZED_KIND} types. 1404 * @param output where the abstract type must be put. 1405 * @see <a href="https://docs.oracle.com/javase/specs/jvms/se9/html/jvms-4.html#jvms-4.7.4">JVMS 1406 * 4.7.4</a> 1407 */ putAbstractType( final SymbolTable symbolTable, final int abstractType, final ByteVector output)1408 static void putAbstractType( 1409 final SymbolTable symbolTable, final int abstractType, final ByteVector output) { 1410 int arrayDimensions = (abstractType & Frame.DIM_MASK) >> DIM_SHIFT; 1411 if (arrayDimensions == 0) { 1412 int typeValue = abstractType & VALUE_MASK; 1413 switch (abstractType & KIND_MASK) { 1414 case CONSTANT_KIND: 1415 output.putByte(typeValue); 1416 break; 1417 case REFERENCE_KIND: 1418 output 1419 .putByte(ITEM_OBJECT) 1420 .putShort(symbolTable.addConstantClass(symbolTable.getType(typeValue).value).index); 1421 break; 1422 case UNINITIALIZED_KIND: 1423 output.putByte(ITEM_UNINITIALIZED).putShort((int) symbolTable.getType(typeValue).data); 1424 break; 1425 default: 1426 throw new AssertionError(); 1427 } 1428 } else { 1429 // Case of an array type, we need to build its descriptor first. 1430 StringBuilder typeDescriptor = new StringBuilder(); 1431 while (arrayDimensions-- > 0) { 1432 typeDescriptor.append('['); 1433 } 1434 if ((abstractType & KIND_MASK) == REFERENCE_KIND) { 1435 typeDescriptor 1436 .append('L') 1437 .append(symbolTable.getType(abstractType & VALUE_MASK).value) 1438 .append(';'); 1439 } else { 1440 switch (abstractType & VALUE_MASK) { 1441 case Frame.ITEM_ASM_BOOLEAN: 1442 typeDescriptor.append('Z'); 1443 break; 1444 case Frame.ITEM_ASM_BYTE: 1445 typeDescriptor.append('B'); 1446 break; 1447 case Frame.ITEM_ASM_CHAR: 1448 typeDescriptor.append('C'); 1449 break; 1450 case Frame.ITEM_ASM_SHORT: 1451 typeDescriptor.append('S'); 1452 break; 1453 case Frame.ITEM_INTEGER: 1454 typeDescriptor.append('I'); 1455 break; 1456 case Frame.ITEM_FLOAT: 1457 typeDescriptor.append('F'); 1458 break; 1459 case Frame.ITEM_LONG: 1460 typeDescriptor.append('J'); 1461 break; 1462 case Frame.ITEM_DOUBLE: 1463 typeDescriptor.append('D'); 1464 break; 1465 default: 1466 throw new AssertionError(); 1467 } 1468 } 1469 output 1470 .putByte(ITEM_OBJECT) 1471 .putShort(symbolTable.addConstantClass(typeDescriptor.toString()).index); 1472 } 1473 } 1474 } 1475