Export of internal Abseil changes

--
487c7a754a3b93bc0f9de14bdced48007a96ae55 by Greg Falcon <gfalcon@google.com>:

Add support for absl::Hash to hash unordered containers.  These can now be hashed directly, as well as combined in AbslHashValue implementations.

This also adds a new method, `H::combine_unordered()`, to the public AbslHashValue hash state API.  This allows users to implement hash specializations for their own unordered collection types.

A traits class, `H::is_hashable<T>`, is also added to the hash state API.  H::is_hashable<T>::value reflects whether type T is considered hashable by the AbslHashValue framework.  This allows users to properly SFINAE templated versions of AbslHashValue.  (The AbslHashValue implementation added to raw_hash_set shows an example of its use.)

PiperOrigin-RevId: 422856706
GitOrigin-RevId: 487c7a754a3b93bc0f9de14bdced48007a96ae55
Change-Id: Id31fd4ccba282f8c9ae6fcee6ae0ad0f7879f456

1 files changed, 83 insertions, 11 deletions

diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc
index dbfacb2d..cea54dc0 100644
--- a/absl/hash/hash_test.cc
+++ b/absl/hash/hash_test.cc
@@ -34,12 +34,18 @@
 #include <tuple>
 #include <type_traits>
 #include <unordered_map>
+#include <unordered_set>
 #include <utility>
 #include <vector>
 
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include "absl/container/btree_map.h"
+#include "absl/container/btree_set.h"
+#include "absl/container/flat_hash_map.h"
 #include "absl/container/flat_hash_set.h"
+#include "absl/container/node_hash_map.h"
+#include "absl/container/node_hash_set.h"
 #include "absl/hash/hash_testing.h"
 #include "absl/hash/internal/spy_hash_state.h"
 #include "absl/meta/type_traits.h"
@@ -433,6 +439,52 @@ TEST(HashValueTest, StdBitset) {
        std::bitset<kNumBits>(bit_strings[5].c_str())}));
 }  // namespace
 
+// Dummy type with unordered equality and hashing semantics.  This preserves
+// input order internally, and is used below to ensure we get test coverage
+// for equal sequences with different iteraton orders.
+template <typename T>
+class UnorderedSequence {
+ public:
+  UnorderedSequence() = default;
+  template <typename TT>
+  UnorderedSequence(std::initializer_list<TT> l)
+      : values_(l.begin(), l.end()) {}
+  template <typename ForwardIterator,
+            typename std::enable_if<!std::is_integral<ForwardIterator>::value,
+                                    bool>::type = true>
+  UnorderedSequence(ForwardIterator begin, ForwardIterator end)
+      : values_(begin, end) {}
+  // one-argument constructor of value type T, to appease older toolchains that
+  // get confused by one-element initializer lists in some contexts
+  explicit UnorderedSequence(const T& v) : values_(&v, &v + 1) {}
+
+  using value_type = T;
+
+  size_t size() const { return values_.size(); }
+  typename std::vector<T>::const_iterator begin() const {
+    return values_.begin();
+  }
+  typename std::vector<T>::const_iterator end() const { return values_.end(); }
+
+  friend bool operator==(const UnorderedSequence& lhs,
+                         const UnorderedSequence& rhs) {
+    return lhs.size() == rhs.size() &&
+           std::is_permutation(lhs.begin(), lhs.end(), rhs.begin());
+  }
+  friend bool operator!=(const UnorderedSequence& lhs,
+                         const UnorderedSequence& rhs) {
+    return !(lhs == rhs);
+  }
+  template <typename H>
+  friend H AbslHashValue(H h, const UnorderedSequence& u) {
+    return H::combine(H::combine_unordered(std::move(h), u.begin(), u.end()),
+                      u.size());
+  }
+
+ private:
+  std::vector<T> values_;
+};
+
 template <typename T>
 class HashValueSequenceTest : public testing::Test {
 };
@@ -456,10 +508,13 @@ TYPED_TEST_P(HashValueSequenceTest, BasicUsage) {
 }
 
 REGISTER_TYPED_TEST_CASE_P(HashValueSequenceTest, BasicUsage);
