//===-- 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>();
}