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   * @version $Id: OperandStack.html 1018313 2017-09-18 09:03:04Z britter $
35   */
36  public class OperandStack implements Cloneable {
37  
38      /** We hold the stack information here. */
39      private ArrayList<Type> stack = new ArrayList<>();
40  
41      /** The maximum number of stack slots this OperandStack instance may hold. */
42      private final int maxStack;
43  
44      /**
45       * Creates an empty stack with a maximum of maxStack slots.
46       */
47      public OperandStack(final int maxStack) {
48          this.maxStack = maxStack;
49      }
50  
51      /**
52       * Creates an otherwise empty stack with a maximum of maxStack slots and
53       * the ObjectType 'obj' at the top.
54       */
55      public OperandStack(final int maxStack, final ObjectType obj) {
56          this.maxStack = maxStack;
57          this.push(obj);
58      }
59      /**
60       * Returns a deep copy of this object; that means, the clone operates
61       * on a new stack. However, the Type objects on the stack are
62       * shared.
63       */
64      @Override
65      public Object clone() {
66          final OperandStack newstack = new OperandStack(this.maxStack);
67          @SuppressWarnings("unchecked") // OK because this.stack is the same type
68          final ArrayList<Type> clone = (ArrayList<Type>) this.stack.clone();
69          newstack.stack = clone;
70          return newstack;
71      }
72  
73      /**
74       * Clears the stack.
75       */
76      public void clear() {
77          stack = new ArrayList<>();
78      }
79  
80      /** @return a hash code value for the object.
81       */
82      @Override
83      public int hashCode() { return stack.hashCode(); }
84  
85      /**
86       * Returns true if and only if this OperandStack
87       * equals another, meaning equal lengths and equal
88       * objects on the stacks.
89       */
90      @Override
91      public boolean equals(final Object o) {
92          if (!(o instanceof OperandStack)) {
93              return false;
94          }
95          final OperandStack s = (OperandStack) o;
96          return this.stack.equals(s.stack);
97      }
98  
99      /**
100      * Returns a (typed!) clone of this.
101      *
102      * @see #clone()
103      */
104     public OperandStack getClone() {
105         return (OperandStack) this.clone();
106     }
107 
108     /**
109      * Returns true IFF this OperandStack is empty.
110    */
111     public boolean isEmpty() {
112         return stack.isEmpty();
113     }
114 
115     /**
116      * Returns the number of stack slots this stack can hold.
117      */
118     public int maxStack() {
119         return this.maxStack;
120     }
121 
122     /**
123      * Returns the element on top of the stack. The element is not popped off the stack!
124      */
125     public Type peek() {
126         return peek(0);
127     }
128 
129     /**
130    * Returns the element that's i elements below the top element; that means,
131    * iff i==0 the top element is returned. The element is not popped off the stack!
132    */
133     public Type peek(final int i) {
134         return stack.get(size()-i-1);
135     }
136 
137     /**
138      * Returns the element on top of the stack. The element is popped off the stack.
139      */
140     public Type pop() {
141         final Type e = stack.remove(size()-1);
142         return e;
143     }
144 
145     /**
146      * Pops i elements off the stack. ALWAYS RETURNS "null"!!!
147      */
148     public Type pop(final int i) {
149         for (int j=0; j<i; j++) {
150             pop();
151         }
152         return null;
153     }
154 
155     /**
156      * Pushes a Type object onto the stack.
157      */
158     public void push(final Type type) {
159         if (type == null) {
160             throw new AssertionViolatedException("Cannot push NULL onto OperandStack.");
161         }
162         if (type == Type.BOOLEAN || type == Type.CHAR || type == Type.BYTE || type == Type.SHORT) {
163             throw new AssertionViolatedException("The OperandStack does not know about '"+type+"'; use Type.INT instead.");
164         }
165         if (slotsUsed() >= maxStack) {
166             throw new AssertionViolatedException(
167                 "OperandStack too small, should have thrown proper Exception elsewhere. Stack: "+this);
168         }
169         stack.add(type);
170     }
171 
172     /**
173      * Returns the size of this OperandStack; that means, how many Type objects there are.
174      */
175     public int size() {
176         return stack.size();
177     }
178 
179     /**
180      * Returns the number of stack slots used.
181      * @see #maxStack()
182      */
183     public int slotsUsed() {
184         /*  XXX change this to a better implementation using a variable
185             that keeps track of the actual slotsUsed()-value monitoring
186             all push()es and pop()s.
187         */
188         int slots = 0;
189         for (int i=0; i<stack.size(); i++) {
190             slots += peek(i).getSize();
191         }
192         return slots;
193     }
194 
195     /**
196      * Returns a String representation of this OperandStack instance.
197      */
198     @Override
199     public String toString() {
200         final StringBuilder sb = new StringBuilder();
201         sb.append("Slots used: ");
202         sb.append(slotsUsed());
203         sb.append(" MaxStack: ");
204         sb.append(maxStack);
205         sb.append(".\n");
206         for (int i=0; i<size(); i++) {
207             sb.append(peek(i));
208             sb.append(" (Size: ");
209             sb.append(String.valueOf(peek(i).getSize()));
210             sb.append(")\n");
211         }
212         return sb.toString();
213     }
214 
215     /**
216      * Merges another stack state into this instance's stack state.
217      * See the Java Virtual Machine Specification, Second Edition, page 146: 4.9.2
218      * for details.
219      */
220     public void merge(final OperandStack s) {
221         try {
222         if ( (slotsUsed() != s.slotsUsed()) || (size() != s.size()) ) {
223             throw new StructuralCodeConstraintException(
224                 "Cannot merge stacks of different size:\nOperandStack A:\n"+this+"\nOperandStack B:\n"+s);
225         }
226 
227         for (int i=0; i<size(); i++) {
228             // If the object _was_ initialized and we're supposed to merge
229             // in some uninitialized object, we reject the code (see vmspec2, 4.9.4, last paragraph).
230             if ( (! (stack.get(i) instanceof UninitializedObjectType)) && (s.stack.get(i) instanceof UninitializedObjectType) ) {
231                 throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
232             }
233             // Even harder, we're not initialized but are supposed to broaden
234             // the known object type
235             if ( (!(stack.get(i).equals(s.stack.get(i)))) &&
236                     (stack.get(i) instanceof UninitializedObjectType) && (!(s.stack.get(i) instanceof UninitializedObjectType))) {
237                 throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
238             }
239             // on the other hand...
240             if (stack.get(i) instanceof UninitializedObjectType) { //if we have an uninitialized object here
241                 if (! (s.stack.get(i) instanceof UninitializedObjectType)) { //that has been initialized by now
242                     stack.set(i, ((UninitializedObjectType) (stack.get(i))).getInitialized() ); //note that.
243                 }
244             }
245             if (! stack.get(i).equals(s.stack.get(i))) {
246                 if (    (stack.get(i) instanceof ReferenceType) &&
247                             (s.stack.get(i) instanceof ReferenceType)  ) {
248                     stack.set(i, ((ReferenceType) stack.get(i)).getFirstCommonSuperclass((ReferenceType) (s.stack.get(i))));
249                 }
250                 else{
251                     throw new StructuralCodeConstraintException(
252                         "Cannot merge stacks of different types:\nStack A:\n"+this+"\nStack B:\n"+s);
253                 }
254             }
255         }
256         } catch (final ClassNotFoundException e) {
257         // FIXME: maybe not the best way to handle this
258         throw new AssertionViolatedException("Missing class: " + e, e);
259         }
260     }
261 
262     /**
263      * Replaces all occurences of u in this OperandStack instance
264      * with an "initialized" ObjectType.
265      */
266     public void initializeObject(final UninitializedObjectType u) {
267         for (int i=0; i<stack.size(); i++) {
268             if (stack.get(i) == u) {
269                 stack.set(i, u.getInitialized());
270             }
271         }
272     }
273 
274 }