001: /*
002: * Bytecode Analysis Framework
003: * Copyright (C) 2003,2004 University of Maryland
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019:
020: package edu.umd.cs.findbugs.ba;
021:
022: import static edu.umd.cs.findbugs.ba.Debug.VERIFY_INTEGRITY;
023:
024: import java.util.ArrayList;
025: import java.util.BitSet;
026: import java.util.Collection;
027: import java.util.Collections;
028:
029: import org.apache.bcel.Constants;
030: import org.apache.bcel.generic.ConstantPoolGen;
031: import org.apache.bcel.generic.Instruction;
032: import org.apache.bcel.generic.InvokeInstruction;
033: import org.apache.bcel.generic.StackConsumer;
034:
035: import edu.umd.cs.findbugs.SystemProperties;
036:
037: /**
038: * Generic class for representing a Java stack frame as a dataflow value. A
039: * frame consists of "slots", which represent the local variables and values on
040: * the Java operand stack. Slots 0 .. <code>getNumLocals() - 1</code>
041: * represent the local variables. Slots <code>getNumLocals()</code> ..
042: * <code>getNumSlots() - 1</code> represent the Java operand stack. <p/>
043: * <p>
044: * Frame is parametized by "ValueType", which is the type of value to be stored
045: * in the Frame's slots. This type must form a lattice, according to the
046: * abstract mergeValues() operation in the corresponding analysis class (which
047: * should be derived from FrameDataflowAnalysis). When a Frame is constructed,
048: * all of its slots will contain null. The analysis is responsible for
049: * initializing created Frames with default values at the appropriate time.
050: * Typically, only initEntryFact() will need to do this. <p/>
051: * <p>
052: * A Frame may have the special "TOP" value. Such frames serve as the identity
053: * element for the meet operation operation. <p/>
054: * <p>
055: * A Frame may have the special "BOTTOM" value. The result of merging any frame
056: * with BOTTOM is BOTTOM.
057: *
058: * @author David Hovemeyer
059: * @see FrameDataflowAnalysis
060: */
061: public abstract class Frame<ValueType> {
062:
063: // //////////////////////////////////////////////////////////////////////////////////
064: // Instance variables
065: // //////////////////////////////////////////////////////////////////////////////////
066:
067: private int lastUpdateTimestamp;
068:
069: /**
070: * Number of local variables in the method.
071: */
072: private int numLocals;
073:
074: /**
075: * Array storing the values of local variables and operand stack slots.
076: */
077: private ArrayList<ValueType> slotList;
078:
079: /**
080: * Flag marking this frame as a special "TOP" value. Such Frames serve as
081: * the identity element when merging.
082: */
083: private boolean isTop;
084:
085: /**
086: * Flag marking this frame as a special "BOTTOM" value. Such Frames arise
087: * when merging two frames of different size.
088: */
089: private boolean isBottom;
090:
091: /**
092: * Default number of stack slots to preallocate space for.
093: */
094: private static final int DEFAULT_STACK_CAPACITY = 10;
095:
096: // //////////////////////////////////////////////////////////////////////////////////
097: // Methods
098: // //////////////////////////////////////////////////////////////////////////////////
099:
100: /**
101: * Constructor. This version of the constructor is for subclasses for which
102: * it is always safe to call getDefaultValue(), even when the object is not
103: * fully initialized.
104: *
105: * @param numLocals
106: * number of local variable slots in the method
107: */
108: public Frame(int numLocals) {
109: this .numLocals = numLocals;
110: this .slotList = new ArrayList<ValueType>(numLocals
111: + DEFAULT_STACK_CAPACITY);
112: for (int i = 0; i < numLocals; ++i)
113: slotList.add(null);
114: }
115:
116: /**
117: * Return whether or not this object the special "TOP" value for Frames.
118: * Such Frames are the identity element of the meet operation.
119: */
120: public boolean isTop() {
121: return isTop;
122: }
123:
124: /**
125: * Make this frame the special "TOP" value. Such Frames are the identity
126: * element of the meet operation.
127: */
128: public void setTop() {
129: isTop = true;
130: isBottom = false;
131: lastUpdateTimestamp = 0;
132: }
133:
134: /**
135: * Return whether or not this object is the special "BOTTOM" value for
136: * Frames. Such Frames arise when merging two frames of different size.
137: */
138: public boolean isBottom() {
139: return isBottom;
140: }
141:
142: /**
143: * Make this Frame the special "BOTTOM" value. Such Frames arise when
144: * merging two frames of different size.
145: */
146: public void setBottom() {
147: isBottom = true;
148: isTop = false;
149: }
150:
151: /**
152: * Set the Frame to be valid (neither TOP nor BOTTOM).
153: */
154: public void setValid() {
155: isTop = isBottom = false;
156: }
157:
158: /**
159: * Is the frame valid (meaning it is not TOP or BOTTOM)?
160: */
161: public boolean isValid() {
162: return !isTop() && !isBottom();
163: }
164:
165: /**
166: * Push a value onto the Java operand stack.
167: *
168: * @param value
169: * the ValueType to push
170: */
171: public void pushValue(ValueType value) {
172: if (VERIFY_INTEGRITY && value == null)
173: throw new IllegalArgumentException();
174: if (!isValid())
175: throw new IllegalStateException(
176: "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(
190: "accessing top or bottom frame");
191: if (slotList.size() == numLocals)
192: throw new DataflowAnalysisException("operand stack empty");
193: return slotList.remove(slotList.size() - 1);
194: }
195:
196: /**
197: * Get the value on the top of the Java operand stack.
198: *
199: * @throws DataflowAnalysisException
200: * if the Java operand stack is empty
201: */
202: public ValueType getTopValue() throws DataflowAnalysisException {
203: if (!isValid())
204: throw new DataflowAnalysisException(
205: "accessing top or bottom frame");
206: assert slotList.size() >= numLocals;
207: if (slotList.size() == numLocals)
208: throw new DataflowAnalysisException(
209: "operand stack is empty");
210: return slotList.get(slotList.size() - 1);
211: }
212:
213: /**
214: * Get the values on the top of the Java operand stack. The top stack item
215: * is placed at the end of the array, so that to restore the values to the
216: * stack, you would push them in the order they appear in the array.
217: */
218: public void getTopStackWords(ValueType[] valueList)
219: throws DataflowAnalysisException {
220: int stackDepth = getStackDepth();
221: if (valueList.length > stackDepth)
222: throw new DataflowAnalysisException(
223: "not enough values on stack");
224: int numSlots = slotList.size();
225: for (int i = numSlots - valueList.length, j = 0; i < numSlots; ++i, ++j) {
226: valueList[j] = slotList.get(i);
227: }
228: }
229:
230: /**
231: * Get a value on the operand stack.
232: *
233: * @param loc
234: * the stack location, counting downwards from the top (location
235: * 0)
236: */
237: public ValueType getStackValue(int loc)
238: throws DataflowAnalysisException {
239: if (!isValid())
240: throw new DataflowAnalysisException(
241: "Accessing TOP or BOTTOM frame!");
242: int stackDepth = getStackDepth();
243: if (loc >= stackDepth)
244: throw new DataflowAnalysisException(
245: "not enough values on stack: access=" + loc
246: + ", avail=" + stackDepth);
247: return slotList.get(slotList.size() - (loc + 1));
248: }
249:
250: /**
251: * Get a the location in the frame of a value on the operand stack.
252: *
253: * @param loc
254: * the stack location, counting downwards from the top (location
255: * 0)
256: */
257: public int getStackLocation(int loc)
258: throws DataflowAnalysisException {
259: int stackDepth = getStackDepth();
260: if (loc >= stackDepth)
261: throw new DataflowAnalysisException(
262: "not enough values on stack: access=" + loc
263: + ", avail=" + stackDepth);
264: return slotList.size() - (loc + 1);
265: }
266:
267: /**
268: * Get the value corresponding to the object instance used in the given
269: * instruction. This relies on the observation that in instructions which
270: * use an object instance (such as getfield, invokevirtual, etc.), the
271: * object instance is the first operand used by the instruction.
272: *
273: * @param ins
274: * the instruction
275: * @param cpg
276: * the ConstantPoolGen for the method
277: */
278: public ValueType getInstance(Instruction ins, ConstantPoolGen cpg)
279: throws DataflowAnalysisException {
280: return getStackValue(getInstanceStackLocation(ins, cpg));
281: }
282:
283: /**
284: * Get the stack location (counting down from top of stack, starting at 0)
285: * containing the object instance referred to by given instruction. This
286: * relies on the observation that in instructions which use an object
287: * instance (such as getfield, invokevirtual, etc.), the object instance is
288: * the first operand used by the instruction.
289: *
290: * <p>
291: * The value returned may be passed to getStackValue(int).
292: * </p>
293: *
294: * @param ins
295: * the Instruction
296: * @param cpg
297: * the ConstantPoolGen for the method
298: * @return stack location (counting down from top of stack, starting at 0)
299: * containing the object instance
300: * @throws DataflowAnalysisException
301: */
302: public int getInstanceStackLocation(Instruction ins,
303: ConstantPoolGen cpg) throws DataflowAnalysisException {
304: int numConsumed = ins.consumeStack(cpg);
305: if (numConsumed == Constants.UNPREDICTABLE)
306: throw new DataflowAnalysisException(
307: "Unpredictable stack consumption in " + ins);
308: return numConsumed - 1;
309: }
310:
311: /**
312: * Get the slot the object instance referred to by given instruction is
313: * located in.
314: *
315: * @param ins
316: * the Instruction
317: * @param cpg
318: * the ConstantPoolGen for the method
319: * @return stack slot the object instance is in
320: * @throws DataflowAnalysisException
321: */
322: public int getInstanceSlot(Instruction ins, ConstantPoolGen cpg)
323: throws DataflowAnalysisException {
324: if (!isValid()) {
325: throw new DataflowAnalysisException(
326: "Accessing invalid frame at " + ins);
327: }
328: int numConsumed = ins.consumeStack(cpg);
329: if (numConsumed == Constants.UNPREDICTABLE)
330: throw new DataflowAnalysisException(
331: "Unpredictable stack consumption in " + ins);
332: if (numConsumed > getStackDepth())
333: throw new DataflowAnalysisException("Stack underflow "
334: + ins);
335: return getNumSlots() - numConsumed;
336: }
337:
338: /**
339: * Get the number of arguments passed to given method invocation.
340: *
341: * @param ins
342: * the method invocation instruction
343: * @param cpg
344: * the ConstantPoolGen for the class containing the method
345: * @return number of arguments; note that this excludes the object instance
346: * for instance methods
347: * @throws DataflowAnalysisException
348: */
349: public int getNumArguments(InvokeInstruction ins,
350: ConstantPoolGen cpg) throws DataflowAnalysisException {
351: SignatureParser parser = new SignatureParser(ins
352: .getSignature(cpg));
353: return parser.getNumParameters();
354: }
355:
356: /**
357: * Get the number of arguments passed to given method invocation, including
358: * the object instance if the call is to an instance method.
359: *
360: * @param ins
361: * the method invocation instruction
362: * @param cpg
363: * the ConstantPoolGen for the class containing the method
364: * @return number of arguments, including object instance if appropriate
365: * @throws DataflowAnalysisException
366: */
367: public int getNumArgumentsIncludingObjectInstance(
368: InvokeInstruction ins, ConstantPoolGen cpg)
369: throws DataflowAnalysisException {
370: int numConsumed = ins.consumeStack(cpg);
371: if (numConsumed == Constants.UNPREDICTABLE)
372: throw new DataflowAnalysisException(
373: "Unpredictable stack consumption in " + ins);
374: return numConsumed;
375: }
376:
377: /**
378: * Get the <i>i</i>th argument passed to given method invocation.
379: *
380: * @param ins
381: * the method invocation instruction
382: * @param cpg
383: * the ConstantPoolGen for the class containing the method
384: * @param i
385: * index of the argument; 0 for the first argument, etc.
386: * @param numArguments
387: * total number of arguments to the method
388: * @return the <i>i</i>th argument
389: * @throws DataflowAnalysisException
390: */
391: @Deprecated
392: public ValueType getArgument(InvokeInstruction ins,
393: ConstantPoolGen cpg, int i, int numArguments)
394: throws DataflowAnalysisException {
395: SignatureParser sigParser = new SignatureParser(ins
396: .getSignature(cpg));
397: return getArgument(ins, cpg, i, sigParser);
398: }
399:
400: /**
401: * Get the <i>i</i>th argument passed to given method invocation.
402: *
403: * @param ins
404: * the method invocation instruction
405: * @param cpg
406: * the ConstantPoolGen for the class containing the method
407: * @param i
408: * index of the argument; 0 for the first argument, etc.
409: * @return the <i>i</i>th argument
410: * @throws DataflowAnalysisException
411: */
412: public ValueType getArgument(InvokeInstruction ins,
413: ConstantPoolGen cpg, int i, SignatureParser sigParser)
414: throws DataflowAnalysisException {
415: if (i >= sigParser.getNumParameters())
416: throw new IllegalArgumentException(
417: "requesting parameter # " + i + " of " + sigParser);
418: return getStackValue(sigParser
419: .getSlotsFromTopOfStackForParameter(i));
420: }
421:
422: /**
423: * Get the stack slot that will contain given method argument. Assumes that
424: * this frame is at the location (just before) a method invocation
425: * instruction.
426: *
427: * @param i
428: * the argument index: 0 for first arg, etc.
429: * @param numArguments
430: * total number of arguments to the called method
431: * @return slot containing the argument value
432: */
433: public int getArgumentSlot(int i, int numArguments) {
434: if (i >= numArguments)
435: throw new IllegalArgumentException();
436:
437: return (slotList.size() - numArguments) + i;
438: }
439:
440: /**
441: * Get the <i>i</i>th operand used by given instruction.
442: *
443: * @param ins
444: * the instruction, which must be a StackConsumer
445: * @param cpg
446: * the ConstantPoolGen
447: * @param i
448: * index of operand to get: 0 for the first operand, etc.
449: * @return the <i>i</i>th operand used by the given instruction
450: * @throws DataflowAnalysisException
451: */
452: public ValueType getOperand(StackConsumer ins, ConstantPoolGen cpg,
453: int i) throws DataflowAnalysisException {
454: int numOperands = ins.consumeStack(cpg);
455: if (numOperands == Constants.UNPREDICTABLE)
456: throw new DataflowAnalysisException(
457: "Unpredictable stack consumption in " + ins);
458: return getStackValue((numOperands - 1) - i);
459: }
460:
461: /**
462: * Get set of arguments passed to a method invocation which match given
463: * predicate.
464: *
465: * @param invokeInstruction
466: * the InvokeInstruction
467: * @param cpg
468: * the ConstantPoolGen
469: * @param chooser
470: * predicate to choose which argument values should be in the
471: * returned set
472: * @return BitSet specifying which arguments match the predicate, indexed by
473: * argument number (starting from 0)
474: * @throws DataflowAnalysisException
475: */
476: public BitSet getArgumentSet(InvokeInstruction invokeInstruction,
477: ConstantPoolGen cpg, DataflowValueChooser<ValueType> chooser)
478: throws DataflowAnalysisException {
479: BitSet chosenArgSet = new BitSet();
480: SignatureParser sigParser = new SignatureParser(
481: invokeInstruction.getSignature(cpg));
482:
483: for (int i = 0; i < sigParser.getNumParameters(); ++i) {
484: ValueType value = getArgument(invokeInstruction, cpg, i,
485: sigParser);
486: if (chooser.choose(value))
487: chosenArgSet.set(i);
488: }
489:
490: return chosenArgSet;
491: }
492:
493: /**
494: * Clear the Java operand stack. Only local variable slots will remain in
495: * the frame.
496: */
497: public void clearStack() {
498: if (!isValid())
499: throw new IllegalStateException(
500: "accessing top or bottom frame");
501: assert slotList.size() >= numLocals;
502: if (slotList.size() > numLocals)
503: slotList.subList(numLocals, slotList.size()).clear();
504: }
505:
506: /**
507: * Get the depth of the Java operand stack.
508: */
509: public int getStackDepth() {
510: return slotList.size() - numLocals;
511: }
512:
513: /**
514: * Get the number of locals.
515: */
516: public int getNumLocals() {
517: return numLocals;
518: }
519:
520: /**
521: * Get the number of slots (locals plus stack values).
522: */
523: public int getNumSlots() {
524: return slotList.size();
525: }
526:
527: /**
528: * Get the value at the <i>n</i>th slot.
529: *
530: * @param n
531: * the slot to get the value of
532: * @return the value in the slot
533: */
534: public ValueType getValue(int n) {
535: if (!isValid())
536: throw new IllegalStateException(
537: "accessing top or bottom frame");
538: return slotList.get(n);
539: }
540:
541: /**
542: * Set the value at the <i>n</i>th slot.
543: *
544: * @param n
545: * the slot in which to set a new value
546: * @param value
547: * the value to set
548: */
549: public void setValue(int n, ValueType value) {
550: if (VERIFY_INTEGRITY && value == null)
551: throw new IllegalArgumentException();
552: if (!isValid())
553: throw new IllegalStateException(
554: "accessing top or bottom frame");
555: slotList.set(n, value);
556: }
557:
558: /**
559: * Return true if this stack frame is the same as the one given as a
560: * parameter.
561: *
562: * @param other
563: * the other Frame
564: * @return true if the frames are the same, false otherwise
565: */
566: public boolean sameAs(Frame<ValueType> other) {
567: if (isTop != other.isTop)
568: return false;
569:
570: if (isTop && other.isTop)
571: return true;
572:
573: if (isBottom != other.isBottom)
574: return false;
575:
576: if (isBottom && other.isBottom)
577: return true;
578:
579: if (getNumSlots() != other.getNumSlots())
580: return false;
581:
582: for (int i = 0; i < getNumSlots(); ++i)
583: if (!getValue(i).equals(other.getValue(i)))
584: return false;
585:
586: return true;
587: }
588:
589: /**
590: * Make this Frame exactly the same as the one given as a parameter.
591: *
592: * @param other
593: * the Frame to make this object the same as
594: */
595: public void copyFrom(Frame<ValueType> other) {
596: lastUpdateTimestamp = other.lastUpdateTimestamp;
597: int size = slotList.size();
598: if (size == other.slotList.size()) {
599: for (int i = 0; i < size; i++)
600: slotList.set(i, other.slotList.get(i));
601: } else {
602: slotList.clear();
603: for (ValueType v : other.slotList)
604: slotList.add(v);
605: }
606: isTop = other.isTop;
607: isBottom = other.isBottom;
608: }
609:
610: private static final boolean STACK_ONLY = SystemProperties
611: .getBoolean("dataflow.stackonly");
612:
613: /**
614: * Convert to string.
615: */
616: @Override
617: public String toString() {
618: if (isTop())
619: return "[TOP]";
620: if (isBottom())
621: return "[BOTTOM]";
622: StringBuffer buf = new StringBuffer();
623: buf.append('[');
624: int numSlots = getNumSlots();
625: int start = STACK_ONLY ? getNumLocals() : 0;
626: for (int i = start; i < numSlots; ++i) {
627: if (!STACK_ONLY && i == getNumLocals()) {
628: // Use a "|" character to visually separate locals from
629: // the operand stack.
630: int last = buf.length() - 1;
631: if (last >= 0) {
632: if (buf.charAt(last) == ',')
633: buf.deleteCharAt(last);
634: }
635: buf.append('|');
636: }
637: String value = valueToString(getValue(i));
638: if (i == numSlots - 1 && value.endsWith(","))
639: value = value.substring(0, value.length() - 1);
640: buf.append(value);
641: // buf.append(' ');
642: }
643: buf.append(']');
644: return buf.toString();
645: }
646:
647: /**
648: * Subclasses may override this if they want to do something special to
649: * convert Value objects to Strings. By default, we just call toString() on
650: * the values.
651: */
652: protected String valueToString(ValueType value) {
653: if (value == null)
654: return "null";
655: return value.toString();
656: }
657:
658: /**
659: * @return an unmodifiable Collection of the local variable and operand stack slots
660: */
661: public Collection<ValueType> allSlots() {
662: if (slotList == null)
663: return Collections.EMPTY_LIST;
664: return Collections.unmodifiableCollection(slotList);
665: }
666:
667: /**
668: * @param lastUpdateTimestamp
669: * The lastUpdateTimestamp to set.
670: */
671: public void setLastUpdateTimestamp(int lastUpdateTimestamp) {
672: this .lastUpdateTimestamp = lastUpdateTimestamp;
673: }
674:
675: /**
676: * @return Returns the lastUpdateTimestamp.
677: */
678: public int getLastUpdateTimestamp() {
679: return lastUpdateTimestamp;
680: }
681:
682: }
683:
684: // vim:ts=4
|