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


1 /*
2  * Bytecode Analysis Framework
3  * Copyright (C) 2003-2005 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.BitSet ;
23 import java.util.Collection ;
24 import java.util.Iterator ;
25 import java.util.LinkedList ;
26 import java.util.NoSuchElementException ;
27
28 import org.apache.bcel.generic.ATHROW;
29 import org.apache.bcel.generic.InstructionHandle;
30 import org.apache.bcel.generic.MethodGen;
31
32 import edu.umd.cs.findbugs.graph.AbstractGraph;
33
34 /**
35  * Simple control flow graph abstraction for BCEL.
36  *
37  * @see BasicBlock
38  * @see Edge
39  */
40 public class CFG extends AbstractGraph<Edge, BasicBlock> implements Debug {
41
42     /* ----------------------------------------------------------------------
43      * Helper classes
44      * ---------------------------------------------------------------------- */
45
46     /**
47      * An Iterator over the Locations in the CFG.
48      * Because of JSR subroutines, the same instruction may actually
49      * be part of multiple basic blocks (with different facts
50      * true in each, due to calling context). Locations specify
51      * both the instruction and the basic block.
52      */
53     private class LocationIterator implements Iterator <Location> {
54         private Iterator <BasicBlock> blockIter;
55         private BasicBlock curBlock;
56         private Iterator <InstructionHandle> instructionIter;
57         private Location next;
58
59         private LocationIterator() {
60             this.blockIter = blockIterator();
61             findNext();
62         }
63
64         public boolean hasNext() {
65             findNext();
66             return next != null;
67         }
68
69         public Location next() {
70             findNext();
71             if (next == null) throw new NoSuchElementException ();
72             Location result = next;
73             next = null;
74             return result;
75         }
76
77         public void remove() {
78             throw new UnsupportedOperationException ();
79         }
80
81         private void findNext() {
82             while (next == null) {
83                 // Make sure we have an instruction iterator
84 if (instructionIter == null) {
85                     if (!blockIter.hasNext())
86                         return; // At end
87 curBlock = blockIter.next();
88                     instructionIter = curBlock.instructionIterator();
89                 }
90
91                 if (instructionIter.hasNext())
92                     next = new Location(instructionIter.next(), curBlock);
93                 else
94                     instructionIter = null; // Go to next block
95 }
96         }
97     }
98
99     /* ----------------------------------------------------------------------
100      * Fields
101      * ---------------------------------------------------------------------- */
102
103     private BasicBlock entry, exit;
104     private int flags;
105     private String methodName; // for informational purposes
106 private MethodGen methodGen;
107     /* ----------------------------------------------------------------------
108      * Public methods
109      * ---------------------------------------------------------------------- */
110
111     /**
112      * Constructor.
113      * Creates empty control flow graph (with just entry and exit nodes).
114      */
115     public CFG() {
116     }
117     
118     /**
119      * @param methodName The methodName to set.
120      */
121     public void setMethodName(String methodName) {
122         this.methodName = methodName;
123     }
124     
125     public void setMethodGen(MethodGen methodGen) {
126         this.methodGen = methodGen;
127     }
128     public MethodGen getMethodGen() {
129         return methodGen;
130     }
131     /**
132      * @return Returns the methodName.
133      */
134     public String getMethodName() {
135         return methodName;
136     }
137
138     void setFlags(int flags) {
139         this.flags = flags;
140     }
141
142     int getFlags() {
143         return flags;
144     }
145
146     boolean isFlagSet(int flag) {
147         return (flags & flag) != 0;
148     }
149
150     /**
151      * Get the entry node.
152      */
153     public BasicBlock getEntry() {
154         if (entry == null) {
155             entry = allocate();
156         }
157         return entry;
158     }
159
160     /**
161      * Get the exit node.
162      */
163     public BasicBlock getExit() {
164         if (exit == null) {
165             exit = allocate();
166         }
167         return exit;
168     }
169
170     /**
171      * Add a unique edge to the graph.
172      * There must be no other edge already in the CFG with
173      * the same source and destination blocks.
174      *
175      * @param source the source basic block
176      * @param dest the destination basic block
177      * @param type the type of edge; see constants in EdgeTypes interface
178      * @return the newly created Edge
179      * @throws IllegalStateException if there is already an edge in the CFG
180      * with the same source and destination block
181      */
182     public Edge createEdge(BasicBlock source, BasicBlock dest, int type) {
183         Edge edge = createEdge(source, dest);
184         edge.setType(type);
185         return edge;
186     }
187
188     /**
189      * Look up an Edge by its id.
190      *
191      * @param id the id of the edge to look up
192      * @return the Edge, or null if no matching Edge was found
193      */
194     public Edge lookupEdgeById(int id) {
195         Iterator <Edge> i = edgeIterator();
196         while (i.hasNext()) {
197             Edge edge = i.next();
198             if (edge.getId() == id)
199                 return edge;
200         }
201         return null;
202     }
203
204     /**
205      * Get an Iterator over the nodes (BasicBlocks) of the control flow graph.
206      */
207     public Iterator <BasicBlock> blockIterator() {
208         return vertexIterator();
209     }
210
211     /**
212      * Get an Iterator over the Locations in the control flow graph.
213      */
214     public Iterator <Location> locationIterator() {
215         return new LocationIterator();
216     }
217
218     /**
219      * Get Collection of basic blocks whose IDs are specified by
220      * given BitSet.
221      *
222      * @param idSet BitSet of block IDs
223      * @return a Collection containing the blocks whose IDs are given
224      */
225     public Collection <BasicBlock> getBlocks(BitSet idSet) {
226         LinkedList <BasicBlock> result = new LinkedList <BasicBlock>();
227         for (Iterator <BasicBlock> i = blockIterator(); i.hasNext();) {
228             BasicBlock block = i.next();
229             if (idSet.get(block.getId()))
230                 result.add(block);
231         }
232         return result;
233     }
234
235     /**
236      * Get a Collection of basic blocks which contain the bytecode
237      * instruction with given offset.
238      *
239      * @param offset the bytecode offset of an instruction
240      * @return Collection of BasicBlock objects which contain the instruction
241      * with that offset
242      */
243     public Collection <BasicBlock> getBlocksContainingInstructionWithOffset(int offset) {
244         LinkedList <BasicBlock> result = new LinkedList <BasicBlock>();
245         for (Iterator <BasicBlock> i = blockIterator(); i.hasNext(); ) {
246             BasicBlock block = i.next();
247             if (block.containsInstructionWithOffset(offset))
248                 result.add(block);
249         }
250         return result;
251     }
252     
253     /**
254      * Get a Collection of Locations which specify the instruction
255      * at given bytecode offset.
256      *
257      * @param offset the bytecode offset
258      * @return all Locations referring to the instruction at that offset
259      */
260     public Collection <Location> getLocationsContainingInstructionWithOffset(int offset) {
261         LinkedList <Location> result = new LinkedList <Location>();
262         for (Iterator <Location> i = locationIterator(); i.hasNext(); ) {
263             Location location = i.next();
264             if (location.getHandle().getPosition() == offset) {
265                 result.add(location);
266             }
267         }
268         return result;
269     }
270     
271     /**
272      * Get the first predecessor reachable from given edge type.
273      *
274      * @param target the target block
275      * @param edgeType the edge type leading from the predecessor
276      * @return the predecessor, or null if there is no incoming edge with
277      * the specified edge type
278      */
279     public BasicBlock getPredecessorWithEdgeType(BasicBlock target, int edgeType) {
280         Edge edge = getIncomingEdgeWithType(target, edgeType);
281         return edge != null ? edge.getSource() : null;
282     }
283
284     /**
285      * Get the first successor reachable from given edge type.
286      *
287      * @param source the source block
288      * @param edgeType the edge type leading to the successor
289      * @return the successor, or null if there is no outgoing edge with
290      * the specified edge type
291      */
292     public BasicBlock getSuccessorWithEdgeType(BasicBlock source, int edgeType) {
293         Edge edge = getOutgoingEdgeWithType(source, edgeType);
294         return edge != null ? edge.getTarget() : null;
295     }
296
297     /**
298      * Get the Location where exception(s) thrown on given exception edge
299      * are thrown.
300      *
301      * @param exceptionEdge the exception Edge
302      * @return Location where exception(s) are thrown from
303      */
304     public Location getExceptionThrowerLocation(Edge exceptionEdge) {
305         if (!exceptionEdge.isExceptionEdge())
306             throw new IllegalArgumentException ();
307
308         InstructionHandle handle = exceptionEdge.getSource().getExceptionThrower();
309         if (handle == null)
310             throw new IllegalStateException ();
311         
312         BasicBlock basicBlock = (handle.getInstruction() instanceof ATHROW)
313             ? exceptionEdge.getSource()
314             : getSuccessorWithEdgeType(exceptionEdge.getSource(), EdgeTypes.FALL_THROUGH_EDGE);
315         if (basicBlock == null)
316             throw new IllegalStateException ("No basic block for thrower " + handle);
317         
318         return new Location(handle, basicBlock);
319     }
320     
321     /**
322      * Get the first incoming edge in basic block with given type.
323      *
324      * @param basicBlock the basic block
325      * @param edgeType the edge type
326      * @return the Edge, or null if there is no edge with that edge type
327      */
328     public Edge getIncomingEdgeWithType(BasicBlock basicBlock, int edgeType) {
329         return getEdgeWithType(incomingEdgeIterator(basicBlock), edgeType);
330     }
331
332     /**
333      * Get the first outgoing edge in basic block with given type.
334      *
335      * @param basicBlock the basic block
336      * @param edgeType the edge type
337      * @return the Edge, or null if there is no edge with that edge type
338      */
339     public Edge getOutgoingEdgeWithType(BasicBlock basicBlock, int edgeType) {
340         return getEdgeWithType(outgoingEdgeIterator(basicBlock), edgeType);
341     }
342     
343     private Edge getEdgeWithType(Iterator <Edge> iter, int edgeType) {
344         while (iter.hasNext()) {
345             Edge edge = iter.next();
346             if (edge.getType() == edgeType)
347                 return edge;
348         }
349         return null;
350     }
351
352     /**
353      * Allocate a new BasicBlock. The block won't be connected to
354      * any node in the graph.
355      */
356     public BasicBlock allocate() {
357         BasicBlock b = new BasicBlock();
358         addVertex(b);
359         return b;
360     }
361
362     /**
363      * Get number of basic blocks.
364      * This is just here for compatibility with the old CFG
365      * method names.
366      */
367     public int getNumBasicBlocks() {
368         return getNumVertices();
369     }
370
371     /**
372      * Get the number of edge labels allocated.
373      * This is just here for compatibility with the old CFG
374      * method names.
375      */
376     public int getMaxEdgeId() {
377         return getNumEdgeLabels();
378     }
379
380     public void checkIntegrity() {
381         // Ensure that basic blocks have only consecutive instructions
382 for (Iterator <BasicBlock> i = blockIterator(); i.hasNext();) {
383             BasicBlock basicBlock = i.next();
384             InstructionHandle prev = null;
385             for (Iterator <InstructionHandle> j = basicBlock.instructionIterator(); j.hasNext();) {
386                 InstructionHandle handle = j.next();
387                 if (prev != null && prev.getNext() != handle)
388                     throw new IllegalStateException ("Non-consecutive instructions in block " + basicBlock.getId() +
389                             ": prev=" + prev + ", handle=" + handle);
390                 prev = handle;
391             }
392         }
393     }
394
395     @Override
396          protected Edge allocateEdge(BasicBlock source, BasicBlock target) {
397         return new Edge(source, target);
398     }
399 }
400
401 // vim:ts=4
402

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags