LCOV - code coverage report
Current view: top level - include/llvm/XRay - Graph.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 87 91 95.6 %
Date: 2017-09-14 15:23:50 Functions: 42 42 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- Graph.h - XRay Graph Class ------------------------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // A Graph Datatype for XRay.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #ifndef LLVM_XRAY_GRAPH_T_H
      15             : #define LLVM_XRAY_GRAPH_T_H
      16             : 
      17             : #include <initializer_list>
      18             : #include <stdint.h>
      19             : #include <type_traits>
      20             : #include <utility>
      21             : 
      22             : #include "llvm/ADT/DenseMap.h"
      23             : #include "llvm/ADT/DenseSet.h"
      24             : #include "llvm/ADT/iterator.h"
      25             : #include "llvm/Support/Error.h"
      26             : 
      27             : namespace llvm {
      28             : namespace xray {
      29             : 
      30             : /// A Graph object represents a Directed Graph and is used in XRay to compute
      31             : /// and store function call graphs and associated statistical information.
      32             : ///
      33             : /// The graph takes in four template parameters, these are:
      34             : ///  - VertexAttribute, this is a structure which is stored for each vertex.
      35             : ///    Must be DefaultConstructible, CopyConstructible, CopyAssignable and
      36             : ///    Destructible.
      37             : ///  - EdgeAttribute, this is a structure which is stored for each edge
      38             : ///    Must be DefaultConstructible, CopyConstructible, CopyAssignable and
      39             : ///    Destructible.
      40             : ///  - EdgeAttribute, this is a structure which is stored for each variable
      41             : ///  - VI, this is a type over which DenseMapInfo is defined and is the type
      42             : ///    used look up strings, available as VertexIdentifier.
      43             : ///  - If the built in DenseMapInfo is not defined, provide a specialization
      44             : ///    class type here.
      45             : ///
      46             : /// Graph is CopyConstructible, CopyAssignable, MoveConstructible and
      47             : /// MoveAssignable but is not EqualityComparible or LessThanComparible.
      48             : ///
      49             : /// Usage Example Graph with weighted edges and vertices:
      50             : ///   Graph<int, int, int> G;
      51             : ///
      52             : ///   G[1] = 0;
      53             : ///   G[2] = 2;
      54             : ///   G[{1,2}] = 1;
      55             : ///   G[{2,1}] = -1;
      56             : ///   for(const auto &v : G.vertices()){
      57             : ///     // Do something with the vertices in the graph;
      58             : ///   }
      59             : ///   for(const auto &e : G.edges()){
      60             : ///     // Do something with the edges in the graph;
      61             : ///   }
      62             : ///
      63             : /// Usage Example with StrRef keys.
      64             : ///   Graph<int, double, StrRef> StrG;
      65             : ///    char va[] = "Vertex A";
      66             : ///    char vaa[] = "Vertex A";
      67             : ///    char vb[] = "Vertex B"; // Vertices are referenced by String Refs.
      68             : ///    G[va] = 0;
      69             : ///    G[vb] = 1;
      70             : ///    G[{va, vb}] = 1.0;
      71             : ///    cout() << G[vaa] << " " << G[{vaa, vb}]; //prints "0 1.0".
      72             : ///
      73             : template <typename VertexAttribute, typename EdgeAttribute,
      74             :           typename VI = int32_t>
      75        1450 : class Graph {
      76             : public:
      77             :   /// These objects are used to name edges and vertices in the graph.
      78             :   typedef VI VertexIdentifier;
      79             :   typedef std::pair<VI, VI> EdgeIdentifier;
      80             : 
      81             :   /// This type is the value_type of all iterators which range over vertices,
      82             :   /// Determined by the Vertices DenseMap
      83             :   using VertexValueType =
      84             :       detail::DenseMapPair<VertexIdentifier, VertexAttribute>;
      85             : 
      86             :   /// This type is the value_type of all iterators which range over edges,
      87             :   /// Determined by the Edges DenseMap.
      88             :   using EdgeValueType = detail::DenseMapPair<EdgeIdentifier, EdgeAttribute>;
      89             : 
      90             :   using size_type = std::size_t;
      91             : 
      92             : private:
      93             :   /// The type used for storing the EdgeAttribute for each edge in the graph
      94             :   using EdgeMapT = DenseMap<EdgeIdentifier, EdgeAttribute>;
      95             : 
      96             :   /// The type used for storing the VertexAttribute for each vertex in
      97             :   /// the graph.
      98             :   using VertexMapT = DenseMap<VertexIdentifier, VertexAttribute>;
      99             : 
     100             :   /// The type used for storing the edges entering a vertex. Indexed by
     101             :   /// the VertexIdentifier of the start of the edge. Only used to determine
     102             :   /// where the incoming edges are, the EdgeIdentifiers are stored in an
     103             :   /// InnerEdgeMapT.
     104             :   using NeighborSetT = DenseSet<VertexIdentifier>;
     105             : 
     106             :   /// The type storing the InnerInvGraphT corresponding to each vertex in
     107             :   /// the graph (When a vertex has an incoming edge incident to it)
     108             :   using NeighborLookupT = DenseMap<VertexIdentifier, NeighborSetT>;
     109             : 
     110             : private:
     111             :   /// Stores the map from the start and end vertex of an edge to it's
     112             :   /// EdgeAttribute
     113             :   EdgeMapT Edges;
     114             : 
     115             :   /// Stores the map from VertexIdentifier to VertexAttribute
     116             :   VertexMapT Vertices;
     117             : 
     118             :   /// Allows fast lookup for the incoming edge set of any given vertex.
     119             :   NeighborLookupT InNeighbors;
     120             : 
     121             :   /// Allows fast lookup for the outgoing edge set of any given vertex.
     122             :   NeighborLookupT OutNeighbors;
     123             : 
     124             :   /// An Iterator adapter using an InnerInvGraphT::iterator as a base iterator,
     125             :   /// and storing the VertexIdentifier the iterator range comes from. The
     126             :   /// dereference operator is then performed using a pointer to the graph's edge
     127             :   /// set.
     128             :   template <bool IsConst, bool IsOut,
     129             :             typename BaseIt = typename NeighborSetT::const_iterator,
     130             :             typename T = typename std::conditional<IsConst, const EdgeValueType,
     131             :                                                    EdgeValueType>::type>
     132             :   class NeighborEdgeIteratorT
     133             :       : public iterator_adaptor_base<
     134             :             NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,
     135             :             typename std::iterator_traits<BaseIt>::iterator_category, T> {
     136             :     using InternalEdgeMapT =
     137             :         typename std::conditional<IsConst, const EdgeMapT, EdgeMapT>::type;
     138             : 
     139             :     friend class NeighborEdgeIteratorT<false, IsOut, BaseIt, EdgeValueType>;
     140             :     friend class NeighborEdgeIteratorT<true, IsOut, BaseIt,
     141             :                                        const EdgeValueType>;
     142             : 
     143             :     InternalEdgeMapT *MP;
     144             :     VertexIdentifier SI;
     145             : 
     146             :   public:
     147             :     template <bool IsConstDest,
     148             :               typename = typename std::enable_if<IsConstDest && !IsConst>::type>
     149             :     operator NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,
     150             :                                    const EdgeValueType>() const {
     151             :       return NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,
     152             :                                    const EdgeValueType>(this->I, MP, SI);
     153             :     }
     154             : 
     155         248 :     NeighborEdgeIteratorT() = default;
     156        1212 :     NeighborEdgeIteratorT(BaseIt _I, InternalEdgeMapT *_MP,
     157             :                           VertexIdentifier _SI)
     158             :         : iterator_adaptor_base<
     159             :               NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,
     160             :               typename std::iterator_traits<BaseIt>::iterator_category, T>(_I),
     161        2424 :           MP(_MP), SI(_SI) {}
     162             : 
     163             :     T &operator*() const {
     164             :       if (!IsOut)
     165        1002 :         return *(MP->find({*(this->I), SI}));
     166             :       else
     167         414 :         return *(MP->find({SI, *(this->I)}));
     168             :     }
     169             :   };
     170             : 
     171             : public:
     172             :   /// A const iterator type for iterating through the set of edges entering a
     173             :   /// vertex.
     174             :   ///
     175             :   /// Has a const EdgeValueType as its value_type
     176             :   using ConstInEdgeIterator = NeighborEdgeIteratorT<true, false>;
     177             : 
     178             :   /// An iterator type for iterating through the set of edges leaving a vertex.
     179             :   ///
     180             :   /// Has an EdgeValueType as its value_type
     181             :   using InEdgeIterator = NeighborEdgeIteratorT<false, false>;
     182             : 
     183             :   /// A const iterator type for iterating through the set of edges entering a
     184             :   /// vertex.
     185             :   ///
     186             :   /// Has a const EdgeValueType as its value_type
     187             :   using ConstOutEdgeIterator = NeighborEdgeIteratorT<true, true>;
     188             : 
     189             :   /// An iterator type for iterating through the set of edges leaving a vertex.
     190             :   ///
     191             :   /// Has an EdgeValueType as its value_type
     192             :   using OutEdgeIterator = NeighborEdgeIteratorT<false, true>;
     193             : 
     194             :   /// A class for ranging over the incoming edges incident to a vertex.
     195             :   ///
     196             :   /// Like all views in this class it provides methods to get the beginning and
     197             :   /// past the range iterators for the range, as well as methods to determine
     198             :   /// the number of elements in the range and whether the range is empty.
     199             :   template <bool isConst, bool isOut> class InOutEdgeView {
     200             :   public:
     201             :     using iterator = NeighborEdgeIteratorT<isConst, isOut>;
     202             :     using const_iterator = NeighborEdgeIteratorT<true, isOut>;
     203             :     using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
     204             :     using InternalEdgeMapT =
     205             :         typename std::conditional<isConst, const EdgeMapT, EdgeMapT>::type;
     206             : 
     207             :   private:
     208             :     InternalEdgeMapT &M;
     209             :     const VertexIdentifier A;
     210             :     const NeighborLookupT &NL;
     211             : 
     212             :   public:
     213         446 :     iterator begin() {
     214         446 :       auto It = NL.find(A);
     215         892 :       if (It == NL.end())
     216          42 :         return iterator();
     217         808 :       return iterator(It->second.begin(), &M, A);
     218             :     }
     219             : 
     220         112 :     const_iterator cbegin() const {
     221         112 :       auto It = NL.find(A);
     222         224 :       if (It == NL.end())
     223           0 :         return const_iterator();
     224         224 :       return const_iterator(It->second.begin(), &M, A);
     225             :     }
     226             : 
     227         112 :     const_iterator begin() const { return cbegin(); }
     228             : 
     229         666 :     iterator end() {
     230         666 :       auto It = NL.find(A);
     231        1332 :       if (It == NL.end())
     232          82 :         return iterator();
     233        1168 :       return iterator(It->second.end(), &M, A);
     234             :     }
     235         112 :     const_iterator cend() const {
     236         112 :       auto It = NL.find(A);
     237         224 :       if (It == NL.end())
     238           0 :         return const_iterator();
     239         224 :       return const_iterator(It->second.end(), &M, A);
     240             :     }
     241             : 
     242         112 :     const_iterator end() const { return cend(); }
     243             : 
     244         116 :     size_type size() const {
     245         116 :       auto I = NL.find(A);
     246         232 :       if (I == NL.end())
     247             :         return 0;
     248             :       else
     249         228 :         return I->second.size();
     250             :     }
     251             : 
     252           8 :     bool empty() const { return NL.count(A) == 0; };
     253             : 
     254        1019 :     InOutEdgeView(GraphT &G, VertexIdentifier A)
     255        1020 :         : M(G.Edges), A(A), NL(isOut ? G.OutNeighbors : G.InNeighbors) {}
     256             :   };
     257             : 
     258             :   /// A const iterator type for iterating through the whole vertex set of the
     259             :   /// graph.
     260             :   ///
     261             :   /// Has a const VertexValueType as its value_type
     262             :   using ConstVertexIterator = typename VertexMapT::const_iterator;
     263             : 
     264             :   /// An iterator type for iterating through the whole vertex set of the graph.
     265             :   ///
     266             :   /// Has a VertexValueType as its value_type
     267             :   using VertexIterator = typename VertexMapT::iterator;
     268             : 
     269             :   /// A class for ranging over the vertices in the graph.
     270             :   ///
     271             :   /// Like all views in this class it provides methods to get the beginning and
     272             :   /// past the range iterators for the range, as well as methods to determine
     273             :   /// the number of elements in the range and whether the range is empty.
     274             :   template <bool isConst> class VertexView {
     275             :   public:
     276             :     using iterator = typename std::conditional<isConst, ConstVertexIterator,
     277             :                                                VertexIterator>::type;
     278             :     using const_iterator = ConstVertexIterator;
     279             :     using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
     280             : 
     281             :   private:
     282             :     GraphT &G;
     283             : 
     284             :   public:
     285         173 :     iterator begin() { return G.Vertices.begin(); }
     286         438 :     iterator end() { return G.Vertices.end(); }
     287             :     const_iterator cbegin() const { return G.Vertices.cbegin(); }
     288             :     const_iterator cend() const { return G.Vertices.cend(); }
     289             :     const_iterator begin() const { return G.Vertices.begin(); }
     290             :     const_iterator end() const { return G.Vertices.end(); }
     291          20 :     size_type size() const { return G.Vertices.size(); }
     292          22 :     bool empty() const { return G.Vertices.empty(); }
     293             :     VertexView(GraphT &_G) : G(_G) {}
     294             :   };
     295             : 
     296             :   /// A const iterator for iterating through the entire edge set of the graph.
     297             :   ///
     298             :   /// Has a const EdgeValueType as its value_type
     299             :   using ConstEdgeIterator = typename EdgeMapT::const_iterator;
     300             : 
     301             :   /// An iterator for iterating through the entire edge set of the graph.
     302             :   ///
     303             :   /// Has an EdgeValueType as its value_type
     304             :   using EdgeIterator = typename EdgeMapT::iterator;
     305             : 
     306             :   /// A class for ranging over all the edges in the graph.
     307             :   ///
     308             :   /// Like all views in this class it provides methods to get the beginning and
     309             :   /// past the range iterators for the range, as well as methods to determine
     310             :   /// the number of elements in the range and whether the range is empty.
     311             :   template <bool isConst> class EdgeView {
     312             :   public:
     313             :     using iterator = typename std::conditional<isConst, ConstEdgeIterator,
     314             :                                                EdgeIterator>::type;
     315             :     using const_iterator = ConstEdgeIterator;
     316             :     using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
     317             : 
     318             :   private:
     319             :     GraphT &G;
     320             : 
     321             :   public:
     322         174 :     iterator begin() { return G.Edges.begin(); }
     323         456 :     iterator end() { return G.Edges.end(); }
     324             :     const_iterator cbegin() const { return G.Edges.cbegin(); }
     325             :     const_iterator cend() const { return G.Edges.cend(); }
     326             :     const_iterator begin() const { return G.Edges.begin(); }
     327             :     const_iterator end() const { return G.Edges.end(); }
     328          20 :     size_type size() const { return G.Edges.size(); }
     329          22 :     bool empty() const { return G.Edges.empty(); }
     330             :     EdgeView(GraphT &_G) : G(_G) {}
     331             :   };
     332             : 
     333             : public:
     334             :   // TODO: implement constructor to enable Graph Initialisation.\
     335             :   // Something like:
     336             :   //   Graph<int, int, int> G(
     337             :   //   {1, 2, 3, 4, 5},
     338             :   //   {{1, 2}, {2, 3}, {3, 4}});
     339             : 
     340             :   /// Empty the Graph
     341             :   void clear() {
     342             :     Edges.clear();
     343             :     Vertices.clear();
     344             :     InNeighbors.clear();
     345             :     OutNeighbors.clear();
     346             :   }
     347             : 
     348             :   /// Returns a view object allowing iteration over the vertices of the graph.
     349             :   /// also allows access to the size of the vertex set.
     350         181 :   VertexView<false> vertices() { return VertexView<false>(*this); }
     351             : 
     352         111 :   VertexView<true> vertices() const { return VertexView<true>(*this); }
     353             : 
     354             :   /// Returns a view object allowing iteration over the edges of the graph.
     355             :   /// also allows access to the size of the edge set.
     356         185 :   EdgeView<false> edges() { return EdgeView<false>(*this); }
     357             : 
     358         125 :   EdgeView<true> edges() const { return EdgeView<true>(*this); }
     359             : 
     360             :   /// Returns a view object allowing iteration over the edges which start at
     361             :   /// a vertex I.
     362             :   InOutEdgeView<false, true> outEdges(const VertexIdentifier I) {
     363         196 :     return InOutEdgeView<false, true>(*this, I);
     364             :   }
     365             : 
     366             :   InOutEdgeView<true, true> outEdges(const VertexIdentifier I) const {
     367         208 :     return InOutEdgeView<true, true>(*this, I);
     368             :   }
     369             : 
     370             :   /// Returns a view object allowing iteration over the edges which point to
     371             :   /// a vertex I.
     372             :   InOutEdgeView<false, false> inEdges(const VertexIdentifier I) {
     373         408 :     return InOutEdgeView<false, false>(*this, I);
     374             :   }
     375             : 
     376             :   InOutEdgeView<true, false> inEdges(const VertexIdentifier I) const {
     377         208 :     return InOutEdgeView<true, false>(*this, I);
     378             :   }
     379             : 
     380             :   /// Looks up the vertex with identifier I, if it does not exist it default
     381             :   /// constructs it.
     382             :   VertexAttribute &operator[](const VertexIdentifier &I) {
     383        1062 :     return Vertices.FindAndConstruct(I).second;
     384             :   }
     385             : 
     386             :   /// Looks up the edge with identifier I, if it does not exist it default
     387             :   /// constructs it, if it's endpoints do not exist it also default constructs
     388             :   /// them.
     389         374 :   EdgeAttribute &operator[](const EdgeIdentifier &I) {
     390         374 :     auto &P = Edges.FindAndConstruct(I);
     391         374 :     Vertices.FindAndConstruct(I.first);
     392         374 :     Vertices.FindAndConstruct(I.second);
     393        1122 :     InNeighbors[I.second].insert(I.first);
     394        1122 :     OutNeighbors[I.first].insert(I.second);
     395         374 :     return P.second;
     396             :   }
     397             : 
     398             :   /// Looks up a vertex with Identifier I, or an error if it does not exist.
     399          24 :   Expected<VertexAttribute &> at(const VertexIdentifier &I) {
     400          24 :     auto It = Vertices.find(I);
     401          72 :     if (It == Vertices.end())
     402             :       return make_error<StringError>(
     403             :           "Vertex Identifier Does Not Exist",
     404           0 :           std::make_error_code(std::errc::invalid_argument));
     405          24 :     return It->second;
     406             :   }
     407             : 
     408         346 :   Expected<const VertexAttribute &> at(const VertexIdentifier &I) const {
     409         346 :     auto It = Vertices.find(I);
     410         692 :     if (It == Vertices.end())
     411             :       return make_error<StringError>(
     412             :           "Vertex Identifier Does Not Exist",
     413           4 :           std::make_error_code(std::errc::invalid_argument));
     414         345 :     return It->second;
     415             :   }
     416             : 
     417             :   /// Looks up an edge with Identifier I, or an error if it does not exist.
     418          28 :   Expected<EdgeAttribute &> at(const EdgeIdentifier &I) {
     419          28 :     auto It = Edges.find(I);
     420          84 :     if (It == Edges.end())
     421             :       return make_error<StringError>(
     422             :           "Edge Identifier Does Not Exist",
     423           0 :           std::make_error_code(std::errc::invalid_argument));
     424          28 :     return It->second;
     425             :   }
     426             : 
     427          30 :   Expected<const EdgeAttribute &> at(const EdgeIdentifier &I) const {
     428          30 :     auto It = Edges.find(I);
     429          60 :     if (It == Edges.end())
     430             :       return make_error<StringError>(
     431             :           "Edge Identifier Does Not Exist",
     432           4 :           std::make_error_code(std::errc::invalid_argument));
     433          29 :     return It->second;
     434             :   }
     435             : 
     436             :   /// Looks for a vertex with identifier I, returns 1 if one exists, and
     437             :   /// 0 otherwise
     438             :   size_type count(const VertexIdentifier &I) const {
     439         530 :     return Vertices.count(I);
     440             :   }
     441             : 
     442             :   /// Looks for an edge with Identifier I, returns 1 if one exists and 0
     443             :   /// otherwise
     444         118 :   size_type count(const EdgeIdentifier &I) const { return Edges.count(I); }
     445             : 
     446             :   /// Inserts a vertex into the graph with Identifier Val.first, and
     447             :   /// Attribute Val.second.
     448             :   std::pair<VertexIterator, bool>
     449             :   insert(const std::pair<VertexIdentifier, VertexAttribute> &Val) {
     450             :     return Vertices.insert(Val);
     451             :   }
     452             : 
     453             :   std::pair<VertexIterator, bool>
     454             :   insert(std::pair<VertexIdentifier, VertexAttribute> &&Val) {
     455         120 :     return Vertices.insert(std::move(Val));
     456             :   }
     457             : 
     458             :   /// Inserts an edge into the graph with Identifier Val.first, and
     459             :   /// Attribute Val.second. If the key is already in the map, it returns false
     460             :   /// and doesn't update the value.
     461             :   std::pair<EdgeIterator, bool>
     462             :   insert(const std::pair<EdgeIdentifier, EdgeAttribute> &Val) {
     463             :     const auto &p = Edges.insert(Val);
     464             :     if (p.second) {
     465             :       const auto &EI = Val.first;
     466             :       Vertices.FindAndConstruct(EI.first);
     467             :       Vertices.FindAndConstruct(EI.second);
     468             :       InNeighbors[EI.second].insert(EI.first);
     469             :       OutNeighbors[EI.first].insert(EI.second);
     470             :     };
     471             : 
     472             :     return p;
     473             :   }
     474             : 
     475             :   /// Inserts an edge into the graph with Identifier Val.first, and
     476             :   /// Attribute Val.second. If the key is already in the map, it returns false
     477             :   /// and doesn't update the value.
     478             :   std::pair<EdgeIterator, bool>
     479          70 :   insert(std::pair<EdgeIdentifier, EdgeAttribute> &&Val) {
     480          70 :     auto EI = Val.first;
     481         140 :     const auto &p = Edges.insert(std::move(Val));
     482          70 :     if (p.second) {
     483          70 :       Vertices.FindAndConstruct(EI.first);
     484          70 :       Vertices.FindAndConstruct(EI.second);
     485         210 :       InNeighbors[EI.second].insert(EI.first);
     486         210 :       OutNeighbors[EI.first].insert(EI.second);
     487             :     };
     488             : 
     489          70 :     return p;
     490             :   }
     491             : };
     492             : }
     493             : }
     494             : #endif

Generated by: LCOV version 1.13