chore(3p/abseil_cpp): unvendor abseil_cpp r/3786

we weren't actually using these sources anymore, okay?

Change-Id: If701571d9716de308d3512e1eb22c35db0877a66
Reviewed-on: https://cl.tvl.fyi/c/depot/+/5248
Tested-by: BuildkiteCI
Reviewed-by: grfn <grfn@gws.fyi>
Autosubmit: tazjin <tazjin@tvl.su>

1 files changed, 0 insertions, 464 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
deleted file mode 100644
index 74eaffe7a806..000000000000
--- a/third_party/abseil_cpp/absl/synchronization/internal/graphcycles_test.cc
+++ /dev/null
@@ -1,464 +0,0 @@
-// 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