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
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
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.
StringRef Filename
Definition: Format.cpp:3177
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:145
uint32_t Id
Definition: SemaARM.cpp:1179
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.
Definition: HeaderMap.cpp:108
StringRef reverseLookupFilename(StringRef DestPath) const
Return key for specifed path.
Definition: HeaderMap.cpp:234
void dump() const
Print the contents of this headermap to stderr.
Definition: HeaderMap.cpp:175
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,...
Definition: HeaderMap.cpp:200
static bool checkHeader(const llvm::MemoryBuffer &File, bool &NeedsByteSwap)
Definition: HeaderMap.cpp:65
This class represents an Apple concept known as a 'header map'.
Definition: HeaderMap.h:84
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
@ Result
The result type of a method or function.
@ HMAP_HeaderVersion
@ HMAP_EmptyBucketKey
@ HMAP_HeaderMagicNumber