external/bsd/llvm/dist/clang/lib/Lex/HeaderMap.cpp

   1 //===--- HeaderMap.cpp - A file that acts like dir of symlinks ------------===//
   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 // This file implements the HeaderMap interface.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Lex/HeaderMap.h"
  15 #include "clang/Basic/CharInfo.h"
  16 #include "clang/Basic/FileManager.h"
  17 #include "llvm/ADT/SmallString.h"
  18 #include "llvm/Support/DataTypes.h"
  19 #include "llvm/Support/MathExtras.h"
  20 #include "llvm/Support/MemoryBuffer.h"
  21 #include <cstdio>
  22 #include <memory>
  23 using namespace clang;
  24
  25 //===----------------------------------------------------------------------===//
  26 // Data Structures and Manifest Constants
  27 //===----------------------------------------------------------------------===//
  28
  29 enum {
  30   HMAP_HeaderMagicNumber = ('h' << 24) | ('m' << 16) | ('a' << 8) | 'p',
  31   HMAP_HeaderVersion = 1,
  32
  33   HMAP_EmptyBucketKey = 0
  34 };
  35
  36 namespace clang {
  37 struct HMapBucket {
  38   uint32_t Key;          // Offset (into strings) of key.
  39
  40   uint32_t Prefix;     // Offset (into strings) of value prefix.
  41   uint32_t Suffix;     // Offset (into strings) of value suffix.
  42 };
  43
  44 struct HMapHeader {
  45   uint32_t Magic;           // Magic word, also indicates byte order.
  46   uint16_t Version;         // Version number -- currently 1.
  47   uint16_t Reserved;        // Reserved for future use - zero for now.
  48   uint32_t StringsOffset;   // Offset to start of string pool.
  49   uint32_t NumEntries;      // Number of entries in the string table.
  50   uint32_t NumBuckets;      // Number of buckets (always a power of 2).
  51   uint32_t MaxValueLength;  // Length of longest result path (excluding nul).
  52   // An array of 'NumBuckets' HMapBucket objects follows this header.
  53   // Strings follow the buckets, at StringsOffset.
  54 };
  55 } // end namespace clang.
  56
  57 /// HashHMapKey - This is the 'well known' hash function required by the file
  58 /// format, used to look up keys in the hash table.  The hash table uses simple
  59 /// linear probing based on this function.
  60 static inline unsigned HashHMapKey(StringRef Str) {
  61   unsigned Result = 0;
  62   const char *S = Str.begin(), *End = Str.end();
  63
  64   for (; S != End; S++)
  65     Result += toLowercase(*S) * 13;
  66   return Result;
  67 }
  68
  69
  70
  71 //===----------------------------------------------------------------------===//
  72 // Verification and Construction
  73 //===----------------------------------------------------------------------===//
  74
  75 /// HeaderMap::Create - This attempts to load the specified file as a header
  76 /// map.  If it doesn't look like a HeaderMap, it gives up and returns null.
  77 /// If it looks like a HeaderMap but is obviously corrupted, it puts a reason
  78 /// into the string error argument and returns null.
  79 const HeaderMap *HeaderMap::Create(const FileEntry *FE, FileManager &FM) {
  80   // If the file is too small to be a header map, ignore it.
  81   unsigned FileSize = FE->getSize();
  82   if (FileSize <= sizeof(HMapHeader)) return nullptr;
  83
  84   auto FileBuffer = FM.getBufferForFile(FE);
  85   if (!FileBuffer) return nullptr;  // Unreadable file?
  86   const char *FileStart = (*FileBuffer)->getBufferStart();
  87
  88   // We know the file is at least as big as the header, check it now.
  89   const HMapHeader *Header = reinterpret_cast<const HMapHeader*>(FileStart);
  90
  91   // Sniff it to see if it's a headermap by checking the magic number and
  92   // version.
  93   bool NeedsByteSwap;
  94   if (Header->Magic == HMAP_HeaderMagicNumber &&
  95       Header->Version == HMAP_HeaderVersion)
  96     NeedsByteSwap = false;
  97   else if (Header->Magic == llvm::ByteSwap_32(HMAP_HeaderMagicNumber) &&
  98            Header->Version == llvm::ByteSwap_16(HMAP_HeaderVersion))
  99     NeedsByteSwap = true;  // Mixed endianness headermap.
 100   else
 101     return nullptr;  // Not a header map.
 102
 103   if (Header->Reserved != 0) return nullptr;
 104
 105   // Okay, everything looks good, create the header map.
 106   return new HeaderMap(std::move(*FileBuffer), NeedsByteSwap);
 107 }
 108
 109 //===----------------------------------------------------------------------===//
 110 //  Utility Methods
 111 //===----------------------------------------------------------------------===//
 112
 113
 114 /// getFileName - Return the filename of the headermap.
 115 const char *HeaderMap::getFileName() const {
 116   return FileBuffer->getBufferIdentifier();
 117 }
 118
 119 unsigned HeaderMap::getEndianAdjustedWord(unsigned X) const {
 120   if (!NeedsBSwap) return X;
 121   return llvm::ByteSwap_32(X);
 122 }
 123
 124 /// getHeader - Return a reference to the file header, in unbyte-swapped form.
 125 /// This method cannot fail.
 126 const HMapHeader &HeaderMap::getHeader() const {
 127   // We know the file is at least as big as the header.  Return it.
 128   return *reinterpret_cast<const HMapHeader*>(FileBuffer->getBufferStart());
 129 }
 130
 131 /// getBucket - Return the specified hash table bucket from the header map,
 132 /// bswap'ing its fields as appropriate.  If the bucket number is not valid,
 133 /// this return a bucket with an empty key (0).
 134 HMapBucket HeaderMap::getBucket(unsigned BucketNo) const {
 135   HMapBucket Result;
 136   Result.Key = HMAP_EmptyBucketKey;
 137
 138   const HMapBucket *BucketArray =
 139     reinterpret_cast<const HMapBucket*>(FileBuffer->getBufferStart() +
 140                                         sizeof(HMapHeader));
 141
 142   const HMapBucket *BucketPtr = BucketArray+BucketNo;
 143   if ((const char*)(BucketPtr+1) > FileBuffer->getBufferEnd()) {
 144     Result.Prefix = 0;
 145     Result.Suffix = 0;
 146     return Result;  // Invalid buffer, corrupt hmap.
 147   }
 148
 149   // Otherwise, the bucket is valid.  Load the values, bswapping as needed.
 150   Result.Key    = getEndianAdjustedWord(BucketPtr->Key);
 151   Result.Prefix = getEndianAdjustedWord(BucketPtr->Prefix);
 152   Result.Suffix = getEndianAdjustedWord(BucketPtr->Suffix);
 153   return Result;
 154 }
 155
 156 /// getString - Look up the specified string in the string table.  If the string
 157 /// index is not valid, it returns an empty string.
 158 const char *HeaderMap::getString(unsigned StrTabIdx) const {
 159   // Add the start of the string table to the idx.
 160   StrTabIdx += getEndianAdjustedWord(getHeader().StringsOffset);
 161
 162   // Check for invalid index.
 163   if (StrTabIdx >= FileBuffer->getBufferSize())
 164     return nullptr;
 165
 166   // Otherwise, we have a valid pointer into the file.  Just return it.  We know
 167   // that the "string" can not overrun the end of the file, because the buffer
 168   // is nul terminated by virtue of being a MemoryBuffer.
 169   return FileBuffer->getBufferStart()+StrTabIdx;
 170 }
 171
 172 //===----------------------------------------------------------------------===//
 173 // The Main Drivers
 174 //===----------------------------------------------------------------------===//
 175
 176 /// dump - Print the contents of this headermap to stderr.
 177 void HeaderMap::dump() const {
 178   const HMapHeader &Hdr = getHeader();
 179   unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
 180
 181   fprintf(stderr, "Header Map %s:\n  %d buckets, %d entries\n",
 182           getFileName(), NumBuckets,
 183           getEndianAdjustedWord(Hdr.NumEntries));
 184
 185   for (unsigned i = 0; i != NumBuckets; ++i) {
 186     HMapBucket B = getBucket(i);
 187     if (B.Key == HMAP_EmptyBucketKey) continue;
 188
 189     const char *Key    = getString(B.Key);
 190     const char *Prefix = getString(B.Prefix);
 191     const char *Suffix = getString(B.Suffix);
 192     fprintf(stderr, "  %d. %s -> '%s' '%s'\n", i, Key, Prefix, Suffix);
 193   }
 194 }
 195
 196 /// LookupFile - Check to see if the specified relative filename is located in
 197 /// this HeaderMap.  If so, open it and return its FileEntry.
 198 const FileEntry *HeaderMap::LookupFile(
 199     StringRef Filename, FileManager &FM) const {
 200
 201   SmallString<1024> Path;
 202   StringRef Dest = lookupFilename(Filename, Path);
 203   if (Dest.empty())
 204     return nullptr;
 205
 206   return FM.getFile(Dest);
 207 }
 208
 209 StringRef HeaderMap::lookupFilename(StringRef Filename,
 210                                     SmallVectorImpl<char> &DestPath) const {
 211   const HMapHeader &Hdr = getHeader();
 212   unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
 213
 214   // If the number of buckets is not a power of two, the headermap is corrupt.
 215   // Don't probe infinitely.
 216   if (NumBuckets & (NumBuckets-1))
 217     return StringRef();
 218
 219   // Linearly probe the hash table.
 220   for (unsigned Bucket = HashHMapKey(Filename);; ++Bucket) {
 221     HMapBucket B = getBucket(Bucket & (NumBuckets-1));
 222     if (B.Key == HMAP_EmptyBucketKey) return StringRef(); // Hash miss.
 223
 224     // See if the key matches.  If not, probe on.
 225     if (!Filename.equals_lower(getString(B.Key)))
 226       continue;
 227
 228     // If so, we have a match in the hash table.  Construct the destination
 229     // path.
 230     StringRef Prefix = getString(B.Prefix);
 231     StringRef Suffix = getString(B.Suffix);
 232     DestPath.clear();
 233     DestPath.append(Prefix.begin(), Prefix.end());
 234     DestPath.append(Suffix.begin(), Suffix.end());
 235     return StringRef(DestPath.begin(), DestPath.size());
 236   }
 237 }