001: /*
002: * Bytecode Analysis Framework
003: * Copyright (C) 2003-2007 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 java.util.BitSet;
023: import java.util.Iterator;
024: import java.util.NoSuchElementException;
025:
026: import org.apache.bcel.Constants;
027: import org.apache.bcel.generic.CodeExceptionGen;
028: import org.apache.bcel.generic.InstructionHandle;
029:
030: import edu.umd.cs.findbugs.SystemProperties;
031: import edu.umd.cs.findbugs.graph.AbstractVertex;
032:
033: /**
034: * Simple basic block abstraction for BCEL.
035: *
036: * @author David Hovemeyer
037: * @see CFG
038: */
039: public class BasicBlock extends AbstractVertex<Edge, BasicBlock>
040: implements Debug {
041:
042: /* ----------------------------------------------------------------------
043: * Static data
044: * ---------------------------------------------------------------------- */
045:
046: /**
047: * Set of instruction opcodes that have an implicit null check.
048: */
049: private static final BitSet nullCheckInstructionSet = new BitSet();
050:
051: static {
052: nullCheckInstructionSet.set(Constants.GETFIELD);
053: nullCheckInstructionSet.set(Constants.PUTFIELD);
054: nullCheckInstructionSet.set(Constants.INVOKESPECIAL);
055: nullCheckInstructionSet.set(Constants.INVOKEVIRTUAL);
056: nullCheckInstructionSet.set(Constants.INVOKEINTERFACE);
057: nullCheckInstructionSet.set(Constants.AALOAD);
058: nullCheckInstructionSet.set(Constants.AASTORE);
059: nullCheckInstructionSet.set(Constants.BALOAD);
060: nullCheckInstructionSet.set(Constants.BASTORE);
061: nullCheckInstructionSet.set(Constants.CALOAD);
062: nullCheckInstructionSet.set(Constants.CASTORE);
063: nullCheckInstructionSet.set(Constants.DALOAD);
064: nullCheckInstructionSet.set(Constants.DASTORE);
065: nullCheckInstructionSet.set(Constants.FALOAD);
066: nullCheckInstructionSet.set(Constants.FASTORE);
067: nullCheckInstructionSet.set(Constants.IALOAD);
068: nullCheckInstructionSet.set(Constants.IASTORE);
069: nullCheckInstructionSet.set(Constants.LALOAD);
070: nullCheckInstructionSet.set(Constants.LASTORE);
071: nullCheckInstructionSet.set(Constants.SALOAD);
072: nullCheckInstructionSet.set(Constants.SASTORE);
073: nullCheckInstructionSet.set(Constants.MONITORENTER);
074: nullCheckInstructionSet.set(Constants.ARRAYLENGTH);
075: //nullCheckInstructionSet.set(Constants.MONITOREXIT);
076: if (!SystemProperties.getBoolean("npe.noAthrow")) {
077: nullCheckInstructionSet.set(Constants.ATHROW);
078: }
079: // Any others?
080: }
081:
082: /* ----------------------------------------------------------------------
083: * Fields
084: * ---------------------------------------------------------------------- */
085:
086: private InstructionHandle firstInstruction;
087: private InstructionHandle lastInstruction;
088: private InstructionHandle exceptionThrower; // instruction for which this block is the ETB
089: private CodeExceptionGen exceptionGen; // set if this block is the entry point of an exception handler
090: private boolean inJSRSubroutine;
091: private int numNonExceptionSuccessors;
092:
093: /* ----------------------------------------------------------------------
094: * Public methods
095: * ---------------------------------------------------------------------- */
096:
097: /**
098: * Constructor.
099: */
100: public BasicBlock() {
101: this .firstInstruction = null;
102: this .lastInstruction = null;
103: this .exceptionThrower = null;
104: this .exceptionGen = null;
105: this .inJSRSubroutine = false;
106: this .numNonExceptionSuccessors = -1;
107: }
108:
109: public boolean isInJSRSubroutine() {
110: return inJSRSubroutine;
111: }
112:
113: void setInJSRSubroutine(boolean inJSRSubroutine) {
114: this .inJSRSubroutine = inJSRSubroutine;
115: }
116:
117: /**
118: * Get the basic block's integer label.
119: *
120: * @deprecated call getLabel() instead
121: * @return the BasicBlock's integer label
122: */
123: @Deprecated
124: public int getId() {
125: return getLabel();
126: }
127:
128: @Override
129: public String toString() {
130: return "block " + String.valueOf(getLabel());
131: }
132:
133: /**
134: * Set the instruction for which this block is the ETB.
135: *
136: * @param exceptionThrower the instruction
137: */
138: public void setExceptionThrower(InstructionHandle exceptionThrower) {
139: this .exceptionThrower = exceptionThrower;
140: }
141:
142: /**
143: * Return whether or not this block is an exception thrower.
144: */
145: public boolean isExceptionThrower() {
146: return exceptionThrower != null;
147: }
148:
149: /**
150: * Get the instruction for which this block is an exception thrower.
151: *
152: * @return the instruction, or null if this block is not an exception thrower
153: */
154: public InstructionHandle getExceptionThrower() {
155: return exceptionThrower;
156: }
157:
158: /**
159: * Return whether or not this block is a null check.
160: */
161: public boolean isNullCheck() {
162: // Null check blocks must be exception throwers,
163: // and are always empty. (The only kind of non-empty
164: // exception throwing block is one terminated by an ATHROW).
165: if (!isExceptionThrower() || getFirstInstruction() != null)
166: return false;
167: short opcode = exceptionThrower.getInstruction().getOpcode();
168: return nullCheckInstructionSet.get(opcode);
169: }
170:
171: /**
172: * Get the first instruction in the basic block.
173: */
174: public InstructionHandle getFirstInstruction() {
175: return firstInstruction;
176: }
177:
178: /**
179: * Get the last instruction in the basic block.
180: */
181: public InstructionHandle getLastInstruction() {
182: return lastInstruction;
183: }
184:
185: /**
186: * Get the successor of given instruction within the basic block.
187: * @param handle the instruction
188: * @return the instruction's successor, or null if the instruction
189: * is the last in the basic block
190: */
191: public InstructionHandle getSuccessorOf(InstructionHandle handle) {
192: if (VERIFY_INTEGRITY) {
193: if (!containsInstruction(handle))
194: throw new IllegalStateException();
195: }
196: return handle == lastInstruction ? null : handle.getNext();
197: }
198:
199: /**
200: * Get the predecessor of given instruction within the basic block.
201: * @param handle the instruction
202: * @return the instruction's predecessor, or null if the instruction
203: * is the first in the basic block
204: */
205: public InstructionHandle getPredecessorOf(InstructionHandle handle) {
206: if (VERIFY_INTEGRITY) {
207: if (!containsInstruction(handle))
208: throw new IllegalStateException();
209: }
210: return handle == firstInstruction ? null : handle.getPrev();
211: }
212:
213: /**
214: * Add an InstructionHandle to the basic block.
215: *
216: * @param handle the InstructionHandle
217: */
218: public void addInstruction(InstructionHandle handle) {
219: if (firstInstruction == null) {
220: firstInstruction = lastInstruction = handle;
221: } else {
222: if (VERIFY_INTEGRITY && handle != lastInstruction.getNext())
223: throw new IllegalStateException(
224: "Adding non-consecutive instruction");
225: lastInstruction = handle;
226: }
227: }
228:
229: /**
230: * A forward Iterator over the instructions of a basic block.
231: * The duplicate() method can be used to make an exact copy of
232: * this iterator. Calling next() on the duplicate will not affect
233: * the original, and vice versa.
234: */
235: public class InstructionIterator implements
236: Iterator<InstructionHandle> {
237: private InstructionHandle next, last;
238:
239: public InstructionIterator(InstructionHandle first,
240: InstructionHandle last) {
241: this .next = first;
242: this .last = last;
243: }
244:
245: public boolean hasNext() {
246: return next != null;
247: }
248:
249: public InstructionHandle next() {
250: if (!hasNext())
251: throw new NoSuchElementException();
252: InstructionHandle result = next;
253: next = (result == last) ? null : next.getNext();
254: return result;
255: }
256:
257: public void remove() {
258: throw new UnsupportedOperationException();
259: }
260:
261: public InstructionIterator duplicate() {
262: return new InstructionIterator(next, last);
263: }
264:
265: @Override
266: public boolean equals(Object o) {
267: if (!(o instanceof InstructionIterator))
268: return false;
269: InstructionIterator other = (InstructionIterator) o;
270: return this .next == other.next && this .last == other.last;
271: }
272:
273: @Override
274: public int hashCode() {
275: int code = getBasicBlock().hashCode() * 227;
276: if (next != null)
277: code += next.getPosition() + 1;
278: return code;
279: }
280:
281: private BasicBlock getBasicBlock() {
282: return BasicBlock.this ;
283: }
284:
285: @Override
286: public String toString() {
287: StringBuffer buf = new StringBuffer();
288: buf.append("[basicBlock=");
289: buf.append(getBasicBlock().getLabel());
290: buf.append(", index=");
291: buf.append(next == null ? "end" : String.valueOf(next
292: .getPosition()));
293: buf.append(']');
294: return buf.toString();
295: }
296: }
297:
298: /**
299: * Get an Iterator over the instructions in the basic block.
300: */
301: public InstructionIterator instructionIterator() {
302: return new InstructionIterator(firstInstruction,
303: lastInstruction);
304: }
305:
306: /**
307: * A reverse Iterator over the instructions in a basic block.
308: */
309: private static class InstructionReverseIterator implements
310: Iterator<InstructionHandle> {
311: private InstructionHandle next, first;
312:
313: public InstructionReverseIterator(InstructionHandle last,
314: InstructionHandle first) {
315: this .next = last;
316: this .first = first;
317: }
318:
319: public boolean hasNext() {
320: return next != null;
321: }
322:
323: public InstructionHandle next() throws NoSuchElementException {
324: if (!hasNext())
325: throw new NoSuchElementException();
326: InstructionHandle result = next;
327: next = (result == first) ? null : next.getPrev();
328: return result;
329: }
330:
331: public void remove() {
332: throw new UnsupportedOperationException();
333: }
334: }
335:
336: /**
337: * Get an Iterator over the instructions in the basic block in reverse order.
338: * This is useful for backwards dataflow analyses.
339: */
340: public Iterator<InstructionHandle> instructionReverseIterator() {
341: return new InstructionReverseIterator(lastInstruction,
342: firstInstruction);
343: }
344:
345: /**
346: * Return true if there are no Instructions in this basic block.
347: */
348: public boolean isEmpty() {
349: return firstInstruction == null;
350: }
351:
352: public int pos() {
353:
354: if (isEmpty())
355: return getExceptionThrower().getPosition();
356: return firstInstruction.getPosition();
357: }
358:
359: /**
360: * Is this block an exception handler?
361: */
362: public boolean isExceptionHandler() {
363: return exceptionGen != null;
364: }
365:
366: /**
367: * Get CodeExceptionGen object; returns null if this basic block is
368: * not the entry point of an exception handler.
369: *
370: * @return the CodeExceptionGen object, or null
371: */
372: public CodeExceptionGen getExceptionGen() {
373: return exceptionGen;
374: }
375:
376: /**
377: * Set the CodeExceptionGen object. Marks this basic block as
378: * the entry point of an exception handler.
379: *
380: * @param exceptionGen the CodeExceptionGen object for the block
381: */
382: public void setExceptionGen(CodeExceptionGen exceptionGen) {
383: this .exceptionGen = exceptionGen;
384: }
385:
386: /**
387: * Return whether or not the basic block contains the given instruction.
388: *
389: * @param handle the instruction
390: * @return true if the block contains the instruction, false otherwise
391: */
392: public boolean containsInstruction(InstructionHandle handle) {
393: Iterator<InstructionHandle> i = instructionIterator();
394: while (i.hasNext()) {
395: if (i.next() == handle)
396: return true;
397: }
398: return false;
399: }
400:
401: /**
402: * Return whether or not the basic block contains the instruction
403: * with the given bytecode offset.
404: *
405: * @param offset the bytecode offset
406: * @return true if the block contains an instruction with the given offset,
407: * false if it does not
408: */
409: public boolean containsInstructionWithOffset(int offset) {
410: Iterator<InstructionHandle> i = instructionIterator();
411: while (i.hasNext()) {
412: if (i.next().getPosition() == offset)
413: return true;
414: }
415: return false;
416: }
417:
418: /**
419: * @return Returns the numNonExceptionSuccessors.
420: */
421: int getNumNonExceptionSuccessors() {
422: return numNonExceptionSuccessors;
423: }
424:
425: /**
426: * @param numNonExceptionSuccessors The numNonExceptionSuccessors to set.
427: */
428: void setNumNonExceptionSuccessors(int numNonExceptionSuccessors) {
429: this .numNonExceptionSuccessors = numNonExceptionSuccessors;
430: }
431: }
432:
433: //vim:ts=4
|