From 643b48a3b4362a932c0e41afce62deb55adf825b Mon Sep 17 00:00:00 2001
From: Dennis Kormalev <denk@google.com>
Date: Wed, 7 Feb 2024 08:39:23 -0800
Subject: Add absl_container_hash-based HashEq specialization

SwissTable provides support for heterogeneous lookup in associative
containers through transparent Hash and Eq types. However, it is not
possible for user types to provide additional specializations to allow
their types to use this functionality.

This CL brings ability for user types to specify their own transparent
absl_container_hash and (optionally) absl_container_eq inner types to
achieve the same functionality.

PiperOrigin-RevId: 604994859
Change-Id: I302486d292c9a18b7d4c77033227008f5539e354
---
 .../internal/hash_function_defaults_test.cc        | 139 ++++++++++++++++++++-
 1 file changed, 138 insertions(+), 1 deletion(-)

(limited to 'absl/container/internal/hash_function_defaults_test.cc')

diff --git a/absl/container/internal/hash_function_defaults_test.cc b/absl/container/internal/hash_function_defaults_test.cc
index 7da0c86a..912d1190 100644
--- a/absl/container/internal/hash_function_defaults_test.cc
+++ b/absl/container/internal/hash_function_defaults_test.cc
@@ -14,11 +14,15 @@
 
 #include "absl/container/internal/hash_function_defaults.h"
 
+#include <cstddef>
 #include <functional>
 #include <type_traits>
 #include <utility>
 
 #include "gtest/gtest.h"
+#include "absl/container/flat_hash_map.h"
+#include "absl/container/flat_hash_set.h"
+#include "absl/hash/hash.h"
 #include "absl/random/random.h"
 #include "absl/strings/cord.h"
 #include "absl/strings/cord_test_helpers.h"
@@ -495,13 +499,146 @@ TYPED_TEST(StringLikeTest, HashEq) {
   EXPECT_NE(this->hash(this->a1), this->hash(this->b2));
 }
 
+struct TypeWithAbslContainerHash {
+  struct absl_container_hash {
+    using is_transparent = void;
+
+    size_t operator()(const TypeWithAbslContainerHash& foo) const {
+      return absl::HashOf(foo.value);
+    }
+
+    // Extra overload to test that heterogeneity works for this hasher.
+    size_t operator()(int value) const { return absl::HashOf(value); }
+  };
+
+  friend bool operator==(const TypeWithAbslContainerHash& lhs,
+                         const TypeWithAbslContainerHash& rhs) {
+    return lhs.value == rhs.value;
+  }
+
+  friend bool operator==(const TypeWithAbslContainerHash& lhs, int rhs) {
+    return lhs.value == rhs;
+  }
+
+  int value;
+  int noise;
+};
+
+struct TypeWithAbslContainerHashAndEq {
+  struct absl_container_hash {
+    using is_transparent = void;
+
+    size_t operator()(const TypeWithAbslContainerHashAndEq& foo) const {
+      return absl::HashOf(foo.value);
+    }
+
+    // Extra overload to test that heterogeneity works for this hasher.
+    size_t operator()(int value) const { return absl::HashOf(value); }
+  };
+
+  struct absl_container_eq {
+    using is_transparent = void;
+
+    bool operator()(const TypeWithAbslContainerHashAndEq& lhs,
+                    const TypeWithAbslContainerHashAndEq& rhs) const {
+      return lhs.value == rhs.value;
+    }
+
+    // Extra overload to test that heterogeneity works for this eq.
+    bool operator()(const TypeWithAbslContainerHashAndEq& lhs, int rhs) const {
+      return lhs.value == rhs;
+    }
+  };
+
+  template <typename T>
+  bool operator==(T&& other) const = delete;
+
+  int value;
+  int noise;
+};
+
+using AbslContainerHashTypes =
+    Types<TypeWithAbslContainerHash, TypeWithAbslContainerHashAndEq>;
+
+template <typename T>
+using AbslContainerHashTest = ::testing::Test;
+
+TYPED_TEST_SUITE(AbslContainerHashTest, AbslContainerHashTypes);
+
+TYPED_TEST(AbslContainerHashTest, HasherWorks) {
+  hash_default_hash<TypeParam> hasher;
+
+  TypeParam foo1{/*value=*/1, /*noise=*/100};
+  TypeParam foo1_copy{/*value=*/1, /*noise=*/20};
+  TypeParam foo2{/*value=*/2, /*noise=*/100};
+
+  EXPECT_EQ(hasher(foo1), absl::HashOf(1));
+  EXPECT_EQ(hasher(foo2), absl::HashOf(2));
+  EXPECT_EQ(hasher(foo1), hasher(foo1_copy));
+
+  // Heterogeneity works.
+  EXPECT_EQ(hasher(foo1), hasher(1));
+  EXPECT_EQ(hasher(foo2), hasher(2));
+}
+
+TYPED_TEST(AbslContainerHashTest, EqWorks) {
+  hash_default_eq<TypeParam> eq;
+
+  TypeParam foo1{/*value=*/1, /*noise=*/100};
+  TypeParam foo1_copy{/*value=*/1, /*noise=*/20};
+  TypeParam foo2{/*value=*/2, /*noise=*/100};
+
+  EXPECT_TRUE(eq(foo1, foo1_copy));
+  EXPECT_FALSE(eq(foo1, foo2));
+
+  // Heterogeneity works.
+  EXPECT_TRUE(eq(foo1, 1));
+  EXPECT_FALSE(eq(foo1, 2));
+}
+
+TYPED_TEST(AbslContainerHashTest, HeterogeneityInMapWorks) {
+  absl::flat_hash_map<TypeParam, int> map;
+
+  TypeParam foo1{/*value=*/1, /*noise=*/100};
+  TypeParam foo1_copy{/*value=*/1, /*noise=*/20};
+  TypeParam foo2{/*value=*/2, /*noise=*/100};
+  TypeParam foo3{/*value=*/3, /*noise=*/100};
+
+  map[foo1] = 1;
+  map[foo2] = 2;
+
+  EXPECT_TRUE(map.contains(foo1_copy));
+  EXPECT_EQ(map.at(foo1_copy), 1);
+  EXPECT_TRUE(map.contains(1));
+  EXPECT_EQ(map.at(1), 1);
+  EXPECT_TRUE(map.contains(2));
+  EXPECT_EQ(map.at(2), 2);
+  EXPECT_FALSE(map.contains(foo3));
+  EXPECT_FALSE(map.contains(3));
+}
+
+TYPED_TEST(AbslContainerHashTest, HeterogeneityInSetWorks) {
+  absl::flat_hash_set<TypeParam> set;
+
+  TypeParam foo1{/*value=*/1, /*noise=*/100};
+  TypeParam foo1_copy{/*value=*/1, /*noise=*/20};
+  TypeParam foo2{/*value=*/2, /*noise=*/100};
+
+  set.insert(foo1);
+
+  EXPECT_TRUE(set.contains(foo1_copy));
+  EXPECT_TRUE(set.contains(1));
+  EXPECT_FALSE(set.contains(foo2));
+  EXPECT_FALSE(set.contains(2));
+}
+
 }  // namespace
 }  // namespace container_internal
 ABSL_NAMESPACE_END
 }  // namespace absl
 
 enum Hash : size_t {
-  kStd = 0x1,       // std::hash
+  kStd = 0x1,  // std::hash
 #ifdef _MSC_VER
   kExtension = kStd,  // In MSVC, std::hash == ::hash
 #else                 // _MSC_VER
-- 
cgit v1.2.3