xref: /llvm-project/llvm/unittests/Support/HashBuilderTest.cpp (revision f039a2cf107a143ea2c0cf3f2a88ec2400421287) 
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 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::makeArrayRef(
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::support::endianness Endianness>
128 void addHash(llvm::HashBuilderImpl<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::support::endianness Endianness>
142   friend void addHash(llvm::HashBuilderImpl<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::support::endianness Endianness>
157   friend void addHash(llvm::HashBuilderImpl<HasherT, Endianness> &HBuilder,
158                       const StructWithFastHash &Value) {
159     if (Endianness == llvm::support::endian::system_endianness()) {
160       HBuilder.update(llvm::makeArrayRef(
161           reinterpret_cast<const uint8_t *>(&Value), 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::support::endianness Endianness>
181   friend void addHash(llvm::HashBuilderImpl<HasherT, Endianness> &HBuilder,
182                       const CustomContainer &Value) {
183     if (Endianness == llvm::support::endian::system_endianness()) {
184       HBuilder.update(llvm::makeArrayRef(
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::support::endianness::little> HBuilder(0,
329                                                                            1);
330     EXPECT_EQ(HBuilder.add(0x02, 0x03, 0x400).getHasher().Hash, 0xa);
331   }
332   {
333     llvm::HashBuilder<SumHash, llvm::support::endianness::little> HBuilder(2,
334                                                                            3);
335     EXPECT_EQ(HBuilder.add("ab", 'c').getHasher().Hash,
336               static_cast<uint8_t>(/*seeds*/ 2 + 3 + /*range size*/ 2 +
337                                    /*characters*/ 'a' + 'b' + 'c'));
338   }
339 }
340