Branch data Line data Source code
1 : : /* Template classes for directed graphs.
2 : : Copyright (C) 2019-2024 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 : 900218 : 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 : 900218 : 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 : 919955 : dedge (node_t *src, node_t *dest)
65 : 473670 : : 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 : 23023 : digraph () {}
89 : 23023 : 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 : 1160 : 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 : 5 : 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 : 34 : digraph<GraphTraits>::dump_dot_to_pp (pretty_printer *pp,
147 : : cluster_t *root_cluster,
148 : : const dump_args_t &args) const
149 : : {
150 : 34 : graphviz_out gv (pp);
151 : :
152 : 34 : pp_string (pp, "digraph \"");
153 : 34 : pp_string (pp, "base");
154 : 34 : pp_string (pp, "\" {\n");
155 : :
156 : 34 : gv.indent ();
157 : :
158 : 34 : pp_string (pp, "overlap=false;\n");
159 : 34 : pp_string (pp, "compound=true;\n");
160 : :
161 : : /* If using clustering, emit all nodes via clusters. */
162 : 34 : if (root_cluster)
163 : : {
164 : : int i;
165 : : node_t *n;
166 : 590 : FOR_EACH_VEC_ELT (m_nodes, i, n)
167 : 585 : root_cluster->add_node (n);
168 : 5 : 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 : 362 : FOR_EACH_VEC_ELT (m_nodes, i, n)
176 : 333 : n->dump_dot (&gv, args);
177 : : }
178 : :
179 : : /* Edges. */
180 : : int i;
181 : : edge_t *e;
182 : 967 : FOR_EACH_VEC_ELT (m_edges, i, e)
183 : 899 : e->dump_dot (&gv, args);
184 : :
185 : : /* Terminate "digraph" */
186 : 34 : gv.outdent ();
187 : 34 : pp_string (pp, "}");
188 : 34 : pp_newline (pp);
189 : 34 : }
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 : 30 : digraph<GraphTraits>::dump_dot_to_file (FILE *fp,
198 : : cluster_t *root_cluster,
199 : : const dump_args_t &args) const
200 : : {
201 : 30 : pretty_printer pp;
202 : : // TODO:
203 : 30 : pp_format_decoder (&pp) = default_tree_printer;
204 : 30 : pp.buffer->stream = fp;
205 : 30 : dump_dot_to_pp (&pp, root_cluster, args);
206 : 30 : pp_flush (&pp);
207 : 30 : }
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 : 30 : digraph<GraphTraits>::dump_dot (const char *path,
216 : : cluster_t *root_cluster,
217 : : const dump_args_t &args) const
218 : : {
219 : 30 : FILE *fp = fopen (path, "w");
220 : 30 : dump_dot_to_file (fp, root_cluster, args);
221 : 30 : fclose (fp);
222 : 30 : }
223 : :
224 : : /* Add NODE to this DIGRAPH, taking ownership. */
225 : :
226 : : template <typename GraphTraits>
227 : : inline void
228 : 829498 : digraph<GraphTraits>::add_node (node_t *node)
229 : : {
230 : 829498 : 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 : 919955 : digraph<GraphTraits>::add_edge (edge_t *edge)
239 : : {
240 : 919955 : m_edges.safe_push (edge);
241 : 919955 : edge->m_dest->m_preds.safe_push (edge);
242 : 919955 : edge->m_src->m_succs.safe_push (edge);
243 : :
244 : 919955 : }
245 : :
246 : : #endif /* GCC_DIGRAPH_H */
|
