diff options
Diffstat (limited to 'third_party/abseil_cpp/absl/synchronization/internal/graphcycles_test.cc')
| -rw-r--r-- | third_party/abseil_cpp/absl/synchronization/internal/graphcycles_test.cc | 464 |
1 files changed, 464 insertions, 0 deletions
diff --git a/third_party/abseil_cpp/absl/synchronization/internal/graphcycles_test.cc b/third_party/abseil_cpp/absl/synchronization/internal/graphcycles_test.cc new file mode 100644 index 0000000000..74eaffe7a8 --- /dev/null +++ b/third_party/abseil_cpp/absl/synchronization/internal/graphcycles_test.cc @@ -0,0 +1,464 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/synchronization/internal/graphcycles.h" + +#include <map> +#include <random> +#include <unordered_set> +#include <utility> +#include <vector> + +#include "gtest/gtest.h" +#include "absl/base/internal/raw_logging.h" +#include "absl/base/macros.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace synchronization_internal { + +// We emulate a GraphCycles object with a node vector and an edge vector. +// We then compare the two implementations. + +using Nodes = std::vector<int>; +struct Edge { + int from; + int to; +}; +using Edges = std::vector<Edge>; +using RandomEngine = std::mt19937_64; + +// Mapping from integer index to GraphId. +typedef std::map<int, GraphId> IdMap; +static GraphId Get(const IdMap& id, int num) { + auto iter = id.find(num); + return (iter == id.end()) ? InvalidGraphId() : iter->second; +} + +// Return whether "to" is reachable from "from". +static bool IsReachable(Edges *edges, int from, int to, + std::unordered_set<int> *seen) { + seen->insert(from); // we are investigating "from"; don't do it again + if (from == to) return true; + for (const auto &edge : *edges) { + if (edge.from == from) { + if (edge.to == to) { // success via edge directly + return true; + } else if (seen->find(edge.to) == seen->end() && // success via edge + IsReachable(edges, edge.to, to, seen)) { + return true; + } + } + } + return false; +} + +static void PrintEdges(Edges *edges) { + ABSL_RAW_LOG(INFO, "EDGES (%zu)", edges->size()); + for (const auto &edge : *edges) { + int a = edge.from; + int b = edge.to; + ABSL_RAW_LOG(INFO, "%d %d", a, b); + } + ABSL_RAW_LOG(INFO, "---"); +} + +static void PrintGCEdges(Nodes *nodes, const IdMap &id, GraphCycles *gc) { + ABSL_RAW_LOG(INFO, "GC EDGES"); + for (int a : *nodes) { + for (int b : *nodes) { + if (gc->HasEdge(Get(id, a), Get(id, b))) { + ABSL_RAW_LOG(INFO, "%d %d", a, b); + } + } + } + ABSL_RAW_LOG(INFO, "---"); +} + +static void PrintTransitiveClosure(Nodes *nodes, Edges *edges) { + ABSL_RAW_LOG(INFO, "Transitive closure"); + for (int a : *nodes) { + for (int b : *nodes) { + std::unordered_set<int> seen; + if (IsReachable(edges, a, b, &seen)) { + ABSL_RAW_LOG(INFO, "%d %d", a, b); + } + } + } + ABSL_RAW_LOG(INFO, "---"); +} + +static void PrintGCTransitiveClosure(Nodes *nodes, const IdMap &id, + GraphCycles *gc) { + ABSL_RAW_LOG(INFO, "GC Transitive closure"); + for (int a : *nodes) { + for (int b : *nodes) { + if (gc->IsReachable(Get(id, a), Get(id, b))) { + ABSL_RAW_LOG(INFO, "%d %d", a, b); + } + } + } + ABSL_RAW_LOG(INFO, "---"); +} + +static void CheckTransitiveClosure(Nodes *nodes, Edges *edges, const IdMap &id, + GraphCycles *gc) { + std::unordered_set<int> seen; + for (const auto &a : *nodes) { + for (const auto &b : *nodes) { + seen.clear(); + bool gc_reachable = gc->IsReachable(Get(id, a), Get(id, b)); + bool reachable = IsReachable(edges, a, b, &seen); + if (gc_reachable != reachable) { + PrintEdges(edges); + PrintGCEdges(nodes, id, gc); + PrintTransitiveClosure(nodes, edges); + PrintGCTransitiveClosure(nodes, id, gc); + ABSL_RAW_LOG(FATAL, "gc_reachable %s reachable %s a %d b %d", + gc_reachable ? "true" : "false", + reachable ? "true" : "false", a, b); + } + } + } +} + +static void CheckEdges(Nodes *nodes, Edges *edges, const IdMap &id, + GraphCycles *gc) { + int count = 0; + for (const auto &edge : *edges) { + int a = edge.from; + int b = edge.to; + if (!gc->HasEdge(Get(id, a), Get(id, b))) { + PrintEdges(edges); + PrintGCEdges(nodes, id, gc); + ABSL_RAW_LOG(FATAL, "!gc->HasEdge(%d, %d)", a, b); + } + } + for (const auto &a : *nodes) { + for (const auto &b : *nodes) { + if (gc->HasEdge(Get(id, a), Get(id, b))) { + count++; + } + } + } + if (count != edges->size()) { + PrintEdges(edges); + PrintGCEdges(nodes, id, gc); + ABSL_RAW_LOG(FATAL, "edges->size() %zu count %d", edges->size(), count); + } +} + +static void CheckInvariants(const GraphCycles &gc) { + if (ABSL_PREDICT_FALSE(!gc.CheckInvariants())) + ABSL_RAW_LOG(FATAL, "CheckInvariants"); +} + +// Returns the index of a randomly chosen node in *nodes. +// Requires *nodes be non-empty. +static int RandomNode(RandomEngine* rng, Nodes *nodes) { + std::uniform_int_distribution<int> uniform(0, nodes->size()-1); + return uniform(*rng); +} + +// Returns the index of a randomly chosen edge in *edges. +// Requires *edges be non-empty. +static int RandomEdge(RandomEngine* rng, Edges *edges) { + std::uniform_int_distribution<int> uniform(0, edges->size()-1); + return uniform(*rng); +} + +// Returns the index of edge (from, to) in *edges or -1 if it is not in *edges. +static int EdgeIndex(Edges *edges, int from, int to) { + int i = 0; + while (i != edges->size() && + ((*edges)[i].from != from || (*edges)[i].to != to)) { + i++; + } + return i == edges->size()? -1 : i; +} + +TEST(GraphCycles, RandomizedTest) { + int next_node = 0; + Nodes nodes; + Edges edges; // from, to + IdMap id; + GraphCycles graph_cycles; + static const int kMaxNodes = 7; // use <= 7 nodes to keep test short + static const int kDataOffset = 17; // an offset to the node-specific data + int n = 100000; + int op = 0; + RandomEngine rng(testing::UnitTest::GetInstance()->random_seed()); + std::uniform_int_distribution<int> uniform(0, 5); + + auto ptr = [](intptr_t i) { + return reinterpret_cast<void*>(i + kDataOffset); + }; + + for (int iter = 0; iter != n; iter++) { + for (const auto &node : nodes) { + ASSERT_EQ(graph_cycles.Ptr(Get(id, node)), ptr(node)) << " node " << node; + } + CheckEdges(&nodes, &edges, id, &graph_cycles); + CheckTransitiveClosure(&nodes, &edges, id, &graph_cycles); + op = uniform(rng); + switch (op) { + case 0: // Add a node + if (nodes.size() < kMaxNodes) { + int new_node = next_node++; + GraphId new_gnode = graph_cycles.GetId(ptr(new_node)); + ASSERT_NE(new_gnode, InvalidGraphId()); + id[new_node] = new_gnode; + ASSERT_EQ(ptr(new_node), graph_cycles.Ptr(new_gnode)); + nodes.push_back(new_node); + } + break; + + case 1: // Remove a node + if (nodes.size() > 0) { + int node_index = RandomNode(&rng, &nodes); + int node = nodes[node_index]; + nodes[node_index] = nodes.back(); + nodes.pop_back(); + graph_cycles.RemoveNode(ptr(node)); + ASSERT_EQ(graph_cycles.Ptr(Get(id, node)), nullptr); + id.erase(node); + int i = 0; + while (i != edges.size()) { + if (edges[i].from == node || edges[i].to == node) { + edges[i] = edges.back(); + edges.pop_back(); + } else { + i++; + } + } + } + break; + + case 2: // Add an edge + if (nodes.size() > 0) { + int from = RandomNode(&rng, &nodes); + int to = RandomNode(&rng, &nodes); + if (EdgeIndex(&edges, nodes[from], nodes[to]) == -1) { + if (graph_cycles.InsertEdge(id[nodes[from]], id[nodes[to]])) { + Edge new_edge; + new_edge.from = nodes[from]; + new_edge.to = nodes[to]; + edges.push_back(new_edge); + } else { + std::unordered_set<int> seen; + ASSERT_TRUE(IsReachable(&edges, nodes[to], nodes[from], &seen)) + << "Edge " << nodes[to] << "->" << nodes[from]; + } + } + } + break; + + case 3: // Remove an edge + if (edges.size() > 0) { + int i = RandomEdge(&rng, &edges); + int from = edges[i].from; + int to = edges[i].to; + ASSERT_EQ(i, EdgeIndex(&edges, from, to)); + edges[i] = edges.back(); + edges.pop_back(); + ASSERT_EQ(-1, EdgeIndex(&edges, from, to)); + graph_cycles.RemoveEdge(id[from], id[to]); + } + break; + + case 4: // Check a path + if (nodes.size() > 0) { + int from = RandomNode(&rng, &nodes); + int to = RandomNode(&rng, &nodes); + GraphId path[2*kMaxNodes]; + int path_len = graph_cycles.FindPath(id[nodes[from]], id[nodes[to]], + ABSL_ARRAYSIZE(path), path); + std::unordered_set<int> seen; + bool reachable = IsReachable(&edges, nodes[from], nodes[to], &seen); + bool gc_reachable = + graph_cycles.IsReachable(Get(id, nodes[from]), Get(id, nodes[to])); + ASSERT_EQ(path_len != 0, reachable); + ASSERT_EQ(path_len != 0, gc_reachable); + // In the following line, we add one because a node can appear + // twice, if the path is from that node to itself, perhaps via + // every other node. + ASSERT_LE(path_len, kMaxNodes + 1); + if (path_len != 0) { + ASSERT_EQ(id[nodes[from]], path[0]); + ASSERT_EQ(id[nodes[to]], path[path_len-1]); + for (int i = 1; i < path_len; i++) { + ASSERT_TRUE(graph_cycles.HasEdge(path[i-1], path[i])); + } + } + } + break; + + case 5: // Check invariants + CheckInvariants(graph_cycles); + break; + + default: + ABSL_RAW_LOG(FATAL, "op %d", op); + } + + // Very rarely, test graph expansion by adding then removing many nodes. + std::bernoulli_distribution one_in_1024(1.0 / 1024); + if (one_in_1024(rng)) { + CheckEdges(&nodes, &edges, id, &graph_cycles); + CheckTransitiveClosure(&nodes, &edges, id, &graph_cycles); + for (int i = 0; i != 256; i++) { + int new_node = next_node++; + GraphId new_gnode = graph_cycles.GetId(ptr(new_node)); + ASSERT_NE(InvalidGraphId(), new_gnode); + id[new_node] = new_gnode; + ASSERT_EQ(ptr(new_node), graph_cycles.Ptr(new_gnode)); + for (const auto &node : nodes) { + ASSERT_NE(node, new_node); + } + nodes.push_back(new_node); + } + for (int i = 0; i != 256; i++) { + ASSERT_GT(nodes.size(), 0); + int node_index = RandomNode(&rng, &nodes); + int node = nodes[node_index]; + nodes[node_index] = nodes.back(); + nodes.pop_back(); + graph_cycles.RemoveNode(ptr(node)); + id.erase(node); + int j = 0; + while (j != edges.size()) { + if (edges[j].from == node || edges[j].to == node) { + edges[j] = edges.back(); + edges.pop_back(); + } else { + j++; + } + } + } + CheckInvariants(graph_cycles); + } + } +} + +class GraphCyclesTest : public ::testing::Test { + public: + IdMap id_; + GraphCycles g_; + + static void* Ptr(int i) { + return reinterpret_cast<void*>(static_cast<uintptr_t>(i)); + } + + static int Num(void* ptr) { + return static_cast<int>(reinterpret_cast<uintptr_t>(ptr)); + } + + // Test relies on ith NewNode() call returning Node numbered i + GraphCyclesTest() { + for (int i = 0; i < 100; i++) { + id_[i] = g_.GetId(Ptr(i)); + } + CheckInvariants(g_); + } + + bool AddEdge(int x, int y) { + return g_.InsertEdge(Get(id_, x), Get(id_, y)); + } + + void AddMultiples() { + // For every node x > 0: add edge to 2*x, 3*x + for (int x = 1; x < 25; x++) { + EXPECT_TRUE(AddEdge(x, 2*x)) << x; + EXPECT_TRUE(AddEdge(x, 3*x)) << x; + } + CheckInvariants(g_); + } + + std::string Path(int x, int y) { + GraphId path[5]; + int np = g_.FindPath(Get(id_, x), Get(id_, y), ABSL_ARRAYSIZE(path), path); + std::string result; + for (int i = 0; i < np; i++) { + if (i >= ABSL_ARRAYSIZE(path)) { + result += " ..."; + break; + } + if (!result.empty()) result.push_back(' '); + char buf[20]; + snprintf(buf, sizeof(buf), "%d", Num(g_.Ptr(path[i]))); + result += buf; + } + return result; + } +}; + +TEST_F(GraphCyclesTest, NoCycle) { + AddMultiples(); + CheckInvariants(g_); +} + +TEST_F(GraphCyclesTest, SimpleCycle) { + AddMultiples(); + EXPECT_FALSE(AddEdge(8, 4)); + EXPECT_EQ("4 8", Path(4, 8)); + CheckInvariants(g_); +} + +TEST_F(GraphCyclesTest, IndirectCycle) { + AddMultiples(); + EXPECT_TRUE(AddEdge(16, 9)); + CheckInvariants(g_); + EXPECT_FALSE(AddEdge(9, 2)); + EXPECT_EQ("2 4 8 16 9", Path(2, 9)); + CheckInvariants(g_); +} + +TEST_F(GraphCyclesTest, LongPath) { + ASSERT_TRUE(AddEdge(2, 4)); + ASSERT_TRUE(AddEdge(4, 6)); + ASSERT_TRUE(AddEdge(6, 8)); + ASSERT_TRUE(AddEdge(8, 10)); + ASSERT_TRUE(AddEdge(10, 12)); + ASSERT_FALSE(AddEdge(12, 2)); + EXPECT_EQ("2 4 6 8 10 ...", Path(2, 12)); + CheckInvariants(g_); +} + +TEST_F(GraphCyclesTest, RemoveNode) { + ASSERT_TRUE(AddEdge(1, 2)); + ASSERT_TRUE(AddEdge(2, 3)); + ASSERT_TRUE(AddEdge(3, 4)); + ASSERT_TRUE(AddEdge(4, 5)); + g_.RemoveNode(g_.Ptr(id_[3])); + id_.erase(3); + ASSERT_TRUE(AddEdge(5, 1)); +} + +TEST_F(GraphCyclesTest, ManyEdges) { + const int N = 50; + for (int i = 0; i < N; i++) { + for (int j = 1; j < N; j++) { + ASSERT_TRUE(AddEdge(i, i+j)); + } + } + CheckInvariants(g_); + ASSERT_TRUE(AddEdge(2*N-1, 0)); + CheckInvariants(g_); + ASSERT_FALSE(AddEdge(10, 9)); + CheckInvariants(g_); +} + +} // namespace synchronization_internal +ABSL_NAMESPACE_END +} // namespace absl |