KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > ba > Frame


1 /*
2  * Bytecode Analysis Framework
3  * Copyright (C) 2003,2004 University of Maryland
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */

19
20 package edu.umd.cs.findbugs.ba;
21
22 import java.util.ArrayList JavaDoc;
23 import java.util.BitSet JavaDoc;
24 import java.util.Collection JavaDoc;
25 import java.util.Collections JavaDoc;
26
27 import org.apache.bcel.Constants;
28 import org.apache.bcel.generic.ConstantPoolGen;
29 import org.apache.bcel.generic.INVOKESTATIC;
30 import org.apache.bcel.generic.Instruction;
31 import org.apache.bcel.generic.InvokeInstruction;
32 import org.apache.bcel.generic.StackConsumer;
33
34 import edu.umd.cs.findbugs.SystemProperties;
35 import edu.umd.cs.findbugs.ba.vna.ValueNumber;
36 import static edu.umd.cs.findbugs.ba.Debug.*;
37
38 /**
39  * Generic class for representing a Java stack frame as a dataflow value. A
40  * frame consists of "slots", which represent the local variables and values on
41  * the Java operand stack. Slots 0 .. <code>getNumLocals() - 1</code>
42  * represent the local variables. Slots <code>getNumLocals()</code> ..
43  * <code>getNumSlots() - 1</code> represent the Java operand stack. <p/>
44  * <p>
45  * Frame is parametized by "ValueType", which is the type of value to be stored
46  * in the Frame's slots. This type must form a lattice, according to the
47  * abstract mergeValues() operation in the corresponding analysis class (which
48  * should be derived from FrameDataflowAnalysis). When a Frame is constructed,
49  * all of its slots will contain null. The analysis is responsible for
50  * initializing created Frames with default values at the appropriate time.
51  * Typically, only initEntryFact() will need to do this. <p/>
52  * <p>
53  * A Frame may have the special "TOP" value. Such frames serve as the identity
54  * element for the meet operation operation. <p/>
55  * <p>
56  * A Frame may have the special "BOTTOM" value. The result of merging any frame
57  * with BOTTOM is BOTTOM.
58  *
59  * @author David Hovemeyer
60  * @see FrameDataflowAnalysis
61  */

