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>
PrintGraph(const G & 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:
clear()44 void clear() { s_.clear(); }
addEdge(uptr from,uptr to)45 bool addEdge(uptr from, uptr to) {
46 return s_.insert(idx(from, to)).second;
47 }
removeEdge(uptr from,uptr to)48 bool removeEdge(uptr from, uptr to) {
49 return s_.erase(idx(from, to));
50 }
51 template <class G>
checkSameAs(G * 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:
idx(uptr from,uptr to)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>
BasicTest()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
TEST(BVGraph,BasicTest)109 TEST(BVGraph, BasicTest) {
110 BasicTest<BV1>();
111 BasicTest<BV2>();
112 BasicTest<BV3>();
113 BasicTest<BV4>();
114 }
115
116 template <class BV>
RemoveEdges()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
TEST(BVGraph,RemoveEdges)156 TEST(BVGraph, RemoveEdges) {
157 RemoveEdges<BV1>();
158 RemoveEdges<BV2>();
159 RemoveEdges<BV3>();
160 RemoveEdges<BV4>();
161 }
162
163 template <class BV>
Test_isReachable()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
TEST(BVGraph,isReachable)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>
LongCycle()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
TEST(BVGraph,LongCycle)257 TEST(BVGraph, LongCycle) {
258 LongCycle<BV1>();
259 LongCycle<BV2>();
260 LongCycle<BV3>();
261 LongCycle<BV4>();
262 }
263
264 template <class BV>
ShortestPath()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
TEST(BVGraph,ShortestPath)297 TEST(BVGraph, ShortestPath) {
298 ShortestPath<BV1>();
299 ShortestPath<BV2>();
300 ShortestPath<BV3>();
301 ShortestPath<BV4>();
302 }
303
304 template <class BV>
RunAddEdgesTest()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
TEST(BVGraph,AddEdgesTest)336 TEST(BVGraph, AddEdgesTest) {
337 RunAddEdgesTest<BV2>();
338 }
339