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