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