View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   *  Unless required by applicable law or agreed to in writing, software
12   *  distributed under the License is distributed on an "AS IS" BASIS,
13   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   *  See the License for the specific language governing permissions and
15   *  limitations under the License.
16   *
17   */
18  package org.apache.bcel.verifier.structurals;
19  
20  
21  import java.util.ArrayList;
22  
23  import org.apache.bcel.generic.ObjectType;
24  import org.apache.bcel.generic.ReferenceType;
25  import org.apache.bcel.generic.Type;
26  import org.apache.bcel.verifier.exc.AssertionViolatedException;
27  import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;
28  
29  /**
30   * This class implements a stack used for symbolic JVM stack simulation.
31   * [It's used an an operand stack substitute.]
32   * Elements of this stack are {@link Type} objects.
33   *
34   */
35  public class OperandStack implements Cloneable {
36  
37      /** We hold the stack information here. */
38      private ArrayList<Type> stack = new ArrayList<>();
39  
40      /** The maximum number of stack slots this OperandStack instance may hold. */
41      private final int maxStack;
42  
43      /**
44       * Creates an empty stack with a maximum of maxStack slots.
45       */
46      public OperandStack(final int maxStack) {
47          this.maxStack = maxStack;
48      }
49  
50      /**
51       * Creates an otherwise empty stack with a maximum of maxStack slots and
52       * the ObjectType 'obj' at the top.
53       */
54      public OperandStack(final int maxStack, final ObjectType obj) {
55          this.maxStack = maxStack;
56          this.push(obj);
57      }
58      /**
59       * Returns a deep copy of this object; that means, the clone operates
60       * on a new stack. However, the Type objects on the stack are
61       * shared.
62       */
63      @Override
64      public Object clone() {
65          final OperandStackals/OperandStack.html#OperandStack">OperandStack newstack = new OperandStack(this.maxStack);
66          @SuppressWarnings("unchecked") // OK because this.stack is the same type
67          final ArrayList<Type> clone = (ArrayList<Type>) this.stack.clone();
68          newstack.stack = clone;
69          return newstack;
70      }
71  
72      /**
73       * Clears the stack.
74       */
75      public void clear() {
76          stack = new ArrayList<>();
77      }
78  
79      /** @return a hash code value for the object.
80       */
81      @Override
82      public int hashCode() { return stack.hashCode(); }
83  
84      /**
85       * Returns true if and only if this OperandStack
86       * equals another, meaning equal lengths and equal
87       * objects on the stacks.
88       */
89      @Override
90      public boolean equals(final Object o) {
91          if (!(o instanceof OperandStack)) {
92              return false;
93          }
94          final OperandStack./../../../../org/apache/bcel/verifier/structurals/OperandStack.html#OperandStack">OperandStack s = (OperandStack) o;
95          return this.stack.equals(s.stack);
96      }
97  
98      /**
99       * Returns a (typed!) clone of this.
100      *
101      * @see #clone()
102      */
103     public OperandStack getClone() {
104         return (OperandStack) this.clone();
105     }
106 
107     /**
108      * Returns true IFF this OperandStack is empty.
109    */
110     public boolean isEmpty() {
111         return stack.isEmpty();
112     }
113 
114     /**
115      * Returns the number of stack slots this stack can hold.
116      */
117     public int maxStack() {
118         return this.maxStack;
119     }
120 
121     /**
122      * Returns the element on top of the stack. The element is not popped off the stack!
123      */
124     public Type peek() {
125         return peek(0);
126     }
127 
128     /**
129    * Returns the element that's i elements below the top element; that means,
130    * iff i==0 the top element is returned. The element is not popped off the stack!
131    */
132     public Type peek(final int i) {
133         return stack.get(size()-i-1);
134     }
135 
136     /**
137      * Returns the element on top of the stack. The element is popped off the stack.
138      */
139     public Type pop() {
140         final Type e = stack.remove(size()-1);
141         return e;
142     }
143 
144     /**
145      * Pops i elements off the stack. ALWAYS RETURNS "null"!!!
146      */
147     public Type pop(final int i) {
148         for (int j=0; j<i; j++) {
149             pop();
150         }
151         return null;
152     }
153 
154     /**
155      * Pushes a Type object onto the stack.
156      */
157     public void push(final Type type) {
158         if (type == null) {
159             throw new AssertionViolatedException("Cannot push NULL onto OperandStack.");
160         }
161         if (type == Type.BOOLEAN || type == Type.CHAR || type == Type.BYTE || type == Type.SHORT) {
162             throw new AssertionViolatedException("The OperandStack does not know about '"+type+"'; use Type.INT instead.");
163         }
164         if (slotsUsed() >= maxStack) {
165             throw new AssertionViolatedException(
166                 "OperandStack too small, should have thrown proper Exception elsewhere. Stack: "+this);
167         }
168         stack.add(type);
169     }
170 
171     /**
172      * Returns the size of this OperandStack; that means, how many Type objects there are.
173      */
174     public int size() {
175         return stack.size();
176     }
177 
178     /**
179      * Returns the number of stack slots used.
180      * @see #maxStack()
181      */
182     public int slotsUsed() {
183         /*  XXX change this to a better implementation using a variable
184             that keeps track of the actual slotsUsed()-value monitoring
185             all push()es and pop()s.
186         */
187         int slots = 0;
188         for (int i=0; i<stack.size(); i++) {
189             slots += peek(i).getSize();
190         }
191         return slots;
192     }
193 
194     /**
195      * Returns a String representation of this OperandStack instance.
196      */
197     @Override
198     public String toString() {
199         final StringBuilder sb = new StringBuilder();
200         sb.append("Slots used: ");
201         sb.append(slotsUsed());
202         sb.append(" MaxStack: ");
203         sb.append(maxStack);
204         sb.append(".\n");
205         for (int i=0; i<size(); i++) {
206             sb.append(peek(i));
207             sb.append(" (Size: ");
208             sb.append(String.valueOf(peek(i).getSize()));
209             sb.append(")\n");
210         }
211         return sb.toString();
212     }
213 
214     /**
215      * Merges another stack state into this instance's stack state.
216      * See the Java Virtual Machine Specification, Second Edition, page 146: 4.9.2
217      * for details.
218      */
219     public void merge(final OperandStack s) {
220         try {
221         if ( (slotsUsed() != s.slotsUsed()) || (size() != s.size()) ) {
222             throw new StructuralCodeConstraintException(
223                 "Cannot merge stacks of different size:\nOperandStack A:\n"+this+"\nOperandStack B:\n"+s);
224         }
225 
226         for (int i=0; i<size(); i++) {
227             // If the object _was_ initialized and we're supposed to merge
228             // in some uninitialized object, we reject the code (see vmspec2, 4.9.4, last paragraph).
229             if ( (! (stack.get(i) instanceof UninitializedObjectTyperals/UninitializedObjectType.html#UninitializedObjectType">UninitializedObjectType)) && (s.stack.get(i) instanceof UninitializedObjectType) ) {
230                 throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
231             }
232             // Even harder, we're not initialized but are supposed to broaden
233             // the known object type
234             if ( (!(stack.get(i).equals(s.stack.get(i)))) &&
235                     (stack.get(i) instanceof UninitializedObjectTypeals/UninitializedObjectType.html#UninitializedObjectType">UninitializedObjectType) && (!(s.stack.get(i) instanceof UninitializedObjectType))) {
236                 throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
237             }
238             // on the other hand...
239             if (stack.get(i) instanceof UninitializedObjectType) { //if we have an uninitialized object here
240                 if (! (s.stack.get(i) instanceof UninitializedObjectType)) { //that has been initialized by now
241                     stack.set(i, ((UninitializedObjectType) (stack.get(i))).getInitialized() ); //note that.
242                 }
243             }
244             if (! stack.get(i).equals(s.stack.get(i))) {
245                 if (    (stack.get(i) instanceof ReferenceType) &&
246                             (s.stack.get(i) instanceof ReferenceType)  ) {
247                     stack.set(i, ((ReferenceType/ReferenceType.html#ReferenceType">ReferenceType) stack.get(i)).getFirstCommonSuperclass((ReferenceType) (s.stack.get(i))));
248                 }
249                 else{
250                     throw new StructuralCodeConstraintException(
251                         "Cannot merge stacks of different types:\nStack A:\n"+this+"\nStack B:\n"+s);
252                 }
253             }
254         }
255         } catch (final ClassNotFoundException e) {
256         // FIXME: maybe not the best way to handle this
257         throw new AssertionViolatedException("Missing class: " + e, e);
258         }
259     }
260 
261     /**
262      * Replaces all occurences of u in this OperandStack instance
263      * with an "initialized" ObjectType.
264      */
265     public void initializeObject(final UninitializedObjectType u) {
266         for (int i=0; i<stack.size(); i++) {
267             if (stack.get(i) == u) {
268                 stack.set(i, u.getInitialized());
269             }
270         }
271     }
272 
273 }