clang 22.0.0git
HeaderMap.cpp
Go to the documentation of this file.
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"
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(*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(FE, /*IsVolatile=*/false,
55 /*RequiresNullTerminator=*/true,
56 /*MaybeList=*/std::nullopt, /*IsText=*/false);
57 if (!FileBuffer || !*FileBuffer)
58 return nullptr;
59 bool NeedsByteSwap;
60 if (!checkHeader(**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>(HMAP_HeaderMagicNumber) &&
80 Header->Version == llvm::byteswap<uint16_t>(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(Header->NumBuckets) : Header->NumBuckets;
92 if (!llvm::isPowerOf2_32(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>(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;
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(BucketPtr->Key);
142 Result.Prefix = getEndianAdjustedWord(BucketPtr->Prefix);
143 Result.Suffix = getEndianAdjustedWord(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(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(Data, 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(Hdr.NumBuckets);
178
179 llvm::dbgs() << "Header Map " << getFileName() << ":\n " << NumBuckets
180 << ", " << getEndianAdjustedWord(Hdr.NumEntries) << "\n";
181
182 auto getStringOrInvalid = [this](unsigned Id) -> StringRef {
183 if (std::optional<StringRef> S = getString(Id))
184 return *S;
185 return "<invalid>";
186 };
187
188 for (unsigned i = 0; i != NumBuckets; ++i) {
189 HMapBucket B = getBucket(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(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(Filename);; ++Bucket) {
210 HMapBucket B = getBucket(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(B.Key);
215 if (LLVM_UNLIKELY(!Key))
216 continue;
217 if (!Filename.equals_insensitive(*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(B.Prefix);
223 std::optional<StringRef> Suffix = getString(B.Suffix);
224
225 DestPath.clear();
226 if (LLVM_LIKELY(Prefix && Suffix)) {
227 DestPath.append(Prefix->begin(), Prefix->end());
228 DestPath.append(Suffix->begin(), 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(DestPath);
237
238 const HMapHeader &Hdr = getHeader();
239 unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
240 StringRef RetKey;
241 for (unsigned i = 0; i != NumBuckets; ++i) {
242 HMapBucket B = getBucket(i);
243 if (B.Key == HMAP_EmptyBucketKey)
244 continue;
245
246 std::optional<StringRef> Key = getString(B.Key);
247 std::optional<StringRef> Prefix = getString(B.Prefix);
248 std::optional<StringRef> Suffix = getString(B.Suffix);
249 if (LLVM_LIKELY(Key && Prefix && Suffix)) {
251 Buf.append(Prefix->begin(), Prefix->end());
252 Buf.append(Suffix->begin(), 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}
Defines the clang::FileManager interface and associated types.
static unsigned HashHMapKey(StringRef Str)
HashHMapKey - This is the 'well known' hash function required by the file format, used to look up key...
Definition HeaderMap.cpp:29
#define X(type, name)
Definition Value.h:97
A reference to a FileEntry that includes the name of the file as it was accessed by the FileManager's...
Definition FileEntry.h:57
off_t getSize() const
Definition FileEntry.h:350
Implements support for file system lookup, file system caching, and directory search management.
Definition FileManager.h:53
llvm::ErrorOr< std::unique_ptr< llvm::MemoryBuffer > > getBufferForFile(FileEntryRef Entry, bool isVolatile=false, bool RequiresNullTerminator=true, std::optional< int64_t > MaybeLimit=std::nullopt, bool IsText=true)
Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful,...
StringRef getFileName() const
Return the filename of the headermap.
StringRef reverseLookupFilename(StringRef DestPath) const
Return key for specifed path.
void dump() const
Print the contents of this headermap to stderr.
StringRef lookupFilename(StringRef Filename, SmallVectorImpl< char > &DestPath) const
If the specified relative filename is located in this HeaderMap return the filename it is mapped to,...
static bool checkHeader(const llvm::MemoryBuffer &File, bool &NeedsByteSwap)
Definition HeaderMap.cpp:65
static std::unique_ptr< HeaderMap > Create(FileEntryRef FE, FileManager &FM)
This attempts to load the specified file as a header map.
Definition HeaderMap.cpp:48
The JSON file list parser is used to communicate input to InstallAPI.
LLVM_READONLY char toLowercase(char c)
Converts the given ASCII character to its lowercase equivalent.
Definition CharInfo.h:224
@ HMAP_HeaderVersion
@ HMAP_EmptyBucketKey
@ HMAP_HeaderMagicNumber
@ Result
The result type of a method or function.
Definition TypeBase.h:905