GraphWriter.hpp

Go to the documentation of this file.

/*
 * Copyright 2024 Håvard Krogstie <krogstie.havard@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_UTIL_GRAPHWRITER_HPP
#define JLM_UTIL_GRAPHWRITER_HPP
 
#include <jlm/util/common.hpp>
 
#include <cstdint>
#include <memory>
#include <optional>
#include <unordered_map>
#include <variant>
#include <vector>
 
namespace jlm::util::graph
{
 
enum class OutputFormat
{
  Dot,   // prints
  ASCII, // output format that makes edges implicit when possible
};
 
enum class AttributeOutputFormat
{
  SpaceSeparatedList, // printed on the form attr=value other="value 2"
  HTMLAttributes      // adds extra restrictions on attribute names
};
 
class Writer;
class Node;
class Edge;
class Port;
class Graph;
 
class GraphElement
{
public:
  virtual ~GraphElement() = default;
 
  GraphElement();
 
  GraphElement(const GraphElement & other) = delete;
 
  GraphElement(GraphElement && other) = delete;
 
  GraphElement &
  operator=(const GraphElement & other) = delete;
 
  GraphElement &
  operator=(GraphElement && other) = delete;
 
  [[nodiscard]] virtual const char *
  GetIdPrefix() const = 0;
 
  [[nodiscard]] std::string
  GetFullId() const;
 
  [[nodiscard]] virtual Graph &
  GetGraph() = 0;
 
  [[nodiscard]] const Graph &
  GetGraph() const;
 
  void
  SetLabel(std::string label);
 
  void
  AppendToLabel(std::string_view text, std::string_view sep = "\n");
 
  [[nodiscard]] bool
  HasLabel() const;
 
  [[nodiscard]] const std::string &
  GetLabel() const;
 
  [[nodiscard]] std::string_view
  GetLabelOr(std::string_view otherwise) const;
 
  [[nodiscard]] size_t
  GetUniqueIdSuffix() const;
 
  template<typename T>
  void
  SetProgramObject(const T & object)
  {
    SetProgramObjectUintptr(reinterpret_cast<uintptr_t>(&object));
  }
 
  void
  RemoveProgramObject();
 
  [[nodiscard]] bool
  HasProgramObject() const noexcept;
 
  [[nodiscard]] uintptr_t
  GetProgramObject() const noexcept;
 
  void
  SetAttribute(const std::string & attribute, std::string value);
 
  void
  SetAttributeObject(const std::string & attribute, uintptr_t object);
 
  template<typename T>
  void
  SetAttributeObject(const std::string & attribute, const T & object)
  {
    SetAttributeObject(attribute, reinterpret_cast<uintptr_t>(&object));
  }
 
  void
  SetAttributeGraphElement(const std::string & attribute, const GraphElement & element);
 
  [[nodiscard]] bool
  HasAttribute(const std::string & attribute) const;
 
  [[nodiscard]] std::optional<std::string_view>
  GetAttributeString(const std::string & attribute) const;
 
  [[nodiscard]] std::optional<uintptr_t>
  GetAttributeObject(const std::string & attribute) const;
 
  [[nodiscard]] const GraphElement *
  GetAttributeGraphElement(const std::string & attribute) const;
 
  bool
  RemoveAttribute(const std::string & attribute);
 
  virtual void
  Finalize();
 
  [[nodiscard]] bool
  IsFinalized() const;
 
  void
  OutputAttributes(std::ostream & out, AttributeOutputFormat format) const;
 
private:
  void
  SetProgramObjectUintptr(uintptr_t object);
 
  // A human-readable piece of text that should be rendered with the element
  std::string Label_;
 
  // A number added to the end of the id stub to make it globally unique
  std::optional<size_t> UniqueIdSuffix_;
 
  // The object in the program this graph object corresponds to, or 0 if none
  uintptr_t ProgramObject_;
 
  // Arbitrary collection of other attributes. The value can be a string, a reference to a
  // GraphElement, or a reference to a program object.
  using AttributeValue = std::variant<std::string, const GraphElement *, uintptr_t>;
  std::unordered_map<std::string, AttributeValue> AttributeMap_;
};
 
class Port : public GraphElement
{
  friend Edge;
 
protected:
  Port();
 
public:
  ~Port() override = default;
 
  virtual Node &
  GetNode() = 0;
 
  Graph &
  GetGraph() override;
 
  [[nodiscard]] virtual bool
  CanBeEdgeHead() const;
 
  [[nodiscard]] virtual bool
  CanBeEdgeTail() const;
 
  [[nodiscard]] const std::vector<Edge *> &
  GetConnections() const;
 
  [[nodiscard]] bool
  HasOutgoingEdges() const;
 
  [[nodiscard]] bool
  HasIncomingEdges() const;
 
  virtual void
  SetFillColor(std::string color) = 0;
 
  virtual void
  OutputDotPortId(std::ostream & out) const = 0;
 
  void
  OutputIncomingEdgesASCII(std::ostream & out) const;
 
private:
  void
  OnEdgeAdded(Edge & edge);
 
  std::vector<Edge *> Connections_;
};
 
class Node : public Port
{
  friend Graph;
 
protected:
  explicit Node(Graph & graph);
 
public:
  ~Node() override = default;
 
  const char *
  GetIdPrefix() const override;
 
  Node &
  GetNode() override;
 
  Graph &
  GetGraph() override;
 
  virtual void
  SetShape(std::string shape);
 
  struct Shape
  {
    static inline const char * const Rectangle = "rect";
    static inline const char * const Circle = "circle";
    static inline const char * const Oval = "oval";
    static inline const char * const Point = "point";
    static inline const char * const Plain = "plain";
    static inline const char * const Plaintext = "plaintext";
    static inline const char * const Triangle = "triangle";
    static inline const char * const DoubleCircle = "doublecircle";
  };
 
  void
  SetFillColor(std::string color) override;
 
  void
  OutputDotPortId(std::ostream & out) const override;
 
  void
  Output(std::ostream & out, OutputFormat format, size_t indent) const;
 
  virtual void
  OutputSubgraphs(std::ostream & out, OutputFormat format, size_t indent) const;
 
protected:
  virtual void
  OutputASCII(std::ostream & out, size_t indent) const;
 
  virtual void
  OutputDot(std::ostream & out, size_t indent) const;
 
private:
  Graph & Graph_;
};
 
class InOutNode;
class InputPort;
class OutputPort;
 
class InputPort final : public Port
{
  friend InOutNode;
 
  explicit InputPort(InOutNode & node);
 
public:
  ~InputPort() override = default;
 
  const char *
  GetIdPrefix() const override;
 
  Node &
  GetNode() override;
 
  bool
  CanBeEdgeTail() const override;
 
  void
  SetFillColor(std::string color) override;
 
  void
  OutputDotPortId(std::ostream & out) const override;
 
private:
  InOutNode & Node_;
};
 
class OutputPort final : public Port
{
  friend InOutNode;
 
  explicit OutputPort(InOutNode & node);
 
public:
  ~OutputPort() override = default;
 
  const char *
  GetIdPrefix() const override;
 
  Node &
  GetNode() override;
 
  bool
  CanBeEdgeHead() const override;
 
  void
  SetFillColor(std::string color) override;
 
  void
  OutputDotPortId(std::ostream & out) const override;
 
private:
  InOutNode & Node_;
};
 
class InOutNode final : public Node
{
  friend Graph;
 
  InOutNode(Graph & graph, size_t inputPorts, size_t outputPorts);
 
public:
  ~InOutNode() override = default;
 
  void SetShape(std::string) override;
 
  InputPort &
  CreateInputPort();
 
  size_t
  NumInputPorts() const;
 
  InputPort &
  GetInputPort(size_t index);
 
  OutputPort &
  CreateOutputPort();
 
  size_t
  NumOutputPorts() const;
 
  OutputPort &
  GetOutputPort(size_t index);
 
  Graph &
  CreateSubgraph();
 
  size_t
  NumSubgraphs() const;
 
  Graph &
  GetSubgraph(size_t index);
 
  void
  SetHtmlTableAttribute(std::string name, std::string value);
 
  void
  SetFillColor(std::string color) override;
 
  void
  Finalize() override;
 
  void
  OutputSubgraphs(std::ostream & out, OutputFormat format, size_t indent) const override;
 
protected:
  void
  OutputASCII(std::ostream & out, size_t indent) const override;
 
  void
  OutputDot(std::ostream & out, size_t indent) const override;
 
private:
  // Attributes that need to be placed on the HTML table in the dot output, and not on the node.
  std::unordered_map<std::string, std::string> HtmlTableAttributes_;
 
  std::vector<std::unique_ptr<InputPort>> InputPorts_;
  std::vector<std::unique_ptr<OutputPort>> OutputPorts_;
  std::vector<Graph *> SubGraphs_;
};
 
class ArgumentNode : public Node
{
  friend Graph;
 
  explicit ArgumentNode(Graph & graph);
 
public:
  ~ArgumentNode() override = default;
 
  const char *
  GetIdPrefix() const override;
 
  bool
  CanBeEdgeHead() const override;
 
  void
  SetOutsideSource(const Port & outsideSource);
 
protected:
  void
  OutputASCII(std::ostream & out, size_t indent) const override;
 
private:
  // Optional reference to a Port outside of this graph from which this argument came
  const Port * OutsideSource_;
};
 
class ResultNode : public Node
{
  friend Graph;
 
  explicit ResultNode(Graph & graph);
 
public:
  ~ResultNode() override = default;
 
  const char *
  GetIdPrefix() const override;
 
  bool
  CanBeEdgeTail() const override;
 
  void
  SetOutsideDestination(const Port & outsideSource);
 
protected:
  void
  OutputASCII(std::ostream & out, size_t indent) const override;
 
private:
  // Optional reference to a Port outside of this graph representing where the result ends up
  const Port * OutsideDestination_;
};
 
class Edge : public GraphElement
{
  friend Graph;
 
  Edge(Port & from, Port & to, bool directed);
 
public:
  ~Edge() override = default;
 
  const char *
  GetIdPrefix() const override;
 
  Graph &
  GetGraph() override;
 
  [[nodiscard]] Port &
  GetFrom();
 
  [[nodiscard]] Port &
  GetTo();
 
  [[nodiscard]] bool
  IsDirected() const;
 
  [[nodiscard]] Port &
  GetOtherEnd(const Port & end);
 
  void
  SetStyle(std::string style);
 
  struct Style
  {
    static inline const char * const Solid = "solid";
    static inline const char * const Dashed = "dashed";
    static inline const char * const Dotted = "dotted";
    static inline const char * const Invisible = "invis";
    static inline const char * const Bold = "bold";
    static inline const char * const Tapered = "tapered";
  };
 
  void
  SetArrowHead(std::string arrow);
 
  void
  SetArrowTail(std::string arrow);
 
  void
  OutputDot(std::ostream & out, size_t indent) const;
 
private:
  Port & From_;
  Port & To_;
  bool Directed_;
};
 
class Graph : public GraphElement
{
  friend Writer;
  friend GraphElement;
 
  explicit Graph(Writer & writer);
 
  Graph(Writer & writer, Node & parentNode);
 
public:
  ~Graph() override = default;
 
  const char *
  GetIdPrefix() const override;
 
  Graph &
  GetGraph() override;
 
  [[nodiscard]] Writer &
  GetWriter();
 
  [[nodiscard]] const Writer &
  GetWriter() const;
 
  [[nodiscard]] bool
  IsSubgraph() const;
 
  [[nodiscard]] Node &
  CreateNode();
 
  [[nodiscard]] InOutNode &
  CreateInOutNode(size_t inputPorts, size_t outputPorts);
 
  [[nodiscard]] size_t
  NumNodes() const noexcept;
 
  [[nodiscard]] Node &
  GetNode(size_t index);
 
  [[nodiscard]] ArgumentNode &
  CreateArgumentNode();
 
  [[nodiscard]] size_t
  NumArgumentNodes() const noexcept;
 
  [[nodiscard]] Node &
  GetArgumentNode(size_t index);
 
  [[nodiscard]] ResultNode &
  CreateResultNode();
 
  [[nodiscard]] size_t
  NumResultNodes() const noexcept;
 
  [[nodiscard]] Node &
  GetResultNode(size_t index);
 
  Edge &
  CreateEdge(Port & from, Port & to, bool directed);
 
  Edge &
  CreateDirectedEdge(Port & from, Port & to)
  {
    return CreateEdge(from, to, true);
  }
 
  Edge &
  CreateUndirectedEdge(Port & a, Port & b)
  {
    return CreateEdge(a, b, false);
  }
 
  [[nodiscard]] size_t
  NumEdges() const noexcept;
 
  [[nodiscard]] Edge &
  GetEdge(size_t index);
 
  [[nodiscard]] Edge *
  GetEdgeBetween(Port & a, Port & b);
 
  [[nodiscard]] GraphElement *
  GetElementFromProgramObject(uintptr_t object) const;
 
  template<typename T>
  [[nodiscard]] GraphElement *
  GetElementFromProgramObject(const T & object) const
  {
    // Check that object is not a reference to a pointer.
    // If the user truly wants to use the address of a pointer, they can cast it to uintptr_t.
    static_assert(!std::is_pointer_v<T>);
    return GetElementFromProgramObject(reinterpret_cast<uintptr_t>(&object));
  }
 
  template<typename Element, typename ProgramObject>
  Element &
  GetFromProgramObject(const ProgramObject & object) const
  {
    static_assert(std::is_base_of_v<GraphElement, Element>);
    GraphElement * element = GetElementFromProgramObject(object);
    auto result = dynamic_cast<Element *>(element);
    JLM_ASSERT(result);
    return *result;
  }
 
  void
  Finalize() override;
 
  void
  Output(std::ostream & out, OutputFormat format, size_t indent = 0) const;
 
private:
  void
  OutputASCII(std::ostream & out, size_t indent) const;
 
  void
  OutputDot(std::ostream & out, size_t indent) const;
 
  void
  MapProgramObjectToElement(GraphElement & element);
 
  void
  RemoveProgramObjectMapping(uintptr_t object);
 
  // The GraphWriter this graph was created by, and belongs to
  Writer & Writer_;
 
  // If this graph is a subgraph, this is its parent node in the parent graph.
  // For top level graphs, this field is nullptr
  Node * ParentNode_;
 
  // The set of nodes in the graph. Finalizing the graph may re-order this list.
  std::vector<std::unique_ptr<Node>> Nodes_;
 
  // Argument nodes and result nodes are kept in separate lists
  std::vector<std::unique_ptr<ArgumentNode>> ArgumentNodes_;
  std::vector<std::unique_ptr<ResultNode>> ResultNodes_;
 
  std::vector<std::unique_ptr<Edge>> Edges_;
 
  // A mapping from pointers to program objects, to the GraphElement representing the program object
  std::unordered_map<uintptr_t, GraphElement *> ProgramObjectMapping_;
};
 
class Writer
{
public:
  ~Writer() = default;
 
  Writer() = default;
 
  Writer(const Writer & other) = delete;
 
  Writer(Writer && other) = delete;
 
  Writer &
  operator=(const Writer & other) = delete;
 
  Writer &
  operator=(Writer && other) = delete;
 
  [[nodiscard]] Graph &
  CreateGraph();
 
  [[nodiscard]] size_t
  NumGraphs() const noexcept;
 
  [[nodiscard]] Graph &
  GetGraph(size_t index);
 
  [[nodiscard]] GraphElement *
  GetElementFromProgramObject(uintptr_t object) const;
 
  template<typename T>
  [[nodiscard]] GraphElement *
  GetElementFromProgramObject(const T & object) const
  {
    // Check that object is not a reference to a pointer.
    // If the user truly wants to use the address of a pointer, they can cast it to uintptr_t.
    static_assert(!std::is_pointer_v<T>);
    return GetElementFromProgramObject(reinterpret_cast<uintptr_t>(&object));
  }
 
  void
  Finalize();
 
  void
  outputAllGraphs(std::ostream & out, OutputFormat format);
 
private:
  [[nodiscard]] Graph &
  CreateSubGraph(Node & parentNode);
 
  friend Graph &
  InOutNode::CreateSubgraph();
 
  [[nodiscard]] size_t
  GetNextUniqueIdStubSuffix(const char * idStub);
 
  friend void
  GraphElement::Finalize();
 
  // All graphs being worked on by the GraphWriter
  // Edges can not go across graphs.
  // IDs are however unique across graphs allowing semantic connections.
  std::vector<std::unique_ptr<Graph>> Graphs_;
 
  // Tracks the next integer to be used when assigning a unique suffix to a given id stub
  std::unordered_map<std::string, size_t> NextUniqueIdStubSuffix_;
};
 
namespace Colors
{
inline const char * const Black = "#000000";
inline const char * const Blue = "#0000FF";
inline const char * const Coral = "#FF7F50";
inline const char * const CornflowerBlue = "#6495ED";
inline const char * const Firebrick = " #B22222";
inline const char * const Gold = "#FFD700";
inline const char * const Gray = "#BEBEBE";
inline const char * const Green = "#00FF00";
inline const char * const Orange = "#FFA500";
inline const char * const Purple = "#A020F0";
inline const char * const Red = "#FF0000";
inline const char * const Brown = "#8B4513"; // X11's Saddle Brown
inline const char * const SkyBlue = "#87CEEB";
inline const char * const White = "#FFFFFF";
inline const char * const Yellow = "#FFFF00";
}
 
}
#endif // JLM_UTIL_GRAPHWRITER_HPP