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 020import java.util.ArrayList; 021 022import org.apache.bcel.generic.ObjectType; 023import org.apache.bcel.generic.ReferenceType; 024import org.apache.bcel.generic.Type; 025import org.apache.bcel.verifier.exc.AssertionViolatedException; 026import org.apache.bcel.verifier.exc.StructuralCodeConstraintException; 027 028/** 029 * This class implements a stack used for symbolic JVM stack simulation. [It's used as an operand stack substitute.] 030 * Elements of this stack are {@link Type} objects. 031 * 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 this.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) this.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 occurences 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}