KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > bcel > verifier > structurals > OperandStack


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 JavaDoc;
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 JavaDoc stack = new ArrayList JavaDoc();
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 JavaDoc clone(){
64         OperandStack newstack = new OperandStack(this.maxStack);
65         newstack.stack = (ArrayList JavaDoc) this.stack.clone();
66         return newstack;
67     }
68
69     /**
70      * Clears the stack.
71      */
72     public void clear(){
73         stack = new ArrayList JavaDoc();
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 JavaDoc 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 JavaDoc toString(){
192         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
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 JavaDoc 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 }
264
Popular Tags