| /*** |
| * ASM: a very small and fast Java bytecode manipulation framework |
| * Copyright (c) 2000-2005 INRIA, France Telecom |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. Neither the name of the copyright holders nor the names of its |
| * contributors may be used to endorse or promote products derived from |
| * this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
| * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
| * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
| * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
| * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF |
| * THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| package org.objectweb.asm.tree.analysis; |
| |
| import java.util.ArrayList; |
| import java.util.List; |
| |
| import org.objectweb.asm.Opcodes; |
| import org.objectweb.asm.Label; |
| import org.objectweb.asm.Type; |
| import org.objectweb.asm.tree.AbstractInsnNode; |
| import org.objectweb.asm.tree.IincInsnNode; |
| import org.objectweb.asm.tree.JumpInsnNode; |
| import org.objectweb.asm.tree.LabelNode; |
| import org.objectweb.asm.tree.LookupSwitchInsnNode; |
| import org.objectweb.asm.tree.MethodNode; |
| import org.objectweb.asm.tree.TableSwitchInsnNode; |
| import org.objectweb.asm.tree.TryCatchBlockNode; |
| import org.objectweb.asm.tree.VarInsnNode; |
| |
| /** |
| * A semantic bytecode analyzer. |
| * |
| * @author Eric Bruneton |
| */ |
| public class Analyzer implements Opcodes { |
| |
| private Interpreter interpreter; |
| |
| private int n; |
| |
| private IntMap indexes; |
| |
| private List[] handlers; |
| |
| private Frame[] frames; |
| |
| private Subroutine[] subroutines; |
| |
| private boolean[] queued; |
| |
| private int[] queue; |
| |
| private int top; |
| |
| private boolean jsr; |
| |
| /** |
| * Constructs a new {@link Analyzer}. |
| * |
| * @param interpreter the interpreter to be used to symbolically interpret |
| * the bytecode instructions. |
| */ |
| public Analyzer(final Interpreter interpreter) { |
| this.interpreter = interpreter; |
| } |
| |
| /** |
| * Analyzes the given method. |
| * |
| * @param owner the internal name of the class to which the method belongs. |
| * @param m the method to be analyzed. |
| * @return the symbolic state of the execution stack frame at each bytecode |
| * instruction of the method. The size of the returned array is |
| * equal to the number of instructions (and labels) of the method. A |
| * given frame is <tt>null</tt> if and only if the corresponding |
| * instruction cannot be reached (dead code). |
| * @throws AnalyzerException if a problem occurs during the analysis. |
| */ |
| public Frame[] analyze(final String owner, final MethodNode m) |
| throws AnalyzerException |
| { |
| n = m.instructions.size(); |
| indexes = new IntMap(2 * n); |
| handlers = new List[n]; |
| frames = new Frame[n]; |
| subroutines = new Subroutine[n]; |
| queued = new boolean[n]; |
| queue = new int[n]; |
| top = 0; |
| |
| // computes instruction indexes |
| for (int i = 0; i < n; ++i) { |
| Object insn = m.instructions.get(i); |
| if (insn instanceof LabelNode) { |
| insn = ((LabelNode) insn).label; |
| } |
| indexes.put(insn, i); |
| } |
| |
| // computes exception handlers for each instruction |
| for (int i = 0; i < m.tryCatchBlocks.size(); ++i) { |
| TryCatchBlockNode tcb = (TryCatchBlockNode) m.tryCatchBlocks.get(i); |
| int begin = indexes.get(tcb.start); |
| int end = indexes.get(tcb.end); |
| for (int j = begin; j < end; ++j) { |
| List insnHandlers = handlers[j]; |
| if (insnHandlers == null) { |
| insnHandlers = new ArrayList(); |
| handlers[j] = insnHandlers; |
| } |
| insnHandlers.add(tcb); |
| } |
| } |
| |
| // initializes the data structures for the control flow analysis |
| // algorithm |
| Frame current = newFrame(m.maxLocals, m.maxStack); |
| Frame handler = newFrame(m.maxLocals, m.maxStack); |
| Type[] args = Type.getArgumentTypes(m.desc); |
| int local = 0; |
| if ((m.access & ACC_STATIC) == 0) { |
| Type ctype = Type.getType("L" + owner + ";"); |
| current.setLocal(local++, interpreter.newValue(ctype)); |
| } |
| for (int i = 0; i < args.length; ++i) { |
| current.setLocal(local++, interpreter.newValue(args[i])); |
| if (args[i].getSize() == 2) { |
| current.setLocal(local++, interpreter.newValue(null)); |
| } |
| } |
| while (local < m.maxLocals) { |
| current.setLocal(local++, interpreter.newValue(null)); |
| } |
| merge(0, current, null); |
| |
| // control flow analysis |
| while (top > 0) { |
| int insn = queue[--top]; |
| Frame f = frames[insn]; |
| Subroutine subroutine = subroutines[insn]; |
| queued[insn] = false; |
| |
| try { |
| Object o = m.instructions.get(insn); |
| jsr = false; |
| |
| if (o instanceof LabelNode) { |
| merge(insn + 1, f, subroutine); |
| } else { |
| AbstractInsnNode insnNode = (AbstractInsnNode) o; |
| int insnOpcode = insnNode.getOpcode(); |
| |
| current.init(f).execute(insnNode, interpreter); |
| subroutine = subroutine == null ? null : subroutine.copy(); |
| |
| if (insnNode instanceof JumpInsnNode) { |
| JumpInsnNode j = (JumpInsnNode) insnNode; |
| if (insnOpcode != GOTO && insnOpcode != JSR) { |
| merge(insn + 1, current, subroutine); |
| } |
| if (insnOpcode == JSR) { |
| jsr = true; |
| merge(indexes.get(j.label), |
| current, |
| new Subroutine(j.label, m.maxLocals, j)); |
| } else { |
| merge(indexes.get(j.label), current, subroutine); |
| } |
| } else if (insnNode instanceof LookupSwitchInsnNode) { |
| LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode; |
| merge(indexes.get(lsi.dflt), current, subroutine); |
| for (int j = 0; j < lsi.labels.size(); ++j) { |
| Label label = (Label) lsi.labels.get(j); |
| merge(indexes.get(label), current, subroutine); |
| } |
| } else if (insnNode instanceof TableSwitchInsnNode) { |
| TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode; |
| merge(indexes.get(tsi.dflt), current, subroutine); |
| for (int j = 0; j < tsi.labels.size(); ++j) { |
| Label label = (Label) tsi.labels.get(j); |
| merge(indexes.get(label), current, subroutine); |
| } |
| } else if (insnOpcode == RET) { |
| if (subroutine == null) { |
| throw new AnalyzerException("RET instruction outside of a sub routine"); |
| } |
| for (int i = 0; i < subroutine.callers.size(); ++i) { |
| int caller = indexes.get(subroutine.callers.get(i)); |
| merge(caller + 1, |
| frames[caller], |
| current, |
| subroutines[caller], |
| subroutine.access); |
| } |
| } else if (insnOpcode != ATHROW |
| && (insnOpcode < IRETURN || insnOpcode > RETURN)) |
| { |
| if (subroutine != null) { |
| if (insnNode instanceof VarInsnNode) { |
| int var = ((VarInsnNode) insnNode).var; |
| subroutine.access[var] = true; |
| if (insnOpcode == LLOAD || insnOpcode == DLOAD |
| || insnOpcode == LSTORE |
| || insnOpcode == DSTORE) |
| { |
| subroutine.access[var + 1] = true; |
| } |
| } else if (insnNode instanceof IincInsnNode) { |
| int var = ((IincInsnNode) insnNode).var; |
| subroutine.access[var] = true; |
| } |
| } |
| merge(insn + 1, current, subroutine); |
| } |
| } |
| |
| List insnHandlers = handlers[insn]; |
| if (insnHandlers != null) { |
| for (int i = 0; i < insnHandlers.size(); ++i) { |
| TryCatchBlockNode tcb = (TryCatchBlockNode) insnHandlers.get(i); |
| Type type; |
| if (tcb.type == null) { |
| type = Type.getType("Ljava/lang/Throwable;"); |
| } else { |
| type = Type.getType("L" + tcb.type + ";"); |
| } |
| handler.init(f); |
| handler.clearStack(); |
| handler.push(interpreter.newValue(type)); |
| merge(indexes.get(tcb.handler), handler, subroutine); |
| } |
| } |
| } catch (AnalyzerException e) { |
| throw new AnalyzerException("Error at instruction " + insn |
| + ": " + e.getMessage(), e); |
| } catch(Exception e) { |
| throw new AnalyzerException("Error at instruction " + insn |
| + ": " + e.getMessage(), e); |
| } |
| } |
| |
| return frames; |
| } |
| |
| /** |
| * Returns the symbolic stack frame for each instruction of the last |
| * recently analyzed method. |
| * |
| * @return the symbolic state of the execution stack frame at each bytecode |
| * instruction of the method. The size of the returned array is |
| * equal to the number of instructions (and labels) of the method. A |
| * given frame is <tt>null</tt> if the corresponding instruction |
| * cannot be reached, or if an error occured during the analysis of |
| * the method. |
| */ |
| public Frame[] getFrames() { |
| return frames; |
| } |
| |
| /** |
| * Returns the index of the given instruction. |
| * |
| * @param insn a {@link Label} or {@link AbstractInsnNode} of the last |
| * recently analyzed method. |
| * @return the index of the given instruction of the last recently analyzed |
| * method. |
| */ |
| public int getIndex(final Object insn) { |
| return indexes.get(insn); |
| } |
| |
| /** |
| * Returns the exception handlers for the given instruction. |
| * |
| * @param insn the index of an instruction of the last recently analyzed |
| * method. |
| * @return a list of {@link TryCatchBlockNode} objects. |
| */ |
| public List getHandlers(final int insn) { |
| return handlers[insn]; |
| } |
| |
| /** |
| * Constructs a new frame with the given size. |
| * |
| * @param nLocals the maximum number of local variables of the frame. |
| * @param nStack the maximum stack size of the frame. |
| * @return the created frame. |
| */ |
| protected Frame newFrame(final int nLocals, final int nStack) { |
| return new Frame(nLocals, nStack); |
| } |
| |
| /** |
| * Constructs a new frame that is identical to the given frame. |
| * |
| * @param src a frame. |
| * @return the created frame. |
| */ |
| protected Frame newFrame(final Frame src) { |
| return new Frame(src); |
| } |
| |
| /** |
| * Creates a control flow graph edge. The default implementation of this |
| * method does nothing. It can be overriden in order to construct the |
| * control flow graph of a method (this method is called by the |
| * {@link #analyze analyze} method during its visit of the method's code). |
| * |
| * @param frame the frame corresponding to an instruction. |
| * @param successor the frame corresponding to a successor instruction. |
| */ |
| protected void newControlFlowEdge(final Frame frame, final Frame successor) |
| { |
| } |
| |
| // ------------------------------------------------------------------------- |
| |
| private void merge( |
| final int insn, |
| final Frame frame, |
| final Subroutine subroutine) throws AnalyzerException |
| { |
| if (insn > n - 1) { |
| throw new AnalyzerException("Execution can fall off end of the code"); |
| } |
| |
| Frame oldFrame = frames[insn]; |
| Subroutine oldSubroutine = subroutines[insn]; |
| boolean changes = false; |
| |
| if (oldFrame == null) { |
| frames[insn] = newFrame(frame); |
| changes = true; |
| } else { |
| changes |= oldFrame.merge(frame, interpreter); |
| } |
| |
| newControlFlowEdge(frame, oldFrame); |
| |
| if (oldSubroutine == null) { |
| if (subroutine != null) { |
| subroutines[insn] = subroutine.copy(); |
| changes = true; |
| } |
| } else { |
| if (subroutine != null) { |
| changes |= oldSubroutine.merge(subroutine, !jsr); |
| } |
| } |
| if (changes && !queued[insn]) { |
| queued[insn] = true; |
| queue[top++] = insn; |
| } |
| } |
| |
| private void merge( |
| final int insn, |
| final Frame beforeJSR, |
| final Frame afterRET, |
| final Subroutine subroutineBeforeJSR, |
| final boolean[] access) throws AnalyzerException |
| { |
| if (insn > n - 1) { |
| throw new AnalyzerException("Execution can fall off end of the code"); |
| } |
| |
| Frame oldFrame = frames[insn]; |
| Subroutine oldSubroutine = subroutines[insn]; |
| boolean changes = false; |
| |
| afterRET.merge(beforeJSR, access); |
| |
| if (oldFrame == null) { |
| frames[insn] = newFrame(afterRET); |
| changes = true; |
| } else { |
| changes |= oldFrame.merge(afterRET, access); |
| } |
| |
| newControlFlowEdge(afterRET, oldFrame); |
| |
| if (oldSubroutine == null) { |
| if (subroutineBeforeJSR != null) { |
| subroutines[insn] = subroutineBeforeJSR.copy(); |
| changes = true; |
| } |
| } else { |
| if (subroutineBeforeJSR != null) { |
| changes |= oldSubroutine.merge(subroutineBeforeJSR, !jsr); |
| } |
| } |
| if (changes && !queued[insn]) { |
| queued[insn] = true; |
| queue[top++] = insn; |
| } |
| } |
| } |
