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