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