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