sanitizer_bvgraph_test.cc   [plain text]

//===-- sanitizer_bvgraph_test.cc -----------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file is a part of Sanitizer runtime.
// Tests for sanitizer_bvgraph.h.
//
//===----------------------------------------------------------------------===//
#include "sanitizer_common/sanitizer_bvgraph.h"

#include "sanitizer_test_utils.h"

#include "gtest/gtest.h"

#include <algorithm>
#include <vector>
#include <set>

using namespace __sanitizer;
using namespace std;

typedef BasicBitVector<u8> BV1;
typedef BasicBitVector<> BV2;
typedef TwoLevelBitVector<> BV3;
typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;

template<class G>
void PrintGraph(const G &g) {
  for (uptr i = 0; i < g.size(); i++) {
    for (uptr j = 0; j < g.size(); j++) {
      fprintf(stderr, "%d", g.hasEdge(i, j));
    }
    fprintf(stderr, "\n");
  }
}


class SimpleGraph {
 public:
  void clear() { s_.clear(); }
  bool addEdge(uptr from, uptr to) {
    return s_.insert(idx(from, to)).second;
  }
  bool removeEdge(uptr from, uptr to) {
    return s_.erase(idx(from, to));
  }
  template <class G>
  void checkSameAs(G *g) {
    for (set<uptr>::iterator it = s_.begin(); it != s_.end(); ++it) {
      uptr from = *it >> 16;
      uptr to = *it & ((1 << 16) - 1);
      EXPECT_TRUE(g->removeEdge(from, to));
    }
    EXPECT_TRUE(g->empty());
  }
 private:
  uptr idx(uptr from, uptr to) {
    CHECK_LE(from|to, 1 << 16);
    return (from << 16) + to;
  }
  set<uptr> s_;
};

template <class BV>
void BasicTest() {
  BVGraph<BV> g;
  g.clear();
  BV target;
  SimpleGraph s_g;
  set<uptr> s;
  set<uptr> s_target;
  int num_reachable = 0;
  for (int it = 0; it < 1000; it++) {
    target.clear();
    s_target.clear();
    for (int t = 0; t < 4; t++) {
      uptr idx = (uptr)my_rand() % g.size();
      EXPECT_EQ(target.setBit(idx), s_target.insert(idx).second);
    }
    uptr from = my_rand() % g.size();
    uptr to = my_rand() % g.size();
    EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to));
    EXPECT_TRUE(g.hasEdge(from, to));
    for (int i = 0; i < 10; i++) {
      from = my_rand() % g.size();
      bool is_reachable = g.isReachable(from, target);
      if (is_reachable) {
        uptr path[BV::kSize];
        uptr len;
        for (len = 1; len < BV::kSize; len++) {
          if (g.findPath(from, target, path, len) == len)
            break;
        }
        EXPECT_LT(len, BV::kSize);
        EXPECT_TRUE(target.getBit(path[len - 1]));
        // fprintf(stderr, "reachable: %zd; path %zd {%zd %zd %zd}\n",
        //        from, len, path[0], path[1], path[2]);
        num_reachable++;
      }
    }
  }
  EXPECT_GT(num_reachable, 0);
}

TEST(BVGraph, BasicTest) {
  BasicTest<BV1>();
  BasicTest<BV2>();
  BasicTest<BV3>();
  BasicTest<BV4>();
}

template <class BV>
void RemoveEdges() {
  SimpleGraph s_g;
  BVGraph<BV> g;
  g.clear();
  BV bv;
  set<uptr> s;
  for (int it = 0; it < 100; it++) {
    s.clear();
    bv.clear();
    s_g.clear();
    g.clear();
    for (uptr j = 0; j < g.size() * 2; j++) {
      uptr from = my_rand() % g.size();
      uptr to = my_rand() % g.size();
      EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to));
    }
    for (uptr j = 0; j < 5; j++) {
      uptr idx = my_rand() % g.size();
      s.insert(idx);
      bv.setBit(idx);
    }

    if (it % 2) {
      g.removeEdgesFrom(bv);
      for (set<uptr>::iterator from = s.begin(); from != s.end(); ++from) {
        for (uptr to = 0; to < g.size(); to++)
          s_g.removeEdge(*from, to);
      }
    } else {
      g.removeEdgesTo(bv);
      for (set<uptr>::iterator to = s.begin(); to != s.end(); ++to) {
        for (uptr from = 0; from < g.size(); from++)
          s_g.removeEdge(from, *to);
      }
    }
    s_g.checkSameAs(&g);
  }
}

TEST(BVGraph, RemoveEdges) {
  RemoveEdges<BV1>();
  RemoveEdges<BV2>();
  RemoveEdges<BV3>();
  RemoveEdges<BV4>();
}

