/Users/buildslave/jenkins/workspace/coverage/llvm-project/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 | | #include <optional> |
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 | 54 | static inline unsigned HashHMapKey(StringRef Str) { |
33 | 54 | unsigned Result = 0; |
34 | 54 | const char *S = Str.begin(), *End = Str.end(); |
35 | | |
36 | 586 | for (; S != End; S++532 ) |
37 | 532 | Result += toLowercase(*S) * 13; |
38 | 54 | return Result; |
39 | 54 | } |
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 | 51 | std::unique_ptr<HeaderMap> HeaderMap::Create(FileEntryRef FE, FileManager &FM) { |
52 | | // If the file is too small to be a header map, ignore it. |
53 | 51 | unsigned FileSize = FE.getSize(); |
54 | 51 | if (FileSize <= sizeof(HMapHeader)) return nullptr4 ; |
55 | | |
56 | 47 | auto FileBuffer = FM.getBufferForFile(FE); |
57 | 47 | if (!FileBuffer || !*FileBuffer) |
58 | 0 | return nullptr; |
59 | 47 | bool NeedsByteSwap; |
60 | 47 | if (!checkHeader(**FileBuffer, NeedsByteSwap)) |
61 | 0 | return nullptr; |
62 | 47 | return std::unique_ptr<HeaderMap>(new HeaderMap(std::move(*FileBuffer), NeedsByteSwap)); |
63 | 47 | } |
64 | | |
65 | | bool HeaderMapImpl::checkHeader(const llvm::MemoryBuffer &File, |
66 | 60 | bool &NeedsByteSwap) { |
67 | 60 | if (File.getBufferSize() <= sizeof(HMapHeader)) |
68 | 2 | return false; |
69 | 58 | const char *FileStart = File.getBufferStart(); |
70 | | |
71 | | // We know the file is at least as big as the header, check it now. |
72 | 58 | const HMapHeader *Header = reinterpret_cast<const HMapHeader*>(FileStart); |
73 | | |
74 | | // Sniff it to see if it's a headermap by checking the magic number and |
75 | | // version. |
76 | 58 | if (Header->Magic == HMAP_HeaderMagicNumber && |
77 | 58 | Header->Version == HMAP_HeaderVersion56 ) |
78 | 55 | NeedsByteSwap = false; |
79 | 3 | else if (Header->Magic == llvm::byteswap<uint32_t>(HMAP_HeaderMagicNumber) && |
80 | 3 | Header->Version == llvm::byteswap<uint16_t>(HMAP_HeaderVersion)1 ) |
81 | 1 | NeedsByteSwap = true; // Mixed endianness headermap. |
82 | 2 | else |
83 | 2 | return false; // Not a header map. |
84 | | |
85 | 56 | if (Header->Reserved != 0) |
86 | 1 | return false; |
87 | | |
88 | | // Check the number of buckets. It should be a power of two, and there |
89 | | // should be enough space in the file for all of them. |
90 | 55 | uint32_t NumBuckets = |
91 | 55 | NeedsByteSwap ? llvm::byteswap(Header->NumBuckets)1 : Header->NumBuckets54 ; |
92 | 55 | if (!llvm::isPowerOf2_32(NumBuckets)) |
93 | 2 | return false; |
94 | 53 | if (File.getBufferSize() < |
95 | 53 | sizeof(HMapHeader) + sizeof(HMapBucket) * NumBuckets) |
96 | 1 | return false; |
97 | | |
98 | | // Okay, everything looks good. |
99 | 52 | return true; |
100 | 53 | } |
101 | | |
102 | | //===----------------------------------------------------------------------===// |
103 | | // Utility Methods |
104 | | //===----------------------------------------------------------------------===// |
105 | | |
106 | | |
107 | | /// getFileName - Return the filename of the headermap. |
108 | 6 | StringRef HeaderMapImpl::getFileName() const { |
109 | 6 | return FileBuffer->getBufferIdentifier(); |
110 | 6 | } |
111 | | |
112 | 1.10k | unsigned HeaderMapImpl::getEndianAdjustedWord(unsigned X) const { |
113 | 1.10k | if (!NeedsBSwap) return X; |
114 | 0 | return llvm::byteswap<uint32_t>(X); |
115 | 1.10k | } |
116 | | |
117 | | /// getHeader - Return a reference to the file header, in unbyte-swapped form. |
118 | | /// This method cannot fail. |
119 | 267 | const HMapHeader &HeaderMapImpl::getHeader() const { |
120 | | // We know the file is at least as big as the header. Return it. |
121 | 267 | return *reinterpret_cast<const HMapHeader*>(FileBuffer->getBufferStart()); |
122 | 267 | } |
123 | | |
124 | | /// getBucket - Return the specified hash table bucket from the header map, |
125 | | /// bswap'ing its fields as appropriate. If the bucket number is not valid, |
126 | | /// this return a bucket with an empty key (0). |
127 | 279 | HMapBucket HeaderMapImpl::getBucket(unsigned BucketNo) const { |
128 | 279 | assert(FileBuffer->getBufferSize() >= |
129 | 279 | sizeof(HMapHeader) + sizeof(HMapBucket) * BucketNo && |
130 | 279 | "Expected bucket to be in range"); |
131 | | |
132 | 279 | HMapBucket Result; |
133 | 279 | Result.Key = HMAP_EmptyBucketKey; |
134 | | |
135 | 279 | const HMapBucket *BucketArray = |
136 | 279 | reinterpret_cast<const HMapBucket*>(FileBuffer->getBufferStart() + |
137 | 279 | sizeof(HMapHeader)); |
138 | 279 | const HMapBucket *BucketPtr = BucketArray+BucketNo; |
139 | | |
140 | | // Load the values, bswapping as needed. |
141 | 279 | Result.Key = getEndianAdjustedWord(BucketPtr->Key); |
142 | 279 | Result.Prefix = getEndianAdjustedWord(BucketPtr->Prefix); |
143 | 279 | Result.Suffix = getEndianAdjustedWord(BucketPtr->Suffix); |
144 | 279 | return Result; |
145 | 279 | } |
146 | | |
147 | 169 | std::optional<StringRef> HeaderMapImpl::getString(unsigned StrTabIdx) const { |
148 | | // Add the start of the string table to the idx. |
149 | 169 | StrTabIdx += getEndianAdjustedWord(getHeader().StringsOffset); |
150 | | |
151 | | // Check for invalid index. |
152 | 169 | if (StrTabIdx >= FileBuffer->getBufferSize()) |
153 | 0 | return std::nullopt; |
154 | | |
155 | 169 | const char *Data = FileBuffer->getBufferStart() + StrTabIdx; |
156 | 169 | unsigned MaxLen = FileBuffer->getBufferSize() - StrTabIdx; |
157 | 169 | unsigned Len = strnlen(Data, MaxLen); |
158 | | |
159 | | // Check whether the buffer is null-terminated. |
160 | 169 | if (Len == MaxLen && Data[Len - 1]2 ) |
161 | 2 | return std::nullopt; |
162 | | |
163 | 167 | return StringRef(Data, Len); |
164 | 169 | } |
165 | | |
166 | | //===----------------------------------------------------------------------===// |
167 | | // The Main Drivers |
168 | | //===----------------------------------------------------------------------===// |
169 | | |
170 | | /// dump - Print the contents of this headermap to stderr. |
171 | 0 | LLVM_DUMP_METHOD void HeaderMapImpl::dump() const { |
172 | 0 | const HMapHeader &Hdr = getHeader(); |
173 | 0 | unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); |
174 | |
|
175 | 0 | llvm::dbgs() << "Header Map " << getFileName() << ":\n " << NumBuckets |
176 | 0 | << ", " << getEndianAdjustedWord(Hdr.NumEntries) << "\n"; |
177 | |
|
178 | 0 | auto getStringOrInvalid = [this](unsigned Id) -> StringRef { |
179 | 0 | if (std::optional<StringRef> S = getString(Id)) |
180 | 0 | return *S; |
181 | 0 | return "<invalid>"; |
182 | 0 | }; |
183 | |
|
184 | 0 | for (unsigned i = 0; i != NumBuckets; ++i) { |
185 | 0 | HMapBucket B = getBucket(i); |
186 | 0 | if (B.Key == HMAP_EmptyBucketKey) continue; |
187 | | |
188 | 0 | StringRef Key = getStringOrInvalid(B.Key); |
189 | 0 | StringRef Prefix = getStringOrInvalid(B.Prefix); |
190 | 0 | StringRef Suffix = getStringOrInvalid(B.Suffix); |
191 | 0 | llvm::dbgs() << " " << i << ". " << Key << " -> '" << Prefix << "' '" |
192 | 0 | << Suffix << "'\n"; |
193 | 0 | } |
194 | 0 | } |
195 | | |
196 | | StringRef HeaderMapImpl::lookupFilename(StringRef Filename, |
197 | 54 | SmallVectorImpl<char> &DestPath) const { |
198 | 54 | const HMapHeader &Hdr = getHeader(); |
199 | 54 | unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); |
200 | | |
201 | | // Don't probe infinitely. This should be checked before constructing. |
202 | 54 | assert(llvm::isPowerOf2_32(NumBuckets) && "Expected power of 2"); |
203 | | |
204 | | // Linearly probe the hash table. |
205 | 69 | for (unsigned Bucket = HashHMapKey(Filename);; 54 ++Bucket15 ) { |
206 | 69 | HMapBucket B = getBucket(Bucket & (NumBuckets-1)); |
207 | 69 | if (B.Key == HMAP_EmptyBucketKey) return StringRef()25 ; // Hash miss. |
208 | | |
209 | | // See if the key matches. If not, probe on. |
210 | 44 | std::optional<StringRef> Key = getString(B.Key); |
211 | 44 | if (LLVM_UNLIKELY(!Key)) |
212 | 0 | continue; |
213 | 44 | if (!Filename.equals_insensitive(*Key)) |
214 | 15 | continue; |
215 | | |
216 | | // If so, we have a match in the hash table. Construct the destination |
217 | | // path. |
218 | 29 | std::optional<StringRef> Prefix = getString(B.Prefix); |
219 | 29 | std::optional<StringRef> Suffix = getString(B.Suffix); |
220 | | |
221 | 29 | DestPath.clear(); |
222 | 29 | if (LLVM_LIKELY(Prefix && Suffix)) { |
223 | 27 | DestPath.append(Prefix->begin(), Prefix->end()); |
224 | 27 | DestPath.append(Suffix->begin(), Suffix->end()); |
225 | 27 | } |
226 | 29 | return StringRef(DestPath.begin(), DestPath.size()); |
227 | 44 | } |
228 | 54 | } |
229 | | |
230 | 7 | StringRef HeaderMapImpl::reverseLookupFilename(StringRef DestPath) const { |
231 | 7 | if (!ReverseMap.empty()) |
232 | 0 | return ReverseMap.lookup(DestPath); |
233 | | |
234 | 7 | const HMapHeader &Hdr = getHeader(); |
235 | 7 | unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); |
236 | 7 | StringRef RetKey; |
237 | 33 | for (unsigned i = 0; i != NumBuckets; ++i26 ) { |
238 | 26 | HMapBucket B = getBucket(i); |
239 | 26 | if (B.Key == HMAP_EmptyBucketKey) |
240 | 19 | continue; |
241 | | |
242 | 7 | std::optional<StringRef> Key = getString(B.Key); |
243 | 7 | std::optional<StringRef> Prefix = getString(B.Prefix); |
244 | 7 | std::optional<StringRef> Suffix = getString(B.Suffix); |
245 | 7 | if (LLVM_LIKELY(Key && Prefix && Suffix)) { |
246 | 7 | SmallVector<char, 1024> Buf; |
247 | 7 | Buf.append(Prefix->begin(), Prefix->end()); |
248 | 7 | Buf.append(Suffix->begin(), Suffix->end()); |
249 | 7 | StringRef Value(Buf.begin(), Buf.size()); |
250 | 7 | ReverseMap[Value] = *Key; |
251 | | |
252 | 7 | if (DestPath == Value) |
253 | 2 | RetKey = *Key; |
254 | 7 | } |
255 | 7 | } |
256 | 7 | return RetKey; |
257 | 7 | } |