1 package org.apache.bcel.verifier.structurals;
2
3 /* ====================================================================
4 * The Apache Software License, Version 1.1
5 *
6 * Copyright (c) 2001 The Apache Software Foundation. All rights
7 * reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 *
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in
18 * the documentation and/or other materials provided with the
19 * distribution.
20 *
21 * 3. The end-user documentation included with the redistribution,
22 * if any, must include the following acknowledgment:
23 * "This product includes software developed by the
24 * Apache Software Foundation (http://www.apache.org/)."
25 * Alternately, this acknowledgment may appear in the software itself,
26 * if and wherever such third-party acknowledgments normally appear.
27 *
28 * 4. The names "Apache" and "Apache Software Foundation" and
29 * "Apache BCEL" must not be used to endorse or promote products
30 * derived from this software without prior written permission. For
31 * written permission, please contact apache@apache.org.
32 *
33 * 5. Products derived from this software may not be called "Apache",
34 * "Apache BCEL", nor may "Apache" appear in their name, without
35 * prior written permission of the Apache Software Foundation.
36 *
37 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
38 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
39 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
40 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
41 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
43 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
44 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
45 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
46 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
47 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
48 * SUCH DAMAGE.
49 * ====================================================================
50 *
51 * This software consists of voluntary contributions made by many
52 * individuals on behalf of the Apache Software Foundation. For more
53 * information on the Apache Software Foundation, please see
54 * <http://www.apache.org/>.
55 */
56
57 import org.apache.bcel.generic.*;
58 import org.apache.bcel.verifier.exc.*;
59 import java.util.*;
60
61 /***
62 * This class implements a stack used for symbolic JVM stack simulation.
63 * [It's used an an operand stack substitute.]
64 * Elements of this stack are org.apache.bcel.generic.Type objects.
65 *
66 * @version $Id: OperandStack.java,v 1.2 2002/08/02 11:57:51 enver Exp $
67 * @author <A HREF="http://www.inf.fu-berlin.de/~ehaase"/>Enver Haase</A>
68 */
69 public class OperandStack{
70
71 /*** We hold the stack information here. */
72 private ArrayList stack = new ArrayList();
73
74 /*** The maximum number of stack slots this OperandStack instance may hold. */
75 private int maxStack;
76
77 /***
78 * Creates an empty stack with a maximum of maxStack slots.
79 */
80 public OperandStack(int maxStack){
81 this.maxStack = maxStack;
82 }
83
84 /***
85 * Creates an otherwise empty stack with a maximum of maxStack slots and
86 * the ObjectType 'obj' at the top.
87 */
88 public OperandStack(int maxStack, ObjectType obj){
89 this.maxStack = maxStack;
90 this.push(obj);
91 }
92 /***
93 * Returns a deep copy of this object; that means, the clone operates
94 * on a new stack. However, the Type objects on the stack are
95 * shared.
96 */
97 protected Object clone(){
98 OperandStack newstack = new OperandStack(this.maxStack);
99 newstack.stack = (ArrayList) this.stack.clone();
100 return newstack;
101 }
102
103 /***
104 * Clears the stack.
105 */
106 public void clear(){
107 stack = new ArrayList();
108 }
109
110 /***
111 * Returns true if and only if this OperandStack
112 * equals another, meaning equal lengths and equal
113 * objects on the stacks.
114 */
115 public boolean equals(Object o){
116 if (!(o instanceof OperandStack)) return false;
117 OperandStack s = (OperandStack) o;
118 return this.stack.equals(s.stack);
119 }
120
121 /***
122 * Returns a (typed!) clone of this.
123 *
124 * @see #clone()
125 */
126 public OperandStack getClone(){
127 return (OperandStack) this.clone();
128 }
129
130 /***
131 * Returns true IFF this OperandStack is empty.
132 */
133 public boolean isEmpty(){
134 return stack.isEmpty();
135 }
136
137 /***
138 * Returns the number of stack slots this stack can hold.
139 */
140 public int maxStack(){
141 return this.maxStack;
142 }
143
144 /***
145 * Returns the element on top of the stack. The element is not popped off the stack!
146 */
147 public Type peek(){
148 return peek(0);
149 }
150
151 /***
152 * Returns the element that's i elements below the top element; that means,
153 * iff i==0 the top element is returned. The element is not popped off the stack!
154 */
155 public Type peek(int i){
156 return (Type) stack.get(size()-i-1);
157 }
158
159 /***
160 * Returns the element on top of the stack. The element is popped off the stack.
161 */
162 public Type pop(){
163 Type e = (Type) stack.remove(size()-1);
164 return e;
165 }
166
167 /***
168 * Pops i elements off the stack. ALWAYS RETURNS "null"!!!
169 */
170 public Type pop(int i){
171 for (int j=0; j<i; j++){
172 pop();
173 }
174 return null;
175 }
176
177 /***
178 * Pushes a Type object onto the stack.
179 */
180 public void push(Type type){
181 if (type == null) throw new AssertionViolatedException("Cannot push NULL onto OperandStack.");
182 if (type == Type.BOOLEAN || type == Type.CHAR || type == Type.BYTE || type == Type.SHORT){
183 throw new AssertionViolatedException("The OperandStack does not know about '"+type+"'; use Type.INT instead.");
184 }
185 if (slotsUsed() >= maxStack){
186 throw new AssertionViolatedException("OperandStack too small, should have thrown proper Exception elsewhere. Stack: "+this);
187 }
188 stack.add(type);
189 }
190
191 /***
192 * Returns the size of this OperandStack; that means, how many Type objects there are.
193 */
194 int size(){
195 return stack.size();
196 }
197
198 /***
199 * Returns the number of stack slots used.
200 * @see #maxStack()
201 */
202 public int slotsUsed(){
203 /* XXX change this to a better implementation using a variable
204 that keeps track of the actual slotsUsed()-value monitoring
205 all push()es and pop()s.
206 */
207 int slots = 0;
208 for (int i=0; i<stack.size(); i++){
209 slots += peek(i).getSize();
210 }
211 return slots;
212 }
213
214 /***
215 * Returns a String representation of this OperandStack instance.
216 */
217 public String toString(){
218 String s = "Slots used: "+slotsUsed()+" MaxStack: "+maxStack+".\n";
219 for (int i=0; i<size(); i++){
220 s+=peek(i)+" (Size: "+peek(i).getSize()+")\n";
221 }
222 return s;
223 }
224
225 /***
226 * Merges another stack state into this instance's stack state.
227 * See the Java Virtual Machine Specification, Second Edition, page 146: 4.9.2
228 * for details.
229 */
230 public void merge(OperandStack s){
231 if ( (slotsUsed() != s.slotsUsed()) || (size() != s.size()) )
232 throw new StructuralCodeConstraintException("Cannot merge stacks of different size:\nOperandStack A:\n"+this+"\nOperandStack B:\n"+s);
233
234 for (int i=0; i<size(); i++){
235 // If the object _was_ initialized and we're supposed to merge
236 // in some uninitialized object, we reject the code (see vmspec2, 4.9.4, last paragraph).
237 if ( (! (stack.get(i) instanceof UninitializedObjectType)) && (s.stack.get(i) instanceof UninitializedObjectType) ){
238 throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
239 }
240 // Even harder, we're not initialized but are supposed to broaden
241 // the known object type
242 if ( (!(stack.get(i).equals(s.stack.get(i)))) && (stack.get(i) instanceof UninitializedObjectType) && (!(s.stack.get(i) instanceof UninitializedObjectType))){
243 throw new StructuralCodeConstraintException("Backwards branch with an uninitialized object on the stack detected.");
244 }
245 // on the other hand...
246 if (stack.get(i) instanceof UninitializedObjectType){ //if we have an uninitialized object here
247 if (! (s.stack.get(i) instanceof UninitializedObjectType)){ //that has been initialized by now
248 stack.set(i, ((UninitializedObjectType) (stack.get(i))).getInitialized() ); //note that.
249 }
250 }
251 if (! stack.get(i).equals(s.stack.get(i))){
252 if ( (stack.get(i) instanceof ReferenceType) &&
253 (s.stack.get(i) instanceof ReferenceType) ){
254 stack.set(i, ((ReferenceType) stack.get(i)).getFirstCommonSuperclass((ReferenceType) (s.stack.get(i))));
255 }
256 else{
257 throw new StructuralCodeConstraintException("Cannot merge stacks of different types:\nStack A:\n"+this+"\nStack B:\n"+s);
258 }
259 }
260 }
261 }
262
263 /***
264 * Replaces all occurences of u in this OperandStack instance
265 * with an "initialized" ObjectType.
266 */
267 public void initializeObject(UninitializedObjectType u){
268 for (int i=0; i<stack.size(); i++){
269 if (stack.get(i) == u){
270 stack.set(i, u.getInitialized());
271 }
272 }
273 }
274
275 }
This page was automatically generated by Maven