BLI: add library to simplify writing dot graph exporters

See D6799 for some examples on how to use the library.

Reviewers: sergey

Differential Revision: https://developer.blender.org/D6799

4 files changed, 723 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_dot_export.hh b/source/blender/blenlib/BLI_dot_export.hh
new file mode 100644
index 00000000000..08c37fec01e
--- /dev/null
+++ b/source/blender/blenlib/BLI_dot_export.hh
@@ -0,0 +1,290 @@
+/*
+ * This program 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 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program 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 this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __BLI_DOT_EXPORT_HH__
+#define __BLI_DOT_EXPORT_HH__
+
+/**
+ * Language grammar: https://www.graphviz.org/doc/info/lang.html
+ * Attributes: https://www.graphviz.org/doc/info/attrs.html
+ * Node Shapes: https://www.graphviz.org/doc/info/shapes.html
+ * Preview: https://dreampuf.github.io/GraphvizOnline
+ */
+
+#include "BLI_map.hh"
+#include "BLI_optional.hh"
+#include "BLI_set.hh"
+#include "BLI_string_map.hh"
+#include "BLI_utility_mixins.hh"
+#include "BLI_vector.hh"
+
+#include "BLI_dot_export_attribute_enums.hh"
+
+#include <sstream>
+
+namespace BLI {
+namespace DotExport {
+
+class Graph;
+class DirectedGraph;
+class UndirectedGraph;
+class Node;
+class NodePort;
+class DirectedEdge;
+class UndirectedEdge;
+class Cluster;
+class AttributeList;
+
+class AttributeList {
+ private:
+  Map<std::string, std::string> m_attributes;
+
+ public:
+  void export__as_bracket_list(std::stringstream &ss) const;
+
+  void set(StringRef key, StringRef value)
+  {
+    m_attributes.add_override(key, value);
+  }
+};
+
+class Graph {
+ private:
+  AttributeList m_attributes;
+  Vector<std::unique_ptr<Node>> m_nodes;
+  Vector<std::unique_ptr<Cluster>> m_clusters;
+
+  Set<Node *> m_top_level_nodes;
+  Set<Cluster *> m_top_level_clusters;
+
+  friend Cluster;
+  friend Node;
+
+ public:
+  Node &new_node(StringRef label);
+  Cluster &new_cluster(StringRef label = "");
+
+  void export__declare_nodes_and_clusters(std::stringstream &ss) const;
+
+  void set_attribute(StringRef key, StringRef value)
+  {
+    m_attributes.set(key, value);
+  }
+
+  void set_rankdir(Attr_rankdir rankdir)
+  {
+    this->set_attribute("rankdir", rankdir_to_string(rankdir));
+  }
+
+  void set_random_cluster_bgcolors();
+};
+
+class Cluster {
+ private:
+  AttributeList m_attributes;
+  Graph &m_graph;
+  Cluster *m_parent = nullptr;
+  Set<Cluster *> m_children;
+  Set<Node *> m_nodes;
+
+  friend Graph;
+  friend Node;
+
+  Cluster(Graph &graph) : m_graph(graph)
+  {
+  }
+
+ public:
+  void export__declare_nodes_and_clusters(std::stringstream &ss) const;
+
+  void set_attribute(StringRef key, StringRef value)
+  {
+    m_attributes.set(key, value);
+  }
+
+  void set_parent_cluster(Cluster *cluster);
+  void set_parent_cluster(Cluster &cluster)
+  {
+    this->set_parent_cluster(&cluster);
+  }
+
+  void set_random_cluster_bgcolors();
+};
+
+class Node {
+ private:
+  AttributeList m_attributes;
+  Graph &m_graph;
+  Cluster *m_cluster = nullptr;
+
+  friend Graph;
+
+  Node(Graph &graph) : m_graph(graph)
+  {
+  }
+
+ public:
+  const AttributeList &attributes() const
+  {
+    return m_attributes;
+  }
+
+  AttributeList &attributes()
+  {
+    return m_attributes;
+  }
+
+  void set_parent_cluster(Cluster *cluster);
+  void set_parent_cluster(Cluster &cluster)
+  {
+    this->set_parent_cluster(&cluster);
+  }
+
+  void set_attribute(StringRef key, StringRef value)
+  {
+    m_attributes.set(key, value);
+  }
+
+  void set_shape(Attr_shape shape)
+  {
+    this->set_attribute("shape", shape_to_string(shape));
+  }
+
+  /* See https://www.graphviz.org/doc/info/attrs.html#k:color. */
+  void set_background_color(StringRef name)
+  {
+    this->set_attribute("fillcolor", name);
+    this->set_attribute("style", "filled");
+  }
+
+  void export__as_id(std::stringstream &ss) const;
+
+  void export__as_declaration(std::stringstream &ss) const;
+};
+
+class UndirectedGraph final : public Graph {
+ private:
+  Vector<std::unique_ptr<UndirectedEdge>> m_edges;
+
+ public:
+  std::string to_dot_string() const;
+
+  UndirectedEdge &new_edge(NodePort a, NodePort b);
+};
+
+class DirectedGraph final : public Graph {
+ private:
+  Vector<std::unique_ptr<DirectedEdge>> m_edges;
+
+ public:
+  std::string to_dot_string() const;
+
+  DirectedEdge &new_edge(NodePort from, NodePort to);
+};
+
+class NodePort {
+ private:
+  Node *m_node;
+  Optional<std::string> m_port_name;
+
+ public:
+  NodePort(Node &node, Optional<std::string> port_name = {})
+      : m_node(&node), m_port_name(std::move(port_name))
+  {
+  }
+
+  void to_dot_string(std::stringstream &ss) const;
+};
+
+class Edge : BLI::NonCopyable, BLI::NonMovable {
+ protected:
+  AttributeList m_attributes;
+  NodePort m_a;
+  NodePort m_b;
+
+ public:
+  Edge(NodePort a, NodePort b) : m_a(std::move(a)), m_b(std::move(b))
+  {
+  }
+
+  void set_attribute(StringRef key, StringRef value)
+  {
+    m_attributes.set(key, value);
+  }
+
+  void set_arrowhead(Attr_arrowType type)
+  {
+    this->set_attribute("arrowhead", arrowType_to_string(type));
+  }
+
+  void set_arrowtail(Attr_arrowType type)
+  {
+    this->set_attribute("arrowtail", arrowType_to_string(type));
+  }
+
+  void set_dir(Attr_dirType type)
+  {
+    this->set_attribute("dir", dirType_to_string(type));
+  }
+};
+
+class DirectedEdge : public Edge {
+ public:
+  DirectedEdge(NodePort from, NodePort to) : Edge(std::move(from), std::move(to))
+  {
+  }
+
+  void export__as_edge_statement(std::stringstream &ss) const;
+};
+
+class UndirectedEdge : public Edge {
+ public:
+  UndirectedEdge(NodePort a, NodePort b) : Edge(std::move(a), std::move(b))
+  {
+  }
+
+  void export__as_edge_statement(std::stringstream &ss) const;
+};
+
+std::string color_attr_from_hsv(float h, float s, float v);
+
+class NodeWithSocketsRef {
+ private:
+  Node *m_node;
+
+ public:
+  NodeWithSocketsRef(Node &node,
+                     StringRef name,
+                     ArrayRef<std::string> input_names,
+                     ArrayRef<std::string> output_names);
+
+  NodePort input(uint index) const
+  {
+    std::string port = "\"in" + std::to_string(index) + "\"";
+    return NodePort(*m_node, port);
+  }
+
+  NodePort output(uint index) const
+  {
+    std::string port = "\"out" + std::to_string(index) + "\"";
+    return NodePort(*m_node, port);
+  }
+};
+
+}  // namespace DotExport
+}  // namespace BLI
+
+#endif /* __BLI_DOT_EXPORT_HH__ */
diff --git a/source/blender/blenlib/BLI_dot_export_attribute_enums.hh b/source/blender/blenlib/BLI_dot_export_attribute_enums.hh
new file mode 100644
index 00000000000..8e61f46dc12
--- /dev/null
+++ b/source/blender/blenlib/BLI_dot_export_attribute_enums.hh
@@ -0,0 +1,125 @@
+/*
+ * This program 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 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program 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 this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __BLI_DOT_EXPORT_ATTRIBUTE_ENUMS_HH__
+#define __BLI_DOT_EXPORT_ATTRIBUTE_ENUMS_HH__
+
+#include "BLI_string_ref.hh"
+
+namespace BLI {
+namespace DotExport {
+
+enum class Attr_rankdir {
+  LeftToRight,
+  TopToBottom,
+};
+
+inline StringRef rankdir_to_string(Attr_rankdir value)
+{
+  switch (value) {
+    case Attr_rankdir::LeftToRight:
+      return "LR";
+    case Attr_rankdir::TopToBottom:
+      return "TB";
+  }
+  return "";
+}
+
+enum class Attr_shape {
+  Rectangle,
+  Ellipse,
+  Circle,
+  Point,
+  Diamond,
+  Square,
+};
+
+inline StringRef shape_to_string(Attr_shape value)
+{
+  switch (value) {
+    case Attr_shape::Rectangle:
+      return "rectangle";
+    case Attr_shape::Ellipse:
+      return "ellipse";
+    case Attr_shape::Circle:
+      return "circle";
+    case Attr_shape::Point:
+      return "point";
+    case Attr_shape::Diamond:
+      return "diamond";
+    case Attr_shape::Square:
+      return "square";
+  }
+  return "";
+}
+
+enum class Attr_arrowType {
+  Normal,
+  Inv,
+  Dot,
+  None,
+  Empty,
+  Box,
+  Vee,
+};
+
+inline StringRef arrowType_to_string(Attr_arrowType value)
+{
+  switch (value) {
+    case Attr_arrowType::Normal:
+      return "normal";
+    case Attr_arrowType::Inv:
+      return "inv";
+    case Attr_arrowType::Dot:
+      return "dot";
+    case Attr_arrowType::None:
+      return "none";
+    case Attr_arrowType::Empty:
+      return "empty";
+    case Attr_arrowType::Box:
+      return "box";
+    case Attr_arrowType::Vee:
+      return "vee";
+  }
+  return "";
+}
+
+enum class Attr_dirType {
+  Forward,
+  Back,
+  Both,
+  None,
+};
+
+inline StringRef dirType_to_string(Attr_dirType value)
+{
+  switch (value) {
+    case Attr_dirType::Forward:
+      return "forward";
+    case Attr_dirType::Back:
+      return "back";
+    case Attr_dirType::Both:
+      return "both";
+    case Attr_dirType::None:
+      return "none";
+  }
+  return "";
+}
+
+}  // namespace DotExport
+}  // namespace BLI
+
+#endif /* __BLI_DOT_EXPORT_ATTRIBUTE_ENUMS_HH__ */
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 19089447b95..a26d5cc46fb 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -64,6 +64,7 @@ set(SRC
   intern/buffer.c
   intern/convexhull_2d.c
   intern/delaunay_2d.c
+  intern/dot_export.cc
   intern/dynlib.c
   intern/easing.c
   intern/edgehash.c
@@ -161,6 +162,8 @@ set(SRC
   BLI_delaunay_2d.h
   BLI_dial_2d.h
   BLI_dlrbTree.h
+  BLI_dot_export.hh
+  BLI_dot_export_attribute_enums.hh
   BLI_dynlib.h
   BLI_dynstr.h
   BLI_easing.h
diff --git a/source/blender/blenlib/intern/dot_export.cc b/source/blender/blenlib/intern/dot_export.cc
new file mode 100644
index 00000000000..96de4056fc5
--- /dev/null
+++ b/source/blender/blenlib/intern/dot_export.cc
@@ -0,0 +1,305 @@
+/*
+ * This program 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 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program 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 this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include <iomanip>
+
+#include "BLI_dot_export.hh"
+
+namespace BLI {
+namespace DotExport {
+
+/* Graph Building
+ ************************************************/
+
+Node &Graph::new_node(StringRef label)
+{
+  Node *node = new Node(*this);
+  m_nodes.append(std::unique_ptr<Node>(node));
+  m_top_level_nodes.add_new(node);
+  node->set_attribute("label", label);
+  return *node;
+}
+
+Cluster &Graph::new_cluster(StringRef label)
+{
+  Cluster *cluster = new Cluster(*this);
+  m_clusters.append(std::unique_ptr<Cluster>(cluster));
+  m_top_level_clusters.add_new(cluster);
+  cluster->set_attribute("label", label);
+  return *cluster;
+}
+
+UndirectedEdge &UndirectedGraph::new_edge(NodePort a, NodePort b)
+{
+  UndirectedEdge *edge = new UndirectedEdge(a, b);
+  m_edges.append(std::unique_ptr<UndirectedEdge>(edge));
+  return *edge;
+}
+
+DirectedEdge &DirectedGraph::new_edge(NodePort from, NodePort to)
+{
+  DirectedEdge *edge = new DirectedEdge(from, to);
+  m_edges.append(std::unique_ptr<DirectedEdge>(edge));
+  return *edge;
+}
+
+void Cluster::set_parent_cluster(Cluster *new_parent)
+{
+  if (m_parent == new_parent) {
+    return;
+  }
+  else if (m_parent == nullptr) {
+    m_graph.m_top_level_clusters.remove(this);
+    new_parent->m_children.add_new(this);
+  }
+  else if (new_parent == nullptr) {
+    m_parent->m_children.remove(this);
+    m_graph.m_top_level_clusters.add_new(this);
+  }
+  else {
+    m_parent->m_children.remove(this);
+    new_parent->m_children.add_new(this);
+  }
+  m_parent = new_parent;
+}
+
+void Node::set_parent_cluster(Cluster *cluster)
+{
+  if (m_cluster == cluster) {
+    return;
+  }
+  else if (m_cluster == nullptr) {
+    m_graph.m_top_level_nodes.remove(this);
+    cluster->m_nodes.add_new(this);
+  }
+  else if (cluster == nullptr) {
+    m_cluster->m_nodes.remove(this);
+    m_graph.m_top_level_nodes.add_new(this);
+  }
+  else {
+    m_cluster->m_nodes.remove(this);
+    cluster->m_nodes.add_new(this);
+  }
+  m_cluster = cluster;
+}
+
+/* Utility methods
+ **********************************************/
+
+void Graph::set_random_cluster_bgcolors()
+{
+  for (Cluster *cluster : m_top_level_clusters) {
+    cluster->set_random_cluster_bgcolors();
+  }
+}
+
+void Cluster::set_random_cluster_bgcolors()
+{
+  float hue = rand() / (float)RAND_MAX;
+  float staturation = 0.3f;
+  float value = 0.8f;
+  this->set_attribute("bgcolor", color_attr_from_hsv(hue, staturation, value));
+
+  for (Cluster *cluster : m_children) {
+    cluster->set_random_cluster_bgcolors();
+  }
+}
+
+/* Dot Generation
+ **********************************************/
+
+std::string DirectedGraph::to_dot_string() const
+{
+  std::stringstream ss;
+  ss << "digraph {\n";
+  this->export__declare_nodes_and_clusters(ss);
+  ss << "\n";
+
+  for (const std::unique_ptr<DirectedEdge> &edge : m_edges) {
+    edge->export__as_edge_statement(ss);
+    ss << "\n";
+  }
+
+  ss << "}\n";
+  return ss.str();
+}
+
+std::string UndirectedGraph::to_dot_string() const
+{
+  std::stringstream ss;
+  ss << "graph {\n";
+  this->export__declare_nodes_and_clusters(ss);
+  ss << "\n";
+
+  for (const std::unique_ptr<UndirectedEdge> &edge : m_edges) {
+    edge->export__as_edge_statement(ss);
+    ss << "\n";
+  }
+
+  ss << "}\n";
+  return ss.str();
+}
+
+void Graph::export__declare_nodes_and_clusters(std::stringstream &ss) const
+{
+  ss << "graph ";
+  m_attributes.export__as_bracket_list(ss);
+  ss << "\n\n";
+
+  for (Node *node : m_top_level_nodes) {
+    node->export__as_declaration(ss);
+  }
+
+  for (Cluster *cluster : m_top_level_clusters) {
+    cluster->export__declare_nodes_and_clusters(ss);
+  }
+}
+
+void Cluster::export__declare_nodes_and_clusters(std::stringstream &ss) const
+{
+  ss << "subgraph cluster_" << (uintptr_t)this << " {\n";
+
+  ss << "graph ";
+  m_attributes.export__as_bracket_list(ss);
+  ss << "\n\n";
+
+  for (Node *node : m_nodes) {
+    node->export__as_declaration(ss);
+  }
+
+  for (Cluster *cluster : m_children) {
+    cluster->export__declare_nodes_and_clusters(ss);
+  }
+
+  ss << "}\n";
+}
+
+void DirectedEdge::export__as_edge_statement(std::stringstream &ss) const
+{
+  m_a.to_dot_string(ss);
+  ss << " -> ";
+  m_b.to_dot_string(ss);
+  ss << " ";
+  m_attributes.export__as_bracket_list(ss);
+}
+
+void UndirectedEdge::export__as_edge_statement(std::stringstream &ss) const
+{
+  m_a.to_dot_string(ss);
+  ss << " -- ";
+  m_b.to_dot_string(ss);
+  ss << " ";
+  m_attributes.export__as_bracket_list(ss);
+}
+
+void AttributeList::export__as_bracket_list(std::stringstream &ss) const
+{
+  ss << "[";
+  m_attributes.foreach_item([&](StringRef key, StringRef value) {
+    if (StringRef(value).startswith("<")) {
+      /* Don't draw the quotes, this is an html-like value. */
+      ss << key << "=" << value << ", ";
+    }
+    else {
+      ss << key << "=\"" << value << "\", ";
+    }
+  });
+  ss << "]";
+}
+
+void Node::export__as_id(std::stringstream &ss) const
+{
+  ss << '"' << (uintptr_t)this << '"';
+}
+
+void Node::export__as_declaration(std::stringstream &ss) const
+{
+  this->export__as_id(ss);
+  ss << " ";
+  m_attributes.export__as_bracket_list(ss);
+  ss << "\n";
+}
+
+void NodePort::to_dot_string(std::stringstream &ss) const
+{
+  m_node->export__as_id(ss);
+  if (m_port_name.has_value()) {
+    ss << ":" << m_port_name.value();
+  }
+}
+
+std::string color_attr_from_hsv(float h, float s, float v)
+{
+  std::stringstream ss;
+  ss << std::setprecision(4) << h << ' ' << s << ' ' << v;
+  return ss.str();
+}
+
+NodeWithSocketsRef::NodeWithSocketsRef(Node &node,
+                                       StringRef name,
+                                       ArrayRef<std::string> input_names,
+                                       ArrayRef<std::string> output_names)
+    : m_node(&node)
+{
+  std::stringstream ss;
+
+  ss << "<<table border=\"0\" cellspacing=\"3\">";
+
+  /* Header */
+  ss << "<tr><td colspan=\"3\" align=\"center\"><b>";
+  ss << ((name.size() == 0) ? "No Name" : name);
+  ss << "</b></td></tr>";
+
+  /* Sockets */
+  uint socket_max_amount = std::max(input_names.size(), output_names.size());
+  for (uint i = 0; i < socket_max_amount; i++) {
+    ss << "<tr>";
+    if (i < input_names.size()) {
+      StringRef name = input_names[i];
+      if (name.size() == 0) {
+        name = "No Name";
+      }
+      ss << "<td align=\"left\" port=\"in" << i << "\">";
+      ss << name;
+      ss << "</td>";
+    }
+    else {
+      ss << "<td></td>";
+    }
+    ss << "<td></td>";
+    if (i < output_names.size()) {
+      StringRef name = output_names[i];
+      if (name.size() == 0) {
+        name = "No Name";
+      }
+      ss << "<td align=\"right\" port=\"out" << i << "\">";
+      ss << name;
+      ss << "</td>";
+    }
+    else {
+      ss << "<td></td>";
+    }
+    ss << "</tr>";
+  }
+
+  ss << "</table>>";
+
+  m_node->set_attribute("label", ss.str());
+  m_node->set_shape(Attr_shape::Rectangle);
+}
+
+}  // namespace DotExport
+}  // namespace BLI