]>
Commit | Line | Data |
---|---|---|
757bf1df DM |
1 | /* Template classes for directed graphs. |
2 | Copyright (C) 2019-2020 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 */ |