• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Javassist, a Java-bytecode translator toolkit.
3  * Copyright (C) 1999-2007 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 
CodeAnalyzer(CodeAttribute ca)25     public CodeAnalyzer(CodeAttribute ca) {
26         codeAttr = ca;
27         constPool = ca.getConstPool();
28     }
29 
computeMaxStack()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 
initStack(int[] stack, CodeAttribute ca)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 
visitBytecode(CodeIterator ci, int[] stack, int index)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         int[] jsrDepth = new int[1];
78         jsrDepth[0] = -1;
79         while (ci.hasNext()) {
80             index = ci.next();
81             stack[index] = stackDepth;
82             int op = ci.byteAt(index);
83             stackDepth = visitInst(op, ci, index, stackDepth);
84             if (stackDepth < 1)
85                 throw new BadBytecode("stack underflow at " + index);
86 
87             if (processBranch(op, ci, index, codeLength, stack, stackDepth, jsrDepth))
88                 break;
89 
90             if (isEnd(op))     // return, ireturn, athrow, ...
91                 break;
92 
93             if (op == JSR || op == JSR_W)
94                 --stackDepth;
95         }
96     }
97 
processBranch(int opcode, CodeIterator ci, int index, int codeLength, int[] stack, int stackDepth, int[] jsrDepth)98     private boolean processBranch(int opcode, CodeIterator ci, int index,
99                                   int codeLength, int[] stack, int stackDepth, int[] jsrDepth)
100         throws BadBytecode
101     {
102         if ((IFEQ <= opcode && opcode <= IF_ACMPNE)
103                             || opcode == IFNULL || opcode == IFNONNULL) {
104             int target = index + ci.s16bitAt(index + 1);
105             checkTarget(index, target, codeLength, stack, stackDepth);
106         }
107         else {
108             int target, index2;
109             switch (opcode) {
110             case GOTO :
111                 target = index + ci.s16bitAt(index + 1);
112                 checkTarget(index, target, codeLength, stack, stackDepth);
113                 return true;
114             case GOTO_W :
115                 target = index + ci.s32bitAt(index + 1);
116                 checkTarget(index, target, codeLength, stack, stackDepth);
117                 return true;
118             case JSR :
119             case JSR_W :
120                 if (opcode == JSR)
121                     target = index + ci.s16bitAt(index + 1);
122                 else
123                     target = index + ci.s32bitAt(index + 1);
124 
125                 checkTarget(index, target, codeLength, stack, stackDepth);
126                 /*
127                  * It is unknown which RET comes back to this JSR.
128                  * So we assume that if the stack depth at one JSR instruction
129                  * is N, then it is also N at other JSRs and N - 1 at all RET
130                  * instructions.  Note that STACK_GROW[JSR] is 1 since it pushes
131                  * a return address on the operand stack.
132                  */
133                 if (jsrDepth[0] < 0) {
134                     jsrDepth[0] = stackDepth;
135                     return false;
136                 }
137                 else if (stackDepth == jsrDepth[0])
138                     return false;
139                 else
140                     throw new BadBytecode(
141                         "sorry, cannot compute this data flow due to JSR: "
142                             + stackDepth + "," + jsrDepth[0]);
143             case RET :
144                 if (jsrDepth[0] < 0) {
145                     jsrDepth[0] = stackDepth + 1;
146                     return false;
147                 }
148                 else if (stackDepth + 1 == jsrDepth[0])
149                     return true;
150                 else
151                     throw new BadBytecode(
152                         "sorry, cannot compute this data flow due to RET: "
153                             + stackDepth + "," + jsrDepth[0]);
154             case LOOKUPSWITCH :
155             case TABLESWITCH :
156                 index2 = (index & ~3) + 4;
157                 target = index + ci.s32bitAt(index2);
158                 checkTarget(index, target, codeLength, stack, stackDepth);
159                 if (opcode == LOOKUPSWITCH) {
160                     int npairs = ci.s32bitAt(index2 + 4);
161                     index2 += 12;
162                     for (int i = 0; i < npairs; ++i) {
163                         target = index + ci.s32bitAt(index2);
164                         checkTarget(index, target, codeLength,
165                                     stack, stackDepth);
166                         index2 += 8;
167                     }
168                 }
169                 else {
170                     int low = ci.s32bitAt(index2 + 4);
171                     int high = ci.s32bitAt(index2 + 8);
172                     int n = high - low + 1;
173                     index2 += 12;
174                     for (int i = 0; i < n; ++i) {
175                         target = index + ci.s32bitAt(index2);
176                         checkTarget(index, target, codeLength,
177                                     stack, stackDepth);
178                         index2 += 4;
179                     }
180                 }
181 
182                 return true;    // always branch.
183             }
184         }
185 
186         return false;   // may not branch.
187     }
188 
checkTarget(int opIndex, int target, int codeLength, int[] stack, int stackDepth)189     private void checkTarget(int opIndex, int target, int codeLength,
190                              int[] stack, int stackDepth)
191         throws BadBytecode
192     {
193         if (target < 0 || codeLength <= target)
194             throw new BadBytecode("bad branch offset at " + opIndex);
195 
196         int d = stack[target];
197         if (d == 0)
198             stack[target] = -stackDepth;
199         else if (d != stackDepth && d != -stackDepth)
200             throw new BadBytecode("verification error (" + stackDepth +
201                                   "," + d + ") at " + opIndex);
202     }
203 
isEnd(int opcode)204     private static boolean isEnd(int opcode) {
205         return (IRETURN <= opcode && opcode <= RETURN) || opcode == ATHROW;
206     }
207 
208     /**
209      * Visits an instruction.
210      */
visitInst(int op, CodeIterator ci, int index, int stack)211     private int visitInst(int op, CodeIterator ci, int index, int stack)
212         throws BadBytecode
213     {
214         String desc;
215         switch (op) {
216         case GETFIELD :
217             stack += getFieldSize(ci, index) - 1;
218             break;
219         case PUTFIELD :
220             stack -= getFieldSize(ci, index) + 1;
221             break;
222         case GETSTATIC :
223             stack += getFieldSize(ci, index);
224             break;
225         case PUTSTATIC :
226             stack -= getFieldSize(ci, index);
227             break;
228         case INVOKEVIRTUAL :
229         case INVOKESPECIAL :
230             desc = constPool.getMethodrefType(ci.u16bitAt(index + 1));
231             stack += Descriptor.dataSize(desc) - 1;
232             break;
233         case INVOKESTATIC :
234             desc = constPool.getMethodrefType(ci.u16bitAt(index + 1));
235             stack += Descriptor.dataSize(desc);
236             break;
237         case INVOKEINTERFACE :
238             desc = constPool.getInterfaceMethodrefType(
239                                             ci.u16bitAt(index + 1));
240             stack += Descriptor.dataSize(desc) - 1;
241             break;
242         case ATHROW :
243             stack = 1;      // the stack becomes empty (1 means no values).
244             break;
245         case MULTIANEWARRAY :
246             stack += 1 - ci.byteAt(index + 3);
247             break;
248         case WIDE :
249             op = ci.byteAt(index + 1);
250             // don't break here.
251         default :
252             stack += STACK_GROW[op];
253         }
254 
255         return stack;
256     }
257 
getFieldSize(CodeIterator ci, int index)258     private int getFieldSize(CodeIterator ci, int index) {
259         String desc = constPool.getFieldrefType(ci.u16bitAt(index + 1));
260         return Descriptor.dataSize(desc);
261     }
262 }
263