unittests/XRay/GraphTest.cpp

   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     typename std::remove_const<T>::type 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 }