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 | |
26 | namespace llvm { |
27 | namespace 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 | /// |
72 | template <typename VertexAttribute, typename EdgeAttribute, |
73 | typename VI = int32_t> |
74 | class Graph { |
75 | public: |
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 | |
91 | private: |
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 | |
109 | private: |
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 | |
170 | public: |
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 | |
332 | public: |
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 | |