Split Table.Decompose and add derived-key and conversion tests.

PiperOrigin-RevId: 1024431817
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index e0a6cb1..2dec4c2 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -2938,6 +2938,10 @@
     return *this;
   }
 
+  friend bool operator==(const DecomposeType& a, const DecomposeType& b) {
+    return a.i == b.i;
+  }
+
   template <typename H>
   friend H AbslHashValue(H h, const DecomposeType& d) {
     return H::combine(std::move(h), d.i);
@@ -2997,9 +3001,6 @@
   const int one = 1;
   const char* three_p = "3";
   const auto& three = three_p;
-  const int elem_vector_count = 256;
-  std::vector<DecomposeType> elem_vector(elem_vector_count, DecomposeType{0});
-  std::iota(elem_vector.begin(), elem_vector.end(), 0);
 
   using DecomposeSet =
       raw_hash_set<DecomposePolicy, Hash, Eq, std::allocator<int>>;
@@ -3014,25 +3015,28 @@
   EXPECT_EQ(++expected_constructed, decompose_constructed);
   set1.emplace("3");
   EXPECT_EQ(++expected_constructed, decompose_constructed);
-  EXPECT_EQ(expected_constructed, decompose_constructed);
 
-  {  // insert(T&&)
+  {  // insert(T&&) / insert(const T&) / insert(hint, ...)
     set1.insert(1);
     EXPECT_EQ(expected_constructed, decompose_constructed);
-  }
-
-  {  // insert(const T&)
     set1.insert(one);
     EXPECT_EQ(expected_constructed, decompose_constructed);
-  }
-
-  {  // insert(hint, T&&)
     set1.insert(set1.begin(), 1);
     EXPECT_EQ(expected_constructed, decompose_constructed);
+    set1.insert(set1.begin(), one);
+    EXPECT_EQ(expected_constructed, decompose_constructed);
   }
 
-  {  // insert(hint, const T&)
-    set1.insert(set1.begin(), one);
+  {  // insert(const init_type&) via derived type and reference_wrapper
+    struct DerivedDecomposeType : DecomposeType {
+      using DecomposeType::DecomposeType;
+    };
+    const DerivedDecomposeType derived(0);
+    ++expected_constructed;
+    EXPECT_FALSE(set1.insert(derived).second);
+    EXPECT_EQ(set1.insert(set1.begin(), derived)->i, 0);
+    EXPECT_FALSE(set1.insert(std::cref(elem)).second);
+    EXPECT_NE(set1.find(derived), set1.end());
     EXPECT_EQ(expected_constructed, decompose_constructed);
   }
 
@@ -3061,6 +3065,16 @@
     expected_constructed += construct_three;
     EXPECT_EQ(expected_constructed, decompose_constructed);
   }
+}
+
+template <typename Hash, typename Eq>
+void TestDecomposeRangeInsert() {
+  const int elem_vector_count = 256;
+  std::vector<DecomposeType> elem_vector(elem_vector_count, DecomposeType{0});
+  std::iota(elem_vector.begin(), elem_vector.end(), 0);
+
+  using DecomposeSet =
+      raw_hash_set<DecomposePolicy, Hash, Eq, std::allocator<int>>;
 
   decompose_copy_constructed = 0;
   decompose_copy_assigned = 0;
@@ -3093,8 +3107,6 @@
     EXPECT_GE(expected_move_constructed, decompose_move_constructed);
     EXPECT_EQ(0, decompose_move_assigned);
     EXPECT_EQ(0, decompose_copy_assigned);
-    expected_copy_constructed = decompose_copy_constructed;
-    expected_move_constructed = decompose_move_constructed;
   }
 
   {  // insert(first, last)
@@ -3110,28 +3122,25 @@
     EXPECT_GE(expected_move_constructed, decompose_move_constructed);
     EXPECT_EQ(0, decompose_move_assigned);
     EXPECT_EQ(0, decompose_copy_assigned);
-    expected_copy_constructed = decompose_copy_constructed;
-    expected_move_constructed = decompose_move_constructed;
   }
 }
 
