contrib/llvm/include/llvm/XRay/Graph.h

   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 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     NeighborEdgeIteratorT() = default;
 156     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           MP(_MP), SI(_SI) {}
 162
 163     T &operator*() const {
 164       if (!IsOut)
 165         return *(MP->find({*(this->I), SI}));
 166       else
 167         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     iterator begin() {
 214       auto It = NL.find(A);
 215       if (It == NL.end())
 216         return iterator();
 217       return iterator(It->second.begin(), &M, A);
 218     }
 219
 220     const_iterator cbegin() const {
 221       auto It = NL.find(A);
 222       if (It == NL.end())
 223         return const_iterator();
 224       return const_iterator(It->second.begin(), &M, A);
 225     }
 226
 227     const_iterator begin() const { return cbegin(); }
 228
 229     iterator end() {
 230       auto It = NL.find(A);
 231       if (It == NL.end())
 232         return iterator();
 233       return iterator(It->second.end(), &M, A);
 234     }
 235     const_iterator cend() const {
 236       auto It = NL.find(A);
 237       if (It == NL.end())
 238         return const_iterator();
 239       return const_iterator(It->second.end(), &M, A);
 240     }
 241
 242     const_iterator end() const { return cend(); }
 243
 244     size_type size() const {
 245       auto I = NL.find(A);
 246       if (I == NL.end())
 247         return 0;
 248       else
 249         return I->second.size();
 250     }
 251
 252     bool empty() const { return NL.count(A) == 0; };
 253
 254     InOutEdgeView(GraphT &G, VertexIdentifier A)
 255         : 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     iterator begin() { return G.Vertices.begin(); }
 286     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     size_type size() const { return G.Vertices.size(); }
 292     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     iterator begin() { return G.Edges.begin(); }
 323     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     size_type size() const { return G.Edges.size(); }
 329     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   VertexView<false> vertices() { return VertexView<false>(*this); }
 351
 352   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   EdgeView<false> edges() { return EdgeView<false>(*this); }
 357
 358   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     return InOutEdgeView<false, true>(*this, I);
 364   }
 365
 366   InOutEdgeView<true, true> outEdges(const VertexIdentifier I) const {
 367     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     return InOutEdgeView<false, false>(*this, I);
 374   }
 375
 376   InOutEdgeView<true, false> inEdges(const VertexIdentifier I) const {
 377     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     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   EdgeAttribute &operator[](const EdgeIdentifier &I) {
 390     auto &P = Edges.FindAndConstruct(I);
 391     Vertices.FindAndConstruct(I.first);
 392     Vertices.FindAndConstruct(I.second);
 393     InNeighbors[I.second].insert(I.first);
 394     OutNeighbors[I.first].insert(I.second);
 395     return P.second;
 396   }
 397
 398   /// Looks up a vertex with Identifier I, or an error if it does not exist.
 399   Expected<VertexAttribute &> at(const VertexIdentifier &I) {
 400     auto It = Vertices.find(I);
 401     if (It == Vertices.end())
 402       return make_error<StringError>(
 403           "Vertex Identifier Does Not Exist",
 404           std::make_error_code(std::errc::invalid_argument));
 405     return It->second;
 406   }
 407
 408   Expected<const VertexAttribute &> at(const VertexIdentifier &I) const {
 409     auto It = Vertices.find(I);
 410     if (It == Vertices.end())
 411       return make_error<StringError>(
 412           "Vertex Identifier Does Not Exist",
 413           std::make_error_code(std::errc::invalid_argument));
 414     return It->second;
 415   }
 416
 417   /// Looks up an edge with Identifier I, or an error if it does not exist.
 418   Expected<EdgeAttribute &> at(const EdgeIdentifier &I) {
 419     auto It = Edges.find(I);
 420     if (It == Edges.end())
 421       return make_error<StringError>(
 422           "Edge Identifier Does Not Exist",
 423           std::make_error_code(std::errc::invalid_argument));
 424     return It->second;
 425   }
 426
 427   Expected<const EdgeAttribute &> at(const EdgeIdentifier &I) const {
 428     auto It = Edges.find(I);
 429     if (It == Edges.end())
 430       return make_error<StringError>(
 431           "Edge Identifier Does Not Exist",
 432           std::make_error_code(std::errc::invalid_argument));
 433     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     return Vertices.count(I);
 440   }
 441
 442   /// Looks for an edge with Identifier I, returns 1 if one exists and 0
 443   /// otherwise
 444   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     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   insert(std::pair<EdgeIdentifier, EdgeAttribute> &&Val) {
 480     auto EI = Val.first;
 481     const auto &p = Edges.insert(std::move(Val));
 482     if (p.second) {
 483       Vertices.FindAndConstruct(EI.first);
 484       Vertices.FindAndConstruct(EI.second);
 485       InNeighbors[EI.second].insert(EI.first);
 486       OutNeighbors[EI.first].insert(EI.second);
 487     };
 488
 489     return p;
 490   }
 491 };
 492 }
 493 }
 494 #endif