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 : 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 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 1212 : MP(_MP), SI(_SI) {}
162 :
163 : T &operator*() const {
164 : if (!IsOut)
165 428 : return *(MP->find({*(this->I), SI}));
166 : else
167 4 : 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 404 : return iterator(It->second.begin(), &M, A);
218 : }
219 56 :
220 56 : const_iterator cbegin() const {
221 112 : auto It = NL.find(A);
222 16 : if (It == NL.end())
223 40 : return const_iterator();
224 : return const_iterator(It->second.begin(), &M, A);
225 56 : }
226 56 :
227 112 : const_iterator begin() const { return cbegin(); }
228 4 :
229 264 : iterator end() {
230 212 : auto It = NL.find(A);
231 485 : if (It == NL.end())
232 61 : return iterator();
233 546 : return iterator(It->second.end(), &M, A);
234 5 : }
235 56 : const_iterator cend() const {
236 : auto It = NL.find(A);
237 61 : if (It == NL.end())
238 61 : return const_iterator();
239 122 : return const_iterator(It->second.end(), &M, A);
240 17 : }
241 44 :
242 : const_iterator end() const { return cend(); }
243 :
244 112 : size_type size() const {
245 112 : auto I = NL.find(A);
246 224 : if (I == NL.end())
247 0 : return 0;
248 112 : else
249 : return I->second.size();
250 28 : }
251 28 :
252 56 : bool empty() const { return NL.count(A) == 0; };
253 0 :
254 240 : InOutEdgeView(GraphT &G, VertexIdentifier A)
255 212 : : M(G.Edges), A(A), NL(isOut ? G.OutNeighbors : G.InNeighbors) {}
256 28 : };
257 28 :
258 56 : /// A const iterator type for iterating through the whole vertex set of the
259 0 : /// graph.
260 28 : ///
261 : /// Has a const VertexValueType as its value_type
262 28 : using ConstVertexIterator = typename VertexMapT::const_iterator;
263 28 :
264 56 : /// An iterator type for iterating through the whole vertex set of the graph.
265 0 : ///
266 28 : /// Has a VertexValueType as its value_type
267 : using VertexIterator = typename VertexMapT::iterator;
268 28 :
269 28 : /// A class for ranging over the vertices in the graph.
270 56 : ///
271 0 : /// Like all views in this class it provides methods to get the beginning and
272 28 : /// 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 112 : public:
276 : using iterator = typename std::conditional<isConst, ConstVertexIterator,
277 454 : VertexIterator>::type;
278 454 : using const_iterator = ConstVertexIterator;
279 908 : using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
280 82 :
281 744 : private:
282 : GraphT &G;
283 112 :
284 112 : public:
285 337 : iterator begin() { return G.Vertices.begin(); }
286 32 : iterator end() { return G.Vertices.end(); }
287 160 : const_iterator cbegin() const { return G.Vertices.cbegin(); }
288 : const_iterator cend() const { return G.Vertices.cend(); }
289 112 : const_iterator begin() const { return G.Vertices.begin(); }
290 112 : const_iterator end() const { return G.Vertices.end(); }
291 224 : size_type size() const { return G.Vertices.size(); }
292 8 : bool empty() const { return G.Vertices.empty(); }
293 208 : VertexView(GraphT &_G) : G(_G) {}
294 : };
295 115 :
296 115 : /// A const iterator for iterating through the entire edge set of the graph.
297 230 : ///
298 9 : /// Has a const EdgeValueType as its value_type
299 212 : using ConstEdgeIterator = typename EdgeMapT::const_iterator;
300 :
301 115 : /// An iterator for iterating through the entire edge set of the graph.
302 115 : ///
303 230 : /// Has an EdgeValueType as its value_type
304 33 : using EdgeIterator = typename EdgeMapT::iterator;
305 164 :
306 : /// A class for ranging over all the edges in the graph.
307 112 : ///
308 112 : /// Like all views in this class it provides methods to get the beginning and
309 224 : /// past the range iterators for the range, as well as methods to determine
310 0 : /// the number of elements in the range and whether the range is empty.
311 224 : template <bool isConst> class EdgeView {
312 : public:
313 28 : using iterator = typename std::conditional<isConst, ConstEdgeIterator,
314 28 : EdgeIterator>::type;
315 56 : using const_iterator = ConstEdgeIterator;
316 0 : using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
317 56 :
318 : private:
319 28 : GraphT &G;
320 28 :
321 56 : public:
322 105 : iterator begin() { return G.Edges.begin(); }
323 56 : iterator end() { return G.Edges.end(); }
324 : const_iterator cbegin() const { return G.Edges.cbegin(); }
325 28 : const_iterator cend() const { return G.Edges.cend(); }
326 28 : const_iterator begin() const { return G.Edges.begin(); }
327 56 : const_iterator end() const { return G.Edges.end(); }
328 0 : size_type size() const { return G.Edges.size(); }
329 56 : bool empty() const { return G.Edges.empty(); }
330 : EdgeView(GraphT &_G) : G(_G) {}
331 28 : };
332 28 :
333 56 : public:
334 0 : // TODO: implement constructor to enable Graph Initialisation.\
335 56 : // Something like:
336 : // Graph<int, int, int> G(
337 : // {1, 2, 3, 4, 5},
338 112 : // {{1, 2}, {2, 3}, {3, 4}});
339 :
340 116 : /// Empty the Graph
341 116 : void clear() {
342 232 : Edges.clear();
343 : Vertices.clear();
344 : InNeighbors.clear();
345 114 : OutNeighbors.clear();
346 : }
347 28 :
348 28 : /// Returns a view object allowing iteration over the vertices of the graph.
349 56 : /// also allows access to the size of the vertex set.
350 : VertexView<false> vertices() { return VertexView<false>(*this); }
351 :
352 28 : VertexView<true> vertices() const { return VertexView<true>(*this); }
353 :
354 28 : /// Returns a view object allowing iteration over the edges of the graph.
355 28 : /// also allows access to the size of the edge set.
356 56 : EdgeView<false> edges() { return EdgeView<false>(*this); }
357 :
358 : EdgeView<true> edges() const { return EdgeView<true>(*this); }
359 28 :
360 : /// Returns a view object allowing iteration over the edges which start at
361 30 : /// a vertex I.
362 30 : InOutEdgeView<false, true> outEdges(const VertexIdentifier I) {
363 60 : return InOutEdgeView<false, true>(*this, I);
364 : }
365 :
366 29 : InOutEdgeView<true, true> outEdges(const VertexIdentifier I) const {
367 : return InOutEdgeView<true, true>(*this, I);
368 30 : }
369 30 :
370 60 : /// 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 29 : return InOutEdgeView<false, false>(*this, I);
374 : }
375 :
376 2 : InOutEdgeView<true, false> inEdges(const VertexIdentifier I) const {
377 : return InOutEdgeView<true, false>(*this, I);
378 807 : }
379 578 :
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 1059 : 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 372 : EdgeAttribute &operator[](const EdgeIdentifier &I) {
390 372 : auto &P = Edges.FindAndConstruct(I);
391 372 : Vertices.FindAndConstruct(I.first);
392 372 : Vertices.FindAndConstruct(I.second);
393 372 : InNeighbors[I.second].insert(I.first);
394 372 : OutNeighbors[I.first].insert(I.second);
395 372 : 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 320 : Expected<const VertexAttribute &> at(const VertexIdentifier &I) const {
409 380 : auto It = Vertices.find(I);
410 320 : if (It == Vertices.end())
411 : return make_error<StringError>(
412 : "Vertex Identifier Does Not Exist",
413 0 : std::make_error_code(std::errc::invalid_argument));
414 320 : return It->second;
415 10 : }
416 0 :
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 212 : 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 69 : /// Inserts a vertex into the graph with Identifier Val.first, and
447 0 : /// Attribute Val.second.
448 : std::pair<VertexIterator, bool>
449 : insert(const std::pair<VertexIdentifier, VertexAttribute> &Val) {
450 : return Vertices.insert(Val);
451 : }
452 10 :
453 0 : 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
|
