389 lines · cpp
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-exception6//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 23namespace llvm {24 25// Helper for test code to print hash codes.26void 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 large31// objects.32struct LargeTestInteger { uint64_t arr[8]; };33 34struct NonPOD {35 uint64_t x, y;36 NonPOD(uint64_t x, uint64_t y) : x(x), y(y) {}37 friend hash_code hash_value(const NonPOD &obj) {38 return hash_combine(obj.x, obj.y);39 }40};41 42namespace hashing {43namespace detail {44template <> struct is_hashable_data<LargeTestInteger> : std::true_type {};45} // namespace detail46} // namespace hashing47 48} // namespace llvm49 50using namespace llvm;51 52namespace {53 54enum TestEnumeration {55 TE_Foo = 42,56 TE_Bar = 4357};58 59TEST(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 81TEST(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 and89 // 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 treated96 // 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 106TEST(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 117TEST(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 134TEST(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 151template <typename T, size_t N> T *begin(T (&arr)[N]) { return arr; }152template <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 is155// the same as its value.156struct HashableDummy { size_t value; };157hash_code hash_value(HashableDummy dummy) { return dummy.value; }158 159TEST(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 EXPECT_EQ(arr1_hash, hash_combine_range(arr1));170 171 const std::vector<int> vec(begin(arr1), end(arr1));172 EXPECT_EQ(arr1_hash, hash_combine_range(vec.begin(), vec.end()));173 EXPECT_EQ(arr1_hash, hash_combine_range(vec));174 175 const std::list<int> list(begin(arr1), end(arr1));176 EXPECT_EQ(arr1_hash, hash_combine_range(list.begin(), list.end()));177 EXPECT_EQ(arr1_hash, hash_combine_range(list));178 179 const std::deque<int> deque(begin(arr1), end(arr1));180 EXPECT_EQ(arr1_hash, hash_combine_range(deque.begin(), deque.end()));181 EXPECT_EQ(arr1_hash, hash_combine_range(deque));182 183 const int arr2[] = { 3, 2, 1 };184 hash_code arr2_hash = hash_combine_range(begin(arr2), end(arr2));185 EXPECT_NE(dummy_hash, arr2_hash);186 EXPECT_NE(arr1_hash, arr2_hash);187 188 const int arr3[] = { 1, 1, 2, 3 };189 hash_code arr3_hash = hash_combine_range(begin(arr3), end(arr3));190 EXPECT_NE(dummy_hash, arr3_hash);191 EXPECT_NE(arr1_hash, arr3_hash);192 193 const int arr4[] = { 1, 2, 3, 3 };194 hash_code arr4_hash = hash_combine_range(begin(arr4), end(arr4));195 EXPECT_NE(dummy_hash, arr4_hash);196 EXPECT_NE(arr1_hash, arr4_hash);197 198 const size_t arr5[] = { 1, 2, 3 };199 const HashableDummy d_arr5[] = { {1}, {2}, {3} };200 hash_code arr5_hash = hash_combine_range(begin(arr5), end(arr5));201 hash_code d_arr5_hash = hash_combine_range(begin(d_arr5), end(d_arr5));202 EXPECT_EQ(arr5_hash, d_arr5_hash);203}204 205TEST(HashingTest, HashCombineRangeLengthDiff) {206 // Test that as only the length varies, we compute different hash codes for207 // sequences.208 std::map<size_t, size_t> code_to_size;209 std::vector<char> all_one_c(256, '\xff');210 for (unsigned Idx = 1, Size = all_one_c.size(); Idx < Size; ++Idx) {211 hash_code code = hash_combine_range(&all_one_c[0], &all_one_c[0] + Idx);212 std::map<size_t, size_t>::iterator213 I = code_to_size.insert(std::make_pair(code, Idx)).first;214 EXPECT_EQ(Idx, I->second);215 }216 code_to_size.clear();217 std::vector<char> all_zero_c(256, '\0');218 for (unsigned Idx = 1, Size = all_zero_c.size(); Idx < Size; ++Idx) {219 hash_code code = hash_combine_range(&all_zero_c[0], &all_zero_c[0] + Idx);220 std::map<size_t, size_t>::iterator221 I = code_to_size.insert(std::make_pair(code, Idx)).first;222 EXPECT_EQ(Idx, I->second);223 }224 code_to_size.clear();225 std::vector<unsigned> all_one_int(512, -1);226 for (unsigned Idx = 1, Size = all_one_int.size(); Idx < Size; ++Idx) {227 hash_code code = hash_combine_range(&all_one_int[0], &all_one_int[0] + Idx);228 std::map<size_t, size_t>::iterator229 I = code_to_size.insert(std::make_pair(code, Idx)).first;230 EXPECT_EQ(Idx, I->second);231 }232 code_to_size.clear();233 std::vector<unsigned> all_zero_int(512, 0);234 for (unsigned Idx = 1, Size = all_zero_int.size(); Idx < Size; ++Idx) {235 hash_code code = hash_combine_range(&all_zero_int[0], &all_zero_int[0] + Idx);236 std::map<size_t, size_t>::iterator237 I = code_to_size.insert(std::make_pair(code, Idx)).first;238 EXPECT_EQ(Idx, I->second);239 }240}241 242TEST(HashingTest, HashCombineBasicTest) {243 // Hashing a sequence of homogenous types matches range hashing.244 const int i1 = 42, i2 = 43, i3 = 123, i4 = 999, i5 = 0, i6 = 79;245 const int arr1[] = { i1, i2, i3, i4, i5, i6 };246 EXPECT_EQ(hash_combine_range(arr1, arr1 + 1), hash_combine(i1));247 EXPECT_EQ(hash_combine_range(arr1, arr1 + 2), hash_combine(i1, i2));248 EXPECT_EQ(hash_combine_range(arr1, arr1 + 3), hash_combine(i1, i2, i3));249 EXPECT_EQ(hash_combine_range(arr1, arr1 + 4), hash_combine(i1, i2, i3, i4));250 EXPECT_EQ(hash_combine_range(arr1, arr1 + 5),251 hash_combine(i1, i2, i3, i4, i5));252 EXPECT_EQ(hash_combine_range(arr1, arr1 + 6),253 hash_combine(i1, i2, i3, i4, i5, i6));254 255 // Hashing a sequence of heterogeneous types which *happen* to all produce the256 // same data for hashing produces the same as a range-based hash of the257 // fundamental values.258 const size_t s1 = 1024, s2 = 8888, s3 = 9000000;259 const HashableDummy d1 = { 1024 }, d2 = { 8888 }, d3 = { 9000000 };260 const size_t arr2[] = { s1, s2, s3 };261 EXPECT_EQ(hash_combine_range(begin(arr2), end(arr2)),262 hash_combine(s1, s2, s3));263 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(s1, s2, d3));264 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(s1, d2, s3));265 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, s2, s3));266 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, d2, s3));267 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, d2, d3));268 269 // Permuting values causes hashes to change.270 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i1, i1, i2));271 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i1, i2, i1));272 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i1, i1));273 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i2, i1));274 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i2, i2));275 EXPECT_NE(hash_combine(i2, i1, i1), hash_combine(i1, i1, i2));276 EXPECT_NE(hash_combine(i1, i1, i2), hash_combine(i1, i2, i1));277 EXPECT_NE(hash_combine(i1, i2, i1), hash_combine(i2, i1, i1));278 279 // Changing type w/o changing value causes hashes to change.280 EXPECT_NE(hash_combine(i1, i2, i3), hash_combine((char)i1, i2, i3));281 EXPECT_NE(hash_combine(i1, i2, i3), hash_combine(i1, (char)i2, i3));282 EXPECT_NE(hash_combine(i1, i2, i3), hash_combine(i1, i2, (char)i3));283 284 // This is array of uint64, but it should have the exact same byte pattern as285 // an array of LargeTestIntegers.286 const uint64_t bigarr[] = {287 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,288 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,289 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL,290 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,291 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,292 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL,293 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,294 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,295 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL296 };297 // Hash a preposterously large integer, both aligned with the buffer and298 // misaligned.299 const LargeTestInteger li = { {300 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,301 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,302 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL303 } };304 // Rotate the storage from 'li'.305 const LargeTestInteger l2 = { {306 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL,307 0xfefefefededededeULL, 0xafafafafededededULL, 0xffffeeeeddddccccULL,308 0xaaaacbcbffffababULL, 0xaaaaaaaaababababULL309 } };310 const LargeTestInteger l3 = { {311 0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL,312 0xafafafafededededULL, 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL,313 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL314 } };315 EXPECT_EQ(hash_combine_range(begin(bigarr), end(bigarr)),316 hash_combine(li, li, li));317 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 9),318 hash_combine(bigarr[0], l2));319 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 10),320 hash_combine(bigarr[0], bigarr[1], l3));321 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 17),322 hash_combine(li, bigarr[0], l2));323 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 18),324 hash_combine(li, bigarr[0], bigarr[1], l3));325 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 18),326 hash_combine(bigarr[0], l2, bigarr[9], l3));327 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 20),328 hash_combine(bigarr[0], l2, bigarr[9], l3, bigarr[18], bigarr[19]));329}330 331TEST(HashingTest, HashCombineArgs18) {332 // This tests that we can pass in up to 18 args.333#define CHECK_SAME(...) \334 EXPECT_EQ(hash_combine(__VA_ARGS__), hash_combine(__VA_ARGS__))335 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18);336 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17);337 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16);338 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);339 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14);340 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13);341 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);342 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11);343 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);344 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9);345 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8);346 CHECK_SAME(1, 2, 3, 4, 5, 6, 7);347 CHECK_SAME(1, 2, 3, 4, 5, 6);348 CHECK_SAME(1, 2, 3, 4, 5);349 CHECK_SAME(1, 2, 3, 4);350 CHECK_SAME(1, 2, 3);351 CHECK_SAME(1, 2);352 CHECK_SAME(1);353#undef CHECK_SAME354}355 356struct StructWithHashBuilderSupport {357 char C;358 int I;359 template <typename HasherT, llvm::endianness Endianness>360 friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder,361 const StructWithHashBuilderSupport &Value) {362 HBuilder.add(Value.C, Value.I);363 }364};365 366TEST(HashingTest, HashWithHashBuilder) {367 StructWithHashBuilderSupport S{'c', 1};368 EXPECT_NE(static_cast<size_t>(llvm::hash_value(S)), static_cast<size_t>(0));369}370 371struct StructWithHashBuilderAndHashValueSupport {372 char C;373 int I;374 template <typename HasherT, llvm::endianness Endianness>375 friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder,376 const StructWithHashBuilderAndHashValueSupport &Value) {}377 friend hash_code378 hash_value(const StructWithHashBuilderAndHashValueSupport &Value) {379 return 0xbeef;380 }381};382 383TEST(HashingTest, HashBuilderAndHashValue) {384 StructWithHashBuilderAndHashValueSupport S{'c', 1};385 EXPECT_EQ(static_cast<size_t>(hash_value(S)), static_cast<size_t>(0xbeef));386}387 388} // namespace389