Clang Project

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