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, checkHeader0Buckets) { 147 // Create with 1 bucket to avoid 0-sized arrays. 148 MapFile<1, 1> File; 149 File.init(); 150 File.Header.NumBuckets = 0; 151 bool NeedsSwap; 152 ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 153 } 154 155 TEST(HeaderMapTest, checkHeaderNotEnoughBuckets) { 156 MapFile<1, 1> File; 157 File.init(); 158 File.Header.NumBuckets = 8; 159 bool NeedsSwap; 160 ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 161 } 162 163 TEST(HeaderMapTest, lookupFilename) { 164 typedef MapFile<2, 7> FileTy; 165 FileTy File; 166 File.init(); 167 168 FileMaker<FileTy> Maker(File); 169 auto a = Maker.addString("a"); 170 auto b = Maker.addString("b"); 171 auto c = Maker.addString("c"); 172 Maker.addBucket(getHash("a"), a, b, c); 173 174 bool NeedsSwap; 175 ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 176 ASSERT_FALSE(NeedsSwap); 177 HeaderMapImpl Map(File.getBuffer(), NeedsSwap); 178 179 SmallString<8> DestPath; 180 ASSERT_EQ("bc", Map.lookupFilename("a", DestPath)); 181 } 182 183 template <class FileTy, class PaddingTy> struct PaddedFile { 184 FileTy File; 185 PaddingTy Padding; 186 }; 187 188 TEST(HeaderMapTest, lookupFilenameTruncatedSuffix) { 189 typedef MapFile<2, 64 - sizeof(HMapHeader) - 2 * sizeof(HMapBucket)> FileTy; 190 static_assert(std::is_standard_layout<FileTy>::value, 191 "Expected standard layout"); 192 static_assert(sizeof(FileTy) == 64, "check the math"); 193 PaddedFile<FileTy, uint64_t> P; 194 auto &File = P.File; 195 auto &Padding = P.Padding; 196 File.init(); 197 198 FileMaker<FileTy> Maker(File); 199 auto a = Maker.addString("a"); 200 auto b = Maker.addString("b"); 201 auto c = Maker.addString("c"); 202 Maker.addBucket(getHash("a"), a, b, c); 203 204 // Add 'x' characters to cause an overflow into Padding. 205 ASSERT_EQ('c', File.Bytes[5]); 206 for (unsigned I = 6; I < sizeof(File.Bytes); ++I) { 207 ASSERT_EQ(0, File.Bytes[I]); 208 File.Bytes[I] = 'x'; 209 } 210 Padding = 0xffffffff; // Padding won't stop it either. 211 212 bool NeedsSwap; 213 ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 214 ASSERT_FALSE(NeedsSwap); 215 HeaderMapImpl Map(File.getBuffer(), NeedsSwap); 216 217 // The string for "c" runs to the end of File. Check that the suffix 218 // ("cxxxx...") is detected as truncated, and an empty string is returned. 219 SmallString<24> DestPath; 220 ASSERT_EQ("", Map.lookupFilename("a", DestPath)); 221 } 222 223 TEST(HeaderMapTest, lookupFilenameTruncatedPrefix) { 224 typedef MapFile<2, 64 - sizeof(HMapHeader) - 2 * sizeof(HMapBucket)> FileTy; 225 static_assert(std::is_standard_layout<FileTy>::value, 226 "Expected standard layout"); 227 static_assert(sizeof(FileTy) == 64, "check the math"); 228 PaddedFile<FileTy, uint64_t> P; 229 auto &File = P.File; 230 auto &Padding = P.Padding; 231 File.init(); 232 233 FileMaker<FileTy> Maker(File); 234 auto a = Maker.addString("a"); 235 auto c = Maker.addString("c"); 236 auto b = Maker.addString("b"); // Store the prefix last. 237 Maker.addBucket(getHash("a"), a, b, c); 238 239 // Add 'x' characters to cause an overflow into Padding. 240 ASSERT_EQ('b', File.Bytes[5]); 241 for (unsigned I = 6; I < sizeof(File.Bytes); ++I) { 242 ASSERT_EQ(0, File.Bytes[I]); 243 File.Bytes[I] = 'x'; 244 } 245 Padding = 0xffffffff; // Padding won't stop it either. 246 247 bool NeedsSwap; 248 ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap)); 249 ASSERT_FALSE(NeedsSwap); 250 HeaderMapImpl Map(File.getBuffer(), NeedsSwap); 251 252 // The string for "b" runs to the end of File. Check that the prefix 253 // ("bxxxx...") is detected as truncated, and an empty string is returned. 254 SmallString<24> DestPath; 255 ASSERT_EQ("", Map.lookupFilename("a", DestPath)); 256 } 257 258 } // end namespace 259
