1 /* Template classes for directed graphs.
2 Copyright (C) 2019-2023 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along 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
41 template <typename GraphTraits>
42 class 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
57 template <typename GraphTraits>
58 class 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
79 template <typename GraphTraits>
80 class 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
125 template <typename GraphTraits>
126 class 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
144 template <typename GraphTraits>
145 inline void
146 digraph<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
195 template <typename GraphTraits>
196 inline void
197 digraph<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, 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
213 template <typename GraphTraits>
214 inline void
215 digraph<GraphTraits>::dump_dot (const char *path,
216 cluster_t *root_cluster,
217 const dump_args_t &args) const
218 {
219 FILE *fp = fopen (path, "w");
220 dump_dot_to_file (fp, root_cluster, args);
221 fclose (fp);
222 }
223
224 /* Add NODE to this DIGRAPH, taking ownership. */
225
226 template <typename GraphTraits>
227 inline void
228 digraph<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
236 template <typename GraphTraits>
237 inline void
238 digraph<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 */