Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===-- Graph.h - XRay Graph Class ------------------------------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// A Graph Datatype for XRay.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_XRAY_GRAPH_H

#define LLVM_XRAY_GRAPH_H

#include <initializer_list>

#include <stdint.h>

#include <type_traits>

#include <utility>

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/DenseSet.h"

#include "llvm/ADT/iterator.h"

#include "llvm/Support/Error.h"

namespace llvm {

namespace xray {

/// A Graph object represents a Directed Graph and is used in XRay to compute

/// and store function call graphs and associated statistical information.

///

/// The graph takes in four template parameters, these are:

///  - VertexAttribute, this is a structure which is stored for each vertex.

///    Must be DefaultConstructible, CopyConstructible, CopyAssignable and

///    Destructible.

///  - EdgeAttribute, this is a structure which is stored for each edge

///    Must be DefaultConstructible, CopyConstructible, CopyAssignable and

///    Destructible.

///  - EdgeAttribute, this is a structure which is stored for each variable

///  - VI, this is a type over which DenseMapInfo is defined and is the type

///    used look up strings, available as VertexIdentifier.

///  - If the built in DenseMapInfo is not defined, provide a specialization

///    class type here.

///

/// Graph is CopyConstructible, CopyAssignable, MoveConstructible and

/// MoveAssignable but is not EqualityComparible or LessThanComparible.

///

/// Usage Example Graph with weighted edges and vertices:

///   Graph<int, int, int> G;

///

///   G[1] = 0;

///   G[2] = 2;

///   G[{1,2}] = 1;

///   G[{2,1}] = -1;

///   for(const auto &v : G.vertices()){

///     // Do something with the vertices in the graph;

///   }

///   for(const auto &e : G.edges()){

///     // Do something with the edges in the graph;

///   }

///

/// Usage Example with StrRef keys.

///   Graph<int, double, StrRef> StrG;

///    char va[] = "Vertex A";

///    char vaa[] = "Vertex A";

///    char vb[] = "Vertex B"; // Vertices are referenced by String Refs.

///    G[va] = 0;

///    G[vb] = 1;

///    G[{va, vb}] = 1.0;

///    cout() << G[vaa] << " " << G[{vaa, vb}]; //prints "0 1.0".

///

template <typename VertexAttribute, typename EdgeAttribute,

          typename VI = int32_t>

class Graph {

public:

  /// These objects are used to name edges and vertices in the graph.

  typedef VI VertexIdentifier;

  typedef std::pair<VI, VI> EdgeIdentifier;

  /// This type is the value_type of all iterators which range over vertices,

  /// Determined by the Vertices DenseMap

  using VertexValueType =

      detail::DenseMapPair<VertexIdentifier, VertexAttribute>;

  /// This type is the value_type of all iterators which range over edges,

  /// Determined by the Edges DenseMap.

  using EdgeValueType = detail::DenseMapPair<EdgeIdentifier, EdgeAttribute>;

  using size_type = std::size_t;

private:

  /// The type used for storing the EdgeAttribute for each edge in the graph

  using EdgeMapT = DenseMap<EdgeIdentifier, EdgeAttribute>;

  /// The type used for storing the VertexAttribute for each vertex in

  /// the graph.

  using VertexMapT = DenseMap<VertexIdentifier, VertexAttribute>;

  /// The type used for storing the edges entering a vertex. Indexed by

  /// the VertexIdentifier of the start of the edge. Only used to determine

  /// where the incoming edges are, the EdgeIdentifiers are stored in an

  /// InnerEdgeMapT.

  using NeighborSetT = DenseSet<VertexIdentifier>;

  /// The type storing the InnerInvGraphT corresponding to each vertex in

  /// the graph (When a vertex has an incoming edge incident to it)

  using NeighborLookupT = DenseMap<VertexIdentifier, NeighborSetT>;

private:

  /// Stores the map from the start and end vertex of an edge to it's

  /// EdgeAttribute

  EdgeMapT Edges;

  /// Stores the map from VertexIdentifier to VertexAttribute

  VertexMapT Vertices;

  /// Allows fast lookup for the incoming edge set of any given vertex.

  NeighborLookupT InNeighbors;

  /// Allows fast lookup for the outgoing edge set of any given vertex.

  NeighborLookupT OutNeighbors;

  /// An Iterator adapter using an InnerInvGraphT::iterator as a base iterator,

  /// and storing the VertexIdentifier the iterator range comes from. The