-TEST(Table, Decompose) {
-  if (SwisstableGenerationsEnabled()) {
-    GTEST_SKIP() << "Generations being enabled causes extra rehashes.";
+struct TransparentHashIntOverload {
+  size_t operator()(const DecomposeType& a) const {
+    return static_cast<size_t>(a.i);
   }
+  size_t operator()(int a) const { return static_cast<size_t>(a); }
+};
 
+struct TransparentEqIntOverload {
+  bool operator()(const DecomposeType& a, const DecomposeType& b) const {
+    return a.i == b.i;
+  }
+  bool operator()(const DecomposeType& a, int b) const { return a.i == b; }
+};
+
+TEST(Table, Decompose) {
   TestDecompose<DecomposeHash, DecomposeEq>(false);
-
-  struct TransparentHashIntOverload {
-    size_t operator()(const DecomposeType& a) const { return a.i; }
-    size_t operator()(int a) const { return a; }
-  };
-  struct TransparentEqIntOverload {
-    bool operator()(const DecomposeType& a, const DecomposeType& b) const {
-      return a.i == b.i;
-    }
-    bool operator()(const DecomposeType& a, int b) const { return a.i == b; }
-  };
   TestDecompose<TransparentHashIntOverload, DecomposeEq>(true);
   TestDecompose<TransparentHashIntOverload, TransparentEqIntOverload>(true);
   TestDecompose<DecomposeHash, TransparentEqIntOverload>(true);
@@ -3139,6 +3148,125 @@
                 TransparentEqIntOverload>(true);
 }
 
+template <typename Hash, typename Eq>
+void TestDecomposeNonTransparent() {
+  using Set = raw_hash_set<DecomposePolicy, Hash, Eq, std::allocator<int>>;
+  Set set;
+  set.insert(DecomposeType{0});
+  set.insert(DecomposeType{2});
+
+  decompose_constructed = 0;
+  // Miss converts for lookup and constructs once in the slot.
+  set.insert(1);
+  EXPECT_GE(decompose_constructed, 2);
+
+  const int one = 1;
+  // TODO(b/413633804): Tighten to EXPECT_EQ(..., 1) once EmplaceDecomposable
+  // converts non-transparent keys at the lookup boundary.
+  auto check_hit = [&](absl::FunctionRef<void(Set&, int)> fn) {
+    decompose_constructed = 0;
+    fn(set, one);
+    EXPECT_GE(decompose_constructed, 1);
+  };
+  check_hit([](Set& s, int) { s.insert(1); });
+  check_hit([](Set& s, int v) { s.insert(v); });
+  check_hit([](Set& s, int) { s.insert(s.begin(), 1); });
+  check_hit([](Set& s, int v) { s.insert(s.begin(), v); });
+  check_hit([](Set& s, int) { s.emplace(1); });
+  check_hit([](Set& s, int v) { s.emplace(v); });
+  check_hit([](Set& s, int) { s.emplace_hint(s.begin(), 1); });
+  check_hit([](Set& s, int v) { s.emplace_hint(s.begin(), v); });
+}
+
+TEST(Table, DecomposeNonTransparentSingleConversion) {
+  struct NonTransparentHash {
+    size_t operator()(const DecomposeType& a) const {
+      // Force collisions so per-probe key conversions would increase the
+      // construction count.
+      return static_cast<size_t>(a.i) % 2;
+    }
+  };
+  struct NonTransparentEq {
+    bool operator()(const DecomposeType& a, const DecomposeType& b) const {
+      return a.i == b.i;
+    }
+  };
+  TestDecomposeNonTransparent<NonTransparentHash, DecomposeEq>();
+  TestDecomposeNonTransparent<NonTransparentHash, NonTransparentEq>();
+  TestDecomposeNonTransparent<DecomposeHash, NonTransparentEq>();
+}
+
+TEST(Table, EmplaceHeterogeneousKeyHitDoesNotMoveValue) {
+  absl::flat_hash_map<int64_t, std::unique_ptr<int>> m;
+  m.emplace(int64_t{1}, std::make_unique<int>(42));
+  auto p = std::make_unique<int>(99);
+  EXPECT_FALSE(m.emplace(1, std::move(p)).second);
+  EXPECT_NE(p, nullptr);
+  EXPECT_EQ(*m[1], 42);
+}
+
+TEST(Table, DecomposeRangeInsert) {
+  if (SwisstableGenerationsEnabled()) {
+    GTEST_SKIP() << "Generations being enabled causes extra rehashes.";
+  }
+
+  TestDecomposeRangeInsert<DecomposeHash, DecomposeEq>();
+  TestDecomposeRangeInsert<TransparentHashIntOverload, DecomposeEq>();
+  TestDecomposeRangeInsert<TransparentHashIntOverload,
+                           TransparentEqIntOverload>();
+  TestDecomposeRangeInsert<DecomposeHash, TransparentEqIntOverload>();
+  TestDecomposeRangeInsert<absl::TransparentHash<DecomposeType, int>,
+                           TransparentEqIntOverload>();
+}
+
+TEST(Table, DerivedKeyMap) {
+  struct DerivedDecomposeType : DecomposeType {
+    using DecomposeType::DecomposeType;
+  };
+  const DerivedDecomposeType d(2);
+  absl::flat_hash_map<DecomposeType, int> map;
+  std::pair<DerivedDecomposeType, int> p(DerivedDecomposeType(10), 100);
+  EXPECT_TRUE(map.insert(p).second);
+  EXPECT_TRUE(map.insert({d, 200}).second);
+  EXPECT_FALSE(map.try_emplace(d, 300).second);
+  EXPECT_EQ(map.find(d)->second, 200);
+  EXPECT_EQ(map[d], 200);
+}
+
+TEST(Table, DerivedKeyTrivialSet) {
+  struct TrivialBase {
+    int v;
+  };
+  struct TrivialDerived : TrivialBase {};
+  struct TrivialHash {
+    size_t operator()(TrivialBase k) const { return static_cast<size_t>(k.v); }
+  };
+  struct TrivialEq {
+    bool operator()(TrivialBase a, TrivialBase b) const { return a.v == b.v; }
+  };
+  absl::flat_hash_set<TrivialBase, TrivialHash, TrivialEq> set;
+  const TrivialDerived td{{7}};
+  EXPECT_TRUE(set.insert(td).second);
+  EXPECT_EQ(set.insert(set.begin(), td)->v, 7);
+}
+
+struct TemplatedConversionProxy {
+  int v;
+  template <typename T>
+  operator T() const {  // NOLINT(google-explicit-constructor)
+    static_assert(std::is_same_v<T, int>);
+    return T(v);
+  }
+};
+
+TEST(Table, InsertTemplatedConversionOperator) {
+  absl::flat_hash_set<int> set;
+  const TemplatedConversionProxy p{42};
+  EXPECT_TRUE(set.insert(p).second);
+  EXPECT_EQ(*set.insert(set.begin(), TemplatedConversionProxy{42}), 42);
+  EXPECT_THAT(set, ElementsAre(42));
+}
+
 struct Modulo1000Hash {
   size_t operator()(int64_t x) const { return static_cast<size_t>(x) % 1000; }
 };