339 lines · cpp
1//===-- sanitizer_bvgraph_test.cpp ----------------------------------------===//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// This file is a part of Sanitizer runtime.10// Tests for sanitizer_bvgraph.h.11//12//===----------------------------------------------------------------------===//13#include "sanitizer_common/sanitizer_bvgraph.h"14 15#include "sanitizer_test_utils.h"16 17#include "gtest/gtest.h"18 19#include <algorithm>20#include <vector>21#include <set>22 23using namespace __sanitizer;24using namespace std;25 26typedef BasicBitVector<u8> BV1;27typedef BasicBitVector<> BV2;28typedef TwoLevelBitVector<> BV3;29typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;30 31template<class G>32void PrintGraph(const G &g) {33 for (uptr i = 0; i < g.size(); i++) {34 for (uptr j = 0; j < g.size(); j++) {35 fprintf(stderr, "%d", g.hasEdge(i, j));36 }37 fprintf(stderr, "\n");38 }39}40 41 42class SimpleGraph {43 public:44 void clear() { s_.clear(); }45 bool addEdge(uptr from, uptr to) {46 return s_.insert(idx(from, to)).second;47 }48 bool removeEdge(uptr from, uptr to) {49 return s_.erase(idx(from, to));50 }51 template <class G>52 void checkSameAs(G *g) {53 for (set<uptr>::iterator it = s_.begin(); it != s_.end(); ++it) {54 uptr from = *it >> 16;55 uptr to = *it & ((1 << 16) - 1);56 EXPECT_TRUE(g->removeEdge(from, to));57 }58 EXPECT_TRUE(g->empty());59 }60 private:61 uptr idx(uptr from, uptr to) {62 CHECK_LE(from|to, 1 << 16);63 return (from << 16) + to;64 }65 set<uptr> s_;66};67 68template <class BV>69void BasicTest() {70 BVGraph<BV> g;71 g.clear();72 BV target;73 SimpleGraph s_g;74 set<uptr> s;75 set<uptr> s_target;76 int num_reachable = 0;77 for (int it = 0; it < 1000; it++) {78 target.clear();79 s_target.clear();80 for (int t = 0; t < 4; t++) {81 uptr idx = (uptr)my_rand() % g.size();82 EXPECT_EQ(target.setBit(idx), s_target.insert(idx).second);83 }84 uptr from = my_rand() % g.size();85 uptr to = my_rand() % g.size();86 EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to));87 EXPECT_TRUE(g.hasEdge(from, to));88 for (int i = 0; i < 10; i++) {89 from = my_rand() % g.size();90 bool is_reachable = g.isReachable(from, target);91 if (is_reachable) {92 uptr path[BV::kSize];93 uptr len;94 for (len = 1; len < BV::kSize; len++) {95 if (g.findPath(from, target, path, len) == len)96 break;97 }98 EXPECT_LT(len, BV::kSize);99 EXPECT_TRUE(target.getBit(path[len - 1]));100 // fprintf(stderr, "reachable: %zd; path %zd {%zd %zd %zd}\n",101 // from, len, path[0], path[1], path[2]);102 num_reachable++;103 }104 }105 }106 EXPECT_GT(num_reachable, 0);107}108 109TEST(BVGraph, BasicTest) {110 BasicTest<BV1>();111 BasicTest<BV2>();112 BasicTest<BV3>();113 BasicTest<BV4>();114}115 116template <class BV>117void RemoveEdges() {118 SimpleGraph s_g;119 BVGraph<BV> g;120 g.clear();121 BV bv;122 set<uptr> s;123 for (int it = 0; it < 100; it++) {124 s.clear();125 bv.clear();126 s_g.clear();127 g.clear();128 for (uptr j = 0; j < g.size() * 2; j++) {129 uptr from = my_rand() % g.size();130 uptr to = my_rand() % g.size();131 EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to));132 }133 for (uptr j = 0; j < 5; j++) {134 uptr idx = my_rand() % g.size();135 s.insert(idx);136 bv.setBit(idx);137 }138 139 if (it % 2) {140 g.removeEdgesFrom(bv);141 for (set<uptr>::iterator from = s.begin(); from != s.end(); ++from) {142 for (uptr to = 0; to < g.size(); to++)143 s_g.removeEdge(*from, to);144 }145 } else {146 g.removeEdgesTo(bv);147 for (set<uptr>::iterator to = s.begin(); to != s.end(); ++to) {148 for (uptr from = 0; from < g.size(); from++)149 s_g.removeEdge(from, *to);150 }151 }152 s_g.checkSameAs(&g);153 }154}155 156TEST(BVGraph, RemoveEdges) {157 RemoveEdges<BV1>();158 RemoveEdges<BV2>();159 RemoveEdges<BV3>();160 RemoveEdges<BV4>();161}162 163template <class BV>164void Test_isReachable() {165 uptr path[5];166 BVGraph<BV> g;167 g.clear();168 BV target;169 target.clear();170 uptr t0 = 0;171 uptr t1 = g.size() - 1;172 target.setBit(t0);173 target.setBit(t1);174 175 uptr f0 = 1;176 uptr f1 = 2;177 uptr f2 = g.size() / 2;178 uptr f3 = g.size() - 2;179 180 EXPECT_FALSE(g.isReachable(f0, target));181 EXPECT_FALSE(g.isReachable(f1, target));182 EXPECT_FALSE(g.isReachable(f2, target));183 EXPECT_FALSE(g.isReachable(f3, target));184 185 g.addEdge(f0, f1);186 g.addEdge(f1, f2);187 g.addEdge(f2, f3);188 EXPECT_FALSE(g.isReachable(f0, target));189 EXPECT_FALSE(g.isReachable(f1, target));190 EXPECT_FALSE(g.isReachable(f2, target));191 EXPECT_FALSE(g.isReachable(f3, target));192 193 g.addEdge(f1, t0);194 EXPECT_TRUE(g.isReachable(f0, target));195 EXPECT_TRUE(g.isReachable(f1, target));196 EXPECT_FALSE(g.isReachable(f2, target));197 EXPECT_FALSE(g.isReachable(f3, target));198 EXPECT_EQ(g.findPath(f0, target, path, ARRAY_SIZE(path)), 3U);199 EXPECT_EQ(path[0], f0);200 EXPECT_EQ(path[1], f1);201 EXPECT_EQ(path[2], t0);202 EXPECT_EQ(g.findPath(f1, target, path, ARRAY_SIZE(path)), 2U);203 EXPECT_EQ(path[0], f1);204 EXPECT_EQ(path[1], t0);205 206 g.addEdge(f3, t1);207 EXPECT_TRUE(g.isReachable(f0, target));208 EXPECT_TRUE(g.isReachable(f1, target));209 EXPECT_TRUE(g.isReachable(f2, target));210 EXPECT_TRUE(g.isReachable(f3, target));211}212 213TEST(BVGraph, isReachable) {214 Test_isReachable<BV1>();215 Test_isReachable<BV2>();216 Test_isReachable<BV3>();217 Test_isReachable<BV4>();218}219 220template <class BV>221void LongCycle() {222 BVGraph<BV> g;223 g.clear();224 vector<uptr> path_vec(g.size());225 uptr *path = path_vec.data();226 uptr start = 5;227 for (uptr i = start; i < g.size() - 1; i++) {228 g.addEdge(i, i + 1);229 for (uptr j = 0; j < start; j++)230 g.addEdge(i, j);231 }232 // Bad graph that looks like this:233 // 00000000000000234 // 00000000000000235 // 00000000000000236 // 00000000000000237 // 00000000000000238 // 11111010000000239 // 11111001000000240 // 11111000100000241 // 11111000010000242 // 11111000001000243 // 11111000000100244 // 11111000000010245 // 11111000000001246 // if (g.size() <= 64) PrintGraph(g);247 BV target;248 for (uptr i = start + 1; i < g.size(); i += 11) {249 // if ((i & (i - 1)) == 0) fprintf(stderr, "Path: : %zd\n", i);250 target.clear();251 target.setBit(i);252 EXPECT_TRUE(g.isReachable(start, target));253 EXPECT_EQ(g.findPath(start, target, path, g.size()), i - start + 1);254 }255}256 257TEST(BVGraph, LongCycle) {258 LongCycle<BV1>();259 LongCycle<BV2>();260 LongCycle<BV3>();261 LongCycle<BV4>();262}263 264template <class BV>265void ShortestPath() {266 uptr path[8];267 BVGraph<BV> g;268 g.clear();269 BV t7;270 t7.clear();271 t7.setBit(7);272 // 1=>2=>3=>4=>5=>6=>7273 // 1=>7274 g.addEdge(1, 2);275 g.addEdge(2, 3);276 g.addEdge(3, 4);277 g.addEdge(4, 5);278 g.addEdge(5, 6);279 g.addEdge(6, 7);280 g.addEdge(1, 7);281 EXPECT_TRUE(g.isReachable(1, t7));282 // No path of length 1.283 EXPECT_EQ(0U, g.findPath(1, t7, path, 1));284 // Trying to find a path of len 2..6 gives path of len 2.285 EXPECT_EQ(2U, g.findPath(1, t7, path, 2));286 EXPECT_EQ(2U, g.findPath(1, t7, path, 3));287 EXPECT_EQ(2U, g.findPath(1, t7, path, 4));288 EXPECT_EQ(2U, g.findPath(1, t7, path, 5));289 EXPECT_EQ(2U, g.findPath(1, t7, path, 6));290 // Trying to find a path of len 7 gives path of len 7, because this is DFS.291 EXPECT_EQ(7U, g.findPath(1, t7, path, 7));292 // But findShortestPath will find the shortest path.293 EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 2));294 EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 7));295}296 297TEST(BVGraph, ShortestPath) {298 ShortestPath<BV1>();299 ShortestPath<BV2>();300 ShortestPath<BV3>();301 ShortestPath<BV4>();302}303 304template <class BV>305void RunAddEdgesTest() {306 BVGraph<BV> g;307 BV from;308 const int kMaxEdges = 10;309 uptr added_edges[kMaxEdges];310 g.clear();311 from.clear();312 EXPECT_EQ(0U, g.addEdges(from, 0, added_edges, kMaxEdges));313 EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges));314 from.setBit(0);315 EXPECT_EQ(1U, g.addEdges(from, 1, added_edges, kMaxEdges));316 EXPECT_EQ(0U, added_edges[0]);317 EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges));318 319 from.clear();320 from.setBit(1);321 EXPECT_EQ(1U, g.addEdges(from, 4, added_edges, kMaxEdges));322 EXPECT_TRUE(g.hasEdge(1, 4));323 EXPECT_FALSE(g.hasEdge(1, 5));324 EXPECT_EQ(1U, added_edges[0]);325 from.setBit(2);326 from.setBit(3);327 EXPECT_EQ(2U, g.addEdges(from, 4, added_edges, kMaxEdges));328 EXPECT_TRUE(g.hasEdge(2, 4));329 EXPECT_FALSE(g.hasEdge(2, 5));330 EXPECT_TRUE(g.hasEdge(3, 4));331 EXPECT_FALSE(g.hasEdge(3, 5));332 EXPECT_EQ(2U, added_edges[0]);333 EXPECT_EQ(3U, added_edges[1]);334}335 336TEST(BVGraph, AddEdgesTest) {337 RunAddEdgesTest<BV2>();338}339