/* Template classes for directed graphs. Copyright (C) 2019-2020 Free Software Foundation, Inc. Contributed by David Malcolm . 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 . */ #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 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 m_preds; auto_vec m_succs; }; /* Abstract base class for an edge in a directed graph. */ template 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 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 m_nodes; auto_delete_vec 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 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 inline void digraph::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 inline void digraph::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 inline void digraph::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 inline void digraph::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 inline void digraph::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 */