1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 // This file contains a few select absl::Hash tests that, due to their reliance
16 // on INSTANTIATE_TYPED_TEST_SUITE_P, require a large amount of memory to
17 // compile. Put new tests in hash_test.cc, not this file.
18
19 #include "absl/hash/hash.h"
20
21 #include <stddef.h>
22
23 #include <algorithm>
24 #include <deque>
25 #include <forward_list>
26 #include <initializer_list>
27 #include <list>
28 #include <map>
29 #include <set>
30 #include <string>
31 #include <type_traits>
32 #include <unordered_map>
33 #include <unordered_set>
34 #include <utility>
35 #include <vector>
36
37 #include "gtest/gtest.h"
38 #include "absl/container/btree_map.h"
39 #include "absl/container/btree_set.h"
40 #include "absl/container/flat_hash_map.h"
41 #include "absl/container/flat_hash_set.h"
42 #include "absl/container/node_hash_map.h"
43 #include "absl/container/node_hash_set.h"
44 #include "absl/hash/hash_testing.h"
45 #include "absl/hash/internal/hash_test.h"
46
47 namespace {
48
49 using ::absl::hash_test_internal::is_hashable;
50 using ::absl::hash_test_internal::TypeErasedContainer;
51
52 // Dummy type with unordered equality and hashing semantics. This preserves
53 // input order internally, and is used below to ensure we get test coverage
54 // for equal sequences with different iteraton orders.
55 template <typename T>
56 class UnorderedSequence {
57 public:
58 UnorderedSequence() = default;
59 template <typename TT>
UnorderedSequence(std::initializer_list<TT> l)60 UnorderedSequence(std::initializer_list<TT> l)
61 : values_(l.begin(), l.end()) {}
62 template <typename ForwardIterator,
63 typename std::enable_if<!std::is_integral<ForwardIterator>::value,
64 bool>::type = true>
UnorderedSequence(ForwardIterator begin,ForwardIterator end)65 UnorderedSequence(ForwardIterator begin, ForwardIterator end)
66 : values_(begin, end) {}
67 // one-argument constructor of value type T, to appease older toolchains that
68 // get confused by one-element initializer lists in some contexts
UnorderedSequence(const T & v)69 explicit UnorderedSequence(const T& v) : values_(&v, &v + 1) {}
70
71 using value_type = T;
72
size() const73 size_t size() const { return values_.size(); }
begin() const74 typename std::vector<T>::const_iterator begin() const {
75 return values_.begin();
76 }
end() const77 typename std::vector<T>::const_iterator end() const { return values_.end(); }
78
operator ==(const UnorderedSequence & lhs,const UnorderedSequence & rhs)79 friend bool operator==(const UnorderedSequence& lhs,
80 const UnorderedSequence& rhs) {
81 return lhs.size() == rhs.size() &&
82 std::is_permutation(lhs.begin(), lhs.end(), rhs.begin());
83 }
operator !=(const UnorderedSequence & lhs,const UnorderedSequence & rhs)84 friend bool operator!=(const UnorderedSequence& lhs,
85 const UnorderedSequence& rhs) {
86 return !(lhs == rhs);
87 }
88 template <typename H>
AbslHashValue(H h,const UnorderedSequence & u)89 friend H AbslHashValue(H h, const UnorderedSequence& u) {
90 return H::combine(H::combine_unordered(std::move(h), u.begin(), u.end()),
91 u.size());
92 }
93
94 private:
95 std::vector<T> values_;
96 };
97
98 template <typename T>
99 class HashValueSequenceTest : public testing::Test {};
100 TYPED_TEST_SUITE_P(HashValueSequenceTest);
101
TYPED_TEST_P(HashValueSequenceTest,BasicUsage)102 TYPED_TEST_P(HashValueSequenceTest, BasicUsage) {
103 EXPECT_TRUE((is_hashable<TypeParam>::value));
104
105 using IntType = typename TypeParam::value_type;
106 auto a = static_cast<IntType>(0);
107 auto b = static_cast<IntType>(23);
108 auto c = static_cast<IntType>(42);
109
110 std::vector<TypeParam> exemplars = {
111 TypeParam(), TypeParam(), TypeParam{a, b, c},
112 TypeParam{a, c, b}, TypeParam{c, a, b}, TypeParam{a},
113 TypeParam{a, a}, TypeParam{a, a, a}, TypeParam{a, a, b},
114 TypeParam{a, b, a}, TypeParam{b, a, a}, TypeParam{a, b},
115 TypeParam{b, c}};
116 EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars));
117 }
118
119 REGISTER_TYPED_TEST_SUITE_P(HashValueSequenceTest, BasicUsage);
120 using IntSequenceTypes = testing::Types<
121 std::deque<int>, std::forward_list<int>, std::list<int>, std::vector<int>,
122 std::vector<bool>, TypeErasedContainer<std::vector<int>>, std::set<int>,
123 std::multiset<int>, UnorderedSequence<int>,
124 TypeErasedContainer<UnorderedSequence<int>>, std::unordered_set<int>,
125 std::unordered_multiset<int>, absl::flat_hash_set<int>,
126 absl::node_hash_set<int>, absl::btree_set<int>>;
127 INSTANTIATE_TYPED_TEST_SUITE_P(My, HashValueSequenceTest, IntSequenceTypes);
128
129 template <typename T>
130 class HashValueNestedSequenceTest : public testing::Test {};
131 TYPED_TEST_SUITE_P(HashValueNestedSequenceTest);
132
TYPED_TEST_P(HashValueNestedSequenceTest,BasicUsage)133 TYPED_TEST_P(HashValueNestedSequenceTest, BasicUsage) {
134 using T = TypeParam;
135 using V = typename T::value_type;
136 std::vector<T> exemplars = {
137 // empty case
138 T{},
139 // sets of empty sets
140 T{V{}}, T{V{}, V{}}, T{V{}, V{}, V{}},
141 // multisets of different values
142 T{V{1}}, T{V{1, 1}, V{1, 1}}, T{V{1, 1, 1}, V{1, 1, 1}, V{1, 1, 1}},
143 // various orderings of same nested sets
144 T{V{}, V{1, 2}}, T{V{}, V{2, 1}}, T{V{1, 2}, V{}}, T{V{2, 1}, V{}},
145 // various orderings of various nested sets, case 2
146 T{V{1, 2}, V{3, 4}}, T{V{1, 2}, V{4, 3}}, T{V{1, 3}, V{2, 4}},
147 T{V{1, 3}, V{4, 2}}, T{V{1, 4}, V{2, 3}}, T{V{1, 4}, V{3, 2}},
148 T{V{2, 3}, V{1, 4}}, T{V{2, 3}, V{4, 1}}, T{V{2, 4}, V{1, 3}},
149 T{V{2, 4}, V{3, 1}}, T{V{3, 4}, V{1, 2}}, T{V{3, 4}, V{2, 1}}};
150 EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars));
151 }
152
153 REGISTER_TYPED_TEST_SUITE_P(HashValueNestedSequenceTest, BasicUsage);
154 template <typename T>
155 using TypeErasedSet = TypeErasedContainer<UnorderedSequence<T>>;
156
157 using NestedIntSequenceTypes = testing::Types<
158 std::vector<std::vector<int>>, std::vector<UnorderedSequence<int>>,
159 std::vector<TypeErasedSet<int>>, UnorderedSequence<std::vector<int>>,
160 UnorderedSequence<UnorderedSequence<int>>,
161 UnorderedSequence<TypeErasedSet<int>>, TypeErasedSet<std::vector<int>>,
162 TypeErasedSet<UnorderedSequence<int>>, TypeErasedSet<TypeErasedSet<int>>>;
163 INSTANTIATE_TYPED_TEST_SUITE_P(My, HashValueNestedSequenceTest,
164 NestedIntSequenceTypes);
165
166 template <typename T>
167 class HashValueAssociativeMapTest : public testing::Test {};
168 TYPED_TEST_SUITE_P(HashValueAssociativeMapTest);
169
TYPED_TEST_P(HashValueAssociativeMapTest,BasicUsage)170 TYPED_TEST_P(HashValueAssociativeMapTest, BasicUsage) {
171 using M = TypeParam;
172 using V = typename M::value_type;
173 std::vector<M> exemplars{M{},
174 M{V{0, "foo"}},
175 M{V{1, "foo"}},
176 M{V{0, "bar"}},
177 M{V{1, "bar"}},
178 M{V{0, "foo"}, V{42, "bar"}},
179 M{V{42, "bar"}, V{0, "foo"}},
180 M{V{1, "foo"}, V{42, "bar"}},
181 M{V{1, "foo"}, V{43, "bar"}},
182 M{V{1, "foo"}, V{43, "baz"}}};
183 EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars));
184 }
185
186 REGISTER_TYPED_TEST_SUITE_P(HashValueAssociativeMapTest, BasicUsage);
187 using AssociativeMapTypes = testing::Types<
188 std::map<int, std::string>, std::unordered_map<int, std::string>,
189 absl::flat_hash_map<int, std::string>,
190 absl::node_hash_map<int, std::string>, absl::btree_map<int, std::string>,
191 UnorderedSequence<std::pair<const int, std::string>>>;
192 INSTANTIATE_TYPED_TEST_SUITE_P(My, HashValueAssociativeMapTest,
193 AssociativeMapTypes);
194
195 template <typename T>
196 class HashValueAssociativeMultimapTest : public testing::Test {};
197 TYPED_TEST_SUITE_P(HashValueAssociativeMultimapTest);
198
TYPED_TEST_P(HashValueAssociativeMultimapTest,BasicUsage)199 TYPED_TEST_P(HashValueAssociativeMultimapTest, BasicUsage) {
200 using MM = TypeParam;
201 using V = typename MM::value_type;
202 std::vector<MM> exemplars{MM{},
203 MM{V{0, "foo"}},
204 MM{V{1, "foo"}},
205 MM{V{0, "bar"}},
206 MM{V{1, "bar"}},
207 MM{V{0, "foo"}, V{0, "bar"}},
208 MM{V{0, "bar"}, V{0, "foo"}},
209 MM{V{0, "foo"}, V{42, "bar"}},
210 MM{V{1, "foo"}, V{42, "bar"}},
211 MM{V{1, "foo"}, V{1, "foo"}, V{43, "bar"}},
212 MM{V{1, "foo"}, V{43, "bar"}, V{1, "foo"}},
213 MM{V{1, "foo"}, V{43, "baz"}}};
214 EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars));
215 }
216
217 REGISTER_TYPED_TEST_SUITE_P(HashValueAssociativeMultimapTest, BasicUsage);
218 using AssociativeMultimapTypes =
219 testing::Types<std::multimap<int, std::string>,
220 std::unordered_multimap<int, std::string>>;
221 INSTANTIATE_TYPED_TEST_SUITE_P(My, HashValueAssociativeMultimapTest,
222 AssociativeMultimapTypes);
223
224 } // namespace
225