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 }
337