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 <algorithm>
32 #include <cstddef>
33 #include <iterator>
34 #include <string>
35 #include <type_traits>
36 #include <vector>
37 
38 namespace llvm {
39 
40 namespace DOT {  // Private functions...
41 
42 std::string EscapeString(const std::string &Label);
43 
44 /// Get a color string for this node number. Simply round-robin selects
45 /// from a reasonable number of colors.
46 StringRef getColorString(unsigned NodeNumber);
47 
48 } // end namespace DOT
49 
50 namespace GraphProgram {
51 
52 enum Name {
53   DOT,
54   FDP,
55   NEATO,
56   TWOPI,
57   CIRCO
58 };
59 
60 } // end namespace GraphProgram
61 
62 bool DisplayGraph(StringRef Filename, bool wait = true,
63                   GraphProgram::Name program = GraphProgram::DOT);
64 
65 template<typename GraphType>
66 class GraphWriter {
67   raw_ostream &O;
68   const GraphType &G;
69 
70   using DOTTraits = DOTGraphTraits<GraphType>;
71   using GTraits = GraphTraits<GraphType>;
72   using NodeRef = typename GTraits::NodeRef;
73   using node_iterator = typename GTraits::nodes_iterator;
74   using child_iterator = typename GTraits::ChildIteratorType;
75   DOTTraits DTraits;
76 
77   static_assert(std::is_pointer<NodeRef>::value,
78                 "FIXME: Currently GraphWriter requires the NodeRef type to be "
79                 "a pointer.\nThe pointer usage should be moved to "
80                 "DOTGraphTraits, and removed from GraphWriter itself.");
81 
82   // Writes the edge labels of the node to O and returns true if there are any
83   // edge labels not equal to the empty string "".
84   bool getEdgeSourceLabels(raw_ostream &O, NodeRef Node) {
85     child_iterator EI = GTraits::child_begin(Node);
86     child_iterator EE = GTraits::child_end(Node);
87     bool hasEdgeSourceLabels = false;
88 
89     for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i) {
90       std::string label = DTraits.getEdgeSourceLabel(Node, EI);
91 
92       if (label.empty())
93         continue;
94 
95       hasEdgeSourceLabels = true;
96 
97       if (i)
98         O << "|";
99 
100       O << "<s" << i << ">" << DOT::EscapeString(label);
101     }
102 
103     if (EI != EE && hasEdgeSourceLabels)
104       O << "|<s64>truncated...";
105 
106     return hasEdgeSourceLabels;
107   }
108 
109 public:
110   GraphWriter(raw_ostream &o, const GraphType &g, bool SN) : O(o), G(g) {
111     DTraits = DOTTraits(SN);
112   }
113 
114   void writeGraph(const std::string &Title = "") {
115     // Output the header for the graph...
116     writeHeader(Title);
117 
118     // Emit all of the nodes in the graph...
119     writeNodes();
120 
121     // Output any customizations on the graph
122     DOTGraphTraits<GraphType>::addCustomGraphFeatures(G, *this);
123 
124     // Output the end of the graph
125     writeFooter();
126   }
127 
128   void writeHeader(const std::string &Title) {
129     std::string GraphName(DTraits.getGraphName(G));
130 
131     if (!Title.empty())
132       O << "digraph \"" << DOT::EscapeString(Title) << "\" {\n";
133     else if (!GraphName.empty())
134       O << "digraph \"" << DOT::EscapeString(GraphName) << "\" {\n";
135     else
136       O << "digraph unnamed {\n";
137 
138     if (DTraits.renderGraphFromBottomUp())
139       O << "\trankdir=\"BT\";\n";
140 
141     if (!Title.empty())
142       O << "\tlabel=\"" << DOT::EscapeString(Title) << "\";\n";
143     else if (!GraphName.empty())
144       O << "\tlabel=\"" << DOT::EscapeString(GraphName) << "\";\n";
145     O << DTraits.getGraphProperties(G);
146     O << "\n";
147   }
148 
149   void writeFooter() {
150     // Finish off the graph
151     O << "}\n";
152   }
153 
154   void writeNodes() {
155     // Loop over the graph, printing it out...
156     for (const auto Node : nodes<GraphType>(G))
157       if (!isNodeHidden(Node))
158         writeNode(Node);
159   }
160 
161   bool isNodeHidden(NodeRef Node) { return DTraits.isNodeHidden(Node, G); }
162 
163   void writeNode(NodeRef Node) {
164     std::string NodeAttributes = DTraits.getNodeAttributes(Node, G);
165 
166     O << "\tNode" << static_cast<const void*>(Node) << " [shape=record,";
167     if (!NodeAttributes.empty()) O << NodeAttributes << ",";
168     O << "label=\"{";
169 
170     if (!DTraits.renderGraphFromBottomUp()) {
171       O << DOT::EscapeString(DTraits.getNodeLabel(Node, G));
172 
173       // If we should include the address of the node in the label, do so now.
174       std::string Id = DTraits.getNodeIdentifierLabel(Node, G);
175       if (!Id.empty())
176         O << "|" << DOT::EscapeString(Id);
177 
178       std::string NodeDesc = DTraits.getNodeDescription(Node, G);
179       if (!NodeDesc.empty())
180         O << "|" << DOT::EscapeString(NodeDesc);
181     }
182 
183     std::string edgeSourceLabels;
184     raw_string_ostream EdgeSourceLabels(edgeSourceLabels);
185     bool hasEdgeSourceLabels = getEdgeSourceLabels(EdgeSourceLabels, Node);
186 
187     if (hasEdgeSourceLabels) {
188       if (!DTraits.renderGraphFromBottomUp()) O << "|";
189 
190       O << "{" << EdgeSourceLabels.str() << "}";
191 
192       if (DTraits.renderGraphFromBottomUp()) O << "|";
193     }
194 
195     if (DTraits.renderGraphFromBottomUp()) {
196       O << DOT::EscapeString(DTraits.getNodeLabel(Node, G));
197 
198       // If we should include the address of the node in the label, do so now.
199       std::string Id = DTraits.getNodeIdentifierLabel(Node, G);
200       if (!Id.empty())
201         O << "|" << DOT::EscapeString(Id);
202 
203       std::string NodeDesc = DTraits.getNodeDescription(Node, G);
204       if (!NodeDesc.empty())
205         O << "|" << DOT::EscapeString(NodeDesc);
206     }
207 
208     if (DTraits.hasEdgeDestLabels()) {
209       O << "|{";
210 
211       unsigned i = 0, e = DTraits.numEdgeDestLabels(Node);
212       for (; i != e && i != 64; ++i) {
213         if (i) O << "|";
214         O << "<d" << i << ">"
215           << DOT::EscapeString(DTraits.getEdgeDestLabel(Node, i));
216       }
217 
218       if (i != e)
219         O << "|<d64>truncated...";
220       O << "}";
221     }
222 
223     O << "}\"];\n";   // Finish printing the "node" line
224 
225     // Output all of the edges now
226     child_iterator EI = GTraits::child_begin(Node);
227     child_iterator EE = GTraits::child_end(Node);
228     for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i)
229       if (!DTraits.isNodeHidden(*EI, G))
230         writeEdge(Node, i, EI);
231     for (; EI != EE; ++EI)
232       if (!DTraits.isNodeHidden(*EI, G))
233         writeEdge(Node, 64, EI);
234   }
235 
236   void writeEdge(NodeRef Node, unsigned edgeidx, child_iterator EI) {
237     if (NodeRef TargetNode = *EI) {
238       int DestPort = -1;
239       if (DTraits.edgeTargetsEdgeSource(Node, EI)) {
240         child_iterator TargetIt = DTraits.getEdgeTarget(Node, EI);
241 
242         // Figure out which edge this targets...
243         unsigned Offset =
244           (unsigned)std::distance(GTraits::child_begin(TargetNode), TargetIt);
245         DestPort = static_cast<int>(Offset);
246       }
247 
248       if (DTraits.getEdgeSourceLabel(Node, EI).empty())
249         edgeidx = -1;
250 
251       emitEdge(static_cast<const void*>(Node), edgeidx,
252                static_cast<const void*>(TargetNode), DestPort,
253                DTraits.getEdgeAttributes(Node, EI, G));
254     }
255   }
256 
257   /// emitSimpleNode - Outputs a simple (non-record) node
258   void emitSimpleNode(const void *ID, const std::string &Attr,
259                    const std::string &Label, unsigned NumEdgeSources = 0,
260                    const std::vector<std::string> *EdgeSourceLabels = nullptr) {
261     O << "\tNode" << ID << "[ ";
262     if (!Attr.empty())
263       O << Attr << ",";
264     O << " label =\"";
265     if (NumEdgeSources) O << "{";
266     O << DOT::EscapeString(Label);
267     if (NumEdgeSources) {
268       O << "|{";
269 
270       for (unsigned i = 0; i != NumEdgeSources; ++i) {
271         if (i) O << "|";
272         O << "<s" << i << ">";
273         if (EdgeSourceLabels) O << DOT::EscapeString((*EdgeSourceLabels)[i]);
274       }
275       O << "}}";
276     }
277     O << "\"];\n";
278   }
279 
280   /// emitEdge - Output an edge from a simple node into the graph...
281   void emitEdge(const void *SrcNodeID, int SrcNodePort,
282                 const void *DestNodeID, int DestNodePort,
283                 const std::string &Attrs) {
284     if (SrcNodePort  > 64) return;             // Eminating from truncated part?
285     if (DestNodePort > 64) DestNodePort = 64;  // Targeting the truncated part?
286 
287     O << "\tNode" << SrcNodeID;
288     if (SrcNodePort >= 0)
289       O << ":s" << SrcNodePort;
290     O << " -> Node" << DestNodeID;
291     if (DestNodePort >= 0 && DTraits.hasEdgeDestLabels())
292       O << ":d" << DestNodePort;
293 
294     if (!Attrs.empty())
295       O << "[" << Attrs << "]";
296     O << ";\n";
297   }
298 
299   /// getOStream - Get the raw output stream into the graph file. Useful to
300   /// write fancy things using addCustomGraphFeatures().
301   raw_ostream &getOStream() {
302     return O;
303   }
304 };
305 
306 template<typename GraphType>
307 raw_ostream &WriteGraph(raw_ostream &O, const GraphType &G,
308                         bool ShortNames = false,
309                         const Twine &Title = "") {
310   // Start the graph emission process...
311   GraphWriter<GraphType> W(O, G, ShortNames);
312 
313   // Emit the graph.
314   W.writeGraph(Title.str());
315 
316   return O;
317 }
318 
319 std::string createGraphFilename(const Twine &Name, int &FD);
320 
321 /// Writes graph into a provided {@code Filename}.
322 /// If {@code Filename} is empty, generates a random one.
323 /// \return The resulting filename, or an empty string if writing
324 /// failed.
325 template <typename GraphType>
326 std::string WriteGraph(const GraphType &G, const Twine &Name,
327                        bool ShortNames = false,
328                        const Twine &Title = "",
329                        std::string Filename = "") {
330   int FD;
331   if (Filename.empty()) {
332     Filename = createGraphFilename(Name.str(), FD);
333   } else {
334     std::error_code EC = sys::fs::openFileForWrite(Filename, FD);
335 
336     // Writing over an existing file is not considered an error.
337     if (EC == std::errc::file_exists) {
338       errs() << "file exists, overwriting" << "\n";
339     } else if (EC) {
340       errs() << "error writing into file" << "\n";
341       return "";
342     } else {
343       errs() << "writing to the newly created file " << Filename << "\n";
344     }
345   }
346   raw_fd_ostream O(FD, /*shouldClose=*/ true);
347 
348   if (FD == -1) {
349     errs() << "error opening file '" << Filename << "' for writing!\n";
350     return "";
351   }
352 
353   llvm::WriteGraph(O, G, ShortNames, Title);
354   errs() << " done. \n";
355 
356   return Filename;
357 }
358 
359 /// DumpDotGraph - Just dump a dot graph to the user-provided file name.
360 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
361 template <typename GraphType>
362 LLVM_DUMP_METHOD void
363 dumpDotGraphToFile(const GraphType &G, const Twine &FileName,
364                    const Twine &Title, bool ShortNames = false,
365                    const Twine &Name = "") {
366   llvm::WriteGraph(G, Name, ShortNames, Title, FileName.str());
367 }
368 #endif
369 
370 /// ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file,
371 /// then cleanup.  For use from the debugger.
372 ///
373 template<typename GraphType>
374 void ViewGraph(const GraphType &G, const Twine &Name,
375                bool ShortNames = false, const Twine &Title = "",
376                GraphProgram::Name Program = GraphProgram::DOT) {
377   std::string Filename = llvm::WriteGraph(G, Name, ShortNames, Title);
378 
379   if (Filename.empty())
380     return;
381 
382   DisplayGraph(Filename, false, Program);
383 }
384 
385 } // end namespace llvm
386 
387 #endif // LLVM_SUPPORT_GRAPHWRITER_H
388