Home | History | Annotate | Download | only in tests 
      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 }
    340