1 //===- llvm/unittest/XRay/GraphTest.cpp - XRay Graph unit tests -*- 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 #include "llvm/XRay/Graph.h"
11 #include "gtest/gtest.h"
12 #include <iostream>
13 #include <set>
14 #include <type_traits>
15
16 using namespace llvm;
17 using namespace xray;
18
19 namespace {
20 struct VAttr {
21 unsigned VA;
22 };
23 struct EAttr {
24 unsigned EA;
25 };
26 typedef Graph<VAttr, EAttr, unsigned> GraphT;
27 typedef typename GraphT::VertexIdentifier VI;
28 typedef typename GraphT::EdgeIdentifier EI;
29
30 // Test Fixture
31 template <typename T> class GraphTest : public testing::Test {
32 protected:
33 T Graph = getTestGraph();
34
35 private:
getTestGraph()36 static T getTestGraph() {
37 using std::make_pair;
38 typename std::remove_const<T>::type G;
39 G.insert(make_pair(1u, VAttr({3u})));
40 G.insert(make_pair(2u, VAttr({5u})));
41 G.insert(make_pair(3u, VAttr({7u})));
42 G.insert(make_pair(4u, VAttr({11u})));
43 G.insert(make_pair(5u, VAttr({13u})));
44 G.insert(make_pair(6u, VAttr({17u})));
45
46 G.insert(std::make_pair(EI(1u, 2u), EAttr({3u * 5u})));
47 G.insert(std::make_pair(EI(2u, 3u), EAttr({5u * 7u})));
48 G.insert(std::make_pair(EI(6u, 3u), EAttr({2u * 7u * 17u})));
49 G.insert(std::make_pair(EI(4u, 6u), EAttr({11u * 17u})));
50 G.insert(std::make_pair(EI(2u, 4u), EAttr({5u * 11u})));
51 G.insert(std::make_pair(EI(2u, 5u), EAttr({5u * 13u})));
52 G.insert(std::make_pair(EI(4u, 5u), EAttr({11u * 13u})));
53
54 return G;
55 }
56 };
57
58 typedef ::testing::Types<GraphT, const GraphT> GraphTestTypes;
59
60 using VVT = typename GraphT::VertexValueType;
61 using EVT = typename GraphT::EdgeValueType;
62
63 TYPED_TEST_CASE(GraphTest, GraphTestTypes);
64
graphVertexTester(T & G)65 template <typename T> void graphVertexTester(T &G) {
66 std::set<unsigned> V({1u, 2u, 3u, 4u, 5u, 6u});
67 std::vector<unsigned> VA({0u, 3u, 5u, 7u, 11u, 13u, 17u});
68
69 EXPECT_EQ(V.size(), G.vertices().size());
70 EXPECT_FALSE(G.vertices().empty());
71 for (unsigned u : V) {
72 auto EVV = G.at(u);
73 ASSERT_TRUE(!!EVV);
74 EXPECT_EQ(1u, G.count(u));
75 EXPECT_EQ(VA[u], EVV->VA);
76 EXPECT_NE(G.vertices().end(),
77 std::find_if(G.vertices().begin(), G.vertices().end(),
78 [&](const VVT &VV) { return VV.first == u; }));
79 consumeError(EVV.takeError());
80 }
81
82 for (auto &VVT : G.vertices()) {
83 EXPECT_EQ(1u, V.count(VVT.first));
84 EXPECT_EQ(VA[VVT.first], VVT.second.VA);
85 }
86 }
87
graphEdgeTester(T & G)88 template <typename T> void graphEdgeTester(T &G) {
89 std::set<unsigned> V({1u, 2u, 3u, 4u, 5u, 6u});
90
91 std::set<std::pair<unsigned, unsigned>> E(
92 {{1u, 2u}, {2u, 3u}, {6u, 3u}, {4u, 6u}, {2u, 4u}, {2u, 5u}, {4u, 5u}});
93 std::vector<unsigned> VA({0u, 3u, 5u, 7u, 11u, 13u, 17u});
94
95 EXPECT_EQ(E.size(), G.edges().size());
96 EXPECT_FALSE(G.edges().empty());
97 for (std::pair<unsigned, unsigned> u : E) {
98 auto EEV = G.at(u);
99 ASSERT_TRUE(!!EEV);
100 EXPECT_EQ(1u, G.count(u));
101 EXPECT_EQ(VA[u.first] * VA[u.second] * ((u.first > u.second) ? 2 : 1),
102 EEV->EA);
103 auto Pred = [&](const EVT &EV) { return EV.first == u; };
104 EXPECT_NE(G.edges().end(),
105 std::find_if(G.edges().begin(), G.edges().end(), Pred));
106 consumeError(EEV.takeError());
107 }
108
109 for (auto &EV : G.edges()) {
110 EXPECT_EQ(1u, E.count(EV.first));
111 EXPECT_EQ(VA[EV.first.first] * VA[EV.first.second] *
112 ((EV.first.first > EV.first.second) ? 2 : 1),
113 EV.second.EA);
114 const auto &IE = G.inEdges(EV.first.second);
115 const auto &OE = G.outEdges(EV.first.first);
116 EXPECT_NE(IE.size(), 0u);
117 EXPECT_NE(OE.size(), 0u);
118 EXPECT_NE(IE.begin(), IE.end());
119 EXPECT_NE(OE.begin(), OE.end());
120 {
121 auto It = std::find_if(
122 G.inEdges(EV.first.second).begin(), G.inEdges(EV.first.second).end(),
123 [&](const EVT &EVI) { return EVI.first == EV.first; });
124 EXPECT_NE(G.inEdges(EV.first.second).end(), It);
125 }
126 {
127 auto It = std::find_if(
128 G.inEdges(EV.first.first).begin(), G.inEdges(EV.first.first).end(),
129 [&](const EVT &EVI) { return EVI.first == EV.first; });
130 EXPECT_EQ(G.inEdges(EV.first.first).end(), It);
131 }
132 {
133 auto It =
134 std::find_if(G.outEdges(EV.first.second).begin(),
135 G.outEdges(EV.first.second).end(),
136 [&](const EVT &EVI) { return EVI.first == EV.first; });
137 EXPECT_EQ(G.outEdges(EV.first.second).end(), It);
138 }
139 {
140 auto It = std::find_if(
141 G.outEdges(EV.first.first).begin(), G.outEdges(EV.first.first).end(),
142 [&](const EVT &EVI) { return EVI.first == EV.first; });
143 EXPECT_NE(G.outEdges(EV.first.first).end(), It);
144 }
145 }
146 }
147
TYPED_TEST(GraphTest,TestGraphEdge)148 TYPED_TEST(GraphTest, TestGraphEdge) {
149 auto &G = this->Graph;
150
151 graphEdgeTester(G);
152 }
153
TYPED_TEST(GraphTest,TestGraphVertex)154 TYPED_TEST(GraphTest, TestGraphVertex) {
155 auto &G = this->Graph;
156
157 graphVertexTester(G);
158 }
159
TYPED_TEST(GraphTest,TestCopyConstructor)160 TYPED_TEST(GraphTest, TestCopyConstructor) {
161 TypeParam G(this->Graph);
162
163 graphEdgeTester(G);
164 graphVertexTester(G);
165 }
166
TYPED_TEST(GraphTest,TestCopyAssign)167 TYPED_TEST(GraphTest, TestCopyAssign) {
168 TypeParam G = this->Graph;
169
170 graphEdgeTester(G);
171 graphVertexTester(G);
172 }
173
TYPED_TEST(GraphTest,TestMoveConstructor)174 TYPED_TEST(GraphTest, TestMoveConstructor) {
175 TypeParam G(std::move(this->Graph));
176
177 graphEdgeTester(G);
178 graphVertexTester(G);
179 }
180
181 // Tests the incremental Construction of a graph
TEST(GraphTest,TestConstruction)182 TEST(GraphTest, TestConstruction) {
183 GraphT MG;
184 const GraphT &G = MG;
185 EXPECT_EQ(0u, G.count(0u));
186 EXPECT_EQ(0u, G.count({0u, 1u}));
187 auto VE = G.at(0);
188 auto EE = G.at({0, 0});
189 EXPECT_FALSE(VE); // G.at[0] returns an error
190 EXPECT_FALSE(EE); // G.at[{0,0}] returns an error
191 consumeError(VE.takeError());
192 consumeError(EE.takeError());
193 EXPECT_TRUE(G.vertices().empty());
194 EXPECT_TRUE(G.edges().empty());
195 EXPECT_EQ(G.vertices().begin(), G.vertices().end());
196 EXPECT_EQ(G.edges().begin(), G.edges().end());
197 }
198
TEST(GraphTest,TestiVertexAccessOperator)199 TEST(GraphTest, TestiVertexAccessOperator) {
200 GraphT MG;
201 const GraphT &G = MG;
202
203 MG[0u] = {1u};
204 EXPECT_EQ(1u, MG[0u].VA);
205 EXPECT_EQ(1u, G.count(0u));
206 EXPECT_EQ(0u, G.count(1u));
207 EXPECT_EQ(1u, MG[0u].VA);
208 auto T = G.at(0u);
209 EXPECT_TRUE(!!T);
210 EXPECT_EQ(1u, T->VA);
211
212 EXPECT_EQ(1u, G.vertices().size());
213 EXPECT_EQ(0u, G.edges().size());
214 EXPECT_FALSE(G.vertices().empty());
215 EXPECT_TRUE(G.edges().empty());
216 EXPECT_NE(G.vertices().begin(), G.vertices().end());
217 EXPECT_EQ(G.edges().begin(), G.edges().end());
218 EXPECT_EQ(1u, G.vertices().begin()->second.VA);
219 EXPECT_EQ(0u, G.vertices().begin()->first);
220 EXPECT_EQ(0u, G.outEdges(0u).size());
221 EXPECT_TRUE(G.outEdges(0u).empty());
222 EXPECT_EQ(G.outEdges(0u).begin(), G.outEdges(0u).end());
223 EXPECT_EQ(0u, G.inEdges(0u).size());
224 EXPECT_TRUE(G.inEdges(0u).empty());
225 EXPECT_EQ(G.inEdges(0u).begin(), G.inEdges(0u).end());
226 }
227
TEST(GraphTest,TestEdgeAccessOperator)228 TEST(GraphTest, TestEdgeAccessOperator) {
229 GraphT MG;
230 const GraphT &G = MG;
231
232 MG[{0u, 0u}] = {2u};
233 EI EdgeIdent({0u, 0u});
234 EXPECT_EQ(2u, MG[EdgeIdent].EA);
235 EXPECT_EQ(1u, G.count({0u, 0u}));
236 EXPECT_EQ(0u, G.count({0u, 1u}));
237 EXPECT_EQ(1u, G.count(0u));
238 EXPECT_NE(1u, G.count(1u));
239 auto T = G.at({0u, 0u});
240 EXPECT_TRUE(T && T->EA == 2u);
241 EXPECT_EQ(1u, G.edges().size());
242 EXPECT_EQ(1u, G.vertices().size());
243 EXPECT_FALSE(G.edges().empty());
244 EXPECT_FALSE(G.vertices().empty());
245 EXPECT_NE(G.edges().begin(), G.edges().end());
246 EXPECT_EQ(EI(0u, 0u), G.edges().begin()->first);
247 EXPECT_EQ(2u, G.edges().begin()->second.EA);
248 EXPECT_EQ(1u, G.outEdges(0u).size());
249 EXPECT_FALSE(G.outEdges(0u).empty());
250 EXPECT_NE(G.outEdges(0u).begin(), G.outEdges(0u).end());
251 EXPECT_EQ(EI(0u, 0u), G.outEdges(0u).begin()->first);
252 EXPECT_EQ(2u, G.outEdges(0u).begin()->second.EA);
253 EXPECT_EQ(++(G.outEdges(0u).begin()), G.outEdges(0u).end());
254 EXPECT_EQ(1u, G.inEdges(0u).size());
255 EXPECT_FALSE(G.inEdges(0u).empty());
256 EXPECT_NE(G.inEdges(0u).begin(), G.inEdges(0u).end());
257 EXPECT_EQ(EI(0u, 0u), G.inEdges(0u).begin()->first);
258 EXPECT_EQ(2u, G.inEdges(0u).begin()->second.EA);
259 EXPECT_EQ(++(G.inEdges(0u).begin()), G.inEdges(0u).end());
260 }
261 }
262