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({3u})));
39     G.insert(make_pair(2u, VAttr({5u})));
40     G.insert(make_pair(3u, VAttr({7u})));
41     G.insert(make_pair(4u, VAttr({11u})));
42     G.insert(make_pair(5u, VAttr({13u})));
43     G.insert(make_pair(6u, VAttr({17u})));
44 
45     G.insert(std::make_pair(EI(1u, 2u), EAttr({3u * 5u})));
46     G.insert(std::make_pair(EI(2u, 3u), EAttr({5u * 7u})));
47     G.insert(std::make_pair(EI(6u, 3u), EAttr({2u * 7u * 17u})));
48     G.insert(std::make_pair(EI(4u, 6u), EAttr({11u * 17u})));
49     G.insert(std::make_pair(EI(2u, 4u), EAttr({5u * 11u})));
50     G.insert(std::make_pair(EI(2u, 5u), EAttr({5u * 13u})));
51     G.insert(std::make_pair(EI(4u, 5u), EAttr({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_CASE(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(0);
187   auto EE = G.at({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(VE.takeError());
191   consumeError(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] = {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(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}] = {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({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