1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
|
/* Template classes for directed graphs.
Copyright (C) 2019-2020 Free Software Foundation, Inc.
Contributed by David Malcolm <dmalcolm@redhat.com>.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#ifndef GCC_DIGRAPH_H
#define GCC_DIGRAPH_H
#include "diagnostic.h"
#include "tree-diagnostic.h" /* for default_tree_printer. */
#include "graphviz.h"
/* Templates for a family of classes: digraph, node, edge, and cluster.
This assumes a traits type with the following typedefs:
node_t: the node class
edge_t: the edge class
dump_args_t: additional args for dot-dumps
cluster_t: the cluster class (for use when generating .dot files).
Using a template allows for typesafe nodes and edges: a node's
predecessor and successor edges can be of a node-specific edge
subclass, without needing casting. */
/* Abstract base class for a node in a directed graph. */
template <typename GraphTraits>
class dnode
{
public:
typedef typename GraphTraits::edge_t edge_t;
typedef typename GraphTraits::dump_args_t dump_args_t;
virtual ~dnode () {}
virtual void dump_dot (graphviz_out *gv, const dump_args_t &args) const = 0;
auto_vec<edge_t *> m_preds;
auto_vec<edge_t *> m_succs;
};
/* Abstract base class for an edge in a directed graph. */
template <typename GraphTraits>
class dedge
{
public:
typedef typename GraphTraits::node_t node_t;
typedef typename GraphTraits::dump_args_t dump_args_t;
dedge (node_t *src, node_t *dest)
: m_src (src), m_dest (dest) {}
virtual ~dedge () {}
virtual void dump_dot (graphviz_out *gv, const dump_args_t &args) const = 0;
node_t *const m_src;
node_t *const m_dest;
};
/* Abstract base class for a directed graph.
This class maintains the vectors of nodes and edges,
and owns the nodes and edges. */
template <typename GraphTraits>
class digraph
{
public:
typedef typename GraphTraits::node_t node_t;
typedef typename GraphTraits::edge_t edge_t;
typedef typename GraphTraits::dump_args_t dump_args_t;
typedef typename GraphTraits::cluster_t cluster_t;
digraph () {}
virtual ~digraph () {}
void dump_dot_to_pp (pretty_printer *pp,
cluster_t *root_cluster,
const dump_args_t &args) const;
void dump_dot_to_file (FILE *fp,
cluster_t *root_cluster,
const dump_args_t &args) const;
void dump_dot (const char *path,
cluster_t *root_cluster,
const dump_args_t &args) const;
void add_node (node_t *node);
void add_edge (edge_t *edge);
auto_delete_vec<node_t> m_nodes;
auto_delete_vec<edge_t> m_edges;
};
/* Abstract base class for splitting dnodes into hierarchical clusters
in the generated .dot file.
See "Subgraphs and Clusters" within
https://www.graphviz.org/doc/info/lang.html
and e.g.
https://graphviz.gitlab.io/_pages/Gallery/directed/cluster.html
If a root_cluster is passed to dump_dot*, then all nodes will be
added to it at the start of dumping, via calls to add_node.
The root cluster can organize the nodes into a hierarchy of
child clusters.
After all nodes are added to the root cluster, dump_dot will then
be called on it (and not on the nodes themselves). */
template <typename GraphTraits>
class cluster
{
public:
typedef typename GraphTraits::node_t node_t;
typedef typename GraphTraits::dump_args_t dump_args_t;
virtual ~cluster () {}
virtual void add_node (node_t *node) = 0;
/* Recursively dump the cluster, all nodes, and child clusters. */
virtual void dump_dot (graphviz_out *gv, const dump_args_t &) const = 0;
};
/* Write .dot information for this graph to PP, passing ARGS to the nodes
and edges.
If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters. */
template <typename GraphTraits>
inline void
digraph<GraphTraits>::dump_dot_to_pp (pretty_printer *pp,
cluster_t *root_cluster,
const dump_args_t &args) const
{
graphviz_out gv (pp);
pp_string (pp, "digraph \"");
pp_string (pp, "base");
pp_string (pp, "\" {\n");
gv.indent ();
pp_string (pp, "overlap=false;\n");
pp_string (pp, "compound=true;\n");
/* If using clustering, emit all nodes via clusters. */
if (root_cluster)
{
int i;
node_t *n;
FOR_EACH_VEC_ELT (m_nodes, i, n)
root_cluster->add_node (n);
root_cluster->dump_dot (&gv, args);
}
else
{
/* Otherwise, display all nodes at top level. */
int i;
node_t *n;
FOR_EACH_VEC_ELT (m_nodes, i, n)
n->dump_dot (&gv, args);
}
/* Edges. */
int i;
edge_t *e;
FOR_EACH_VEC_ELT (m_edges, i, e)
e->dump_dot (&gv, args);
/* Terminate "digraph" */
gv.outdent ();
pp_string (pp, "}");
pp_newline (pp);
}
/* Write .dot information for this graph to FP, passing ARGS to the nodes
and edges.
If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters. */
template <typename GraphTraits>
inline void
digraph<GraphTraits>::dump_dot_to_file (FILE *fp,
cluster_t *root_cluster,
const dump_args_t &args) const
{
pretty_printer pp;
// TODO:
pp_format_decoder (&pp) = default_tree_printer;
pp.buffer->stream = fp;
dump_dot_to_pp (&pp, root_cluster, args);
pp_flush (&pp);
}
/* Write .dot information for this graph to a file at PATH, passing ARGS
to the nodes and edges.
If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters. */
template <typename GraphTraits>
inline void
digraph<GraphTraits>::dump_dot (const char *path,
cluster_t *root_cluster,
const dump_args_t &args) const
{
FILE *fp = fopen (path, "w");
dump_dot_to_file (fp, root_cluster, args);
fclose (fp);
}
/* Add NODE to this DIGRAPH, taking ownership. */
template <typename GraphTraits>
inline void
digraph<GraphTraits>::add_node (node_t *node)
{
m_nodes.safe_push (node);
}
/* Add EDGE to this digraph, and to the preds/succs of its endpoints.
Take ownership of EDGE. */
template <typename GraphTraits>
inline void
digraph<GraphTraits>::add_edge (edge_t *edge)
{
m_edges.safe_push (edge);
edge->m_dest->m_preds.safe_push (edge);
edge->m_src->m_succs.safe_push (edge);
}
#endif /* GCC_DIGRAPH_H */
|