template <class BV>
void Test_isReachable() {
  uptr path[5];
  BVGraph<BV> g;
  g.clear();
  BV target;
  target.clear();
  uptr t0 = 0;
  uptr t1 = g.size() - 1;
  target.setBit(t0);
  target.setBit(t1);

  uptr f0 = 1;
  uptr f1 = 2;
  uptr f2 = g.size() / 2;
  uptr f3 = g.size() - 2;

  EXPECT_FALSE(g.isReachable(f0, target));
  EXPECT_FALSE(g.isReachable(f1, target));
  EXPECT_FALSE(g.isReachable(f2, target));
  EXPECT_FALSE(g.isReachable(f3, target));

  g.addEdge(f0, f1);
  g.addEdge(f1, f2);
  g.addEdge(f2, f3);
  EXPECT_FALSE(g.isReachable(f0, target));
  EXPECT_FALSE(g.isReachable(f1, target));
  EXPECT_FALSE(g.isReachable(f2, target));
  EXPECT_FALSE(g.isReachable(f3, target));

  g.addEdge(f1, t0);
  EXPECT_TRUE(g.isReachable(f0, target));
  EXPECT_TRUE(g.isReachable(f1, target));
  EXPECT_FALSE(g.isReachable(f2, target));
  EXPECT_FALSE(g.isReachable(f3, target));
  EXPECT_EQ(g.findPath(f0, target, path, ARRAY_SIZE(path)), 3U);
  EXPECT_EQ(path[0], f0);
  EXPECT_EQ(path[1], f1);
  EXPECT_EQ(path[2], t0);
  EXPECT_EQ(g.findPath(f1, target, path, ARRAY_SIZE(path)), 2U);
  EXPECT_EQ(path[0], f1);
  EXPECT_EQ(path[1], t0);

  g.addEdge(f3, t1);
  EXPECT_TRUE(g.isReachable(f0, target));
  EXPECT_TRUE(g.isReachable(f1, target));
  EXPECT_TRUE(g.isReachable(f2, target));
  EXPECT_TRUE(g.isReachable(f3, target));
}

TEST(BVGraph, isReachable) {
  Test_isReachable<BV1>();
  Test_isReachable<BV2>();
  Test_isReachable<BV3>();
  Test_isReachable<BV4>();
}

template <class BV>
void LongCycle() {
  BVGraph<BV> g;
  g.clear();
  vector<uptr> path_vec(g.size());
  uptr *path = path_vec.data();
  uptr start = 5;
  for (uptr i = start; i < g.size() - 1; i++) {
    g.addEdge(i, i + 1);
    for (uptr j = 0; j < start; j++)
      g.addEdge(i, j);
  }
  //  Bad graph that looks like this:
  // 00000000000000
  // 00000000000000
  // 00000000000000
  // 00000000000000
  // 00000000000000
  // 11111010000000
  // 11111001000000
  // 11111000100000
  // 11111000010000
  // 11111000001000
  // 11111000000100
  // 11111000000010
  // 11111000000001
  // if (g.size() <= 64) PrintGraph(g);
  BV target;
  for (uptr i = start + 1; i < g.size(); i += 11) {
    // if ((i & (i - 1)) == 0) fprintf(stderr, "Path: : %zd\n", i);
    target.clear();
    target.setBit(i);
    EXPECT_TRUE(g.isReachable(start, target));
    EXPECT_EQ(g.findPath(start, target, path, g.size()), i - start + 1);
  }
}

TEST(BVGraph, LongCycle) {
  LongCycle<BV1>();
  LongCycle<BV2>();
  LongCycle<BV3>();
  LongCycle<BV4>();
}

template <class BV>
void ShortestPath() {
  uptr path[8];
  BVGraph<BV> g;
  g.clear();
  BV t7;
  t7.clear();
  t7.setBit(7);
  // 1=>2=>3=>4=>5=>6=>7
  // 1=>7
  g.addEdge(1, 2);
  g.addEdge(2, 3);
  g.addEdge(3, 4);
  g.addEdge(4, 5);
  g.addEdge(5, 6);
  g.addEdge(6, 7);
  g.addEdge(1, 7);
  EXPECT_TRUE(g.isReachable(1, t7));
  // No path of length 1.
  EXPECT_EQ(0U, g.findPath(1, t7, path, 1));
  // Trying to find a path of len 2..6 gives path of len 2.
  EXPECT_EQ(2U, g.findPath(1, t7, path, 2));
  EXPECT_EQ(2U, g.findPath(1, t7, path, 3));
  EXPECT_EQ(2U, g.findPath(1, t7, path, 4));
  EXPECT_EQ(2U, g.findPath(1, t7, path, 5));
  EXPECT_EQ(2U, g.findPath(1, t7, path, 6));
  // Trying to find a path of len 7 gives path of len 7, because this is DFS.
  EXPECT_EQ(7U, g.findPath(1, t7, path, 7));
  // But findShortestPath will find the shortest path.
  EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 2));
  EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 7));
}

TEST(BVGraph, ShortestPath) {
  ShortestPath<BV1>();
  ShortestPath<BV2>();
  ShortestPath<BV3>();
  ShortestPath<BV4>();
}

template <class BV>
void RunAddEdgesTest() {
  BVGraph<BV> g;
  BV from;
  const int kMaxEdges = 10;
  uptr added_edges[kMaxEdges];
  g.clear();
  from.clear();
  EXPECT_EQ(0U, g.addEdges(from, 0, added_edges, kMaxEdges));
  EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges));
  from.setBit(0);
  EXPECT_EQ(1U, g.addEdges(from, 1, added_edges, kMaxEdges));
  EXPECT_EQ(0U, added_edges[0]);
  EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges));

  from.clear();
  from.setBit(1);
  EXPECT_EQ(1U, g.addEdges(from, 4, added_edges, kMaxEdges));
  EXPECT_TRUE(g.hasEdge(1, 4));
  EXPECT_FALSE(g.hasEdge(1, 5));
  EXPECT_EQ(1U, added_edges[0]);
  from.setBit(2);
  from.setBit(3);
  EXPECT_EQ(2U, g.addEdges(from, 4, added_edges, kMaxEdges));
  EXPECT_TRUE(g.hasEdge(2, 4));
  EXPECT_FALSE(g.hasEdge(2, 5));
  EXPECT_TRUE(g.hasEdge(3, 4));
  EXPECT_FALSE(g.hasEdge(3, 5));
  EXPECT_EQ(2U, added_edges[0]);
  EXPECT_EQ(3U, added_edges[1]);
}

TEST(BVGraph, AddEdgesTest) {
  RunAddEdgesTest<BV2>();
}