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