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 19using namespace clang; 20using namespace llvm; 21 22namespace { 23 24// Lay out a header file for testing. 25template <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. 55static inline unsigned getHash(StringRef Str) { 56 unsigned Result = 0; 57 for (char C : Str) 58 Result += toLowercase(C) * 13; 59 return Result; 60} 61 62template <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 93TEST(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 101TEST(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 109TEST(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 117TEST(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 125TEST(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 137TEST(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 146TEST(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 155TEST(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 163TEST(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 183template <class FileTy, class PaddingTy> struct PaddedFile { 184 FileTy File; 185 PaddingTy Padding; 186}; 187 188TEST(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 223TEST(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