  /// dereference operator is then performed using a pointer to the graph's edge

  /// set.

  template <bool IsConst, bool IsOut,

            typename BaseIt = typename NeighborSetT::const_iterator,

            typename T =

                std::conditional_t<IsConst, const EdgeValueType, EdgeValueType>>

  class NeighborEdgeIteratorT

      : public iterator_adaptor_base<

            NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,

            typename std::iterator_traits<BaseIt>::iterator_category, T> {

    using InternalEdgeMapT =

        std::conditional_t<IsConst, const EdgeMapT, EdgeMapT>;

    friend class NeighborEdgeIteratorT<false, IsOut, BaseIt, EdgeValueType>;

    friend class NeighborEdgeIteratorT<true, IsOut, BaseIt,

                                       const EdgeValueType>;

    InternalEdgeMapT *MP;

    VertexIdentifier SI;

  public:

    template <bool IsConstDest,

              typename = std::enable_if<IsConstDest && !IsConst>>

    operator NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,

                                   const EdgeValueType>() const {

      return NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,

                                   const EdgeValueType>(this->I, MP, SI);

    }

    NeighborEdgeIteratorT() = default;

    NeighborEdgeIteratorT(BaseIt _I, InternalEdgeMapT *_MP,

                          VertexIdentifier _SI)

        : iterator_adaptor_base<

              NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,

              typename std::iterator_traits<BaseIt>::iterator_category, T>(_I),

          MP(_MP), SI(_SI) {}

    T &operator*() const {

      if (!IsOut)

        return *(MP->find({*(this->I), SI}));

      else

        return *(MP->find({SI, *(this->I)}));

    }

  };

public:

  /// A const iterator type for iterating through the set of edges entering a

  /// vertex.

  ///

  /// Has a const EdgeValueType as its value_type

  using ConstInEdgeIterator = NeighborEdgeIteratorT<true, false>;

  /// An iterator type for iterating through the set of edges leaving a vertex.

  ///

  /// Has an EdgeValueType as its value_type

  using InEdgeIterator = NeighborEdgeIteratorT<false, false>;

  /// A const iterator type for iterating through the set of edges entering a

  /// vertex.

  ///

  /// Has a const EdgeValueType as its value_type

  using ConstOutEdgeIterator = NeighborEdgeIteratorT<true, true>;

  /// An iterator type for iterating through the set of edges leaving a vertex.

  ///

  /// Has an EdgeValueType as its value_type

  using OutEdgeIterator = NeighborEdgeIteratorT<false, true>;

  /// A class for ranging over the incoming edges incident to a vertex.

  ///

  /// Like all views in this class it provides methods to get the beginning and

  /// past the range iterators for the range, as well as methods to determine

  /// the number of elements in the range and whether the range is empty.

  template <bool isConst, bool isOut> class InOutEdgeView {

  public:

    using iterator = NeighborEdgeIteratorT<isConst, isOut>;

    using const_iterator = NeighborEdgeIteratorT<true, isOut>;

    using GraphT = std::conditional_t<isConst, const Graph, Graph>;

    using InternalEdgeMapT =

        std::conditional_t<isConst, const EdgeMapT, EdgeMapT>;

  private:

    InternalEdgeMapT &M;

    const VertexIdentifier A;

    const NeighborLookupT &NL;

  public:

    iterator begin() {

      auto It = NL.find(A);

      if (It == NL.end())

        return iterator();

      return iterator(It->second.begin(), &M, A);

    }

    const_iterator cbegin() const {

      auto It = NL.find(A);

      if (It == NL.end())

        return const_iterator();

      return const_iterator(It->second.begin(), &M, A);

    }

    const_iterator begin() const { return cbegin(); }

    iterator end() {

      auto It = NL.find(A);

      if (It == NL.end())

        return iterator();

      return iterator(It->second.end(), &M, A);

    }

    const_iterator cend() const {

      auto It = NL.find(A);

      if (It == NL.end())

        return const_iterator();

      return const_iterator(It->second.end(), &M, A);

    }

    const_iterator end() const { return cend(); }

    size_type size() const {

      auto I = NL.find(A);

      if (I == NL.end())

        return 0;

      else

        return I->second.size();

    }

    bool empty() const { return NL.count(A) == 0; };

    InOutEdgeView(GraphT &G, VertexIdentifier A)

        : M(G.Edges), A(A), NL(isOut ? G.OutNeighbors : G.InNeighbors) {}

  };

  /// A const iterator type for iterating through the whole vertex set of the

  /// graph.

  ///

  /// Has a const VertexValueType as its value_type

  using ConstVertexIterator = typename VertexMapT::const_iterator;

  /// An iterator type for iterating through the whole vertex set of the graph.

  ///

  /// Has a VertexValueType as its value_type

  using VertexIterator = typename VertexMapT::iterator;

  /// A class for ranging over the vertices in the graph.

  ///

  /// Like all views in this class it provides methods to get the beginning and

  /// past the range iterators for the range, as well as methods to determine

  /// the number of elements in the range and whether the range is empty.

  template <bool isConst> class VertexView {

  public:

    using iterator =

        std::conditional_t<isConst, ConstVertexIterator, VertexIterator>;

    using const_iterator = ConstVertexIterator;

    using GraphT = std::conditional_t<isConst, const Graph, Graph>;

  private:

    GraphT &G;

  public:

    iterator begin() { return G.Vertices.begin(); }

    iterator end() { return G.Vertices.end(); }

    const_iterator cbegin() const { return G.Vertices.cbegin(); }

    const_iterator cend() const { return G.Vertices.cend(); }

    const_iterator begin() const { return G.Vertices.begin(); }

    const_iterator end() const { return G.Vertices.end(); }

    size_type size() const { return G.Vertices.size(); }

    bool empty() const { return G.Vertices.empty(); }

    VertexView(GraphT &_G) : G(_G) {}

  };

  /// A const iterator for iterating through the entire edge set of the graph.

  ///

  /// Has a const EdgeValueType as its value_type

  using ConstEdgeIterator = typename EdgeMapT::const_iterator;

  /// An iterator for iterating through the entire edge set of the graph.

  ///

  /// Has an EdgeValueType as its value_type

  using EdgeIterator = typename EdgeMapT::iterator;

  /// A class for ranging over all the edges in the graph.

  ///

  /// Like all views in this class it provides methods to get the beginning and

  /// past the range iterators for the range, as well as methods to determine

  /// the number of elements in the range and whether the range is empty.

  template <bool isConst> class EdgeView {

  public:

    using iterator =

        std::conditional_t<isConst, ConstEdgeIterator, EdgeIterator>;

    using const_iterator = ConstEdgeIterator;

    using GraphT = std::conditional_t<isConst, const Graph, Graph>;

  private:

    GraphT &G;

  public:

    iterator begin() { return G.Edges.begin(); }

    iterator end() { return G.Edges.end(); }

    const_iterator cbegin() const { return G.Edges.cbegin(); }

    const_iterator cend() const { return G.Edges.cend(); }

    const_iterator begin() const { return G.Edges.begin(); }

    const_iterator end() const { return G.Edges.end(); }

    size_type size() const { return G.Edges.size(); }

    bool empty() const { return G.Edges.empty(); }

    EdgeView(GraphT &_G) : G(_G) {}

  };

public:

  // TODO: implement constructor to enable Graph Initialisation.\

  // Something like:

  //   Graph<int, int, int> G(

  //   {1, 2, 3, 4, 5},

  //   {{1, 2}, {2, 3}, {3, 4}});

  /// Empty the Graph

  void clear() {

    Edges.clear();

    Vertices.clear();

    InNeighbors.clear();

    OutNeighbors.clear();

  }

  /// Returns a view object allowing iteration over the vertices of the graph.

  /// also allows access to the size of the vertex set.

  VertexView<false> vertices() { return VertexView<false>(*this); }

  VertexView<true> vertices() const { return VertexView<true>(*this); }

  /// Returns a view object allowing iteration over the edges of the graph.

  /// also allows access to the size of the edge set.

  EdgeView<false> edges() { return EdgeView<false>(*this); }

  EdgeView<true> edges() const { return EdgeView<true>(*this); }

  /// Returns a view object allowing iteration over the edges which start at

  /// a vertex I.

  InOutEdgeView<false, true> outEdges(const VertexIdentifier I) {

    return InOutEdgeView<false, true>(*this, I);

  }

  InOutEdgeView<true, true> outEdges(const VertexIdentifier I) const {

    return InOutEdgeView<true, true>(*this, I);

  }

  /// Returns a view object allowing iteration over the edges which point to

  /// a vertex I.

  InOutEdgeView<false, false> inEdges(const VertexIdentifier I) {

    return InOutEdgeView<false, false>(*this, I);

  }

  InOutEdgeView<true, false> inEdges(const VertexIdentifier I) const {

    return InOutEdgeView<true, false>(*this, I);

  }

  /// Looks up the vertex with identifier I, if it does not exist it default

  /// constructs it.

  VertexAttribute &operator[](const VertexIdentifier &I) {

    return Vertices.FindAndConstruct(I).second;

  }

  /// Looks up the edge with identifier I, if it does not exist it default

  /// constructs it, if it's endpoints do not exist it also default constructs

  /// them.

  EdgeAttribute &operator[](const EdgeIdentifier &I) {

    auto &P = Edges.FindAndConstruct(I);

    Vertices.FindAndConstruct(I.first);

    Vertices.FindAndConstruct(I.second);

    InNeighbors[I.second].insert(I.first);

    OutNeighbors[I.first].insert(I.second);

    return P.second;

  }

  /// Looks up a vertex with Identifier I, or an error if it does not exist.

  Expected<VertexAttribute &> at(const VertexIdentifier &I) {

    auto It = Vertices.find(I);

    if (It == Vertices.end())

      return make_error<StringError>(

          "Vertex Identifier Does Not Exist",

          std::make_error_code(std::errc::invalid_argument));

    return It->second;

  }

  Expected<const VertexAttribute &> at(const VertexIdentifier &I) const {

    auto It = Vertices.find(I);

    if (It == Vertices.end())

      return make_error<StringError>(

          "Vertex Identifier Does Not Exist",

          std::make_error_code(std::errc::invalid_argument));

    return It->second;

  }

  /// Looks up an edge with Identifier I, or an error if it does not exist.

  Expected<EdgeAttribute &> at(const EdgeIdentifier &I) {

    auto It = Edges.find(I);

    if (It == Edges.end())

      return make_error<StringError>(

          "Edge Identifier Does Not Exist",

          std::make_error_code(std::errc::invalid_argument));

    return It->second;

  }

  Expected<const EdgeAttribute &> at(const EdgeIdentifier &I) const {

    auto It = Edges.find(I);

    if (It == Edges.end())

      return make_error<StringError>(

          "Edge Identifier Does Not Exist",

          std::make_error_code(std::errc::invalid_argument));

    return It->second;

  }

  /// Looks for a vertex with identifier I, returns 1 if one exists, and

  /// 0 otherwise

  size_type count(const VertexIdentifier &I) const {

    return Vertices.count(I);

  }

  /// Looks for an edge with Identifier I, returns 1 if one exists and 0

  /// otherwise

  size_type count(const EdgeIdentifier &I) const { return Edges.count(I); }

  /// Inserts a vertex into the graph with Identifier Val.first, and

  /// Attribute Val.second.

  std::pair<VertexIterator, bool>

  insert(const std::pair<VertexIdentifier, VertexAttribute> &Val) {

    return Vertices.insert(Val);

  }

  std::pair<VertexIterator, bool>

  insert(std::pair<VertexIdentifier, VertexAttribute> &&Val) {

    return Vertices.insert(std::move(Val));

  }

  /// Inserts an edge into the graph with Identifier Val.first, and

  /// Attribute Val.second. If the key is already in the map, it returns false

  /// and doesn't update the value.

  std::pair<EdgeIterator, bool>

  insert(const std::pair<EdgeIdentifier, EdgeAttribute> &Val) {

    const auto &p = Edges.insert(Val);

    if (p.second) {

      const auto &EI = Val.first;

      Vertices.FindAndConstruct(EI.first);

      Vertices.FindAndConstruct(EI.second);

      InNeighbors[EI.second].insert(EI.first);

      OutNeighbors[EI.first].insert(EI.second);

    };

    return p;

  }

  /// Inserts an edge into the graph with Identifier Val.first, and

  /// Attribute Val.second. If the key is already in the map, it returns false

  /// and doesn't update the value.

  std::pair<EdgeIterator, bool>

  insert(std::pair<EdgeIdentifier, EdgeAttribute> &&Val) {

    auto EI = Val.first;

    const auto &p = Edges.insert(std::move(Val));

    if (p.second) {

      Vertices.FindAndConstruct(EI.first);

      Vertices.FindAndConstruct(EI.second);

      InNeighbors[EI.second].insert(EI.first);

      OutNeighbors[EI.first].insert(EI.second);

    };

    return p;

  }

};

}

}

#endif