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

source code of llvm/include/llvm/XRay/Graph.h