Frame


1   /***
2    * ASM: a very small and fast Java bytecode manipulation framework
3    * Copyright (c) 2000-2005 INRIA, France Telecom
4    * All rights reserved.
5    *
6    * Redistribution and use in source and binary forms, with or without
7    * modification, are permitted provided that the following conditions
8    * are met:
9    * 1. Redistributions of source code must retain the above copyright
10   *    notice, this list of conditions and the following disclaimer.
11   * 2. Redistributions in binary form must reproduce the above copyright
12   *    notice, this list of conditions and the following disclaimer in the
13   *    documentation and/or other materials provided with the distribution.
14   * 3. Neither the name of the copyright holders nor the names of its
15   *    contributors may be used to endorse or promote products derived from
16   *    this software without specific prior written permission.
17   *
18   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21   * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22   * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23   * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24   * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25   * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26   * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27   * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
28   * THE POSSIBILITY OF SUCH DAMAGE.
29   */
30  package com.tc.asm.tree.analysis;
31  
32  import java.util.ArrayList  ;
33  import java.util.List  ;
34  
35  import com.tc.asm.Opcodes;
36  import com.tc.asm.Type;
37  import com.tc.asm.tree.AbstractInsnNode;
38  import com.tc.asm.tree.IincInsnNode;
39  import com.tc.asm.tree.MethodInsnNode;
40  import com.tc.asm.tree.MultiANewArrayInsnNode;
41  import com.tc.asm.tree.VarInsnNode;
42  
43  /**
44   * A symbolic execution stack frame. A stack frame contains a set of local
45   * variable slots, and an operand stack. Warning: long and double values are
46   * represented by <i>two</i> slots in local variables, and by <i>one</i> slot
47   * in the operand stack.
48   * 
49   * @author Eric Bruneton
50   */
51  public class Frame {
52  
53      /**
54       * The local variables and operand stack of this frame.
55       */
56      private Value[] values;
57  
58      /**
59       * The number of local variables of this frame.
60       */
61      private int locals;
62  
63      /**
64       * The number of elements in the operand stack.
65       */
66      private int top;
67  
68      /**
69       * Constructs a new frame with the given size.
70       * 
71       * @param nLocals the maximum number of local variables of the frame.
72       * @param nStack the maximum stack size of the frame.
73       */
74      public Frame(final int nLocals, final int nStack) {
75          this.values = new Value[nLocals + nStack];
76          this.locals = nLocals;
77      }
78  
79      /**
80       * Constructs a new frame that is identical to the given frame.
81       * 
82       * @param src a frame.
83       */
84      public Frame(final Frame src) {
85          this(src.locals, src.values.length - src.locals);
86          init(src);
87      }
88  
89      /**
90       * Copies the state of the given frame into this frame.
91       * 
92       * @param src a frame.
93       * @return this frame.
94       */
95      public Frame init(final Frame src) {
96          System.arraycopy(src.values, 0, values, 0, values.length);
97          top = src.top;
98          return this;
99      }
100 
101     /**
102      * Returns the maximum number of local variables of this frame.
103      * 
104      * @return the maximum number of local variables of this frame.
105      */
106     public int getLocals() {
107         return locals;
108     }
109 
110     /**
111      * Returns the value of the given local variable.
112      * 
113      * @param i a local variable index.
114      * @return the value of the given local variable.
115      * @throws IndexOutOfBoundsException if the variable does not exist.
116      */
117     public Value getLocal(final int i) throws IndexOutOfBoundsException   {
118         if (i >= locals) {
119             throw new IndexOutOfBoundsException  ("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     {
134         if (i >= locals) {
135             throw new IndexOutOfBoundsException  ("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         if (i >= top) {
160             throw new IndexOutOfBoundsException  ("Trying to access an inexistant stack element");
161         }
162         return values[i + locals];
163     }
164 
165     /**
166      * Clears the operand stack of this frame.
167      */
168     public void clearStack() {
169         top = 0;
170     }
171 
172     /**
173      * Pops a value from the operand stack of this frame.
174      * 
175      * @return the value that has been popped from the stack.
176      * @throws IndexOutOfBoundsException if the operand stack is empty.
177      */
178     public Value pop() throws IndexOutOfBoundsException   {
179         if (top == 0) {
180             throw new IndexOutOfBoundsException  ("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) throws IndexOutOfBoundsException   {
192         if (top + locals >= values.length) {
193             throw new IndexOutOfBoundsException  ("Insufficient maximum stack size.");
194         }
195         values[top++ + locals] = value;
196     }
197 
198     public void execute(
199         final AbstractInsnNode insn,
200         final Interpreter interpreter) throws AnalyzerException
201     {
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.copyOperation(insn, value2));
383                                 push(interpreter.copyOperation(insn, value1));
384                                 push(interpreter.copyOperation(insn, value4));
385                                 push(interpreter.copyOperation(insn, value3));
386                                 push(interpreter.copyOperation(insn, value2));
387                                 push(interpreter.copyOperation(insn, value1));
388                                 break;
389                             }
390                         } else {
391                             push(interpreter.copyOperation(insn, value2));
392                             push(interpreter.copyOperation(insn, value1));
393                             push(interpreter.copyOperation(insn, value3));
394                             push(interpreter.copyOperation(insn, value2));
395                             push(interpreter.copyOperation(insn, value1));
396                             break;
397                         }
398                     }
399                 } else {
400                     value2 = pop();
401                     if (value2.getSize() == 1) {
402                         value3 = pop();
403                         if (value3.getSize() == 1) {
404                             push(interpreter.copyOperation(insn, value1));
405                             push(interpreter.copyOperation(insn, value3));
406                             push(interpreter.copyOperation(insn, value2));
407                             push(interpreter.copyOperation(insn, value1));
408                             break;
409                         }
410                     } else {
411                         push(interpreter.copyOperation(insn, value1));
412                         push(interpreter.copyOperation(insn, value2));
413                         push(interpreter.copyOperation(insn, value1));
414                         break;
415                     }
416                 }
417                 throw new AnalyzerException("Illegal use of DUP2_X2");
418             case Opcodes.SWAP:
419                 value2 = pop();
420                 value1 = pop();
421                 if (value1.getSize() != 1 || value2.getSize() != 1) {
422                     throw new AnalyzerException("Illegal use of SWAP");
423                 }
424                 push(interpreter.copyOperation(insn, value2));
425                 push(interpreter.copyOperation(insn, value1));
426                 break;
427             case Opcodes.IADD:
428             case Opcodes.LADD:
429             case Opcodes.FADD:
430             case Opcodes.DADD:
431             case Opcodes.ISUB:
432             case Opcodes.LSUB:
433             case Opcodes.FSUB:
434             case Opcodes.DSUB:
435             case Opcodes.IMUL:
436             case Opcodes.LMUL:
437             case Opcodes.FMUL:
438             case Opcodes.DMUL:
439             case Opcodes.IDIV:
440             case Opcodes.LDIV:
441             case Opcodes.FDIV:
442             case Opcodes.DDIV:
443             case Opcodes.IREM:
444             case Opcodes.LREM:
445             case Opcodes.FREM:
446             case Opcodes.DREM:
447                 value2 = pop();
448                 value1 = pop();
449                 push(interpreter.binaryOperation(insn, value1, value2));
450                 break;
451             case Opcodes.INEG:
452             case Opcodes.LNEG:
453             case Opcodes.FNEG:
454             case Opcodes.DNEG:
455                 push(interpreter.unaryOperation(insn, pop()));
456                 break;
457             case Opcodes.ISHL:
458             case Opcodes.LSHL:
459             case Opcodes.ISHR:
460             case Opcodes.LSHR:
461             case Opcodes.IUSHR:
462             case Opcodes.LUSHR:
463             case Opcodes.IAND:
464             case Opcodes.LAND:
465             case Opcodes.IOR:
466             case Opcodes.LOR:
467             case Opcodes.IXOR:
468             case Opcodes.LXOR:
469                 value2 = pop();
470                 value1 = pop();
471                 push(interpreter.binaryOperation(insn, value1, value2));
472                 break;
473             case Opcodes.IINC:
474                 var = ((IincInsnNode) insn).var;
475                 setLocal(var, interpreter.unaryOperation(insn, getLocal(var)));
476                 break;
477             case Opcodes.I2L:
478             case Opcodes.I2F:
479             case Opcodes.I2D:
480             case Opcodes.L2I:
481             case Opcodes.L2F:
482             case Opcodes.L2D:
483             case Opcodes.F2I:
484             case Opcodes.F2L:
485             case Opcodes.F2D:
486             case Opcodes.D2I:
487             case Opcodes.D2L:
488             case Opcodes.D2F:
489             case Opcodes.I2B:
490             case Opcodes.I2C:
491             case Opcodes.I2S:
492                 push(interpreter.unaryOperation(insn, pop()));
493                 break;
494             case Opcodes.LCMP:
495             case Opcodes.FCMPL:
496             case Opcodes.FCMPG:
497             case Opcodes.DCMPL:
498             case Opcodes.DCMPG:
499                 value2 = pop();
500                 value1 = pop();
501                 push(interpreter.binaryOperation(insn, value1, value2));
502                 break;
503             case Opcodes.IFEQ:
504             case Opcodes.IFNE:
505             case Opcodes.IFLT:
506             case Opcodes.IFGE:
507             case Opcodes.IFGT:
508             case Opcodes.IFLE:
509                 interpreter.unaryOperation(insn, pop());
510                 break;
511             case Opcodes.IF_ICMPEQ:
512             case Opcodes.IF_ICMPNE:
513             case Opcodes.IF_ICMPLT:
514             case Opcodes.IF_ICMPGE:
515             case Opcodes.IF_ICMPGT:
516             case Opcodes.IF_ICMPLE:
517             case Opcodes.IF_ACMPEQ:
518             case Opcodes.IF_ACMPNE:
519                 value2 = pop();
520                 value1 = pop();
521                 interpreter.binaryOperation(insn, value1, value2);
522                 break;
523             case Opcodes.GOTO:
524                 break;
525             case Opcodes.JSR:
526                 push(interpreter.newOperation(insn));
527                 break;
528             case Opcodes.RET:
529                 break;
530             case Opcodes.TABLESWITCH:
531             case Opcodes.LOOKUPSWITCH:
532             case Opcodes.IRETURN:
533             case Opcodes.LRETURN:
534             case Opcodes.FRETURN:
535             case Opcodes.DRETURN:
536             case Opcodes.ARETURN:
537                 interpreter.unaryOperation(insn, pop());
538                 break;
539             case Opcodes.RETURN:
540                 break;
541             case Opcodes.GETSTATIC:
542                 push(interpreter.newOperation(insn));
543                 break;
544             case Opcodes.PUTSTATIC:
545                 interpreter.unaryOperation(insn, pop());
546                 break;
547             case Opcodes.GETFIELD:
548                 push(interpreter.unaryOperation(insn, pop()));
549                 break;
550             case Opcodes.PUTFIELD:
551                 value2 = pop();
552                 value1 = pop();
553                 interpreter.binaryOperation(insn, value1, value2);
554                 break;
555             case Opcodes.INVOKEVIRTUAL:
556             case Opcodes.INVOKESPECIAL:
557             case Opcodes.INVOKESTATIC:
558             case Opcodes.INVOKEINTERFACE:
559                 values = new ArrayList  ();
560                 String   desc = ((MethodInsnNode) insn).desc;
561                 for (int i = Type.getArgumentTypes(desc).length; i > 0; --i) {
562                     values.add(0, pop());
563                 }
564                 if (insn.getOpcode() != Opcodes.INVOKESTATIC) {
565                     values.add(0, pop());
566                 }
567                 if (Type.getReturnType(desc) == Type.VOID_TYPE) {
568                     interpreter.naryOperation(insn, values);
569                 } else {
570                     push(interpreter.naryOperation(insn, values));
571                 }
572                 break;
573             case Opcodes.NEW:
574                 push(interpreter.newOperation(insn));
575                 break;
576             case Opcodes.NEWARRAY:
577             case Opcodes.ANEWARRAY:
578             case Opcodes.ARRAYLENGTH:
579                 push(interpreter.unaryOperation(insn, pop()));
580                 break;
581             case Opcodes.ATHROW:
582                 interpreter.unaryOperation(insn, pop());
583                 break;
584             case Opcodes.CHECKCAST:
585             case Opcodes.INSTANCEOF:
586                 push(interpreter.unaryOperation(insn, pop()));
587                 break;
588             case Opcodes.MONITORENTER:
589             case Opcodes.MONITOREXIT:
590                 interpreter.unaryOperation(insn, pop());
591                 break;
592             case Opcodes.MULTIANEWARRAY:
593                 values = new ArrayList  ();
594                 for (int i = ((MultiANewArrayInsnNode) insn).dims; i > 0; --i) {
595                     values.add(0, pop());
596                 }
597                 push(interpreter.naryOperation(insn, values));
598                 break;
599             case Opcodes.IFNULL:
600             case Opcodes.IFNONNULL:
601                 interpreter.unaryOperation(insn, pop());
602                 break;
603             default:
604                 throw new RuntimeException  ("Illegal opcode");
605         }
606     }
607 
608     /**
609      * Merges this frame with the given frame.
610      * 
611      * @param frame a frame.
612      * @param interpreter the interpreter used to merge values.
613      * @return <tt>true</tt> if this frame has been changed as a result of the
614      *         merge operation, or <tt>false</tt> otherwise.
615      * @throws AnalyzerException if the frames have incompatible sizes.
616      */
617     public boolean merge(final Frame frame, final Interpreter interpreter)
618             throws AnalyzerException
619     {
620         if (top != frame.top) {
621             throw new AnalyzerException("Incompatible stack heights");
622         }
623         boolean changes = false;
624         for (int i = 0; i < locals + top; ++i) {
625             Value v = interpreter.merge(values[i], frame.values[i]);
626             if (v != values[i]) {
627                 values[i] = v;
628                 changes |= true;
629             }
630         }
631         return changes;
632     }
633 
634     /**
635      * Merges this frame with the given frame (case of a RET instruction).
636      * 
637      * @param frame a frame
638      * @param access the local variables that have been accessed by the
639      *        subroutine to which the RET instruction corresponds.
640      * @return <tt>true</tt> if this frame has been changed as a result of the
641      *         merge operation, or <tt>false</tt> otherwise.
642      */
643     public boolean merge(final Frame frame, final boolean[] access) {
644         boolean changes = false;
645         for (int i = 0; i < locals; ++i) {
646             if (!access[i] && !values[i].equals(frame.values[i])) {
647                 values[i] = frame.values[i];
648                 changes = true;
649             }
650         }
651         return changes;
652     }
653 
654     /**
655      * Returns a string representation of this frame.
656      * 
657      * @return a string representation of this frame.
658      */
659     public String   toString() {
660         StringBuffer   b = new StringBuffer  ();
661         for (int i = 0; i < locals; ++i) {
662             b.append(values[i]).append(' ');
663         }
664         b.append(' ');
665         for (int i = 0; i < top; ++i) {
666             b.append(values[i + locals].toString()).append(' ');
667         }
668         return b.toString();
669     }
670 }
671
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags