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-exception 6 // 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 23 using namespace __sanitizer; 24 using namespace std; 25 26 typedef BasicBitVector<u8> BV1; 27 typedef BasicBitVector<> BV2; 28 typedef TwoLevelBitVector<> BV3; 29 typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4; 30 31 template<class G> 32 void 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 42 class 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 68 template <class BV> 69 void 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 109 TEST(BVGraph, BasicTest) { 110 BasicTest<BV1>(); 111 BasicTest<BV2>(); 112 BasicTest<BV3>(); 113 BasicTest<BV4>(); 114 } 115 116 template <class BV> 117 void 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 156 TEST(BVGraph, RemoveEdges) { 157 RemoveEdges<BV1>(); 158 RemoveEdges<BV2>(); 159 RemoveEdges<BV3>(); 160 RemoveEdges<BV4>(); 161 } 162 163 template <class BV> 164 void 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 213 TEST(BVGraph, isReachable) { 214 Test_isReachable<BV1>(); 215 Test_isReachable<BV2>(); 216 Test_isReachable<BV3>(); 217 Test_isReachable<BV4>(); 218 } 219 220 template <class BV> 221 void 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 // 00000000000000 234 // 00000000000000 235 // 00000000000000 236 // 00000000000000 237 // 00000000000000 238 // 11111010000000 239 // 11111001000000 240 // 11111000100000 241 // 11111000010000 242 // 11111000001000 243 // 11111000000100 244 // 11111000000010 245 // 11111000000001 246 // 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 257 TEST(BVGraph, LongCycle) { 258 LongCycle<BV1>(); 259 LongCycle<BV2>(); 260 LongCycle<BV3>(); 261 LongCycle<BV4>(); 262 } 263 264 template <class BV> 265 void 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=>7 273 // 1=>7 274 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 297 TEST(BVGraph, ShortestPath) { 298 ShortestPath<BV1>(); 299 ShortestPath<BV2>(); 300 ShortestPath<BV3>(); 301 ShortestPath<BV4>(); 302 } 303 304 template <class BV> 305 void 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 336 TEST(BVGraph, AddEdgesTest) { 337 RunAddEdgesTest<BV2>(); 338 } 339