Java > Open Source Codes > soot > util > cfgcmd > CFGToDotGraph


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 John Jorgensen
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 package soot.util.cfgcmd;
21
22 import java.util.*;
23
24 import soot.*;
25 import soot.toolkits.exceptions.ThrowableSet;
26 import soot.toolkits.graph.DirectedGraph;
27 import soot.toolkits.graph.BlockGraph;
28 import soot.toolkits.graph.ExceptionalGraph;
29 import soot.toolkits.graph.Block;
30 import soot.toolkits.graph.UnitGraph;
31 import soot.util.dot.DotGraph;
32 import soot.util.dot.DotGraphAttribute;
33 import soot.util.dot.DotGraphConstants;
34 import soot.util.dot.DotGraphEdge;
35 import soot.util.dot.DotGraphNode;
36
37
38 /**
39  * Class that creates a {@link DotGraph} visualization
40  * of a control flow graph.
41  */
42 public class CFGToDotGraph {
43
44   private boolean onePage; // in one or several 8.5x11 pages.
45 private boolean isBrief;
46   private boolean showExceptions;
47   private DotGraphAttribute unexceptionalControlFlowAttr;
48   private DotGraphAttribute exceptionalControlFlowAttr;
49   private DotGraphAttribute exceptionEdgeAttr;
50   private DotGraphAttribute headAttr;
51   private DotGraphAttribute tailAttr;
52     
53   /**
54    * <p>Returns a CFGToDotGraph converter which will draw the graph
55    * as a single arbitrarily-sized page, with full-length node labels.</p>
56    *
57    * <p> If asked to draw a <code>ExceptionalGraph</code>, the
58    * converter will identify the exceptions that will be thrown. By
59    * default, it will distinguish different edges by coloring regular
60    * control flow edges black, exceptional control flow edges red, and
61    * thrown exception edges light gray. Head and tail nodes are filled
62    * in, head nodes with gray, and tail nodes with light gray.</p>
63    */
64   public CFGToDotGraph() {
65     setOnePage(true);
66     setBriefLabels(false);
67     setShowExceptions(true);
68     setUnexceptionalControlFlowAttr("color", "black");
69     setExceptionalControlFlowAttr("color", "red");
70     setExceptionEdgeAttr("color", "lightgray");
71     setHeadAttr("fillcolor", "gray");
72     setTailAttr("fillcolor", "lightgray");
73   }
74
75
76   /**
77    * Specify whether to split the graph into pages.
78    *
79    * @param onePage indicates whether to produce the graph as a
80    * single, arbitrarily-sized page (if <code>onePage</code> is
81    * <code>true</code>) or several 8.5x11-inch pages (if
82    * <code>onePage</code> is <code>false</code>).
83    */
84   public void setOnePage(boolean onePage) {
85     this.onePage = onePage;
86   }
87
88
89   /**
90    * Specify whether to abbreviate the text in node labels. This is most
91    * relevant when the nodes represent basic blocks: abbreviated
92    * node labels contain only a numeric label for the block, while
93    * unabbreviated labels contain the code of its instructions.
94    *
95    * @param useBrief indicates whether to abbreviate the text of
96    * node labels.
97    */
98   public void setBriefLabels(boolean useBrief) {
99     this.isBrief = useBrief;
100   }
101
102
103   /**
104    * Specify whether the graph should depict the exceptions which
105    * each node may throw, in the form of an edge from the throwing
106    * node to the handler (if any), labeled with the possible
107    * exception types. This parameter has an effect only when
108    * drawing <code>ExceptionalGraph</code>s.
109    *
110    * @param showExceptions indicates whether to show possible exceptions
111    * and their handlers.
112    */
113   public void setShowExceptions(boolean showExceptions) {
114     this.showExceptions = showExceptions;
115   }
116
117
118   /**
119    * Specify the dot graph attribute to use for regular control flow
120    * edges. This parameter has an effect only when
121    * drawing <code>ExceptionalGraph</code>s.
122    *
123    * @param id The attribute name, for example "style" or "color".
124    *
125    * @param value The attribute value, for example "solid" or "black".
126    *
127    * @see <a HREF="http://www.research.att.com/sw/tools/graphviz/dotguide.pdf">"Drawing graphs with dot"</a>
128    */
129   public void setUnexceptionalControlFlowAttr(String id, String value) {
130     unexceptionalControlFlowAttr = new DotGraphAttribute(id, value);
131   }
132
133
134   /**
135    * Specify the dot graph attribute to use for exceptional control
136    * flow edges. This parameter has an effect only when
137    * drawing <code>ExceptionalGraph</code>s.
138    *
139    * @param id The attribute name, for example "style" or "color".
140    *
141    * @param value The attribute value, for example "dashed" or "red".
142    *
143    * @see <a HREF="http://www.research.att.com/sw/tools/graphviz/dotguide.pdf">"Drawing graphs with dot"</a>
144    */
145   public void setExceptionalControlFlowAttr(String id, String value) {
146     exceptionalControlFlowAttr = new DotGraphAttribute(id, value);
147   }
148
149
150   /**
151    * Specify the dot graph attribute to use for edges depicting the
152    * exceptions each node may throw, and their handlers. This
153    * parameter has an effect only when drawing
154    * <code>ExceptionalGraph</code>s.
155    *
156    * @param id The attribute name, for example "style" or "color".
157    *
158    * @param value The attribute value, for example "dotted" or "lightgray".
159    *
160    * @see <a HREF="http://www.research.att.com/sw/tools/graphviz/dotguide.pdf">"Drawing graphs with dot"</a>
161    */
162   public void setExceptionEdgeAttr(String id, String value) {
163     exceptionEdgeAttr = new DotGraphAttribute(id, value);
164   }
165
166
167   /**
168    * Specify the dot graph attribute to use for head nodes (in addition
169    * to filling in the nodes).
170    *
171    * @param id The attribute name, for example "fillcolor".
172    *
173    * @param value The attribute value, for example "gray".
174    *
175    * @see <a HREF="http://www.research.att.com/sw/tools/graphviz/dotguide.pdf">"Drawing graphs with dot"</a>
176    */
177   public void setHeadAttr(String id, String value) {
178     headAttr = new DotGraphAttribute(id, value);
179   }
180
181
182   /**
183    * Specify the dot graph attribute to use for tail nodes (in addition
184    * to filling in the nodes).
185    *
186    * @param id The attribute name, for example "fillcolor".
187    *
188    * @param value The attribute value, for example "lightgray".
189    *
190    * @see <a HREF="http://www.research.att.com/sw/tools/graphviz/dotguide.pdf">"Drawing graphs with dot"</a>
191    */
192   public void setTailAttr(String id, String value) {
193     tailAttr = new DotGraphAttribute(id, value);
194   }
195
196
197   /**
198    * Returns an {@link Iterator} over a {@link Collection} which
199    * iterates over its elements in a specified order. Used to order
200    * lists of destination nodes consistently before adding the
201    * corresponding edges to the graph. (Maintaining a consistent
202    * ordering of edges makes it easier to diff the dot files output
203    * for different graphs of a given method.)
204    *
205    * @param coll The collection to iterator over.
206    *
207    * @param comp The comparator for the ordering.
208    *
209    * @return An iterator which presents the elements of <code>coll</code>
210    * in the order specified by <code>comp</code>.
211    */
212   private static Iterator sortedIterator(Collection coll, Comparator comp) {
213     if (coll.size() <= 1) {
214       return coll.iterator();
215     } else {
216       Object array[] = coll.toArray();
217       Arrays.sort(array, comp);
218       return Arrays.asList(array).iterator();
219     }
220   }
221
222   /**
223    * Comparator used to order a list of nodes by the order in
224    * which they were labeled.
225    */
226   private static class NodeComparator implements java.util.Comparator {
227     private DotNamer namer;
228
229     NodeComparator(DotNamer namer) {
230       this.namer = namer;
231     }
232
233     public int compare(Object o1, Object o2) {
234       return (namer.getNumber(o1) - namer.getNumber(o2));
235     }
236
237     public boolean equal(Object o1, Object o2) {
238       return (namer.getNumber(o1) == namer.getNumber(o2));
239     }
240   }
241
242
243   /**
244    * Comparator used to order a list of ExceptionDests by the order in
245    * which their handler nodes were labeled.
246    */
247   private static class ExceptionDestComparator implements java.util.Comparator {
248     private DotNamer namer;
249
250     ExceptionDestComparator(DotNamer namer) {
251       this.namer = namer;
252     }
253
254     private int getValue(Object o) {
255       Object handler = ((ExceptionalGraph.ExceptionDest) o).getHandlerNode();
256       if (handler == null) {
257     return Integer.MAX_VALUE;
258       } else {
259     return namer.getNumber(handler);
260       }
261     }
262
263     public int compare(Object o1, Object o2) {
264       return (getValue(o1) - getValue(o2));
265     }
266
267     public boolean equal(Object o1, Object o2) {
268       return (getValue(o1) == getValue(o2));
269     }
270   }
271
272
273   /**
274    * Create a <code>DotGraph</code> whose nodes and edges depict
275    * a control flow graph without distinguished
276    * exceptional edges.
277    *
278    * @param graph a <code>DirectedGraph</code> representing a CFG
279    * (probably an instance of {@link UnitGraph}, {@link BlockGraph},
280    * or one of their subclasses).
281    *
282    * @param body the <code>Body</code> represented by <code>graph</code> (used
283    * to format the text within nodes). If no body is available, pass
284    * <code>null</code>.
285    *
286    * @return a visualization of <code>graph</code>.
287    */
288   public DotGraph drawCFG(DirectedGraph graph, Body body) {
289     DotGraph canvas = initDotGraph(body);
290     DotNamer namer = new DotNamer((int)(graph.size()/0.7f), 0.7f);
291     NodeComparator comparator = new NodeComparator(namer);
292
293     // To facilitate comparisons between different graphs of the same
294 // method, prelabel the nodes in the order they appear
295 // in the iterator, rather than the order that they appear in the
296 // graph traversal (so that corresponding nodes are more likely
297 // to have the same label in different graphs of a given method).
298 for (Iterator nodesIt = graph.iterator(); nodesIt.hasNext(); ) {
299       String junk = namer.getName(nodesIt.next());
300     }
301
302     for (Iterator nodesIt = graph.iterator(); nodesIt.hasNext(); ) {
303       Object node = nodesIt.next();
304       canvas.drawNode(namer.getName(node));
305       for (Iterator succsIt = sortedIterator(graph.getSuccsOf(node), comparator);
306        succsIt.hasNext(); ) {
307     Object succ = succsIt.next();
308     canvas.drawEdge(namer.getName(node), namer.getName(succ));
309       }
310     }
311     setStyle(graph.getHeads(), canvas, namer,
312          DotGraphConstants.NODE_STYLE_FILLED, headAttr);
313     setStyle(graph.getTails(), canvas, namer,
314          DotGraphConstants.NODE_STYLE_FILLED, tailAttr);
315     if (! isBrief) {
316       formatNodeText(body, canvas, namer);
317     }
318
319     return canvas;
320   }
321
322
323   /**
324    * Create a <code>DotGraph</code> whose nodes and edges depict the
325    * control flow in a <code>ExceptionalGraph</code>, with
326    * distinguished edges for exceptional control flow.
327    *
328    * @param graph the control flow graph
329    *
330    * @return a visualization of <code>graph</code>.
331    */
332   public DotGraph drawCFG(ExceptionalGraph graph) {
333     Body body = graph.getBody();
334     DotGraph canvas = initDotGraph(body);
335     DotNamer namer = new DotNamer((int)(graph.size()/0.7f), 0.7f);
336     NodeComparator nodeComparator = new NodeComparator(namer);
337
338     // Prelabel nodes in iterator order, to facilitate
339 // comparisons between graphs of a given method.
340 for (Iterator nodesIt = graph.iterator(); nodesIt.hasNext(); ) {
341       String junk = namer.getName(nodesIt.next());
342     }
343
344     for (Iterator nodesIt = graph.iterator(); nodesIt.hasNext(); ) {
345     Object node = nodesIt.next();
346
347       canvas.drawNode(namer.getName(node));
348
349       for (Iterator succsIt = sortedIterator(graph.getUnexceptionalSuccsOf(node),
350                          nodeComparator);
351        succsIt.hasNext(); ) {
352         Object succ = succsIt.next();
353         DotGraphEdge edge = canvas.drawEdge(namer.getName(node),
354                         namer.getName(succ));
355     edge.setAttribute(unexceptionalControlFlowAttr);
356       }
357
358       for (Iterator succsIt = sortedIterator(graph.getExceptionalSuccsOf(node),
359                          nodeComparator);
360        succsIt.hasNext(); ) {
361     Object succ = succsIt.next();
362     DotGraphEdge edge = canvas.drawEdge(namer.getName(node),
363                         namer.getName(succ));
364     edge.setAttribute(exceptionalControlFlowAttr);
365       }
366
367       if (showExceptions) {
368     for (Iterator destsIt = sortedIterator(graph.getExceptionDests(node),
369                            new ExceptionDestComparator(namer));
370          destsIt.hasNext(); ) {
371       ExceptionalGraph.ExceptionDest dest
372         = (ExceptionalGraph.ExceptionDest) destsIt.next();
373       Object handlerStart = dest.getHandlerNode();
374       if (handlerStart == null) {
375         // Giving each escaping exception its own, invisible
376 // exceptional exit node produces a less cluttered
377 // graph.
378 handlerStart = new Object () {
379         public String toString() {
380           return "Esc";
381         }
382           };
383         DotGraphNode escapeNode =
384           canvas.drawNode(namer.getName(handlerStart));
385         escapeNode.setStyle(DotGraphConstants.NODE_STYLE_INVISIBLE);
386       }
387       DotGraphEdge edge = canvas.drawEdge(namer.getName(node),
388                           namer.getName(handlerStart));
389       edge.setAttribute(exceptionEdgeAttr);
390       edge.setLabel(formatThrowableSet(dest.getThrowables()));
391     }
392       }
393     }
394     setStyle(graph.getHeads(), canvas, namer,
395          DotGraphConstants.NODE_STYLE_FILLED, headAttr);
396     setStyle(graph.getTails(), canvas, namer,
397          DotGraphConstants.NODE_STYLE_FILLED, tailAttr);
398     if (! isBrief) {
399       formatNodeText(graph.getBody(), canvas, namer);
400     }
401     return canvas;
402   }
403
404
405   /**
406    * A utility method that initializes a DotGraph object for use in any
407    * variety of drawCFG().
408    *
409    * @param body The <code>Body</code> that the graph will represent
410    * (used in the graph's title). If no <code>Body</code>
411    * is available, pass <code>null</code>.
412    *
413    * @return a <code>DotGraph</code> for visualizing <code>body</code>.
414    */
415   private DotGraph initDotGraph(Body body) {
416     String graphname = "cfg";
417     if (body != null) {
418       graphname = body.getMethod().getSubSignature();
419     }
420     DotGraph canvas = new DotGraph(graphname);
421     canvas.setGraphLabel(graphname);
422     if (!onePage) {
423       canvas.setPageSize(8.5, 11.0);
424     }
425     if (isBrief) {
426       canvas.setNodeShape(DotGraphConstants.NODE_SHAPE_CIRCLE);
427     } else {
428       canvas.setNodeShape(DotGraphConstants.NODE_SHAPE_BOX);
429     }
430     return canvas;
431   }
432
433
434   /**
435    * A utility class for assigning unique names to DotGraph
436    * entities. It maintains a mapping from CFG <code>Object</code>s
437    * to strings identifying the corresponding nodes in generated dot
438    * source.
439    */
440   private static class DotNamer extends HashMap {
441     private int nodecount = 0;
442
443     DotNamer(int initialCapacity, float loadFactor) {
444       super(initialCapacity, loadFactor);
445     }
446
447     DotNamer() {
448       super();
449     }
450
451     String getName(Object node) {
452       Integer index = (Integer )this.get(node);
453       if (index == null) {
454     index = new Integer (nodecount++);
455     this.put(node, index);
456       }
457       return index.toString();
458     }
459
460     int getNumber(Object node) {
461       Integer index = (Integer )this.get(node);
462       if (index == null) {
463     index = new Integer (nodecount++);
464     this.put(node, index);
465       }
466       return index.intValue();
467     }
468   }
469
470
471
472   /**
473    * A utility method which formats the text for each node in
474    * a <code>DotGraph</code> representing a CFG.
475    *
476    * @param body the <code>Body</code> whose control flow is visualized in
477    * <code>canvas</code>.
478    *
479    * @param canvas the <code>DotGraph</code> for visualizing the CFG.
480    *
481    * @param namer provides a mapping from CFG objects to identifiers in
482    * generated dot source.
483    */
484   private void formatNodeText(Body body, DotGraph canvas, DotNamer namer) {
485
486     LabeledUnitPrinter printer = null;
487     if (body != null) {
488       printer = new BriefUnitPrinter(body);
489       printer.noIndent();
490     }
491
492     for (Iterator nodesIt = namer.keySet().iterator();
493      nodesIt.hasNext(); ) {
494       Object node = nodesIt.next();
495       DotGraphNode dotnode = canvas.getNode(namer.getName(node));
496       String nodeLabel = null;
497
498       if (printer == null) {
499     nodeLabel = node.toString();
500       } else {
501     if (node instanceof Unit) {
502       ((Unit) node).toString(printer);
503       String targetLabel = (String ) printer.labels().get(node);
504       if (targetLabel == null) {
505         nodeLabel = printer.toString();
506       } else {
507         nodeLabel = targetLabel + ": " + printer.toString();
508       }
509
510     } else if (node instanceof Block) {
511       Iterator units = ((Block) node).iterator();
512       StringBuffer buffer = new StringBuffer ();
513       while (units.hasNext()) {
514         Unit unit = (Unit) units.next();
515         String targetLabel = (String ) printer.labels().get(unit);
516         if (targetLabel != null) {
517           buffer.append(targetLabel)
518         .append(":\\n");
519         }
520         unit.toString(printer);
521         buffer.append(printer.toString())
522           .append("\\l");
523       }
524       nodeLabel = buffer.toString();
525     } else {
526       nodeLabel = node.toString();
527     }
528       }
529       dotnode.setLabel(nodeLabel);
530     }
531   }
532
533
534   /**
535    * Utility routine for setting some common formatting style for the
536    * {@link DotGraphNode}s corresponding to some collection of objects.
537    *
538    * @param objects is the collection of {@link Object}s whose
539    * nodes are to be styled.
540    * @param canvas the {@link DotGraph} containing nodes corresponding
541    * to the collection.
542    * @param namer maps from {@link Object} to the strings used
543    * to identify corresponding {@link DotGraphNode}s.
544    * @param style the style to set for each of the nodes.
545    * @param attrib if non-null, an additional attribute to associate
546    * with each of the nodes.
547    */
548   private void setStyle(Collection objects, DotGraph canvas,
549             DotNamer namer, String style,
550             DotGraphAttribute attrib) {
551     // Fill the entry and exit nodes.
552 for (Iterator it = objects.iterator(); it.hasNext(); ) {
553       Object object = it.next();
554       DotGraphNode objectNode = canvas.getNode(namer.getName(object));
555       objectNode.setStyle(style);
556       objectNode.setAttribute(attrib);
557     }
558   }
559
560   /**
561    * Utility routine to format the list of names in
562    * a ThrowableSet into a label for the edge showing where those
563    * Throwables are handled.
564    */
565   private String formatThrowableSet(ThrowableSet set) {
566     String input = set.toAbbreviatedString();
567
568     // Insert line breaks between individual Throwables (dot seems to
569 // orient these edges more or less vertically, most of the time).
570 int inputLength = input.length();
571     StringBuffer result = new StringBuffer (inputLength+5);
572     for (int i = 0; i < inputLength; i++) {
573       char c = input.charAt(i);
574       if (c == '+' || c == '-') {
575     result.append("\\l");
576       }
577       result.append(c);
578     }
579     return result.toString();
580   }
581 }
582
583
584

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags