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