001: /*
002: * Javassist, a Java-bytecode translator toolkit.
003: * Copyright (C) 1999-2006 Shigeru Chiba. All Rights Reserved.
004: *
005: * The contents of this file are subject to the Mozilla Public License Version
006: * 1.1 (the "License"); you may not use this file except in compliance with
007: * the License. Alternatively, the contents of this file may be used under
008: * the terms of the GNU Lesser General Public License Version 2.1 or later.
009: *
010: * Software distributed under the License is distributed on an "AS IS" basis,
011: * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
012: * for the specific language governing rights and limitations under the
013: * License.
014: */
015:
016: package javassist.bytecode;
017:
018: /**
019: * Utility for computing <code>max_stack</code>.
020: */
021: class CodeAnalyzer implements Opcode {
022: private ConstPool constPool;
023: private CodeAttribute codeAttr;
024:
025: public CodeAnalyzer(CodeAttribute ca) {
026: codeAttr = ca;
027: constPool = ca.getConstPool();
028: }
029:
030: public int computeMaxStack() throws BadBytecode {
031: /* d = stack[i]
032: * d == 0: not visited
033: * d > 0: the depth is d - 1 after executing the bytecode at i.
034: * d < 0: not visited. the initial depth (before execution) is 1 - d.
035: */
036: CodeIterator ci = codeAttr.iterator();
037: int length = ci.getCodeLength();
038: int[] stack = new int[length];
039: constPool = codeAttr.getConstPool();
040: initStack(stack, codeAttr);
041: boolean repeat;
042: do {
043: repeat = false;
044: for (int i = 0; i < length; ++i)
045: if (stack[i] < 0) {
046: repeat = true;
047: visitBytecode(ci, stack, i);
048: }
049: } while (repeat);
050:
051: int maxStack = 1;
052: for (int i = 0; i < length; ++i)
053: if (stack[i] > maxStack)
054: maxStack = stack[i];
055:
056: return maxStack - 1; // the base is 1.
057: }
058:
059: private void initStack(int[] stack, CodeAttribute ca) {
060: stack[0] = -1;
061: ExceptionTable et = ca.getExceptionTable();
062: if (et != null) {
063: int size = et.size();
064: for (int i = 0; i < size; ++i)
065: stack[et.handlerPc(i)] = -2; // an exception is on stack
066: }
067: }
068:
069: private void visitBytecode(CodeIterator ci, int[] stack, int index)
070: throws BadBytecode {
071: int codeLength = stack.length;
072: ci.move(index);
073: int stackDepth = -stack[index];
074: while (ci.hasNext()) {
075: index = ci.next();
076: stack[index] = stackDepth;
077: int op = ci.byteAt(index);
078: stackDepth = visitInst(op, ci, index, stackDepth);
079: if (stackDepth < 1)
080: throw new BadBytecode("stack underflow at " + index);
081:
082: if (processBranch(op, ci, index, codeLength, stack,
083: stackDepth))
084: break;
085:
086: if (isEnd(op)) // return, ireturn, athrow, ...
087: break;
088:
089: if (op == JSR || op == JSR_W)
090: --stackDepth;
091: }
092: }
093:
094: private boolean processBranch(int opcode, CodeIterator ci,
095: int index, int codeLength, int[] stack, int stackDepth)
096: throws BadBytecode {
097: if ((IFEQ <= opcode && opcode <= IF_ACMPNE) || opcode == IFNULL
098: || opcode == IFNONNULL) {
099: int target = index + ci.s16bitAt(index + 1);
100: checkTarget(index, target, codeLength, stack, stackDepth);
101: } else {
102: int target, index2;
103: switch (opcode) {
104: case GOTO:
105: target = index + ci.s16bitAt(index + 1);
106: checkTarget(index, target, codeLength, stack,
107: stackDepth);
108: return true;
109: case GOTO_W:
110: target = index + ci.s32bitAt(index + 1);
111: checkTarget(index, target, codeLength, stack,
112: stackDepth);
113: return true;
114: case JSR:
115: case JSR_W:
116: if (opcode == JSR)
117: target = index + ci.s16bitAt(index + 1);
118: else
119: target = index + ci.s32bitAt(index + 1);
120:
121: checkTarget(index, target, codeLength, stack,
122: stackDepth);
123: if (stackDepth == 2) // stackDepth is 1 if empty
124: return false;
125: else
126: throw new BadBytecode(
127: "sorry, cannot compute this data flow due to JSR");
128: case RET:
129: if (stackDepth == 1) // stackDepth is 1 if empty
130: return true;
131: else
132: throw new BadBytecode(
133: "sorry, cannot compute this data flow due to RET");
134: case LOOKUPSWITCH:
135: case TABLESWITCH:
136: index2 = (index & ~3) + 4;
137: target = index + ci.s32bitAt(index2);
138: checkTarget(index, target, codeLength, stack,
139: 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, stack,
146: stackDepth);
147: index2 += 8;
148: }
149: } else {
150: int low = ci.s32bitAt(index2 + 4);
151: int high = ci.s32bitAt(index2 + 8);
152: int n = high - low + 1;
153: index2 += 12;
154: for (int i = 0; i < n; ++i) {
155: target = index + ci.s32bitAt(index2);
156: checkTarget(index, target, codeLength, stack,
157: stackDepth);
158: index2 += 4;
159: }
160: }
161:
162: return true; // always branch.
163: }
164: }
165:
166: return false; // may not branch.
167: }
168:
169: private void checkTarget(int opIndex, int target, int codeLength,
170: int[] stack, int stackDepth) throws BadBytecode {
171: if (target < 0 || codeLength <= target)
172: throw new BadBytecode("bad branch offset at " + opIndex);
173:
174: int d = stack[target];
175: if (d == 0)
176: stack[target] = -stackDepth;
177: else if (d != stackDepth && d != -stackDepth)
178: throw new BadBytecode("verification error (" + stackDepth
179: + "," + d + ") at " + opIndex);
180: }
181:
182: private static boolean isEnd(int opcode) {
183: return (IRETURN <= opcode && opcode <= RETURN)
184: || opcode == ATHROW;
185: }
186:
187: /**
188: * Visits an instruction.
189: */
190: private int visitInst(int op, CodeIterator ci, int index, int stack)
191: throws BadBytecode {
192: String desc;
193: switch (op) {
194: case GETFIELD:
195: stack += getFieldSize(ci, index) - 1;
196: break;
197: case PUTFIELD:
198: stack -= getFieldSize(ci, index) + 1;
199: break;
200: case GETSTATIC:
201: stack += getFieldSize(ci, index);
202: break;
203: case PUTSTATIC:
204: stack -= getFieldSize(ci, index);
205: break;
206: case INVOKEVIRTUAL:
207: case INVOKESPECIAL:
208: desc = constPool.getMethodrefType(ci.u16bitAt(index + 1));
209: stack += Descriptor.dataSize(desc) - 1;
210: break;
211: case INVOKESTATIC:
212: desc = constPool.getMethodrefType(ci.u16bitAt(index + 1));
213: stack += Descriptor.dataSize(desc);
214: break;
215: case INVOKEINTERFACE:
216: desc = constPool.getInterfaceMethodrefType(ci
217: .u16bitAt(index + 1));
218: stack += Descriptor.dataSize(desc) - 1;
219: break;
220: case ATHROW:
221: stack = 1; // the stack becomes empty (1 means no values).
222: break;
223: case MULTIANEWARRAY:
224: stack += 1 - ci.byteAt(index + 3);
225: break;
226: case WIDE:
227: op = ci.byteAt(index + 1);
228: // don't break here.
229: default:
230: stack += STACK_GROW[op];
231: }
232:
233: return stack;
234: }
235:
236: private int getFieldSize(CodeIterator ci, int index) {
237: String desc = constPool.getFieldrefType(ci.u16bitAt(index + 1));
238: return Descriptor.dataSize(desc);
239: }
240: }
|