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