1 //===- unittests/Lex/HeaderMapTest.cpp - HeaderMap tests ----------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===--------------------------------------------------------------===// 9 10 #include "clang/Basic/CharInfo.h" 11 #include "clang/Lex/HeaderMap.h" 12 #include "clang/Lex/HeaderMapTypes.h" 13 #include "llvm/ADT/SmallString.h" 14 #include "llvm/Support/SwapByteOrder.h" 15 #include "gtest/gtest.h" 16 #include <cassert> 17 #include <type_traits> 18 19 using namespace clang; 20 using namespace llvm; 21 22 namespace { 23 24 // Lay out a header file for testing. 25 template <unsigned NumBuckets, unsigned NumBytes> struct MapFile { 26 HMapHeader Header; 27 HMapBucket Buckets[NumBuckets]; 28 unsigned char Bytes[NumBytes]; 29 30 void init() { 31 memset(this, 0, sizeof(MapFile)); 32 Header.Magic = HMAP_HeaderMagicNumber; 33 Header.Version = HMAP_HeaderVersion; 34 Header.NumBuckets = NumBuckets; 35 Header.StringsOffset = sizeof(Header) + sizeof(Buckets); 36 } 37 38 void swapBytes() { 39 using llvm::sys::getSwappedBytes; 40 Header.Magic = getSwappedBytes(Header.Magic); 41 Header.Version = getSwappedBytes(Header.Version); 42 Header.NumBuckets = getSwappedBytes(Header.NumBuckets); 43 Header.StringsOffset = getSwappedBytes(Header.StringsOffset); 44 } 45 46 std::unique_ptr<const MemoryBuffer> getBuffer() const { 47 return MemoryBuffer::getMemBuffer( 48 StringRef(reinterpret_cast<const char *>(this), sizeof(MapFile)), 49 "header", 50 /* RequresNullTerminator */ false); 51 } 52 }; 53 54 // The header map hash function. 55 static inline unsigned getHash(StringRef Str) { 56 unsigned Result = 0; 57 for (char C : Str) 58 Result += toLowercase(C) * 13; 59 return Result; 60 } 61 62 template <class FileTy> struct FileMaker { 63 FileTy &File; 64 unsigned SI = 1; 65 unsigned BI = 0; 66 FileMaker(FileTy &File) : File(File) {} 67 68 unsigned addString(StringRef S) { 69 assert(SI + S.size() + 1 <= sizeof(File.Bytes)); 70 std::copy(S.begin(), S.end(), File.Bytes + SI); 71 auto OldSI = SI; 72 SI += S.size() + 1; 73 return OldSI; 74 } 75 void addBucket(unsigned Hash, unsigned Key, unsigned Prefix, unsigned Suffix) { 76 assert(!(File.Header.NumBuckets & (File.Header.NumBuckets - 1))); 77 unsigned I = Hash & (File.Header.NumBuckets - 1); 78 do { 79 if (!File.Buckets[I].Key) { 80 File.Buckets[I].Key = Key; 81 File.Buckets[I].Prefix = Prefix; 82 File.Buckets[I].Suffix = Suffix; 83 ++File.Header.NumEntries; 84 return; 85 } 86 ++I; 87 I &= File.Header.NumBuckets - 1; 88 } while (I != (Hash & (File.Header.NumBuckets - 1))); 89 llvm_unreachable("no empty buckets"); 90 } 91 }; 92 93 TEST(HeaderMapTest, checkHeaderEmpty) { 94 bool NeedsSwap; 95 ASSERT_FALSE(HeaderMapImpl::checkHeader( 96 *MemoryBuffer::getMemBufferCopy("", "empty"), NeedsSwap)); 97 ASSERT_FALSE(HeaderMapImpl::checkHeader( 98 *MemoryBuffer::getMemBufferCopy("", "empty"), NeedsSwap)); 99 } 100 101 TEST(HeaderMapTest, checkHeaderMagic) { 102 MapFile<1, 1> File; 103 File.init(); 104 File.Header.Magic = 0; 105 bool NeedsSwap; 106 ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 107 } 108 109 TEST(HeaderMapTest, checkHeaderReserved) { 110 MapFile<1, 1> File; 111 File.init(); 112 File.Header.Reserved = 1; 113 bool NeedsSwap; 114 ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 115 } 116 117 TEST(HeaderMapTest, checkHeaderVersion) { 118 MapFile<1, 1> File; 119 File.init(); 120 ++File.Header.Version; 121 bool NeedsSwap; 122 ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 123 } 124 125 TEST(HeaderMapTest, checkHeaderValidButEmpty) { 126 MapFile<1, 1> File; 127 File.init(); 128 bool NeedsSwap; 129 ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 130 ASSERT_FALSE(NeedsSwap); 131 132 File.swapBytes(); 133 ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 134 ASSERT_TRUE(NeedsSwap); 135 } 136 137 TEST(HeaderMapTest, checkHeader3Buckets) { 138 MapFile<3, 1> File; 139 ASSERT_EQ(3 * sizeof(HMapBucket), sizeof(File.Buckets)); 140 141 File.init(); 142 bool NeedsSwap; 143 ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 144 } 145 146 TEST(HeaderMapTest, checkHeaderNotEnoughBuckets) { 147 MapFile<1, 1> File; 148 File.init(); 149 File.Header.NumBuckets = 8; 150 bool NeedsSwap; 151 ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 152 } 153 154 TEST(HeaderMapTest, lookupFilename) { 155 typedef MapFile<2, 7> FileTy; 156 FileTy File; 157 File.init(); 158 159 FileMaker<FileTy> Maker(File); 160 auto a = Maker.addString("a"); 161 auto b = Maker.addString("b"); 162 auto c = Maker.addString("c"); 163 Maker.addBucket(getHash("a"), a, b, c); 164 165 bool NeedsSwap; 166 ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 167 ASSERT_FALSE(NeedsSwap); 168 HeaderMapImpl Map(File.getBuffer(), NeedsSwap); 169 170 SmallString<8> DestPath; 171 ASSERT_EQ("bc", Map.lookupFilename("a", DestPath)); 172 } 173 174 template <class FileTy, class PaddingTy> struct PaddedFile { 175 FileTy File; 176 PaddingTy Padding; 177 }; 178 179 TEST(HeaderMapTest, lookupFilenameTruncated) { 180 typedef MapFile<2, 64 - sizeof(HMapHeader) - 2 * sizeof(HMapBucket)> FileTy; 181 static_assert(std::is_standard_layout<FileTy>::value, 182 "Expected standard layout"); 183 static_assert(sizeof(FileTy) == 64, "check the math"); 184 PaddedFile<FileTy, uint64_t> P; 185 auto &File = P.File; 186 auto &Padding = P.Padding; 187 File.init(); 188 189 FileMaker<FileTy> Maker(File); 190 auto a = Maker.addString("a"); 191 auto b = Maker.addString("b"); 192 auto c = Maker.addString("c"); 193 Maker.addBucket(getHash("a"), a, b, c); 194 195 // Add 'x' characters to cause an overflow into Padding. 196 ASSERT_EQ('c', File.Bytes[5]); 197 for (unsigned I = 6; I < sizeof(File.Bytes); ++I) { 198 ASSERT_EQ(0, File.Bytes[I]); 199 File.Bytes[I] = 'x'; 200 } 201 Padding = 0xffffffff; // Padding won't stop it either. 202 203 bool NeedsSwap; 204 ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 205 ASSERT_FALSE(NeedsSwap); 206 HeaderMapImpl Map(File.getBuffer(), NeedsSwap); 207 208 // The string for "c" runs to the end of File. Check that the suffix 209 // ("cxxxx...") is ignored. Another option would be to return an empty 210 // filename altogether. 211 SmallString<24> DestPath; 212 ASSERT_EQ("b", Map.lookupFilename("a", DestPath)); 213 } 214 215 } // end namespace 216