001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 *  Unless required by applicable law or agreed to in writing, software
012 *  distributed under the License is distributed on an "AS IS" BASIS,
013 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 *  See the License for the specific language governing permissions and
015 *  limitations under the License.
016 *
017 */
018package org.apache.bcel.verifier.structurals;
019
020import java.util.ArrayList;
021
022import org.apache.bcel.generic.ObjectType;
023import org.apache.bcel.generic.ReferenceType;
024import org.apache.bcel.generic.Type;
025import org.apache.bcel.verifier.exc.AssertionViolatedException;
026import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;
027
028/**
029 * This class implements a stack used for symbolic JVM stack simulation. [It's used as an operand stack substitute.]
030 * Elements of this stack are {@link Type} objects.
031 *
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    public OperandStack(final int maxStack) {
045        this.maxStack = maxStack;
046    }
047
048    /**
049     * Creates an otherwise empty stack with a maximum of maxStack slots and the ObjectType 'obj' at the top.
050     */
051    public OperandStack(final int maxStack, final ObjectType obj) {
052        this.maxStack = maxStack;
053        this.push(obj);
054    }
055
056    /**
057     * Clears the stack.
058     */
059    public void clear() {
060        stack = new ArrayList<>();
061    }
062
063    /**
064     * Returns a deep copy of this object; that means, the clone operates on a new stack. However, the Type objects on the
065     * stack are shared.
066     */
067    @Override
068    public Object clone() {
069        final OperandStack newstack = new OperandStack(this.maxStack);
070        @SuppressWarnings("unchecked") // OK because this.stack is the same type
071        final ArrayList<Type> clone = (ArrayList<Type>) this.stack.clone();
072        newstack.stack = clone;
073        return newstack;
074    }
075
076    /**
077     * Returns true if and only if this OperandStack equals another, meaning equal lengths and equal objects on the stacks.
078     */
079    @Override
080    public boolean equals(final Object o) {
081        if (!(o instanceof OperandStack)) {
082            return false;
083        }
084        final OperandStack s = (OperandStack) o;
085        return this.stack.equals(s.stack);
086    }
087
088    /**
089     * Returns a (typed!) clone of this.
090     *
091     * @see #clone()
092     */
093    public OperandStack getClone() {
094        return (OperandStack) this.clone();
095    }
096
097    /**
098     * @return a hash code value for the object.
099     */
100    @Override
101    public int hashCode() {
102        return stack.hashCode();
103    }
104
105    /**
106     * Replaces all occurences of u in this OperandStack instance with an "initialized" ObjectType.
107     */
108    public void initializeObject(final UninitializedObjectType u) {
109        for (int i = 0; i < stack.size(); i++) {
110            if (stack.get(i) == u) {
111                stack.set(i, u.getInitialized());
112            }
113        }
114    }
115
116    /**
117     * Returns true IFF this OperandStack is empty.
118     */
119    public boolean isEmpty() {
120        return stack.isEmpty();
121    }
122
123    /**
124     * Returns the number of stack slots this stack can hold.
125     */
126    public int maxStack() {
127        return this.maxStack;
128    }
129
130    /**
131     * Merges another stack state into this instance's stack state. See the Java Virtual Machine Specification, Second
132     * Edition, page 146: 4.9.2 for details.
133     */
134    public void merge(final OperandStack s) {
135        try {
136            if (slotsUsed() != s.slotsUsed() || size() != s.size()) {
137                throw new StructuralCodeConstraintException("Cannot merge stacks of different size:\nOperandStack A:\n" + this + "\nOperandStack B:\n" + s);
138            }
139
140            for (int i = 0; i < size(); i++) {
141                // If the object _was_ initialized and we're supposed to merge
142                // in some uninitialized object, we reject the code (see vmspec2, 4.9.4, last paragraph).
143                if (!(stack.get(i) instanceof UninitializedObjectType) && s.stack.get(i) instanceof UninitializedObjectType) {
144                    throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
145                }
146                // Even harder, we're not initialized but are supposed to broaden
147                // the known object type
148                if (!stack.get(i).equals(s.stack.get(i)) && stack.get(i) instanceof UninitializedObjectType
149                    && !(s.stack.get(i) instanceof UninitializedObjectType)) {
150                    throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
151                }
152                // on the other hand...
153                if (stack.get(i) instanceof UninitializedObjectType && !(s.stack.get(i) instanceof UninitializedObjectType)) { // that has been initialized by
154                                                                                                                               // now
155                    stack.set(i, ((UninitializedObjectType) stack.get(i)).getInitialized()); // note that.
156                }
157                if (!stack.get(i).equals(s.stack.get(i))) {
158                    if (!(stack.get(i) instanceof ReferenceType) || !(s.stack.get(i) instanceof ReferenceType)) {
159                        throw new StructuralCodeConstraintException("Cannot merge stacks of different types:\nStack A:\n" + this + "\nStack B:\n" + s);
160                    }
161                    stack.set(i, ((ReferenceType) stack.get(i)).getFirstCommonSuperclass((ReferenceType) s.stack.get(i)));
162                }
163            }
164        } catch (final ClassNotFoundException e) {
165            // FIXME: maybe not the best way to handle this
166            throw new AssertionViolatedException("Missing class: " + e, e);
167        }
168    }
169
170    /**
171     * Returns the element on top of the stack. The element is not popped off the stack!
172     */
173    public Type peek() {
174        return peek(0);
175    }
176
177    /**
178     * Returns the element that's i elements below the top element; that means, iff i==0 the top element is returned. The
179     * element is not popped off the stack!
180     */
181    public Type peek(final int i) {
182        return stack.get(size() - i - 1);
183    }
184
185    /**
186     * Returns the element on top of the stack. The element is popped off the stack.
187     */
188    public Type pop() {
189        return stack.remove(size() - 1);
190    }
191
192    /**
193     * Pops i elements off the stack. Always returns null.
194     *
195     * @return Always returns null.
196     */
197    public Type pop(final int count) {
198        for (int j = 0; j < count; j++) {
199            pop();
200        }
201        return null;
202    }
203
204    /**
205     * Pushes a Type object onto the stack.
206     */
207    public void push(final Type type) {
208        if (type == null) {
209            throw new AssertionViolatedException("Cannot push NULL onto OperandStack.");
210        }
211        if (type == Type.BOOLEAN || type == Type.CHAR || type == Type.BYTE || type == Type.SHORT) {
212            throw new AssertionViolatedException("The OperandStack does not know about '" + type + "'; use Type.INT instead.");
213        }
214        if (slotsUsed() >= maxStack) {
215            throw new AssertionViolatedException("OperandStack too small, should have thrown proper Exception elsewhere. Stack: " + this);
216        }
217        stack.add(type);
218    }
219
220    /**
221     * Returns the size of this OperandStack; that means, how many Type objects there are.
222     */
223    public int size() {
224        return stack.size();
225    }
226
227    /**
228     * Returns the number of stack slots used.
229     *
230     * @see #maxStack()
231     */
232    public int slotsUsed() {
233        /*
234         * XXX change this to a better implementation using a variable that keeps track of the actual slotsUsed()-value
235         * monitoring all push()es and pop()s.
236         */
237        int slots = 0;
238        for (int i = 0; i < stack.size(); i++) {
239            slots += peek(i).getSize();
240        }
241        return slots;
242    }
243
244    /**
245     * Returns a String representation of this OperandStack instance.
246     */
247    @Override
248    public String toString() {
249        final StringBuilder sb = new StringBuilder();
250        sb.append("Slots used: ");
251        sb.append(slotsUsed());
252        sb.append(" MaxStack: ");
253        sb.append(maxStack);
254        sb.append(".\n");
255        for (int i = 0; i < size(); i++) {
256            sb.append(peek(i));
257            sb.append(" (Size: ");
258            sb.append(String.valueOf(peek(i).getSize()));
259            sb.append(")\n");
260        }
261        return sb.toString();
262    }
263
264}