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