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
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.
031 * [It's used an an operand stack substitute.]
032 * Elements of this stack are {@link Type} objects.
033 *
034 */
035public class OperandStack implements Cloneable {
036
037    /** We hold the stack information here. */
038    private ArrayList<Type> stack = new ArrayList<>();
039
040    /** The maximum number of stack slots this OperandStack instance may hold. */
041    private final int maxStack;
042
043    /**
044     * Creates an empty stack with a maximum of maxStack slots.
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
052     * the ObjectType 'obj' at the top.
053     */
054    public OperandStack(final int maxStack, final ObjectType obj) {
055        this.maxStack = maxStack;
056        this.push(obj);
057    }
058    /**
059     * Returns a deep copy of this object; that means, the clone operates
060     * on a new stack. However, the Type objects on the stack are
061     * shared.
062     */
063    @Override
064    public Object clone() {
065        final OperandStack newstack = new OperandStack(this.maxStack);
066        @SuppressWarnings("unchecked") // OK because this.stack is the same type
067        final ArrayList<Type> clone = (ArrayList<Type>) this.stack.clone();
068        newstack.stack = clone;
069        return newstack;
070    }
071
072    /**
073     * Clears the stack.
074     */
075    public void clear() {
076        stack = new ArrayList<>();
077    }
078
079    /** @return a hash code value for the object.
080     */
081    @Override
082    public int hashCode() { return stack.hashCode(); }
083
084    /**
085     * Returns true if and only if this OperandStack
086     * equals another, meaning equal lengths and equal
087     * objects on the stacks.
088     */
089    @Override
090    public boolean equals(final Object o) {
091        if (!(o instanceof OperandStack)) {
092            return false;
093        }
094        final OperandStack s = (OperandStack) o;
095        return this.stack.equals(s.stack);
096    }
097
098    /**
099     * Returns a (typed!) clone of this.
100     *
101     * @see #clone()
102     */
103    public OperandStack getClone() {
104        return (OperandStack) this.clone();
105    }
106
107    /**
108     * Returns true IFF this OperandStack is empty.
109   */
110    public boolean isEmpty() {
111        return stack.isEmpty();
112    }
113
114    /**
115     * Returns the number of stack slots this stack can hold.
116     */
117    public int maxStack() {
118        return this.maxStack;
119    }
120
121    /**
122     * Returns the element on top of the stack. The element is not popped off the stack!
123     */
124    public Type peek() {
125        return peek(0);
126    }
127
128    /**
129   * Returns the element that's i elements below the top element; that means,
130   * iff i==0 the top element is returned. The element is not popped off the stack!
131   */
132    public Type peek(final int i) {
133        return stack.get(size()-i-1);
134    }
135
136    /**
137     * Returns the element on top of the stack. The element is popped off the stack.
138     */
139    public Type pop() {
140        final Type e = stack.remove(size()-1);
141        return e;
142    }
143
144    /**
145     * Pops i elements off the stack. ALWAYS RETURNS "null"!!!
146     */
147    public Type pop(final int i) {
148        for (int j=0; j<i; j++) {
149            pop();
150        }
151        return null;
152    }
153
154    /**
155     * Pushes a Type object onto the stack.
156     */
157    public void push(final Type type) {
158        if (type == null) {
159            throw new AssertionViolatedException("Cannot push NULL onto OperandStack.");
160        }
161        if (type == Type.BOOLEAN || type == Type.CHAR || type == Type.BYTE || type == Type.SHORT) {
162            throw new AssertionViolatedException("The OperandStack does not know about '"+type+"'; use Type.INT instead.");
163        }
164        if (slotsUsed() >= maxStack) {
165            throw new AssertionViolatedException(
166                "OperandStack too small, should have thrown proper Exception elsewhere. Stack: "+this);
167        }
168        stack.add(type);
169    }
170
171    /**
172     * Returns the size of this OperandStack; that means, how many Type objects there are.
173     */
174    public int size() {
175        return stack.size();
176    }
177
178    /**
179     * Returns the number of stack slots used.
180     * @see #maxStack()
181     */
182    public int slotsUsed() {
183        /*  XXX change this to a better implementation using a variable
184            that keeps track of the actual slotsUsed()-value monitoring
185            all push()es and pop()s.
186        */
187        int slots = 0;
188        for (int i=0; i<stack.size(); i++) {
189            slots += peek(i).getSize();
190        }
191        return slots;
192    }
193
194    /**
195     * Returns a String representation of this OperandStack instance.
196     */
197    @Override
198    public String toString() {
199        final StringBuilder sb = new StringBuilder();
200        sb.append("Slots used: ");
201        sb.append(slotsUsed());
202        sb.append(" MaxStack: ");
203        sb.append(maxStack);
204        sb.append(".\n");
205        for (int i=0; i<size(); i++) {
206            sb.append(peek(i));
207            sb.append(" (Size: ");
208            sb.append(String.valueOf(peek(i).getSize()));
209            sb.append(")\n");
210        }
211        return sb.toString();
212    }
213
214    /**
215     * Merges another stack state into this instance's stack state.
216     * See the Java Virtual Machine Specification, Second Edition, page 146: 4.9.2
217     * for details.
218     */
219    public void merge(final OperandStack s) {
220        try {
221        if ( (slotsUsed() != s.slotsUsed()) || (size() != s.size()) ) {
222            throw new StructuralCodeConstraintException(
223                "Cannot merge stacks of different size:\nOperandStack A:\n"+this+"\nOperandStack B:\n"+s);
224        }
225
226        for (int i=0; i<size(); i++) {
227            // If the object _was_ initialized and we're supposed to merge
228            // in some uninitialized object, we reject the code (see vmspec2, 4.9.4, last paragraph).
229            if ( (! (stack.get(i) instanceof UninitializedObjectType)) && (s.stack.get(i) instanceof UninitializedObjectType) ) {
230                throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
231            }
232            // Even harder, we're not initialized but are supposed to broaden
233            // the known object type
234            if ( (!(stack.get(i).equals(s.stack.get(i)))) &&
235                    (stack.get(i) instanceof UninitializedObjectType) && (!(s.stack.get(i) instanceof UninitializedObjectType))) {
236                throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
237            }
238            // on the other hand...
239            if (stack.get(i) instanceof UninitializedObjectType) { //if we have an uninitialized object here
240                if (! (s.stack.get(i) instanceof UninitializedObjectType)) { //that has been initialized by now
241                    stack.set(i, ((UninitializedObjectType) (stack.get(i))).getInitialized() ); //note that.
242                }
243            }
244            if (! stack.get(i).equals(s.stack.get(i))) {
245                if (    (stack.get(i) instanceof ReferenceType) &&
246                            (s.stack.get(i) instanceof ReferenceType)  ) {
247                    stack.set(i, ((ReferenceType) stack.get(i)).getFirstCommonSuperclass((ReferenceType) (s.stack.get(i))));
248                }
249                else{
250                    throw new StructuralCodeConstraintException(
251                        "Cannot merge stacks of different types:\nStack A:\n"+this+"\nStack B:\n"+s);
252                }
253            }
254        }
255        } catch (final ClassNotFoundException e) {
256        // FIXME: maybe not the best way to handle this
257        throw new AssertionViolatedException("Missing class: " + e, e);
258        }
259    }
260
261    /**
262     * Replaces all occurences of u in this OperandStack instance
263     * with an "initialized" ObjectType.
264     */
265    public void initializeObject(final UninitializedObjectType u) {
266        for (int i=0; i<stack.size(); i++) {
267            if (stack.get(i) == u) {
268                stack.set(i, u.getInitialized());
269            }
270        }
271    }
272
273}