1 //===-- sanitizer_bvgraph_test.cc -----------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file is a part of Sanitizer runtime.
11 // Tests for sanitizer_bvgraph.h.
13 //===----------------------------------------------------------------------===//
14 #include "sanitizer_common/sanitizer_bvgraph.h"
16 #include "sanitizer_test_utils.h"
18 #include "gtest/gtest.h"
24 using namespace __sanitizer;
27 typedef BasicBitVector<u8> BV1;
28 typedef BasicBitVector<> BV2;
29 typedef TwoLevelBitVector<> BV3;
30 typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;
33 void PrintGraph(const G &g) {
34 for (uptr i = 0; i < g.size(); i++) {
35 for (uptr j = 0; j < g.size(); j++) {
36 fprintf(stderr, "%d", g.hasEdge(i, j));
38 fprintf(stderr, "\n");
45 void clear() { s_.clear(); }
46 bool addEdge(uptr from, uptr to) {
47 return s_.insert(idx(from, to)).second;
49 bool removeEdge(uptr from, uptr to) {
50 return s_.erase(idx(from, to));
53 void checkSameAs(G *g) {
54 for (set<uptr>::iterator it = s_.begin(); it != s_.end(); ++it) {
55 uptr from = *it >> 16;
56 uptr to = *it & ((1 << 16) - 1);
57 EXPECT_TRUE(g->removeEdge(from, to));
59 EXPECT_TRUE(g->empty());
62 uptr idx(uptr from, uptr to) {
63 CHECK_LE(from|to, 1 << 16);
64 return (from << 16) + to;
77 int num_reachable = 0;
78 for (int it = 0; it < 1000; it++) {
81 for (int t = 0; t < 4; t++) {
82 uptr idx = (uptr)my_rand() % g.size();
83 EXPECT_EQ(target.setBit(idx), s_target.insert(idx).second);
85 uptr from = my_rand() % g.size();
86 uptr to = my_rand() % g.size();
87 EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to));
88 EXPECT_TRUE(g.hasEdge(from, to));
89 for (int i = 0; i < 10; i++) {
90 from = my_rand() % g.size();
91 bool is_reachable = g.isReachable(from, target);
95 for (len = 1; len < BV::kSize; len++) {
96 if (g.findPath(from, target, path, len) == len)
99 EXPECT_LT(len, BV::kSize);
100 EXPECT_TRUE(target.getBit(path[len - 1]));
101 // fprintf(stderr, "reachable: %zd; path %zd {%zd %zd %zd}\n",
102 // from, len, path[0], path[1], path[2]);
107 EXPECT_GT(num_reachable, 0);
110 TEST(BVGraph, BasicTest) {
124 for (int it = 0; it < 100; it++) {
129 for (uptr j = 0; j < g.size() * 2; j++) {
130 uptr from = my_rand() % g.size();
131 uptr to = my_rand() % g.size();
132 EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to));
134 for (uptr j = 0; j < 5; j++) {
135 uptr idx = my_rand() % g.size();
141 g.removeEdgesFrom(bv);
142 for (set<uptr>::iterator from = s.begin(); from != s.end(); ++from) {
143 for (uptr to = 0; to < g.size(); to++)
144 s_g.removeEdge(*from, to);
148 for (set<uptr>::iterator to = s.begin(); to != s.end(); ++to) {
149 for (uptr from = 0; from < g.size(); from++)
150 s_g.removeEdge(from, *to);
157 TEST(BVGraph, RemoveEdges) {
165 void Test_isReachable() {
172 uptr t1 = g.size() - 1;
178 uptr f2 = g.size() / 2;
179 uptr f3 = g.size() - 2;
181 EXPECT_FALSE(g.isReachable(f0, target));
182 EXPECT_FALSE(g.isReachable(f1, target));
183 EXPECT_FALSE(g.isReachable(f2, target));
184 EXPECT_FALSE(g.isReachable(f3, target));
189 EXPECT_FALSE(g.isReachable(f0, target));
190 EXPECT_FALSE(g.isReachable(f1, target));
191 EXPECT_FALSE(g.isReachable(f2, target));
192 EXPECT_FALSE(g.isReachable(f3, target));
195 EXPECT_TRUE(g.isReachable(f0, target));
196 EXPECT_TRUE(g.isReachable(f1, target));
197 EXPECT_FALSE(g.isReachable(f2, target));
198 EXPECT_FALSE(g.isReachable(f3, target));
199 EXPECT_EQ(g.findPath(f0, target, path, ARRAY_SIZE(path)), 3U);
200 EXPECT_EQ(path[0], f0);
201 EXPECT_EQ(path[1], f1);
202 EXPECT_EQ(path[2], t0);
203 EXPECT_EQ(g.findPath(f1, target, path, ARRAY_SIZE(path)), 2U);
204 EXPECT_EQ(path[0], f1);
205 EXPECT_EQ(path[1], t0);
208 EXPECT_TRUE(g.isReachable(f0, target));
209 EXPECT_TRUE(g.isReachable(f1, target));
210 EXPECT_TRUE(g.isReachable(f2, target));
211 EXPECT_TRUE(g.isReachable(f3, target));
214 TEST(BVGraph, isReachable) {
215 Test_isReachable<BV1>();
216 Test_isReachable<BV2>();
217 Test_isReachable<BV3>();
218 Test_isReachable<BV4>();
225 vector<uptr> path_vec(g.size());
226 uptr *path = path_vec.data();
228 for (uptr i = start; i < g.size() - 1; i++) {
230 for (uptr j = 0; j < start; j++)
233 // Bad graph that looks like this:
247 // if (g.size() <= 64) PrintGraph(g);
249 for (uptr i = start + 1; i < g.size(); i += 11) {
250 // if ((i & (i - 1)) == 0) fprintf(stderr, "Path: : %zd\n", i);
253 EXPECT_TRUE(g.isReachable(start, target));
254 EXPECT_EQ(g.findPath(start, target, path, g.size()), i - start + 1);
258 TEST(BVGraph, LongCycle) {
266 void ShortestPath() {
273 // 1=>2=>3=>4=>5=>6=>7
282 EXPECT_TRUE(g.isReachable(1, t7));
283 // No path of length 1.
284 EXPECT_EQ(0U, g.findPath(1, t7, path, 1));
285 // Trying to find a path of len 2..6 gives path of len 2.
286 EXPECT_EQ(2U, g.findPath(1, t7, path, 2));
287 EXPECT_EQ(2U, g.findPath(1, t7, path, 3));
288 EXPECT_EQ(2U, g.findPath(1, t7, path, 4));
289 EXPECT_EQ(2U, g.findPath(1, t7, path, 5));
290 EXPECT_EQ(2U, g.findPath(1, t7, path, 6));
291 // Trying to find a path of len 7 gives path of len 7, because this is DFS.
292 EXPECT_EQ(7U, g.findPath(1, t7, path, 7));
293 // But findShortestPath will find the shortest path.
294 EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 2));
295 EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 7));
298 TEST(BVGraph, ShortestPath) {
306 void RunAddEdgesTest() {
309 const int kMaxEdges = 10;
310 uptr added_edges[kMaxEdges];
313 EXPECT_EQ(0U, g.addEdges(from, 0, added_edges, kMaxEdges));
314 EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges));
316 EXPECT_EQ(1U, g.addEdges(from, 1, added_edges, kMaxEdges));
317 EXPECT_EQ(0U, added_edges[0]);
318 EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges));
322 EXPECT_EQ(1U, g.addEdges(from, 4, added_edges, kMaxEdges));
323 EXPECT_TRUE(g.hasEdge(1, 4));
324 EXPECT_FALSE(g.hasEdge(1, 5));
325 EXPECT_EQ(1U, added_edges[0]);
328 EXPECT_EQ(2U, g.addEdges(from, 4, added_edges, kMaxEdges));
329 EXPECT_TRUE(g.hasEdge(2, 4));
330 EXPECT_FALSE(g.hasEdge(2, 5));
331 EXPECT_TRUE(g.hasEdge(3, 4));
332 EXPECT_FALSE(g.hasEdge(3, 5));
333 EXPECT_EQ(2U, added_edges[0]);
334 EXPECT_EQ(3U, added_edges[1]);
337 TEST(BVGraph, AddEdgesTest) {
338 RunAddEdgesTest<BV2>();