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