llvm/unittests/Support/HashBuilderTest.cpp

   1 //===- llvm/unittest/Support/HashBuilderTest.cpp - HashBuilder unit tests -===//
   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 #include "llvm/Support/HashBuilder.h"
  10 #include "llvm/ADT/ArrayRef.h"
  11 #include "llvm/Support/MD5.h"
  12 #include "llvm/Support/SHA1.h"
  13 #include "llvm/Support/SHA256.h"
  14 #include "gtest/gtest.h"
  15
  16 #include <list>
  17 #include <string>
  18 #include <type_traits>
  19 #include <utility>
  20 #include <vector>
  21
  22 // gtest utilities and macros rely on using a single type. So wrap both the
  23 // hasher type and endianness.
  24 template <typename _HasherT, llvm::endianness _Endianness>
  25 struct HasherTAndEndianness {
  26   using HasherT = _HasherT;
  27   static constexpr llvm::endianness Endianness = _Endianness;
  28 };
  29 using HasherTAndEndiannessToTest = ::testing::Types<
  30     HasherTAndEndianness<llvm::MD5, llvm::endianness::big>,
  31     HasherTAndEndianness<llvm::MD5, llvm::endianness::little>,
  32     HasherTAndEndianness<llvm::MD5, llvm::endianness::native>,
  33     HasherTAndEndianness<llvm::SHA1, llvm::endianness::big>,
  34     HasherTAndEndianness<llvm::SHA1, llvm::endianness::little>,
  35     HasherTAndEndianness<llvm::SHA1, llvm::endianness::native>,
  36     HasherTAndEndianness<llvm::SHA256, llvm::endianness::big>,
  37     HasherTAndEndianness<llvm::SHA256, llvm::endianness::little>,
  38     HasherTAndEndianness<llvm::SHA256, llvm::endianness::native>>;
  39 template <typename HasherT> class HashBuilderTest : public testing::Test {};
  40 TYPED_TEST_SUITE(HashBuilderTest, HasherTAndEndiannessToTest, );
  41
  42 template <typename HasherTAndEndianness>
  43 using HashBuilder = llvm::HashBuilder<typename HasherTAndEndianness::HasherT,
  44                                       HasherTAndEndianness::Endianness>;
  45
  46 template <typename HasherTAndEndianness, typename... Ts>
  47 static typename HashBuilder<HasherTAndEndianness>::template HashResultTy<>
  48 hashWithBuilder(const Ts &...Args) {
  49   return HashBuilder<HasherTAndEndianness>().add(Args...).final();
  50 }
  51
  52 template <typename HasherTAndEndianness, typename... Ts>
  53 static typename HashBuilder<HasherTAndEndianness>::template HashResultTy<>
  54 hashRangeWithBuilder(const Ts &...Args) {
  55   return HashBuilder<HasherTAndEndianness>().addRange(Args...).final();
  56 }
  57
  58 // All the test infrastructure relies on the variadic helpers. Test them first.
  59 TYPED_TEST(HashBuilderTest, VariadicHelpers) {
  60   {
  61     HashBuilder<TypeParam> HBuilder;
  62
  63     HBuilder.add(100);
  64     HBuilder.add('c');
  65     HBuilder.add("string");
  66
  67     EXPECT_EQ(HBuilder.final(), hashWithBuilder<TypeParam>(100, 'c', "string"));
  68   }
  69
  70   {
  71     HashBuilder<TypeParam> HBuilder;
  72
  73     std::vector<int> Vec{100, 101, 102};
  74     HBuilder.addRange(Vec);
  75
  76     EXPECT_EQ(HBuilder.final(), hashRangeWithBuilder<TypeParam>(Vec));
  77   }
  78
  79   {
  80     HashBuilder<TypeParam> HBuilder;
  81
  82     std::vector<int> Vec{200, 201, 202};
  83     HBuilder.addRange(Vec.begin(), Vec.end());
  84
  85     EXPECT_EQ(HBuilder.final(),
  86               hashRangeWithBuilder<TypeParam>(Vec.begin(), Vec.end()));
  87   }
  88 }
  89
  90 TYPED_TEST(HashBuilderTest, AddRangeElements) {
  91   HashBuilder<TypeParam> HBuilder;
  92   int Values[] = {1, 2, 3};
  93   HBuilder.addRangeElements(llvm::ArrayRef<int>(Values));
  94   EXPECT_EQ(HBuilder.final(), hashWithBuilder<TypeParam>(1, 2, 3));
  95 }
  96
  97 TYPED_TEST(HashBuilderTest, AddHashableData) {
  98   using HE = TypeParam;
  99
 100   auto ByteSwapAndHashWithHasher = [](auto Data) {
 101     using H = typename HE::HasherT;
 102     constexpr auto E = HE::Endianness;
 103     H Hasher;
 104     auto SwappedData = llvm::support::endian::byte_swap(Data, E);
 105     Hasher.update(llvm::ArrayRef(
 106         reinterpret_cast<const uint8_t *>(&SwappedData), sizeof(Data)));
 107     return Hasher.final();
 108   };
 109
 110   char C = 'c';
 111   int32_t I = 0x12345678;
 112   uint64_t UI64 = static_cast<uint64_t>(1) << 50;
 113   enum TestEnumeration : uint16_t { TE_One = 1, TE_Two = 2 };
 114   TestEnumeration Enum = TE_Two;
 115
 116   EXPECT_EQ(ByteSwapAndHashWithHasher(C), hashWithBuilder<HE>(C));
 117   EXPECT_EQ(ByteSwapAndHashWithHasher(I), hashWithBuilder<HE>(I));
 118   EXPECT_EQ(ByteSwapAndHashWithHasher(UI64), hashWithBuilder<HE>(UI64));
 119   EXPECT_EQ(ByteSwapAndHashWithHasher(Enum), hashWithBuilder<HE>(Enum));
 120 }
 121
 122 struct SimpleStruct {
 123   char C;
 124   int I;
 125 };
 126
 127 template <typename HasherT, llvm::endianness Endianness>
 128 void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder,
 129              const SimpleStruct &Value) {
 130   HBuilder.add(Value.C);
 131   HBuilder.add(Value.I);
 132 }
 133
 134 struct StructWithoutCopyOrMove {
 135   int I;
 136   StructWithoutCopyOrMove() = default;
 137   explicit StructWithoutCopyOrMove(int I) : I(I) {}
 138   StructWithoutCopyOrMove(const StructWithoutCopyOrMove &) = delete;
 139   StructWithoutCopyOrMove &operator=(const StructWithoutCopyOrMove &) = delete;
 140
 141   template <typename HasherT, llvm::endianness Endianness>
 142   friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder,
 143                       const StructWithoutCopyOrMove &Value) {
 144     HBuilder.add(Value.I);
 145   }
 146 };
 147
 148 // The struct and associated tests are simplified to avoid failures caused by
 149 // different alignments on different platforms.
 150 struct /* __attribute__((packed)) */ StructWithFastHash {
 151   int I;
 152   // char C;
 153
 154   // If possible, we want to hash both `I` and `C` in a single `update`
 155   // call for performance concerns.
 156   template <typename HasherT, llvm::endianness Endianness>
 157   friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder,
 158                       const StructWithFastHash &Value) {
 159     if (Endianness == llvm::endianness::native) {
 160       HBuilder.update(llvm::ArrayRef(reinterpret_cast<const uint8_t *>(&Value),
 161                                      sizeof(Value)));
 162     } else {
 163       // Rely on existing `add` methods to handle endianness.
 164       HBuilder.add(Value.I);
 165       // HBuilder.add(Value.C);
 166     }
 167   }
 168 };
 169
 170 struct CustomContainer {
 171 private:
 172   size_t Size;
 173   int Elements[100];
 174
 175 public:
 176   CustomContainer(size_t Size) : Size(Size) {
 177     for (size_t I = 0; I != Size; ++I)
 178       Elements[I] = I;
 179   }
 180   template <typename HasherT, llvm::endianness Endianness>
 181   friend void addHash(llvm::HashBuilder<HasherT, Endianness> &HBuilder,
 182                       const CustomContainer &Value) {
 183     if (Endianness == llvm::endianness::native) {
 184       HBuilder.update(llvm::ArrayRef(
 185           reinterpret_cast<const uint8_t *>(&Value.Size),
 186           sizeof(Value.Size) + Value.Size * sizeof(Value.Elements[0])));
 187     } else {
 188       HBuilder.addRange(&Value.Elements[0], &Value.Elements[0] + Value.Size);
 189     }
 190   }
 191 };
 192
 193 TYPED_TEST(HashBuilderTest, HashUserDefinedStruct) {
 194   using HE = TypeParam;
 195   EXPECT_EQ(hashWithBuilder<HE>(SimpleStruct{'c', 123}),
 196             hashWithBuilder<HE>('c', 123));
 197   EXPECT_EQ(hashWithBuilder<HE>(StructWithoutCopyOrMove{1}),
 198             hashWithBuilder<HE>(1));
 199   EXPECT_EQ(hashWithBuilder<HE>(StructWithFastHash{123}),
 200             hashWithBuilder<HE>(123));
 201   EXPECT_EQ(hashWithBuilder<HE>(CustomContainer(3)),
 202             hashWithBuilder<HE>(static_cast<size_t>(3), 0, 1, 2));
 203 }
 204
 205 TYPED_TEST(HashBuilderTest, HashArrayRefHashableDataTypes) {
 206   using HE = TypeParam;
 207   int Values[] = {1, 20, 0x12345678};
 208   llvm::ArrayRef<int> Array(Values);
 209   EXPECT_NE(hashWithBuilder<HE>(Array), hashWithBuilder<HE>(1, 20, 0x12345678));
 210   EXPECT_EQ(hashWithBuilder<HE>(Array),
 211             hashRangeWithBuilder<HE>(Array.begin(), Array.end()));
 212   EXPECT_EQ(
 213       hashWithBuilder<HE>(Array),
 214       hashRangeWithBuilder<HE>(Array.data(), Array.data() + Array.size()));
 215 }
 216
 217 TYPED_TEST(HashBuilderTest, HashArrayRef) {
 218   using HE = TypeParam;
 219   int Values[] = {1, 2, 3};
 220   llvm::ArrayRef<int> Array123(&Values[0], 3);
 221   llvm::ArrayRef<int> Array12(&Values[0], 2);
 222   llvm::ArrayRef<int> Array1(&Values[0], 1);
 223   llvm::ArrayRef<int> Array23(&Values[1], 2);
 224   llvm::ArrayRef<int> Array3(&Values[2], 1);
 225   llvm::ArrayRef<int> ArrayEmpty(&Values[0], static_cast<size_t>(0));
 226
 227   auto Hash123andEmpty = hashWithBuilder<HE>(Array123, ArrayEmpty);
 228   auto Hash12And3 = hashWithBuilder<HE>(Array12, Array3);
 229   auto Hash1And23 = hashWithBuilder<HE>(Array1, Array23);
 230   auto HashEmptyAnd123 = hashWithBuilder<HE>(ArrayEmpty, Array123);
 231
 232   EXPECT_NE(Hash123andEmpty, Hash12And3);
 233   EXPECT_NE(Hash123andEmpty, Hash1And23);
 234   EXPECT_NE(Hash123andEmpty, HashEmptyAnd123);
 235   EXPECT_NE(Hash12And3, Hash1And23);
 236   EXPECT_NE(Hash12And3, HashEmptyAnd123);
 237   EXPECT_NE(Hash1And23, HashEmptyAnd123);
 238 }
 239
 240 TYPED_TEST(HashBuilderTest, HashArrayRefNonHashableDataTypes) {
 241   using HE = TypeParam;
 242   SimpleStruct Values[] = {{'a', 100}, {'b', 200}};
 243   llvm::ArrayRef<SimpleStruct> Array(Values);
 244   EXPECT_NE(
 245       hashWithBuilder<HE>(Array),
 246       hashWithBuilder<HE>(SimpleStruct{'a', 100}, SimpleStruct{'b', 200}));
 247 }
 248
 249 TYPED_TEST(HashBuilderTest, HashStringRef) {
 250   using HE = TypeParam;
 251   llvm::StringRef SEmpty("");
 252   llvm::StringRef S1("1");
 253   llvm::StringRef S12("12");
 254   llvm::StringRef S123("123");
 255   llvm::StringRef S23("23");
 256   llvm::StringRef S3("3");
 257
 258   auto Hash123andEmpty = hashWithBuilder<HE>(S123, SEmpty);
 259   auto Hash12And3 = hashWithBuilder<HE>(S12, S3);
 260   auto Hash1And23 = hashWithBuilder<HE>(S1, S23);
 261   auto HashEmptyAnd123 = hashWithBuilder<HE>(SEmpty, S123);
 262
 263   EXPECT_NE(Hash123andEmpty, Hash12And3);
 264   EXPECT_NE(Hash123andEmpty, Hash1And23);
 265   EXPECT_NE(Hash123andEmpty, HashEmptyAnd123);
 266   EXPECT_NE(Hash12And3, Hash1And23);
 267   EXPECT_NE(Hash12And3, HashEmptyAnd123);
 268   EXPECT_NE(Hash1And23, HashEmptyAnd123);
 269 }
 270
 271 TYPED_TEST(HashBuilderTest, HashStdString) {
 272   using HE = TypeParam;
 273   EXPECT_EQ(hashWithBuilder<HE>(std::string("123")),
 274             hashWithBuilder<HE>(llvm::StringRef("123")));
 275 }
 276
 277 TYPED_TEST(HashBuilderTest, HashStdPair) {
 278   using HE = TypeParam;
 279   EXPECT_EQ(hashWithBuilder<HE>(std::make_pair(1, "string")),
 280             hashWithBuilder<HE>(1, "string"));
 281
 282   std::pair<StructWithoutCopyOrMove, std::string> Pair;
 283   Pair.first.I = 1;
 284   Pair.second = "string";
 285   EXPECT_EQ(hashWithBuilder<HE>(Pair), hashWithBuilder<HE>(1, "string"));
 286 }
 287
 288 TYPED_TEST(HashBuilderTest, HashStdTuple) {
 289   using HE = TypeParam;
 290
 291   EXPECT_EQ(hashWithBuilder<HE>(std::make_tuple(1)), hashWithBuilder<HE>(1));
 292   EXPECT_EQ(hashWithBuilder<HE>(std::make_tuple(2ULL)),
 293             hashWithBuilder<HE>(2ULL));
 294   EXPECT_EQ(hashWithBuilder<HE>(std::make_tuple("three")),
 295             hashWithBuilder<HE>("three"));
 296   EXPECT_EQ(hashWithBuilder<HE>(std::make_tuple(1, 2ULL)),
 297             hashWithBuilder<HE>(1, 2ULL));
 298   EXPECT_EQ(hashWithBuilder<HE>(std::make_tuple(1, 2ULL, "three")),
 299             hashWithBuilder<HE>(1, 2ULL, "three"));
 300
 301   std::tuple<StructWithoutCopyOrMove, std::string> Tuple;
 302   std::get<0>(Tuple).I = 1;
 303   std::get<1>(Tuple) = "two";
 304
 305   EXPECT_EQ(hashWithBuilder<HE>(Tuple), hashWithBuilder<HE>(1, "two"));
 306 }
 307
 308 TYPED_TEST(HashBuilderTest, HashRangeWithForwardIterator) {
 309   using HE = TypeParam;
 310   std::list<int> List;
 311   List.push_back(1);
 312   List.push_back(2);
 313   List.push_back(3);
 314   EXPECT_NE(hashRangeWithBuilder<HE>(List), hashWithBuilder<HE>(1, 2, 3));
 315 }
 316
 317 TEST(CustomHasher, CustomHasher) {
 318   struct SumHash {
 319     explicit SumHash(uint8_t Seed1, uint8_t Seed2) : Hash(Seed1 + Seed2) {}
 320     void update(llvm::ArrayRef<uint8_t> Data) {
 321       for (uint8_t C : Data)
 322         Hash += C;
 323     }
 324     uint8_t Hash;
 325   };
 326
 327   {
 328     llvm::HashBuilder<SumHash, llvm::endianness::little> HBuilder(0, 1);
 329     EXPECT_EQ(HBuilder.add(0x02, 0x03, 0x400).getHasher().Hash, 0xa);
 330   }
 331   {
 332     llvm::HashBuilder<SumHash, llvm::endianness::little> HBuilder(2, 3);
 333     EXPECT_EQ(HBuilder.add("ab", 'c').getHasher().Hash,
 334               static_cast<uint8_t>(/*seeds*/ 2 + 3 + /*range size*/ 2 +
 335                                    /*characters*/ 'a' + 'b' + 'c'));
 336   }
 337 }