62 public abstract class Frame<ValueType> {
63
64     // //////////////////////////////////////////////////////////////////////////////////
65
// Instance variables
66
// //////////////////////////////////////////////////////////////////////////////////
67

68     private int lastUpdateTimestamp;
69
70     /**
71      * Number of local variables in the method.
72      */

73     private int numLocals;
74
75     /**
76      * Array storing the values of local variables and operand stack slots.
77      */

78     private ArrayList JavaDoc<ValueType> slotList;
79
80     /**
81      * Flag marking this frame as a special "TOP" value. Such Frames serve as
82      * the identity element when merging.
83      */

84     private boolean isTop;
85
86     /**
87      * Flag marking this frame as a special "BOTTOM" value. Such Frames arise
88      * when merging two frames of different size.
89      */

90     private boolean isBottom;
91
92     /**
93      * Default number of stack slots to preallocate space for.
94      */

95     private static final int DEFAULT_STACK_CAPACITY = 10;
96
97     // //////////////////////////////////////////////////////////////////////////////////
98
// Methods
99
// //////////////////////////////////////////////////////////////////////////////////
100

101     /**
102      * Constructor. This version of the constructor is for subclasses for which
103      * it is always safe to call getDefaultValue(), even when the object is not
104      * fully initialized.
105      *
106      * @param numLocals
107      * number of local variable slots in the method
108      */

109     public Frame(int numLocals) {
110         this.numLocals = numLocals;
111         this.slotList = new ArrayList JavaDoc<ValueType>(numLocals
112                 + DEFAULT_STACK_CAPACITY);
113         for (int i = 0; i < numLocals; ++i)
114             slotList.add(null);
115     }
116
117     /**
118      * Return whether or not this object the special "TOP" value for Frames.
119      * Such Frames are the identity element of the meet operation.
120      */

121     public boolean isTop() {
122         return isTop;
123     }
124
125     /**
126      * Make this frame the special "TOP" value. Such Frames are the identity
127      * element of the meet operation.
128      */

129     public void setTop() {
130         isTop = true;
131         isBottom = false;
132         lastUpdateTimestamp = 0;
133     }
134
135     /**
136      * Return whether or not this object is the special "BOTTOM" value for
137      * Frames. Such Frames arise when merging two frames of different size.
138      */

139     public boolean isBottom() {
140         return isBottom;
141     }
142
143     /**
144      * Make this Frame the special "BOTTOM" value. Such Frames arise when
145      * merging two frames of different size.
146      */

147     public void setBottom() {
148         isBottom = true;
149         isTop = false;
150     }
151
152     /**
153      * Set the Frame to be valid (neither TOP nor BOTTOM).
154      */

155     public void setValid() {
156         isTop = isBottom = false;
157     }
158
159     /**
160      * Is the frame valid (meaning it is not TOP or BOTTOM)?
161      */

162     public boolean isValid() {
163         return !isTop() && !isBottom();
164     }
165
166     /**
167      * Push a value onto the Java operand stack.
168      *
169      * @param value
170      * the ValueType to push
171      */

172     public void pushValue(ValueType value) {
173         if (VERIFY_INTEGRITY && value == null)
174             throw new IllegalArgumentException JavaDoc();
175         if (!isValid())
176             throw new IllegalStateException JavaDoc("accessing top or bottom frame");
177         slotList.add(value);
178     }
179
180     /**
181      * Pop a value off of the Java operand stack.
182      *
183      * @return the value that was popped
184      * @throws DataflowAnalysisException
185      * if the Java operand stack is empty
186      */

187     public ValueType popValue() throws DataflowAnalysisException {
188         if (!isValid())
189             throw new DataflowAnalysisException("accessing top or bottom frame");
190         if (slotList.size() == numLocals)
191             throw new DataflowAnalysisException("operand stack empty");
192         return slotList.remove(slotList.size() - 1);
193     }
194
195     /**
196      * Get the value on the top of the Java operand stack.
197      *
198      * @throws DataflowAnalysisException
199      * if the Java operand stack is empty
200      */

201     public ValueType getTopValue() throws DataflowAnalysisException {
202         if (!isValid())
203             throw new DataflowAnalysisException("accessing top or bottom frame");
204         assert slotList.size() >= numLocals;
205         if (slotList.size() == numLocals)
206             throw new DataflowAnalysisException("operand stack is empty");
207         return slotList.get(slotList.size() - 1);
208     }
209
210     /**
211      * Get the values on the top of the Java operand stack. The top stack item
212      * is placed at the end of the array, so that to restore the values to the
213      * stack, you would push them in the order they appear in the array.
214      */

215     public void getTopStackWords(ValueType[] valueList)
216             throws DataflowAnalysisException {
217         int stackDepth = getStackDepth();
218         if (valueList.length > stackDepth)
219             throw new DataflowAnalysisException("not enough values on stack");
220         int numSlots = slotList.size();
221         for (int i = numSlots - valueList.length, j = 0; i < numSlots; ++i, ++j) {
222             valueList[j] = slotList.get(i);
223         }
224     }
225
226     /**
227      * Get a value on the operand stack.
228      *
229      * @param loc
230      * the stack location, counting downwards from the top (location
231      * 0)
232      */

233     public ValueType getStackValue(int loc) throws DataflowAnalysisException {
234         if (!isValid())
235             throw new DataflowAnalysisException(
236                     "Accessing TOP or BOTTOM frame!");
237         int stackDepth = getStackDepth();
238         if (loc >= stackDepth)
239             throw new DataflowAnalysisException(
240                     "not enough values on stack: access=" + loc + ", avail="
241                             + stackDepth);
242         return slotList.get(slotList.size() - (loc + 1));
243     }
244
245     /**
246      * Get a the location in the frame of a value on the operand stack.
247      *
248      * @param loc
249      * the stack location, counting downwards from the top (location
250      * 0)
251      */

252     public int getStackLocation(int loc) throws DataflowAnalysisException {
253         int stackDepth = getStackDepth();
254         if (loc >= stackDepth)
255             throw new DataflowAnalysisException(
256                     "not enough values on stack: access=" + loc + ", avail="
257                             + stackDepth);
258         return slotList.size() - (loc + 1);
259     }
260
261     /**
262      * Get the value corresponding to the object instance used in the given
263      * instruction. This relies on the observation that in instructions which
264      * use an object instance (such as getfield, invokevirtual, etc.), the
265      * object instance is the first operand used by the instruction.
266      *
267      * @param ins
268      * the instruction
269      * @param cpg
270      * the ConstantPoolGen for the method
271      */

272     public ValueType getInstance(Instruction ins, ConstantPoolGen cpg)
273             throws DataflowAnalysisException {
274         return getStackValue(getInstanceStackLocation(ins, cpg));
275     }
276
277     /**
278      * Get the stack location (counting down from top of stack, starting at 0)
279      * containing the object instance referred to by given instruction. This
280      * relies on the observation that in instructions which use an object
281      * instance (such as getfield, invokevirtual, etc.), the object instance is
282      * the first operand used by the instruction.
283      *
284      * <p>
285      * The value returned may be passed to getStackValue(int).
286      * </p>
287      *
288      * @param ins
289      * the Instruction
290      * @param cpg
291      * the ConstantPoolGen for the method
292      * @return stack location (counting down from top of stack, starting at 0)
293      * containing the object instance
294      * @throws DataflowAnalysisException
295      */

296     public int getInstanceStackLocation(Instruction ins, ConstantPoolGen cpg)
297             throws DataflowAnalysisException {
298         int numConsumed = ins.consumeStack(cpg);
299         if (numConsumed == Constants.UNPREDICTABLE)
300             throw new DataflowAnalysisException(
301                     "Unpredictable stack consumption in " + ins);
302         return numConsumed - 1;
303     }
304
305     /**
306      * Get the slot the object instance referred to by given instruction is
307      * located in.
308      *
309      * @param ins
310      * the Instruction
311      * @param cpg
312      * the ConstantPoolGen for the method
313      * @return stack slot the object instance is in
314      * @throws DataflowAnalysisException
315      */

316     public int getInstanceSlot(Instruction ins, ConstantPoolGen cpg)
317             throws DataflowAnalysisException {
318         if (!isValid()) {
319             throw new DataflowAnalysisException("Accessing invalid frame at "
320                     + ins);
321         }
322         int numConsumed = ins.consumeStack(cpg);
323         if (numConsumed == Constants.UNPREDICTABLE)
324             throw new DataflowAnalysisException(
325                     "Unpredictable stack consumption in " + ins);
326         if (numConsumed > getStackDepth())
327             throw new DataflowAnalysisException("Stack underflow " + ins);
328         return getNumSlots() - numConsumed;
329     }
330
331     /**
332      * Get the number of arguments passed to given method invocation.
333      *
334      * @param ins
335      * the method invocation instruction
336      * @param cpg
337      * the ConstantPoolGen for the class containing the method
338      * @return number of arguments; note that this excludes the object instance
339      * for instance methods
340      * @throws DataflowAnalysisException
341      */

342     public int getNumArguments(InvokeInstruction ins, ConstantPoolGen cpg)
343             throws DataflowAnalysisException {
344         int numConsumed = getNumArgumentsIncludingObjectInstance(ins, cpg);
345         return (ins instanceof INVOKESTATIC) ? numConsumed : numConsumed - 1;
346     }
347
348     /**
349      * Get the number of arguments passed to given method invocation, including
350      * the object instance if the call is to an instance method.
351      *
352      * @param ins
353      * the method invocation instruction
354      * @param cpg
355      * the ConstantPoolGen for the class containing the method
356      * @return number of arguments, including object instance if appropriate
357      * @throws DataflowAnalysisException
358      */

359     public int getNumArgumentsIncludingObjectInstance(InvokeInstruction ins,
360             ConstantPoolGen cpg) throws DataflowAnalysisException {
361         int numConsumed = ins.consumeStack(cpg);
362         if (numConsumed == Constants.UNPREDICTABLE)
363             throw new DataflowAnalysisException(
364                     "Unpredictable stack consumption in " + ins);
365         return numConsumed;
366     }
367
368     /**
369      * Get the <i>i</i>th argument passed to given method invocation.
370      *
371      * @param ins
372      * the method invocation instruction
373      * @param cpg
374      * the ConstantPoolGen for the class containing the method
375      * @param i
376      * index of the argument; 0 for the first argument, etc.
377      * @param numArguments
378      * total number of arguments to the method
379      * @return the <i>i</i>th argument
380      * @throws DataflowAnalysisException
381      */

382     public ValueType getArgument(InvokeInstruction ins, ConstantPoolGen cpg,
383             int i, int numArguments) throws DataflowAnalysisException {
384         if (i >= numArguments)
385             throw new IllegalArgumentException JavaDoc();
386         return getStackValue((numArguments - 1) - i);
387     }
388
389     /**
390      * Get the stack slot that will contain given method argument. Assumes that
391      * this frame is at the location (just before) a method invocation
392      * instruction.
393      *
394      * @param i
395      * the argument index: 0 for first arg, etc.
396      * @param numArguments
397      * total number of arguments to the called method
398      * @return slot containing the argument value
399      */

400     public int getArgumentSlot(int i, int numArguments) {
401         if (i >= numArguments)
402             throw new IllegalArgumentException JavaDoc();
403
404         return (slotList.size() - numArguments) + i;
405     }
406
407     /**
408      * Get the <i>i</i>th operand used by given instruction.
409      *
410      * @param ins
411      * the instruction, which must be a StackConsumer
412      * @param cpg
413      * the ConstantPoolGen
414      * @param i
415      * index of operand to get: 0 for the first operand, etc.
416      * @return the <i>i</i>th operand used by the given instruction
417      * @throws DataflowAnalysisException
418      */

419     public ValueType getOperand(StackConsumer ins, ConstantPoolGen cpg, int i)
420             throws DataflowAnalysisException {
421         int numOperands = ins.consumeStack(cpg);
422         if (numOperands == Constants.UNPREDICTABLE)
423             throw new DataflowAnalysisException(
424                     "Unpredictable stack consumption in " + ins);
425         return getStackValue((numOperands - 1) - i);
426     }
427
428     /**
429      * Get set of arguments passed to a method invocation which match given
430      * predicate.
431      *
432      * @param invokeInstruction
433      * the InvokeInstruction
434      * @param cpg
435      * the ConstantPoolGen
436      * @param chooser
437      * predicate to choose which argument values should be in the
438      * returned set
439      * @return BitSet specifying which arguments match the predicate, indexed by
440      * argument number (starting from 0)
441      * @throws DataflowAnalysisException
442      */

443     public BitSet JavaDoc getArgumentSet(InvokeInstruction invokeInstruction,
444             ConstantPoolGen cpg, DataflowValueChooser<ValueType> chooser)
445             throws DataflowAnalysisException {
446         BitSet JavaDoc chosenArgSet = new BitSet JavaDoc();
447         int numArguments = getNumArguments(invokeInstruction, cpg);
448
449         for (int i = 0; i < numArguments; ++i) {
450             ValueType value = getArgument(invokeInstruction, cpg, i,
451                     numArguments);
452             if (chooser.choose(value))
453                 chosenArgSet.set(i);
454         }
455
456         return chosenArgSet;
457     }
458
459     /**
460      * Clear the Java operand stack. Only local variable slots will remain in
461      * the frame.
462      */

463     public void clearStack() {
464         if (!isValid())
465             throw new IllegalStateException JavaDoc("accessing top or bottom frame");
466         assert slotList.size() >= numLocals;
467         if (slotList.size() > numLocals)
468             slotList.subList(numLocals, slotList.size()).clear();
469     }
470
471     /**
472      * Get the depth of the Java operand stack.
473      */

474     public int getStackDepth() {
475         return slotList.size() - numLocals;
476     }
477
478     /**
479      * Get the number of locals.
480      */

481     public int getNumLocals() {
482         return numLocals;
483     }
484
485     /**
486      * Get the number of slots (locals plus stack values).
487      */

488     public int getNumSlots() {
489         return slotList.size();
490     }
491
492     /**
493      * Get the value at the <i>n</i>th slot.
494      *
495      * @param n
496      * the slot to get the value of
497      * @return the value in the slot
498      */

499     public ValueType getValue(int n) {
500         if (!isValid())
501             throw new IllegalStateException JavaDoc("accessing top or bottom frame");
502         return slotList.get(n);
503     }
504
505     /**
506      * Set the value at the <i>n</i>th slot.
507      *
508      * @param n
509      * the slot in which to set a new value
510      * @param value
511      * the value to set
512      */

513     public void setValue(int n, ValueType value) {
514         if (VERIFY_INTEGRITY && value == null)
515             throw new IllegalArgumentException JavaDoc();
516         if (!isValid())
517             throw new IllegalStateException JavaDoc("accessing top or bottom frame");
518         slotList.set(n, value);
519     }
520
521     /**
522      * Return true if this stack frame is the same as the one given as a
523      * parameter.
524      *
525      * @param other
526      * the other Frame
527      * @return true if the frames are the same, false otherwise
528      */

529     public boolean sameAs(Frame<ValueType> other) {
530         if (isTop != other.isTop)
531             return false;
532
533         if (isTop && other.isTop)
534             return true;
535
536         if (isBottom != other.isBottom)
537             return false;
538
539         if (isBottom && other.isBottom)
540             return true;
541
542         if (getNumSlots() != other.getNumSlots())
543             return false;
544
545         for (int i = 0; i < getNumSlots(); ++i)
546             if (!getValue(i).equals(other.getValue(i)))
547                 return false;
548
549         return true;
550     }
551
552     /**
553      * Make this Frame exactly the same as the one given as a parameter.
554      *
555      * @param other
556      * the Frame to make this object the same as
557      */

558     public void copyFrom(Frame<ValueType> other) {
559         lastUpdateTimestamp = other.lastUpdateTimestamp;
560         int size = slotList.size();
561         if (size == other.slotList.size()) {
562             for (int i = 0; i < size; i++)
563                 slotList.set(i, other.slotList.get(i));
564         } else {
565             slotList.clear();
566             for (ValueType v : other.slotList)
567                 slotList.add(v);
568         }
569         isTop = other.isTop;
570         isBottom = other.isBottom;
571     }
572
573     private static final boolean STACK_ONLY = SystemProperties
574             .getBoolean("dataflow.stackonly");
575
576     /**
577      * Convert to string.
578      */

579     @Override JavaDoc
580     public String JavaDoc toString() {
581         if (isTop())
582             return "[TOP]";
583         if (isBottom())
584             return "[BOTTOM]";
585         StringBuffer JavaDoc buf = new StringBuffer JavaDoc();
586         buf.append('[');
587         int numSlots = getNumSlots();
588         int start = STACK_ONLY ? getNumLocals() : 0;
589         for (int i = start; i < numSlots; ++i) {
590             if (!STACK_ONLY && i == getNumLocals()) {
591                 // Use a "|" character to visually separate locals from
592
// the operand stack.
593
int last = buf.length() - 1;
594                 if (last >= 0) {
595                     if (buf.charAt(last) == ',')
596                         buf.deleteCharAt(last);
597                 }
598                 buf.append('|');
599             }
600             String JavaDoc value = valueToString(getValue(i));
601             if (i == numSlots - 1 && value.endsWith(","))
602                 value = value.substring(0, value.length() - 1);
603             buf.append(value);
604             // buf.append(' ');
605
}
606         buf.append(']');
607         return buf.toString();
608     }
609
610     /**
611      * Subclasses may override this if they want to do something special to
612      * convert Value objects to Strings. By default, we just call toString() on
613      * the values.
614      */

615     protected String JavaDoc valueToString(ValueType value) {
616         return value.toString();
617     }
618
619     /**
620      * @return an unmodifiable Collection of the local variable and operand stack slots
621      */

622     public Collection JavaDoc<ValueType> allSlots() {
623         if (slotList == null)
624             return Collections.EMPTY_LIST;
625         return Collections.unmodifiableCollection(slotList);
626     }
627
628     /**
629      * @param lastUpdateTimestamp
630      * The lastUpdateTimestamp to set.
631      */

632     public void setLastUpdateTimestamp(int lastUpdateTimestamp) {
633         this.lastUpdateTimestamp = lastUpdateTimestamp;
634     }
635
636     /**
637      * @return Returns the lastUpdateTimestamp.
638      */

639     public int getLastUpdateTimestamp() {
640         return lastUpdateTimestamp;
641     }
642
643 }
644
645 // vim:ts=4
646
Popular Tags