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<>
hashWithBuilder(const Ts &...Args)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<>
hashRangeWithBuilder(const Ts &...Args)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.
TYPED_TEST(HashBuilderTest,VariadicHelpers)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
TYPED_TEST(HashBuilderTest,AddRangeElements)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
TYPED_TEST(HashBuilderTest,AddHashableData)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>
addHash(llvm::HashBuilder<HasherT,Endianness> & HBuilder,const SimpleStruct & Value)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;
StructWithoutCopyOrMoveStructWithoutCopyOrMove137 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>
addHash(llvm::HashBuilder<HasherT,Endianness> & HBuilder,const StructWithoutCopyOrMove & Value)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>
addHash(llvm::HashBuilder<HasherT,Endianness> & HBuilder,const StructWithFastHash & Value)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:
CustomContainerCustomContainer176 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>
addHash(llvm::HashBuilder<HasherT,Endianness> & HBuilder,const CustomContainer & Value)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
TYPED_TEST(HashBuilderTest,HashUserDefinedStruct)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
TYPED_TEST(HashBuilderTest,HashArrayRefHashableDataTypes)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
TYPED_TEST(HashBuilderTest,HashArrayRef)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
TYPED_TEST(HashBuilderTest,HashArrayRefNonHashableDataTypes)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
TYPED_TEST(HashBuilderTest,HashStringRef)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
TYPED_TEST(HashBuilderTest,HashStdString)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
TYPED_TEST(HashBuilderTest,HashStdPair)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
TYPED_TEST(HashBuilderTest,HashStdTuple)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
TYPED_TEST(HashBuilderTest,HashRangeWithForwardIterator)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
TEST(CustomHasher,CustomHasher)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 }
338