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: &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 (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 | |
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 */ |
247 | |