diff options
Diffstat (limited to 'tools/external/asm/org/objectweb/asm/tree/analysis/Analyzer.java')
| -rw-r--r-- | tools/external/asm/org/objectweb/asm/tree/analysis/Analyzer.java | 416 |
1 files changed, 416 insertions, 0 deletions
diff --git a/tools/external/asm/org/objectweb/asm/tree/analysis/Analyzer.java b/tools/external/asm/org/objectweb/asm/tree/analysis/Analyzer.java new file mode 100644 index 000000000..9fd402831 --- /dev/null +++ b/tools/external/asm/org/objectweb/asm/tree/analysis/Analyzer.java @@ -0,0 +1,416 @@ +/*** + * 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; + } + } +} |