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[] = {{.C: 'a', .I: 100}, {.C: 'b', .I: 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>(t&: Tuple).I = 1; |
303 | std::get<1>(t&: 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(x: 1); |
312 | List.push_back(x: 2); |
313 | List.push_back(x: 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 | } |
338 | |