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