    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}