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