• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- sanitizer_bvgraph_test.cc -----------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file is a part of Sanitizer runtime.
11 // Tests for sanitizer_bvgraph.h.
12 //
13 //===----------------------------------------------------------------------===//
14 #include "sanitizer_common/sanitizer_bvgraph.h"
15 
16 #include "sanitizer_test_utils.h"
17 
18 #include "gtest/gtest.h"
19 
20 #include <algorithm>
21 #include <vector>
22 #include <set>
23 
24 using namespace __sanitizer;
25 using namespace std;
26 
27 typedef BasicBitVector<u8> BV1;
28 typedef BasicBitVector<> BV2;
29 typedef TwoLevelBitVector<> BV3;
30 typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;
31 
32 template<class G>
PrintGraph(const G & g)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));
37     }
38     fprintf(stderr, "\n");
39   }
40 }
41 
42 
43 class SimpleGraph {
44  public:
clear()45   void clear() { s_.clear(); }
addEdge(uptr from,uptr to)46   bool addEdge(uptr from, uptr to) {
47     return s_.insert(idx(from, to)).second;
48   }
removeEdge(uptr from,uptr to)49   bool removeEdge(uptr from, uptr to) {
50     return s_.erase(idx(from, to));
51   }
52   template <class G>
checkSameAs(G * g)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));
58     }
59     EXPECT_TRUE(g->empty());
60   }
61  private:
idx(uptr from,uptr to)62   uptr idx(uptr from, uptr to) {
63     CHECK_LE(from|to, 1 << 16);
64     return (from << 16) + to;
65   }
66   set<uptr> s_;
67 };
68 
69 template <class BV>
BasicTest()70 void BasicTest() {
71   BVGraph<BV> g;
72   g.clear();
73   BV target;
74   SimpleGraph s_g;
75   set<uptr> s;
76   set<uptr> s_target;
77   int num_reachable = 0;
78   for (int it = 0; it < 1000; it++) {
79     target.clear();
80     s_target.clear();
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);
84     }
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);
92       if (is_reachable) {
93         uptr path[BV::kSize];
94         uptr len;
95         for (len = 1; len < BV::kSize; len++) {
96           if (g.findPath(from, target, path, len) == len)
97             break;
98         }
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]);
103         num_reachable++;
104       }
105     }
106   }
107   EXPECT_GT(num_reachable, 0);
108 }
109 
TEST(BVGraph,BasicTest)110 TEST(BVGraph, BasicTest) {
111   BasicTest<BV1>();
112   BasicTest<BV2>();
113   BasicTest<BV3>();
114   BasicTest<BV4>();
115 }
116 
117 template <class BV>
RemoveEdges()118 void RemoveEdges() {
119   SimpleGraph s_g;
120   BVGraph<BV> g;
121   g.clear();
122   BV bv;
123   set<uptr> s;
124   for (int it = 0; it < 100; it++) {
125     s.clear();
126     bv.clear();
127     s_g.clear();
128     g.clear();
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));
133     }
134     for (uptr j = 0; j < 5; j++) {
135       uptr idx = my_rand() % g.size();
136       s.insert(idx);
137       bv.setBit(idx);
138     }
139 
140     if (it % 2) {
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);
145       }
146     } else {
147       g.removeEdgesTo(bv);
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);
151       }
152     }
153     s_g.checkSameAs(&g);
154   }
155 }
156 
TEST(BVGraph,RemoveEdges)157 TEST(BVGraph, RemoveEdges) {
158   RemoveEdges<BV1>();
159   RemoveEdges<BV2>();
160   RemoveEdges<BV3>();
161   RemoveEdges<BV4>();
162 }
163 
164 template <class BV>
Test_isReachable()165 void Test_isReachable() {
166   uptr path[5];
167   BVGraph<BV> g;
168   g.clear();
169   BV target;
170   target.clear();
171   uptr t0 = 0;
172   uptr t1 = g.size() - 1;
173   target.setBit(t0);
174   target.setBit(t1);
175 
176   uptr f0 = 1;
177   uptr f1 = 2;
178   uptr f2 = g.size() / 2;
179   uptr f3 = g.size() - 2;
180 
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));
185 
186   g.addEdge(f0, f1);
187   g.addEdge(f1, f2);
188   g.addEdge(f2, f3);
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));
193 
194   g.addEdge(f1, t0);
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);
206 
207   g.addEdge(f3, t1);
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));
212 }
213 
TEST(BVGraph,isReachable)214 TEST(BVGraph, isReachable) {
215   Test_isReachable<BV1>();
216   Test_isReachable<BV2>();
217   Test_isReachable<BV3>();
218   Test_isReachable<BV4>();
219 }
220 
221 template <class BV>
LongCycle()222 void LongCycle() {
223   BVGraph<BV> g;
224   g.clear();
225   vector<uptr> path_vec(g.size());
226   uptr *path = path_vec.data();
227   uptr start = 5;
228   for (uptr i = start; i < g.size() - 1; i++) {
229     g.addEdge(i, i + 1);
230     for (uptr j = 0; j < start; j++)
231       g.addEdge(i, j);
232   }
233   //  Bad graph that looks like this:
234   // 00000000000000
235   // 00000000000000
236   // 00000000000000
237   // 00000000000000
238   // 00000000000000
239   // 11111010000000
240   // 11111001000000
241   // 11111000100000
242   // 11111000010000
243   // 11111000001000
244   // 11111000000100
245   // 11111000000010
246   // 11111000000001
247   // if (g.size() <= 64) PrintGraph(g);
248   BV target;
249   for (uptr i = start + 1; i < g.size(); i += 11) {
250     // if ((i & (i - 1)) == 0) fprintf(stderr, "Path: : %zd\n", i);
251     target.clear();
252     target.setBit(i);
253     EXPECT_TRUE(g.isReachable(start, target));
254     EXPECT_EQ(g.findPath(start, target, path, g.size()), i - start + 1);
255   }
256 }
257 
TEST(BVGraph,LongCycle)258 TEST(BVGraph, LongCycle) {
259   LongCycle<BV1>();
260   LongCycle<BV2>();
261   LongCycle<BV3>();
262   LongCycle<BV4>();
263 }
264 
265 template <class BV>
ShortestPath()266 void ShortestPath() {
267   uptr path[8];
268   BVGraph<BV> g;
269   g.clear();
270   BV t7;
271   t7.clear();
272   t7.setBit(7);
273   // 1=>2=>3=>4=>5=>6=>7
274   // 1=>7
275   g.addEdge(1, 2);
276   g.addEdge(2, 3);
277   g.addEdge(3, 4);
278   g.addEdge(4, 5);
279   g.addEdge(5, 6);
280   g.addEdge(6, 7);
281   g.addEdge(1, 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));
296 }
297 
TEST(BVGraph,ShortestPath)298 TEST(BVGraph, ShortestPath) {
299   ShortestPath<BV1>();
300   ShortestPath<BV2>();
301   ShortestPath<BV3>();
302   ShortestPath<BV4>();
303 }
304 
305 template <class BV>
RunAddEdgesTest()306 void RunAddEdgesTest() {
307   BVGraph<BV> g;
308   BV from;
309   const int kMaxEdges = 10;
310   uptr added_edges[kMaxEdges];
311   g.clear();
312   from.clear();
313   EXPECT_EQ(0U, g.addEdges(from, 0, added_edges, kMaxEdges));
314   EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges));
315   from.setBit(0);
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));
319 
320   from.clear();
321   from.setBit(1);
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]);
326   from.setBit(2);
327   from.setBit(3);
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]);
335 }
336 
TEST(BVGraph,AddEdgesTest)337 TEST(BVGraph, AddEdgesTest) {
338   RunAddEdgesTest<BV2>();
339 }
340