1/*** 2 * ASM: a very small and fast Java bytecode manipulation framework 3 * Copyright (c) 2000-2007 INRIA, France Telecom 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. Neither the name of the copyright holders nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 28 * THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30package org.mockito.asm; 31 32/** 33 * A label represents a position in the bytecode of a method. Labels are used 34 * for jump, goto, and switch instructions, and for try catch blocks. 35 * 36 * @author Eric Bruneton 37 */ 38public class Label { 39 40 /** 41 * Indicates if this label is only used for debug attributes. Such a label 42 * is not the start of a basic block, the target of a jump instruction, or 43 * an exception handler. It can be safely ignored in control flow graph 44 * analysis algorithms (for optimization purposes). 45 */ 46 static final int DEBUG = 1; 47 48 /** 49 * Indicates if the position of this label is known. 50 */ 51 static final int RESOLVED = 2; 52 53 /** 54 * Indicates if this label has been updated, after instruction resizing. 55 */ 56 static final int RESIZED = 4; 57 58 /** 59 * Indicates if this basic block has been pushed in the basic block stack. 60 * See {@link MethodWriter#visitMaxs visitMaxs}. 61 */ 62 static final int PUSHED = 8; 63 64 /** 65 * Indicates if this label is the target of a jump instruction, or the start 66 * of an exception handler. 67 */ 68 static final int TARGET = 16; 69 70 /** 71 * Indicates if a stack map frame must be stored for this label. 72 */ 73 static final int STORE = 32; 74 75 /** 76 * Indicates if this label corresponds to a reachable basic block. 77 */ 78 static final int REACHABLE = 64; 79 80 /** 81 * Indicates if this basic block ends with a JSR instruction. 82 */ 83 static final int JSR = 128; 84 85 /** 86 * Indicates if this basic block ends with a RET instruction. 87 */ 88 static final int RET = 256; 89 90 /** 91 * Indicates if this basic block is the start of a subroutine. 92 */ 93 static final int SUBROUTINE = 512; 94 95 /** 96 * Indicates if this subroutine basic block has been visited. 97 */ 98 static final int VISITED = 1024; 99 100 /** 101 * Field used to associate user information to a label. Warning: this field 102 * is used by the ASM tree package. In order to use it with the ASM tree 103 * package you must override the {@link 104 * org.mockito.asm.tree.MethodNode#getLabelNode} method. 105 */ 106 public Object info; 107 108 /** 109 * Flags that indicate the status of this label. 110 * 111 * @see #DEBUG 112 * @see #RESOLVED 113 * @see #RESIZED 114 * @see #PUSHED 115 * @see #TARGET 116 * @see #STORE 117 * @see #REACHABLE 118 * @see #JSR 119 * @see #RET 120 */ 121 int status; 122 123 /** 124 * The line number corresponding to this label, if known. 125 */ 126 int line; 127 128 /** 129 * The position of this label in the code, if known. 130 */ 131 int position; 132 133 /** 134 * Number of forward references to this label, times two. 135 */ 136 private int referenceCount; 137 138 /** 139 * Informations about forward references. Each forward reference is 140 * described by two consecutive integers in this array: the first one is the 141 * position of the first byte of the bytecode instruction that contains the 142 * forward reference, while the second is the position of the first byte of 143 * the forward reference itself. In fact the sign of the first integer 144 * indicates if this reference uses 2 or 4 bytes, and its absolute value 145 * gives the position of the bytecode instruction. This array is also used 146 * as a bitset to store the subroutines to which a basic block belongs. This 147 * information is needed in {@linked MethodWriter#visitMaxs}, after all 148 * forward references have been resolved. Hence the same array can be used 149 * for both purposes without problems. 150 */ 151 private int[] srcAndRefPositions; 152 153 // ------------------------------------------------------------------------ 154 155 /* 156 * Fields for the control flow and data flow graph analysis algorithms (used 157 * to compute the maximum stack size or the stack map frames). A control 158 * flow graph contains one node per "basic block", and one edge per "jump" 159 * from one basic block to another. Each node (i.e., each basic block) is 160 * represented by the Label object that corresponds to the first instruction 161 * of this basic block. Each node also stores the list of its successors in 162 * the graph, as a linked list of Edge objects. 163 * 164 * The control flow analysis algorithms used to compute the maximum stack 165 * size or the stack map frames are similar and use two steps. The first 166 * step, during the visit of each instruction, builds information about the 167 * state of the local variables and the operand stack at the end of each 168 * basic block, called the "output frame", <i>relatively</i> to the frame 169 * state at the beginning of the basic block, which is called the "input 170 * frame", and which is <i>unknown</i> during this step. The second step, 171 * in {@link MethodWriter#visitMaxs}, is a fix point algorithm that 172 * computes information about the input frame of each basic block, from the 173 * input state of the first basic block (known from the method signature), 174 * and by the using the previously computed relative output frames. 175 * 176 * The algorithm used to compute the maximum stack size only computes the 177 * relative output and absolute input stack heights, while the algorithm 178 * used to compute stack map frames computes relative output frames and 179 * absolute input frames. 180 */ 181 182 /** 183 * Start of the output stack relatively to the input stack. The exact 184 * semantics of this field depends on the algorithm that is used. 185 * 186 * When only the maximum stack size is computed, this field is the number of 187 * elements in the input stack. 188 * 189 * When the stack map frames are completely computed, this field is the 190 * offset of the first output stack element relatively to the top of the 191 * input stack. This offset is always negative or null. A null offset means 192 * that the output stack must be appended to the input stack. A -n offset 193 * means that the first n output stack elements must replace the top n input 194 * stack elements, and that the other elements must be appended to the input 195 * stack. 196 */ 197 int inputStackTop; 198 199 /** 200 * Maximum height reached by the output stack, relatively to the top of the 201 * input stack. This maximum is always positive or null. 202 */ 203 int outputStackMax; 204 205 /** 206 * Information about the input and output stack map frames of this basic 207 * block. This field is only used when {@link ClassWriter#COMPUTE_FRAMES} 208 * option is used. 209 */ 210 Frame frame; 211 212 /** 213 * The successor of this label, in the order they are visited. This linked 214 * list does not include labels used for debug info only. If 215 * {@link ClassWriter#COMPUTE_FRAMES} option is used then, in addition, it 216 * does not contain successive labels that denote the same bytecode position 217 * (in this case only the first label appears in this list). 218 */ 219 Label successor; 220 221 /** 222 * The successors of this node in the control flow graph. These successors 223 * are stored in a linked list of {@link Edge Edge} objects, linked to each 224 * other by their {@link Edge#next} field. 225 */ 226 Edge successors; 227 228 /** 229 * The next basic block in the basic block stack. This stack is used in the 230 * main loop of the fix point algorithm used in the second step of the 231 * control flow analysis algorithms. 232 * 233 * @see MethodWriter#visitMaxs 234 */ 235 Label next; 236 237 // ------------------------------------------------------------------------ 238 // Constructor 239 // ------------------------------------------------------------------------ 240 241 /** 242 * Constructs a new label. 243 */ 244 public Label() { 245 } 246 247 // ------------------------------------------------------------------------ 248 // Methods to compute offsets and to manage forward references 249 // ------------------------------------------------------------------------ 250 251 /** 252 * Returns the offset corresponding to this label. This offset is computed 253 * from the start of the method's bytecode. <i>This method is intended for 254 * {@link Attribute} sub classes, and is normally not needed by class 255 * generators or adapters.</i> 256 * 257 * @return the offset corresponding to this label. 258 * @throws IllegalStateException if this label is not resolved yet. 259 */ 260 public int getOffset() { 261 if ((status & RESOLVED) == 0) { 262 throw new IllegalStateException("Label offset position has not been resolved yet"); 263 } 264 return position; 265 } 266 267 /** 268 * Puts a reference to this label in the bytecode of a method. If the 269 * position of the label is known, the offset is computed and written 270 * directly. Otherwise, a null offset is written and a new forward reference 271 * is declared for this label. 272 * 273 * @param owner the code writer that calls this method. 274 * @param out the bytecode of the method. 275 * @param source the position of first byte of the bytecode instruction that 276 * contains this label. 277 * @param wideOffset <tt>true</tt> if the reference must be stored in 4 278 * bytes, or <tt>false</tt> if it must be stored with 2 bytes. 279 * @throws IllegalArgumentException if this label has not been created by 280 * the given code writer. 281 */ 282 void put( 283 final MethodWriter owner, 284 final ByteVector out, 285 final int source, 286 final boolean wideOffset) 287 { 288 if ((status & RESOLVED) == 0) { 289 if (wideOffset) { 290 addReference(-1 - source, out.length); 291 out.putInt(-1); 292 } else { 293 addReference(source, out.length); 294 out.putShort(-1); 295 } 296 } else { 297 if (wideOffset) { 298 out.putInt(position - source); 299 } else { 300 out.putShort(position - source); 301 } 302 } 303 } 304 305 /** 306 * Adds a forward reference to this label. This method must be called only 307 * for a true forward reference, i.e. only if this label is not resolved 308 * yet. For backward references, the offset of the reference can be, and 309 * must be, computed and stored directly. 310 * 311 * @param sourcePosition the position of the referencing instruction. This 312 * position will be used to compute the offset of this forward 313 * reference. 314 * @param referencePosition the position where the offset for this forward 315 * reference must be stored. 316 */ 317 private void addReference( 318 final int sourcePosition, 319 final int referencePosition) 320 { 321 if (srcAndRefPositions == null) { 322 srcAndRefPositions = new int[6]; 323 } 324 if (referenceCount >= srcAndRefPositions.length) { 325 int[] a = new int[srcAndRefPositions.length + 6]; 326 System.arraycopy(srcAndRefPositions, 327 0, 328 a, 329 0, 330 srcAndRefPositions.length); 331 srcAndRefPositions = a; 332 } 333 srcAndRefPositions[referenceCount++] = sourcePosition; 334 srcAndRefPositions[referenceCount++] = referencePosition; 335 } 336 337 /** 338 * Resolves all forward references to this label. This method must be called 339 * when this label is added to the bytecode of the method, i.e. when its 340 * position becomes known. This method fills in the blanks that where left 341 * in the bytecode by each forward reference previously added to this label. 342 * 343 * @param owner the code writer that calls this method. 344 * @param position the position of this label in the bytecode. 345 * @param data the bytecode of the method. 346 * @return <tt>true</tt> if a blank that was left for this label was to 347 * small to store the offset. In such a case the corresponding jump 348 * instruction is replaced with a pseudo instruction (using unused 349 * opcodes) using an unsigned two bytes offset. These pseudo 350 * instructions will need to be replaced with true instructions with 351 * wider offsets (4 bytes instead of 2). This is done in 352 * {@link MethodWriter#resizeInstructions}. 353 * @throws IllegalArgumentException if this label has already been resolved, 354 * or if it has not been created by the given code writer. 355 */ 356 boolean resolve( 357 final MethodWriter owner, 358 final int position, 359 final byte[] data) 360 { 361 boolean needUpdate = false; 362 this.status |= RESOLVED; 363 this.position = position; 364 int i = 0; 365 while (i < referenceCount) { 366 int source = srcAndRefPositions[i++]; 367 int reference = srcAndRefPositions[i++]; 368 int offset; 369 if (source >= 0) { 370 offset = position - source; 371 if (offset < Short.MIN_VALUE || offset > Short.MAX_VALUE) { 372 /* 373 * changes the opcode of the jump instruction, in order to 374 * be able to find it later (see resizeInstructions in 375 * MethodWriter). These temporary opcodes are similar to 376 * jump instruction opcodes, except that the 2 bytes offset 377 * is unsigned (and can therefore represent values from 0 to 378 * 65535, which is sufficient since the size of a method is 379 * limited to 65535 bytes). 380 */ 381 int opcode = data[reference - 1] & 0xFF; 382 if (opcode <= Opcodes.JSR) { 383 // changes IFEQ ... JSR to opcodes 202 to 217 384 data[reference - 1] = (byte) (opcode + 49); 385 } else { 386 // changes IFNULL and IFNONNULL to opcodes 218 and 219 387 data[reference - 1] = (byte) (opcode + 20); 388 } 389 needUpdate = true; 390 } 391 data[reference++] = (byte) (offset >>> 8); 392 data[reference] = (byte) offset; 393 } else { 394 offset = position + source + 1; 395 data[reference++] = (byte) (offset >>> 24); 396 data[reference++] = (byte) (offset >>> 16); 397 data[reference++] = (byte) (offset >>> 8); 398 data[reference] = (byte) offset; 399 } 400 } 401 return needUpdate; 402 } 403 404 /** 405 * Returns the first label of the series to which this label belongs. For an 406 * isolated label or for the first label in a series of successive labels, 407 * this method returns the label itself. For other labels it returns the 408 * first label of the series. 409 * 410 * @return the first label of the series to which this label belongs. 411 */ 412 Label getFirst() { 413 return !ClassReader.FRAMES || frame == null ? this : frame.owner; 414 } 415 416 // ------------------------------------------------------------------------ 417 // Methods related to subroutines 418 // ------------------------------------------------------------------------ 419 420 /** 421 * Returns true is this basic block belongs to the given subroutine. 422 * 423 * @param id a subroutine id. 424 * @return true is this basic block belongs to the given subroutine. 425 */ 426 boolean inSubroutine(final long id) { 427 if ((status & Label.VISITED) != 0) { 428 return (srcAndRefPositions[(int) (id >>> 32)] & (int) id) != 0; 429 } 430 return false; 431 } 432 433 /** 434 * Returns true if this basic block and the given one belong to a common 435 * subroutine. 436 * 437 * @param block another basic block. 438 * @return true if this basic block and the given one belong to a common 439 * subroutine. 440 */ 441 boolean inSameSubroutine(final Label block) { 442 for (int i = 0; i < srcAndRefPositions.length; ++i) { 443 if ((srcAndRefPositions[i] & block.srcAndRefPositions[i]) != 0) { 444 return true; 445 } 446 } 447 return false; 448 } 449 450 /** 451 * Marks this basic block as belonging to the given subroutine. 452 * 453 * @param id a subroutine id. 454 * @param nbSubroutines the total number of subroutines in the method. 455 */ 456 void addToSubroutine(final long id, final int nbSubroutines) { 457 if ((status & VISITED) == 0) { 458 status |= VISITED; 459 srcAndRefPositions = new int[(nbSubroutines - 1) / 32 + 1]; 460 } 461 srcAndRefPositions[(int) (id >>> 32)] |= (int) id; 462 } 463 464 /** 465 * Finds the basic blocks that belong to a given subroutine, and marks these 466 * blocks as belonging to this subroutine. This recursive method follows the 467 * control flow graph to find all the blocks that are reachable from the 468 * current block WITHOUT following any JSR target. 469 * 470 * @param JSR a JSR block that jumps to this subroutine. If this JSR is not 471 * null it is added to the successor of the RET blocks found in the 472 * subroutine. 473 * @param id the id of this subroutine. 474 * @param nbSubroutines the total number of subroutines in the method. 475 */ 476 void visitSubroutine(final Label JSR, final long id, final int nbSubroutines) 477 { 478 if (JSR != null) { 479 if ((status & VISITED) != 0) { 480 return; 481 } 482 status |= VISITED; 483 // adds JSR to the successors of this block, if it is a RET block 484 if ((status & RET) != 0) { 485 if (!inSameSubroutine(JSR)) { 486 Edge e = new Edge(); 487 e.info = inputStackTop; 488 e.successor = JSR.successors.successor; 489 e.next = successors; 490 successors = e; 491 } 492 } 493 } else { 494 // if this block already belongs to subroutine 'id', returns 495 if (inSubroutine(id)) { 496 return; 497 } 498 // marks this block as belonging to subroutine 'id' 499 addToSubroutine(id, nbSubroutines); 500 } 501 // calls this method recursively on each successor, except JSR targets 502 Edge e = successors; 503 while (e != null) { 504 // if this block is a JSR block, then 'successors.next' leads 505 // to the JSR target (see {@link #visitJumpInsn}) and must therefore 506 // not be followed 507 if ((status & Label.JSR) == 0 || e != successors.next) { 508 e.successor.visitSubroutine(JSR, id, nbSubroutines); 509 } 510 e = e.next; 511 } 512 } 513 514 // ------------------------------------------------------------------------ 515 // Overriden Object methods 516 // ------------------------------------------------------------------------ 517 518 /** 519 * Returns a string representation of this label. 520 * 521 * @return a string representation of this label. 522 */ 523 public String toString() { 524 return "L" + System.identityHashCode(this); 525 } 526} 527