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 */ 30 package org.mockito.asm.tree.analysis; 31 32 import java.util.ArrayList; 33 import java.util.HashMap; 34 import java.util.List; 35 import java.util.Map; 36 37 import org.mockito.asm.Opcodes; 38 import org.mockito.asm.Type; 39 import org.mockito.asm.tree.AbstractInsnNode; 40 import org.mockito.asm.tree.IincInsnNode; 41 import org.mockito.asm.tree.InsnList; 42 import org.mockito.asm.tree.JumpInsnNode; 43 import org.mockito.asm.tree.LabelNode; 44 import org.mockito.asm.tree.LookupSwitchInsnNode; 45 import org.mockito.asm.tree.MethodNode; 46 import org.mockito.asm.tree.TableSwitchInsnNode; 47 import org.mockito.asm.tree.TryCatchBlockNode; 48 import org.mockito.asm.tree.VarInsnNode; 49 50 /** 51 * A semantic bytecode analyzer. <i>This class does not fully check that JSR and 52 * RET instructions are valid.</i> 53 * 54 * @author Eric Bruneton 55 */ 56 public class Analyzer implements Opcodes { 57 58 private final Interpreter interpreter; 59 60 private int n; 61 62 private InsnList insns; 63 64 private List[] handlers; 65 66 private Frame[] frames; 67 68 private Subroutine[] subroutines; 69 70 private boolean[] queued; 71 72 private int[] queue; 73 74 private int top; 75 76 /** 77 * Constructs a new {@link Analyzer}. 78 * 79 * @param interpreter the interpreter to be used to symbolically interpret 80 * the bytecode instructions. 81 */ Analyzer(final Interpreter interpreter)82 public Analyzer(final Interpreter interpreter) { 83 this.interpreter = interpreter; 84 } 85 86 /** 87 * Analyzes the given method. 88 * 89 * @param owner the internal name of the class to which the method belongs. 90 * @param m the method to be analyzed. 91 * @return the symbolic state of the execution stack frame at each bytecode 92 * instruction of the method. The size of the returned array is 93 * equal to the number of instructions (and labels) of the method. A 94 * given frame is <tt>null</tt> if and only if the corresponding 95 * instruction cannot be reached (dead code). 96 * @throws AnalyzerException if a problem occurs during the analysis. 97 */ analyze(final String owner, final MethodNode m)98 public Frame[] analyze(final String owner, final MethodNode m) 99 throws AnalyzerException 100 { 101 if ((m.access & (ACC_ABSTRACT | ACC_NATIVE)) != 0) { 102 frames = new Frame[0]; 103 return frames; 104 } 105 n = m.instructions.size(); 106 insns = m.instructions; 107 handlers = new List[n]; 108 frames = new Frame[n]; 109 subroutines = new Subroutine[n]; 110 queued = new boolean[n]; 111 queue = new int[n]; 112 top = 0; 113 114 // computes exception handlers for each instruction 115 for (int i = 0; i < m.tryCatchBlocks.size(); ++i) { 116 TryCatchBlockNode tcb = (TryCatchBlockNode) m.tryCatchBlocks.get(i); 117 int begin = insns.indexOf(tcb.start); 118 int end = insns.indexOf(tcb.end); 119 for (int j = begin; j < end; ++j) { 120 List insnHandlers = handlers[j]; 121 if (insnHandlers == null) { 122 insnHandlers = new ArrayList(); 123 handlers[j] = insnHandlers; 124 } 125 insnHandlers.add(tcb); 126 } 127 } 128 129 // computes the subroutine for each instruction: 130 Subroutine main = new Subroutine(null, m.maxLocals, null); 131 List subroutineCalls = new ArrayList(); 132 Map subroutineHeads = new HashMap(); 133 findSubroutine(0, main, subroutineCalls); 134 while (!subroutineCalls.isEmpty()) { 135 JumpInsnNode jsr = (JumpInsnNode) subroutineCalls.remove(0); 136 Subroutine sub = (Subroutine) subroutineHeads.get(jsr.label); 137 if (sub == null) { 138 sub = new Subroutine(jsr.label, m.maxLocals, jsr); 139 subroutineHeads.put(jsr.label, sub); 140 findSubroutine(insns.indexOf(jsr.label), sub, subroutineCalls); 141 } else { 142 sub.callers.add(jsr); 143 } 144 } 145 for (int i = 0; i < n; ++i) { 146 if (subroutines[i] != null && subroutines[i].start == null) { 147 subroutines[i] = null; 148 } 149 } 150 151 // initializes the data structures for the control flow analysis 152 Frame current = newFrame(m.maxLocals, m.maxStack); 153 Frame handler = newFrame(m.maxLocals, m.maxStack); 154 Type[] args = Type.getArgumentTypes(m.desc); 155 int local = 0; 156 if ((m.access & ACC_STATIC) == 0) { 157 Type ctype = Type.getObjectType(owner); 158 current.setLocal(local++, interpreter.newValue(ctype)); 159 } 160 for (int i = 0; i < args.length; ++i) { 161 current.setLocal(local++, interpreter.newValue(args[i])); 162 if (args[i].getSize() == 2) { 163 current.setLocal(local++, interpreter.newValue(null)); 164 } 165 } 166 while (local < m.maxLocals) { 167 current.setLocal(local++, interpreter.newValue(null)); 168 } 169 merge(0, current, null); 170 171 // control flow analysis 172 while (top > 0) { 173 int insn = queue[--top]; 174 Frame f = frames[insn]; 175 Subroutine subroutine = subroutines[insn]; 176 queued[insn] = false; 177 178 try { 179 AbstractInsnNode insnNode = m.instructions.get(insn); 180 int insnOpcode = insnNode.getOpcode(); 181 int insnType = insnNode.getType(); 182 183 if (insnType == AbstractInsnNode.LABEL 184 || insnType == AbstractInsnNode.LINE 185 || insnType == AbstractInsnNode.FRAME) 186 { 187 merge(insn + 1, f, subroutine); 188 newControlFlowEdge(insn, insn + 1); 189 } else { 190 current.init(f).execute(insnNode, interpreter); 191 subroutine = subroutine == null ? null : subroutine.copy(); 192 193 if (insnNode instanceof JumpInsnNode) { 194 JumpInsnNode j = (JumpInsnNode) insnNode; 195 if (insnOpcode != GOTO && insnOpcode != JSR) { 196 merge(insn + 1, current, subroutine); 197 newControlFlowEdge(insn, insn + 1); 198 } 199 int jump = insns.indexOf(j.label); 200 if (insnOpcode == JSR) { 201 merge(jump, current, new Subroutine(j.label, 202 m.maxLocals, 203 j)); 204 } else { 205 merge(jump, current, subroutine); 206 } 207 newControlFlowEdge(insn, jump); 208 } else if (insnNode instanceof LookupSwitchInsnNode) { 209 LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode; 210 int jump = insns.indexOf(lsi.dflt); 211 merge(jump, current, subroutine); 212 newControlFlowEdge(insn, jump); 213 for (int j = 0; j < lsi.labels.size(); ++j) { 214 LabelNode label = (LabelNode) lsi.labels.get(j); 215 jump = insns.indexOf(label); 216 merge(jump, current, subroutine); 217 newControlFlowEdge(insn, jump); 218 } 219 } else if (insnNode instanceof TableSwitchInsnNode) { 220 TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode; 221 int jump = insns.indexOf(tsi.dflt); 222 merge(jump, current, subroutine); 223 newControlFlowEdge(insn, jump); 224 for (int j = 0; j < tsi.labels.size(); ++j) { 225 LabelNode label = (LabelNode) tsi.labels.get(j); 226 jump = insns.indexOf(label); 227 merge(jump, current, subroutine); 228 newControlFlowEdge(insn, jump); 229 } 230 } else if (insnOpcode == RET) { 231 if (subroutine == null) { 232 throw new AnalyzerException("RET instruction outside of a sub routine"); 233 } 234 for (int i = 0; i < subroutine.callers.size(); ++i) { 235 Object caller = subroutine.callers.get(i); 236 int call = insns.indexOf((AbstractInsnNode) caller); 237 if (frames[call] != null) { 238 merge(call + 1, 239 frames[call], 240 current, 241 subroutines[call], 242 subroutine.access); 243 newControlFlowEdge(insn, call + 1); 244 } 245 } 246 } else if (insnOpcode != ATHROW 247 && (insnOpcode < IRETURN || insnOpcode > RETURN)) 248 { 249 if (subroutine != null) { 250 if (insnNode instanceof VarInsnNode) { 251 int var = ((VarInsnNode) insnNode).var; 252 subroutine.access[var] = true; 253 if (insnOpcode == LLOAD || insnOpcode == DLOAD 254 || insnOpcode == LSTORE 255 || insnOpcode == DSTORE) 256 { 257 subroutine.access[var + 1] = true; 258 } 259 } else if (insnNode instanceof IincInsnNode) { 260 int var = ((IincInsnNode) insnNode).var; 261 subroutine.access[var] = true; 262 } 263 } 264 merge(insn + 1, current, subroutine); 265 newControlFlowEdge(insn, insn + 1); 266 } 267 } 268 269 List insnHandlers = handlers[insn]; 270 if (insnHandlers != null) { 271 for (int i = 0; i < insnHandlers.size(); ++i) { 272 TryCatchBlockNode tcb = (TryCatchBlockNode) insnHandlers.get(i); 273 Type type; 274 if (tcb.type == null) { 275 type = Type.getObjectType("java/lang/Throwable"); 276 } else { 277 type = Type.getObjectType(tcb.type); 278 } 279 int jump = insns.indexOf(tcb.handler); 280 if (newControlFlowExceptionEdge(insn, jump)) { 281 handler.init(f); 282 handler.clearStack(); 283 handler.push(interpreter.newValue(type)); 284 merge(jump, handler, subroutine); 285 } 286 } 287 } 288 } catch (AnalyzerException e) { 289 throw new AnalyzerException("Error at instruction " + insn 290 + ": " + e.getMessage(), e); 291 } catch (Exception e) { 292 throw new AnalyzerException("Error at instruction " + insn 293 + ": " + e.getMessage(), e); 294 } 295 } 296 297 return frames; 298 } 299 findSubroutine(int insn, final Subroutine sub, final List calls)300 private void findSubroutine(int insn, final Subroutine sub, final List calls) 301 throws AnalyzerException 302 { 303 while (true) { 304 if (insn < 0 || insn >= n) { 305 throw new AnalyzerException("Execution can fall off end of the code"); 306 } 307 if (subroutines[insn] != null) { 308 return; 309 } 310 subroutines[insn] = sub.copy(); 311 AbstractInsnNode node = insns.get(insn); 312 313 // calls findSubroutine recursively on normal successors 314 if (node instanceof JumpInsnNode) { 315 if (node.getOpcode() == JSR) { 316 // do not follow a JSR, it leads to another subroutine! 317 calls.add(node); 318 } else { 319 JumpInsnNode jnode = (JumpInsnNode) node; 320 findSubroutine(insns.indexOf(jnode.label), sub, calls); 321 } 322 } else if (node instanceof TableSwitchInsnNode) { 323 TableSwitchInsnNode tsnode = (TableSwitchInsnNode) node; 324 findSubroutine(insns.indexOf(tsnode.dflt), sub, calls); 325 for (int i = tsnode.labels.size() - 1; i >= 0; --i) { 326 LabelNode l = (LabelNode) tsnode.labels.get(i); 327 findSubroutine(insns.indexOf(l), sub, calls); 328 } 329 } else if (node instanceof LookupSwitchInsnNode) { 330 LookupSwitchInsnNode lsnode = (LookupSwitchInsnNode) node; 331 findSubroutine(insns.indexOf(lsnode.dflt), sub, calls); 332 for (int i = lsnode.labels.size() - 1; i >= 0; --i) { 333 LabelNode l = (LabelNode) lsnode.labels.get(i); 334 findSubroutine(insns.indexOf(l), sub, calls); 335 } 336 } 337 338 // calls findSubroutine recursively on exception handler successors 339 List insnHandlers = handlers[insn]; 340 if (insnHandlers != null) { 341 for (int i = 0; i < insnHandlers.size(); ++i) { 342 TryCatchBlockNode tcb = (TryCatchBlockNode) insnHandlers.get(i); 343 findSubroutine(insns.indexOf(tcb.handler), sub, calls); 344 } 345 } 346 347 // if insn does not falls through to the next instruction, return. 348 switch (node.getOpcode()) { 349 case GOTO: 350 case RET: 351 case TABLESWITCH: 352 case LOOKUPSWITCH: 353 case IRETURN: 354 case LRETURN: 355 case FRETURN: 356 case DRETURN: 357 case ARETURN: 358 case RETURN: 359 case ATHROW: 360 return; 361 } 362 insn++; 363 } 364 } 365 366 /** 367 * Returns the symbolic stack frame for each instruction of the last 368 * recently analyzed method. 369 * 370 * @return the symbolic state of the execution stack frame at each bytecode 371 * instruction of the method. The size of the returned array is 372 * equal to the number of instructions (and labels) of the method. A 373 * given frame is <tt>null</tt> if the corresponding instruction 374 * cannot be reached, or if an error occured during the analysis of 375 * the method. 376 */ getFrames()377 public Frame[] getFrames() { 378 return frames; 379 } 380 381 /** 382 * Returns the exception handlers for the given instruction. 383 * 384 * @param insn the index of an instruction of the last recently analyzed 385 * method. 386 * @return a list of {@link TryCatchBlockNode} objects. 387 */ getHandlers(final int insn)388 public List getHandlers(final int insn) { 389 return handlers[insn]; 390 } 391 392 /** 393 * Constructs a new frame with the given size. 394 * 395 * @param nLocals the maximum number of local variables of the frame. 396 * @param nStack the maximum stack size of the frame. 397 * @return the created frame. 398 */ newFrame(final int nLocals, final int nStack)399 protected Frame newFrame(final int nLocals, final int nStack) { 400 return new Frame(nLocals, nStack); 401 } 402 403 /** 404 * Constructs a new frame that is identical to the given frame. 405 * 406 * @param src a frame. 407 * @return the created frame. 408 */ newFrame(final Frame src)409 protected Frame newFrame(final Frame src) { 410 return new Frame(src); 411 } 412 413 /** 414 * Creates a control flow graph edge. The default implementation of this 415 * method does nothing. It can be overriden in order to construct the 416 * control flow graph of a method (this method is called by the 417 * {@link #analyze analyze} method during its visit of the method's code). 418 * 419 * @param insn an instruction index. 420 * @param successor index of a successor instruction. 421 */ newControlFlowEdge(final int insn, final int successor)422 protected void newControlFlowEdge(final int insn, final int successor) { 423 } 424 425 /** 426 * Creates a control flow graph edge corresponding to an exception handler. 427 * The default implementation of this method does nothing. It can be 428 * overriden in order to construct the control flow graph of a method (this 429 * method is called by the {@link #analyze analyze} method during its visit 430 * of the method's code). 431 * 432 * @param insn an instruction index. 433 * @param successor index of a successor instruction. 434 * @return true if this edge must be considered in the data flow analysis 435 * performed by this analyzer, or false otherwise. The default 436 * implementation of this method always returns true. 437 */ newControlFlowExceptionEdge( final int insn, final int successor)438 protected boolean newControlFlowExceptionEdge( 439 final int insn, 440 final int successor) 441 { 442 return true; 443 } 444 445 // ------------------------------------------------------------------------- 446 merge( final int insn, final Frame frame, final Subroutine subroutine)447 private void merge( 448 final int insn, 449 final Frame frame, 450 final Subroutine subroutine) throws AnalyzerException 451 { 452 Frame oldFrame = frames[insn]; 453 Subroutine oldSubroutine = subroutines[insn]; 454 boolean changes; 455 456 if (oldFrame == null) { 457 frames[insn] = newFrame(frame); 458 changes = true; 459 } else { 460 changes = oldFrame.merge(frame, interpreter); 461 } 462 463 if (oldSubroutine == null) { 464 if (subroutine != null) { 465 subroutines[insn] = subroutine.copy(); 466 changes = true; 467 } 468 } else { 469 if (subroutine != null) { 470 changes |= oldSubroutine.merge(subroutine); 471 } 472 } 473 if (changes && !queued[insn]) { 474 queued[insn] = true; 475 queue[top++] = insn; 476 } 477 } 478 merge( final int insn, final Frame beforeJSR, final Frame afterRET, final Subroutine subroutineBeforeJSR, final boolean[] access)479 private void merge( 480 final int insn, 481 final Frame beforeJSR, 482 final Frame afterRET, 483 final Subroutine subroutineBeforeJSR, 484 final boolean[] access) throws AnalyzerException 485 { 486 Frame oldFrame = frames[insn]; 487 Subroutine oldSubroutine = subroutines[insn]; 488 boolean changes; 489 490 afterRET.merge(beforeJSR, access); 491 492 if (oldFrame == null) { 493 frames[insn] = newFrame(afterRET); 494 changes = true; 495 } else { 496 changes = oldFrame.merge(afterRET, access); 497 } 498 499 if (oldSubroutine != null && subroutineBeforeJSR != null) { 500 changes |= oldSubroutine.merge(subroutineBeforeJSR); 501 } 502 if (changes && !queued[insn]) { 503 queued[insn] = true; 504 queue[top++] = insn; 505 } 506 } 507 } 508