Source code

001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *   https://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing,
013 * software distributed under the License is distributed on an
014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 * KIND, either express or implied.  See the License for the
016 * specific language governing permissions and limitations
017 * under the License.
018 */
019package org.apache.bcel.verifier.structurals;
020
021import java.util.ArrayList;
022
023import org.apache.bcel.generic.ObjectType;
024import org.apache.bcel.generic.ReferenceType;
025import org.apache.bcel.generic.Type;
026import org.apache.bcel.verifier.exc.AssertionViolatedException;
027import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;
028
029/**
030 * This class implements a stack used for symbolic JVM stack simulation. [It's used as an operand stack substitute.]
031 * Elements of this stack are {@link Type} objects.
032 */
033public class OperandStack implements Cloneable {
034
035    /** We hold the stack information here. */
036    private ArrayList<Type> stack = new ArrayList<>();
037
038    /** The maximum number of stack slots this OperandStack instance may hold. */
039    private final int maxStack;
040
041    /**
042     * Creates an empty stack with a maximum of maxStack slots.
043     *
044     * @param maxStack The maximum stack size.
045     */
046    public OperandStack(final int maxStack) {
047        this.maxStack = maxStack;
048    }
049
050    /**
051     * Creates an otherwise empty stack with a maximum of maxStack slots and the ObjectType 'obj' at the top.
052     *
053     * @param maxStack The maximum stack size.
054     * @param obj The object type to place at the top.
055     */
056    public OperandStack(final int maxStack, final ObjectType obj) {
057        this.maxStack = maxStack;
058        push(obj);
059    }
060
061    /**
062     * Clears the stack.
063     */
064    public void clear() {
065        stack = new ArrayList<>();
066    }
067
068    /**
069     * Returns a deep copy of this object; that means, the clone operates on a new stack. However, the Type objects on the
070     * stack are shared.
071     */
072    @Override
073    public Object clone() {
074        final OperandStack newstack = new OperandStack(this.maxStack);
075        @SuppressWarnings("unchecked") // OK because this.stack is the same type
076        final ArrayList<Type> clone = (ArrayList<Type>) this.stack.clone();
077        newstack.stack = clone;
078        return newstack;
079    }
080
081    /**
082     * Returns true if and only if this OperandStack equals another, meaning equal lengths and equal objects on the stacks.
083     */
084    @Override
085    public boolean equals(final Object o) {
086        if (!(o instanceof OperandStack)) {
087            return false;
088        }
089        final OperandStack s = (OperandStack) o;
090        return this.stack.equals(s.stack);
091    }
092
093    /**
094     * Returns a (typed!) clone of this.
095     *
096     * @return A clone of this operand stack.
097     * @see #clone()
098     */
099    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}