1/* Template classes for directed graphs.
2 Copyright (C) 2019-2023 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#ifndef GCC_DIGRAPH_H
22#define GCC_DIGRAPH_H
23
24#include "diagnostic.h"
25#include "tree-diagnostic.h" /* for default_tree_printer. */
26#include "graphviz.h"
27
28/* Templates for a family of classes: digraph, node, edge, and cluster.
29 This assumes a traits type with the following typedefs:
30 node_t: the node class
31 edge_t: the edge class
32 dump_args_t: additional args for dot-dumps
33 cluster_t: the cluster class (for use when generating .dot files).
34
35 Using a template allows for typesafe nodes and edges: a node's
36 predecessor and successor edges can be of a node-specific edge
37 subclass, without needing casting. */
38
39/* Abstract base class for a node in a directed graph. */
40
41template <typename GraphTraits>
42class dnode
43{
44 public:
45 typedef typename GraphTraits::edge_t edge_t;
46 typedef typename GraphTraits::dump_args_t dump_args_t;
47
48 virtual ~dnode () {}
49 virtual void dump_dot (graphviz_out *gv, const dump_args_t &args) const = 0;
50
51 auto_vec<edge_t *> m_preds;
52 auto_vec<edge_t *> m_succs;
53};
54
55/* Abstract base class for an edge in a directed graph. */
56
57template <typename GraphTraits>
58class dedge
59{
60 public:
61 typedef typename GraphTraits::node_t node_t;
62 typedef typename GraphTraits::dump_args_t dump_args_t;
63
64 dedge (node_t *src, node_t *dest)
65 : m_src (src), m_dest (dest) {}
66
67 virtual ~dedge () {}
68
69 virtual void dump_dot (graphviz_out *gv, const dump_args_t &args) const = 0;
70
71 node_t *const m_src;
72 node_t *const m_dest;
73};
74
75/* Abstract base class for a directed graph.
76 This class maintains the vectors of nodes and edges,
77 and owns the nodes and edges. */
78
79template <typename GraphTraits>
80class digraph
81{
82 public:
83 typedef typename GraphTraits::node_t node_t;
84 typedef typename GraphTraits::edge_t edge_t;
85 typedef typename GraphTraits::dump_args_t dump_args_t;
86 typedef typename GraphTraits::cluster_t cluster_t;
87
88 digraph () {}
89 virtual ~digraph () {}
90
91 void dump_dot_to_pp (pretty_printer *pp,
92 cluster_t *root_cluster,
93 const dump_args_t &args) const;
94 void dump_dot_to_file (FILE *fp,
95 cluster_t *root_cluster,
96 const dump_args_t &args) const;
97 void dump_dot (const char *path,
98 cluster_t *root_cluster,
99 const dump_args_t &args) const;
100
101 void add_node (node_t *node);
102 void add_edge (edge_t *edge);
103
104 auto_delete_vec<node_t> m_nodes;
105 auto_delete_vec<edge_t> m_edges;
106};
107
108/* Abstract base class for splitting dnodes into hierarchical clusters
109 in the generated .dot file.
110
111 See "Subgraphs and Clusters" within
112 https://www.graphviz.org/doc/info/lang.html
113 and e.g.
114 https://graphviz.gitlab.io/_pages/Gallery/directed/cluster.html
115
116 If a root_cluster is passed to dump_dot*, then all nodes will be
117 added to it at the start of dumping, via calls to add_node.
118
119 The root cluster can organize the nodes into a hierarchy of
120 child clusters.
121
122 After all nodes are added to the root cluster, dump_dot will then
123 be called on it (and not on the nodes themselves). */
124
125template <typename GraphTraits>
126class cluster
127{
128 public:
129 typedef typename GraphTraits::node_t node_t;
130 typedef typename GraphTraits::dump_args_t dump_args_t;
131
132 virtual ~cluster () {}
133
134 virtual void add_node (node_t *node) = 0;
135
136 /* Recursively dump the cluster, all nodes, and child clusters. */
137 virtual void dump_dot (graphviz_out *gv, const dump_args_t &) const = 0;
138};
139
140/* Write .dot information for this graph to PP, passing ARGS to the nodes
141 and edges.
142 If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters. */
143
144template <typename GraphTraits>
145inline void
146digraph<GraphTraits>::dump_dot_to_pp (pretty_printer *pp,
147 cluster_t *root_cluster,
148 const dump_args_t &args) const
149{
150 graphviz_out gv (pp);
151
152 pp_string (pp, "digraph \"");
153 pp_string (pp, "base");
154 pp_string (pp, "\" {\n");
155
156 gv.indent ();
157
158 pp_string (pp, "overlap=false;\n");
159 pp_string (pp, "compound=true;\n");
160
161 /* If using clustering, emit all nodes via clusters. */
162 if (root_cluster)
163 {
164 int i;
165 node_t *n;
166 FOR_EACH_VEC_ELT (m_nodes, i, n)
167 root_cluster->add_node (n);
168 root_cluster->dump_dot (&gv, args);
169 }
170 else
171 {
172 /* Otherwise, display all nodes at top level. */
173 int i;
174 node_t *n;
175 FOR_EACH_VEC_ELT (m_nodes, i, n)
176 n->dump_dot (&gv, args);
177 }
178
179 /* Edges. */
180 int i;
181 edge_t *e;
182 FOR_EACH_VEC_ELT (m_edges, i, e)
183 e->dump_dot (&gv, args);
184
185 /* Terminate "digraph" */
186 gv.outdent ();
187 pp_string (pp, "}");
188 pp_newline (pp);
189}
190
191/* Write .dot information for this graph to FP, passing ARGS to the nodes
192 and edges.
193 If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters. */
194
195template <typename GraphTraits>
196inline void
197digraph<GraphTraits>::dump_dot_to_file (FILE *fp,
198 cluster_t *root_cluster,
199 const dump_args_t &args) const
200{
201 pretty_printer pp;
202 // TODO:
203 pp_format_decoder (&pp) = default_tree_printer;
204 pp.buffer->stream = fp;
205 dump_dot_to_pp (pp: &pp, root_cluster, args);
206 pp_flush (&pp);
207}
208
209/* Write .dot information for this graph to a file at PATH, passing ARGS
210 to the nodes and edges.
211 If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters. */
212
213template <typename GraphTraits>
214inline void
215digraph<GraphTraits>::dump_dot (const char *path,
216 cluster_t *root_cluster,
217 const dump_args_t &args) const
218{
219 FILE *fp = fopen (filename: path, modes: "w");
220 dump_dot_to_file (fp, root_cluster, args);
221 fclose (stream: fp);
222}
223
224/* Add NODE to this DIGRAPH, taking ownership. */
225
226template <typename GraphTraits>
227inline void
228digraph<GraphTraits>::add_node (node_t *node)
229{
230 m_nodes.safe_push (node);
231}
232
233/* Add EDGE to this digraph, and to the preds/succs of its endpoints.
234 Take ownership of EDGE. */
235
236template <typename GraphTraits>
237inline void
238digraph<GraphTraits>::add_edge (edge_t *edge)
239{
240 m_edges.safe_push (edge);
241 edge->m_dest->m_preds.safe_push (edge);
242 edge->m_src->m_succs.safe_push (edge);
243
244}
245
246#endif /* GCC_DIGRAPH_H */
247

source code of gcc/digraph.h