CodeAnalyzer


1   /*
2    * Javassist, a Java-bytecode translator toolkit.
3    * Copyright (C) 1999-2005 Shigeru Chiba. All Rights Reserved.
4    *
5    * The contents of this file are subject to the Mozilla Public License Version
6    * 1.1 (the "License"); you may not use this file except in compliance with
7    * the License.  Alternatively, the contents of this file may be used under
8    * the terms of the GNU Lesser General Public License Version 2.1 or later.
9    *
10   * Software distributed under the License is distributed on an "AS IS" basis,
11   * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12   * for the specific language governing rights and limitations under the
13   * License.
14   */
15  
16  package javassist.bytecode;
17  
18  /**
19   * Utility for computing <code>max_stack</code>.
20   */
21  class CodeAnalyzer implements Opcode {
22      private ConstPool constPool;
23      private CodeAttribute codeAttr;
24  
25      public CodeAnalyzer(CodeAttribute ca) {
26          codeAttr = ca;
27          constPool = ca.getConstPool();
28      }
29  
30      public int computeMaxStack()
31          throws BadBytecode
32      {
33          /* d = stack[i]
34           * d == 0: not visited
35           * d > 0: the depth is d - 1 after executing the bytecode at i.
36           * d < 0: not visited. the initial depth (before execution) is 1 - d.
37           */
38          CodeIterator ci = codeAttr.iterator();
39          int length = ci.getCodeLength();
40          int[] stack = new int[length];
41          constPool = codeAttr.getConstPool();
42          initStack(stack, codeAttr);
43          boolean repeat;
44          do {
45              repeat = false;
46              for (int i = 0; i < length; ++i)
47                  if (stack[i] < 0) {
48                      repeat = true;
49                      visitBytecode(ci, stack, i);
50                  }
51          } while (repeat);
52  
53          int maxStack = 1;
54          for (int i = 0; i < length; ++i)
55              if (stack[i] > maxStack)
56                  maxStack = stack[i];
57  
58          return maxStack - 1;    // the base is 1.
59      }
60  
61      private void initStack(int[] stack, CodeAttribute ca) {
62          stack[0] = -1;
63          ExceptionTable et = ca.getExceptionTable();
64          if (et != null) {
65              int size = et.size();
66              for (int i = 0; i < size; ++i)
67                  stack[et.handlerPc(i)] = -2;    // an exception is on stack
68          }
69      }
70  
71      private void visitBytecode(CodeIterator ci, int[] stack, int index)
72          throws BadBytecode
73      {
74          int codeLength = stack.length;
75          ci.move(index);
76          int stackDepth = -stack[index];
77          while (ci.hasNext()) {
78              index = ci.next();
79              stack[index] = stackDepth;
80              int op = ci.byteAt(index);
81              stackDepth = visitInst(op, ci, index, stackDepth);
82              if (stackDepth < 1)
83                  throw new BadBytecode("stack underflow at " + index);
84  
85              if (processBranch(op, ci, index, codeLength, stack, stackDepth))
86                  break;
87  
88              if (isEnd(op))     // return, ireturn, athrow, ...
89                  break;
90  
91              if (op == JSR || op == JSR_W)
92                  --stackDepth;
93          }
94      }
95  
96      private boolean processBranch(int opcode, CodeIterator ci, int index,
97                                    int codeLength, int[] stack, int stackDepth)
98          throws BadBytecode
99      {
100         if ((IFEQ <= opcode && opcode <= IF_ACMPNE)
101                             || opcode == IFNULL || opcode == IFNONNULL) {
102             int target = index + ci.s16bitAt(index + 1);
103             checkTarget(index, target, codeLength, stack, stackDepth);
104         }
105         else {
106             int target, index2;
107             switch (opcode) {
108             case GOTO :
109                 target = index + ci.s16bitAt(index + 1);
110                 checkTarget(index, target, codeLength, stack, stackDepth);
111                 return true;
112             case GOTO_W :
113                 target = index + ci.s32bitAt(index + 1);
114                 checkTarget(index, target, codeLength, stack, stackDepth);
115                 return true;
116             case JSR :
117             case JSR_W :
118                 if (opcode == JSR)
119                     target = index + ci.s16bitAt(index + 1);
120                 else
121                     target = index + ci.s32bitAt(index + 1);
122 
123                 checkTarget(index, target, codeLength, stack, stackDepth);
124                 if (stackDepth == 2)    // stackDepth is 1 if empty
125                     return false;
126                 else
127                     throw new BadBytecode(
128                         "sorry, cannot compute this data flow due to JSR");
129             case RET :
130                 if (stackDepth == 1)    // stackDepth is 1 if empty
131                     return true;
132                 else
133                     throw new BadBytecode(
134                         "sorry, cannot compute this data flow due to RET");
135             case LOOKUPSWITCH :
136             case TABLESWITCH :
137                 index2 = (index & ~3) + 4;
138                 target = index + ci.s32bitAt(index2);
139                 checkTarget(index, target, codeLength, stack, stackDepth);
140                 if (opcode == LOOKUPSWITCH) {
141                     int npairs = ci.s32bitAt(index2 + 4);
142                     index2 += 12;
143                     for (int i = 0; i < npairs; ++i) {
144                         target = index + ci.s32bitAt(index2);
145                         checkTarget(index, target, codeLength,
146                                     stack, stackDepth);
147                         index2 += 8;
148                     }
149                 }
150                 else {
151                     int low = ci.s32bitAt(index2 + 4);
152                     int high = ci.s32bitAt(index2 + 8);
153                     int n = high - low + 1;
154                     index2 += 12;
155                     for (int i = 0; i < n; ++i) {
156                         target = index + ci.s32bitAt(index2);
157                         checkTarget(index, target, codeLength,
158                                     stack, stackDepth);
159                         index2 += 4;
160                     }
161                 }
162 
163                 return true;    // always branch.
164             }
165         }
166 
167         return false;   // may not branch.
168     }
169 
170     private void checkTarget(int opIndex, int target, int codeLength,
171                              int[] stack, int stackDepth)
172         throws BadBytecode
173     {
174         if (target < 0 || codeLength <= target)
175             throw new BadBytecode("bad branch offset at " + opIndex);
176 
177         int d = stack[target];
178         if (d == 0)
179             stack[target] = -stackDepth;
180         else if (d != stackDepth && d != -stackDepth)
181             throw new BadBytecode("verification error (" + stackDepth +
182                                   "," + d + ") at " + opIndex);
183     }
184                              
185     private static boolean isEnd(int opcode) {
186         return (IRETURN <= opcode && opcode <= RETURN) || opcode == ATHROW; 
187     }
188 
189     /**
190      * Visits an instruction.
191      */
192     private int visitInst(int op, CodeIterator ci, int index, int stack)
193         throws BadBytecode
194     {
195         String   desc;
196         switch (op) {
197         case GETFIELD :
198             stack += getFieldSize(ci, index) - 1;
199             break;
200         case PUTFIELD :
201             stack -= getFieldSize(ci, index) + 1;
202             break;
203         case GETSTATIC :
204             stack += getFieldSize(ci, index);
205             break;
206         case PUTSTATIC :
207             stack -= getFieldSize(ci, index);
208             break;
209         case INVOKEVIRTUAL :
210         case INVOKESPECIAL :
211             desc = constPool.getMethodrefType(ci.u16bitAt(index + 1));
212             stack += Descriptor.dataSize(desc) - 1;
213             break;
214         case INVOKESTATIC :
215             desc = constPool.getMethodrefType(ci.u16bitAt(index + 1));
216             stack += Descriptor.dataSize(desc);
217             break;
218         case INVOKEINTERFACE :
219             desc = constPool.getInterfaceMethodrefType(
220                                             ci.u16bitAt(index + 1));
221             stack += Descriptor.dataSize(desc) - 1;
222             break;
223         case ATHROW :
224             stack = 1;      // the stack becomes empty (1 means no values).
225             break;
226         case MULTIANEWARRAY :
227             stack += 1 - ci.byteAt(index + 3);
228             break;
229         case WIDE :
230             op = ci.byteAt(index + 1);
231             // don't break here.
232         default :
233             stack += STACK_GROW[op];
234         }
235 
236         return stack;
237     }
238 
239     private int getFieldSize(CodeIterator ci, int index) {
240         String   desc = constPool.getFieldrefType(ci.u16bitAt(index + 1));
241         return Descriptor.dataSize(desc);
242     }
243 }
244
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags