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
24using namespace __sanitizer;
25using namespace std;
26
27typedef BasicBitVector<u8> BV1;
28typedef BasicBitVector<> BV2;
29typedef TwoLevelBitVector<> BV3;
30typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;
31
32template<class G>
33void 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
43class SimpleGraph {
44 public:
45  void clear() { s_.clear(); }
46  bool addEdge(uptr from, uptr to) {
47    return s_.insert(idx(from, to)).second;
48  }
49  bool removeEdge(uptr from, uptr to) {
50    return s_.erase(idx(from, to));
51  }
52  template <class 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:
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
69template <class BV>
70void 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
110TEST(BVGraph, BasicTest) {
111  BasicTest<BV1>();
112  BasicTest<BV2>();
113  BasicTest<BV3>();
114  BasicTest<BV4>();
115}
116
117template <class BV>
118void 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
157TEST(BVGraph, RemoveEdges) {
158  RemoveEdges<BV1>();
159  RemoveEdges<BV2>();
160  RemoveEdges<BV3>();
161  RemoveEdges<BV4>();
162}
163
164template <class BV>
165void 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
214TEST(BVGraph, isReachable) {
215  Test_isReachable<BV1>();
216  Test_isReachable<BV2>();
217  Test_isReachable<BV3>();
218  Test_isReachable<BV4>();
219}
220
221template <class BV>
222void 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
258TEST(BVGraph, LongCycle) {
259  LongCycle<BV1>();
260  LongCycle<BV2>();
261  LongCycle<BV3>();
262  LongCycle<BV4>();
263}
264
265template <class BV>
266void 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
298TEST(BVGraph, ShortestPath) {
299  ShortestPath<BV1>();
300  ShortestPath<BV2>();
301  ShortestPath<BV3>();
302  ShortestPath<BV4>();
303}
304
305template <class BV>
306void 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
337TEST(BVGraph, AddEdgesTest) {
338  RunAddEdgesTest<BV2>();
339}
340