diff options
Diffstat (limited to 'third_party/abseil_cpp/absl/hash/hash_test.cc')
| -rw-r--r-- | third_party/abseil_cpp/absl/hash/hash_test.cc | 976 |
1 files changed, 976 insertions, 0 deletions
diff --git a/third_party/abseil_cpp/absl/hash/hash_test.cc b/third_party/abseil_cpp/absl/hash/hash_test.cc new file mode 100644 index 000000000000..39ba24a85afb --- /dev/null +++ b/third_party/abseil_cpp/absl/hash/hash_test.cc @@ -0,0 +1,976 @@ +// Copyright 2018 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/hash/hash.h" + +#include <array> +#include <bitset> +#include <cstring> +#include <deque> +#include <forward_list> +#include <functional> +#include <iterator> +#include <limits> +#include <list> +#include <map> +#include <memory> +#include <numeric> +#include <random> +#include <set> +#include <string> +#include <tuple> +#include <type_traits> +#include <unordered_map> +#include <utility> +#include <vector> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/container/flat_hash_set.h" +#include "absl/hash/hash_testing.h" +#include "absl/hash/internal/spy_hash_state.h" +#include "absl/meta/type_traits.h" +#include "absl/numeric/int128.h" +#include "absl/strings/cord_test_helpers.h" + +namespace { + +using absl::Hash; +using absl::hash_internal::SpyHashState; + +template <typename T> +class HashValueIntTest : public testing::Test { +}; +TYPED_TEST_SUITE_P(HashValueIntTest); + +template <typename T> +SpyHashState SpyHash(const T& value) { + return SpyHashState::combine(SpyHashState(), value); +} + +// Helper trait to verify if T is hashable. We use absl::Hash's poison status to +// detect it. +template <typename T> +using is_hashable = std::is_default_constructible<absl::Hash<T>>; + +TYPED_TEST_P(HashValueIntTest, BasicUsage) { + EXPECT_TRUE((is_hashable<TypeParam>::value)); + + TypeParam n = 42; + EXPECT_EQ(SpyHash(n), SpyHash(TypeParam{42})); + EXPECT_NE(SpyHash(n), SpyHash(TypeParam{0})); + EXPECT_NE(SpyHash(std::numeric_limits<TypeParam>::max()), + SpyHash(std::numeric_limits<TypeParam>::min())); +} + +TYPED_TEST_P(HashValueIntTest, FastPath) { + // Test the fast-path to make sure the values are the same. + TypeParam n = 42; + EXPECT_EQ(absl::Hash<TypeParam>{}(n), + absl::Hash<std::tuple<TypeParam>>{}(std::tuple<TypeParam>(n))); +} + +REGISTER_TYPED_TEST_CASE_P(HashValueIntTest, BasicUsage, FastPath); +using IntTypes = testing::Types<unsigned char, char, int, int32_t, int64_t, uint32_t, + uint64_t, size_t>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueIntTest, IntTypes); + +enum LegacyEnum { kValue1, kValue2, kValue3 }; + +enum class EnumClass { kValue4, kValue5, kValue6 }; + +TEST(HashValueTest, EnumAndBool) { + EXPECT_TRUE((is_hashable<LegacyEnum>::value)); + EXPECT_TRUE((is_hashable<EnumClass>::value)); + EXPECT_TRUE((is_hashable<bool>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + LegacyEnum::kValue1, LegacyEnum::kValue2, LegacyEnum::kValue3))); + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + EnumClass::kValue4, EnumClass::kValue5, EnumClass::kValue6))); + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(true, false))); +} + +TEST(HashValueTest, FloatingPoint) { + EXPECT_TRUE((is_hashable<float>::value)); + EXPECT_TRUE((is_hashable<double>::value)); + EXPECT_TRUE((is_hashable<long double>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(42.f, 0.f, -0.f, std::numeric_limits<float>::infinity(), + -std::numeric_limits<float>::infinity()))); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(42., 0., -0., std::numeric_limits<double>::infinity(), + -std::numeric_limits<double>::infinity()))); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + // Add some values with small exponent to test that NORMAL values also + // append their category. + .5L, 1.L, 2.L, 4.L, 42.L, 0.L, -0.L, + 17 * static_cast<long double>(std::numeric_limits<double>::max()), + std::numeric_limits<long double>::infinity(), + -std::numeric_limits<long double>::infinity()))); +} + +TEST(HashValueTest, Pointer) { + EXPECT_TRUE((is_hashable<int*>::value)); + + int i; + int* ptr = &i; + int* n = nullptr; + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(&i, ptr, nullptr, ptr + 1, n))); +} + +TEST(HashValueTest, PointerAlignment) { + // We want to make sure that pointer alignment will not cause bits to be + // stuck. + + constexpr size_t kTotalSize = 1 << 20; + std::unique_ptr<char[]> data(new char[kTotalSize]); + constexpr size_t kLog2NumValues = 5; + constexpr size_t kNumValues = 1 << kLog2NumValues; + + for (size_t align = 1; align < kTotalSize / kNumValues; + align < 8 ? align += 1 : align < 1024 ? align += 8 : align += 32) { + SCOPED_TRACE(align); + ASSERT_LE(align * kNumValues, kTotalSize); + + size_t bits_or = 0; + size_t bits_and = ~size_t{}; + + for (size_t i = 0; i < kNumValues; ++i) { + size_t hash = absl::Hash<void*>()(data.get() + i * align); + bits_or |= hash; + bits_and &= hash; + } + + // Limit the scope to the bits we would be using for Swisstable. + constexpr size_t kMask = (1 << (kLog2NumValues + 7)) - 1; + size_t stuck_bits = (~bits_or | bits_and) & kMask; + EXPECT_EQ(stuck_bits, 0) << "0x" << std::hex << stuck_bits; + } +} + +TEST(HashValueTest, PairAndTuple) { + EXPECT_TRUE((is_hashable<std::pair<int, int>>::value)); + EXPECT_TRUE((is_hashable<std::pair<const int&, const int&>>::value)); + EXPECT_TRUE((is_hashable<std::tuple<int&, int&>>::value)); + EXPECT_TRUE((is_hashable<std::tuple<int&&, int&&>>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + std::make_pair(0, 42), std::make_pair(0, 42), std::make_pair(42, 0), + std::make_pair(0, 0), std::make_pair(42, 42), std::make_pair(1, 42)))); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(std::make_tuple(0, 0, 0), std::make_tuple(0, 0, 42), + std::make_tuple(0, 23, 0), std::make_tuple(17, 0, 0), + std::make_tuple(42, 0, 0), std::make_tuple(3, 9, 9), + std::make_tuple(0, 0, -42)))); + + // Test that tuples of lvalue references work (so we need a few lvalues): + int a = 0, b = 1, c = 17, d = 23; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + std::tie(a, a), std::tie(a, b), std::tie(b, c), std::tie(c, d)))); + + // Test that tuples of rvalue references work: + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + std::forward_as_tuple(0, 0, 0), std::forward_as_tuple(0, 0, 42), + std::forward_as_tuple(0, 23, 0), std::forward_as_tuple(17, 0, 0), + std::forward_as_tuple(42, 0, 0), std::forward_as_tuple(3, 9, 9), + std::forward_as_tuple(0, 0, -42)))); +} + +TEST(HashValueTest, CombineContiguousWorks) { + std::vector<std::tuple<int>> v1 = {std::make_tuple(1), std::make_tuple(3)}; + std::vector<std::tuple<int>> v2 = {std::make_tuple(1), std::make_tuple(2)}; + + auto vh1 = SpyHash(v1); + auto vh2 = SpyHash(v2); + EXPECT_NE(vh1, vh2); +} + +struct DummyDeleter { + template <typename T> + void operator() (T* ptr) {} +}; + +struct SmartPointerEq { + template <typename T, typename U> + bool operator()(const T& t, const U& u) const { + return GetPtr(t) == GetPtr(u); + } + + template <typename T> + static auto GetPtr(const T& t) -> decltype(&*t) { + return t ? &*t : nullptr; + } + + static std::nullptr_t GetPtr(std::nullptr_t) { return nullptr; } +}; + +TEST(HashValueTest, SmartPointers) { + EXPECT_TRUE((is_hashable<std::unique_ptr<int>>::value)); + EXPECT_TRUE((is_hashable<std::unique_ptr<int, DummyDeleter>>::value)); + EXPECT_TRUE((is_hashable<std::shared_ptr<int>>::value)); + + int i, j; + std::unique_ptr<int, DummyDeleter> unique1(&i); + std::unique_ptr<int, DummyDeleter> unique2(&i); + std::unique_ptr<int, DummyDeleter> unique_other(&j); + std::unique_ptr<int, DummyDeleter> unique_null; + + std::shared_ptr<int> shared1(&i, DummyDeleter()); + std::shared_ptr<int> shared2(&i, DummyDeleter()); + std::shared_ptr<int> shared_other(&j, DummyDeleter()); + std::shared_ptr<int> shared_null; + + // Sanity check of the Eq function. + ASSERT_TRUE(SmartPointerEq{}(unique1, shared1)); + ASSERT_FALSE(SmartPointerEq{}(unique1, shared_other)); + ASSERT_TRUE(SmartPointerEq{}(unique_null, nullptr)); + ASSERT_FALSE(SmartPointerEq{}(shared2, nullptr)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::forward_as_tuple(&i, nullptr, // + unique1, unique2, unique_null, // + absl::make_unique<int>(), // + shared1, shared2, shared_null, // + std::make_shared<int>()), + SmartPointerEq{})); +} + +TEST(HashValueTest, FunctionPointer) { + using Func = int (*)(); + EXPECT_TRUE(is_hashable<Func>::value); + + Func p1 = [] { return 2; }, p2 = [] { return 1; }; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(p1, p2, nullptr))); +} + +struct WrapInTuple { + template <typename T> + std::tuple<int, T, size_t> operator()(const T& t) const { + return std::make_tuple(7, t, 0xdeadbeef); + } +}; + +absl::Cord FlatCord(absl::string_view sv) { + absl::Cord c(sv); + c.Flatten(); + return c; +} + +absl::Cord FragmentedCord(absl::string_view sv) { + if (sv.size() < 2) { + return absl::Cord(sv); + } + size_t halfway = sv.size() / 2; + std::vector<absl::string_view> parts = {sv.substr(0, halfway), + sv.substr(halfway)}; + return absl::MakeFragmentedCord(parts); +} + +TEST(HashValueTest, Strings) { + EXPECT_TRUE((is_hashable<std::string>::value)); + + const std::string small = "foo"; + const std::string dup = "foofoo"; + const std::string large = std::string(2048, 'x'); // multiple of chunk size + const std::string huge = std::string(5000, 'a'); // not a multiple + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( // + std::string(), absl::string_view(), absl::Cord(), // + std::string(""), absl::string_view(""), absl::Cord(""), // + std::string(small), absl::string_view(small), absl::Cord(small), // + std::string(dup), absl::string_view(dup), absl::Cord(dup), // + std::string(large), absl::string_view(large), absl::Cord(large), // + std::string(huge), absl::string_view(huge), FlatCord(huge), // + FragmentedCord(huge)))); + + // Also check that nested types maintain the same hash. + const WrapInTuple t{}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( // + t(std::string()), t(absl::string_view()), t(absl::Cord()), // + t(std::string("")), t(absl::string_view("")), t(absl::Cord("")), // + t(std::string(small)), t(absl::string_view(small)), // + t(absl::Cord(small)), // + t(std::string(dup)), t(absl::string_view(dup)), t(absl::Cord(dup)), // + t(std::string(large)), t(absl::string_view(large)), // + t(absl::Cord(large)), // + t(std::string(huge)), t(absl::string_view(huge)), // + t(FlatCord(huge)), t(FragmentedCord(huge))))); + + // Make sure that hashing a `const char*` does not use its string-value. + EXPECT_NE(SpyHash(static_cast<const char*>("ABC")), + SpyHash(absl::string_view("ABC"))); +} + +TEST(HashValueTest, WString) { + EXPECT_TRUE((is_hashable<std::wstring>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + std::wstring(), std::wstring(L"ABC"), std::wstring(L"ABC"), + std::wstring(L"Some other different string"), + std::wstring(L"Iñtërnâtiônàlizætiøn")))); +} + +TEST(HashValueTest, U16String) { + EXPECT_TRUE((is_hashable<std::u16string>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + std::u16string(), std::u16string(u"ABC"), std::u16string(u"ABC"), + std::u16string(u"Some other different string"), + std::u16string(u"Iñtërnâtiônàlizætiøn")))); +} + +TEST(HashValueTest, U32String) { + EXPECT_TRUE((is_hashable<std::u32string>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + std::u32string(), std::u32string(U"ABC"), std::u32string(U"ABC"), + std::u32string(U"Some other different string"), + std::u32string(U"Iñtërnâtiônàlizætiøn")))); +} + +TEST(HashValueTest, StdArray) { + EXPECT_TRUE((is_hashable<std::array<int, 3>>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(std::array<int, 3>{}, std::array<int, 3>{{0, 23, 42}}))); +} + +TEST(HashValueTest, StdBitset) { + EXPECT_TRUE((is_hashable<std::bitset<257>>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + {std::bitset<2>("00"), std::bitset<2>("01"), std::bitset<2>("10"), + std::bitset<2>("11")})); + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + {std::bitset<5>("10101"), std::bitset<5>("10001"), std::bitset<5>()})); + + constexpr int kNumBits = 256; + std::array<std::string, 6> bit_strings; + bit_strings.fill(std::string(kNumBits, '1')); + bit_strings[1][0] = '0'; + bit_strings[2][1] = '0'; + bit_strings[3][kNumBits / 3] = '0'; + bit_strings[4][kNumBits - 2] = '0'; + bit_strings[5][kNumBits - 1] = '0'; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + {std::bitset<kNumBits>(bit_strings[0].c_str()), + std::bitset<kNumBits>(bit_strings[1].c_str()), + std::bitset<kNumBits>(bit_strings[2].c_str()), + std::bitset<kNumBits>(bit_strings[3].c_str()), + std::bitset<kNumBits>(bit_strings[4].c_str()), + std::bitset<kNumBits>(bit_strings[5].c_str())})); +} // namespace + +template <typename T> +class HashValueSequenceTest : public testing::Test { +}; +TYPED_TEST_SUITE_P(HashValueSequenceTest); + +TYPED_TEST_P(HashValueSequenceTest, BasicUsage) { + EXPECT_TRUE((is_hashable<TypeParam>::value)); + + using ValueType = typename TypeParam::value_type; + auto a = static_cast<ValueType>(0); + auto b = static_cast<ValueType>(23); + auto c = static_cast<ValueType>(42); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(TypeParam(), TypeParam{}, TypeParam{a, b, c}, + TypeParam{a, b}, TypeParam{b, c}))); +} + +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>, std::set<int>, + std::multiset<int>>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueSequenceTest, IntSequenceTypes); + +// Private type that only supports AbslHashValue to make sure our chosen hash +// implementation is recursive within absl::Hash. +// It uses std::abs() on the value to provide different bitwise representations +// of the same logical value. +struct Private { + int i; + template <typename H> + friend H AbslHashValue(H h, Private p) { + return H::combine(std::move(h), std::abs(p.i)); + } + + friend bool operator==(Private a, Private b) { + return std::abs(a.i) == std::abs(b.i); + } + + friend std::ostream& operator<<(std::ostream& o, Private p) { + return o << p.i; + } +}; + +// Test helper for combine_piecewise_buffer. It holds a string_view to the +// buffer-to-be-hashed. Its AbslHashValue specialization will split up its +// contents at the character offsets requested. +class PiecewiseHashTester { + public: + // Create a hash view of a buffer to be hashed contiguously. + explicit PiecewiseHashTester(absl::string_view buf) + : buf_(buf), piecewise_(false), split_locations_() {} + + // Create a hash view of a buffer to be hashed piecewise, with breaks at the + // given locations. + PiecewiseHashTester(absl::string_view buf, std::set<size_t> split_locations) + : buf_(buf), + piecewise_(true), + split_locations_(std::move(split_locations)) {} + + template <typename H> + friend H AbslHashValue(H h, const PiecewiseHashTester& p) { + if (!p.piecewise_) { + return H::combine_contiguous(std::move(h), p.buf_.data(), p.buf_.size()); + } + absl::hash_internal::PiecewiseCombiner combiner; + if (p.split_locations_.empty()) { + h = combiner.add_buffer(std::move(h), p.buf_.data(), p.buf_.size()); + return combiner.finalize(std::move(h)); + } + size_t begin = 0; + for (size_t next : p.split_locations_) { + absl::string_view chunk = p.buf_.substr(begin, next - begin); + h = combiner.add_buffer(std::move(h), chunk.data(), chunk.size()); + begin = next; + } + absl::string_view last_chunk = p.buf_.substr(begin); + if (!last_chunk.empty()) { + h = combiner.add_buffer(std::move(h), last_chunk.data(), + last_chunk.size()); + } + return combiner.finalize(std::move(h)); + } + + private: + absl::string_view buf_; + bool piecewise_; + std::set<size_t> split_locations_; +}; + +// Dummy object that hashes as two distinct contiguous buffers, "foo" followed +// by "bar" +struct DummyFooBar { + template <typename H> + friend H AbslHashValue(H h, const DummyFooBar&) { + const char* foo = "foo"; + const char* bar = "bar"; + h = H::combine_contiguous(std::move(h), foo, 3); + h = H::combine_contiguous(std::move(h), bar, 3); + return h; + } +}; + +TEST(HashValueTest, CombinePiecewiseBuffer) { + absl::Hash<PiecewiseHashTester> hash; + + // Check that hashing an empty buffer through the piecewise API works. + EXPECT_EQ(hash(PiecewiseHashTester("")), hash(PiecewiseHashTester("", {}))); + + // Similarly, small buffers should give consistent results + EXPECT_EQ(hash(PiecewiseHashTester("foobar")), + hash(PiecewiseHashTester("foobar", {}))); + EXPECT_EQ(hash(PiecewiseHashTester("foobar")), + hash(PiecewiseHashTester("foobar", {3}))); + + // But hashing "foobar" in pieces gives a different answer than hashing "foo" + // contiguously, then "bar" contiguously. + EXPECT_NE(hash(PiecewiseHashTester("foobar", {3})), + absl::Hash<DummyFooBar>()(DummyFooBar{})); + + // Test hashing a large buffer incrementally, broken up in several different + // ways. Arrange for breaks on and near the stride boundaries to look for + // off-by-one errors in the implementation. + // + // This test is run on a buffer that is a multiple of the stride size, and one + // that isn't. + for (size_t big_buffer_size : {1024 * 2 + 512, 1024 * 3}) { + SCOPED_TRACE(big_buffer_size); + std::string big_buffer; + for (int i = 0; i < big_buffer_size; ++i) { + // Arbitrary string + big_buffer.push_back(32 + (i * (i / 3)) % 64); + } + auto big_buffer_hash = hash(PiecewiseHashTester(big_buffer)); + + const int possible_breaks = 9; + size_t breaks[possible_breaks] = {1, 512, 1023, 1024, 1025, + 1536, 2047, 2048, 2049}; + for (unsigned test_mask = 0; test_mask < (1u << possible_breaks); + ++test_mask) { + SCOPED_TRACE(test_mask); + std::set<size_t> break_locations; + for (int j = 0; j < possible_breaks; ++j) { + if (test_mask & (1u << j)) { + break_locations.insert(breaks[j]); + } + } + EXPECT_EQ( + hash(PiecewiseHashTester(big_buffer, std::move(break_locations))), + big_buffer_hash); + } + } +} + +TEST(HashValueTest, PrivateSanity) { + // Sanity check that Private is working as the tests below expect it to work. + EXPECT_TRUE(is_hashable<Private>::value); + EXPECT_NE(SpyHash(Private{0}), SpyHash(Private{1})); + EXPECT_EQ(SpyHash(Private{1}), SpyHash(Private{1})); +} + +TEST(HashValueTest, Optional) { + EXPECT_TRUE(is_hashable<absl::optional<Private>>::value); + + using O = absl::optional<Private>; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(O{}, O{{1}}, O{{-1}}, O{{10}}))); +} + +TEST(HashValueTest, Variant) { + using V = absl::variant<Private, std::string>; + EXPECT_TRUE(is_hashable<V>::value); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + V(Private{1}), V(Private{-1}), V(Private{2}), V("ABC"), V("BCD")))); + +#if ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ + struct S {}; + EXPECT_FALSE(is_hashable<absl::variant<S>>::value); +#endif +} + +TEST(HashValueTest, Maps) { + EXPECT_TRUE((is_hashable<std::map<int, std::string>>::value)); + + using M = std::map<int, std::string>; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + M{}, M{{0, "foo"}}, M{{1, "foo"}}, M{{0, "bar"}}, M{{1, "bar"}}, + M{{0, "foo"}, {42, "bar"}}, M{{1, "foo"}, {42, "bar"}}, + M{{1, "foo"}, {43, "bar"}}, M{{1, "foo"}, {43, "baz"}}))); + + using MM = std::multimap<int, std::string>; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + MM{}, MM{{0, "foo"}}, MM{{1, "foo"}}, MM{{0, "bar"}}, MM{{1, "bar"}}, + MM{{0, "foo"}, {0, "bar"}}, MM{{0, "bar"}, {0, "foo"}}, + MM{{0, "foo"}, {42, "bar"}}, MM{{1, "foo"}, {42, "bar"}}, + MM{{1, "foo"}, {1, "foo"}, {43, "bar"}}, MM{{1, "foo"}, {43, "baz"}}))); +} + +TEST(HashValueTest, ReferenceWrapper) { + EXPECT_TRUE(is_hashable<std::reference_wrapper<Private>>::value); + + Private p1{1}, p10{10}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + p1, p10, std::ref(p1), std::ref(p10), std::cref(p1), std::cref(p10)))); + + EXPECT_TRUE(is_hashable<std::reference_wrapper<int>>::value); + int one = 1, ten = 10; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + one, ten, std::ref(one), std::ref(ten), std::cref(one), std::cref(ten)))); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(std::tuple<std::reference_wrapper<int>>(std::ref(one)), + std::tuple<std::reference_wrapper<int>>(std::ref(ten)), + std::tuple<int>(one), std::tuple<int>(ten)))); +} + +template <typename T, typename = void> +struct IsHashCallable : std::false_type {}; + +template <typename T> +struct IsHashCallable<T, absl::void_t<decltype(std::declval<absl::Hash<T>>()( + std::declval<const T&>()))>> : std::true_type {}; + +template <typename T, typename = void> +struct IsAggregateInitializable : std::false_type {}; + +template <typename T> +struct IsAggregateInitializable<T, absl::void_t<decltype(T{})>> + : std::true_type {}; + +TEST(IsHashableTest, ValidHash) { + EXPECT_TRUE((is_hashable<int>::value)); + EXPECT_TRUE(std::is_default_constructible<absl::Hash<int>>::value); + EXPECT_TRUE(std::is_copy_constructible<absl::Hash<int>>::value); + EXPECT_TRUE(std::is_move_constructible<absl::Hash<int>>::value); + EXPECT_TRUE(absl::is_copy_assignable<absl::Hash<int>>::value); + EXPECT_TRUE(absl::is_move_assignable<absl::Hash<int>>::value); + EXPECT_TRUE(IsHashCallable<int>::value); + EXPECT_TRUE(IsAggregateInitializable<absl::Hash<int>>::value); +} + +#if ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ +TEST(IsHashableTest, PoisonHash) { + struct X {}; + EXPECT_FALSE((is_hashable<X>::value)); + EXPECT_FALSE(std::is_default_constructible<absl::Hash<X>>::value); + EXPECT_FALSE(std::is_copy_constructible<absl::Hash<X>>::value); + EXPECT_FALSE(std::is_move_constructible<absl::Hash<X>>::value); + EXPECT_FALSE(absl::is_copy_assignable<absl::Hash<X>>::value); + EXPECT_FALSE(absl::is_move_assignable<absl::Hash<X>>::value); + EXPECT_FALSE(IsHashCallable<X>::value); +#if !defined(__GNUC__) || __GNUC__ < 9 + // This doesn't compile on GCC 9. + EXPECT_FALSE(IsAggregateInitializable<absl::Hash<X>>::value); +#endif +} +#endif // ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ + +// Hashable types +// +// These types exist simply to exercise various AbslHashValue behaviors, so +// they are named by what their AbslHashValue overload does. +struct NoOp { + template <typename HashCode> + friend HashCode AbslHashValue(HashCode h, NoOp n) { + return h; + } +}; + +struct EmptyCombine { + template <typename HashCode> + friend HashCode AbslHashValue(HashCode h, EmptyCombine e) { + return HashCode::combine(std::move(h)); + } +}; + +template <typename Int> +struct CombineIterative { + template <typename HashCode> + friend HashCode AbslHashValue(HashCode h, CombineIterative c) { + for (int i = 0; i < 5; ++i) { + h = HashCode::combine(std::move(h), Int(i)); + } + return h; + } +}; + +template <typename Int> +struct CombineVariadic { + template <typename HashCode> + friend HashCode AbslHashValue(HashCode h, CombineVariadic c) { + return HashCode::combine(std::move(h), Int(0), Int(1), Int(2), Int(3), + Int(4)); + } +}; +enum class InvokeTag { + kUniquelyRepresented, + kHashValue, +#if ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ + kLegacyHash, +#endif // ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ + kStdHash, + kNone +}; + +template <InvokeTag T> +using InvokeTagConstant = std::integral_constant<InvokeTag, T>; + +template <InvokeTag... Tags> +struct MinTag; + +template <InvokeTag a, InvokeTag b, InvokeTag... Tags> +struct MinTag<a, b, Tags...> : MinTag<(a < b ? a : b), Tags...> {}; + +template <InvokeTag a> +struct MinTag<a> : InvokeTagConstant<a> {}; + +template <InvokeTag... Tags> +struct CustomHashType { + explicit CustomHashType(size_t val) : value(val) {} + size_t value; +}; + +template <InvokeTag allowed, InvokeTag... tags> +struct EnableIfContained + : std::enable_if<absl::disjunction< + std::integral_constant<bool, allowed == tags>...>::value> {}; + +template < + typename H, InvokeTag... Tags, + typename = typename EnableIfContained<InvokeTag::kHashValue, Tags...>::type> +H AbslHashValue(H state, CustomHashType<Tags...> t) { + static_assert(MinTag<Tags...>::value == InvokeTag::kHashValue, ""); + return H::combine(std::move(state), + t.value + static_cast<int>(InvokeTag::kHashValue)); +} + +} // namespace + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace hash_internal { +template <InvokeTag... Tags> +struct is_uniquely_represented< + CustomHashType<Tags...>, + typename EnableIfContained<InvokeTag::kUniquelyRepresented, Tags...>::type> + : std::true_type {}; +} // namespace hash_internal +ABSL_NAMESPACE_END +} // namespace absl + +#if ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ +namespace ABSL_INTERNAL_LEGACY_HASH_NAMESPACE { +template <InvokeTag... Tags> +struct hash<CustomHashType<Tags...>> { + template <InvokeTag... TagsIn, typename = typename EnableIfContained< + InvokeTag::kLegacyHash, TagsIn...>::type> + size_t operator()(CustomHashType<TagsIn...> t) const { + static_assert(MinTag<Tags...>::value == InvokeTag::kLegacyHash, ""); + return t.value + static_cast<int>(InvokeTag::kLegacyHash); + } +}; +} // namespace ABSL_INTERNAL_LEGACY_HASH_NAMESPACE +#endif // ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ + +namespace std { +template <InvokeTag... Tags> // NOLINT +struct hash<CustomHashType<Tags...>> { + template <InvokeTag... TagsIn, typename = typename EnableIfContained< + InvokeTag::kStdHash, TagsIn...>::type> + size_t operator()(CustomHashType<TagsIn...> t) const { + static_assert(MinTag<Tags...>::value == InvokeTag::kStdHash, ""); + return t.value + static_cast<int>(InvokeTag::kStdHash); + } +}; +} // namespace std + +namespace { + +template <typename... T> +void TestCustomHashType(InvokeTagConstant<InvokeTag::kNone>, T...) { + using type = CustomHashType<T::value...>; + SCOPED_TRACE(testing::PrintToString(std::vector<InvokeTag>{T::value...})); + EXPECT_TRUE(is_hashable<type>()); + EXPECT_TRUE(is_hashable<const type>()); + EXPECT_TRUE(is_hashable<const type&>()); + + const size_t offset = static_cast<int>(std::min({T::value...})); + EXPECT_EQ(SpyHash(type(7)), SpyHash(size_t{7 + offset})); +} + +void TestCustomHashType(InvokeTagConstant<InvokeTag::kNone>) { +#if ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ + // is_hashable is false if we don't support any of the hooks. + using type = CustomHashType<>; + EXPECT_FALSE(is_hashable<type>()); + EXPECT_FALSE(is_hashable<const type>()); + EXPECT_FALSE(is_hashable<const type&>()); +#endif // ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ +} + +template <InvokeTag Tag, typename... T> +void TestCustomHashType(InvokeTagConstant<Tag> tag, T... t) { + constexpr auto next = static_cast<InvokeTag>(static_cast<int>(Tag) + 1); + TestCustomHashType(InvokeTagConstant<next>(), tag, t...); + TestCustomHashType(InvokeTagConstant<next>(), t...); +} + +TEST(HashTest, CustomHashType) { + TestCustomHashType(InvokeTagConstant<InvokeTag{}>()); +} + +TEST(HashTest, NoOpsAreEquivalent) { + EXPECT_EQ(Hash<NoOp>()({}), Hash<NoOp>()({})); + EXPECT_EQ(Hash<NoOp>()({}), Hash<EmptyCombine>()({})); +} + +template <typename T> +class HashIntTest : public testing::Test { +}; +TYPED_TEST_SUITE_P(HashIntTest); + +TYPED_TEST_P(HashIntTest, BasicUsage) { + EXPECT_NE(Hash<NoOp>()({}), Hash<TypeParam>()(0)); + EXPECT_NE(Hash<NoOp>()({}), + Hash<TypeParam>()(std::numeric_limits<TypeParam>::max())); + if (std::numeric_limits<TypeParam>::min() != 0) { + EXPECT_NE(Hash<NoOp>()({}), + Hash<TypeParam>()(std::numeric_limits<TypeParam>::min())); + } + + EXPECT_EQ(Hash<CombineIterative<TypeParam>>()({}), + Hash<CombineVariadic<TypeParam>>()({})); +} + +REGISTER_TYPED_TEST_CASE_P(HashIntTest, BasicUsage); +using IntTypes = testing::Types<unsigned char, char, int, int32_t, int64_t, uint32_t, + uint64_t, size_t>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashIntTest, IntTypes); + +struct StructWithPadding { + char c; + int i; + + template <typename H> + friend H AbslHashValue(H hash_state, const StructWithPadding& s) { + return H::combine(std::move(hash_state), s.c, s.i); + } +}; + +static_assert(sizeof(StructWithPadding) > sizeof(char) + sizeof(int), + "StructWithPadding doesn't have padding"); +static_assert(std::is_standard_layout<StructWithPadding>::value, ""); + +// This check has to be disabled because libstdc++ doesn't support it. +// static_assert(std::is_trivially_constructible<StructWithPadding>::value, ""); + +template <typename T> +struct ArraySlice { + T* begin; + T* end; + + template <typename H> + friend H AbslHashValue(H hash_state, const ArraySlice& slice) { + for (auto t = slice.begin; t != slice.end; ++t) { + hash_state = H::combine(std::move(hash_state), *t); + } + return hash_state; + } +}; + +TEST(HashTest, HashNonUniquelyRepresentedType) { + // Create equal StructWithPadding objects that are known to have non-equal + // padding bytes. + static const size_t kNumStructs = 10; + unsigned char buffer1[kNumStructs * sizeof(StructWithPadding)]; + std::memset(buffer1, 0, sizeof(buffer1)); + auto* s1 = reinterpret_cast<StructWithPadding*>(buffer1); + + unsigned char buffer2[kNumStructs * sizeof(StructWithPadding)]; + std::memset(buffer2, 255, sizeof(buffer2)); + auto* s2 = reinterpret_cast<StructWithPadding*>(buffer2); + for (int i = 0; i < kNumStructs; ++i) { + SCOPED_TRACE(i); + s1[i].c = s2[i].c = '0' + i; + s1[i].i = s2[i].i = i; + ASSERT_FALSE(memcmp(buffer1 + i * sizeof(StructWithPadding), + buffer2 + i * sizeof(StructWithPadding), + sizeof(StructWithPadding)) == 0) + << "Bug in test code: objects do not have unequal" + << " object representations"; + } + + EXPECT_EQ(Hash<StructWithPadding>()(s1[0]), Hash<StructWithPadding>()(s2[0])); + EXPECT_EQ(Hash<ArraySlice<StructWithPadding>>()({s1, s1 + kNumStructs}), + Hash<ArraySlice<StructWithPadding>>()({s2, s2 + kNumStructs})); +} + +TEST(HashTest, StandardHashContainerUsage) { + std::unordered_map<int, std::string, Hash<int>> map = {{0, "foo"}, + {42, "bar"}}; + + EXPECT_NE(map.find(0), map.end()); + EXPECT_EQ(map.find(1), map.end()); + EXPECT_NE(map.find(0u), map.end()); +} + +struct ConvertibleFromNoOp { + ConvertibleFromNoOp(NoOp) {} // NOLINT(runtime/explicit) + + template <typename H> + friend H AbslHashValue(H hash_state, ConvertibleFromNoOp) { + return H::combine(std::move(hash_state), 1); + } +}; + +TEST(HashTest, HeterogeneousCall) { + EXPECT_NE(Hash<ConvertibleFromNoOp>()(NoOp()), + Hash<NoOp>()(NoOp())); +} + +TEST(IsUniquelyRepresentedTest, SanityTest) { + using absl::hash_internal::is_uniquely_represented; + + EXPECT_TRUE(is_uniquely_represented<unsigned char>::value); + EXPECT_TRUE(is_uniquely_represented<int>::value); + EXPECT_FALSE(is_uniquely_represented<bool>::value); + EXPECT_FALSE(is_uniquely_represented<int*>::value); +} + +struct IntAndString { + int i; + std::string s; + + template <typename H> + friend H AbslHashValue(H hash_state, IntAndString int_and_string) { + return H::combine(std::move(hash_state), int_and_string.s, + int_and_string.i); + } +}; + +TEST(HashTest, SmallValueOn64ByteBoundary) { + Hash<IntAndString>()(IntAndString{0, std::string(63, '0')}); +} + +struct TypeErased { + size_t n; + + template <typename H> + friend H AbslHashValue(H hash_state, const TypeErased& v) { + v.HashValue(absl::HashState::Create(&hash_state)); + return hash_state; + } + + void HashValue(absl::HashState state) const { + absl::HashState::combine(std::move(state), n); + } +}; + +TEST(HashTest, TypeErased) { + EXPECT_TRUE((is_hashable<TypeErased>::value)); + EXPECT_TRUE((is_hashable<std::pair<TypeErased, int>>::value)); + + EXPECT_EQ(SpyHash(TypeErased{7}), SpyHash(size_t{7})); + EXPECT_NE(SpyHash(TypeErased{7}), SpyHash(size_t{13})); + + EXPECT_EQ(SpyHash(std::make_pair(TypeErased{7}, 17)), + SpyHash(std::make_pair(size_t{7}, 17))); +} + +struct ValueWithBoolConversion { + operator bool() const { return false; } + int i; +}; + +} // namespace +namespace std { +template <> +struct hash<ValueWithBoolConversion> { + size_t operator()(ValueWithBoolConversion v) { return v.i; } +}; +} // namespace std + +namespace { + +TEST(HashTest, DoesNotUseImplicitConversionsToBool) { + EXPECT_NE(absl::Hash<ValueWithBoolConversion>()(ValueWithBoolConversion{0}), + absl::Hash<ValueWithBoolConversion>()(ValueWithBoolConversion{1})); +} + +} // namespace |