1193326Sed//===--- HeaderMap.cpp - A file that acts like dir of symlinks ------------===// 2193326Sed// 3193326Sed// The LLVM Compiler Infrastructure 4193326Sed// 5193326Sed// This file is distributed under the University of Illinois Open Source 6193326Sed// License. See LICENSE.TXT for details. 7193326Sed// 8193326Sed//===----------------------------------------------------------------------===// 9193326Sed// 10193326Sed// This file implements the HeaderMap interface. 11193326Sed// 12193326Sed//===----------------------------------------------------------------------===// 13193326Sed 14193326Sed#include "clang/Lex/HeaderMap.h" 15249423Sdim#include "clang/Basic/CharInfo.h" 16193326Sed#include "clang/Basic/FileManager.h" 17193326Sed#include "llvm/ADT/OwningPtr.h" 18193326Sed#include "llvm/ADT/SmallString.h" 19218893Sdim#include "llvm/Support/DataTypes.h" 20193326Sed#include "llvm/Support/MathExtras.h" 21193326Sed#include "llvm/Support/MemoryBuffer.h" 22193326Sed#include <cstdio> 23193326Sedusing namespace clang; 24193326Sed 25193326Sed//===----------------------------------------------------------------------===// 26193326Sed// Data Structures and Manifest Constants 27193326Sed//===----------------------------------------------------------------------===// 28193326Sed 29193326Sedenum { 30193326Sed HMAP_HeaderMagicNumber = ('h' << 24) | ('m' << 16) | ('a' << 8) | 'p', 31193326Sed HMAP_HeaderVersion = 1, 32198092Srdivacky 33198092Srdivacky HMAP_EmptyBucketKey = 0 34193326Sed}; 35193326Sed 36193326Sednamespace clang { 37193326Sedstruct HMapBucket { 38193326Sed uint32_t Key; // Offset (into strings) of key. 39193326Sed 40193326Sed uint32_t Prefix; // Offset (into strings) of value prefix. 41193326Sed uint32_t Suffix; // Offset (into strings) of value suffix. 42193326Sed}; 43193326Sed 44193326Sedstruct HMapHeader { 45193326Sed uint32_t Magic; // Magic word, also indicates byte order. 46193326Sed uint16_t Version; // Version number -- currently 1. 47193326Sed uint16_t Reserved; // Reserved for future use - zero for now. 48193326Sed uint32_t StringsOffset; // Offset to start of string pool. 49193326Sed uint32_t NumEntries; // Number of entries in the string table. 50193326Sed uint32_t NumBuckets; // Number of buckets (always a power of 2). 51193326Sed uint32_t MaxValueLength; // Length of longest result path (excluding nul). 52193326Sed // An array of 'NumBuckets' HMapBucket objects follows this header. 53193326Sed // Strings follow the buckets, at StringsOffset. 54193326Sed}; 55193326Sed} // end namespace clang. 56193326Sed 57193326Sed/// HashHMapKey - This is the 'well known' hash function required by the file 58193326Sed/// format, used to look up keys in the hash table. The hash table uses simple 59193326Sed/// linear probing based on this function. 60226633Sdimstatic inline unsigned HashHMapKey(StringRef Str) { 61193326Sed unsigned Result = 0; 62202379Srdivacky const char *S = Str.begin(), *End = Str.end(); 63198092Srdivacky 64193326Sed for (; S != End; S++) 65249423Sdim Result += toLowercase(*S) * 13; 66193326Sed return Result; 67193326Sed} 68193326Sed 69193326Sed 70193326Sed 71193326Sed//===----------------------------------------------------------------------===// 72193326Sed// Verification and Construction 73193326Sed//===----------------------------------------------------------------------===// 74193326Sed 75193326Sed/// HeaderMap::Create - This attempts to load the specified file as a header 76193326Sed/// map. If it doesn't look like a HeaderMap, it gives up and returns null. 77193326Sed/// If it looks like a HeaderMap but is obviously corrupted, it puts a reason 78193326Sed/// into the string error argument and returns null. 79218893Sdimconst HeaderMap *HeaderMap::Create(const FileEntry *FE, FileManager &FM) { 80193326Sed // If the file is too small to be a header map, ignore it. 81193326Sed unsigned FileSize = FE->getSize(); 82193326Sed if (FileSize <= sizeof(HMapHeader)) return 0; 83198092Srdivacky 84234353Sdim OwningPtr<const llvm::MemoryBuffer> FileBuffer(FM.getBufferForFile(FE)); 85263508Sdim if (!FileBuffer) return 0; // Unreadable file? 86193326Sed const char *FileStart = FileBuffer->getBufferStart(); 87193326Sed 88193326Sed // We know the file is at least as big as the header, check it now. 89193326Sed const HMapHeader *Header = reinterpret_cast<const HMapHeader*>(FileStart); 90198092Srdivacky 91193326Sed // Sniff it to see if it's a headermap by checking the magic number and 92193326Sed // version. 93193326Sed bool NeedsByteSwap; 94198092Srdivacky if (Header->Magic == HMAP_HeaderMagicNumber && 95193326Sed Header->Version == HMAP_HeaderVersion) 96193326Sed NeedsByteSwap = false; 97193326Sed else if (Header->Magic == llvm::ByteSwap_32(HMAP_HeaderMagicNumber) && 98193326Sed Header->Version == llvm::ByteSwap_16(HMAP_HeaderVersion)) 99193326Sed NeedsByteSwap = true; // Mixed endianness headermap. 100198092Srdivacky else 101193326Sed return 0; // Not a header map. 102198092Srdivacky 103193326Sed if (Header->Reserved != 0) return 0; 104193326Sed 105193326Sed // Okay, everything looks good, create the header map. 106193326Sed return new HeaderMap(FileBuffer.take(), NeedsByteSwap); 107193326Sed} 108193326Sed 109193326SedHeaderMap::~HeaderMap() { 110193326Sed delete FileBuffer; 111193326Sed} 112193326Sed 113193326Sed//===----------------------------------------------------------------------===// 114193326Sed// Utility Methods 115193326Sed//===----------------------------------------------------------------------===// 116193326Sed 117193326Sed 118193326Sed/// getFileName - Return the filename of the headermap. 119193326Sedconst char *HeaderMap::getFileName() const { 120193326Sed return FileBuffer->getBufferIdentifier(); 121193326Sed} 122193326Sed 123193326Sedunsigned HeaderMap::getEndianAdjustedWord(unsigned X) const { 124193326Sed if (!NeedsBSwap) return X; 125193326Sed return llvm::ByteSwap_32(X); 126193326Sed} 127193326Sed 128193326Sed/// getHeader - Return a reference to the file header, in unbyte-swapped form. 129193326Sed/// This method cannot fail. 130193326Sedconst HMapHeader &HeaderMap::getHeader() const { 131193326Sed // We know the file is at least as big as the header. Return it. 132193326Sed return *reinterpret_cast<const HMapHeader*>(FileBuffer->getBufferStart()); 133193326Sed} 134193326Sed 135193326Sed/// getBucket - Return the specified hash table bucket from the header map, 136193326Sed/// bswap'ing its fields as appropriate. If the bucket number is not valid, 137193326Sed/// this return a bucket with an empty key (0). 138193326SedHMapBucket HeaderMap::getBucket(unsigned BucketNo) const { 139193326Sed HMapBucket Result; 140193326Sed Result.Key = HMAP_EmptyBucketKey; 141198092Srdivacky 142198092Srdivacky const HMapBucket *BucketArray = 143193326Sed reinterpret_cast<const HMapBucket*>(FileBuffer->getBufferStart() + 144193326Sed sizeof(HMapHeader)); 145198092Srdivacky 146193326Sed const HMapBucket *BucketPtr = BucketArray+BucketNo; 147243830Sdim if ((const char*)(BucketPtr+1) > FileBuffer->getBufferEnd()) { 148193326Sed Result.Prefix = 0; 149193326Sed Result.Suffix = 0; 150193326Sed return Result; // Invalid buffer, corrupt hmap. 151193326Sed } 152193326Sed 153193326Sed // Otherwise, the bucket is valid. Load the values, bswapping as needed. 154193326Sed Result.Key = getEndianAdjustedWord(BucketPtr->Key); 155193326Sed Result.Prefix = getEndianAdjustedWord(BucketPtr->Prefix); 156193326Sed Result.Suffix = getEndianAdjustedWord(BucketPtr->Suffix); 157193326Sed return Result; 158193326Sed} 159193326Sed 160193326Sed/// getString - Look up the specified string in the string table. If the string 161193326Sed/// index is not valid, it returns an empty string. 162193326Sedconst char *HeaderMap::getString(unsigned StrTabIdx) const { 163193326Sed // Add the start of the string table to the idx. 164193326Sed StrTabIdx += getEndianAdjustedWord(getHeader().StringsOffset); 165198092Srdivacky 166193326Sed // Check for invalid index. 167193326Sed if (StrTabIdx >= FileBuffer->getBufferSize()) 168193326Sed return 0; 169198092Srdivacky 170193326Sed // Otherwise, we have a valid pointer into the file. Just return it. We know 171193326Sed // that the "string" can not overrun the end of the file, because the buffer 172193326Sed // is nul terminated by virtue of being a MemoryBuffer. 173193326Sed return FileBuffer->getBufferStart()+StrTabIdx; 174193326Sed} 175193326Sed 176193326Sed//===----------------------------------------------------------------------===// 177193326Sed// The Main Drivers 178193326Sed//===----------------------------------------------------------------------===// 179193326Sed 180193326Sed/// dump - Print the contents of this headermap to stderr. 181193326Sedvoid HeaderMap::dump() const { 182193326Sed const HMapHeader &Hdr = getHeader(); 183193326Sed unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); 184198092Srdivacky 185198092Srdivacky fprintf(stderr, "Header Map %s:\n %d buckets, %d entries\n", 186193326Sed getFileName(), NumBuckets, 187193326Sed getEndianAdjustedWord(Hdr.NumEntries)); 188198092Srdivacky 189193326Sed for (unsigned i = 0; i != NumBuckets; ++i) { 190193326Sed HMapBucket B = getBucket(i); 191193326Sed if (B.Key == HMAP_EmptyBucketKey) continue; 192198092Srdivacky 193193326Sed const char *Key = getString(B.Key); 194193326Sed const char *Prefix = getString(B.Prefix); 195193326Sed const char *Suffix = getString(B.Suffix); 196193326Sed fprintf(stderr, " %d. %s -> '%s' '%s'\n", i, Key, Prefix, Suffix); 197193326Sed } 198193326Sed} 199193326Sed 200193326Sed/// LookupFile - Check to see if the specified relative filename is located in 201193326Sed/// this HeaderMap. If so, open it and return its FileEntry. 202221345Sdimconst FileEntry *HeaderMap::LookupFile( 203226633Sdim StringRef Filename, FileManager &FM) const { 204193326Sed const HMapHeader &Hdr = getHeader(); 205193326Sed unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); 206193326Sed 207193326Sed // If the number of buckets is not a power of two, the headermap is corrupt. 208193326Sed // Don't probe infinitely. 209193326Sed if (NumBuckets & (NumBuckets-1)) 210193326Sed return 0; 211198092Srdivacky 212193326Sed // Linearly probe the hash table. 213202379Srdivacky for (unsigned Bucket = HashHMapKey(Filename);; ++Bucket) { 214193326Sed HMapBucket B = getBucket(Bucket & (NumBuckets-1)); 215193326Sed if (B.Key == HMAP_EmptyBucketKey) return 0; // Hash miss. 216198092Srdivacky 217193326Sed // See if the key matches. If not, probe on. 218202379Srdivacky if (!Filename.equals_lower(getString(B.Key))) 219193326Sed continue; 220198092Srdivacky 221193326Sed // If so, we have a match in the hash table. Construct the destination 222193326Sed // path. 223234353Sdim SmallString<1024> DestPath; 224193326Sed DestPath += getString(B.Prefix); 225193326Sed DestPath += getString(B.Suffix); 226218893Sdim return FM.getFile(DestPath.str()); 227193326Sed } 228193326Sed} 229