/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // This file implements the HeaderMap interface. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #include "clang/Lex/HeaderMap.h" |
14 | | #include "clang/Lex/HeaderMapTypes.h" |
15 | | #include "clang/Basic/CharInfo.h" |
16 | | #include "clang/Basic/FileManager.h" |
17 | | #include "llvm/ADT/SmallString.h" |
18 | | #include "llvm/Support/Compiler.h" |
19 | | #include "llvm/Support/DataTypes.h" |
20 | | #include "llvm/Support/MathExtras.h" |
21 | | #include "llvm/Support/MemoryBuffer.h" |
22 | | #include "llvm/Support/SwapByteOrder.h" |
23 | | #include "llvm/Support/Debug.h" |
24 | | #include <cstring> |
25 | | #include <memory> |
26 | | using namespace clang; |
27 | | |
28 | | /// HashHMapKey - This is the 'well known' hash function required by the file |
29 | | /// format, used to look up keys in the hash table. The hash table uses simple |
30 | | /// linear probing based on this function. |
31 | 61 | static inline unsigned HashHMapKey(StringRef Str) { |
32 | 61 | unsigned Result = 0; |
33 | 61 | const char *S = Str.begin(), *End = Str.end(); |
34 | 61 | |
35 | 655 | for (; S != End; S++594 ) |
36 | 594 | Result += toLowercase(*S) * 13; |
37 | 61 | return Result; |
38 | 61 | } |
39 | | |
40 | | |
41 | | |
42 | | //===----------------------------------------------------------------------===// |
43 | | // Verification and Construction |
44 | | //===----------------------------------------------------------------------===// |
45 | | |
46 | | /// HeaderMap::Create - This attempts to load the specified file as a header |
47 | | /// map. If it doesn't look like a HeaderMap, it gives up and returns null. |
48 | | /// If it looks like a HeaderMap but is obviously corrupted, it puts a reason |
49 | | /// into the string error argument and returns null. |
50 | | std::unique_ptr<HeaderMap> HeaderMap::Create(const FileEntry *FE, |
51 | 34 | FileManager &FM) { |
52 | 34 | // If the file is too small to be a header map, ignore it. |
53 | 34 | unsigned FileSize = FE->getSize(); |
54 | 34 | if (FileSize <= sizeof(HMapHeader)) return nullptr4 ; |
55 | 30 | |
56 | 30 | auto FileBuffer = FM.getBufferForFile(FE); |
57 | 30 | if (!FileBuffer || !*FileBuffer) |
58 | 0 | return nullptr; |
59 | 30 | bool NeedsByteSwap; |
60 | 30 | if (!checkHeader(**FileBuffer, NeedsByteSwap)) |
61 | 0 | return nullptr; |
62 | 30 | return std::unique_ptr<HeaderMap>(new HeaderMap(std::move(*FileBuffer), NeedsByteSwap)); |
63 | 30 | } |
64 | | |
65 | | bool HeaderMapImpl::checkHeader(const llvm::MemoryBuffer &File, |
66 | 43 | bool &NeedsByteSwap) { |
67 | 43 | if (File.getBufferSize() <= sizeof(HMapHeader)) |
68 | 2 | return false; |
69 | 41 | const char *FileStart = File.getBufferStart(); |
70 | 41 | |
71 | 41 | // We know the file is at least as big as the header, check it now. |
72 | 41 | const HMapHeader *Header = reinterpret_cast<const HMapHeader*>(FileStart); |
73 | 41 | |
74 | 41 | // Sniff it to see if it's a headermap by checking the magic number and |
75 | 41 | // version. |
76 | 41 | if (Header->Magic == HMAP_HeaderMagicNumber && |
77 | 41 | Header->Version == HMAP_HeaderVersion39 ) |
78 | 38 | NeedsByteSwap = false; |
79 | 3 | else if (Header->Magic == llvm::ByteSwap_32(HMAP_HeaderMagicNumber) && |
80 | 3 | Header->Version == llvm::ByteSwap_16(HMAP_HeaderVersion)1 ) |
81 | 1 | NeedsByteSwap = true; // Mixed endianness headermap. |
82 | 2 | else |
83 | 2 | return false; // Not a header map. |
84 | 39 | |
85 | 39 | if (Header->Reserved != 0) |
86 | 1 | return false; |
87 | 38 | |
88 | 38 | // Check the number of buckets. It should be a power of two, and there |
89 | 38 | // should be enough space in the file for all of them. |
90 | 38 | uint32_t NumBuckets = NeedsByteSwap |
91 | 38 | ? llvm::sys::getSwappedBytes(Header->NumBuckets)1 |
92 | 38 | : Header->NumBuckets37 ; |
93 | 38 | if (!llvm::isPowerOf2_32(NumBuckets)) |
94 | 2 | return false; |
95 | 36 | if (File.getBufferSize() < |
96 | 36 | sizeof(HMapHeader) + sizeof(HMapBucket) * NumBuckets) |
97 | 1 | return false; |
98 | 35 | |
99 | 35 | // Okay, everything looks good. |
100 | 35 | return true; |
101 | 35 | } |
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 | 371 | unsigned HeaderMapImpl::getEndianAdjustedWord(unsigned X) const { |
114 | 371 | if (!NeedsBSwap) return X; |
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 | 140 | const HMapHeader &HeaderMapImpl::getHeader() const { |
121 | 140 | // We know the file is at least as big as the header. Return it. |
122 | 140 | return *reinterpret_cast<const HMapHeader*>(FileBuffer->getBufferStart()); |
123 | 140 | } |
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 | 77 | HMapBucket HeaderMapImpl::getBucket(unsigned BucketNo) const { |
129 | 77 | assert(FileBuffer->getBufferSize() >= |
130 | 77 | sizeof(HMapHeader) + sizeof(HMapBucket) * BucketNo && |
131 | 77 | "Expected bucket to be in range"); |
132 | 77 | |
133 | 77 | HMapBucket Result; |
134 | 77 | Result.Key = HMAP_EmptyBucketKey; |
135 | 77 | |
136 | 77 | const HMapBucket *BucketArray = |
137 | 77 | reinterpret_cast<const HMapBucket*>(FileBuffer->getBufferStart() + |
138 | 77 | sizeof(HMapHeader)); |
139 | 77 | const HMapBucket *BucketPtr = BucketArray+BucketNo; |
140 | 77 | |
141 | 77 | // Load the values, bswapping as needed. |
142 | 77 | Result.Key = getEndianAdjustedWord(BucketPtr->Key); |
143 | 77 | Result.Prefix = getEndianAdjustedWord(BucketPtr->Prefix); |
144 | 77 | Result.Suffix = getEndianAdjustedWord(BucketPtr->Suffix); |
145 | 77 | return Result; |
146 | 77 | } |
147 | | |
148 | 79 | Optional<StringRef> HeaderMapImpl::getString(unsigned StrTabIdx) const { |
149 | 79 | // Add the start of the string table to the idx. |
150 | 79 | StrTabIdx += getEndianAdjustedWord(getHeader().StringsOffset); |
151 | 79 | |
152 | 79 | // Check for invalid index. |
153 | 79 | if (StrTabIdx >= FileBuffer->getBufferSize()) |
154 | 0 | return None; |
155 | 79 | |
156 | 79 | const char *Data = FileBuffer->getBufferStart() + StrTabIdx; |
157 | 79 | unsigned MaxLen = FileBuffer->getBufferSize() - StrTabIdx; |
158 | 79 | unsigned Len = strnlen(Data, MaxLen); |
159 | 79 | |
160 | 79 | // Check whether the buffer is null-terminated. |
161 | 79 | if (Len == MaxLen && Data[Len - 1]2 ) |
162 | 2 | return None; |
163 | 77 | |
164 | 77 | return StringRef(Data, Len); |
165 | 77 | } |
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 != NumBuckets; ++i) { |
186 | 0 | HMapBucket B = getBucket(i); |
187 | 0 | if (B.Key == HMAP_EmptyBucketKey) continue; |
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 | 18 | StringRef Filename, FileManager &FM) const { |
201 | 18 | |
202 | 18 | SmallString<1024> Path; |
203 | 18 | StringRef Dest = HeaderMapImpl::lookupFilename(Filename, Path); |
204 | 18 | if (Dest.empty()) |
205 | 18 | return nullptr; |
206 | 0 | |
207 | 0 | return FM.getFile(Dest); |
208 | 0 | } |
209 | | |
210 | | StringRef HeaderMapImpl::lookupFilename(StringRef Filename, |
211 | 61 | SmallVectorImpl<char> &DestPath) const { |
212 | 61 | const HMapHeader &Hdr = getHeader(); |
213 | 61 | unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); |
214 | 61 | |
215 | 61 | // Don't probe infinitely. This should be checked before constructing. |
216 | 61 | assert(llvm::isPowerOf2_32(NumBuckets) && "Expected power of 2"); |
217 | 61 | |
218 | 61 | // Linearly probe the hash table. |
219 | 77 | for (unsigned Bucket = HashHMapKey(Filename);; ++Bucket16 ) { |
220 | 77 | HMapBucket B = getBucket(Bucket & (NumBuckets-1)); |
221 | 77 | if (B.Key == HMAP_EmptyBucketKey) return StringRef()40 ; // Hash miss. |
222 | 37 | |
223 | 37 | // See if the key matches. If not, probe on. |
224 | 37 | Optional<StringRef> Key = getString(B.Key); |
225 | 37 | if (LLVM_UNLIKELY(!Key)) |
226 | 37 | continue0 ; |
227 | 37 | if (!Filename.equals_lower(*Key)) |
228 | 16 | continue; |
229 | 21 | |
230 | 21 | // If so, we have a match in the hash table. Construct the destination |
231 | 21 | // path. |
232 | 21 | Optional<StringRef> Prefix = getString(B.Prefix); |
233 | 21 | Optional<StringRef> Suffix = getString(B.Suffix); |
234 | 21 | |
235 | 21 | DestPath.clear(); |
236 | 21 | if (LLVM_LIKELY(Prefix && Suffix)) { |
237 | 19 | DestPath.append(Prefix->begin(), Prefix->end()); |
238 | 19 | DestPath.append(Suffix->begin(), Suffix->end()); |
239 | 19 | } |
240 | 21 | return StringRef(DestPath.begin(), DestPath.size()); |
241 | 21 | } |
242 | 61 | } |