gcc/digraph.h

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