contrib/llvm/tools/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/OwningPtr.h"
  18 #include "llvm/ADT/SmallString.h"
  19 #include "llvm/Support/DataTypes.h"
  20 #include "llvm/Support/MathExtras.h"
  21 #include "llvm/Support/MemoryBuffer.h"
  22 #include <cstdio>
  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 0;
  83
  84   OwningPtr<const llvm::MemoryBuffer> FileBuffer(FM.getBufferForFile(FE));
  85   if (FileBuffer == 0) return 0;  // 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 0;  // Not a header map.
 102
 103   if (Header->Reserved != 0) return 0;
 104
 105   // Okay, everything looks good, create the header map.
 106   return new HeaderMap(FileBuffer.take(), NeedsByteSwap);
 107 }
 108
 109 HeaderMap::~HeaderMap() {
 110   delete FileBuffer;
 111 }
 112
 113 //===----------------------------------------------------------------------===//
 114 //  Utility Methods
 115 //===----------------------------------------------------------------------===//
 116
 117
 118 /// getFileName - Return the filename of the headermap.
 119 const char *HeaderMap::getFileName() const {
 120   return FileBuffer->getBufferIdentifier();
 121 }
 122
 123 unsigned HeaderMap::getEndianAdjustedWord(unsigned X) const {
 124   if (!NeedsBSwap) return X;
 125   return llvm::ByteSwap_32(X);
 126 }
 127
 128 /// getHeader - Return a reference to the file header, in unbyte-swapped form.
 129 /// This method cannot fail.
 130 const HMapHeader &HeaderMap::getHeader() const {
 131   // We know the file is at least as big as the header.  Return it.
 132   return *reinterpret_cast<const HMapHeader*>(FileBuffer->getBufferStart());
 133 }
 134
 135 /// getBucket - Return the specified hash table bucket from the header map,
 136 /// bswap'ing its fields as appropriate.  If the bucket number is not valid,
 137 /// this return a bucket with an empty key (0).
 138 HMapBucket HeaderMap::getBucket(unsigned BucketNo) const {
 139   HMapBucket Result;
 140   Result.Key = HMAP_EmptyBucketKey;
 141
 142   const HMapBucket *BucketArray =
 143     reinterpret_cast<const HMapBucket*>(FileBuffer->getBufferStart() +
 144                                         sizeof(HMapHeader));
 145
 146   const HMapBucket *BucketPtr = BucketArray+BucketNo;
 147   if ((const char*)(BucketPtr+1) > FileBuffer->getBufferEnd()) {
 148     Result.Prefix = 0;
 149     Result.Suffix = 0;
 150     return Result;  // Invalid buffer, corrupt hmap.
 151   }
 152
 153   // Otherwise, the bucket is valid.  Load the values, bswapping as needed.
 154   Result.Key    = getEndianAdjustedWord(BucketPtr->Key);
 155   Result.Prefix = getEndianAdjustedWord(BucketPtr->Prefix);
 156   Result.Suffix = getEndianAdjustedWord(BucketPtr->Suffix);
 157   return Result;
 158 }
 159
 160 /// getString - Look up the specified string in the string table.  If the string
 161 /// index is not valid, it returns an empty string.
 162 const char *HeaderMap::getString(unsigned StrTabIdx) const {
 163   // Add the start of the string table to the idx.
 164   StrTabIdx += getEndianAdjustedWord(getHeader().StringsOffset);
 165
 166   // Check for invalid index.
 167   if (StrTabIdx >= FileBuffer->getBufferSize())
 168     return 0;
 169
 170   // Otherwise, we have a valid pointer into the file.  Just return it.  We know
 171   // that the "string" can not overrun the end of the file, because the buffer
 172   // is nul terminated by virtue of being a MemoryBuffer.
 173   return FileBuffer->getBufferStart()+StrTabIdx;
 174 }
 175
 176 //===----------------------------------------------------------------------===//
 177 // The Main Drivers
 178 //===----------------------------------------------------------------------===//
 179
 180 /// dump - Print the contents of this headermap to stderr.
 181 void HeaderMap::dump() const {
 182   const HMapHeader &Hdr = getHeader();
 183   unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
 184
 185   fprintf(stderr, "Header Map %s:\n  %d buckets, %d entries\n",
 186           getFileName(), NumBuckets,
 187           getEndianAdjustedWord(Hdr.NumEntries));
 188
 189   for (unsigned i = 0; i != NumBuckets; ++i) {
 190     HMapBucket B = getBucket(i);
 191     if (B.Key == HMAP_EmptyBucketKey) continue;
 192
 193     const char *Key    = getString(B.Key);
 194     const char *Prefix = getString(B.Prefix);
 195     const char *Suffix = getString(B.Suffix);
 196     fprintf(stderr, "  %d. %s -> '%s' '%s'\n", i, Key, Prefix, Suffix);
 197   }
 198 }
 199
 200 /// LookupFile - Check to see if the specified relative filename is located in
 201 /// this HeaderMap.  If so, open it and return its FileEntry.
 202 const FileEntry *HeaderMap::LookupFile(
 203     StringRef Filename, FileManager &FM) const {
 204   const HMapHeader &Hdr = getHeader();
 205   unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
 206
 207   // If the number of buckets is not a power of two, the headermap is corrupt.
 208   // Don't probe infinitely.
 209   if (NumBuckets & (NumBuckets-1))
 210     return 0;
 211
 212   // Linearly probe the hash table.
 213   for (unsigned Bucket = HashHMapKey(Filename);; ++Bucket) {
 214     HMapBucket B = getBucket(Bucket & (NumBuckets-1));
 215     if (B.Key == HMAP_EmptyBucketKey) return 0; // Hash miss.
 216
 217     // See if the key matches.  If not, probe on.
 218     if (!Filename.equals_lower(getString(B.Key)))
 219       continue;
 220
 221     // If so, we have a match in the hash table.  Construct the destination
 222     // path.
 223     SmallString<1024> DestPath;
 224     DestPath += getString(B.Prefix);
 225     DestPath += getString(B.Suffix);
 226     return FM.getFile(DestPath.str());
 227   }
 228 }