1 //===- llvm/unittest/ADT/HashingTest.cpp ----------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Hashing.h unit tests.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/ADT/Hashing.h"
14 #include "llvm/Support/DataTypes.h"
15 #include "llvm/Support/HashBuilder.h"
16 #include "gtest/gtest.h"
17 #include <deque>
18 #include <list>
19 #include <map>
20 #include <optional>
21 #include <vector>
22
23 namespace llvm {
24
25 // Helper for test code to print hash codes.
PrintTo(const hash_code & code,std::ostream * os)26 void PrintTo(const hash_code &code, std::ostream *os) {
27 *os << static_cast<size_t>(code);
28 }
29
30 // Fake an object that is recognized as hashable data to test super large
31 // objects.
32 struct LargeTestInteger { uint64_t arr[8]; };
33
34 struct NonPOD {
35 uint64_t x, y;
NonPODllvm::NonPOD36 NonPOD(uint64_t x, uint64_t y) : x(x), y(y) {}
hash_value(const NonPOD & obj)37 friend hash_code hash_value(const NonPOD &obj) {
38 return hash_combine(obj.x, obj.y);
39 }
40 };
41
42 namespace hashing {
43 namespace detail {
44 template <> struct is_hashable_data<LargeTestInteger> : std::true_type {};
45 } // namespace detail
46 } // namespace hashing
47
48 } // namespace llvm
49
50 using namespace llvm;
51
52 namespace {
53
54 enum TestEnumeration {
55 TE_Foo = 42,
56 TE_Bar = 43
57 };
58
TEST(HashingTest,HashValueBasicTest)59 TEST(HashingTest, HashValueBasicTest) {
60 int x = 42, y = 43, c = 'x';
61 void *p = nullptr;
62 uint64_t i = 71;
63 const unsigned ci = 71;
64 volatile int vi = 71;
65 const volatile int cvi = 71;
66 uintptr_t addr = reinterpret_cast<uintptr_t>(&y);
67 EXPECT_EQ(hash_value(42), hash_value(x));
68 EXPECT_EQ(hash_value(42), hash_value(TE_Foo));
69 EXPECT_NE(hash_value(42), hash_value(y));
70 EXPECT_NE(hash_value(42), hash_value(TE_Bar));
71 EXPECT_NE(hash_value(42), hash_value(p));
72 EXPECT_EQ(hash_value(71), hash_value(i));
73 EXPECT_EQ(hash_value(71), hash_value(ci));
74 EXPECT_EQ(hash_value(71), hash_value(vi));
75 EXPECT_EQ(hash_value(71), hash_value(cvi));
76 EXPECT_EQ(hash_value(c), hash_value('x'));
77 EXPECT_EQ(hash_value('4'), hash_value('0' + 4));
78 EXPECT_EQ(hash_value(addr), hash_value(&y));
79 }
80
TEST(HashingTest,HashValueStdPair)81 TEST(HashingTest, HashValueStdPair) {
82 EXPECT_EQ(hash_combine(42, 43), hash_value(std::make_pair(42, 43)));
83 EXPECT_NE(hash_combine(43, 42), hash_value(std::make_pair(42, 43)));
84 EXPECT_NE(hash_combine(42, 43), hash_value(std::make_pair(42ull, 43ull)));
85 EXPECT_NE(hash_combine(42, 43), hash_value(std::make_pair(42, 43ull)));
86 EXPECT_NE(hash_combine(42, 43), hash_value(std::make_pair(42ull, 43)));
87
88 // Note that pairs are implicitly flattened to a direct sequence of data and
89 // hashed efficiently as a consequence.
90 EXPECT_EQ(hash_combine(42, 43, 44),
91 hash_value(std::make_pair(42, std::make_pair(43, 44))));
92 EXPECT_EQ(hash_value(std::make_pair(42, std::make_pair(43, 44))),
93 hash_value(std::make_pair(std::make_pair(42, 43), 44)));
94
95 // Ensure that pairs which have padding bytes *inside* them don't get treated
96 // this way.
97 EXPECT_EQ(hash_combine('0', hash_combine(1ull, '2')),
98 hash_value(std::make_pair('0', std::make_pair(1ull, '2'))));
99
100 // Ensure that non-POD pairs don't explode the traits used.
101 NonPOD obj1(1, 2), obj2(3, 4), obj3(5, 6);
102 EXPECT_EQ(hash_combine(obj1, hash_combine(obj2, obj3)),
103 hash_value(std::make_pair(obj1, std::make_pair(obj2, obj3))));
104 }
105
TEST(HashingTest,HashValueStdTuple)106 TEST(HashingTest, HashValueStdTuple) {
107 EXPECT_EQ(hash_combine(), hash_value(std::make_tuple()));
108 EXPECT_EQ(hash_combine(42), hash_value(std::make_tuple(42)));
109 EXPECT_EQ(hash_combine(42, 'c'), hash_value(std::make_tuple(42, 'c')));
110
111 EXPECT_NE(hash_combine(43, 42), hash_value(std::make_tuple(42, 43)));
112 EXPECT_NE(hash_combine(42, 43), hash_value(std::make_tuple(42ull, 43ull)));
113 EXPECT_NE(hash_combine(42, 43), hash_value(std::make_tuple(42, 43ull)));
114 EXPECT_NE(hash_combine(42, 43), hash_value(std::make_tuple(42ull, 43)));
115 }
116
TEST(HashingTest,HashValueStdString)117 TEST(HashingTest, HashValueStdString) {
118 std::string s = "Hello World!";
119 EXPECT_EQ(hash_combine_range(s.c_str(), s.c_str() + s.size()), hash_value(s));
120 EXPECT_EQ(hash_combine_range(s.c_str(), s.c_str() + s.size() - 1),
121 hash_value(s.substr(0, s.size() - 1)));
122 EXPECT_EQ(hash_combine_range(s.c_str() + 1, s.c_str() + s.size() - 1),
123 hash_value(s.substr(1, s.size() - 2)));
124
125 std::wstring ws = L"Hello Wide World!";
126 EXPECT_EQ(hash_combine_range(ws.c_str(), ws.c_str() + ws.size()),
127 hash_value(ws));
128 EXPECT_EQ(hash_combine_range(ws.c_str(), ws.c_str() + ws.size() - 1),
129 hash_value(ws.substr(0, ws.size() - 1)));
130 EXPECT_EQ(hash_combine_range(ws.c_str() + 1, ws.c_str() + ws.size() - 1),
131 hash_value(ws.substr(1, ws.size() - 2)));
132 }
133
TEST(HashingTest,HashValueStdOptional)134 TEST(HashingTest, HashValueStdOptional) {
135 // Check that std::nullopt, false, and true all hash differently.
136 std::optional<bool> B, B0 = false, B1 = true;
137 EXPECT_NE(hash_value(B0), hash_value(B));
138 EXPECT_NE(hash_value(B1), hash_value(B));
139 EXPECT_NE(hash_value(B1), hash_value(B0));
140
141 // Check that std::nullopt, 0, and 1 all hash differently.
142 std::optional<int> I, I0 = 0, I1 = 1;
143 EXPECT_NE(hash_value(I0), hash_value(I));
144 EXPECT_NE(hash_value(I1), hash_value(I));
145 EXPECT_NE(hash_value(I1), hash_value(I0));
146
147 // Check std::nullopt hash the same way regardless of type.
148 EXPECT_EQ(hash_value(B), hash_value(I));
149 }
150
begin(T (& arr)[N])151 template <typename T, size_t N> T *begin(T (&arr)[N]) { return arr; }
end(T (& arr)[N])152 template <typename T, size_t N> T *end(T (&arr)[N]) { return arr + N; }
153
154 // Provide a dummy, hashable type designed for easy verification: its hash is
155 // the same as its value.
156 struct HashableDummy { size_t value; };
hash_value(HashableDummy dummy)157 hash_code hash_value(HashableDummy dummy) { return dummy.value; }
158
TEST(HashingTest,HashCombineRangeBasicTest)159 TEST(HashingTest, HashCombineRangeBasicTest) {
160 // Leave this uninitialized in the hope that valgrind will catch bad reads.
161 int dummy;
162 hash_code dummy_hash = hash_combine_range(&dummy, &dummy);
163 EXPECT_NE(hash_code(0), dummy_hash);
164
165 const int arr1[] = { 1, 2, 3 };
166 hash_code arr1_hash = hash_combine_range(begin(arr1), end(arr1));
167 EXPECT_NE(dummy_hash, arr1_hash);
168 EXPECT_EQ(arr1_hash, hash_combine_range(begin(arr1), end(arr1)));
169
170 const std::vector<int> vec(begin(arr1), end(arr1));
171 EXPECT_EQ(arr1_hash, hash_combine_range(vec.begin(), vec.end()));
172
173 const std::list<int> list(begin(arr1), end(arr1));
174 EXPECT_EQ(arr1_hash, hash_combine_range(list.begin(), list.end()));
175
176 const std::deque<int> deque(begin(arr1), end(arr1));
177 EXPECT_EQ(arr1_hash, hash_combine_range(deque.begin(), deque.end()));
178
179 const int arr2[] = { 3, 2, 1 };
180 hash_code arr2_hash = hash_combine_range(begin(arr2), end(arr2));
181 EXPECT_NE(dummy_hash, arr2_hash);
182 EXPECT_NE(arr1_hash, arr2_hash);
183
184 const int arr3[] = { 1, 1, 2, 3 };
185 hash_code arr3_hash = hash_combine_range(begin(arr3), end(arr3));
186 EXPECT_NE(dummy_hash, arr3_hash);
187 EXPECT_NE(arr1_hash, arr3_hash);
188
189 const int arr4[] = { 1, 2, 3, 3 };
190 hash_code arr4_hash = hash_combine_range(begin(arr4), end(arr4));
191 EXPECT_NE(dummy_hash, arr4_hash);
192 EXPECT_NE(arr1_hash, arr4_hash);
193
194 const size_t arr5[] = { 1, 2, 3 };
195 const HashableDummy d_arr5[] = { {1}, {2}, {3} };
196 hash_code arr5_hash = hash_combine_range(begin(arr5), end(arr5));
197 hash_code d_arr5_hash = hash_combine_range(begin(d_arr5), end(d_arr5));
198 EXPECT_EQ(arr5_hash, d_arr5_hash);
199 }
200
TEST(HashingTest,HashCombineRangeLengthDiff)201 TEST(HashingTest, HashCombineRangeLengthDiff) {
202 // Test that as only the length varies, we compute different hash codes for
203 // sequences.
204 std::map<size_t, size_t> code_to_size;
205 std::vector<char> all_one_c(256, '\xff');
206 for (unsigned Idx = 1, Size = all_one_c.size(); Idx < Size; ++Idx) {
207 hash_code code = hash_combine_range(&all_one_c[0], &all_one_c[0] + Idx);
208 std::map<size_t, size_t>::iterator
209 I = code_to_size.insert(std::make_pair(code, Idx)).first;
210 EXPECT_EQ(Idx, I->second);
211 }
212 code_to_size.clear();
213 std::vector<char> all_zero_c(256, '\0');
214 for (unsigned Idx = 1, Size = all_zero_c.size(); Idx < Size; ++Idx) {
215 hash_code code = hash_combine_range(&all_zero_c[0], &all_zero_c[0] + Idx);
216 std::map<size_t, size_t>::iterator
217 I = code_to_size.insert(std::make_pair(code, Idx)).first;
218 EXPECT_EQ(Idx, I->second);
219 }
220 code_to_size.clear();
221 std::vector<unsigned> all_one_int(512, -1);
222 for (unsigned Idx = 1, Size = all_one_int.size(); Idx < Size; ++Idx) {
223 hash_code code = hash_combine_range(&all_one_int[0], &all_one_int[0] + Idx);
224 std::map<size_t, size_t>::iterator
225 I = code_to_size.insert(std::make_pair(code, Idx)).first;
226 EXPECT_EQ(Idx, I->second);
227 }
228 code_to_size.clear();
229 std::vector<unsigned> all_zero_int(512, 0);
230 for (unsigned Idx = 1, Size = all_zero_int.size(); Idx < Size; ++Idx) {
231 hash_code code = hash_combine_range(&all_zero_int[0], &all_zero_int[0] + Idx);
232 std::map<size_t, size_t>::iterator
233 I = code_to_size.insert(std::make_pair(code, Idx)).first;
234 EXPECT_EQ(Idx, I->second);
235 }
236 }
237
TEST(HashingTest,HashCombineBasicTest)238 TEST(HashingTest, HashCombineBasicTest) {
239 // Hashing a sequence of homogenous types matches range hashing.
240 const int i1 = 42, i2 = 43, i3 = 123, i4 = 999, i5 = 0, i6 = 79;
241 const int arr1[] = { i1, i2, i3, i4, i5, i6 };
242 EXPECT_EQ(hash_combine_range(arr1, arr1 + 1), hash_combine(i1));
243 EXPECT_EQ(hash_combine_range(arr1, arr1 + 2), hash_combine(i1, i2));
244 EXPECT_EQ(hash_combine_range(arr1, arr1 + 3), hash_combine(i1, i2, i3));
245 EXPECT_EQ(hash_combine_range(arr1, arr1 + 4), hash_combine(i1, i2, i3, i4));
246 EXPECT_EQ(hash_combine_range(arr1, arr1 + 5),
247 hash_combine(i1, i2, i3, i4, i5));
248 EXPECT_EQ(hash_combine_range(arr1, arr1 + 6),
249 hash_combine(i1, i2, i3, i4, i5, i6));
250
251 // Hashing a sequence of heterogeneous types which *happen* to all produce the
252 // same data for hashing produces the same as a range-based hash of the
253 // fundamental values.
254 const size_t s1 = 1024, s2 = 8888, s3 = 9000000;
255 const HashableDummy d1 = { 1024 }, d2 = { 8888 }, d3 = { 9000000 };
256 const size_t arr2[] = { s1, s2, s3 };
257 EXPECT_EQ(hash_combine_range(begin(arr2), end(arr2)),
258 hash_combine(s1, s2, s3));
259 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(s1, s2, d3));
260 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(s1, d2, s3));
261 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, s2, s3));
262 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, d2, s3));
263 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, d2, d3));
264
265 // Permuting values causes hashes to change.
266 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i1, i1, i2));
267 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i1, i2, i1));
268 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i1, i1));
269 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i2, i1));
270 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i2, i2));
271 EXPECT_NE(hash_combine(i2, i1, i1), hash_combine(i1, i1, i2));
272 EXPECT_NE(hash_combine(i1, i1, i2), hash_combine(i1, i2, i1));
273 EXPECT_NE(hash_combine(i1, i2, i1), hash_combine(i2, i1, i1));
274
275 // Changing type w/o changing value causes hashes to change.
276 EXPECT_NE(hash_combine(i1, i2, i3), hash_combine((char)i1, i2, i3));
277 EXPECT_NE(hash_combine(i1, i2, i3), hash_combine(i1, (char)i2, i3));
278 EXPECT_NE(hash_combine(i1, i2, i3), hash_combine(i1, i2, (char)i3));
279
280 // This is array of uint64, but it should have the exact same byte pattern as
281 // an array of LargeTestIntegers.
282 const uint64_t bigarr[] = {
283 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,
284 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,
285 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL,
286 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,
287 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,
288 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL,
289 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,
290 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,
291 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL
292 };
293 // Hash a preposterously large integer, both aligned with the buffer and
294 // misaligned.
295 const LargeTestInteger li = { {
296 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,
297 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,
298 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL
299 } };
300 // Rotate the storage from 'li'.
301 const LargeTestInteger l2 = { {
302 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL,
303 0xfefefefededededeULL, 0xafafafafededededULL, 0xffffeeeeddddccccULL,
304 0xaaaacbcbffffababULL, 0xaaaaaaaaababababULL
305 } };
306 const LargeTestInteger l3 = { {
307 0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL,
308 0xafafafafededededULL, 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL,
309 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL
310 } };
311 EXPECT_EQ(hash_combine_range(begin(bigarr), end(bigarr)),
312 hash_combine(li, li, li));
313 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 9),
314 hash_combine(bigarr[0], l2));
315 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 10),
316 hash_combine(bigarr[0], bigarr[1], l3));
317 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 17),
318 hash_combine(li, bigarr[0], l2));
319 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 18),
320 hash_combine(li, bigarr[0], bigarr[1], l3));
321 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 18),
322 hash_combine(bigarr[0], l2, bigarr[9], l3));
323 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 20),
324 hash_combine(bigarr[0], l2, bigarr[9], l3, bigarr[18], bigarr[19]));
325 }
326
TEST(HashingTest,HashCombineArgs18)327 TEST(HashingTest, HashCombineArgs18) {
328 // This tests that we can pass in up to 18 args.
329 #define CHECK_SAME(...) \
330 EXPECT_EQ(hash_combine(__VA_ARGS__), hash_combine(__VA_ARGS__))
331 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18);
332 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17);
333 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16);
334 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
335 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14);
336 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13);
337 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);
338 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11);
339 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
340 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9);
341 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8);
342 CHECK_SAME(1, 2, 3, 4, 5, 6, 7);
343 CHECK_SAME(1, 2, 3, 4, 5, 6);
344 CHECK_SAME(1, 2, 3, 4, 5);
345 CHECK_SAME(1, 2, 3, 4);
346 CHECK_SAME(1, 2, 3);
347 CHECK_SAME(1, 2);
348 CHECK_SAME(1);
349 #undef CHECK_SAME
350 }
351
352 struct StructWithHashBuilderSupport {
353 char C;
354 int I;
355 template <typename HasherT, llvm::endianness Endianness>
addHash(llvm::HashBuilder<HasherT,Endianness> & HBuilder,const StructWithHashBuilderSupport & Value)356 friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder,
357 const StructWithHashBuilderSupport &Value) {
358 HBuilder.add(Value.C, Value.I);
359 }
360 };
361
TEST(HashingTest,HashWithHashBuilder)362 TEST(HashingTest, HashWithHashBuilder) {
363 StructWithHashBuilderSupport S{'c', 1};
364 EXPECT_NE(static_cast<size_t>(llvm::hash_value(S)), static_cast<size_t>(0));
365 }
366
367 struct StructWithHashBuilderAndHashValueSupport {
368 char C;
369 int I;
370 template <typename HasherT, llvm::endianness Endianness>
addHash(llvm::HashBuilder<HasherT,Endianness> & HBuilder,const StructWithHashBuilderAndHashValueSupport & Value)371 friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder,
372 const StructWithHashBuilderAndHashValueSupport &Value) {}
373 friend hash_code
hash_value(const StructWithHashBuilderAndHashValueSupport & Value)374 hash_value(const StructWithHashBuilderAndHashValueSupport &Value) {
375 return 0xbeef;
376 }
377 };
378
TEST(HashingTest,HashBuilderAndHashValue)379 TEST(HashingTest, HashBuilderAndHashValue) {
380 StructWithHashBuilderAndHashValueSupport S{'c', 1};
381 EXPECT_EQ(static_cast<size_t>(hash_value(S)), static_cast<size_t>(0xbeef));
382 }
383
384 } // namespace
385