llvm/unittests/ADT/HashingTest.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-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.
  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;
  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
  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
  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
  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
 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
 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
 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
 151 template <typename T, size_t N> T *begin(T (&arr)[N]) { return arr; }
 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; };
 157 hash_code hash_value(HashableDummy dummy) { return dummy.value; }
 158
 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
 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
 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
 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>
 356   friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder,
 357                       const StructWithHashBuilderSupport &Value) {
 358     HBuilder.add(Value.C, Value.I);
 359   }
 360 };
 361
 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>
 371   friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder,
 372                       const StructWithHashBuilderAndHashValueSupport &Value) {}
 373   friend hash_code
 374   hash_value(const StructWithHashBuilderAndHashValueSupport &Value) {
 375     return 0xbeef;
 376   }
 377 };
 378
 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