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