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.Collection;
024: import java.util.Iterator;
025: import java.util.LinkedList;
026: import java.util.List;
027: import java.util.NoSuchElementException;
028: import java.util.TreeSet;
029:
030: import org.apache.bcel.generic.ATHROW;
031: import org.apache.bcel.generic.InstructionHandle;
032: import org.apache.bcel.generic.MethodGen;
033:
034: import edu.umd.cs.findbugs.graph.AbstractGraph;
035: import edu.umd.cs.findbugs.util.NullIterator;
036:
037: /**
038: * Simple control flow graph abstraction for BCEL.
039: *
040: * @see BasicBlock
041: * @see Edge
042: */
043: public class CFG extends AbstractGraph<Edge, BasicBlock> implements
044: Debug {
045: /* ----------------------------------------------------------------------
046: * CFG flags
047: * ---------------------------------------------------------------------- */
048:
049: /** Flag set if infeasible exception edges have been pruned from the CFG. */
050: public static final int PRUNED_INFEASIBLE_EXCEPTIONS = 1;
051:
052: /** Flag set if normal return edges from calls to methods which unconditionally
053: * throw an exception have been removed. */
054: public static final int PRUNED_UNCONDITIONAL_THROWERS = 2;
055:
056: /** Flag set if CFG has been "refined"; i.e., to the extent possible,
057: * all infeasible edges have been removed. */
058: public static final int REFINED = 4;
059:
060: /** Flag set if CFG edges corresponding to failed assertions have been removed. */
061: public static final int PRUNED_FAILED_ASSERTION_EDGES = 8;
062:
063: /** Flag set if CFG is busy (in the process of being refined. */
064: public static final int BUSY = 16;
065:
066: /* ----------------------------------------------------------------------
067: * Helper classes
068: * ---------------------------------------------------------------------- */
069:
070: /**
071: * An Iterator over the Locations in the CFG.
072: * Because of JSR subroutines, the same instruction may actually
073: * be part of multiple basic blocks (with different facts
074: * true in each, due to calling context). Locations specify
075: * both the instruction and the basic block.
076: */
077: private class LocationIterator implements Iterator<Location> {
078: private Iterator<BasicBlock> blockIter;
079: private BasicBlock curBlock;
080: private Iterator<InstructionHandle> instructionIter;
081: private Location next;
082:
083: private LocationIterator() {
084: this .blockIter = blockIterator();
085: findNext();
086: }
087:
088: public boolean hasNext() {
089: findNext();
090: return next != null;
091: }
092:
093: public Location next() {
094: findNext();
095: if (next == null)
096: throw new NoSuchElementException();
097: Location result = next;
098: next = null;
099: return result;
100: }
101:
102: public void remove() {
103: throw new UnsupportedOperationException();
104: }
105:
106: private void findNext() {
107: while (next == null) {
108: // Make sure we have an instruction iterator
109: if (instructionIter == null) {
110: if (!blockIter.hasNext())
111: return; // At end
112: curBlock = blockIter.next();
113: instructionIter = curBlock.instructionIterator();
114: }
115:
116: if (instructionIter.hasNext())
117: next = new Location(instructionIter.next(),
118: curBlock);
119: else
120: instructionIter = null; // Go to next block
121: }
122: }
123: }
124:
125: /* ----------------------------------------------------------------------
126: * Fields
127: * ---------------------------------------------------------------------- */
128:
129: private BasicBlock entry, exit;
130: private int flags;
131: private String methodName; // for informational purposes
132: private MethodGen methodGen;
133: private List<Edge> removedEdgeList;
134:
135: /* ----------------------------------------------------------------------
136: * Public methods
137: * ---------------------------------------------------------------------- */
138:
139: /**
140: * Constructor.
141: * Creates empty control flow graph (with just entry and exit nodes).
142: */
143: public CFG() {
144: }
145:
146: /**
147: * @param methodName The methodName to set.
148: */
149: public void setMethodName(String methodName) {
150: this .methodName = methodName;
151: }
152:
153: public void setMethodGen(MethodGen methodGen) {
154: this .methodGen = methodGen;
155: }
156:
157: public MethodGen getMethodGen() {
158: return methodGen;
159: }
160:
161: /**
162: * @return Returns the methodName.
163: */
164: public String getMethodName() {
165: return methodName;
166: }
167:
168: public void setFlags(int flags) {
169: this .flags = flags;
170: }
171:
172: public void setFlag(int flags) {
173: this .flags |= flags;
174: }
175:
176: public void clearFlag(int flags) {
177: this .flags &= ~flags;
178: }
179:
180: public int getFlags() {
181: return flags;
182: }
183:
184: public boolean isFlagSet(int flag) {
185: return (flags & flag) != 0;
186: }
187:
188: /**
189: * Get the entry node.
190: */
191: public BasicBlock getEntry() {
192: if (entry == null) {
193: entry = allocate();
194: }
195: return entry;
196: }
197:
198: /**
199: * Get the exit node.
200: */
201: public BasicBlock getExit() {
202: if (exit == null) {
203: exit = allocate();
204: }
205: return exit;
206: }
207:
208: /**
209: * Add a unique edge to the graph.
210: * There must be no other edge already in the CFG with
211: * the same source and destination blocks.
212: *
213: * @param source the source basic block
214: * @param dest the destination basic block
215: * @param type the type of edge; see constants in EdgeTypes interface
216: * @return the newly created Edge
217: * @throws IllegalStateException if there is already an edge in the CFG
218: * with the same source and destination block
219: */
220: public Edge createEdge(BasicBlock source, BasicBlock dest, int type) {
221: Edge edge = createEdge(source, dest);
222: edge.setType(type);
223: return edge;
224: }
225:
226: /**
227: * Look up an Edge by its id.
228: *
229: * @param id the id of the edge to look up
230: * @return the Edge, or null if no matching Edge was found
231: */
232: public Edge lookupEdgeById(int id) {
233: Iterator<Edge> i = edgeIterator();
234: while (i.hasNext()) {
235: Edge edge = i.next();
236: if (edge.getId() == id)
237: return edge;
238: }
239: return null;
240: }
241:
242: /**
243: * Get an Iterator over the nodes (BasicBlocks) of the control flow graph.
244: */
245: public Iterator<BasicBlock> blockIterator() {
246: return vertexIterator();
247: }
248:
249: /**
250: * Get an Iterator over the Locations in the control flow graph.
251: */
252: public Iterator<Location> locationIterator() {
253: return new LocationIterator();
254: }
255:
256: /**
257: * Returns a collection of locations, ordered according to the compareTo ordering over locations.
258: * If you want to list all the locations in a CFG for debugging purposes, this is a good order to do so in.
259: *
260: * @return collection of locations
261: */
262: public Collection<Location> orderedLocations() {
263: TreeSet<Location> tree = new TreeSet<Location>();
264: for (Iterator<Location> locs = locationIterator(); locs
265: .hasNext();) {
266: Location loc = locs.next();
267: tree.add(loc);
268: }
269: return tree;
270: }
271:
272: /**
273: * Get Collection of basic blocks whose IDs are specified by
274: * given BitSet.
275: *
276: * @param labelSet BitSet of block labels
277: * @return a Collection containing the blocks whose IDs are given
278: */
279: public Collection<BasicBlock> getBlocks(BitSet labelSet) {
280: LinkedList<BasicBlock> result = new LinkedList<BasicBlock>();
281: for (Iterator<BasicBlock> i = blockIterator(); i.hasNext();) {
282: BasicBlock block = i.next();
283: if (labelSet.get(block.getLabel()))
284: result.add(block);
285: }
286: return result;
287: }
288:
289: /**
290: * Get a Collection of basic blocks which contain the bytecode
291: * instruction with given offset.
292: *
293: * @param offset the bytecode offset of an instruction
294: * @return Collection of BasicBlock objects which contain the instruction
295: * with that offset
296: */
297: public Collection<BasicBlock> getBlocksContainingInstructionWithOffset(
298: int offset) {
299: LinkedList<BasicBlock> result = new LinkedList<BasicBlock>();
300: for (Iterator<BasicBlock> i = blockIterator(); i.hasNext();) {
301: BasicBlock block = i.next();
302: if (block.containsInstructionWithOffset(offset))
303: result.add(block);
304: }
305: return result;
306: }
307:
308: /**
309: * Get a Collection of Locations which specify the instruction
310: * at given bytecode offset.
311: *
312: * @param offset the bytecode offset
313: * @return all Locations referring to the instruction at that offset
314: */
315: public Collection<Location> getLocationsContainingInstructionWithOffset(
316: int offset) {
317: LinkedList<Location> result = new LinkedList<Location>();
318: for (Iterator<Location> i = locationIterator(); i.hasNext();) {
319: Location location = i.next();
320: if (location.getHandle().getPosition() == offset) {
321: result.add(location);
322: }
323: }
324: return result;
325: }
326:
327: /**
328: * Get the first predecessor reachable from given edge type.
329: *
330: * @param target the target block
331: * @param edgeType the edge type leading from the predecessor
332: * @return the predecessor, or null if there is no incoming edge with
333: * the specified edge type
334: */
335: public BasicBlock getPredecessorWithEdgeType(BasicBlock target,
336: int edgeType) {
337: Edge edge = getIncomingEdgeWithType(target, edgeType);
338: return edge != null ? edge.getSource() : null;
339: }
340:
341: /**
342: * Get the first successor reachable from given edge type.
343: *
344: * @param source the source block
345: * @param edgeType the edge type leading to the successor
346: * @return the successor, or null if there is no outgoing edge with
347: * the specified edge type
348: */
349: public BasicBlock getSuccessorWithEdgeType(BasicBlock source,
350: int edgeType) {
351: Edge edge = getOutgoingEdgeWithType(source, edgeType);
352: return edge != null ? edge.getTarget() : null;
353: }
354:
355: /**
356: * Get the Location where exception(s) thrown on given exception edge
357: * are thrown.
358: *
359: * @param exceptionEdge the exception Edge
360: * @return Location where exception(s) are thrown from
361: */
362: public Location getExceptionThrowerLocation(Edge exceptionEdge) {
363: if (!exceptionEdge.isExceptionEdge())
364: throw new IllegalArgumentException();
365:
366: InstructionHandle handle = exceptionEdge.getSource()
367: .getExceptionThrower();
368: if (handle == null)
369: throw new IllegalStateException();
370:
371: BasicBlock basicBlock = (handle.getInstruction() instanceof ATHROW) ? exceptionEdge
372: .getSource()
373: : getSuccessorWithEdgeType(exceptionEdge.getSource(),
374: EdgeTypes.FALL_THROUGH_EDGE);
375:
376: if (basicBlock == null) {
377: if (removedEdgeList != null) {
378: // The fall-through edge might have been removed during
379: // CFG pruning. Look for it in the removed edge list.
380: for (Edge removedEdge : removedEdgeList) {
381: if (removedEdge.getType() == EdgeTypes.FALL_THROUGH_EDGE
382: && removedEdge.getSource() == exceptionEdge
383: .getSource()) {
384: basicBlock = removedEdge.getTarget();
385: break;
386: }
387: }
388: }
389: }
390:
391: if (basicBlock == null) {
392: throw new IllegalStateException(
393: "No basic block for thrower " + handle + " in "
394: + this .methodGen.getClassName() + "."
395: + this .methodName + " : "
396: + this .methodGen.getSignature());
397: }
398:
399: return new Location(handle, basicBlock);
400: }
401:
402: /**
403: * Get an Iterator over Edges removed from this CFG.
404: *
405: * @return Iterator over Edges removed from this CFG
406: */
407: public Iterator<Edge> removedEdgeIterator() {
408: return removedEdgeList != null ? removedEdgeList.iterator()
409: : new NullIterator<Edge>();
410: }
411:
412: /**
413: * Get the first incoming edge in basic block with given type.
414: *
415: * @param basicBlock the basic block
416: * @param edgeType the edge type
417: * @return the Edge, or null if there is no edge with that edge type
418: */
419: public Edge getIncomingEdgeWithType(BasicBlock basicBlock,
420: int edgeType) {
421: return getEdgeWithType(incomingEdgeIterator(basicBlock),
422: edgeType);
423: }
424:
425: /**
426: * Get the first outgoing edge in basic block with given type.
427: *
428: * @param basicBlock the basic block
429: * @param edgeType the edge type
430: * @return the Edge, or null if there is no edge with that edge type
431: */
432: public Edge getOutgoingEdgeWithType(BasicBlock basicBlock,
433: int edgeType) {
434: return getEdgeWithType(outgoingEdgeIterator(basicBlock),
435: edgeType);
436: }
437:
438: private Edge getEdgeWithType(Iterator<Edge> iter, int edgeType) {
439: while (iter.hasNext()) {
440: Edge edge = iter.next();
441: if (edge.getType() == edgeType)
442: return edge;
443: }
444: return null;
445: }
446:
447: /**
448: * Allocate a new BasicBlock. The block won't be connected to
449: * any node in the graph.
450: */
451: public BasicBlock allocate() {
452: BasicBlock b = new BasicBlock();
453: addVertex(b);
454: return b;
455: }
456:
457: /**
458: * Get number of basic blocks.
459: * This is just here for compatibility with the old CFG
460: * method names.
461: */
462: public int getNumBasicBlocks() {
463: return getNumVertices();
464: }
465:
466: /**
467: * Get the number of edge labels allocated.
468: * This is just here for compatibility with the old CFG
469: * method names.
470: */
471: public int getMaxEdgeId() {
472: return getNumEdgeLabels();
473: }
474:
475: public void checkIntegrity() {
476: // Ensure that basic blocks have only consecutive instructions
477: for (Iterator<BasicBlock> i = blockIterator(); i.hasNext();) {
478: BasicBlock basicBlock = i.next();
479: InstructionHandle prev = null;
480: for (Iterator<InstructionHandle> j = basicBlock
481: .instructionIterator(); j.hasNext();) {
482: InstructionHandle handle = j.next();
483: if (prev != null && prev.getNext() != handle)
484: throw new IllegalStateException(
485: "Non-consecutive instructions in block "
486: + basicBlock.getLabel() + ": prev="
487: + prev + ", handle=" + handle);
488: prev = handle;
489: }
490: }
491: }
492:
493: @Override
494: protected Edge allocateEdge(BasicBlock source, BasicBlock target) {
495: return new Edge(source, target);
496: }
497:
498: /* (non-Javadoc)
499: * @see edu.umd.cs.findbugs.graph.AbstractGraph#removeEdge(edu.umd.cs.findbugs.graph.AbstractEdge)
500: */
501: @Override
502: public void removeEdge(Edge edge) {
503: super .removeEdge(edge);
504:
505: // Keep track of removed edges.
506: if (removedEdgeList == null) {
507: removedEdgeList = new LinkedList<Edge>();
508: }
509: removedEdgeList.add(edge);
510: }
511:
512: /**
513: * Get number of non-exception control successors of given basic block.
514: *
515: * @param block a BasicBlock
516: * @return number of non-exception control successors of the basic block
517: */
518: public int getNumNonExceptionSucessors(BasicBlock block) {
519: int numNonExceptionSuccessors = block
520: .getNumNonExceptionSuccessors();
521: if (numNonExceptionSuccessors < 0) {
522: numNonExceptionSuccessors = 0;
523: for (Iterator<Edge> i = outgoingEdgeIterator(block); i
524: .hasNext();) {
525: Edge edge = i.next();
526: if (!edge.isExceptionEdge()) {
527: numNonExceptionSuccessors++;
528: }
529: }
530: block
531: .setNumNonExceptionSuccessors(numNonExceptionSuccessors);
532: }
533: return numNonExceptionSuccessors;
534: }
535:
536: /**
537: * Get the Location representing the entry to the CFG.
538: * Note that this is a "fake" Location, and shouldn't
539: * be relied on to yield source line information.
540: *
541: * @return Location at entry to CFG
542: */
543: public Location getLocationAtEntry() {
544: InstructionHandle handle = getEntry().getFirstInstruction();
545: assert handle != null;
546: return new Location(handle, getEntry());
547: }
548: }
549:
550: // vim:ts=4
|