/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/clang/lib/Lex/HeaderMap.cpp
Line | Count | Source (jump to first uncovered line) |
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/Lex/HeaderMapTypes.h" |
16 | | #include "clang/Basic/CharInfo.h" |
17 | | #include "clang/Basic/FileManager.h" |
18 | | #include "llvm/ADT/SmallString.h" |
19 | | #include "llvm/Support/Compiler.h" |
20 | | #include "llvm/Support/DataTypes.h" |
21 | | #include "llvm/Support/MathExtras.h" |
22 | | #include "llvm/Support/MemoryBuffer.h" |
23 | | #include "llvm/Support/SwapByteOrder.h" |
24 | | #include "llvm/Support/Debug.h" |
25 | | #include <cstring> |
26 | | #include <memory> |
27 | | using namespace clang; |
28 | | |
29 | | /// HashHMapKey - This is the 'well known' hash function required by the file |
30 | | /// format, used to look up keys in the hash table. The hash table uses simple |
31 | | /// linear probing based on this function. |
32 | 15 | static inline unsigned HashHMapKey(StringRef Str) { |
33 | 15 | unsigned Result = 0; |
34 | 15 | const char *S = Str.begin(), *End = Str.end(); |
35 | 15 | |
36 | 150 | for (; S != End150 ; S++135 ) |
37 | 135 | Result += toLowercase(*S) * 13; |
38 | 15 | return Result; |
39 | 15 | } |
40 | | |
41 | | |
42 | | |
43 | | //===----------------------------------------------------------------------===// |
44 | | // Verification and Construction |
45 | | //===----------------------------------------------------------------------===// |
46 | | |
47 | | /// HeaderMap::Create - This attempts to load the specified file as a header |
48 | | /// map. If it doesn't look like a HeaderMap, it gives up and returns null. |
49 | | /// If it looks like a HeaderMap but is obviously corrupted, it puts a reason |
50 | | /// into the string error argument and returns null. |
51 | 10 | const HeaderMap *HeaderMap::Create(const FileEntry *FE, FileManager &FM) { |
52 | 10 | // If the file is too small to be a header map, ignore it. |
53 | 10 | unsigned FileSize = FE->getSize(); |
54 | 10 | if (FileSize <= sizeof(HMapHeader)10 ) return nullptr4 ; |
55 | 6 | |
56 | 6 | auto FileBuffer = FM.getBufferForFile(FE); |
57 | 6 | if (!FileBuffer || 6 !*FileBuffer6 ) |
58 | 0 | return nullptr; |
59 | 6 | bool NeedsByteSwap; |
60 | 6 | if (!checkHeader(**FileBuffer, NeedsByteSwap)) |
61 | 0 | return nullptr; |
62 | 6 | return new HeaderMap(std::move(*FileBuffer), NeedsByteSwap); |
63 | 6 | } |
64 | | |
65 | | bool HeaderMapImpl::checkHeader(const llvm::MemoryBuffer &File, |
66 | 19 | bool &NeedsByteSwap) { |
67 | 19 | if (File.getBufferSize() <= sizeof(HMapHeader)) |
68 | 2 | return false; |
69 | 17 | const char *FileStart = File.getBufferStart(); |
70 | 17 | |
71 | 17 | // We know the file is at least as big as the header, check it now. |
72 | 17 | const HMapHeader *Header = reinterpret_cast<const HMapHeader*>(FileStart); |
73 | 17 | |
74 | 17 | // Sniff it to see if it's a headermap by checking the magic number and |
75 | 17 | // version. |
76 | 17 | if (Header->Magic == HMAP_HeaderMagicNumber && |
77 | 15 | Header->Version == HMAP_HeaderVersion) |
78 | 14 | NeedsByteSwap = false; |
79 | 3 | else if (3 Header->Magic == llvm::ByteSwap_32(HMAP_HeaderMagicNumber) && |
80 | 1 | Header->Version == llvm::ByteSwap_16(HMAP_HeaderVersion)) |
81 | 1 | NeedsByteSwap = true; // Mixed endianness headermap. |
82 | 3 | else |
83 | 2 | return false; // Not a header map. |
84 | 15 | |
85 | 15 | if (15 Header->Reserved != 015 ) |
86 | 1 | return false; |
87 | 14 | |
88 | 14 | // Check the number of buckets. It should be a power of two, and there |
89 | 14 | // should be enough space in the file for all of them. |
90 | 14 | uint32_t NumBuckets = NeedsByteSwap |
91 | 1 | ? llvm::sys::getSwappedBytes(Header->NumBuckets) |
92 | 13 | : Header->NumBuckets; |
93 | 14 | if (!llvm::isPowerOf2_32(NumBuckets)) |
94 | 2 | return false; |
95 | 12 | if (12 File.getBufferSize() < |
96 | 12 | sizeof(HMapHeader) + sizeof(HMapBucket) * NumBuckets) |
97 | 1 | return false; |
98 | 11 | |
99 | 11 | // Okay, everything looks good. |
100 | 11 | return true; |
101 | 11 | } |
102 | | |
103 | | //===----------------------------------------------------------------------===// |
104 | | // Utility Methods |
105 | | //===----------------------------------------------------------------------===// |
106 | | |
107 | | |
108 | | /// getFileName - Return the filename of the headermap. |
109 | 1 | StringRef HeaderMapImpl::getFileName() const { |
110 | 1 | return FileBuffer->getBufferIdentifier(); |
111 | 1 | } |
112 | | |
113 | 95 | unsigned HeaderMapImpl::getEndianAdjustedWord(unsigned X) const { |
114 | 95 | if (!NeedsBSwap95 ) return X95 ; |
115 | 0 | return llvm::ByteSwap_32(X); |
116 | 0 | } |
117 | | |
118 | | /// getHeader - Return a reference to the file header, in unbyte-swapped form. |
119 | | /// This method cannot fail. |
120 | 44 | const HMapHeader &HeaderMapImpl::getHeader() const { |
121 | 44 | // We know the file is at least as big as the header. Return it. |
122 | 44 | return *reinterpret_cast<const HMapHeader*>(FileBuffer->getBufferStart()); |
123 | 44 | } |
124 | | |
125 | | /// getBucket - Return the specified hash table bucket from the header map, |
126 | | /// bswap'ing its fields as appropriate. If the bucket number is not valid, |
127 | | /// this return a bucket with an empty key (0). |
128 | 17 | HMapBucket HeaderMapImpl::getBucket(unsigned BucketNo) const { |
129 | 17 | assert(FileBuffer->getBufferSize() >= |
130 | 17 | sizeof(HMapHeader) + sizeof(HMapBucket) * BucketNo && |
131 | 17 | "Expected bucket to be in range"); |
132 | 17 | |
133 | 17 | HMapBucket Result; |
134 | 17 | Result.Key = HMAP_EmptyBucketKey; |
135 | 17 | |
136 | 17 | const HMapBucket *BucketArray = |
137 | 17 | reinterpret_cast<const HMapBucket*>(FileBuffer->getBufferStart() + |
138 | 17 | sizeof(HMapHeader)); |
139 | 17 | const HMapBucket *BucketPtr = BucketArray+BucketNo; |
140 | 17 | |
141 | 17 | // Load the values, bswapping as needed. |
142 | 17 | Result.Key = getEndianAdjustedWord(BucketPtr->Key); |
143 | 17 | Result.Prefix = getEndianAdjustedWord(BucketPtr->Prefix); |
144 | 17 | Result.Suffix = getEndianAdjustedWord(BucketPtr->Suffix); |
145 | 17 | return Result; |
146 | 17 | } |
147 | | |
148 | 29 | Optional<StringRef> HeaderMapImpl::getString(unsigned StrTabIdx) const { |
149 | 29 | // Add the start of the string table to the idx. |
150 | 29 | StrTabIdx += getEndianAdjustedWord(getHeader().StringsOffset); |
151 | 29 | |
152 | 29 | // Check for invalid index. |
153 | 29 | if (StrTabIdx >= FileBuffer->getBufferSize()) |
154 | 0 | return None; |
155 | 29 | |
156 | 29 | const char *Data = FileBuffer->getBufferStart() + StrTabIdx; |
157 | 29 | unsigned MaxLen = FileBuffer->getBufferSize() - StrTabIdx; |
158 | 29 | unsigned Len = strnlen(Data, MaxLen); |
159 | 29 | |
160 | 29 | // Check whether the buffer is null-terminated. |
161 | 29 | if (Len == MaxLen && 29 Data[Len - 1]2 ) |
162 | 2 | return None; |
163 | 27 | |
164 | 27 | return StringRef(Data, Len); |
165 | 27 | } |
166 | | |
167 | | //===----------------------------------------------------------------------===// |
168 | | // The Main Drivers |
169 | | //===----------------------------------------------------------------------===// |
170 | | |
171 | | /// dump - Print the contents of this headermap to stderr. |
172 | 0 | LLVM_DUMP_METHOD void HeaderMapImpl::dump() const { |
173 | 0 | const HMapHeader &Hdr = getHeader(); |
174 | 0 | unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); |
175 | 0 |
|
176 | 0 | llvm::dbgs() << "Header Map " << getFileName() << ":\n " << NumBuckets |
177 | 0 | << ", " << getEndianAdjustedWord(Hdr.NumEntries) << "\n"; |
178 | 0 |
|
179 | 0 | auto getStringOrInvalid = [this](unsigned Id) -> StringRef { |
180 | 0 | if (Optional<StringRef> S = getString(Id)) |
181 | 0 | return *S; |
182 | 0 | return "<invalid>"; |
183 | 0 | }; |
184 | 0 |
|
185 | 0 | for (unsigned i = 0; i != NumBuckets0 ; ++i0 ) { |
186 | 0 | HMapBucket B = getBucket(i); |
187 | 0 | if (B.Key == HMAP_EmptyBucketKey0 ) continue0 ; |
188 | 0 |
|
189 | 0 | StringRef Key = getStringOrInvalid(B.Key); |
190 | 0 | StringRef Prefix = getStringOrInvalid(B.Prefix); |
191 | 0 | StringRef Suffix = getStringOrInvalid(B.Suffix); |
192 | 0 | llvm::dbgs() << " " << i << ". " << Key << " -> '" << Prefix << "' '" |
193 | 0 | << Suffix << "'\n"; |
194 | 0 | } |
195 | 0 | } |
196 | | |
197 | | /// LookupFile - Check to see if the specified relative filename is located in |
198 | | /// this HeaderMap. If so, open it and return its FileEntry. |
199 | | const FileEntry *HeaderMap::LookupFile( |
200 | 6 | StringRef Filename, FileManager &FM) const { |
201 | 6 | |
202 | 6 | SmallString<1024> Path; |
203 | 6 | StringRef Dest = HeaderMapImpl::lookupFilename(Filename, Path); |
204 | 6 | if (Dest.empty()) |
205 | 6 | return nullptr; |
206 | 0 |
|
207 | 0 | return FM.getFile(Dest); |
208 | 0 | } |
209 | | |
210 | | StringRef HeaderMapImpl::lookupFilename(StringRef Filename, |
211 | 15 | SmallVectorImpl<char> &DestPath) const { |
212 | 15 | const HMapHeader &Hdr = getHeader(); |
213 | 15 | unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); |
214 | 15 | |
215 | 15 | // Don't probe infinitely. This should be checked before constructing. |
216 | 15 | assert(llvm::isPowerOf2_32(NumBuckets) && "Expected power of 2"); |
217 | 15 | |
218 | 15 | // Linearly probe the hash table. |
219 | 15 | for (unsigned Bucket = HashHMapKey(Filename);; ++Bucket2 ) { |
220 | 17 | HMapBucket B = getBucket(Bucket & (NumBuckets-1)); |
221 | 17 | if (B.Key == HMAP_EmptyBucketKey17 ) return StringRef()6 ; // Hash miss. |
222 | 11 | |
223 | 11 | // See if the key matches. If not, probe on. |
224 | 11 | Optional<StringRef> Key = getString(B.Key); |
225 | 11 | if (LLVM_UNLIKELY(!Key)) |
226 | 0 | continue; |
227 | 11 | if (11 !Filename.equals_lower(*Key)11 ) |
228 | 2 | continue; |
229 | 9 | |
230 | 9 | // If so, we have a match in the hash table. Construct the destination |
231 | 9 | // path. |
232 | 9 | Optional<StringRef> Prefix = getString(B.Prefix); |
233 | 9 | Optional<StringRef> Suffix = getString(B.Suffix); |
234 | 9 | |
235 | 9 | DestPath.clear(); |
236 | 9 | if (LLVM_LIKELY9 (Prefix && Suffix)) { |
237 | 7 | DestPath.append(Prefix->begin(), Prefix->end()); |
238 | 7 | DestPath.append(Suffix->begin(), Suffix->end()); |
239 | 7 | } |
240 | 17 | return StringRef(DestPath.begin(), DestPath.size()); |
241 | 17 | } |
242 | 15 | } |