-using IntSequenceTypes =
-    testing::Types<std::deque<int>, std::forward_list<int>, std::list<int>,
-                   std::vector<int>, std::vector<bool>, TypeErasedVector<int>,
-                   TypeErasedVector<bool>, std::set<int>, std::multiset<int>>;
+using IntSequenceTypes = testing::Types<
+    std::deque<int>, std::forward_list<int>, std::list<int>, std::vector<int>,
+    std::vector<bool>, TypeErasedContainer<std::vector<int>>, std::set<int>,
+    std::multiset<int>, UnorderedSequence<int>,
+    TypeErasedContainer<UnorderedSequence<int>>, std::unordered_set<int>,
+    std::unordered_multiset<int>, absl::flat_hash_set<int>,
+    absl::node_hash_set<int>, absl::btree_set<int>>;
 INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueSequenceTest, IntSequenceTypes);
 
 template <typename T>
@@ -487,11 +542,15 @@ TYPED_TEST_P(HashValueNestedSequenceTest, BasicUsage) {
 }
 
 REGISTER_TYPED_TEST_CASE_P(HashValueNestedSequenceTest, BasicUsage);
-using NestedIntSequenceTypes =
-    testing::Types<std::vector<std::vector<int>>,
-                   std::vector<TypeErasedVector<int>>,
-                   TypeErasedVector<std::vector<int>>,
-                   TypeErasedVector<TypeErasedVector<int>>>;
+template <typename T>
+using TypeErasedSet = TypeErasedContainer<UnorderedSequence<T>>;
+
+using NestedIntSequenceTypes = testing::Types<
+    std::vector<std::vector<int>>, std::vector<UnorderedSequence<int>>,
+    std::vector<TypeErasedSet<int>>, UnorderedSequence<std::vector<int>>,
+    UnorderedSequence<UnorderedSequence<int>>,
+    UnorderedSequence<TypeErasedSet<int>>, TypeErasedSet<std::vector<int>>,
+    TypeErasedSet<UnorderedSequence<int>>, TypeErasedSet<TypeErasedSet<int>>>;
 INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueNestedSequenceTest,
                               NestedIntSequenceTypes);
 
@@ -674,7 +733,11 @@ TYPED_TEST_P(HashValueAssociativeMapTest, BasicUsage) {
 }
 
 REGISTER_TYPED_TEST_CASE_P(HashValueAssociativeMapTest, BasicUsage);
-using AssociativeMapTypes = testing::Types<std::map<int, std::string>>;
+using AssociativeMapTypes = testing::Types<
+    std::map<int, std::string>, std::unordered_map<int, std::string>,
+    absl::flat_hash_map<int, std::string>,
+    absl::node_hash_map<int, std::string>, absl::btree_map<int, std::string>,
+    UnorderedSequence<std::pair<const int, std::string>>>;
 INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueAssociativeMapTest,
                               AssociativeMapTypes);
 
@@ -702,7 +765,8 @@ TYPED_TEST_P(HashValueAssociativeMultimapTest, BasicUsage) {
 
 REGISTER_TYPED_TEST_CASE_P(HashValueAssociativeMultimapTest, BasicUsage);
 using AssociativeMultimapTypes =
-    testing::Types<std::multimap<int, std::string>>;
+    testing::Types<std::multimap<int, std::string>,
+                   std::unordered_multimap<int, std::string>>;
 INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueAssociativeMultimapTest,
                               AssociativeMultimapTypes);
 
@@ -1062,6 +1126,14 @@ TEST(HashTest, TypeErased) {
 
   EXPECT_EQ(SpyHash(std::make_pair(TypeErasedValue<size_t>(7), 17)),
             SpyHash(std::make_pair(size_t{7}, 17)));
+
+  absl::flat_hash_set<absl::flat_hash_set<int>> ss = {{1, 2}, {3, 4}};
+  TypeErasedContainer<absl::flat_hash_set<absl::flat_hash_set<int>>> es = {
+      absl::flat_hash_set<int>{1, 2}, {3, 4}};
+  absl::flat_hash_set<TypeErasedContainer<absl::flat_hash_set<int>>> se = {
+      {1, 2}, {3, 4}};
+  EXPECT_EQ(SpyHash(ss), SpyHash(es));
+  EXPECT_EQ(SpyHash(ss), SpyHash(se));
 }
 
 struct ValueWithBoolConversion {