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