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