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/Basic/CharInfo.h"
15#include "clang/Basic/FileManager.h"
16#include "clang/Lex/HeaderMapTypes.h"
17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/Debug.h"
19#include "llvm/Support/MathExtras.h"
20#include "llvm/Support/MemoryBuffer.h"
21#include <cstring>
22#include <memory>
23#include <optional>
24using namespace clang;
25
26/// HashHMapKey - This is the 'well known' hash function required by the file
27/// format, used to look up keys in the hash table. The hash table uses simple
28/// linear probing based on this function.
29static inline unsigned HashHMapKey(StringRef Str) {
30 unsigned Result = 0;
31 const char *S = Str.begin(), *End = Str.end();
32
33 for (; S != End; S++)
34 Result += toLowercase(c: *S) * 13;
35 return Result;
36}
37
38
39
40//===----------------------------------------------------------------------===//
41// Verification and Construction
42//===----------------------------------------------------------------------===//
43
44/// HeaderMap::Create - This attempts to load the specified file as a header
45/// map. If it doesn't look like a HeaderMap, it gives up and returns null.
46/// If it looks like a HeaderMap but is obviously corrupted, it puts a reason
47/// into the string error argument and returns null.
48std::unique_ptr<HeaderMap> HeaderMap::Create(FileEntryRef FE, FileManager &FM) {
49 // If the file is too small to be a header map, ignore it.
50 unsigned FileSize = FE.getSize();
51 if (FileSize <= sizeof(HMapHeader)) return nullptr;
52
53 auto FileBuffer =
54 FM.getBufferForFile(Entry: FE, /*IsVolatile=*/isVolatile: false,
55 /*RequiresNullTerminator=*/true,
56 /*MaybeList=*/MaybeLimit: std::nullopt, /*IsText=*/false);
57 if (!FileBuffer || !*FileBuffer)
58 return nullptr;
59 bool NeedsByteSwap;
60 if (!checkHeader(File: **FileBuffer, NeedsByteSwap))
61 return nullptr;
62 return std::unique_ptr<HeaderMap>(new HeaderMap(std::move(*FileBuffer), NeedsByteSwap));
63}
64
65bool HeaderMapImpl::checkHeader(const llvm::MemoryBuffer &File,
66 bool &NeedsByteSwap) {
67 if (File.getBufferSize() <= sizeof(HMapHeader))
68 return false;
69 const char *FileStart = File.getBufferStart();
70
71 // We know the file is at least as big as the header, check it now.
72 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 if (Header->Magic == HMAP_HeaderMagicNumber &&
77 Header->Version == HMAP_HeaderVersion)
78 NeedsByteSwap = false;
79 else if (Header->Magic == llvm::byteswap<uint32_t>(V: HMAP_HeaderMagicNumber) &&
80 Header->Version == llvm::byteswap<uint16_t>(V: HMAP_HeaderVersion))
81 NeedsByteSwap = true; // Mixed endianness headermap.
82 else
83 return false; // Not a header map.
84
85 if (Header->Reserved != 0)
86 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 uint32_t NumBuckets =
91 NeedsByteSwap ? llvm::byteswap(V: Header->NumBuckets) : Header->NumBuckets;
92 if (!llvm::isPowerOf2_32(Value: NumBuckets))
93 return false;
94 if (File.getBufferSize() <
95 sizeof(HMapHeader) + sizeof(HMapBucket) * NumBuckets)
96 return false;
97
98 // Okay, everything looks good.
99 return true;
100}
101
102//===----------------------------------------------------------------------===//
103// Utility Methods
104//===----------------------------------------------------------------------===//
105
106
107/// getFileName - Return the filename of the headermap.
108StringRef HeaderMapImpl::getFileName() const {
109 return FileBuffer->getBufferIdentifier();
110}
111
112unsigned HeaderMapImpl::getEndianAdjustedWord(unsigned X) const {
113 if (!NeedsBSwap) return X;
114 return llvm::byteswap<uint32_t>(V: X);
115}
116
117/// getHeader - Return a reference to the file header, in unbyte-swapped form.
118/// This method cannot fail.
119const HMapHeader &HeaderMapImpl::getHeader() const {
120 // We know the file is at least as big as the header. Return it.
121 return *reinterpret_cast<const HMapHeader*>(FileBuffer->getBufferStart());
122}
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).
127HMapBucket HeaderMapImpl::getBucket(unsigned BucketNo) const {
128 assert(FileBuffer->getBufferSize() >=
129 sizeof(HMapHeader) + sizeof(HMapBucket) * BucketNo &&
130 "Expected bucket to be in range");
131
132 HMapBucket Result;
133 Result.Key = HMAP_EmptyBucketKey;
134
135 const HMapBucket *BucketArray =
136 reinterpret_cast<const HMapBucket*>(FileBuffer->getBufferStart() +
137 sizeof(HMapHeader));
138 const HMapBucket *BucketPtr = BucketArray+BucketNo;
139
140 // Load the values, bswapping as needed.
141 Result.Key = getEndianAdjustedWord(X: BucketPtr->Key);
142 Result.Prefix = getEndianAdjustedWord(X: BucketPtr->Prefix);
143 Result.Suffix = getEndianAdjustedWord(X: BucketPtr->Suffix);
144 return Result;
145}
146
147std::optional<StringRef> HeaderMapImpl::getString(unsigned StrTabIdx) const {
148 // Add the start of the string table to the idx.
149 StrTabIdx += getEndianAdjustedWord(X: getHeader().StringsOffset);
150
151 // Check for invalid index.
152 if (StrTabIdx >= FileBuffer->getBufferSize())
153 return std::nullopt;
154
155 const char *Data = FileBuffer->getBufferStart() + StrTabIdx;
156 unsigned MaxLen = FileBuffer->getBufferSize() - StrTabIdx;
157
158 if (MaxLen == 0)
159 return std::nullopt;
160
161 unsigned Len = strnlen(string: Data, maxlen: MaxLen);
162
163 // Check whether the buffer is null-terminated.
164 if (Len == MaxLen && Data[Len - 1])
165 return std::nullopt;
166
167 return StringRef(Data, Len);
168}
169
170//===----------------------------------------------------------------------===//
171// The Main Drivers
172//===----------------------------------------------------------------------===//
173
174/// dump - Print the contents of this headermap to stderr.
175LLVM_DUMP_METHOD void HeaderMapImpl::dump() const {
176 const HMapHeader &Hdr = getHeader();
177 unsigned NumBuckets = getEndianAdjustedWord(X: Hdr.NumBuckets);
178
179 llvm::dbgs() << "Header Map " << getFileName() << ":\n " << NumBuckets
180 << ", " << getEndianAdjustedWord(X: Hdr.NumEntries) << "\n";
181
182 auto getStringOrInvalid = [this](unsigned Id) -> StringRef {
183 if (std::optional<StringRef> S = getString(StrTabIdx: Id))
184 return *S;
185 return "<invalid>";
186 };
187
188 for (unsigned i = 0; i != NumBuckets; ++i) {
189 HMapBucket B = getBucket(BucketNo: i);
190 if (B.Key == HMAP_EmptyBucketKey) continue;
191
192 StringRef Key = getStringOrInvalid(B.Key);
193 StringRef Prefix = getStringOrInvalid(B.Prefix);
194 StringRef Suffix = getStringOrInvalid(B.Suffix);
195 llvm::dbgs() << " " << i << ". " << Key << " -> '" << Prefix << "' '"
196 << Suffix << "'\n";
197 }
198}
199
200StringRef HeaderMapImpl::lookupFilename(StringRef Filename,
201 SmallVectorImpl<char> &DestPath) const {
202 const HMapHeader &Hdr = getHeader();
203 unsigned NumBuckets = getEndianAdjustedWord(X: Hdr.NumBuckets);
204
205 // Don't probe infinitely. This should be checked before constructing.
206 assert(llvm::isPowerOf2_32(NumBuckets) && "Expected power of 2");
207
208 // Linearly probe the hash table.
209 for (unsigned Bucket = HashHMapKey(Str: Filename);; ++Bucket) {
210 HMapBucket B = getBucket(BucketNo: Bucket & (NumBuckets-1));
211 if (B.Key == HMAP_EmptyBucketKey) return StringRef(); // Hash miss.
212
213 // See if the key matches. If not, probe on.
214 std::optional<StringRef> Key = getString(StrTabIdx: B.Key);
215 if (LLVM_UNLIKELY(!Key))
216 continue;
217 if (!Filename.equals_insensitive(RHS: *Key))
218 continue;
219
220 // If so, we have a match in the hash table. Construct the destination
221 // path.
222 std::optional<StringRef> Prefix = getString(StrTabIdx: B.Prefix);
223 std::optional<StringRef> Suffix = getString(StrTabIdx: B.Suffix);
224
225 DestPath.clear();
226 if (LLVM_LIKELY(Prefix && Suffix)) {
227 DestPath.append(in_start: Prefix->begin(), in_end: Prefix->end());
228 DestPath.append(in_start: Suffix->begin(), in_end: Suffix->end());
229 }
230 return StringRef(DestPath.begin(), DestPath.size());
231 }
232}
233
234StringRef HeaderMapImpl::reverseLookupFilename(StringRef DestPath) const {
235 if (!ReverseMap.empty())
236 return ReverseMap.lookup(Key: DestPath);
237
238 const HMapHeader &Hdr = getHeader();
239 unsigned NumBuckets = getEndianAdjustedWord(X: Hdr.NumBuckets);
240 StringRef RetKey;
241 for (unsigned i = 0; i != NumBuckets; ++i) {
242 HMapBucket B = getBucket(BucketNo: i);
243 if (B.Key == HMAP_EmptyBucketKey)
244 continue;
245
246 std::optional<StringRef> Key = getString(StrTabIdx: B.Key);
247 std::optional<StringRef> Prefix = getString(StrTabIdx: B.Prefix);
248 std::optional<StringRef> Suffix = getString(StrTabIdx: B.Suffix);
249 if (LLVM_LIKELY(Key && Prefix && Suffix)) {
250 SmallVector<char, 1024> Buf;
251 Buf.append(in_start: Prefix->begin(), in_end: Prefix->end());
252 Buf.append(in_start: Suffix->begin(), in_end: Suffix->end());
253 StringRef Value(Buf.begin(), Buf.size());
254 ReverseMap[Value] = *Key;
255
256 if (DestPath == Value)
257 RetKey = *Key;
258 }
259 }
260 return RetKey;
261}
262