    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one
    003 * or more contributor license agreements.  See the NOTICE file
    004 * distributed with this work for additional information
    005 * regarding copyright ownership.  The ASF licenses this file
    006 * to you under the Apache License, Version 2.0 (the
    007 * "License"); you may not use this file except in compliance
    008 * with the License.  You may obtain a copy of the License at
    009 *
    010 *   https://www.apache.org/licenses/LICENSE-2.0
    011 *
    012 * Unless required by applicable law or agreed to in writing,
    013 * software distributed under the License is distributed on an
    014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    015 * KIND, either express or implied.  See the License for the
    016 * specific language governing permissions and limitations
    017 * under the License.
    018 */
    019package org.apache.bcel.verifier.structurals;
    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. [It's used as an operand stack substitute.]
    031 * Elements of this stack are {@link Type} objects.
    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        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) 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 occurrences 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}