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 com.tc.asm.tree.analysis;
31  
32  import java.util.ArrayList  ;
33  import java.util.List  ;
34  
35  import com.tc.asm.Opcodes;
36  import com.tc.asm.Label;
37  import com.tc.asm.Type;
38  import com.tc.asm.tree.AbstractInsnNode;
39  import com.tc.asm.tree.IincInsnNode;
40  import com.tc.asm.tree.JumpInsnNode;
41  import com.tc.asm.tree.LabelNode;
42  import com.tc.asm.tree.LookupSwitchInsnNode;
43  import com.tc.asm.tree.MethodNode;
44  import com.tc.asm.tree.TableSwitchInsnNode;
45  import com.tc.asm.tree.TryCatchBlockNode;
46  import com.tc.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             } catch(Exception   e) {
255                 throw new AnalyzerException("Error at instruction " + insn
256                         + ": " + e.getMessage(), e);
257             }
258         }
259 
260         return frames;
261     }
262 
263     /**
264      * Returns the symbolic stack frame for each instruction of the last
265      * recently analyzed method.
266      * 
267      * @return the symbolic state of the execution stack frame at each bytecode
268      *         instruction of the method. The size of the returned array is
269      *         equal to the number of instructions (and labels) of the method. A
270      *         given frame is <tt>null</tt> if the corresponding instruction
271      *         cannot be reached, or if an error occured during the analysis of
272      *         the method.
273      */
274     public Frame[] getFrames() {
275         return frames;
276     }
277 
278     /**
279      * Returns the index of the given instruction.
280      * 
281      * @param insn a {@link Label} or {@link AbstractInsnNode} of the last
282      *        recently analyzed method.
283      * @return the index of the given instruction of the last recently analyzed
284      *         method.
285      */
286     public int getIndex(final Object   insn) {
287         return indexes.get(insn);
288     }
289 
290     /**
291      * Returns the exception handlers for the given instruction.
292      * 
293      * @param insn the index of an instruction of the last recently analyzed
294      *        method.
295      * @return a list of {@link TryCatchBlockNode} objects.
296      */
297     public List   getHandlers(final int insn) {
298         return handlers[insn];
299     }
300 
301     /**
302      * Constructs a new frame with the given size.
303      * 
304      * @param nLocals the maximum number of local variables of the frame.
305      * @param nStack the maximum stack size of the frame.
306      * @return the created frame.
307      */
308     protected Frame newFrame(final int nLocals, final int nStack) {
309         return new Frame(nLocals, nStack);
310     }
311 
312     /**
313      * Constructs a new frame that is identical to the given frame.
314      * 
315      * @param src a frame.
316      * @return the created frame.
317      */
318     protected Frame newFrame(final Frame src) {
319         return new Frame(src);
320     }
321 
322     /**
323      * Creates a control flow graph edge. The default implementation of this
324      * method does nothing. It can be overriden in order to construct the
325      * control flow graph of a method (this method is called by the
326      * {@link #analyze analyze} method during its visit of the method's code).
327      * 
328      * @param frame the frame corresponding to an instruction.
329      * @param successor the frame corresponding to a successor instruction.
330      */
331     protected void newControlFlowEdge(final Frame frame, final Frame successor)
332     {
333     }
334 
335     // -------------------------------------------------------------------------
336 
337     private void merge(
338         final int insn,
339         final Frame frame,
340         final Subroutine subroutine) throws AnalyzerException
341     {
342         if (insn > n - 1) {
343             throw new AnalyzerException("Execution can fall off end of the code");
344         }
345 
346         Frame oldFrame = frames[insn];
347         Subroutine oldSubroutine = subroutines[insn];
348         boolean changes = false;
349 
350         if (oldFrame == null) {
351             frames[insn] = newFrame(frame);
352             changes = true;
353         } else {
354             changes |= oldFrame.merge(frame, interpreter);
355         }
356 
357         newControlFlowEdge(frame, oldFrame);
358 
359         if (oldSubroutine == null) {
360             if (subroutine != null) {
361                 subroutines[insn] = subroutine.copy();
362                 changes = true;
363             }
364         } else {
365             if (subroutine != null) {
366                 changes |= oldSubroutine.merge(subroutine, !jsr);
367             }
368         }
369         if (changes && !queued[insn]) {
370             queued[insn] = true;
371             queue[top++] = insn;
372         }
373     }
374 
375     private void merge(
376         final int insn,
377         final Frame beforeJSR,
378         final Frame afterRET,
379         final Subroutine subroutineBeforeJSR,
380         final boolean[] access) throws AnalyzerException
381     {
382         if (insn > n - 1) {
383             throw new AnalyzerException("Execution can fall off end of the code");
384         }
385 
386         Frame oldFrame = frames[insn];
387         Subroutine oldSubroutine = subroutines[insn];
388         boolean changes = false;
389 
390         afterRET.merge(beforeJSR, access);
391 
392         if (oldFrame == null) {
393             frames[insn] = newFrame(afterRET);
394             changes = true;
395         } else {
396             changes |= oldFrame.merge(afterRET, access);
397         }
398 
399         newControlFlowEdge(afterRET, oldFrame);
400 
401         if (oldSubroutine == null) {
402             if (subroutineBeforeJSR != null) {
403                 subroutines[insn] = subroutineBeforeJSR.copy();
404                 changes = true;
405             }
406         } else {
407             if (subroutineBeforeJSR != null) {
408                 changes |= oldSubroutine.merge(subroutineBeforeJSR, !jsr);
409             }
410         }
411         if (changes && !queued[insn]) {
412             queued[insn] = true;
413             queue[top++] = insn;
414         }
415     }
416 }
417
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags