1 // ASM: a very small and fast Java bytecode manipulation framework 2 // Copyright (c) 2000-2011 INRIA, France Telecom 3 // All rights reserved. 4 // 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions 7 // are met: 8 // 1. Redistributions of source code must retain the above copyright 9 // notice, this list of conditions and the following disclaimer. 10 // 2. Redistributions in binary form must reproduce the above copyright 11 // notice, this list of conditions and the following disclaimer in the 12 // documentation and/or other materials provided with the distribution. 13 // 3. Neither the name of the copyright holders nor the names of its 14 // contributors may be used to endorse or promote products derived from 15 // this software without specific prior written permission. 16 // 17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 27 // THE POSSIBILITY OF SUCH DAMAGE. 28 package org.objectweb.asm.tree.analysis; 29 30 import java.util.ArrayList; 31 import java.util.HashMap; 32 import java.util.List; 33 import java.util.Map; 34 import org.objectweb.asm.Opcodes; 35 import org.objectweb.asm.Type; 36 import org.objectweb.asm.tree.AbstractInsnNode; 37 import org.objectweb.asm.tree.IincInsnNode; 38 import org.objectweb.asm.tree.InsnList; 39 import org.objectweb.asm.tree.JumpInsnNode; 40 import org.objectweb.asm.tree.LabelNode; 41 import org.objectweb.asm.tree.LookupSwitchInsnNode; 42 import org.objectweb.asm.tree.MethodNode; 43 import org.objectweb.asm.tree.TableSwitchInsnNode; 44 import org.objectweb.asm.tree.TryCatchBlockNode; 45 import org.objectweb.asm.tree.VarInsnNode; 46 47 /** 48 * A semantic bytecode analyzer. <i>This class does not fully check that JSR and RET instructions 49 * are valid.</i> 50 * 51 * @param <V> type of the {@link Value} used for the analysis. 52 * @author Eric Bruneton 53 */ 54 public class Analyzer<V extends Value> implements Opcodes { 55 56 /** The interpreter to use to symbolically interpret the bytecode instructions. */ 57 private final Interpreter<V> interpreter; 58 59 /** The instructions of the currently analyzed method. */ 60 private InsnList insnList; 61 62 /** The size of {@link #insnList}. */ 63 private int insnListSize; 64 65 /** The exception handlers of the currently analyzed method (one list per instruction index). */ 66 private List<TryCatchBlockNode>[] handlers; 67 68 /** The execution stack frames of the currently analyzed method (one per instruction index). */ 69 private Frame<V>[] frames; 70 71 /** The subroutines of the currently analyzed method (one per instruction index). */ 72 private Subroutine[] subroutines; 73 74 /** The instructions that remain to process (one boolean per instruction index). */ 75 private boolean[] inInstructionsToProcess; 76 77 /** The indices of the instructions that remain to process in the currently analyzed method. */ 78 private int[] instructionsToProcess; 79 80 /** The number of instructions that remain to process in the currently analyzed method. */ 81 private int numInstructionsToProcess; 82 83 /** 84 * Constructs a new {@link Analyzer}. 85 * 86 * @param interpreter the interpreter to use to symbolically interpret the bytecode instructions. 87 */ Analyzer(final Interpreter<V> interpreter)88 public Analyzer(final Interpreter<V> interpreter) { 89 this.interpreter = interpreter; 90 } 91 92 /** 93 * Analyzes the given method. 94 * 95 * @param owner the internal name of the class to which 'method' belongs (see {@link 96 * Type#getInternalName()}). 97 * @param method the method to be analyzed. The maxStack and maxLocals fields must have correct 98 * values. 99 * @return the symbolic state of the execution stack frame at each bytecode instruction of the 100 * method. The size of the returned array is equal to the number of instructions (and labels) 101 * of the method. A given frame is {@literal null} if and only if the corresponding 102 * instruction cannot be reached (dead code). 103 * @throws AnalyzerException if a problem occurs during the analysis. 104 */ 105 @SuppressWarnings("unchecked") analyze(final String owner, final MethodNode method)106 public Frame<V>[] analyze(final String owner, final MethodNode method) throws AnalyzerException { 107 if ((method.access & (ACC_ABSTRACT | ACC_NATIVE)) != 0) { 108 frames = (Frame<V>[]) new Frame<?>[0]; 109 return frames; 110 } 111 insnList = method.instructions; 112 insnListSize = insnList.size(); 113 handlers = (List<TryCatchBlockNode>[]) new List<?>[insnListSize]; 114 frames = (Frame<V>[]) new Frame<?>[insnListSize]; 115 subroutines = new Subroutine[insnListSize]; 116 inInstructionsToProcess = new boolean[insnListSize]; 117 instructionsToProcess = new int[insnListSize]; 118 numInstructionsToProcess = 0; 119 120 // For each exception handler, and each instruction within its range, record in 'handlers' the 121 // fact that execution can flow from this instruction to the exception handler. 122 for (int i = 0; i < method.tryCatchBlocks.size(); ++i) { 123 TryCatchBlockNode tryCatchBlock = method.tryCatchBlocks.get(i); 124 int startIndex = insnList.indexOf(tryCatchBlock.start); 125 int endIndex = insnList.indexOf(tryCatchBlock.end); 126 for (int j = startIndex; j <= endIndex; ++j) { 127 List<TryCatchBlockNode> insnHandlers = handlers[j]; 128 if (insnHandlers == null) { 129 insnHandlers = new ArrayList<>(); 130 handlers[j] = insnHandlers; 131 } 132 insnHandlers.add(tryCatchBlock); 133 } 134 } 135 136 // Finds the method's subroutines. 137 findSubroutines(method.maxLocals); 138 139 // Initializes the data structures for the control flow analysis. 140 Frame<V> currentFrame; 141 try { 142 currentFrame = computeInitialFrame(owner, method); 143 merge(0, currentFrame, null); 144 init(owner, method); 145 } catch (RuntimeException e) { 146 // DontCheck(IllegalCatch): can't be fixed, for backward compatibility. 147 throw new AnalyzerException(insnList.get(0), "Error at instruction 0: " + e.getMessage(), e); 148 } 149 150 // Control flow analysis. 151 while (numInstructionsToProcess > 0) { 152 // Get and remove one instruction from the list of instructions to process. 153 int insnIndex = instructionsToProcess[--numInstructionsToProcess]; 154 Frame<V> oldFrame = frames[insnIndex]; 155 Subroutine subroutine = subroutines[insnIndex]; 156 inInstructionsToProcess[insnIndex] = false; 157 158 // Simulate the execution of this instruction. 159 AbstractInsnNode insnNode = null; 160 try { 161 insnNode = method.instructions.get(insnIndex); 162 int insnOpcode = insnNode.getOpcode(); 163 int insnType = insnNode.getType(); 164 165 if (insnType == AbstractInsnNode.LABEL 166 || insnType == AbstractInsnNode.LINE 167 || insnType == AbstractInsnNode.FRAME) { 168 merge(insnIndex + 1, oldFrame, subroutine); 169 newControlFlowEdge(insnIndex, insnIndex + 1); 170 } else { 171 currentFrame.init(oldFrame).execute(insnNode, interpreter); 172 subroutine = subroutine == null ? null : new Subroutine(subroutine); 173 174 if (insnNode instanceof JumpInsnNode) { 175 JumpInsnNode jumpInsn = (JumpInsnNode) insnNode; 176 if (insnOpcode != GOTO && insnOpcode != JSR) { 177 currentFrame.initJumpTarget(insnOpcode, /* target = */ null); 178 merge(insnIndex + 1, currentFrame, subroutine); 179 newControlFlowEdge(insnIndex, insnIndex + 1); 180 } 181 int jumpInsnIndex = insnList.indexOf(jumpInsn.label); 182 currentFrame.initJumpTarget(insnOpcode, jumpInsn.label); 183 if (insnOpcode == JSR) { 184 merge( 185 jumpInsnIndex, 186 currentFrame, 187 new Subroutine(jumpInsn.label, method.maxLocals, jumpInsn)); 188 } else { 189 merge(jumpInsnIndex, currentFrame, subroutine); 190 } 191 newControlFlowEdge(insnIndex, jumpInsnIndex); 192 } else if (insnNode instanceof LookupSwitchInsnNode) { 193 LookupSwitchInsnNode lookupSwitchInsn = (LookupSwitchInsnNode) insnNode; 194 int targetInsnIndex = insnList.indexOf(lookupSwitchInsn.dflt); 195 currentFrame.initJumpTarget(insnOpcode, lookupSwitchInsn.dflt); 196 merge(targetInsnIndex, currentFrame, subroutine); 197 newControlFlowEdge(insnIndex, targetInsnIndex); 198 for (int i = 0; i < lookupSwitchInsn.labels.size(); ++i) { 199 LabelNode label = lookupSwitchInsn.labels.get(i); 200 targetInsnIndex = insnList.indexOf(label); 201 currentFrame.initJumpTarget(insnOpcode, label); 202 merge(targetInsnIndex, currentFrame, subroutine); 203 newControlFlowEdge(insnIndex, targetInsnIndex); 204 } 205 } else if (insnNode instanceof TableSwitchInsnNode) { 206 TableSwitchInsnNode tableSwitchInsn = (TableSwitchInsnNode) insnNode; 207 int targetInsnIndex = insnList.indexOf(tableSwitchInsn.dflt); 208 currentFrame.initJumpTarget(insnOpcode, tableSwitchInsn.dflt); 209 merge(targetInsnIndex, currentFrame, subroutine); 210 newControlFlowEdge(insnIndex, targetInsnIndex); 211 for (int i = 0; i < tableSwitchInsn.labels.size(); ++i) { 212 LabelNode label = tableSwitchInsn.labels.get(i); 213 currentFrame.initJumpTarget(insnOpcode, label); 214 targetInsnIndex = insnList.indexOf(label); 215 merge(targetInsnIndex, currentFrame, subroutine); 216 newControlFlowEdge(insnIndex, targetInsnIndex); 217 } 218 } else if (insnOpcode == RET) { 219 if (subroutine == null) { 220 throw new AnalyzerException(insnNode, "RET instruction outside of a subroutine"); 221 } 222 for (int i = 0; i < subroutine.callers.size(); ++i) { 223 JumpInsnNode caller = subroutine.callers.get(i); 224 int jsrInsnIndex = insnList.indexOf(caller); 225 if (frames[jsrInsnIndex] != null) { 226 merge( 227 jsrInsnIndex + 1, 228 frames[jsrInsnIndex], 229 currentFrame, 230 subroutines[jsrInsnIndex], 231 subroutine.localsUsed); 232 newControlFlowEdge(insnIndex, jsrInsnIndex + 1); 233 } 234 } 235 } else if (insnOpcode != ATHROW && (insnOpcode < IRETURN || insnOpcode > RETURN)) { 236 if (subroutine != null) { 237 if (insnNode instanceof VarInsnNode) { 238 int varIndex = ((VarInsnNode) insnNode).var; 239 subroutine.localsUsed[varIndex] = true; 240 if (insnOpcode == LLOAD 241 || insnOpcode == DLOAD 242 || insnOpcode == LSTORE 243 || insnOpcode == DSTORE) { 244 subroutine.localsUsed[varIndex + 1] = true; 245 } 246 } else if (insnNode instanceof IincInsnNode) { 247 int varIndex = ((IincInsnNode) insnNode).var; 248 subroutine.localsUsed[varIndex] = true; 249 } 250 } 251 merge(insnIndex + 1, currentFrame, subroutine); 252 newControlFlowEdge(insnIndex, insnIndex + 1); 253 } 254 } 255 256 List<TryCatchBlockNode> insnHandlers = handlers[insnIndex]; 257 if (insnHandlers != null) { 258 for (TryCatchBlockNode tryCatchBlock : insnHandlers) { 259 Type catchType; 260 if (tryCatchBlock.type == null) { 261 catchType = Type.getObjectType("java/lang/Throwable"); 262 } else { 263 catchType = Type.getObjectType(tryCatchBlock.type); 264 } 265 if (newControlFlowExceptionEdge(insnIndex, tryCatchBlock)) { 266 Frame<V> handler = newFrame(oldFrame); 267 handler.clearStack(); 268 handler.push(interpreter.newExceptionValue(tryCatchBlock, handler, catchType)); 269 merge(insnList.indexOf(tryCatchBlock.handler), handler, subroutine); 270 } 271 } 272 } 273 } catch (AnalyzerException e) { 274 throw new AnalyzerException( 275 e.node, "Error at instruction " + insnIndex + ": " + e.getMessage(), e); 276 } catch (RuntimeException e) { 277 // DontCheck(IllegalCatch): can't be fixed, for backward compatibility. 278 throw new AnalyzerException( 279 insnNode, "Error at instruction " + insnIndex + ": " + e.getMessage(), e); 280 } 281 } 282 283 return frames; 284 } 285 286 /** 287 * Analyzes the given method and computes and sets its maximum stack size and maximum number of 288 * local variables. 289 * 290 * @param owner the internal name of the class to which 'method' belongs (see {@link 291 * Type#getInternalName()}). 292 * @param method the method to be analyzed. 293 * @return the symbolic state of the execution stack frame at each bytecode instruction of the 294 * method. The size of the returned array is equal to the number of instructions (and labels) 295 * of the method. A given frame is {@literal null} if and only if the corresponding 296 * instruction cannot be reached (dead code). 297 * @throws AnalyzerException if a problem occurs during the analysis. 298 */ analyzeAndComputeMaxs(final String owner, final MethodNode method)299 public Frame<V>[] analyzeAndComputeMaxs(final String owner, final MethodNode method) 300 throws AnalyzerException { 301 method.maxLocals = computeMaxLocals(method); 302 method.maxStack = -1; 303 analyze(owner, method); 304 method.maxStack = computeMaxStack(frames); 305 return frames; 306 } 307 308 /** 309 * Computes and returns the maximum number of local variables used in the given method. 310 * 311 * @param method a method. 312 * @return the maximum number of local variables used in the given method. 313 */ computeMaxLocals(final MethodNode method)314 private static int computeMaxLocals(final MethodNode method) { 315 int maxLocals = Type.getArgumentsAndReturnSizes(method.desc) >> 2; 316 if ((method.access & Opcodes.ACC_STATIC) != 0) { 317 maxLocals -= 1; 318 } 319 for (AbstractInsnNode insnNode : method.instructions) { 320 if (insnNode instanceof VarInsnNode) { 321 int local = ((VarInsnNode) insnNode).var; 322 int size = 323 (insnNode.getOpcode() == Opcodes.LLOAD 324 || insnNode.getOpcode() == Opcodes.DLOAD 325 || insnNode.getOpcode() == Opcodes.LSTORE 326 || insnNode.getOpcode() == Opcodes.DSTORE) 327 ? 2 328 : 1; 329 maxLocals = Math.max(maxLocals, local + size); 330 } else if (insnNode instanceof IincInsnNode) { 331 int local = ((IincInsnNode) insnNode).var; 332 maxLocals = Math.max(maxLocals, local + 1); 333 } 334 } 335 return maxLocals; 336 } 337 338 /** 339 * Computes and returns the maximum stack size of a method, given its stack map frames. 340 * 341 * @param frames the stack map frames of a method. 342 * @return the maximum stack size of the given method. 343 */ computeMaxStack(final Frame<?>[] frames)344 private static int computeMaxStack(final Frame<?>[] frames) { 345 int maxStack = 0; 346 for (Frame<?> frame : frames) { 347 if (frame != null) { 348 int stackSize = 0; 349 for (int i = 0; i < frame.getStackSize(); ++i) { 350 stackSize += frame.getStack(i).getSize(); 351 } 352 maxStack = Math.max(maxStack, stackSize); 353 } 354 } 355 return maxStack; 356 } 357 358 /** 359 * Finds the subroutines of the currently analyzed method and stores them in {@link #subroutines}. 360 * 361 * @param maxLocals the maximum number of local variables of the currently analyzed method (long 362 * and double values count for two variables). 363 * @throws AnalyzerException if the control flow graph can fall off the end of the code. 364 */ findSubroutines(final int maxLocals)365 private void findSubroutines(final int maxLocals) throws AnalyzerException { 366 // For each instruction, compute the subroutine to which it belongs. 367 // Follow the main 'subroutine', and collect the jsr instructions to nested subroutines. 368 Subroutine main = new Subroutine(null, maxLocals, null); 369 List<AbstractInsnNode> jsrInsns = new ArrayList<>(); 370 findSubroutine(0, main, jsrInsns); 371 // Follow the nested subroutines, and collect their own nested subroutines, until all 372 // subroutines are found. 373 Map<LabelNode, Subroutine> jsrSubroutines = new HashMap<>(); 374 while (!jsrInsns.isEmpty()) { 375 JumpInsnNode jsrInsn = (JumpInsnNode) jsrInsns.remove(0); 376 Subroutine subroutine = jsrSubroutines.get(jsrInsn.label); 377 if (subroutine == null) { 378 subroutine = new Subroutine(jsrInsn.label, maxLocals, jsrInsn); 379 jsrSubroutines.put(jsrInsn.label, subroutine); 380 findSubroutine(insnList.indexOf(jsrInsn.label), subroutine, jsrInsns); 381 } else { 382 subroutine.callers.add(jsrInsn); 383 } 384 } 385 // Clear the main 'subroutine', which is not a real subroutine (and was used only as an 386 // intermediate step above to find the real ones). 387 for (int i = 0; i < insnListSize; ++i) { 388 if (subroutines[i] != null && subroutines[i].start == null) { 389 subroutines[i] = null; 390 } 391 } 392 } 393 394 /** 395 * Follows the control flow graph of the currently analyzed method, starting at the given 396 * instruction index, and stores a copy of the given subroutine in {@link #subroutines} for each 397 * encountered instruction. Jumps to nested subroutines are <i>not</i> followed: instead, the 398 * corresponding instructions are put in the given list. 399 * 400 * @param insnIndex an instruction index. 401 * @param subroutine a subroutine. 402 * @param jsrInsns where the jsr instructions for nested subroutines must be put. 403 * @throws AnalyzerException if the control flow graph can fall off the end of the code. 404 */ findSubroutine( final int insnIndex, final Subroutine subroutine, final List<AbstractInsnNode> jsrInsns)405 private void findSubroutine( 406 final int insnIndex, final Subroutine subroutine, final List<AbstractInsnNode> jsrInsns) 407 throws AnalyzerException { 408 ArrayList<Integer> instructionIndicesToProcess = new ArrayList<>(); 409 instructionIndicesToProcess.add(insnIndex); 410 while (!instructionIndicesToProcess.isEmpty()) { 411 int currentInsnIndex = 412 instructionIndicesToProcess.remove(instructionIndicesToProcess.size() - 1); 413 if (currentInsnIndex < 0 || currentInsnIndex >= insnListSize) { 414 throw new AnalyzerException(null, "Execution can fall off the end of the code"); 415 } 416 if (subroutines[currentInsnIndex] != null) { 417 continue; 418 } 419 subroutines[currentInsnIndex] = new Subroutine(subroutine); 420 AbstractInsnNode currentInsn = insnList.get(currentInsnIndex); 421 422 // Push the normal successors of currentInsn onto instructionIndicesToProcess. 423 if (currentInsn instanceof JumpInsnNode) { 424 if (currentInsn.getOpcode() == JSR) { 425 // Do not follow a jsr, it leads to another subroutine! 426 jsrInsns.add(currentInsn); 427 } else { 428 JumpInsnNode jumpInsn = (JumpInsnNode) currentInsn; 429 instructionIndicesToProcess.add(insnList.indexOf(jumpInsn.label)); 430 } 431 } else if (currentInsn instanceof TableSwitchInsnNode) { 432 TableSwitchInsnNode tableSwitchInsn = (TableSwitchInsnNode) currentInsn; 433 findSubroutine(insnList.indexOf(tableSwitchInsn.dflt), subroutine, jsrInsns); 434 for (int i = tableSwitchInsn.labels.size() - 1; i >= 0; --i) { 435 LabelNode labelNode = tableSwitchInsn.labels.get(i); 436 instructionIndicesToProcess.add(insnList.indexOf(labelNode)); 437 } 438 } else if (currentInsn instanceof LookupSwitchInsnNode) { 439 LookupSwitchInsnNode lookupSwitchInsn = (LookupSwitchInsnNode) currentInsn; 440 findSubroutine(insnList.indexOf(lookupSwitchInsn.dflt), subroutine, jsrInsns); 441 for (int i = lookupSwitchInsn.labels.size() - 1; i >= 0; --i) { 442 LabelNode labelNode = lookupSwitchInsn.labels.get(i); 443 instructionIndicesToProcess.add(insnList.indexOf(labelNode)); 444 } 445 } 446 447 // Push the exception handler successors of currentInsn onto instructionIndicesToProcess. 448 List<TryCatchBlockNode> insnHandlers = handlers[currentInsnIndex]; 449 if (insnHandlers != null) { 450 for (TryCatchBlockNode tryCatchBlock : insnHandlers) { 451 instructionIndicesToProcess.add(insnList.indexOf(tryCatchBlock.handler)); 452 } 453 } 454 455 // Push the next instruction, if the control flow can go from currentInsn to the next. 456 switch (currentInsn.getOpcode()) { 457 case GOTO: 458 case RET: 459 case TABLESWITCH: 460 case LOOKUPSWITCH: 461 case IRETURN: 462 case LRETURN: 463 case FRETURN: 464 case DRETURN: 465 case ARETURN: 466 case RETURN: 467 case ATHROW: 468 break; 469 default: 470 instructionIndicesToProcess.add(currentInsnIndex + 1); 471 break; 472 } 473 } 474 } 475 476 /** 477 * Computes the initial execution stack frame of the given method. 478 * 479 * @param owner the internal name of the class to which 'method' belongs (see {@link 480 * Type#getInternalName()}). 481 * @param method the method to be analyzed. 482 * @return the initial execution stack frame of the 'method'. 483 */ computeInitialFrame(final String owner, final MethodNode method)484 private Frame<V> computeInitialFrame(final String owner, final MethodNode method) { 485 Frame<V> frame = newFrame(method.maxLocals, method.maxStack); 486 int currentLocal = 0; 487 boolean isInstanceMethod = (method.access & ACC_STATIC) == 0; 488 if (isInstanceMethod) { 489 Type ownerType = Type.getObjectType(owner); 490 frame.setLocal( 491 currentLocal, interpreter.newParameterValue(isInstanceMethod, currentLocal, ownerType)); 492 currentLocal++; 493 } 494 Type[] argumentTypes = Type.getArgumentTypes(method.desc); 495 for (Type argumentType : argumentTypes) { 496 frame.setLocal( 497 currentLocal, 498 interpreter.newParameterValue(isInstanceMethod, currentLocal, argumentType)); 499 currentLocal++; 500 if (argumentType.getSize() == 2) { 501 frame.setLocal(currentLocal, interpreter.newEmptyValue(currentLocal)); 502 currentLocal++; 503 } 504 } 505 while (currentLocal < method.maxLocals) { 506 frame.setLocal(currentLocal, interpreter.newEmptyValue(currentLocal)); 507 currentLocal++; 508 } 509 frame.setReturn(interpreter.newReturnTypeValue(Type.getReturnType(method.desc))); 510 return frame; 511 } 512 513 /** 514 * Returns the symbolic execution stack frame for each instruction of the last analyzed method. 515 * 516 * @return the symbolic state of the execution stack frame at each bytecode instruction of the 517 * method. The size of the returned array is equal to the number of instructions (and labels) 518 * of the method. A given frame is {@literal null} if the corresponding instruction cannot be 519 * reached, or if an error occurred during the analysis of the method. 520 */ getFrames()521 public Frame<V>[] getFrames() { 522 return frames; 523 } 524 525 /** 526 * Returns the exception handlers for the given instruction. 527 * 528 * @param insnIndex the index of an instruction of the last analyzed method. 529 * @return a list of {@link TryCatchBlockNode} objects. 530 */ getHandlers(final int insnIndex)531 public List<TryCatchBlockNode> getHandlers(final int insnIndex) { 532 return handlers[insnIndex]; 533 } 534 535 /** 536 * Initializes this analyzer. This method is called just before the execution of control flow 537 * analysis loop in {@link #analyze}. The default implementation of this method does nothing. 538 * 539 * @param owner the internal name of the class to which the method belongs (see {@link 540 * Type#getInternalName()}). 541 * @param method the method to be analyzed. 542 * @throws AnalyzerException if a problem occurs. 543 */ init(final String owner, final MethodNode method)544 protected void init(final String owner, final MethodNode method) throws AnalyzerException { 545 // Nothing to do. 546 } 547 548 /** 549 * Constructs a new frame with the given size. 550 * 551 * @param numLocals the maximum number of local variables of the frame. 552 * @param numStack the maximum stack size of the frame. 553 * @return the created frame. 554 */ newFrame(final int numLocals, final int numStack)555 protected Frame<V> newFrame(final int numLocals, final int numStack) { 556 return new Frame<>(numLocals, numStack); 557 } 558 559 /** 560 * Constructs a copy of the given frame. 561 * 562 * @param frame a frame. 563 * @return the created frame. 564 */ newFrame(final Frame<? extends V> frame)565 protected Frame<V> newFrame(final Frame<? extends V> frame) { 566 return new Frame<>(frame); 567 } 568 569 /** 570 * Creates a control flow graph edge. The default implementation of this method does nothing. It 571 * can be overridden in order to construct the control flow graph of a method (this method is 572 * called by the {@link #analyze} method during its visit of the method's code). 573 * 574 * @param insnIndex an instruction index. 575 * @param successorIndex index of a successor instruction. 576 */ newControlFlowEdge(final int insnIndex, final int successorIndex)577 protected void newControlFlowEdge(final int insnIndex, final int successorIndex) { 578 // Nothing to do. 579 } 580 581 /** 582 * Creates a control flow graph edge corresponding to an exception handler. The default 583 * implementation of this method does nothing. It can be overridden in order to construct the 584 * control flow graph of a method (this method is called by the {@link #analyze} method during its 585 * visit of the method's code). 586 * 587 * @param insnIndex an instruction index. 588 * @param successorIndex index of a successor instruction. 589 * @return true if this edge must be considered in the data flow analysis performed by this 590 * analyzer, or false otherwise. The default implementation of this method always returns 591 * true. 592 */ newControlFlowExceptionEdge(final int insnIndex, final int successorIndex)593 protected boolean newControlFlowExceptionEdge(final int insnIndex, final int successorIndex) { 594 return true; 595 } 596 597 /** 598 * Creates a control flow graph edge corresponding to an exception handler. The default 599 * implementation of this method delegates to {@link #newControlFlowExceptionEdge(int, int)}. It 600 * can be overridden in order to construct the control flow graph of a method (this method is 601 * called by the {@link #analyze} method during its visit of the method's code). 602 * 603 * @param insnIndex an instruction index. 604 * @param tryCatchBlock TryCatchBlockNode corresponding to this edge. 605 * @return true if this edge must be considered in the data flow analysis performed by this 606 * analyzer, or false otherwise. The default implementation of this method delegates to {@link 607 * #newControlFlowExceptionEdge(int, int)}. 608 */ newControlFlowExceptionEdge( final int insnIndex, final TryCatchBlockNode tryCatchBlock)609 protected boolean newControlFlowExceptionEdge( 610 final int insnIndex, final TryCatchBlockNode tryCatchBlock) { 611 return newControlFlowExceptionEdge(insnIndex, insnList.indexOf(tryCatchBlock.handler)); 612 } 613 614 // ----------------------------------------------------------------------------------------------- 615 616 /** 617 * Merges the given frame and subroutine into the frame and subroutines at the given instruction 618 * index. If the frame or the subroutine at the given instruction index changes as a result of 619 * this merge, the instruction index is added to the list of instructions to process (if it is not 620 * already the case). 621 * 622 * @param insnIndex an instruction index. 623 * @param frame a frame. This frame is left unchanged by this method. 624 * @param subroutine a subroutine. This subroutine is left unchanged by this method. 625 * @throws AnalyzerException if the frames have incompatible sizes. 626 */ merge(final int insnIndex, final Frame<V> frame, final Subroutine subroutine)627 private void merge(final int insnIndex, final Frame<V> frame, final Subroutine subroutine) 628 throws AnalyzerException { 629 boolean changed; 630 Frame<V> oldFrame = frames[insnIndex]; 631 if (oldFrame == null) { 632 frames[insnIndex] = newFrame(frame); 633 changed = true; 634 } else { 635 changed = oldFrame.merge(frame, interpreter); 636 } 637 Subroutine oldSubroutine = subroutines[insnIndex]; 638 if (oldSubroutine == null) { 639 if (subroutine != null) { 640 subroutines[insnIndex] = new Subroutine(subroutine); 641 changed = true; 642 } 643 } else { 644 if (subroutine != null) { 645 changed |= oldSubroutine.merge(subroutine); 646 } 647 } 648 if (changed && !inInstructionsToProcess[insnIndex]) { 649 inInstructionsToProcess[insnIndex] = true; 650 instructionsToProcess[numInstructionsToProcess++] = insnIndex; 651 } 652 } 653 654 /** 655 * Merges the given frame and subroutine into the frame and subroutines at the given instruction 656 * index (case of a RET instruction). If the frame or the subroutine at the given instruction 657 * index changes as a result of this merge, the instruction index is added to the list of 658 * instructions to process (if it is not already the case). 659 * 660 * @param insnIndex the index of an instruction immediately following a jsr instruction. 661 * @param frameBeforeJsr the execution stack frame before the jsr instruction. This frame is 662 * merged into 'frameAfterRet'. 663 * @param frameAfterRet the execution stack frame after a ret instruction of the subroutine. This 664 * frame is merged into the frame at 'insnIndex' (after it has itself been merge with 665 * 'frameBeforeJsr'). 666 * @param subroutineBeforeJsr if the jsr is itself part of a subroutine (case of nested 667 * subroutine), the subroutine it belongs to. 668 * @param localsUsed the local variables read or written in the subroutine. 669 * @throws AnalyzerException if the frames have incompatible sizes. 670 */ merge( final int insnIndex, final Frame<V> frameBeforeJsr, final Frame<V> frameAfterRet, final Subroutine subroutineBeforeJsr, final boolean[] localsUsed)671 private void merge( 672 final int insnIndex, 673 final Frame<V> frameBeforeJsr, 674 final Frame<V> frameAfterRet, 675 final Subroutine subroutineBeforeJsr, 676 final boolean[] localsUsed) 677 throws AnalyzerException { 678 frameAfterRet.merge(frameBeforeJsr, localsUsed); 679 680 boolean changed; 681 Frame<V> oldFrame = frames[insnIndex]; 682 if (oldFrame == null) { 683 frames[insnIndex] = newFrame(frameAfterRet); 684 changed = true; 685 } else { 686 changed = oldFrame.merge(frameAfterRet, interpreter); 687 } 688 Subroutine oldSubroutine = subroutines[insnIndex]; 689 if (oldSubroutine != null && subroutineBeforeJsr != null) { 690 changed |= oldSubroutine.merge(subroutineBeforeJsr); 691 } 692 if (changed && !inInstructionsToProcess[insnIndex]) { 693 inInstructionsToProcess[insnIndex] = true; 694 instructionsToProcess[numInstructionsToProcess++] = insnIndex; 695 } 696 } 697 } 698