add: added projectsHEADmain

1 files changed, 213 insertions, 0 deletions

diff --git a/tiger-compiler/lib/misc/graph.hh b/tiger-compiler/lib/misc/graph.hh
new file mode 100644
index 0000000..c21aa99
--- /dev/null
+++ b/tiger-compiler/lib/misc/graph.hh
@@ -0,0 +1,213 @@
+/**
+ ** \file misc/graph.hh
+ ** \brief Undirected/oriented graph definition.
+ */
+
+#pragma once
+
+#include <iosfwd>
+#include <set>
+#include <string>
+#include <vector>
+
+#include <boost/functional/hash.hpp> // Required by boost/graph/detail/edge.hpp.
+/* Forward declarations to help the compiler not to mix up the
+   namespace `target' with `boost::target'.  This happens in the
+   instantiation of graph concepts in boost/graph/graph_concepts.hpp
+   if this forward declaration is omitted.  */
+#include <boost/graph/detail/edge.hpp>
+
+namespace boost
+{
+  template <class OutEdgeListS,
+            class VertexListS,
+            class DirectedS,
+            class VertexProperty,
+            class EdgeProperty,
+            class GraphProperty,
+            class EdgeListS>
+  class adjacency_list;
+
+  template <class Directed,
+            class Vertex,
+            class OutEdgeListS,
+            class VertexListS,
+            class DirectedS,
+            class VertexProperty,
+            class EdgeProperty,
+            class GraphProperty,
+            class EdgeListS>
+  inline Vertex target(const detail::edge_base<Directed, Vertex>& e,
+                       const adjacency_list<OutEdgeListS,
+                                            VertexListS,
+                                            DirectedS,
+                                            VertexProperty,
+                                            EdgeProperty,
+                                            GraphProperty,
+                                            EdgeListS>&);
+
+} // namespace boost
+
+#include <boost/graph/adjacency_list.hpp>
+
+#include <misc/set.hh>
+
+/// Handling of generic, oriented or undirected, graph.
+namespace misc
+{
+  /*--------.
+  | Graph.  |
+  `--------*/
+
+  /// Graph property: name.
+  using name_prop_type = boost::property<boost::graph_name_t, std::string>;
+
+  template <typename Orientation, typename VertexLabel, typename EdgeLabel>
+  class graph
+    : public boost::adjacency_list<boost::setS,
+                                   boost::vecS,
+                                   Orientation,
+                                   VertexLabel,
+                                   EdgeLabel,
+                                   name_prop_type>
+  {
+  public:
+    virtual ~graph() = default;
+
+  public:
+    using self_type = graph<Orientation, VertexLabel, EdgeLabel>;
+    using super_type = boost::adjacency_list<boost::setS,
+                                             boost::vecS,
+                                             Orientation,
+                                             VertexLabel,
+                                             EdgeLabel,
+                                             name_prop_type>;
+    using vertex_descriptor = typename super_type::vertex_descriptor;
+
+    /// Iterators.
+  public:
+    /// \{
+    /// Iterator on the vertices of a graph.
+    using vertex_iter_type =
+      typename boost::graph_traits<self_type>::vertex_iterator;
+    /// Iterator on the edges of a graph.
+    using edge_iter_type =
+      typename boost::graph_traits<self_type>::edge_iterator;
+    /// \}
+
+    /// Graph manipulation.
+    /// \{
+  public:
+    /// \brief Add a vertex to the graph.
+    ///
+    /// Just a wrapper around boost::add_vertex.
+    vertex_descriptor vertex_add(const VertexLabel& l);
+    /// Add an edge between two vertices.
+    virtual void edge_add(const vertex_descriptor& v1,
+                          const vertex_descriptor& v2) = 0;
+    /// \}
+
+    /// Graph pretty printing.
+    /// \{
+  public:
+    virtual std::ostream& print(std::ostream& ostr) const;
+    virtual std::ostream& epilogue_print(std::ostream& ostr) const;
+    virtual void print(std::string file) const;
+
+  private:
+    /// Print the label of vertex of a graph.
+    virtual std::ostream& vertex_print(vertex_descriptor v,
+                                       std::ostream& ostr) const = 0;
+    /// \}
+
+    /// Graph name.
+    /// \{
+  public:
+    const std::string& name_get() const;
+    void name_set(const std::string& name);
+    /// \}
+  };
+
+  template <typename Orientation, typename VertexLabel, typename EdgeLabel>
+  std::ostream& operator<<(std::ostream& ostr,
+                           const graph<Orientation, VertexLabel, EdgeLabel>& g);
+
+  // An helper class when we do not want any data attached to vertex
+  // or an edge.
+  struct empty
+  {};
+  inline std::ostream& operator<<(std::ostream& ostr, empty);
+
+  /*----------------------------------------------------.
+  | Specialization for directed (bidirectional) graph.  |
+  `----------------------------------------------------*/
+
+  /* Note that boost::bidirectionalS is like boost::directedS, except
+     that it provides access to both in-edges and out-edges, whereas
+     boost::directedS gives us only out-edges.  The consequence is
+     that a bidirectional graph is twice as large as its directed
+     version.  */
+  template <typename VertexLabel = empty, typename EdgeLabel = empty>
+  class directed_graph
+    : public graph<boost::bidirectionalS, VertexLabel, EdgeLabel>
+  {
+  public:
+    using self_type = directed_graph<VertexLabel, EdgeLabel>;
+    using super_type = graph<boost::bidirectionalS, VertexLabel, EdgeLabel>;
+    using vertex_descriptor = typename super_type::vertex_descriptor;
+
+  public:
+    /// Iterator on the vertices of a directed_graph.
+    using vertex_iter_type =
+      typename boost::graph_traits<self_type>::vertex_iterator;
+    /// Iterator on the neighbors of the vertex of a directed_graph.
+    using neighb_iter_type =
+      typename boost::graph_traits<self_type>::adjacency_iterator;
+
+    /// Iterators.
+    /// \{
+  public:
+    /// \brief Add an edge between two vertices.
+    ///
+    /// This is just a wrapper around boost::add_edge.
+    void edge_add(const vertex_descriptor& v1,
+                  const vertex_descriptor& v2) override;
+    /// \}
+
+    /// \brief Topological sort.
+    ///
+    /// This version (algorithm 17.5 in Modern Compiler Implementation
+    /// in ML, p. 390) is not the same as boost::topological_sort since
+    /// the former works on directed acyclic graphs (DAGs) and the latter
+    /// doesn't.
+    ///
+    /// \{
+  public:
+    std::vector<vertex_descriptor> topological_sort() const;
+    /// \}
+  };
+
+  /*--------------------------------------.
+  | Specialization for undirected graph.  |
+  `--------------------------------------*/
+
+  template <typename VertexLabel = empty, typename EdgeLabel = empty>
+  class undirected_graph
+    : public graph<boost::undirectedS, VertexLabel, EdgeLabel>
+  {
+  public:
+    using super_type = graph<boost::undirectedS, VertexLabel, EdgeLabel>;
+    using vertex_descriptor = typename super_type::vertex_descriptor;
+
+  public:
+    /// \brief Add an edge between two vertices.
+    ///
+    /// Use this method instead of boost::add_edge directly to keep
+    /// the order between the ends of an edge.
+    void edge_add(const vertex_descriptor& v1,
+                  const vertex_descriptor& v2) override;
+  };
+
+} // namespace misc
+
+#include <misc/graph.hxx>