001: /***
002: * ASM: a very small and fast Java bytecode manipulation framework
003: * Copyright (c) 2000-2005 INRIA, France Telecom
004: * All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: * 1. Redistributions of source code must retain the above copyright
010: * notice, this list of conditions and the following disclaimer.
011: * 2. Redistributions in binary form must reproduce the above copyright
012: * notice, this list of conditions and the following disclaimer in the
013: * documentation and/or other materials provided with the distribution.
014: * 3. Neither the name of the copyright holders nor the names of its
015: * contributors may be used to endorse or promote products derived from
016: * this software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
022: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
023: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
024: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
025: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
026: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
027: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
028: * THE POSSIBILITY OF SUCH DAMAGE.
029: */package org.objectweb.asm.tree.analysis;
030:
031: import java.util.ArrayList;
032: import java.util.List;
033:
034: import org.objectweb.asm.Opcodes;
035: import org.objectweb.asm.Type;
036: import org.objectweb.asm.tree.AbstractInsnNode;
037: import org.objectweb.asm.tree.IincInsnNode;
038: import org.objectweb.asm.tree.InsnList;
039: import org.objectweb.asm.tree.JumpInsnNode;
040: import org.objectweb.asm.tree.LabelNode;
041: import org.objectweb.asm.tree.LookupSwitchInsnNode;
042: import org.objectweb.asm.tree.MethodNode;
043: import org.objectweb.asm.tree.TableSwitchInsnNode;
044: import org.objectweb.asm.tree.TryCatchBlockNode;
045: import org.objectweb.asm.tree.VarInsnNode;
046:
047: /**
048: * A semantic bytecode analyzer.
049: *
050: * @author Eric Bruneton
051: */
052: @SuppressWarnings("unchecked")
053: public class Analyzer implements Opcodes {
054:
055: private Interpreter interpreter;
056:
057: private int n;
058:
059: private InsnList insns;
060:
061: private List[] handlers;
062:
063: private Frame[] frames;
064:
065: private Subroutine[] subroutines;
066:
067: private boolean[] queued;
068:
069: private int[] queue;
070:
071: private int top;
072:
073: private boolean jsr;
074:
075: /**
076: * Constructs a new {@link Analyzer}.
077: *
078: * @param interpreter the interpreter to be used to symbolically interpret
079: * the bytecode instructions.
080: */
081: public Analyzer(final Interpreter interpreter) {
082: this .interpreter = interpreter;
083: }
084:
085: /**
086: * Analyzes the given method.
087: *
088: * @param owner the internal name of the class to which the method belongs.
089: * @param m the method to be analyzed.
090: * @return the symbolic state of the execution stack frame at each bytecode
091: * instruction of the method. The size of the returned array is
092: * equal to the number of instructions (and labels) of the method. A
093: * given frame is <tt>null</tt> if and only if the corresponding
094: * instruction cannot be reached (dead code).
095: * @throws AnalyzerException if a problem occurs during the analysis.
096: */
097: public Frame[] analyze(final String owner, final MethodNode m)
098: throws AnalyzerException {
099: n = m.instructions.size();
100: insns = m.instructions;
101: handlers = new List[n];
102: frames = new Frame[n];
103: subroutines = new Subroutine[n];
104: queued = new boolean[n];
105: queue = new int[n];
106: top = 0;
107:
108: // computes exception handlers for each instruction
109: for (int i = 0; i < m.tryCatchBlocks.size(); ++i) {
110: TryCatchBlockNode tcb = (TryCatchBlockNode) m.tryCatchBlocks
111: .get(i);
112: int begin = insns.indexOf(tcb.start);
113: int end = insns.indexOf(tcb.end);
114: for (int j = begin; j < end; ++j) {
115: List insnHandlers = handlers[j];
116: if (insnHandlers == null) {
117: insnHandlers = new ArrayList();
118: handlers[j] = insnHandlers;
119: }
120: insnHandlers.add(tcb);
121: }
122: }
123:
124: // initializes the data structures for the control flow analysis
125: // algorithm
126: Frame current = newFrame(m.maxLocals, m.maxStack);
127: Frame handler = newFrame(m.maxLocals, m.maxStack);
128: Type[] args = Type.getArgumentTypes(m.desc);
129: int local = 0;
130: if ((m.access & ACC_STATIC) == 0) {
131: Type ctype = Type.getType("L" + owner + ";");
132: current.setLocal(local++, interpreter.newValue(ctype));
133: }
134: for (int i = 0; i < args.length; ++i) {
135: current.setLocal(local++, interpreter.newValue(args[i]));
136: if (args[i].getSize() == 2) {
137: current.setLocal(local++, interpreter.newValue(null));
138: }
139: }
140: while (local < m.maxLocals) {
141: current.setLocal(local++, interpreter.newValue(null));
142: }
143: merge(0, current, null);
144:
145: // control flow analysis
146: while (top > 0) {
147: int insn = queue[--top];
148: Frame f = frames[insn];
149: Subroutine subroutine = subroutines[insn];
150: queued[insn] = false;
151:
152: try {
153: AbstractInsnNode insnNode = m.instructions.get(insn);
154: int insnOpcode = insnNode.getOpcode();
155: int insnType = insnNode.getType();
156: jsr = false;
157:
158: if (insnType == AbstractInsnNode.LABEL
159: || insnType == AbstractInsnNode.LINE
160: || insnType == AbstractInsnNode.FRAME) {
161: merge(insn + 1, f, subroutine);
162: newControlFlowEdge(frames[insn], frames[insn + 1]);
163: } else {
164: current.init(f).execute(insnNode, interpreter);
165: subroutine = subroutine == null ? null : subroutine
166: .copy();
167:
168: if (insnNode instanceof JumpInsnNode) {
169: JumpInsnNode j = (JumpInsnNode) insnNode;
170: if (insnOpcode != GOTO && insnOpcode != JSR) {
171: merge(insn + 1, current, subroutine);
172: newControlFlowEdge(frames[insn],
173: frames[insn + 1]);
174: }
175: int jump = insns.indexOf(j.label);
176: if (insnOpcode == JSR) {
177: jsr = true;
178: merge(jump, current, new Subroutine(
179: j.label, m.maxLocals, j));
180: } else {
181: merge(jump, current, subroutine);
182: }
183: newControlFlowEdge(frames[insn], frames[jump]);
184: } else if (insnNode instanceof LookupSwitchInsnNode) {
185: LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode;
186: int jump = insns.indexOf(lsi.dflt);
187: merge(jump, current, subroutine);
188: newControlFlowEdge(frames[insn], frames[jump]);
189: for (int j = 0; j < lsi.labels.size(); ++j) {
190: LabelNode label = (LabelNode) lsi.labels
191: .get(j);
192: jump = insns.indexOf(label);
193: merge(jump, current, subroutine);
194: newControlFlowEdge(frames[insn],
195: frames[jump]);
196: }
197: } else if (insnNode instanceof TableSwitchInsnNode) {
198: TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode;
199: int jump = insns.indexOf(tsi.dflt);
200: merge(jump, current, subroutine);
201: newControlFlowEdge(frames[insn], frames[jump]);
202: for (int j = 0; j < tsi.labels.size(); ++j) {
203: LabelNode label = (LabelNode) tsi.labels
204: .get(j);
205: jump = insns.indexOf(label);
206: merge(jump, current, subroutine);
207: newControlFlowEdge(frames[insn],
208: frames[jump]);
209: }
210: } else if (insnOpcode == RET) {
211: if (subroutine == null) {
212: throw new AnalyzerException(
213: "RET instruction outside of a sub routine");
214: }
215: for (int i = 0; i < subroutine.callers.size(); ++i) {
216: Object caller = subroutine.callers.get(i);
217: int call = insns
218: .indexOf((AbstractInsnNode) caller);
219: merge(call + 1, frames[call], current,
220: subroutines[call],
221: subroutine.access);
222: newControlFlowEdge(frames[insn],
223: frames[call + 1]);
224: }
225: } else if (insnOpcode != ATHROW
226: && (insnOpcode < IRETURN || insnOpcode > RETURN)) {
227: if (subroutine != null) {
228: if (insnNode instanceof VarInsnNode) {
229: int var = ((VarInsnNode) insnNode).var;
230: subroutine.access[var] = true;
231: if (insnOpcode == LLOAD
232: || insnOpcode == DLOAD
233: || insnOpcode == LSTORE
234: || insnOpcode == DSTORE) {
235: subroutine.access[var + 1] = true;
236: }
237: } else if (insnNode instanceof IincInsnNode) {
238: int var = ((IincInsnNode) insnNode).var;
239: subroutine.access[var] = true;
240: }
241: }
242: merge(insn + 1, current, subroutine);
243: newControlFlowEdge(frames[insn],
244: frames[insn + 1]);
245: }
246: }
247:
248: List insnHandlers = handlers[insn];
249: if (insnHandlers != null) {
250: for (int i = 0; i < insnHandlers.size(); ++i) {
251: TryCatchBlockNode tcb = (TryCatchBlockNode) insnHandlers
252: .get(i);
253: Type type;
254: if (tcb.type == null) {
255: type = Type
256: .getType("Ljava/lang/Throwable;");
257: } else {
258: type = Type.getType("L" + tcb.type + ";");
259: }
260: handler.init(f);
261: handler.clearStack();
262: handler.push(interpreter.newValue(type));
263: int jump = insns.indexOf(tcb.handler);
264: merge(jump, handler, subroutine);
265: newControlFlowExceptionEdge(frames[insn],
266: frames[jump]);
267: }
268: }
269: } catch (AnalyzerException e) {
270: throw new AnalyzerException("Error at instruction "
271: + insn + ": " + e.getMessage(), e);
272: } catch (Exception e) {
273: throw new AnalyzerException("Error at instruction "
274: + insn + ": " + e.getMessage(), e);
275: }
276: }
277:
278: return frames;
279: }
280:
281: /**
282: * Returns the symbolic stack frame for each instruction of the last
283: * recently analyzed method.
284: *
285: * @return the symbolic state of the execution stack frame at each bytecode
286: * instruction of the method. The size of the returned array is
287: * equal to the number of instructions (and labels) of the method. A
288: * given frame is <tt>null</tt> if the corresponding instruction
289: * cannot be reached, or if an error occured during the analysis of
290: * the method.
291: */
292: public Frame[] getFrames() {
293: return frames;
294: }
295:
296: /**
297: * Returns the exception handlers for the given instruction.
298: *
299: * @param insn the index of an instruction of the last recently analyzed
300: * method.
301: * @return a list of {@link TryCatchBlockNode} objects.
302: */
303: public List getHandlers(final int insn) {
304: return handlers[insn];
305: }
306:
307: /**
308: * Constructs a new frame with the given size.
309: *
310: * @param nLocals the maximum number of local variables of the frame.
311: * @param nStack the maximum stack size of the frame.
312: * @return the created frame.
313: */
314: protected Frame newFrame(final int nLocals, final int nStack) {
315: return new Frame(nLocals, nStack);
316: }
317:
318: /**
319: * Constructs a new frame that is identical to the given frame.
320: *
321: * @param src a frame.
322: * @return the created frame.
323: */
324: protected Frame newFrame(final Frame src) {
325: return new Frame(src);
326: }
327:
328: /**
329: * Creates a control flow graph edge. The default implementation of this
330: * method does nothing. It can be overriden in order to construct the
331: * control flow graph of a method (this method is called by the
332: * {@link #analyze analyze} method during its visit of the method's code).
333: *
334: * @param frame the frame corresponding to an instruction.
335: * @param successor the frame corresponding to a successor instruction.
336: */
337: protected void newControlFlowEdge(final Frame frame,
338: final Frame successor) {
339: }
340:
341: /**
342: * Creates a control flow graph edge corresponding to an exception handler.
343: * The default implementation of this method does nothing. It can be
344: * overriden in order to construct the control flow graph of a method (this
345: * method is called by the {@link #analyze analyze} method during its visit
346: * of the method's code).
347: *
348: * @param frame the frame corresponding to an instruction.
349: * @param successor the frame corresponding to a successor instruction.
350: */
351: protected void newControlFlowExceptionEdge(final Frame frame,
352: final Frame successor) {
353: }
354:
355: // -------------------------------------------------------------------------
356:
357: private void merge(final int insn, final Frame frame,
358: final Subroutine subroutine) throws AnalyzerException {
359: if (insn > n - 1) {
360: throw new AnalyzerException(
361: "Execution can fall off end of the code");
362: }
363:
364: Frame oldFrame = frames[insn];
365: Subroutine oldSubroutine = subroutines[insn];
366: boolean changes = false;
367:
368: if (oldFrame == null) {
369: frames[insn] = newFrame(frame);
370: changes = true;
371: } else {
372: changes |= oldFrame.merge(frame, interpreter);
373: }
374:
375: if (oldSubroutine == null) {
376: if (subroutine != null) {
377: subroutines[insn] = subroutine.copy();
378: changes = true;
379: }
380: } else {
381: if (subroutine != null) {
382: changes |= oldSubroutine.merge(subroutine, !jsr);
383: }
384: }
385: if (changes && !queued[insn]) {
386: queued[insn] = true;
387: queue[top++] = insn;
388: }
389: }
390:
391: private void merge(final int insn, final Frame beforeJSR,
392: final Frame afterRET, final Subroutine subroutineBeforeJSR,
393: final boolean[] access) throws AnalyzerException {
394: if (insn > n - 1) {
395: throw new AnalyzerException(
396: "Execution can fall off end of the code");
397: }
398:
399: Frame oldFrame = frames[insn];
400: Subroutine oldSubroutine = subroutines[insn];
401: boolean changes = false;
402:
403: afterRET.merge(beforeJSR, access);
404:
405: if (oldFrame == null) {
406: frames[insn] = newFrame(afterRET);
407: changes = true;
408: } else {
409: changes |= oldFrame.merge(afterRET, access);
410: }
411:
412: if (oldSubroutine == null) {
413: if (subroutineBeforeJSR != null) {
414: subroutines[insn] = subroutineBeforeJSR.copy();
415: changes = true;
416: }
417: } else {
418: if (subroutineBeforeJSR != null) {
419: changes |= oldSubroutine.merge(subroutineBeforeJSR,
420: !jsr);
421: }
422: }
423: if (changes && !queued[insn]) {
424: queued[insn] = true;
425: queue[top++] = insn;
426: }
427: }
428: }
|