clang/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
  18 using namespace clang;
  19 using namespace llvm;
  20
  21 namespace {
  22
  23 // Lay out a header file for testing.
  24 template <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.
  54 static inline unsigned getHash(StringRef Str) {
  55   unsigned Result = 0;
  56   for (char C : Str)
  57     Result += toLowercase(C) * 13;
  58   return Result;
  59 }
  60
  61 template <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
  92 TEST(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
 100 TEST(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
 108 TEST(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
 116 TEST(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
 124 TEST(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
 136 TEST(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
 145 TEST(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
 154 TEST(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
 162 TEST(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
 182 template <class FileTy, class PaddingTy> struct PaddedFile {
 183   FileTy File;
 184   PaddingTy Padding;
 185 };
 186
 187 TEST(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
 222 TEST(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