contrib/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc

   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>
  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:
  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
  69 template <class BV>
  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
 110 TEST(BVGraph, BasicTest) {
 111   BasicTest<BV1>();
 112   BasicTest<BV2>();
 113   BasicTest<BV3>();
 114   BasicTest<BV4>();
 115 }
 116
 117 template <class BV>
 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
 157 TEST(BVGraph, RemoveEdges) {
 158   RemoveEdges<BV1>();
 159   RemoveEdges<BV2>();
 160   RemoveEdges<BV3>();
 161   RemoveEdges<BV4>();
 162 }
 163
 164 template <class BV>
 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
 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>
 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
 258 TEST(BVGraph, LongCycle) {
 259   LongCycle<BV1>();
 260   LongCycle<BV2>();
 261   LongCycle<BV3>();
 262   LongCycle<BV4>();
 263 }
 264
 265 template <class BV>
 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
 298 TEST(BVGraph, ShortestPath) {
 299   ShortestPath<BV1>();
 300   ShortestPath<BV2>();
 301   ShortestPath<BV3>();
 302   ShortestPath<BV4>();
 303 }
 304
 305 template <class BV>
 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
 337 TEST(BVGraph, AddEdgesTest) {
 338   RunAddEdgesTest<BV2>();
 339 }