Analyzer


1   /***
2    * ASM: a very small and fast Java bytecode manipulation framework
3    * Copyright (c) 2000-2005 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.objectweb.asm.tree.analysis;
31  
32  import java.util.ArrayList  ;
33  import java.util.List  ;
34  
35  import org.objectweb.asm.Opcodes;
36  import org.objectweb.asm.Label;
37  import org.objectweb.asm.Type;
38  import org.objectweb.asm.tree.AbstractInsnNode;
39  import org.objectweb.asm.tree.IincInsnNode;
40  import org.objectweb.asm.tree.JumpInsnNode;
41  import org.objectweb.asm.tree.LabelNode;
42  import org.objectweb.asm.tree.LookupSwitchInsnNode;
43  import org.objectweb.asm.tree.MethodNode;
44  import org.objectweb.asm.tree.TableSwitchInsnNode;
45  import org.objectweb.asm.tree.TryCatchBlockNode;
46  import org.objectweb.asm.tree.VarInsnNode;
47  
48  /**
49   * A semantic bytecode analyzer.
50   * 
51   * @author Eric Bruneton
52   */
53  public class Analyzer implements Opcodes {
54  
55      private Interpreter interpreter;
56  
57      private int n;
58  
59      private IntMap indexes;
60  
61      private List  [] handlers;
62  
63      private Frame[] frames;
64  
65      private Subroutine[] subroutines;
66  
67      private boolean[] queued;
68  
69      private int[] queue;
70  
71      private int top;
72  
73      private boolean jsr;
74  
75      /**
76       * Constructs a new {@link Analyzer}.
77       * 
78       * @param interpreter the interpreter to be used to symbolically interpret
79       *        the bytecode instructions.
80       */
81      public Analyzer(final Interpreter interpreter) {
82          this.interpreter = interpreter;
83      }
84  
85      /**
86       * Analyzes the given method.
87       * 
88       * @param owner the internal name of the class to which the method belongs.
89       * @param m the method to be analyzed.
90       * @return the symbolic state of the execution stack frame at each bytecode
91       *         instruction of the method. The size of the returned array is
92       *         equal to the number of instructions (and labels) of the method. A
93       *         given frame is <tt>null</tt> if and only if the corresponding
94       *         instruction cannot be reached (dead code).
95       * @throws AnalyzerException if a problem occurs during the analysis.
96       */
97      public Frame[] analyze(final String   owner, final MethodNode m)
98              throws AnalyzerException
99      {
100         n = m.instructions.size();
101         indexes = new IntMap(2 * n);
102         handlers = new List  [n];
103         frames = new Frame[n];
104         subroutines = new Subroutine[n];
105         queued = new boolean[n];
106         queue = new int[n];
107         top = 0;
108 
109         // computes instruction indexes
110         for (int i = 0; i < n; ++i) {
111             Object   insn = m.instructions.get(i);
112             if (insn instanceof LabelNode) {
113                 insn = ((LabelNode) insn).label;
114             }
115             indexes.put(insn, i);
116         }
117 
118         // computes exception handlers for each instruction
119         for (int i = 0; i < m.tryCatchBlocks.size(); ++i) {
120             TryCatchBlockNode tcb = (TryCatchBlockNode) m.tryCatchBlocks.get(i);
121             int begin = indexes.get(tcb.start);
122             int end = indexes.get(tcb.end);
123             for (int j = begin; j < end; ++j) {
124                 List   insnHandlers = handlers[j];
125                 if (insnHandlers == null) {
126                     insnHandlers = new ArrayList  ();
127                     handlers[j] = insnHandlers;
128                 }
129                 insnHandlers.add(tcb);
130             }
131         }
132 
133         // initializes the data structures for the control flow analysis
134         // algorithm
135         Frame current = newFrame(m.maxLocals, m.maxStack);
136         Frame handler = newFrame(m.maxLocals, m.maxStack);
137         Type[] args = Type.getArgumentTypes(m.desc);
138         int local = 0;
139         if ((m.access & ACC_STATIC) == 0) {
140             Type ctype = Type.getType("L" + owner + ";");
141             current.setLocal(local++, interpreter.newValue(ctype));
142         }
143         for (int i = 0; i < args.length; ++i) {
144             current.setLocal(local++, interpreter.newValue(args[i]));
145             if (args[i].getSize() == 2) {
146                 current.setLocal(local++, interpreter.newValue(null));
147             }
148         }
149         while (local < m.maxLocals) {
150             current.setLocal(local++, interpreter.newValue(null));
151         }
152         merge(0, current, null);
153 
154         // control flow analysis
155         while (top > 0) {
156             int insn = queue[--top];
157             Frame f = frames[insn];
158             Subroutine subroutine = subroutines[insn];
159             queued[insn] = false;
160 
161             try {
162                 Object   o = m.instructions.get(insn);
163                 jsr = false;
164 
165                 if (o instanceof LabelNode) {
166                     merge(insn + 1, f, subroutine);
167                 } else {
168                     AbstractInsnNode insnNode = (AbstractInsnNode) o;
169                     int insnOpcode = insnNode.getOpcode();
170 
171                     current.init(f).execute(insnNode, interpreter);
172                     subroutine = subroutine == null ? null : subroutine.copy();
173 
174                     if (insnNode instanceof JumpInsnNode) {
175                         JumpInsnNode j = (JumpInsnNode) insnNode;
176                         if (insnOpcode != GOTO && insnOpcode != JSR) {
177                             merge(insn + 1, current, subroutine);
178                         }
179                         if (insnOpcode == JSR) {
180                             jsr = true;
181                             merge(indexes.get(j.label),
182                                     current,
183                                     new Subroutine(j.label, m.maxLocals, j));
184                         } else {
185                             merge(indexes.get(j.label), current, subroutine);
186                         }
187                     } else if (insnNode instanceof LookupSwitchInsnNode) {
188                         LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode;
189                         merge(indexes.get(lsi.dflt), current, subroutine);
190                         for (int j = 0; j < lsi.labels.size(); ++j) {
191                             Label label = (Label) lsi.labels.get(j);
192                             merge(indexes.get(label), current, subroutine);
193                         }
194                     } else if (insnNode instanceof TableSwitchInsnNode) {
195                         TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode;
196                         merge(indexes.get(tsi.dflt), current, subroutine);
197                         for (int j = 0; j < tsi.labels.size(); ++j) {
198                             Label label = (Label) tsi.labels.get(j);
199                             merge(indexes.get(label), current, subroutine);
200                         }
201                     } else if (insnOpcode == RET) {
202                         if (subroutine == null) {
203                             throw new AnalyzerException("RET instruction outside of a sub routine");
204                         }
205                         for (int i = 0; i < subroutine.callers.size(); ++i) {
206                             int caller = indexes.get(subroutine.callers.get(i));
207                             merge(caller + 1,
208                                     frames[caller],
209                                     current,
210                                     subroutines[caller],
211                                     subroutine.access);
212                         }
213                     } else if (insnOpcode != ATHROW
214                             && (insnOpcode < IRETURN || insnOpcode > RETURN))
215                     {
216                         if (subroutine != null) {
217                             if (insnNode instanceof VarInsnNode) {
218                                 int var = ((VarInsnNode) insnNode).var;
219                                 subroutine.access[var] = true;
220                                 if (insnOpcode == LLOAD || insnOpcode == DLOAD
221                                         || insnOpcode == LSTORE
222                                         || insnOpcode == DSTORE)
223                                 {
224                                     subroutine.access[var + 1] = true;
225                                 }
226                             } else if (insnNode instanceof IincInsnNode) {
227                                 int var = ((IincInsnNode) insnNode).var;
228                                 subroutine.access[var] = true;
229                             }
230                         }
231                         merge(insn + 1, current, subroutine);
232                     }
233                 }
234 
235                 List   insnHandlers = handlers[insn];
236                 if (insnHandlers != null) {
237                     for (int i = 0; i < insnHandlers.size(); ++i) {
238                         TryCatchBlockNode tcb = (TryCatchBlockNode) insnHandlers.get(i);
239                         Type type;
240                         if (tcb.type == null) {
241                             type = Type.getType("Ljava/lang/Throwable;");
242                         } else {
243                             type = Type.getType("L" + tcb.type + ";");
244                         }
245                         handler.init(f);
246                         handler.clearStack();
247                         handler.push(interpreter.newValue(type));
248                         merge(indexes.get(tcb.handler), handler, subroutine);
249                     }
250                 }
251             } catch (AnalyzerException e) {
252                 throw new AnalyzerException("Error at instruction " + insn
253                         + ": " + e.getMessage(), e);
254             }
255         }
256 
257         return frames;
258     }
259 
260     /**
261      * Returns the symbolic stack frame for each instruction of the last
262      * recently analyzed method.
263      * 
264      * @return the symbolic state of the execution stack frame at each bytecode
265      *         instruction of the method. The size of the returned array is
266      *         equal to the number of instructions (and labels) of the method. A
267      *         given frame is <tt>null</tt> if the corresponding instruction
268      *         cannot be reached, or if an error occured during the analysis of
269      *         the method.
270      */
271     public Frame[] getFrames() {
272         return frames;
273     }
274 
275     /**
276      * Returns the index of the given instruction.
277      * 
278      * @param insn a {@link Label} or {@link AbstractInsnNode} of the last
279      *        recently analyzed method.
280      * @return the index of the given instruction of the last recently analyzed
281      *         method.
282      */
283     public int getIndex(final Object   insn) {
284         return indexes.get(insn);
285     }
286 
287     /**
288      * Returns the exception handlers for the given instruction.
289      * 
290      * @param insn the index of an instruction of the last recently analyzed
291      *        method.
292      * @return a list of {@link TryCatchBlockNode} objects.
293      */
294     public List   getHandlers(final int insn) {
295         return handlers[insn];
296     }
297 
298     /**
299      * Constructs a new frame with the given size.
300      * 
301      * @param nLocals the maximum number of local variables of the frame.
302      * @param nStack the maximum stack size of the frame.
303      * @return the created frame.
304      */
305     protected Frame newFrame(final int nLocals, final int nStack) {
306         return new Frame(nLocals, nStack);
307     }
308 
309     /**
310      * Constructs a new frame that is identical to the given frame.
311      * 
312      * @param src a frame.
313      * @return the created frame.
314      */
315     protected Frame newFrame(final Frame src) {
316         return new Frame(src);
317     }
318 
319     /**
320      * Creates a control flow graph edge. The default implementation of this
321      * method does nothing. It can be overriden in order to construct the
322      * control flow graph of a method (this method is called by the
323      * {@link #analyze analyze} method during its visit of the method's code).
324      * 
325      * @param frame the frame corresponding to an instruction.
326      * @param successor the frame corresponding to a successor instruction.
327      */
328     protected void newControlFlowEdge(final Frame frame, final Frame successor)
329     {
330     }
331 
332     // -------------------------------------------------------------------------
333 
334     private void merge(
335         final int insn,
336         final Frame frame,
337         final Subroutine subroutine) throws AnalyzerException
338     {
339         if (insn > n - 1) {
340             throw new AnalyzerException("Execution can fall off end of the code");
341         }
342 
343         Frame oldFrame = frames[insn];
344         Subroutine oldSubroutine = subroutines[insn];
345         boolean changes = false;
346 
347         if (oldFrame == null) {
348             frames[insn] = newFrame(frame);
349             changes = true;
350         } else {
351             changes |= oldFrame.merge(frame, interpreter);
352         }
353 
354         newControlFlowEdge(frame, oldFrame);
355 
356         if (oldSubroutine == null) {
357             if (subroutine != null) {
358                 subroutines[insn] = subroutine.copy();
359                 changes = true;
360             }
361         } else {
362             if (subroutine != null) {
363                 changes |= oldSubroutine.merge(subroutine, !jsr);
364             }
365         }
366         if (changes && !queued[insn]) {
367             queued[insn] = true;
368             queue[top++] = insn;
369         }
370     }
371 
372     private void merge(
373         final int insn,
374         final Frame beforeJSR,
375         final Frame afterRET,
376         final Subroutine subroutineBeforeJSR,
377         final boolean[] access) throws AnalyzerException
378     {
379         if (insn > n - 1) {
380             throw new AnalyzerException("Execution can fall off end of the code");
381         }
382 
383         Frame oldFrame = frames[insn];
384         Subroutine oldSubroutine = subroutines[insn];
385         boolean changes = false;
386 
387         afterRET.merge(beforeJSR, access);
388 
389         if (oldFrame == null) {
390             frames[insn] = newFrame(afterRET);
391             changes = true;
392         } else {
393             changes |= oldFrame.merge(afterRET, access);
394         }
395 
396         newControlFlowEdge(afterRET, oldFrame);
397 
398         if (oldSubroutine == null) {
399             if (subroutineBeforeJSR != null) {
400                 subroutines[insn] = subroutineBeforeJSR.copy();
401                 changes = true;
402             }
403         } else {
404             if (subroutineBeforeJSR != null) {
405                 changes |= oldSubroutine.merge(subroutineBeforeJSR, !jsr);
406             }
407         }
408         if (changes && !queued[insn]) {
409             queued[insn] = true;
410             queue[top++] = insn;
411         }
412     }
413 }
414
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags