diff options
Diffstat (limited to 'absl/hash/hash_testing.h')
| -rw-r--r-- | absl/hash/hash_testing.h | 372 |
1 files changed, 372 insertions, 0 deletions
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 <initializer_list> +#include <tuple> +#include <type_traits> +#include <vector> + +#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<MyType> 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 <typename H> +// 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 <typename H> +// 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 <typename H> +// 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 <typename H> +// friend H AbslHashValue(H state, Bad4 x) { +// return H::combine(H::combine_range(x.p, x.p + x.size), x.size); +// } +// +template <int&... ExplicitBarrier, typename Container> +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(const Container& values); + +template <int&... ExplicitBarrier, typename Container, typename Eq> +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(const Container& values, Eq equals); + +template <int&..., typename T> +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(std::initializer_list<T> values); + +template <int&..., typename T, typename Eq> +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(std::initializer_list<T> values, + Eq equals); + +namespace hash_internal { + +struct PrintVisitor { + size_t index; + template <typename T> + std::string operator()(const T* value) const { + return absl::StrCat("#", index, "(", testing::PrintToString(*value), ")"); + } +}; + +template <typename Eq> +struct EqVisitor { + Eq eq; + template <typename T, typename U> + bool operator()(const T* t, const U* u) const { + return eq(*t, *u); + } +}; + +struct ExpandVisitor { + template <typename T> + SpyHashState operator()(const T* value) const { + return SpyHashState::combine(SpyHashState(), *value); + } +}; + +template <typename Container, typename Eq> +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<Info>; + std::vector<EqClass> 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<Eq>{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 <typename... T> +struct TypeSet { + template <typename U, bool = disjunction<std::is_same<T, U>...>::value> + struct Insert { + using type = TypeSet<U, T...>; + }; + template <typename U> + struct Insert<U, true> { + using type = TypeSet; + }; + + template <template <typename...> class C> + using apply = C<T...>; +}; + +template <typename... T> +struct MakeTypeSet : TypeSet<>{}; +template <typename T, typename... Ts> +struct MakeTypeSet<T, Ts...> : MakeTypeSet<Ts...>::template Insert<T>::type {}; + +template <typename... T> +using VariantForTypes = typename MakeTypeSet< + const typename std::decay<T>::type*...>::template apply<absl::variant>; + +template <typename Container> +struct ContainerAsVector { + using V = absl::variant<const typename Container::value_type*>; + using Out = std::vector<V>; + + static Out Do(const Container& values) { + Out out; + for (const auto& v : values) out.push_back(&v); + return out; + } +}; + +template <typename... T> +struct ContainerAsVector<std::tuple<T...>> { + using V = VariantForTypes<T...>; + using Out = std::vector<V>; + + template <size_t... I> + static Out DoImpl(const std::tuple<T...>& tuple, absl::index_sequence<I...>) { + return Out{&std::get<I>(tuple)...}; + } + + static Out Do(const std::tuple<T...>& values) { + return DoImpl(values, absl::index_sequence_for<T...>()); + } +}; + +template <> +struct ContainerAsVector<std::tuple<>> { + static std::vector<VariantForTypes<int>> Do(std::tuple<>) { return {}; } +}; + +struct DefaultEquals { + template <typename T, typename U> + bool operator()(const T& t, const U& u) const { + return t == u; + } +}; + +} // namespace hash_internal + +template <int&..., typename Container> +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(const Container& values) { + return hash_internal::VerifyTypeImplementsAbslHashCorrectly( + hash_internal::ContainerAsVector<Container>::Do(values), + hash_internal::DefaultEquals{}); +} + +template <int&..., typename Container, typename Eq> +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(const Container& values, Eq equals) { + return hash_internal::VerifyTypeImplementsAbslHashCorrectly( + hash_internal::ContainerAsVector<Container>::Do(values), + equals); +} + +template <int&..., typename T> +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(std::initializer_list<T> values) { + return hash_internal::VerifyTypeImplementsAbslHashCorrectly( + hash_internal::ContainerAsVector<std::initializer_list<T>>::Do(values), + hash_internal::DefaultEquals{}); +} + +template <int&..., typename T, typename Eq> +ABSL_MUST_USE_RESULT testing::AssertionResult +VerifyTypeImplementsAbslHashCorrectly(std::initializer_list<T> values, + Eq equals) { + return hash_internal::VerifyTypeImplementsAbslHashCorrectly( + hash_internal::ContainerAsVector<std::initializer_list<T>>::Do(values), + equals); +} + +} // namespace absl + +#endif // ABSL_HASH_HASH_TESTING_H_ |