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
init__anon54b0c0200111::MapFile30 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
swapBytes__anon54b0c0200111::MapFile38 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
getBuffer__anon54b0c0200111::MapFile46 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.
getHash(StringRef Str)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;
FileMaker__anon54b0c0200111::FileMaker66 FileMaker(FileTy &File) : File(File) {}
67
addString__anon54b0c0200111::FileMaker68 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 }
addBucket__anon54b0c0200111::FileMaker75 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
TEST(HeaderMapTest,checkHeaderEmpty)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
TEST(HeaderMapTest,checkHeaderMagic)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
TEST(HeaderMapTest,checkHeaderReserved)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
TEST(HeaderMapTest,checkHeaderVersion)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
TEST(HeaderMapTest,checkHeaderValidButEmpty)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
TEST(HeaderMapTest,checkHeader3Buckets)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
TEST(HeaderMapTest,checkHeader0Buckets)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
TEST(HeaderMapTest,checkHeaderNotEnoughBuckets)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
TEST(HeaderMapTest,lookupFilename)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
TEST(HeaderMapTest,lookupFilenameTruncatedSuffix)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
TEST(HeaderMapTest,lookupFilenameTruncatedPrefix)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