1
2
3
4 package joeq.Compiler.Quad;
5
6 import java.util.ArrayList;
7 import java.util.HashMap;
8 import java.util.Iterator;
9 import java.util.List;
10 import java.util.Map;
11 import java.io.File;
12 import java.io.FileOutputStream;
13 import java.io.IOException;
14 import java.io.PrintWriter;
15 import joeq.Class.jq_Class;
16 import joeq.Class.jq_Method;
17 import joeq.Util.Templates.ListIterator;
18
19 /***
20 * @author Godmar Back <gback@cs.utah.edu, @stanford.edu>
21 *
22 * This class is a ControlFlowGraphVisitor.
23 * For each CFG, it produces a "dot" file in the output directory.
24 * See or change createMethodName to adapt how the filenames are formed.
25 *
26 * @see DotGraph#outputDir
27 * @see DotGraph#dotFilePrefix
28 * @see DotGraph#createMethodName(jq_Method)
29 *
30 * @version $Id: DotGraph.java 1931 2004-09-22 22:17:47Z joewhaley $
31 */
32 public class DotGraph implements ControlFlowGraphVisitor {
33
34 /***
35 * The output directory for the dot graph descriptions
36 */
37 public static String outputDir = "dottedcfgs";
38
39 /***
40 * Prefix that goes before the name.
41 */
42 public static String dotFilePrefix = "joeq-";
43
44 /***
45 * Adapt this method to create filenames the way you want them.
46 */
47 protected String createMethodName(jq_Method mth) {
48 String filename = dotFilePrefix + mth.toString();
49 filename = filename.replace('/', '_');
50 filename = filename.replace(' ', '_');
51 filename = filename.replace('<', '_');
52 filename = filename.replace('>', '_');
53 filename = filename.replace('(', '_');
54 filename = filename.replace(')', '_');
55
56 return filename;
57 }
58
59 /***
60 * dot - helper class for outputting graphviz specifications for simple cfgs
61 *
62 * See http://www.research.att.com/sw/tools/graphviz/
63 *
64 * Process with, for instance, "dot -Tgif -o graph.gif <inputfile>"
65 * or simply "dotgif <inputfile>"
66 *
67 * @author Godmar Back <gback@cs.utah.edu>
68 */
69 public static class dot {
70 private static PrintWriter containedgraph = null;
71 /***
72 * The first argument specifies what directory to use for output, the
73 * second is the file name.
74 */
75 public static void openGraph(String the_outputDir, String name) {
76 try {
77 if (the_outputDir != null)
78 outputDir = the_outputDir;
79 String dirname = outputDir;
80 File d = new File(dirname);
81 if (!d.exists()) {
82 d.mkdir();
83 }
84 String dirsep = System.getProperty("file.separator");
85 containedgraph = new PrintWriter(new FileOutputStream(dirname
86 + dirsep + name));
87 containedgraph.println("digraph contained_in_graph {");
88 containedgraph
89 .println("\tnode[shape=box,fontname = \"Arial\", fontsize=10];");
90 containedgraph
91 .println("\tedge[fontname = \"Arial\", fontcolor=red, fontsize=8];");
92 containedgraph.println("\tlabel = \"" + name + "\";");
93 } catch (IOException _) {
94 _.printStackTrace(System.err);
95 }
96 }
97 public static void openGraph(String name) {
98 openGraph(null, name);
99 }
100
101 public static String escape(String from) {
102 from = from.replace('\t', ' ').trim();
103 StringBuffer fb = new StringBuffer();
104 for (int i = 0, sucspaces = 0; i < from.length(); i++) {
105 char c = from.charAt(i);
106 if (c == '"' || c == '//')
107 fb.append("//" + c);
108 else if (c == '\n')
109 fb.append("////n");
110 else if (c == '\r')
111 fb.append("////r");
112 else if (sucspaces == 0 || c != ' ')
113 fb.append(c);
114 if (c == ' ')
115 sucspaces++;
116 else
117 sucspaces = 0;
118 }
119 return fb.toString();
120 }
121
122 private static void outputString(String from) {
123 containedgraph.print("\"" + escape(from) + "\"");
124 }
125
126 private static void labelEdge(String edge) {
127 if (edge != null) {
128 containedgraph.print("[label=");
129 outputString(edge);
130 containedgraph.print(",color=red]");
131 }
132 }
133
134 public static void userDefined(String useroutput) {
135 if (containedgraph != null) {
136 containedgraph.print(useroutput);
137 }
138 }
139
140 private static void makeCircleNode(String to) {
141 containedgraph.print("\t");
142 outputString(to);
143 containedgraph.println("[shape=circle,fontcolor=red,color=red];");
144 }
145
146 public static void addEntryEdge(String from, String to, String edge) {
147 if (containedgraph != null) {
148 makeCircleNode(from);
149 containedgraph.print("\t");
150 outputString(from);
151 containedgraph.print(" -> ");
152 outputString(to);
153 labelEdge(edge);
154 containedgraph.println(";");
155 }
156 }
157
158 public static void addLeavingEdge(String from, String to, String edge) {
159 if (containedgraph != null) {
160 makeCircleNode(to);
161 containedgraph.print("\t");
162 outputString(from);
163 containedgraph.print(" -> ");
164 outputString(to);
165 labelEdge(edge);
166 containedgraph.println(";");
167 }
168 }
169
170 public static void addEdge(String from, String to) {
171 addEdge(from, to, null);
172 }
173
174 public static void addEdge(String from, String to, String edge) {
175 if (containedgraph != null) {
176 containedgraph.print("\t");
177 outputString(from);
178 containedgraph.print(" -> ");
179 outputString(to);
180 labelEdge(edge);
181 containedgraph.println(";");
182 }
183 }
184
185 public static void closeGraph() {
186 containedgraph.println("}");
187 containedgraph.close();
188 containedgraph = null;
189 }
190 }
191
192 /***
193 * Use the dot helper class to output this cfg as a Graph.
194 */
195 public void visitCFG(ControlFlowGraph cfg) {
196 final HashMap fedge2PEIList = new HashMap();
197 try {
198 String filename = createMethodName(cfg.getMethod());
199 dot.openGraph(filename);
200 cfg.visitBasicBlocks(new BasicBlockVisitor() {
201 public void visitBasicBlock(BasicBlock bb) {
202 if (bb.isEntry()) {
203 if (bb.getNumberOfSuccessors() != 1)
204 throw new Error("entry bb has != 1 successors "
205 + bb.getNumberOfSuccessors());
206 dot.addEntryEdge(bb.toString(), bb.getSuccessors()
207 .iterator().next().toString(), null);
208 } else if (!bb.isExit()) {
209 ListIterator.Quad qit = bb.iterator();
210 StringBuffer l = new StringBuffer(" " + bb.toString()
211 + "//l");
212 HashMap
213 while (qit.hasNext()) {
214 l.append(" ");
215 Quad quad = qit.nextQuad();
216 l.append(dot.escape(quad.toString()));
217 l.append("//l");
218 ListIterator.jq_Class exceptions = quad
219 .getThrownExceptions().classIterator();
220 while (exceptions.hasNext()) {
221 jq_Class exc = exceptions.nextClass();
222 ArrayList peis = (ArrayList) exceptions2PEIList
223 .get(exc);
224 if (peis == null)
225 exceptions2PEIList.put(exc,
226 peis = new ArrayList());
227 peis.add(quad);
228 }
229 }
230 dot.userDefined("\t" + bb.toString()
231 + " [shape=box,label=\"" + l + "\"];\n");
232 ListIterator.BasicBlock bit = bb.getSuccessors()
233 .basicBlockIterator();
234 while (bit.hasNext()) {
235 BasicBlock nextbb = bit.nextBasicBlock();
236 if (nextbb.isExit()) {
237 dot.addLeavingEdge(bb.toString(), nextbb
238 .toString(), null);
239 } else {
240 dot.addEdge(bb.toString(), nextbb.toString());
241 }
242 }
243 Iterator eit = exceptions2PEIList.entrySet().iterator();
244 while (eit.hasNext()) {
245 Map.Entry e = (Map.Entry) eit.next();
246 jq_Class exc = (jq_Class) e.getKey();
247 List
248 ListIterator.ExceptionHandler mayCatch;
249 mayCatch = bb.getExceptionHandlers().mayCatch(exc)
250 .exceptionHandlerIterator();
251 while (mayCatch.hasNext()) {
252 ExceptionHandler exceptionHandler = mayCatch
253 .nextExceptionHandler();
254 BasicBlock nextbb = exceptionHandler.getEntry();
255 FactoredEdge fe = new FactoredEdge(bb, nextbb,
256 exceptionHandler.getExceptionType());
257 List factoredPeiList = (List) fedge2PEIList
258 .get(fe);
259 if (factoredPeiList == null) {
260 fedge2PEIList.put(fe,
261 factoredPeiList = new ArrayList());
262 }
263 factoredPeiList.addAll(thisPeiList);
264
265
266
267 }
268
269
270 }
271 }
272 }
273 });
274 } finally {
275 Iterator fedges = fedge2PEIList.entrySet().iterator();
276 while (fedges.hasNext()) {
277 Map.Entry e = (Map.Entry) fedges.next();
278 FactoredEdge fe = (FactoredEdge) e.getKey();
279 List factoredPeiList = (List) e.getValue();
280 String peis = "[" + ((Quad) factoredPeiList.get(0)).getID();
281 for (int i = 1; i < factoredPeiList.size(); i++) {
282 peis += ", " + ((Quad) factoredPeiList.get(i)).getID();
283 }
284 peis += "] ";
285 dot.addEdge(fe.from.toString(), fe.to.toString(), peis
286 + fe.exception);
287 }
288 dot.closeGraph();
289 }
290 }
291
292 class FactoredEdge {
293 BasicBlock from, to;
294 jq_Class exception;
295 FactoredEdge(BasicBlock from, BasicBlock to, jq_Class exception) {
296 this.from = from;
297 this.to = to;
298 this.exception = exception;
299 }
300 public boolean equals(Object that) {
301 return equals((FactoredEdge) that);
302 }
303 public int hashCode() {
304 return from.hashCode() ^ to.hashCode();
305 }
306 public boolean equals(FactoredEdge that) {
307 return this.from.equals(that.from) && this.to.equals(that.to)
308 && this.exception.equals(that.exception);
309 }
310 }
311 }