View Javadoc

    1   /*
    2    * Copyright  2000-2004 The Apache Software Foundation
    3    *
    4    *  Licensed under the Apache License, Version 2.0 (the "License");
    5    *  you may not use this file except in compliance with the License.
    6    *  You may obtain a copy of the License at
    7    *
    8    *      http://www.apache.org/licenses/LICENSE-2.0
    9    *
    10   *  Unless required by applicable law or agreed to in writing, software
    11   *  distributed under the License is distributed on an "AS IS" BASIS,
    12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13   *  See the License for the specific language governing permissions and
    14   *  limitations under the License.
    15   *
    16   */
    17  package org.apache.bcel.verifier.structurals;
    18
    19
    20  import java.util.ArrayList;
    21  import org.apache.bcel.generic.ObjectType;
    22  import org.apache.bcel.generic.ReferenceType;
    23  import org.apache.bcel.generic.Type;
    24  import org.apache.bcel.verifier.exc.AssertionViolatedException;
    25  import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;
    26
    27  /***
    28   * This class implements a stack used for symbolic JVM stack simulation.
    29   * [It's used an an operand stack substitute.]
    30   * Elements of this stack are org.apache.bcel.generic.Type objects.
    31   *
    32   * @version $Id: OperandStack.java 386056 2006-03-15 11:31:56Z tcurdt $
    33   * @author Enver Haase
    34   */
    35  public class OperandStack{
    36
    37  	/*** We hold the stack information here. */
    38  	private ArrayList stack = new ArrayList();
    39
    40  	/*** The maximum number of stack slots this OperandStack instance may hold. */
    41  	private int maxStack;
    42
    43  	/***
    44  	 * Creates an empty stack with a maximum of maxStack slots.
    45  	 */
    46  	public OperandStack(int maxStack){
    47  		this.maxStack = maxStack;
    48  	}
    49
    50  	/***
    51  	 * Creates an otherwise empty stack with a maximum of maxStack slots and
    52  	 * the ObjectType 'obj' at the top.
    53  	 */
    54  	public OperandStack(int maxStack, ObjectType obj){
    55  		this.maxStack = maxStack;
    56  		this.push(obj);
    57  	}
    58  	/***
    59  	 * Returns a deep copy of this object; that means, the clone operates
    60  	 * on a new stack. However, the Type objects on the stack are
    61  	 * shared.
    62  	 */
    63  	protected Object clone(){
    64  		OperandStack newstack = new OperandStack(this.maxStack);
    65  		newstack.stack = (ArrayList) this.stack.clone();
    66  		return newstack;
    67  	}
    68
    69  	/***
    70  	 * Clears the stack.
    71  	 */
    72  	public void clear(){
    73  		stack = new ArrayList();
    74  	}
    75
    76  	/*** @return a hash code value for the object.
    77       */
    78  	public int hashCode() { return stack.hashCode(); }
    79
    80  	/***
    81  	 * Returns true if and only if this OperandStack
    82  	 * equals another, meaning equal lengths and equal
    83  	 * objects on the stacks.
    84  	 */
    85  	public boolean equals(Object o){
    86  		if (!(o instanceof OperandStack)) {
    87              return false;
    88          }
    89  		OperandStack s = (OperandStack) o;
    90  		return this.stack.equals(s.stack);
    91  	}
    92
    93  	/***
    94  	 * Returns a (typed!) clone of this.
    95  	 *
    96  	 * @see #clone()
    97  	 */
    98  	public OperandStack getClone(){
    99  		return (OperandStack) this.clone();
    100 	}
    101
    102 	/***
    103 	 * Returns true IFF this OperandStack is empty.
    104    */
    105 	public boolean isEmpty(){
    106 		return stack.isEmpty();
    107 	}
    108
    109 	/***
    110 	 * Returns the number of stack slots this stack can hold.
    111 	 */
    112 	public int maxStack(){
    113 		return this.maxStack;
    114 	}
    115
    116 	/***
    117 	 * Returns the element on top of the stack. The element is not popped off the stack!
    118 	 */
    119 	public Type peek(){
    120 		return peek(0);
    121 	}
    122
    123 	/***
    124    * Returns the element that's i elements below the top element; that means,
    125    * iff i==0 the top element is returned. The element is not popped off the stack!
    126    */
    127 	public Type peek(int i){
    128 		return (Type) stack.get(size()-i-1);
    129 	}
    130
    131 	/***
    132 	 * Returns the element on top of the stack. The element is popped off the stack.
    133 	 */
    134 	public Type pop(){
    135 		Type e = (Type) stack.remove(size()-1);
    136 		return e;
    137 	}
    138
    139 	/***
    140 	 * Pops i elements off the stack. ALWAYS RETURNS "null"!!!
    141 	 */
    142 	public Type pop(int i){
    143 		for (int j=0; j<i; j++){
    144 			pop();
    145 		}
    146 		return null;
    147 	}
    148
    149 	/***
    150 	 * Pushes a Type object onto the stack.
    151 	 */
    152 	public void push(Type type){
    153 		if (type == null) {
    154             throw new AssertionViolatedException("Cannot push NULL onto OperandStack.");
    155         }
    156 		if (type == Type.BOOLEAN || type == Type.CHAR || type == Type.BYTE || type == Type.SHORT){
    157 			throw new AssertionViolatedException("The OperandStack does not know about '"+type+"'; use Type.INT instead.");
    158 		}
    159 		if (slotsUsed() >= maxStack){
    160 			throw new AssertionViolatedException("OperandStack too small, should have thrown proper Exception elsewhere. Stack: "+this);
    161 		}
    162 		stack.add(type);
    163 	}
    164
    165 	/***
    166 	 * Returns the size of this OperandStack; that means, how many Type objects there are.
    167 	 */
    168 	public int size(){
    169 		return stack.size();
    170 	}
    171
    172 	/***
    173 	 * Returns the number of stack slots used.
    174 	 * @see #maxStack()
    175 	 */
    176 	public int slotsUsed(){
    177 		/*  XXX change this to a better implementation using a variable
    178 		    that keeps track of the actual slotsUsed()-value monitoring
    179 		    all push()es and pop()s.
    180 		*/
    181 		int slots = 0;
    182 		for (int i=0; i<stack.size(); i++){
    183 			slots += peek(i).getSize();
    184 		}
    185 		return slots;
    186 	}
    187
    188 	/***
    189 	 * Returns a String representation of this OperandStack instance.
    190 	 */
    191 	public String toString(){
    192 		StringBuffer sb = new StringBuffer();
    193 		sb.append("Slots used: ");
    194 		sb.append(slotsUsed());
    195 		sb.append(" MaxStack: ");
    196 		sb.append(maxStack);
    197 		sb.append(".\n");
    198 		for (int i=0; i<size(); i++){
    199 			sb.append(peek(i));
    200 			sb.append(" (Size: ");
    201 			sb.append(String.valueOf(peek(i).getSize()));
    202 			sb.append(")\n");
    203 		}
    204 		return sb.toString();
    205 	}
    206
    207 	/***
    208 	 * Merges another stack state into this instance's stack state.
    209 	 * See the Java Virtual Machine Specification, Second Edition, page 146: 4.9.2
    210 	 * for details.
    211 	 */
    212 	public void merge(OperandStack s){
    213 	    try {
    214 		if ( (slotsUsed() != s.slotsUsed()) || (size() != s.size()) ) {
    215             throw new StructuralCodeConstraintException("Cannot merge stacks of different size:\nOperandStack A:\n"+this+"\nOperandStack B:\n"+s);
    216         }
    217
    218 		for (int i=0; i<size(); i++){
    219 			// If the object _was_ initialized and we're supposed to merge
    220 			// in some uninitialized object, we reject the code (see vmspec2, 4.9.4, last paragraph).
    221 			if ( (! (stack.get(i) instanceof UninitializedObjectType)) && (s.stack.get(i) instanceof UninitializedObjectType) ){
    222 				throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
    223 			}
    224 			// Even harder, we're not initialized but are supposed to broaden
    225 			// the known object type
    226 			if ( (!(stack.get(i).equals(s.stack.get(i)))) && (stack.get(i) instanceof UninitializedObjectType) && (!(s.stack.get(i) instanceof UninitializedObjectType))){
    227 				throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
    228 			}
    229 			// on the other hand...
    230 			if (stack.get(i) instanceof UninitializedObjectType){ //if we have an uninitialized object here
    231 				if (! (s.stack.get(i) instanceof UninitializedObjectType)){ //that has been initialized by now
    232 					stack.set(i, ((UninitializedObjectType) (stack.get(i))).getInitialized() ); //note that.
    233 				}
    234 			}
    235 			if (! stack.get(i).equals(s.stack.get(i))){
    236 				if (	(stack.get(i) instanceof ReferenceType) &&
    237 							(s.stack.get(i) instanceof ReferenceType)  ){
    238 					stack.set(i, ((ReferenceType) stack.get(i)).getFirstCommonSuperclass((ReferenceType) (s.stack.get(i))));
    239 				}
    240 				else{
    241 					throw new StructuralCodeConstraintException("Cannot merge stacks of different types:\nStack A:\n"+this+"\nStack B:\n"+s);
    242 				}
    243 			}
    244 		}
    245 	    } catch (ClassNotFoundException e) {
    246 		// FIXME: maybe not the best way to handle this
    247 		throw new AssertionViolatedException("Missing class: " + e.toString());
    248 	    }
    249 	}
    250
    251 	/***
    252 	 * Replaces all occurences of u in this OperandStack instance
    253 	 * with an "initialized" ObjectType.
    254 	 */
    255 	public void initializeObject(UninitializedObjectType u){
    256 		for (int i=0; i<stack.size(); i++){
    257 			if (stack.get(i) == u){
    258 				stack.set(i, u.getInitialized());
    259 			}
    260 		}
    261 	}
    262
    263 }