compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cpp

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