View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.javaflow.bytecode.transformation.bcel.analyser;
18  
19  import org.apache.bcel.generic.*;
20  import org.apache.bcel.verifier.exc.*;
21  import java.util.*;
22  
23  /**
24   * This class implements a stack used for symbolic JVM stack simulation.
25   * [It's used an an operand stack substitute.]
26   * Elements of this stack are org.apache.bcel.generic.Type objects.
27   * 
28   * WARNING! These classes are a fork of the bcel verifier.
29   *
30   * @version $Id: OperandStack.java 480487 2006-11-29 08:54:42Z bayard $
31   * @author <A HREF="http://www.inf.fu-berlin.de/~ehaase"/>Enver Haase</A>
32   */
33  public class OperandStack{
34  
35  	/** We hold the stack information here. */
36  	private ArrayList stack = new ArrayList();
37  
38  	/** The maximum number of stack slots this OperandStack instance may hold. */
39  	private int maxStack;
40  
41  	/**
42  	 * Creates an empty stack with a maximum of maxStack slots.
43  	 */
44  	public OperandStack(int maxStack){
45  		this.maxStack = maxStack;
46  	}
47  
48  	/**
49  	 * Creates an otherwise empty stack with a maximum of maxStack slots and
50  	 * the ObjectType 'obj' at the top.
51  	 */
52  	public OperandStack(int maxStack, ObjectType obj){
53  		this.maxStack = maxStack;
54  		this.push(obj);
55  	}	
56  	/**
57  	 * Returns a deep copy of this object; that means, the clone operates
58  	 * on a new stack. However, the Type objects on the stack are
59  	 * shared.
60  	 */
61  	protected Object clone(){
62  		OperandStack newstack = new OperandStack(this.maxStack);
63  		newstack.stack = (ArrayList) this.stack.clone();
64  		return newstack;
65  	}
66  
67  	/**
68  	 * Clears the stack.
69  	 */
70  	public void clear(){
71  		stack = new ArrayList();
72  	}
73  
74  	/**
75  	 * Returns true if and only if this OperandStack
76  	 * equals another, meaning equal lengths and equal
77  	 * objects on the stacks.
78  	 */
79  	public boolean equals(Object o){
80  		if (!(o instanceof OperandStack)) return false;
81  		OperandStack s = (OperandStack) o;
82  		return this.stack.equals(s.stack);
83  	}
84  
85  	/**
86  	 * Returns a (typed!) clone of this.
87  	 *
88  	 * @see #clone()
89  	 */
90  	public OperandStack getClone(){
91  		return (OperandStack) this.clone();
92  	}
93  
94  	/**
95  	 * Returns true IFF this OperandStack is empty.
96     */
97  	public boolean isEmpty(){
98  		return stack.isEmpty();
99  	}
100 
101 	/**
102 	 * Returns the number of stack slots this stack can hold.
103 	 */
104 	public int maxStack(){
105 		return this.maxStack;
106 	}
107 
108 	/**
109 	 * Returns the element on top of the stack. The element is not popped off the stack!
110 	 */
111 	public Type peek(){
112 		return peek(0);
113 	}
114 
115 	/**
116    * Returns the element that's i elements below the top element; that means,
117    * iff i==0 the top element is returned. The element is not popped off the stack!
118    */
119 	public Type peek(int i){
120 		return (Type) stack.get(size()-i-1);
121 	}
122 
123 	/**
124 	 * Returns the element on top of the stack. The element is popped off the stack.
125 	 */
126 	public Type pop(){
127 		Type e = (Type) stack.remove(size()-1);
128 		return e;
129 	}
130 
131 	/**
132 	 * Pops i elements off the stack. ALWAYS RETURNS "null"!!!
133 	 */
134 	public Type pop(int i){
135 		for (int j=0; j<i; j++){
136 			pop();
137 		}
138 		return null;
139 	}
140 
141 	/**
142 	 * Pushes a Type object onto the stack.
143 	 */
144 	public void push(Type type){
145 		if (type == null) throw new AssertionViolatedException("Cannot push NULL onto OperandStack.");
146 		if (type == Type.BOOLEAN || type == Type.CHAR || type == Type.BYTE || type == Type.SHORT){
147 			throw new AssertionViolatedException("The OperandStack does not know about '"+type+"'; use Type.INT instead.");
148 		}
149 		if (slotsUsed() >= maxStack){
150 			throw new AssertionViolatedException("OperandStack too small, should have thrown proper Exception elsewhere. Stack: "+this);
151 		}
152 		stack.add(type);
153 	}
154 
155 	/**
156 	 * Returns the size of this OperandStack; that means, how many Type objects there are.
157 	 */
158 	public int size(){
159 		return stack.size();
160 	}
161 
162 	/**
163 	 * Returns the number of stack slots used.
164 	 * @see #maxStack()
165 	 */	
166 	public int slotsUsed(){
167 		/*  XXX change this to a better implementation using a variable
168 		    that keeps track of the actual slotsUsed()-value monitoring
169 		    all push()es and pop()s.
170 		*/
171 		int slots = 0;
172 		for (int i=0; i<stack.size(); i++){
173 			slots += peek(i).getSize();
174 		}
175 		return slots;
176 	}
177 	
178 	/**
179 	 * Returns a String representation of this OperandStack instance.
180 	 */
181 	public String toString(){
182 		String s = "Slots used: "+slotsUsed()+" MaxStack: "+maxStack+".\n";
183 		for (int i=0; i<size(); i++){
184 			s+=peek(i)+" (Size: "+peek(i).getSize()+")\n";
185 		}
186 		return s;
187 	}
188 
189 	/**
190 	 * Merges another stack state into this instance's stack state.
191 	 * See the Java Virtual Machine Specification, Second Edition, page 146: 4.9.2
192 	 * for details.
193 	 */
194 	public void merge(OperandStack s){
195 		if ( (slotsUsed() != s.slotsUsed()) || (size() != s.size()) )
196 			throw new StructuralCodeConstraintException("Cannot merge stacks of different size:\nOperandStack A:\n"+this+"\nOperandStack B:\n"+s);
197 		
198 		for (int i=0; i<size(); i++){
199             this.stack.set(i, Frame.merge((Type)this.stack.get(i), (Type)s.stack.get(i), true));
200 		}
201 	}
202 
203 	/**
204 	 * Replaces all occurences of u in this OperandStack instance
205 	 * with an "initialized" ObjectType.
206 	 */
207 	public void initializeObject(UninitializedObjectType u){
208 		for (int i=0; i<stack.size(); i++){
209             if (stack.get(i) == u){
210 				stack.set(i, u.getInitialized());
211 			}
212 		}
213 	}
214 
215 }