238 lines · 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-exception6//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 GraphT::VertexIdentifier VI;27typedef GraphT::EdgeIdentifier EI;28 29// Test Fixture30template <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({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 57typedef ::testing::Types<GraphT, const GraphT> GraphTestTypes;58 59using VVT = GraphT::VertexValueType;60using EVT = 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_TRUE(llvm::is_contained(llvm::make_first_range(G.vertices()), u));76 consumeError(EVV.takeError());77 }78 79 for (auto &VVT : G.vertices()) {80 EXPECT_EQ(1u, V.count(VVT.first));81 EXPECT_EQ(VA[VVT.first], VVT.second.VA);82 }83}84 85template <typename T> void graphEdgeTester(T &G) {86 std::set<std::pair<unsigned, unsigned>> E(87 {{1u, 2u}, {2u, 3u}, {6u, 3u}, {4u, 6u}, {2u, 4u}, {2u, 5u}, {4u, 5u}});88 std::vector<unsigned> VA({0u, 3u, 5u, 7u, 11u, 13u, 17u});89 90 EXPECT_EQ(E.size(), G.edges().size());91 EXPECT_FALSE(G.edges().empty());92 for (std::pair<unsigned, unsigned> u : E) {93 auto EEV = G.at(u);94 ASSERT_TRUE(!!EEV);95 EXPECT_EQ(1u, G.count(u));96 EXPECT_EQ(VA[u.first] * VA[u.second] * ((u.first > u.second) ? 2 : 1),97 EEV->EA);98 EXPECT_TRUE(llvm::is_contained(llvm::make_first_range(G.edges()), u));99 consumeError(EEV.takeError());100 }101 102 for (auto &EV : G.edges()) {103 EXPECT_EQ(1u, E.count(EV.first));104 EXPECT_EQ(VA[EV.first.first] * VA[EV.first.second] *105 ((EV.first.first > EV.first.second) ? 2 : 1),106 EV.second.EA);107 const auto &IE = G.inEdges(EV.first.second);108 const auto &OE = G.outEdges(EV.first.first);109 EXPECT_NE(IE.size(), 0u);110 EXPECT_NE(OE.size(), 0u);111 EXPECT_NE(IE.begin(), IE.end());112 EXPECT_NE(OE.begin(), OE.end());113 EXPECT_TRUE(llvm::is_contained(114 llvm::make_first_range(G.inEdges(EV.first.second)), EV.first));115 EXPECT_FALSE(llvm::is_contained(116 llvm::make_first_range(G.inEdges(EV.first.first)), EV.first));117 EXPECT_FALSE(llvm::is_contained(118 llvm::make_first_range(G.outEdges(EV.first.second)), EV.first));119 EXPECT_TRUE(llvm::is_contained(120 llvm::make_first_range(G.outEdges(EV.first.first)), EV.first));121 }122}123 124TYPED_TEST(GraphTest, TestGraphEdge) {125 auto &G = this->Graph;126 127 graphEdgeTester(G);128}129 130TYPED_TEST(GraphTest, TestGraphVertex) {131 auto &G = this->Graph;132 133 graphVertexTester(G);134}135 136TYPED_TEST(GraphTest, TestCopyConstructor) {137 TypeParam G(this->Graph);138 139 graphEdgeTester(G);140 graphVertexTester(G);141}142 143TYPED_TEST(GraphTest, TestCopyAssign) {144 TypeParam G = this->Graph;145 146 graphEdgeTester(G);147 graphVertexTester(G);148}149 150TYPED_TEST(GraphTest, TestMoveConstructor) {151 TypeParam G(std::move(this->Graph));152 153 graphEdgeTester(G);154 graphVertexTester(G);155}156 157// Tests the incremental Construction of a graph158TEST(GraphTest, TestConstruction) {159 GraphT MG;160 const GraphT &G = MG;161 EXPECT_EQ(0u, G.count(0u));162 EXPECT_EQ(0u, G.count({0u, 1u}));163 auto VE = G.at(0);164 auto EE = G.at({0, 0});165 EXPECT_FALSE(VE); // G.at[0] returns an error166 EXPECT_FALSE(EE); // G.at[{0,0}] returns an error167 consumeError(VE.takeError());168 consumeError(EE.takeError());169 EXPECT_TRUE(G.vertices().empty());170 EXPECT_TRUE(G.edges().empty());171 EXPECT_EQ(G.vertices().begin(), G.vertices().end());172 EXPECT_EQ(G.edges().begin(), G.edges().end());173}174 175TEST(GraphTest, TestiVertexAccessOperator) {176 GraphT MG;177 const GraphT &G = MG;178 179 MG[0u] = {1u};180 EXPECT_EQ(1u, MG[0u].VA);181 EXPECT_EQ(1u, G.count(0u));182 EXPECT_EQ(0u, G.count(1u));183 EXPECT_EQ(1u, MG[0u].VA);184 auto T = G.at(0u);185 EXPECT_TRUE(!!T);186 EXPECT_EQ(1u, T->VA);187 188 EXPECT_EQ(1u, G.vertices().size());189 EXPECT_EQ(0u, G.edges().size());190 EXPECT_FALSE(G.vertices().empty());191 EXPECT_TRUE(G.edges().empty());192 EXPECT_NE(G.vertices().begin(), G.vertices().end());193 EXPECT_EQ(G.edges().begin(), G.edges().end());194 EXPECT_EQ(1u, G.vertices().begin()->second.VA);195 EXPECT_EQ(0u, G.vertices().begin()->first);196 EXPECT_EQ(0u, G.outEdges(0u).size());197 EXPECT_TRUE(G.outEdges(0u).empty());198 EXPECT_EQ(G.outEdges(0u).begin(), G.outEdges(0u).end());199 EXPECT_EQ(0u, G.inEdges(0u).size());200 EXPECT_TRUE(G.inEdges(0u).empty());201 EXPECT_EQ(G.inEdges(0u).begin(), G.inEdges(0u).end());202}203 204TEST(GraphTest, TestEdgeAccessOperator) {205 GraphT MG;206 const GraphT &G = MG;207 208 MG[{0u, 0u}] = {2u};209 EI EdgeIdent({0u, 0u});210 EXPECT_EQ(2u, MG[EdgeIdent].EA);211 EXPECT_EQ(1u, G.count({0u, 0u}));212 EXPECT_EQ(0u, G.count({0u, 1u}));213 EXPECT_EQ(1u, G.count(0u));214 EXPECT_NE(1u, G.count(1u));215 auto T = G.at({0u, 0u});216 EXPECT_TRUE(T && T->EA == 2u);217 EXPECT_EQ(1u, G.edges().size());218 EXPECT_EQ(1u, G.vertices().size());219 EXPECT_FALSE(G.edges().empty());220 EXPECT_FALSE(G.vertices().empty());221 EXPECT_NE(G.edges().begin(), G.edges().end());222 EXPECT_EQ(EI(0u, 0u), G.edges().begin()->first);223 EXPECT_EQ(2u, G.edges().begin()->second.EA);224 EXPECT_EQ(1u, G.outEdges(0u).size());225 EXPECT_FALSE(G.outEdges(0u).empty());226 EXPECT_NE(G.outEdges(0u).begin(), G.outEdges(0u).end());227 EXPECT_EQ(EI(0u, 0u), G.outEdges(0u).begin()->first);228 EXPECT_EQ(2u, G.outEdges(0u).begin()->second.EA);229 EXPECT_EQ(++(G.outEdges(0u).begin()), G.outEdges(0u).end());230 EXPECT_EQ(1u, G.inEdges(0u).size());231 EXPECT_FALSE(G.inEdges(0u).empty());232 EXPECT_NE(G.inEdges(0u).begin(), G.inEdges(0u).end());233 EXPECT_EQ(EI(0u, 0u), G.inEdges(0u).begin()->first);234 EXPECT_EQ(2u, G.inEdges(0u).begin()->second.EA);235 EXPECT_EQ(++(G.inEdges(0u).begin()), G.inEdges(0u).end());236}237}238