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
15using namespace llvm;
16using namespace xray;
17
18namespace {
19struct VAttr {
20 unsigned VA;
21};
22struct EAttr {
23 unsigned EA;
24};
25typedef Graph<VAttr, EAttr, unsigned> GraphT;
26typedef typename GraphT::VertexIdentifier VI;
27typedef typename GraphT::EdgeIdentifier EI;
28
29// Test Fixture
30template <typename T> class GraphTest : public testing::Test {
31protected:
32 T Graph = getTestGraph();
33
34private:
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
57typedef ::testing::Types<GraphT, const GraphT> GraphTestTypes;
58
59using VVT = typename GraphT::VertexValueType;
60using EVT = typename GraphT::EdgeValueType;
61
62TYPED_TEST_SUITE(GraphTest, GraphTestTypes, );
63
64template <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
87template <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
147TYPED_TEST(GraphTest, TestGraphEdge) {
148 auto &G = this->Graph;
149
150 graphEdgeTester(G);
151}
152
153TYPED_TEST(GraphTest, TestGraphVertex) {
154 auto &G = this->Graph;
155
156 graphVertexTester(G);
157}
158
159TYPED_TEST(GraphTest, TestCopyConstructor) {
160 TypeParam G(this->Graph);
161
162 graphEdgeTester(G);
163 graphVertexTester(G);
164}
165
166TYPED_TEST(GraphTest, TestCopyAssign) {
167 TypeParam G = this->Graph;
168
169 graphEdgeTester(G);
170 graphVertexTester(G);
171}
172
173TYPED_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
181TEST(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
198TEST(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
227TEST(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

source code of llvm/unittests/XRay/GraphTest.cpp