1 //===- llvm/Support/GraphWriter.h - Write graph to a .dot file --*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines a simple interface that can be used to print out generic
10 // LLVM graphs to ".dot" files.  "dot" is a tool that is part of the AT&T
11 // graphviz package (http://www.research.att.com/sw/tools/graphviz/) which can
12 // be used to turn the files output by this interface into a variety of
13 // different graphics formats.
14 //
15 // Graphs do not need to implement any interface past what is already required
16 // by the GraphTraits template, but they can choose to implement specializations
17 // of the DOTGraphTraits template if they want to customize the graphs output in
18 // any way.
19 //
20 //===----------------------------------------------------------------------===//
21 
22 #ifndef LLVM_SUPPORT_GRAPHWRITER_H
23 #define LLVM_SUPPORT_GRAPHWRITER_H
24 
25 #include "llvm/ADT/GraphTraits.h"
26 #include "llvm/ADT/StringRef.h"
27 #include "llvm/ADT/Twine.h"
28 #include "llvm/Support/DOTGraphTraits.h"
29 #include "llvm/Support/FileSystem.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include <iterator>
32 #include <string>
33 #include <type_traits>
34 #include <vector>
35 
36 namespace llvm {
37 
38 namespace DOT {  // Private functions...
39 
40 std::string EscapeString(const std::string &Label);
41 
42 /// Get a color string for this node number. Simply round-robin selects
43 /// from a reasonable number of colors.
44 StringRef getColorString(unsigned NodeNumber);
45 
46 } // end namespace DOT
47 
48 namespace GraphProgram {
49 
50 enum Name {
51   DOT,
52   FDP,
53   NEATO,
54   TWOPI,
55   CIRCO
56 };
57 
58 } // end namespace GraphProgram
59 
60 bool DisplayGraph(StringRef Filename, bool wait = true,
61                   GraphProgram::Name program = GraphProgram::DOT);
62 
63 template<typename GraphType>
64 class GraphWriter {
65   raw_ostream &O;
66   const GraphType &G;
67   bool RenderUsingHTML = false;
68 
69   using DOTTraits = DOTGraphTraits<GraphType>;
70   using GTraits = GraphTraits<GraphType>;
71   using NodeRef = typename GTraits::NodeRef;
72   using node_iterator = typename GTraits::nodes_iterator;
73   using child_iterator = typename GTraits::ChildIteratorType;
74   DOTTraits DTraits;
75 
76   static_assert(std::is_pointer_v<NodeRef>,
77                 "FIXME: Currently GraphWriter requires the NodeRef type to be "
78                 "a pointer.\nThe pointer usage should be moved to "
79                 "DOTGraphTraits, and removed from GraphWriter itself.");
80 
81   // Writes the edge labels of the node to O and returns true if there are any
82   // edge labels not equal to the empty string "".
83   bool getEdgeSourceLabels(raw_ostream &O, NodeRef Node) {
84     child_iterator EI = GTraits::child_begin(Node);
85     child_iterator EE = GTraits::child_end(Node);
86     bool hasEdgeSourceLabels = false;
87 
88     if (RenderUsingHTML)
89       O << "</tr><tr>";
90 
91     for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i) {
92       std::string label = DTraits.getEdgeSourceLabel(Node, EI);
93 
94       if (label.empty())
95         continue;
96 
97       hasEdgeSourceLabels = true;
98 
99       if (RenderUsingHTML)
100         O << "<td colspan=\"1\" port=\"s" << i << "\">" << label << "</td>";
101       else {
102         if (i)
103           O << "|";
104 
105         O << "<s" << i << ">" << DOT::EscapeString(label);
106       }
107     }
108 
109     if (EI != EE && hasEdgeSourceLabels) {
110       if (RenderUsingHTML)
111         O << "<td colspan=\"1\" port=\"s64\">truncated...</td>";
112       else
113         O << "|<s64>truncated...";
114     }
115 
116     return hasEdgeSourceLabels;
117   }
118 
119 public:
120   GraphWriter(raw_ostream &o, const GraphType &g, bool SN) : O(o), G(g) {
121     DTraits = DOTTraits(SN);
122     RenderUsingHTML = DTraits.renderNodesUsingHTML();
123   }
124 
125   void writeGraph(const std::string &Title = "") {
126     // Output the header for the graph...
127     writeHeader(Title);
128 
129     // Emit all of the nodes in the graph...
130     writeNodes();
131 
132     // Output any customizations on the graph
133     DOTGraphTraits<GraphType>::addCustomGraphFeatures(G, *this);
134 
135     // Output the end of the graph
136     writeFooter();
137   }
138 
139   void writeHeader(const std::string &Title) {
140     std::string GraphName(DTraits.getGraphName(G));
141 
142     if (!Title.empty())
143       O << "digraph \"" << DOT::EscapeString(Title) << "\" {\n";
144     else if (!GraphName.empty())
145       O << "digraph \"" << DOT::EscapeString(GraphName) << "\" {\n";
146     else
147       O << "digraph unnamed {\n";
148 
149     if (DTraits.renderGraphFromBottomUp())
150       O << "\trankdir=\"BT\";\n";
151 
152     if (!Title.empty())
153       O << "\tlabel=\"" << DOT::EscapeString(Title) << "\";\n";
154     else if (!GraphName.empty())
155       O << "\tlabel=\"" << DOT::EscapeString(GraphName) << "\";\n";
156     O << DTraits.getGraphProperties(G);
157     O << "\n";
158   }
159 
160   void writeFooter() {
161     // Finish off the graph
162     O << "}\n";
163   }
164 
165   void writeNodes() {
166     // Loop over the graph, printing it out...
167     for (const auto Node : nodes<GraphType>(G))
168       if (!isNodeHidden(Node))
169         writeNode(Node);
170   }
171 
172   bool isNodeHidden(NodeRef Node) { return DTraits.isNodeHidden(Node, G); }
173 
174   void writeNode(NodeRef Node) {
175     std::string NodeAttributes = DTraits.getNodeAttributes(Node, G);
176 
177     O << "\tNode" << static_cast<const void *>(Node) << " [shape=";
178     if (RenderUsingHTML)
179       O << "none,";
180     else
181       O << "record,";
182 
183     if (!NodeAttributes.empty()) O << NodeAttributes << ",";
184     O << "label=";
185 
186     if (RenderUsingHTML) {
187       // Count the numbewr of edges out of the node to determine how
188       // many columns to span (max 64)
189       unsigned ColSpan = 0;
190       child_iterator EI = GTraits::child_begin(Node);
191       child_iterator EE = GTraits::child_end(Node);
192       for (; EI != EE && ColSpan != 64; ++EI, ++ColSpan)
193         ;
194       if (ColSpan == 0)
195         ColSpan = 1;
196       // Include truncated messages when counting.
197       if (EI != EE)
198         ++ColSpan;
199       O << "<<table border=\"0\" cellborder=\"1\" cellspacing=\"0\""
200         << " cellpadding=\"0\"><tr><td align=\"text\" colspan=\"" << ColSpan
201         << "\">";
202     } else
203       O << "\"{";
204 
205     if (!DTraits.renderGraphFromBottomUp()) {
206       if (RenderUsingHTML)
207         O << DTraits.getNodeLabel(Node, G) << "</td>";
208       else
209         O << DOT::EscapeString(DTraits.getNodeLabel(Node, G));
210 
211       // If we should include the address of the node in the label, do so now.
212       std::string Id = DTraits.getNodeIdentifierLabel(Node, G);
213       if (!Id.empty())
214         O << "|" << DOT::EscapeString(Id);
215 
216       std::string NodeDesc = DTraits.getNodeDescription(Node, G);
217       if (!NodeDesc.empty())
218         O << "|" << DOT::EscapeString(NodeDesc);
219     }
220 
221     std::string edgeSourceLabels;
222     raw_string_ostream EdgeSourceLabels(edgeSourceLabels);
223     bool hasEdgeSourceLabels = getEdgeSourceLabels(EdgeSourceLabels, Node);
224 
225     if (hasEdgeSourceLabels) {
226       if (!DTraits.renderGraphFromBottomUp())
227         if (!RenderUsingHTML)
228           O << "|";
229 
230       if (RenderUsingHTML)
231         O << EdgeSourceLabels.str();
232       else
233         O << "{" << EdgeSourceLabels.str() << "}";
234 
235       if (DTraits.renderGraphFromBottomUp())
236         if (!RenderUsingHTML)
237           O << "|";
238     }
239 
240     if (DTraits.renderGraphFromBottomUp()) {
241       if (RenderUsingHTML)
242         O << DTraits.getNodeLabel(Node, G);
243       else
244         O << DOT::EscapeString(DTraits.getNodeLabel(Node, G));
245 
246       // If we should include the address of the node in the label, do so now.
247       std::string Id = DTraits.getNodeIdentifierLabel(Node, G);
248       if (!Id.empty())
249         O << "|" << DOT::EscapeString(Id);
250 
251       std::string NodeDesc = DTraits.getNodeDescription(Node, G);
252       if (!NodeDesc.empty())
253         O << "|" << DOT::EscapeString(NodeDesc);
254     }
255 
256     if (DTraits.hasEdgeDestLabels()) {
257       O << "|{";
258 
259       unsigned i = 0, e = DTraits.numEdgeDestLabels(Node);
260       for (; i != e && i != 64; ++i) {
261         if (i) O << "|";
262         O << "<d" << i << ">"
263           << DOT::EscapeString(DTraits.getEdgeDestLabel(Node, i));
264       }
265 
266       if (i != e)
267         O << "|<d64>truncated...";
268       O << "}";
269     }
270 
271     if (RenderUsingHTML)
272       O << "</tr></table>>";
273     else
274       O << "}\"";
275     O << "];\n"; // Finish printing the "node" line
276 
277     // Output all of the edges now
278     child_iterator EI = GTraits::child_begin(Node);
279     child_iterator EE = GTraits::child_end(Node);
280     for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i)
281       if (!DTraits.isNodeHidden(*EI, G))
282         writeEdge(Node, i, EI);
283     for (; EI != EE; ++EI)
284       if (!DTraits.isNodeHidden(*EI, G))
285         writeEdge(Node, 64, EI);
286   }
287 
288   void writeEdge(NodeRef Node, unsigned edgeidx, child_iterator EI) {
289     if (NodeRef TargetNode = *EI) {
290       int DestPort = -1;
291       if (DTraits.edgeTargetsEdgeSource(Node, EI)) {
292         child_iterator TargetIt = DTraits.getEdgeTarget(Node, EI);
293 
294         // Figure out which edge this targets...
295         unsigned Offset =
296           (unsigned)std::distance(GTraits::child_begin(TargetNode), TargetIt);
297         DestPort = static_cast<int>(Offset);
298       }
299 
300       if (DTraits.getEdgeSourceLabel(Node, EI).empty())
301         edgeidx = -1;
302 
303       emitEdge(static_cast<const void*>(Node), edgeidx,
304                static_cast<const void*>(TargetNode), DestPort,
305                DTraits.getEdgeAttributes(Node, EI, G));
306     }
307   }
308 
309   /// emitSimpleNode - Outputs a simple (non-record) node
310   void emitSimpleNode(const void *ID, const std::string &Attr,
311                    const std::string &Label, unsigned NumEdgeSources = 0,
312                    const std::vector<std::string> *EdgeSourceLabels = nullptr) {
313     O << "\tNode" << ID << "[ ";
314     if (!Attr.empty())
315       O << Attr << ",";
316     O << " label =\"";
317     if (NumEdgeSources) O << "{";
318     O << DOT::EscapeString(Label);
319     if (NumEdgeSources) {
320       O << "|{";
321 
322       for (unsigned i = 0; i != NumEdgeSources; ++i) {
323         if (i) O << "|";
324         O << "<s" << i << ">";
325         if (EdgeSourceLabels) O << DOT::EscapeString((*EdgeSourceLabels)[i]);
326       }
327       O << "}}";
328     }
329     O << "\"];\n";
330   }
331 
332   /// emitEdge - Output an edge from a simple node into the graph...
333   void emitEdge(const void *SrcNodeID, int SrcNodePort,
334                 const void *DestNodeID, int DestNodePort,
335                 const std::string &Attrs) {
336     if (SrcNodePort  > 64) return;             // Eminating from truncated part?
337     if (DestNodePort > 64) DestNodePort = 64;  // Targeting the truncated part?
338 
339     O << "\tNode" << SrcNodeID;
340     if (SrcNodePort >= 0)
341       O << ":s" << SrcNodePort;
342     O << " -> Node" << DestNodeID;
343     if (DestNodePort >= 0 && DTraits.hasEdgeDestLabels())
344       O << ":d" << DestNodePort;
345 
346     if (!Attrs.empty())
347       O << "[" << Attrs << "]";
348     O << ";\n";
349   }
350 
351   /// getOStream - Get the raw output stream into the graph file. Useful to
352   /// write fancy things using addCustomGraphFeatures().
353   raw_ostream &getOStream() {
354     return O;
355   }
356 };
357 
358 template<typename GraphType>
359 raw_ostream &WriteGraph(raw_ostream &O, const GraphType &G,
360                         bool ShortNames = false,
361                         const Twine &Title = "") {
362   // Start the graph emission process...
363   GraphWriter<GraphType> W(O, G, ShortNames);
364 
365   // Emit the graph.
366   W.writeGraph(Title.str());
367 
368   return O;
369 }
370 
371 std::string createGraphFilename(const Twine &Name, int &FD);
372 
373 /// Writes graph into a provided @c Filename.
374 /// If @c Filename is empty, generates a random one.
375 /// \return The resulting filename, or an empty string if writing
376 /// failed.
377 template <typename GraphType>
378 std::string WriteGraph(const GraphType &G, const Twine &Name,
379                        bool ShortNames = false,
380                        const Twine &Title = "",
381                        std::string Filename = "") {
382   int FD;
383   if (Filename.empty()) {
384     Filename = createGraphFilename(Name.str(), FD);
385   } else {
386     std::error_code EC = sys::fs::openFileForWrite(
387         Filename, FD, sys::fs::CD_CreateAlways, sys::fs::OF_Text);
388 
389     // Writing over an existing file is not considered an error.
390     if (EC == std::errc::file_exists) {
391       errs() << "file exists, overwriting" << "\n";
392     } else if (EC) {
393       errs() << "error writing into file" << "\n";
394       return "";
395     } else {
396       errs() << "writing to the newly created file " << Filename << "\n";
397     }
398   }
399   raw_fd_ostream O(FD, /*shouldClose=*/ true);
400 
401   if (FD == -1) {
402     errs() << "error opening file '" << Filename << "' for writing!\n";
403     return "";
404   }
405 
406   llvm::WriteGraph(O, G, ShortNames, Title);
407   errs() << " done. \n";
408 
409   return Filename;
410 }
411 
412 /// DumpDotGraph - Just dump a dot graph to the user-provided file name.
413 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
414 template <typename GraphType>
415 LLVM_DUMP_METHOD void
416 dumpDotGraphToFile(const GraphType &G, const Twine &FileName,
417                    const Twine &Title, bool ShortNames = false,
418                    const Twine &Name = "") {
419   llvm::WriteGraph(G, Name, ShortNames, Title, FileName.str());
420 }
421 #endif
422 
423 /// ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file,
424 /// then cleanup.  For use from the debugger.
425 ///
426 template<typename GraphType>
427 void ViewGraph(const GraphType &G, const Twine &Name,
428                bool ShortNames = false, const Twine &Title = "",
429                GraphProgram::Name Program = GraphProgram::DOT) {
430   std::string Filename = llvm::WriteGraph(G, Name, ShortNames, Title);
431 
432   if (Filename.empty())
433     return;
434 
435   DisplayGraph(Filename, false, Program);
436 }
437 
438 } // end namespace llvm
439 
440 #endif // LLVM_SUPPORT_GRAPHWRITER_H
441