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