001: /***
002: * ASM: a very small and fast Java bytecode manipulation framework
003: * Copyright (c) 2000-2005 INRIA, France Telecom
004: * All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: * 1. Redistributions of source code must retain the above copyright
010: * notice, this list of conditions and the following disclaimer.
011: * 2. Redistributions in binary form must reproduce the above copyright
012: * notice, this list of conditions and the following disclaimer in the
013: * documentation and/or other materials provided with the distribution.
014: * 3. Neither the name of the copyright holders nor the names of its
015: * contributors may be used to endorse or promote products derived from
016: * this software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
022: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
023: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
024: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
025: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
026: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
027: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
028: * THE POSSIBILITY OF SUCH DAMAGE.
029: */package org.ejb3unit.asm.tree.analysis;
030:
031: import java.util.ArrayList;
032: import java.util.List;
033:
034: import org.ejb3unit.asm.Opcodes;
035: import org.ejb3unit.asm.Type;
036: import org.ejb3unit.asm.tree.AbstractInsnNode;
037: import org.ejb3unit.asm.tree.IincInsnNode;
038: import org.ejb3unit.asm.tree.MethodInsnNode;
039: import org.ejb3unit.asm.tree.MultiANewArrayInsnNode;
040: import org.ejb3unit.asm.tree.VarInsnNode;
041:
042: /**
043: * A symbolic execution stack frame. A stack frame contains a set of local
044: * variable slots, and an operand stack. Warning: long and double values are
045: * represented by <i>two</i> slots in local variables, and by <i>one</i> slot
046: * in the operand stack.
047: *
048: * @author Eric Bruneton
049: */
050: public class Frame {
051:
052: /**
053: * The local variables and operand stack of this frame.
054: */
055: private Value[] values;
056:
057: /**
058: * The number of local variables of this frame.
059: */
060: private int locals;
061:
062: /**
063: * The number of elements in the operand stack.
064: */
065: private int top;
066:
067: /**
068: * Constructs a new frame with the given size.
069: *
070: * @param nLocals the maximum number of local variables of the frame.
071: * @param nStack the maximum stack size of the frame.
072: */
073: public Frame(final int nLocals, final int nStack) {
074: this .values = new Value[nLocals + nStack];
075: this .locals = nLocals;
076: }
077:
078: /**
079: * Constructs a new frame that is identical to the given frame.
080: *
081: * @param src a frame.
082: */
083: public Frame(final Frame src) {
084: this (src.locals, src.values.length - src.locals);
085: init(src);
086: }
087:
088: /**
089: * Copies the state of the given frame into this frame.
090: *
091: * @param src a frame.
092: * @return this frame.
093: */
094: public Frame init(final Frame src) {
095: System.arraycopy(src.values, 0, values, 0, values.length);
096: top = src.top;
097: return this ;
098: }
099:
100: /**
101: * Returns the maximum number of local variables of this frame.
102: *
103: * @return the maximum number of local variables of this frame.
104: */
105: public int getLocals() {
106: return locals;
107: }
108:
109: /**
110: * Returns the value of the given local variable.
111: *
112: * @param i a local variable index.
113: * @return the value of the given local variable.
114: * @throws IndexOutOfBoundsException if the variable does not exist.
115: */
116: public Value getLocal(final int i) throws IndexOutOfBoundsException {
117: if (i >= locals) {
118: throw new IndexOutOfBoundsException(
119: "Trying to access an inexistant local variable");
120: }
121: return values[i];
122: }
123:
124: /**
125: * Sets the value of the given local variable.
126: *
127: * @param i a local variable index.
128: * @param value the new value of this local variable.
129: * @throws IndexOutOfBoundsException if the variable does not exist.
130: */
131: public void setLocal(final int i, final Value value)
132: throws IndexOutOfBoundsException {
133: if (i >= locals) {
134: throw new IndexOutOfBoundsException(
135: "Trying to access an inexistant local variable");
136: }
137: values[i] = value;
138: }
139:
140: /**
141: * Returns the number of values in the operand stack of this frame. Long and
142: * double values are treated as single values.
143: *
144: * @return the number of values in the operand stack of this frame.
145: */
146: public int getStackSize() {
147: return top;
148: }
149:
150: /**
151: * Returns the value of the given operand stack slot.
152: *
153: * @param i the index of an operand stack slot.
154: * @return the value of the given operand stack slot.
155: * @throws IndexOutOfBoundsException if the operand stack slot does not
156: * exist.
157: */
158: public Value getStack(final int i) throws IndexOutOfBoundsException {
159: return values[i + locals];
160: }
161:
162: /**
163: * Clears the operand stack of this frame.
164: */
165: public void clearStack() {
166: top = 0;
167: }
168:
169: /**
170: * Pops a value from the operand stack of this frame.
171: *
172: * @return the value that has been popped from the stack.
173: * @throws IndexOutOfBoundsException if the operand stack is empty.
174: */
175: public Value pop() throws IndexOutOfBoundsException {
176: if (top == 0) {
177: throw new IndexOutOfBoundsException(
178: "Cannot pop operand off an empty stack.");
179: }
180: return values[--top + locals];
181: }
182:
183: /**
184: * Pushes a value into the operand stack of this frame.
185: *
186: * @param value the value that must be pushed into the stack.
187: * @throws IndexOutOfBoundsException if the operand stack is full.
188: */
189: public void push(final Value value)
190: throws IndexOutOfBoundsException {
191: if (top + locals >= values.length) {
192: throw new IndexOutOfBoundsException(
193: "Insufficient maximum stack size.");
194: }
195: values[top++ + locals] = value;
196: }
197:
198: public void execute(final AbstractInsnNode insn,
199: final Interpreter interpreter) throws AnalyzerException {
200: Value value1, value2, value3, value4;
201: List values;
202: int var;
203:
204: switch (insn.getOpcode()) {
205: case Opcodes.NOP:
206: break;
207: case Opcodes.ACONST_NULL:
208: case Opcodes.ICONST_M1:
209: case Opcodes.ICONST_0:
210: case Opcodes.ICONST_1:
211: case Opcodes.ICONST_2:
212: case Opcodes.ICONST_3:
213: case Opcodes.ICONST_4:
214: case Opcodes.ICONST_5:
215: case Opcodes.LCONST_0:
216: case Opcodes.LCONST_1:
217: case Opcodes.FCONST_0:
218: case Opcodes.FCONST_1:
219: case Opcodes.FCONST_2:
220: case Opcodes.DCONST_0:
221: case Opcodes.DCONST_1:
222: case Opcodes.BIPUSH:
223: case Opcodes.SIPUSH:
224: case Opcodes.LDC:
225: push(interpreter.newOperation(insn));
226: break;
227: case Opcodes.ILOAD:
228: case Opcodes.LLOAD:
229: case Opcodes.FLOAD:
230: case Opcodes.DLOAD:
231: case Opcodes.ALOAD:
232: push(interpreter.copyOperation(insn,
233: getLocal(((VarInsnNode) insn).var)));
234: break;
235: case Opcodes.IALOAD:
236: case Opcodes.LALOAD:
237: case Opcodes.FALOAD:
238: case Opcodes.DALOAD:
239: case Opcodes.AALOAD:
240: case Opcodes.BALOAD:
241: case Opcodes.CALOAD:
242: case Opcodes.SALOAD:
243: value2 = pop();
244: value1 = pop();
245: push(interpreter.binaryOperation(insn, value1, value2));
246: break;
247: case Opcodes.ISTORE:
248: case Opcodes.LSTORE:
249: case Opcodes.FSTORE:
250: case Opcodes.DSTORE:
251: case Opcodes.ASTORE:
252: value1 = interpreter.copyOperation(insn, pop());
253: var = ((VarInsnNode) insn).var;
254: setLocal(var, value1);
255: if (value1.getSize() == 2) {
256: setLocal(var + 1, interpreter.newValue(null));
257: }
258: if (var > 0) {
259: Value local = getLocal(var - 1);
260: if (local != null && local.getSize() == 2) {
261: setLocal(var + 1, interpreter.newValue(null));
262: }
263: }
264: break;
265: case Opcodes.IASTORE:
266: case Opcodes.LASTORE:
267: case Opcodes.FASTORE:
268: case Opcodes.DASTORE:
269: case Opcodes.AASTORE:
270: case Opcodes.BASTORE:
271: case Opcodes.CASTORE:
272: case Opcodes.SASTORE:
273: value3 = pop();
274: value2 = pop();
275: value1 = pop();
276: interpreter.ternaryOperation(insn, value1, value2, value3);
277: break;
278: case Opcodes.POP:
279: if (pop().getSize() == 2) {
280: throw new AnalyzerException("Illegal use of POP");
281: }
282: break;
283: case Opcodes.POP2:
284: if (pop().getSize() == 1) {
285: if (pop().getSize() != 1) {
286: throw new AnalyzerException("Illegal use of POP2");
287: }
288: }
289: break;
290: case Opcodes.DUP:
291: value1 = pop();
292: if (value1.getSize() != 1) {
293: throw new AnalyzerException("Illegal use of DUP");
294: }
295: push(interpreter.copyOperation(insn, value1));
296: push(interpreter.copyOperation(insn, value1));
297: break;
298: case Opcodes.DUP_X1:
299: value1 = pop();
300: value2 = pop();
301: if (value1.getSize() != 1 || value2.getSize() != 1) {
302: throw new AnalyzerException("Illegal use of DUP_X1");
303: }
304: push(interpreter.copyOperation(insn, value1));
305: push(interpreter.copyOperation(insn, value2));
306: push(interpreter.copyOperation(insn, value1));
307: break;
308: case Opcodes.DUP_X2:
309: value1 = pop();
310: if (value1.getSize() == 1) {
311: value2 = pop();
312: if (value2.getSize() == 1) {
313: value3 = pop();
314: if (value3.getSize() == 1) {
315: push(interpreter.copyOperation(insn, value1));
316: push(interpreter.copyOperation(insn, value3));
317: push(interpreter.copyOperation(insn, value2));
318: push(interpreter.copyOperation(insn, value1));
319: break;
320: }
321: } else {
322: push(interpreter.copyOperation(insn, value1));
323: push(interpreter.copyOperation(insn, value2));
324: push(interpreter.copyOperation(insn, value1));
325: break;
326: }
327: }
328: throw new AnalyzerException("Illegal use of DUP_X2");
329: case Opcodes.DUP2:
330: value1 = pop();
331: if (value1.getSize() == 1) {
332: value2 = pop();
333: if (value2.getSize() == 1) {
334: push(interpreter.copyOperation(insn, value2));
335: push(interpreter.copyOperation(insn, value1));
336: push(interpreter.copyOperation(insn, value2));
337: push(interpreter.copyOperation(insn, value1));
338: break;
339: }
340: } else {
341: push(interpreter.copyOperation(insn, value1));
342: push(interpreter.copyOperation(insn, value1));
343: break;
344: }
345: throw new AnalyzerException("Illegal use of DUP2");
346: case Opcodes.DUP2_X1:
347: value1 = pop();
348: if (value1.getSize() == 1) {
349: value2 = pop();
350: if (value2.getSize() == 1) {
351: value3 = pop();
352: if (value3.getSize() == 1) {
353: push(interpreter.copyOperation(insn, value2));
354: push(interpreter.copyOperation(insn, value1));
355: push(interpreter.copyOperation(insn, value3));
356: push(interpreter.copyOperation(insn, value2));
357: push(interpreter.copyOperation(insn, value1));
358: break;
359: }
360: }
361: } else {
362: value2 = pop();
363: if (value2.getSize() == 1) {
364: push(interpreter.copyOperation(insn, value1));
365: push(interpreter.copyOperation(insn, value2));
366: push(interpreter.copyOperation(insn, value1));
367: break;
368: }
369: }
370: throw new AnalyzerException("Illegal use of DUP2_X1");
371: case Opcodes.DUP2_X2:
372: value1 = pop();
373: if (value1.getSize() == 1) {
374: value2 = pop();
375: if (value2.getSize() == 1) {
376: value3 = pop();
377: if (value3.getSize() == 1) {
378: value4 = pop();
379: if (value4.getSize() == 1) {
380: push(interpreter
381: .copyOperation(insn, value2));
382: push(interpreter
383: .copyOperation(insn, value1));
384: push(interpreter
385: .copyOperation(insn, value4));
386: push(interpreter
387: .copyOperation(insn, value3));
388: push(interpreter
389: .copyOperation(insn, value2));
390: push(interpreter
391: .copyOperation(insn, value1));
392: break;
393: }
394: } else {
395: push(interpreter.copyOperation(insn, value2));
396: push(interpreter.copyOperation(insn, value1));
397: push(interpreter.copyOperation(insn, value3));
398: push(interpreter.copyOperation(insn, value2));
399: push(interpreter.copyOperation(insn, value1));
400: break;
401: }
402: }
403: } else {
404: value2 = pop();
405: if (value2.getSize() == 1) {
406: value3 = pop();
407: if (value3.getSize() == 1) {
408: push(interpreter.copyOperation(insn, value1));
409: push(interpreter.copyOperation(insn, value3));
410: push(interpreter.copyOperation(insn, value2));
411: push(interpreter.copyOperation(insn, value1));
412: break;
413: }
414: } else {
415: push(interpreter.copyOperation(insn, value1));
416: push(interpreter.copyOperation(insn, value2));
417: push(interpreter.copyOperation(insn, value1));
418: break;
419: }
420: }
421: throw new AnalyzerException("Illegal use of DUP2_X2");
422: case Opcodes.SWAP:
423: value2 = pop();
424: value1 = pop();
425: if (value1.getSize() != 1 || value2.getSize() != 1) {
426: throw new AnalyzerException("Illegal use of SWAP");
427: }
428: push(interpreter.copyOperation(insn, value2));
429: push(interpreter.copyOperation(insn, value1));
430: break;
431: case Opcodes.IADD:
432: case Opcodes.LADD:
433: case Opcodes.FADD:
434: case Opcodes.DADD:
435: case Opcodes.ISUB:
436: case Opcodes.LSUB:
437: case Opcodes.FSUB:
438: case Opcodes.DSUB:
439: case Opcodes.IMUL:
440: case Opcodes.LMUL:
441: case Opcodes.FMUL:
442: case Opcodes.DMUL:
443: case Opcodes.IDIV:
444: case Opcodes.LDIV:
445: case Opcodes.FDIV:
446: case Opcodes.DDIV:
447: case Opcodes.IREM:
448: case Opcodes.LREM:
449: case Opcodes.FREM:
450: case Opcodes.DREM:
451: value2 = pop();
452: value1 = pop();
453: push(interpreter.binaryOperation(insn, value1, value2));
454: break;
455: case Opcodes.INEG:
456: case Opcodes.LNEG:
457: case Opcodes.FNEG:
458: case Opcodes.DNEG:
459: push(interpreter.unaryOperation(insn, pop()));
460: break;
461: case Opcodes.ISHL:
462: case Opcodes.LSHL:
463: case Opcodes.ISHR:
464: case Opcodes.LSHR:
465: case Opcodes.IUSHR:
466: case Opcodes.LUSHR:
467: case Opcodes.IAND:
468: case Opcodes.LAND:
469: case Opcodes.IOR:
470: case Opcodes.LOR:
471: case Opcodes.IXOR:
472: case Opcodes.LXOR:
473: value2 = pop();
474: value1 = pop();
475: push(interpreter.binaryOperation(insn, value1, value2));
476: break;
477: case Opcodes.IINC:
478: var = ((IincInsnNode) insn).var;
479: setLocal(var, interpreter.unaryOperation(insn,
480: getLocal(var)));
481: break;
482: case Opcodes.I2L:
483: case Opcodes.I2F:
484: case Opcodes.I2D:
485: case Opcodes.L2I:
486: case Opcodes.L2F:
487: case Opcodes.L2D:
488: case Opcodes.F2I:
489: case Opcodes.F2L:
490: case Opcodes.F2D:
491: case Opcodes.D2I:
492: case Opcodes.D2L:
493: case Opcodes.D2F:
494: case Opcodes.I2B:
495: case Opcodes.I2C:
496: case Opcodes.I2S:
497: push(interpreter.unaryOperation(insn, pop()));
498: break;
499: case Opcodes.LCMP:
500: case Opcodes.FCMPL:
501: case Opcodes.FCMPG:
502: case Opcodes.DCMPL:
503: case Opcodes.DCMPG:
504: value2 = pop();
505: value1 = pop();
506: push(interpreter.binaryOperation(insn, value1, value2));
507: break;
508: case Opcodes.IFEQ:
509: case Opcodes.IFNE:
510: case Opcodes.IFLT:
511: case Opcodes.IFGE:
512: case Opcodes.IFGT:
513: case Opcodes.IFLE:
514: interpreter.unaryOperation(insn, pop());
515: break;
516: case Opcodes.IF_ICMPEQ:
517: case Opcodes.IF_ICMPNE:
518: case Opcodes.IF_ICMPLT:
519: case Opcodes.IF_ICMPGE:
520: case Opcodes.IF_ICMPGT:
521: case Opcodes.IF_ICMPLE:
522: case Opcodes.IF_ACMPEQ:
523: case Opcodes.IF_ACMPNE:
524: value2 = pop();
525: value1 = pop();
526: interpreter.binaryOperation(insn, value1, value2);
527: break;
528: case Opcodes.GOTO:
529: break;
530: case Opcodes.JSR:
531: push(interpreter.newOperation(insn));
532: break;
533: case Opcodes.RET:
534: break;
535: case Opcodes.TABLESWITCH:
536: case Opcodes.LOOKUPSWITCH:
537: case Opcodes.IRETURN:
538: case Opcodes.LRETURN:
539: case Opcodes.FRETURN:
540: case Opcodes.DRETURN:
541: case Opcodes.ARETURN:
542: interpreter.unaryOperation(insn, pop());
543: break;
544: case Opcodes.RETURN:
545: break;
546: case Opcodes.GETSTATIC:
547: push(interpreter.newOperation(insn));
548: break;
549: case Opcodes.PUTSTATIC:
550: interpreter.unaryOperation(insn, pop());
551: break;
552: case Opcodes.GETFIELD:
553: push(interpreter.unaryOperation(insn, pop()));
554: break;
555: case Opcodes.PUTFIELD:
556: value2 = pop();
557: value1 = pop();
558: interpreter.binaryOperation(insn, value1, value2);
559: break;
560: case Opcodes.INVOKEVIRTUAL:
561: case Opcodes.INVOKESPECIAL:
562: case Opcodes.INVOKESTATIC:
563: case Opcodes.INVOKEINTERFACE:
564: values = new ArrayList();
565: String desc = ((MethodInsnNode) insn).desc;
566: for (int i = Type.getArgumentTypes(desc).length; i > 0; --i) {
567: values.add(0, pop());
568: }
569: if (insn.getOpcode() != Opcodes.INVOKESTATIC) {
570: values.add(0, pop());
571: }
572: if (Type.getReturnType(desc) == Type.VOID_TYPE) {
573: interpreter.naryOperation(insn, values);
574: } else {
575: push(interpreter.naryOperation(insn, values));
576: }
577: break;
578: case Opcodes.NEW:
579: push(interpreter.newOperation(insn));
580: break;
581: case Opcodes.NEWARRAY:
582: case Opcodes.ANEWARRAY:
583: case Opcodes.ARRAYLENGTH:
584: push(interpreter.unaryOperation(insn, pop()));
585: break;
586: case Opcodes.ATHROW:
587: interpreter.unaryOperation(insn, pop());
588: break;
589: case Opcodes.CHECKCAST:
590: case Opcodes.INSTANCEOF:
591: push(interpreter.unaryOperation(insn, pop()));
592: break;
593: case Opcodes.MONITORENTER:
594: case Opcodes.MONITOREXIT:
595: interpreter.unaryOperation(insn, pop());
596: break;
597: case Opcodes.MULTIANEWARRAY:
598: values = new ArrayList();
599: for (int i = ((MultiANewArrayInsnNode) insn).dims; i > 0; --i) {
600: values.add(0, pop());
601: }
602: push(interpreter.naryOperation(insn, values));
603: break;
604: case Opcodes.IFNULL:
605: case Opcodes.IFNONNULL:
606: interpreter.unaryOperation(insn, pop());
607: break;
608: default:
609: throw new RuntimeException("Illegal opcode");
610: }
611: }
612:
613: /**
614: * Merges this frame with the given frame.
615: *
616: * @param frame a frame.
617: * @param interpreter the interpreter used to merge values.
618: * @return <tt>true</tt> if this frame has been changed as a result of the
619: * merge operation, or <tt>false</tt> otherwise.
620: * @throws AnalyzerException if the frames have incompatible sizes.
621: */
622: public boolean merge(final Frame frame,
623: final Interpreter interpreter) throws AnalyzerException {
624: if (top != frame.top) {
625: throw new AnalyzerException("Incompatible stack heights");
626: }
627: boolean changes = false;
628: for (int i = 0; i < locals + top; ++i) {
629: Value v = interpreter.merge(values[i], frame.values[i]);
630: if (v != values[i]) {
631: values[i] = v;
632: changes |= true;
633: }
634: }
635: return changes;
636: }
637:
638: /**
639: * Merges this frame with the given frame (case of a RET instruction).
640: *
641: * @param frame a frame
642: * @param access the local variables that have been accessed by the
643: * subroutine to which the RET instruction corresponds.
644: * @return <tt>true</tt> if this frame has been changed as a result of the
645: * merge operation, or <tt>false</tt> otherwise.
646: */
647: public boolean merge(final Frame frame, final boolean[] access) {
648: boolean changes = false;
649: for (int i = 0; i < locals; ++i) {
650: if (!access[i] && !values[i].equals(frame.values[i])) {
651: values[i] = frame.values[i];
652: changes = true;
653: }
654: }
655: return changes;
656: }
657:
658: /**
659: * Returns a string representation of this frame.
660: *
661: * @return a string representation of this frame.
662: */
663: public String toString() {
664: StringBuffer b = new StringBuffer();
665: for (int i = 0; i < getLocals(); ++i) {
666: b.append(getLocal(i));
667: }
668: b.append(' ');
669: for (int i = 0; i < getStackSize(); ++i) {
670: b.append(getStack(i).toString());
671: }
672: return b.toString();
673: }
674: }
|