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}