|
145
|
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 */
|
