blob: 0b75af54d1b06a8ae0a21728a755478938d6ccc9 [file] [log] [blame]
Chris Lattner0f441ab2007-12-17 08:22:46 +00001//===--- HeaderMap.cpp - A file that acts like dir of symlinks ------------===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner0bc735f2007-12-29 19:59:25 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Chris Lattner0f441ab2007-12-17 08:22:46 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the HeaderMap interface.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Lex/HeaderMap.h"
Chris Lattner1bfd4a62007-12-17 18:34:53 +000015#include "clang/Basic/FileManager.h"
Ted Kremenekee533642007-12-20 19:47:16 +000016#include "llvm/ADT/OwningPtr.h"
Chris Lattner5fb125c2007-12-17 21:38:04 +000017#include "llvm/ADT/SmallString.h"
Chris Lattner1bfd4a62007-12-17 18:34:53 +000018#include "llvm/Support/DataTypes.h"
19#include "llvm/Support/MathExtras.h"
20#include "llvm/Support/MemoryBuffer.h"
Chris Lattner0f441ab2007-12-17 08:22:46 +000021using namespace clang;
22
Chris Lattner1adbf632007-12-17 21:06:11 +000023//===----------------------------------------------------------------------===//
24// Data Structures and Manifest Constants
25//===----------------------------------------------------------------------===//
26
Chris Lattner1bfd4a62007-12-17 18:34:53 +000027enum {
Chris Lattner1adbf632007-12-17 21:06:11 +000028 HMAP_HeaderMagicNumber = ('h' << 24) | ('m' << 16) | ('a' << 8) | 'p',
29 HMAP_HeaderVersion = 1,
30
31 HMAP_EmptyBucketKey = 0
32};
33
34namespace clang {
35struct HMapBucket {
36 uint32_t Key; // Offset (into strings) of key.
37
38 uint32_t Prefix; // Offset (into strings) of value prefix.
39 uint32_t Suffix; // Offset (into strings) of value suffix.
Chris Lattner1bfd4a62007-12-17 18:34:53 +000040};
41
42struct HMapHeader {
43 uint32_t Magic; // Magic word, also indicates byte order.
44 uint16_t Version; // Version number -- currently 1.
45 uint16_t Reserved; // Reserved for future use - zero for now.
46 uint32_t StringsOffset; // Offset to start of string pool.
Chris Lattner1adbf632007-12-17 21:06:11 +000047 uint32_t NumEntries; // Number of entries in the string table.
48 uint32_t NumBuckets; // Number of buckets (always a power of 2).
Chris Lattner1bfd4a62007-12-17 18:34:53 +000049 uint32_t MaxValueLength; // Length of longest result path (excluding nul).
Chris Lattner1adbf632007-12-17 21:06:11 +000050 // An array of 'NumBuckets' HMapBucket objects follows this header.
Chris Lattner1bfd4a62007-12-17 18:34:53 +000051 // Strings follow the buckets, at StringsOffset.
52};
Chris Lattner1adbf632007-12-17 21:06:11 +000053} // end namespace clang.
Chris Lattner1bfd4a62007-12-17 18:34:53 +000054
Chris Lattner5fb125c2007-12-17 21:38:04 +000055/// HashHMapKey - This is the 'well known' hash function required by the file
56/// format, used to look up keys in the hash table. The hash table uses simple
57/// linear probing based on this function.
58static inline unsigned HashHMapKey(const char *S, const char *End) {
59 unsigned Result = 0;
60
61 for (; S != End; S++)
62 Result += tolower(*S) * 13;
63 return Result;
64}
65
66
67
Chris Lattner1adbf632007-12-17 21:06:11 +000068//===----------------------------------------------------------------------===//
69// Verification and Construction
70//===----------------------------------------------------------------------===//
Chris Lattner1bfd4a62007-12-17 18:34:53 +000071
72/// HeaderMap::Create - This attempts to load the specified file as a header
73/// map. If it doesn't look like a HeaderMap, it gives up and returns null.
74/// If it looks like a HeaderMap but is obviously corrupted, it puts a reason
75/// into the string error argument and returns null.
76const HeaderMap *HeaderMap::Create(const FileEntry *FE) {
77 // If the file is too small to be a header map, ignore it.
78 unsigned FileSize = FE->getSize();
79 if (FileSize <= sizeof(HMapHeader)) return 0;
80
Ted Kremenekee533642007-12-20 19:47:16 +000081 llvm::OwningPtr<const llvm::MemoryBuffer> FileBuffer(
Chris Lattner35de5122008-04-01 18:04:30 +000082 llvm::MemoryBuffer::getFile(FE->getName(), 0, FE->getSize()));
Chris Lattner98751312007-12-17 18:44:09 +000083 if (FileBuffer == 0) return 0; // Unreadable file?
84 const char *FileStart = FileBuffer->getBufferStart();
Chris Lattner1bfd4a62007-12-17 18:34:53 +000085
86 // We know the file is at least as big as the header, check it now.
87 const HMapHeader *Header = reinterpret_cast<const HMapHeader*>(FileStart);
88
Chris Lattnerba832652007-12-17 18:59:44 +000089 // Sniff it to see if it's a headermap by checking the magic number and
90 // version.
Chris Lattner1bfd4a62007-12-17 18:34:53 +000091 bool NeedsByteSwap;
Chris Lattner1adbf632007-12-17 21:06:11 +000092 if (Header->Magic == HMAP_HeaderMagicNumber &&
93 Header->Version == HMAP_HeaderVersion)
Chris Lattner1bfd4a62007-12-17 18:34:53 +000094 NeedsByteSwap = false;
Chris Lattner1adbf632007-12-17 21:06:11 +000095 else if (Header->Magic == llvm::ByteSwap_32(HMAP_HeaderMagicNumber) &&
96 Header->Version == llvm::ByteSwap_16(HMAP_HeaderVersion))
Chris Lattner1bfd4a62007-12-17 18:34:53 +000097 NeedsByteSwap = true; // Mixed endianness headermap.
98 else
99 return 0; // Not a header map.
Chris Lattnerba832652007-12-17 18:59:44 +0000100
101 if (Header->Reserved != 0) return 0;
Chris Lattner98751312007-12-17 18:44:09 +0000102
103 // Okay, everything looks good, create the header map.
Chris Lattnerba832652007-12-17 18:59:44 +0000104 return new HeaderMap(FileBuffer.take(), NeedsByteSwap);
Chris Lattner98751312007-12-17 18:44:09 +0000105}
106
107HeaderMap::~HeaderMap() {
108 delete FileBuffer;
109}
110
Chris Lattner1adbf632007-12-17 21:06:11 +0000111//===----------------------------------------------------------------------===//
112// Utility Methods
113//===----------------------------------------------------------------------===//
114
Chris Lattner98751312007-12-17 18:44:09 +0000115
116/// getFileName - Return the filename of the headermap.
117const char *HeaderMap::getFileName() const {
118 return FileBuffer->getBufferIdentifier();
Chris Lattner0f441ab2007-12-17 08:22:46 +0000119}
120
Chris Lattner1adbf632007-12-17 21:06:11 +0000121unsigned HeaderMap::getEndianAdjustedWord(unsigned X) const {
122 if (!NeedsBSwap) return X;
123 return llvm::ByteSwap_32(X);
124}
125
126/// getHeader - Return a reference to the file header, in unbyte-swapped form.
127/// This method cannot fail.
128const HMapHeader &HeaderMap::getHeader() const {
129 // We know the file is at least as big as the header. Return it.
130 return *reinterpret_cast<const HMapHeader*>(FileBuffer->getBufferStart());
131}
132
133/// getBucket - Return the specified hash table bucket from the header map,
134/// bswap'ing its fields as appropriate. If the bucket number is not valid,
135/// this return a bucket with an empty key (0).
136HMapBucket HeaderMap::getBucket(unsigned BucketNo) const {
137 HMapBucket Result;
138 Result.Key = HMAP_EmptyBucketKey;
139
140 const HMapBucket *BucketArray =
141 reinterpret_cast<const HMapBucket*>(FileBuffer->getBufferStart() +
142 sizeof(HMapHeader));
143
144 const HMapBucket *BucketPtr = BucketArray+BucketNo;
Ted Kremenek8173dba2008-10-28 00:18:42 +0000145 if ((char*)(BucketPtr+1) > FileBuffer->getBufferEnd()) {
146 Result.Prefix = 0;
147 Result.Suffix = 0;
Chris Lattner1adbf632007-12-17 21:06:11 +0000148 return Result; // Invalid buffer, corrupt hmap.
Ted Kremenek8173dba2008-10-28 00:18:42 +0000149 }
Chris Lattner1adbf632007-12-17 21:06:11 +0000150
151 // Otherwise, the bucket is valid. Load the values, bswapping as needed.
152 Result.Key = getEndianAdjustedWord(BucketPtr->Key);
153 Result.Prefix = getEndianAdjustedWord(BucketPtr->Prefix);
154 Result.Suffix = getEndianAdjustedWord(BucketPtr->Suffix);
155 return Result;
156}
157
158/// getString - Look up the specified string in the string table. If the string
159/// index is not valid, it returns an empty string.
160const char *HeaderMap::getString(unsigned StrTabIdx) const {
161 // Add the start of the string table to the idx.
162 StrTabIdx += getEndianAdjustedWord(getHeader().StringsOffset);
163
164 // Check for invalid index.
165 if (StrTabIdx >= FileBuffer->getBufferSize())
166 return 0;
167
168 // Otherwise, we have a valid pointer into the file. Just return it. We know
169 // that the "string" can not overrun the end of the file, because the buffer
170 // is nul terminated by virtue of being a MemoryBuffer.
171 return FileBuffer->getBufferStart()+StrTabIdx;
172}
173
Chris Lattner5fb125c2007-12-17 21:38:04 +0000174/// StringsEqualWithoutCase - Compare the specified two strings for case-
175/// insensitive equality, returning true if they are equal. Both strings are
176/// known to have the same length.
177static bool StringsEqualWithoutCase(const char *S1, const char *S2,
178 unsigned Len) {
179 for (; Len; ++S1, ++S2, --Len)
180 if (tolower(*S1) != tolower(*S2))
181 return false;
182 return true;
183}
184
Chris Lattner1adbf632007-12-17 21:06:11 +0000185//===----------------------------------------------------------------------===//
186// The Main Drivers
187//===----------------------------------------------------------------------===//
188
189/// dump - Print the contents of this headermap to stderr.
190void HeaderMap::dump() const {
191 const HMapHeader &Hdr = getHeader();
192 unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
193
194 fprintf(stderr, "Header Map %s:\n %d buckets, %d entries\n",
195 getFileName(), NumBuckets,
196 getEndianAdjustedWord(Hdr.NumEntries));
197
198 for (unsigned i = 0; i != NumBuckets; ++i) {
199 HMapBucket B = getBucket(i);
200 if (B.Key == HMAP_EmptyBucketKey) continue;
201
202 const char *Key = getString(B.Key);
203 const char *Prefix = getString(B.Prefix);
204 const char *Suffix = getString(B.Suffix);
205 fprintf(stderr, " %d. %s -> '%s' '%s'\n", i, Key, Prefix, Suffix);
206 }
207}
208
Chris Lattner0f441ab2007-12-17 08:22:46 +0000209/// LookupFile - Check to see if the specified relative filename is located in
210/// this HeaderMap. If so, open it and return its FileEntry.
211const FileEntry *HeaderMap::LookupFile(const char *FilenameStart,
212 const char *FilenameEnd,
213 FileManager &FM) const {
Chris Lattner5fb125c2007-12-17 21:38:04 +0000214 const HMapHeader &Hdr = getHeader();
215 unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
216
217 // If the number of buckets is not a power of two, the headermap is corrupt.
218 // Don't probe infinitely.
219 if (NumBuckets & (NumBuckets-1))
220 return 0;
221
222 // Linearly probe the hash table.
223 for (unsigned Bucket = HashHMapKey(FilenameStart, FilenameEnd);; ++Bucket) {
224 HMapBucket B = getBucket(Bucket & (NumBuckets-1));
225 if (B.Key == HMAP_EmptyBucketKey) return 0; // Hash miss.
226
227 // See if the key matches. If not, probe on.
228 const char *Key = getString(B.Key);
229 unsigned BucketKeyLen = strlen(Key);
230 if (BucketKeyLen != unsigned(FilenameEnd-FilenameStart))
231 continue;
232
233 // See if the actual strings equal.
234 if (!StringsEqualWithoutCase(FilenameStart, Key, BucketKeyLen))
235 continue;
236
237 // If so, we have a match in the hash table. Construct the destination
238 // path.
239 llvm::SmallString<1024> DestPath;
240 DestPath += getString(B.Prefix);
241 DestPath += getString(B.Suffix);
242 return FM.getFile(DestPath.begin(), DestPath.end());
243 }
Chris Lattner0f441ab2007-12-17 08:22:46 +0000244}