digraph.h

Go to the documentation of this file.

/* Template classes for directed graphs.
   Copyright (C) 2019-2026 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;
 
  void add_in_edge (edge_t *e)
  {
    m_preds.safe_push (e);
  }
  void remove_in_edge (edge_t *e)
  {
    m_preds.unordered_remove (find_edge_idx (m_preds, e));
  }
  void add_out_edge (edge_t *e)
  {
    m_succs.safe_push (e);
  }
  void remove_out_edge (edge_t *e)
  {
    m_succs.unordered_remove (find_edge_idx (m_succs, e));
  }
 
public:
  auto_vec<edge_t *> m_preds;
  auto_vec<edge_t *> m_succs;
 
private:
  static unsigned
  find_edge_idx (auto_vec<edge_t *> &edges, edge_t *e)
  {
    for (unsigned i = 0; i < edges.length (); ++i)
      if (edges[i] == e)
        return i;
    gcc_unreachable ();
  }
};
 
/* 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::edge_t edge_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;
 
  void set_dest (node_t *new_dest)
  {
    node_t *old_dest = m_dest;
    if (new_dest != old_dest)
      {
        old_dest->remove_in_edge (static_cast<edge_t *> (this));
        m_dest = new_dest;
        new_dest->add_in_edge (static_cast<edge_t *> (this));
      }
  }
 
  node_t *m_src;
  node_t *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);
 
  virtual void
  add_any_extra_stmts (graphviz_out &) const
  {
    // no-op hook
  }
 
  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);
 
  add_any_extra_stmts (gv);
 
  /* 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.set_output_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 */