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: 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 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 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 148 TYPED_TEST(GraphTest, TestGraphEdge) { 149 auto &G = this->Graph; 150 151 graphEdgeTester(G); 152 } 153 154 TYPED_TEST(GraphTest, TestGraphVertex) { 155 auto &G = this->Graph; 156 157 graphVertexTester(G); 158 } 159 160 TYPED_TEST(GraphTest, TestCopyConstructor) { 161 TypeParam G(this->Graph); 162 163 graphEdgeTester(G); 164 graphVertexTester(G); 165 } 166 167 TYPED_TEST(GraphTest, TestCopyAssign) { 168 TypeParam G = this->Graph; 169 170 graphEdgeTester(G); 171 graphVertexTester(G); 172 } 173 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 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 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 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
