From 48cd2c3f351ff188bc85684b84a91b6e6d17d896 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 27 Sep 2018 12:24:54 -0700 Subject: Export of internal Abseil changes. -- 4eacae3ff1b14b1d309e8092185bc10e8a6203cf by Derek Mauro : Release SwissTable - a fast, efficient, cache-friendly hash table. https://www.youtube.com/watch?v=ncHmEUmJZf4 PiperOrigin-RevId: 214816527 -- df8c3dfab3cfb2f4365909a84d0683b193cfbb11 by Derek Mauro : Internal change PiperOrigin-RevId: 214785288 -- 1eabd5266bbcebc33eecc91e5309b751856a75c8 by Abseil Team : Internal change PiperOrigin-RevId: 214722931 -- 2ebbfac950f83146b46253038e7dd7dcde9f2951 by Derek Mauro : Internal change PiperOrigin-RevId: 214701684 GitOrigin-RevId: 4eacae3ff1b14b1d309e8092185bc10e8a6203cf Change-Id: I9ba64e395b22ad7863213d157b8019b082adc19d --- absl/hash/BUILD.bazel | 114 +++ absl/hash/CMakeLists.txt | 80 ++ absl/hash/hash.h | 312 ++++++ absl/hash/hash_test.cc | 425 ++++++++ absl/hash/hash_testing.h | 372 +++++++ absl/hash/internal/city.cc | 589 ++++++++++++ absl/hash/internal/city.h | 108 +++ absl/hash/internal/city_crc.h | 41 + absl/hash/internal/city_test.cc | 1812 +++++++++++++++++++++++++++++++++++ absl/hash/internal/hash.cc | 23 + absl/hash/internal/hash.h | 885 +++++++++++++++++ absl/hash/internal/print_hash_of.cc | 23 + absl/hash/internal/spy_hash_state.h | 218 +++++ 13 files changed, 5002 insertions(+) create mode 100644 absl/hash/BUILD.bazel create mode 100644 absl/hash/CMakeLists.txt create mode 100644 absl/hash/hash.h create mode 100644 absl/hash/hash_test.cc create mode 100644 absl/hash/hash_testing.h create mode 100644 absl/hash/internal/city.cc create mode 100644 absl/hash/internal/city.h create mode 100644 absl/hash/internal/city_crc.h create mode 100644 absl/hash/internal/city_test.cc create mode 100644 absl/hash/internal/hash.cc create mode 100644 absl/hash/internal/hash.h create mode 100644 absl/hash/internal/print_hash_of.cc create mode 100644 absl/hash/internal/spy_hash_state.h (limited to 'absl/hash') diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel new file mode 100644 index 0000000..50aa550 --- /dev/null +++ b/absl/hash/BUILD.bazel @@ -0,0 +1,114 @@ +# +# 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 +# +# http://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. +# + +load( + "//absl:copts.bzl", + "ABSL_DEFAULT_COPTS", + "ABSL_TEST_COPTS", +) + +package(default_visibility = ["//visibility:public"]) + +licenses(["notice"]) # Apache 2.0 + +cc_library( + name = "hash", + srcs = [ + "internal/hash.cc", + "internal/hash.h", + ], + hdrs = ["hash.h"], + copts = ABSL_DEFAULT_COPTS, + deps = [ + ":city", + "//absl/base:core_headers", + "//absl/base:endian", + "//absl/container:fixed_array", + "//absl/meta:type_traits", + "//absl/numeric:int128", + "//absl/strings", + "//absl/types:optional", + "//absl/types:variant", + "//absl/utility", + ], +) + +cc_library( + name = "hash_testing", + testonly = 1, + hdrs = ["hash_testing.h"], + deps = [ + ":spy_hash_state", + "//absl/meta:type_traits", + "//absl/strings", + "//absl/types:variant", + "@com_google_googletest//:gtest", + ], +) + +cc_test( + name = "hash_test", + srcs = ["hash_test.cc"], + copts = ABSL_TEST_COPTS, + deps = [ + ":hash", + ":hash_testing", + "//absl/base:core_headers", + "//absl/container:flat_hash_set", + "//absl/hash:spy_hash_state", + "//absl/meta:type_traits", + "//absl/numeric:int128", + "@com_google_googletest//:gtest_main", + ], +) + +cc_library( + name = "spy_hash_state", + testonly = 1, + hdrs = ["internal/spy_hash_state.h"], + copts = ABSL_DEFAULT_COPTS, + visibility = ["//visibility:private"], + deps = [ + ":hash", + "//absl/strings", + "//absl/strings:str_format", + ], +) + +cc_library( + name = "city", + srcs = ["internal/city.cc"], + hdrs = [ + "internal/city.h", + "internal/city_crc.h", + ], + copts = ABSL_DEFAULT_COPTS, + deps = [ + "//absl/base:config", + "//absl/base:core_headers", + "//absl/base:endian", + ], +) + +cc_test( + name = "city_test", + srcs = ["internal/city_test.cc"], + copts = ABSL_TEST_COPTS, + deps = [ + ":city", + "@com_google_googletest//:gtest_main", + ], +) diff --git a/absl/hash/CMakeLists.txt b/absl/hash/CMakeLists.txt new file mode 100644 index 0000000..35081e3 --- /dev/null +++ b/absl/hash/CMakeLists.txt @@ -0,0 +1,80 @@ +# +# 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 +# +# http://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. +# + +list(APPEND HASH_PUBLIC_HEADERS + "hash.h" +) + +list(APPEND HASH_INTERNAL_HEADERS + "internal/city.h" + "internal/city_crc.h" + "internal/hash.h" +) + +# absl_hash library +list(APPEND HASH_SRC + "internal/city.cc" + "internal/hash.cc" + ${HASH_PUBLIC_HEADERS} + ${HASH_INTERNAL_HEADERS} +) + +set(HASH_PUBLIC_LIBRARIES absl::hash absl::container absl::strings absl::str_format absl::utility) + +absl_library( + TARGET + absl_hash + SOURCES + ${HASH_SRC} + PUBLIC_LIBRARIES + ${HASH_PUBLIC_LIBRARIES} + EXPORT_NAME + hash +) + +# +## TESTS +# + +# testing support +set(HASH_TEST_HEADERS hash_testing.h internal/spy_hash_state.h) +set(HASH_TEST_PUBLIC_LIBRARIES absl::hash absl::container absl::numeric absl::strings absl::str_format) + +# hash_test +set(HASH_TEST_SRC "hash_test.cc" ${HASH_TEST_HEADERS}) + +absl_test( + TARGET + hash_test + SOURCES + ${HASH_TEST_SRC} + PUBLIC_LIBRARIES + ${HASH_TEST_PUBLIC_LIBRARIES} +) + +# hash_test +set(CITY_TEST_SRC "internal/city_test.cc") + +absl_test( + TARGET + city_test + SOURCES + ${CITY_TEST_SRC} + PUBLIC_LIBRARIES + ${HASH_TEST_PUBLIC_LIBRARIES} +) + + diff --git a/absl/hash/hash.h b/absl/hash/hash.h new file mode 100644 index 0000000..c7ba4c2 --- /dev/null +++ b/absl/hash/hash.h @@ -0,0 +1,312 @@ +// 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 +// +// http://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. +// +// ----------------------------------------------------------------------------- +// File: hash.h +// ----------------------------------------------------------------------------- +// +// This header file defines the Abseil `hash` library and the Abseil hashing +// framework. This framework consists of the following: +// +// * The `absl::Hash` functor, which is used to invoke the hasher within the +// Abseil hashing framework. `absl::Hash` supports most basic types and +// a number of Abseil types out of the box. +// * `AbslHashValue`, an extension point that allows you to extend types to +// support Abseil hashing without requiring you to define a hashing +// algorithm. +// * `HashState`, a type-erased class which implement the manipulation of the +// hash state (H) itself. containing member functions `combine()` and +// `combine_contiguous()`, which you can use to contribute to an existing +// hash state when hashing your types. +// +// Unlike `std::hash` or other hashing frameworks, the Abseil hashing framework +// provides most of its utility by abstracting away the hash algorithm (and its +// implementation) entirely. Instead, a type invokes the Abseil hashing +// framework by simply combining its state with the state of known, hashable +// types. Hashing of that combined state is separately done by `absl::Hash`. +// +// Example: +// +// // Suppose we have a class `Circle` for which we want to add hashing +// class Circle { +// public: +// ... +// private: +// std::pair center_; +// int radius_; +// }; +// +// // To add hashing support to `Circle`, we simply need to add an ordinary +// // function `AbslHashValue()`, and return the combined hash state of the +// // existing hash state and the class state: +// +// template +// friend H AbslHashValue(H h, const Circle& c) { +// return H::combine(std::move(h), c.center_, c.radius_); +// } +// +// For more information, see Adding Type Support to `absl::Hash` below. +// +#ifndef ABSL_HASH_HASH_H_ +#define ABSL_HASH_HASH_H_ + +#include "absl/hash/internal/hash.h" + +namespace absl { + +// ----------------------------------------------------------------------------- +// `absl::Hash` +// ----------------------------------------------------------------------------- +// +// `absl::Hash` is a convenient general-purpose hash functor for a type `T` +// satisfying any of the following conditions (in order): +// +// * T is an arithmetic or pointer type +// * T defines an overload for `AbslHashValue(H, const T&)` for an arbitrary +// hash state `H`. +// - T defines a specialization of `HASH_NAMESPACE::hash` +// - T defines a specialization of `std::hash` +// +// `absl::Hash` intrinsically supports the following types: +// +// * All integral types (including bool) +// * All enum types +// * All floating-point types (although hashing them is discouraged) +// * All pointer types, including nullptr_t +// * std::pair, if T1 and T2 are hashable +// * std::tuple, if all the Ts... are hashable +// * std::unique_ptr and std::shared_ptr +// * All string-like types including: +// * std::string +// * std::string_view (as well as any instance of std::basic_string that +// uses char and std::char_traits) +// * All the standard sequence containers (provided the elements are hashable) +// * All the standard ordered associative containers (provided the elements are +// hashable) +// * absl types such as the following: +// * absl::string_view +// * absl::InlinedVector +// * absl::FixedArray +// * absl::unit128 +// * absl::Time, absl::Duration, and absl::TimeZone +// +// Note: the list above is not meant to be exhaustive. Additional type support +// may be added, in which case the above list will be updated. +// +// ----------------------------------------------------------------------------- +// absl::Hash Invocation Evaluation +// ----------------------------------------------------------------------------- +// +// When invoked, `absl::Hash` searches for supplied hash functions in the +// following order: +// +// * Natively supported types out of the box (see above) +// * Types for which an `AbslHashValue()` overload is provided (such as +// user-defined types). See "Adding Type Support to `absl::Hash`" below. +// * Types which define a `HASH_NAMESPACE::hash` specialization (aka +// `__gnu_cxx::hash` for gcc/Clang or `stdext::hash` for MSVC) +// * Types which define a `std::hash` specialization +// +// The fallback to legacy hash functions exists mainly for backwards +// compatibility. If you have a choice, prefer defining an `AbslHashValue` +// overload instead of specializing any legacy hash functors. +// +// ----------------------------------------------------------------------------- +// The Hash State Concept, and using `HashState` for Type Erasure +// ----------------------------------------------------------------------------- +// +// The `absl::Hash` framework relies on the Concept of a "hash state." Such a +// hash state is used in several places: +// +// * Within existing implementations of `absl::Hash` to store the hashed +// state of an object. Note that it is up to the implementation how it stores +// such state. A hash table, for example, may mix the state to produce an +// integer value; a testing framework may simply hold a vector of that state. +// * Within implementations of `AbslHashValue()` used to extend user-defined +// types. (See "Adding Type Support to absl::Hash" below.) +// * Inside a `HashState`, providing type erasure for the concept of a hash +// state, which you can use to extend the `absl::Hash` framework for types +// that are otherwise difficult to extend using `AbslHashValue()`. (See the +// `HashState` class below.) +// +// The "hash state" concept contains two member functions for mixing hash state: +// +// * `H::combine()` +// +// Combines an arbitrary number of values into a hash state, returning the +// updated state. Note that the existing hash state is move-only and must be +// passed by value. +// +// Each of the value types T must be hashable by H. +// +// NOTE: +// +// state = H::combine(std::move(state), value1, value2, value3); +// +// must be guaranteed to produce the same hash expansion as +// +// state = H::combine(std::move(state), value1); +// state = H::combine(std::move(state), value2); +// state = H::combine(std::move(state), value3); +// +// * `H::combine_contiguous()` +// +// Combines a contiguous array of `size` elements into a hash state, +// returning the updated state. Note that the existing hash state is +// move-only and must be passed by value. +// +// NOTE: +// +// state = H::combine_contiguous(std::move(state), data, size); +// +// need NOT be guaranteed to produce the same hash expansion as a loop +// (it may perform internal optimizations). If you need this guarantee, use a +// loop instead. +// +// ----------------------------------------------------------------------------- +// Adding Type Support to `absl::Hash` +// ----------------------------------------------------------------------------- +// +// To add support for your user-defined type, add a proper `AbslHashValue()` +// overload as a free (non-member) function. The overload will take an +// existing hash state and should combine that state with state from the type. +// +// Example: +// +// template +// H AbslHashValue(H state, const MyType& v) { +// return H::combine(std::move(state), v.field1, ..., v.fieldN); +// } +// +// where `(field1, ..., fieldN)` are the members you would use on your +// `operator==` to define equality. +// +// Notice that `AbslHashValue` is not a class member, but an ordinary function. +// An `AbslHashValue` overload for a type should only be declared in the same +// file and namespace as said type. The proper `AbslHashValue` implementation +// for a given type will be discovered via ADL. +// +// Note: unlike `std::hash', `absl::Hash` should never be specialized. It must +// only be extended by adding `AbslHashValue()` overloads. +// +template +using Hash = absl::hash_internal::Hash; + +// HashState +// +// A type erased version of the hash state concept, for use in user-defined +// `AbslHashValue` implementations that can't use templates (such as PImpl +// classes, virtual functions, etc.). The type erasure adds overhead so it +// should be avoided unless necessary. +// +// Note: This wrapper will only erase calls to: +// combine_contiguous(H, const unsigned char*, size_t) +// +// All other calls will be handled internally and will not invoke overloads +// provided by the wrapped class. +// +// Users of this class should still define a template `AbslHashValue` function, +// but can use `absl::HashState::Create(&state)` to erase the type of the hash +// state and dispatch to their private hashing logic. +// +// This state can be used like any other hash state. In particular, you can call +// `HashState::combine()` and `HashState::combine_contiguous()` on it. +// +// Example: +// +// class Interface { +// public: +// template +// friend H AbslHashValue(H state, const Interface& value) { +// state = H::combine(std::move(state), std::type_index(typeid(*this))); +// value.HashValue(absl::HashState::Create(&state)); +// return state; +// } +// private: +// virtual void HashValue(absl::HashState state) const = 0; +// }; +// +// class Impl : Interface { +// private: +// void HashValue(absl::HashState state) const override { +// absl::HashState::combine(std::move(state), v1_, v2_); +// } +// int v1_; +// string v2_; +// }; +class HashState : public hash_internal::HashStateBase { + public: + // HashState::Create() + // + // Create a new `HashState` instance that wraps `state`. All calls to + // `combine()` and `combine_contiguous()` on the new instance will be + // redirected to the original `state` object. The `state` object must outlive + // the `HashState` instance. + template + static HashState Create(T* state) { + HashState s; + s.Init(state); + return s; + } + + HashState(const HashState&) = delete; + HashState& operator=(const HashState&) = delete; + HashState(HashState&&) = default; + HashState& operator=(HashState&&) = default; + + // HashState::combine() + // + // Combines an arbitrary number of values into a hash state, returning the + // updated state. + using HashState::HashStateBase::combine; + + // HashState::combine_contiguous() + // + // Combines a contiguous array of `size` elements into a hash state, returning + // the updated state. + static HashState combine_contiguous(HashState hash_state, + const unsigned char* first, size_t size) { + hash_state.combine_contiguous_(hash_state.state_, first, size); + return hash_state; + } + using HashState::HashStateBase::combine_contiguous; + + private: + HashState() = default; + + template + static void CombineContiguousImpl(void* p, const unsigned char* first, + size_t size) { + T& state = *static_cast(p); + state = T::combine_contiguous(std::move(state), first, size); + } + + template + void Init(T* state) { + state_ = state; + combine_contiguous_ = &CombineContiguousImpl; + } + + // Do not erase an already erased state. + void Init(HashState* state) { + state_ = state->state_; + combine_contiguous_ = state->combine_contiguous_; + } + + void* state_; + void (*combine_contiguous_)(void*, const unsigned char*, size_t); +}; + +} // namespace absl +#endif // ABSL_HASH_HASH_H_ diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc new file mode 100644 index 0000000..7b6fb2e --- /dev/null +++ b/absl/hash/hash_test.cc @@ -0,0 +1,425 @@ +// 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 +// +// http://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 +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#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" + +namespace { + +using absl::Hash; +using absl::hash_internal::SpyHashState; + +template +class HashValueIntTest : public testing::Test { +}; +TYPED_TEST_CASE_P(HashValueIntTest); + +template +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 +using is_hashable = std::is_default_constructible>; + +TYPED_TEST_P(HashValueIntTest, BasicUsage) { + EXPECT_TRUE((is_hashable::value)); + + TypeParam n = 42; + EXPECT_EQ(SpyHash(n), SpyHash(TypeParam{42})); + EXPECT_NE(SpyHash(n), SpyHash(TypeParam{0})); + EXPECT_NE(SpyHash(std::numeric_limits::max()), + SpyHash(std::numeric_limits::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{}(n), + absl::Hash>{}(std::tuple(n))); +} + +REGISTER_TYPED_TEST_CASE_P(HashValueIntTest, BasicUsage, FastPath); +using IntTypes = testing::Types; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueIntTest, IntTypes); + +template +struct IsHashCallble : std::false_type {}; + +template +struct IsHashCallble>()( + std::declval()))>> : std::true_type {}; + +template +struct IsAggregateInitializable : std::false_type {}; + +template +struct IsAggregateInitializable> + : std::true_type {}; + +TEST(IsHashableTest, ValidHash) { + EXPECT_TRUE((is_hashable::value)); + EXPECT_TRUE(std::is_default_constructible>::value); + EXPECT_TRUE(std::is_copy_constructible>::value); + EXPECT_TRUE(std::is_move_constructible>::value); + EXPECT_TRUE(absl::is_copy_assignable>::value); + EXPECT_TRUE(absl::is_move_assignable>::value); + EXPECT_TRUE(IsHashCallble::value); + EXPECT_TRUE(IsAggregateInitializable>::value); +} +#if ABSL_HASH_INTERNAL_CAN_POISON_ && !defined(__APPLE__) +TEST(IsHashableTest, PoisonHash) { + struct X {}; + EXPECT_FALSE((is_hashable::value)); + EXPECT_FALSE(std::is_default_constructible>::value); + EXPECT_FALSE(std::is_copy_constructible>::value); + EXPECT_FALSE(std::is_move_constructible>::value); + EXPECT_FALSE(absl::is_copy_assignable>::value); + EXPECT_FALSE(absl::is_move_assignable>::value); + EXPECT_FALSE(IsHashCallble::value); + EXPECT_FALSE(IsAggregateInitializable>::value); +} +#endif // ABSL_HASH_INTERNAL_CAN_POISON_ + +// Hashable types +// +// These types exist simply to exercise various AbslHashValue behaviors, so +// they are named by what their AbslHashValue overload does. +struct NoOp { + template + friend HashCode AbslHashValue(HashCode h, NoOp n) { + return std::move(h); + } +}; + +struct EmptyCombine { + template + friend HashCode AbslHashValue(HashCode h, EmptyCombine e) { + return HashCode::combine(std::move(h)); + } +}; + +template +struct CombineIterative { + template + 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 +struct CombineVariadic { + template + friend HashCode AbslHashValue(HashCode h, CombineVariadic c) { + return HashCode::combine(std::move(h), Int(0), Int(1), Int(2), Int(3), + Int(4)); + } +}; + +using InvokeTag = absl::hash_internal::InvokeHashTag; +template +using InvokeTagConstant = std::integral_constant; + +template +struct MinTag; + +template +struct MinTag : MinTag<(a < b ? a : b), Tags...> {}; + +template +struct MinTag : InvokeTagConstant {}; + +template +struct CustomHashType { + size_t value; +}; + +template +struct EnableIfContained + : std::enable_if...>::value> {}; + +template < + typename H, InvokeTag... Tags, + typename = typename EnableIfContained::type> +H AbslHashValue(H state, CustomHashType t) { + static_assert(MinTag::value == InvokeTag::kHashValue, ""); + return H::combine(std::move(state), + t.value + static_cast(InvokeTag::kHashValue)); +} + +} // namespace + +namespace absl { +namespace hash_internal { +template +struct is_uniquely_represented< + CustomHashType, + typename EnableIfContained::type> + : std::true_type {}; +} // namespace hash_internal +} // namespace absl + +#if ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ +namespace ABSL_INTERNAL_LEGACY_HASH_NAMESPACE { +template +struct hash> { + template ::type> + size_t operator()(CustomHashType t) const { + static_assert(MinTag::value == InvokeTag::kLegacyHash, ""); + return t.value + static_cast(InvokeTag::kLegacyHash); + } +}; +} // namespace ABSL_INTERNAL_LEGACY_HASH_NAMESPACE +#endif // ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ + +namespace std { +template // NOLINT +struct hash> { + template ::type> + size_t operator()(CustomHashType t) const { + static_assert(MinTag::value == InvokeTag::kStdHash, ""); + return t.value + static_cast(InvokeTag::kStdHash); + } +}; +} // namespace std + +namespace { + +template +void TestCustomHashType(InvokeTagConstant, T...) { + using type = CustomHashType; + SCOPED_TRACE(testing::PrintToString(std::vector{T::value...})); + EXPECT_TRUE(is_hashable()); + EXPECT_TRUE(is_hashable()); + EXPECT_TRUE(is_hashable()); + + const size_t offset = static_cast(std::min({T::value...})); + EXPECT_EQ(SpyHash(type{7}), SpyHash(size_t{7 + offset})); +} + +void TestCustomHashType(InvokeTagConstant) { +#if ABSL_HASH_INTERNAL_CAN_POISON_ + // is_hashable is false if we don't support any of the hooks. + using type = CustomHashType<>; + EXPECT_FALSE(is_hashable()); + EXPECT_FALSE(is_hashable()); + EXPECT_FALSE(is_hashable()); +#endif // ABSL_HASH_INTERNAL_CAN_POISON_ +} + +template +void TestCustomHashType(InvokeTagConstant tag, T... t) { + constexpr auto next = static_cast(static_cast(Tag) + 1); + TestCustomHashType(InvokeTagConstant(), tag, t...); + TestCustomHashType(InvokeTagConstant(), t...); +} + +TEST(HashTest, CustomHashType) { + TestCustomHashType(InvokeTagConstant()); +} + +TEST(HashTest, NoOpsAreEquivalent) { + EXPECT_EQ(Hash()({}), Hash()({})); + EXPECT_EQ(Hash()({}), Hash()({})); +} + +template +class HashIntTest : public testing::Test { +}; +TYPED_TEST_CASE_P(HashIntTest); + +TYPED_TEST_P(HashIntTest, BasicUsage) { + EXPECT_NE(Hash()({}), Hash()(0)); + EXPECT_NE(Hash()({}), + Hash()(std::numeric_limits::max())); + if (std::numeric_limits::min() != 0) { + EXPECT_NE(Hash()({}), + Hash()(std::numeric_limits::min())); + } + + EXPECT_EQ(Hash>()({}), + Hash>()({})); +} + +REGISTER_TYPED_TEST_CASE_P(HashIntTest, BasicUsage); +using IntTypes = testing::Types; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashIntTest, IntTypes); + +struct StructWithPadding { + char c; + int i; + + template + 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::value, ""); + +// This check has to be disabled because libstdc++ doesn't support it. +// static_assert(std::is_trivially_constructible::value, ""); + +template +struct ArraySlice { + T* begin; + T* end; + + template + 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(buffer1); + + unsigned char buffer2[kNumStructs * sizeof(StructWithPadding)]; + std::memset(buffer2, 255, sizeof(buffer2)); + auto* s2 = reinterpret_cast(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()(s1[0]), Hash()(s2[0])); + EXPECT_EQ(Hash>()({s1, s1 + kNumStructs}), + Hash>()({s2, s2 + kNumStructs})); +} + +TEST(HashTest, StandardHashContainerUsage) { + std::unordered_map> 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 + friend H AbslHashValue(H hash_state, ConvertibleFromNoOp) { + return H::combine(std::move(hash_state), 1); + } +}; + +TEST(HashTest, HeterogeneousCall) { + EXPECT_NE(Hash()(NoOp()), + Hash()(NoOp())); +} + +TEST(IsUniquelyRepresentedTest, SanityTest) { + using absl::hash_internal::is_uniquely_represented; + + EXPECT_TRUE(is_uniquely_represented::value); + EXPECT_TRUE(is_uniquely_represented::value); + EXPECT_FALSE(is_uniquely_represented::value); + EXPECT_FALSE(is_uniquely_represented::value); +} + +struct IntAndString { + int i; + std::string s; + + template + 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{0, std::string(63, '0')}); +} + +struct TypeErased { + size_t n; + + template + 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::value)); + EXPECT_TRUE((is_hashable>::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))); +} + +} // namespace diff --git a/absl/hash/hash_testing.h b/absl/hash/hash_testing.h new file mode 100644 index 0000000..1e3cda6 --- /dev/null +++ b/absl/hash/hash_testing.h @@ -0,0 +1,372 @@ +// 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 +// +// http://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. + +#ifndef ABSL_HASH_HASH_TESTING_H_ +#define ABSL_HASH_HASH_TESTING_H_ + +#include +#include +#include +#include + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/hash/internal/spy_hash_state.h" +#include "absl/meta/type_traits.h" +#include "absl/strings/str_cat.h" +#include "absl/types/variant.h" + +namespace absl { + +// Run the absl::Hash algorithm over all the elements passed in and verify that +// their hash expansion is congruent with their `==` operator. +// +// It is used in conjunction with EXPECT_TRUE. Failures will output information +// on what requirement failed and on which objects. +// +// Users should pass a collection of types as either an initializer list or a +// container of cases. +// +// EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( +// {v1, v2, ..., vN})); +// +// std::vector cases; +// // Fill cases... +// EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(cases)); +// +// Users can pass a variety of types for testing heterogeneous lookup with +// `std::make_tuple`: +// +// EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( +// std::make_tuple(v1, v2, ..., vN))); +// +// +// Ideally, the values passed should provide enough coverage of the `==` +// operator and the AbslHashValue implementations. +// For dynamically sized types, the empty state should usually be included in +// the values. +// +// The function accepts an optional comparator function, in case that `==` is +// not enough for the values provided. +// +// Usage: +// +// EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( +// std::make_tuple(v1, v2, ..., vN), MyCustomEq{})); +// +// It checks the following requirements: +// 1. The expansion for a value is deterministic. +// 2. For any two objects `a` and `b` in the sequence, if `a == b` evaluates +// to true, then their hash expansion must be equal. +// 3. If `a == b` evaluates to false their hash expansion must be unequal. +// 4. If `a == b` evaluates to false neither hash expansion can be a +// suffix of the other. +// 5. AbslHashValue overloads should not be called by the user. They are only +// meant to be called by the framework. Users should call H::combine() and +// H::combine_contiguous(). +// 6. No moved-from instance of the hash state is used in the implementation +// of AbslHashValue. +// +// The values do not have to have the same type. This can be useful for +// equivalent types that support heterogeneous lookup. +// +// A possible reason for breaking (2) is combining state in the hash expansion +// that was not used in `==`. +// For example: +// +// struct Bad2 { +// int a, b; +// template +// friend H AbslHashValue(H state, Bad2 x) { +// // Uses a and b. +// return H::combine(x.a, x.b); +// } +// friend bool operator==(Bad2 x, Bad2 y) { +// // Only uses a. +// return x.a == y.a; +// } +// }; +// +// As for (3), breaking this usually means that there is state being passed to +// the `==` operator that is not used in the hash expansion. +// For example: +// +// struct Bad3 { +// int a, b; +// template +// friend H AbslHashValue(H state, Bad3 x) { +// // Only uses a. +// return H::combine(x.a); +// } +// friend bool operator==(Bad3 x, Bad3 y) { +// // Uses a and b. +// return x.a == y.a && x.b == y.b; +// } +// }; +// +// Finally, a common way to break 4 is by combining dynamic ranges without +// combining the size of the range. +// For example: +// +// struct Bad4 { +// int *p, size; +// template +// friend H AbslHashValue(H state, Bad4 x) { +// return H::combine_range(x.p, x.p + x.size); +// } +// friend bool operator==(Bad4 x, Bad4 y) { +// return std::equal(x.p, x.p + x.size, y.p, y.p + y.size); +// } +// }; +// +// An easy solution to this is to combine the size after combining the range, +// like so: +// template +// friend H AbslHashValue(H state, Bad4 x) { +// return H::combine(H::combine_range(x.p, x.p + x.size), x.size); +// } +// +template +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(const Container& values); + +template +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(const Container& values, Eq equals); + +template +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(std::initializer_list values); + +template +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(std::initializer_list values, + Eq equals); + +namespace hash_internal { + +struct PrintVisitor { + size_t index; + template + std::string operator()(const T* value) const { + return absl::StrCat("#", index, "(", testing::PrintToString(*value), ")"); + } +}; + +template +struct EqVisitor { + Eq eq; + template + bool operator()(const T* t, const U* u) const { + return eq(*t, *u); + } +}; + +struct ExpandVisitor { + template + SpyHashState operator()(const T* value) const { + return SpyHashState::combine(SpyHashState(), *value); + } +}; + +template +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(const Container& values, Eq equals) { + using V = typename Container::value_type; + + struct Info { + const V& value; + size_t index; + std::string ToString() const { return absl::visit(PrintVisitor{index}, value); } + SpyHashState expand() const { return absl::visit(ExpandVisitor{}, value); } + }; + + using EqClass = std::vector; + std::vector classes; + + // Gather the values in equivalence classes. + size_t i = 0; + for (const auto& value : values) { + EqClass* c = nullptr; + for (auto& eqclass : classes) { + if (absl::visit(EqVisitor{equals}, value, eqclass[0].value)) { + c = &eqclass; + break; + } + } + if (c == nullptr) { + classes.emplace_back(); + c = &classes.back(); + } + c->push_back({value, i}); + ++i; + + // Verify potential errors captured by SpyHashState. + if (auto error = c->back().expand().error()) { + return testing::AssertionFailure() << *error; + } + } + + if (classes.size() < 2) { + return testing::AssertionFailure() + << "At least two equivalence classes are expected."; + } + + // We assume that equality is correctly implemented. + // Now we verify that AbslHashValue is also correctly implemented. + + for (const auto& c : classes) { + // All elements of the equivalence class must have the same hash expansion. + const SpyHashState expected = c[0].expand(); + for (const Info& v : c) { + if (v.expand() != v.expand()) { + return testing::AssertionFailure() + << "Hash expansion for " << v.ToString() + << " is non-deterministic."; + } + if (v.expand() != expected) { + return testing::AssertionFailure() + << "Values " << c[0].ToString() << " and " << v.ToString() + << " evaluate as equal but have an unequal hash expansion."; + } + } + + // Elements from other classes must have different hash expansion. + for (const auto& c2 : classes) { + if (&c == &c2) continue; + const SpyHashState c2_hash = c2[0].expand(); + switch (SpyHashState::Compare(expected, c2_hash)) { + case SpyHashState::CompareResult::kEqual: + return testing::AssertionFailure() + << "Values " << c[0].ToString() << " and " << c2[0].ToString() + << " evaluate as unequal but have an equal hash expansion."; + case SpyHashState::CompareResult::kBSuffixA: + return testing::AssertionFailure() + << "Hash expansion of " << c2[0].ToString() + << " is a suffix of the hash expansion of " << c[0].ToString() + << "."; + case SpyHashState::CompareResult::kASuffixB: + return testing::AssertionFailure() + << "Hash expansion of " << c[0].ToString() + << " is a suffix of the hash expansion of " << c2[0].ToString() + << "."; + case SpyHashState::CompareResult::kUnequal: + break; + } + } + } + return testing::AssertionSuccess(); +} + +template +struct TypeSet { + template ...>::value> + struct Insert { + using type = TypeSet; + }; + template + struct Insert { + using type = TypeSet; + }; + + template