1*06f32e7eSjoerg //===--- HeaderMap.cpp - A file that acts like dir of symlinks ------------===//
2*06f32e7eSjoerg //
3*06f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*06f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
5*06f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6*06f32e7eSjoerg //
7*06f32e7eSjoerg //===----------------------------------------------------------------------===//
8*06f32e7eSjoerg //
9*06f32e7eSjoerg // This file implements the HeaderMap interface.
10*06f32e7eSjoerg //
11*06f32e7eSjoerg //===----------------------------------------------------------------------===//
12*06f32e7eSjoerg
13*06f32e7eSjoerg #include "clang/Lex/HeaderMap.h"
14*06f32e7eSjoerg #include "clang/Lex/HeaderMapTypes.h"
15*06f32e7eSjoerg #include "clang/Basic/CharInfo.h"
16*06f32e7eSjoerg #include "clang/Basic/FileManager.h"
17*06f32e7eSjoerg #include "llvm/ADT/SmallString.h"
18*06f32e7eSjoerg #include "llvm/Support/Compiler.h"
19*06f32e7eSjoerg #include "llvm/Support/DataTypes.h"
20*06f32e7eSjoerg #include "llvm/Support/MathExtras.h"
21*06f32e7eSjoerg #include "llvm/Support/MemoryBuffer.h"
22*06f32e7eSjoerg #include "llvm/Support/SwapByteOrder.h"
23*06f32e7eSjoerg #include "llvm/Support/Debug.h"
24*06f32e7eSjoerg #include <cstring>
25*06f32e7eSjoerg #include <memory>
26*06f32e7eSjoerg using namespace clang;
27*06f32e7eSjoerg
28*06f32e7eSjoerg /// HashHMapKey - This is the 'well known' hash function required by the file
29*06f32e7eSjoerg /// format, used to look up keys in the hash table. The hash table uses simple
30*06f32e7eSjoerg /// linear probing based on this function.
HashHMapKey(StringRef Str)31*06f32e7eSjoerg static inline unsigned HashHMapKey(StringRef Str) {
32*06f32e7eSjoerg unsigned Result = 0;
33*06f32e7eSjoerg const char *S = Str.begin(), *End = Str.end();
34*06f32e7eSjoerg
35*06f32e7eSjoerg for (; S != End; S++)
36*06f32e7eSjoerg Result += toLowercase(*S) * 13;
37*06f32e7eSjoerg return Result;
38*06f32e7eSjoerg }
39*06f32e7eSjoerg
40*06f32e7eSjoerg
41*06f32e7eSjoerg
42*06f32e7eSjoerg //===----------------------------------------------------------------------===//
43*06f32e7eSjoerg // Verification and Construction
44*06f32e7eSjoerg //===----------------------------------------------------------------------===//
45*06f32e7eSjoerg
46*06f32e7eSjoerg /// HeaderMap::Create - This attempts to load the specified file as a header
47*06f32e7eSjoerg /// map. If it doesn't look like a HeaderMap, it gives up and returns null.
48*06f32e7eSjoerg /// If it looks like a HeaderMap but is obviously corrupted, it puts a reason
49*06f32e7eSjoerg /// into the string error argument and returns null.
Create(const FileEntry * FE,FileManager & FM)50*06f32e7eSjoerg std::unique_ptr<HeaderMap> HeaderMap::Create(const FileEntry *FE,
51*06f32e7eSjoerg FileManager &FM) {
52*06f32e7eSjoerg // If the file is too small to be a header map, ignore it.
53*06f32e7eSjoerg unsigned FileSize = FE->getSize();
54*06f32e7eSjoerg if (FileSize <= sizeof(HMapHeader)) return nullptr;
55*06f32e7eSjoerg
56*06f32e7eSjoerg auto FileBuffer = FM.getBufferForFile(FE);
57*06f32e7eSjoerg if (!FileBuffer || !*FileBuffer)
58*06f32e7eSjoerg return nullptr;
59*06f32e7eSjoerg bool NeedsByteSwap;
60*06f32e7eSjoerg if (!checkHeader(**FileBuffer, NeedsByteSwap))
61*06f32e7eSjoerg return nullptr;
62*06f32e7eSjoerg return std::unique_ptr<HeaderMap>(new HeaderMap(std::move(*FileBuffer), NeedsByteSwap));
63*06f32e7eSjoerg }
64*06f32e7eSjoerg
checkHeader(const llvm::MemoryBuffer & File,bool & NeedsByteSwap)65*06f32e7eSjoerg bool HeaderMapImpl::checkHeader(const llvm::MemoryBuffer &File,
66*06f32e7eSjoerg bool &NeedsByteSwap) {
67*06f32e7eSjoerg if (File.getBufferSize() <= sizeof(HMapHeader))
68*06f32e7eSjoerg return false;
69*06f32e7eSjoerg const char *FileStart = File.getBufferStart();
70*06f32e7eSjoerg
71*06f32e7eSjoerg // We know the file is at least as big as the header, check it now.
72*06f32e7eSjoerg const HMapHeader *Header = reinterpret_cast<const HMapHeader*>(FileStart);
73*06f32e7eSjoerg
74*06f32e7eSjoerg // Sniff it to see if it's a headermap by checking the magic number and
75*06f32e7eSjoerg // version.
76*06f32e7eSjoerg if (Header->Magic == HMAP_HeaderMagicNumber &&
77*06f32e7eSjoerg Header->Version == HMAP_HeaderVersion)
78*06f32e7eSjoerg NeedsByteSwap = false;
79*06f32e7eSjoerg else if (Header->Magic == llvm::ByteSwap_32(HMAP_HeaderMagicNumber) &&
80*06f32e7eSjoerg Header->Version == llvm::ByteSwap_16(HMAP_HeaderVersion))
81*06f32e7eSjoerg NeedsByteSwap = true; // Mixed endianness headermap.
82*06f32e7eSjoerg else
83*06f32e7eSjoerg return false; // Not a header map.
84*06f32e7eSjoerg
85*06f32e7eSjoerg if (Header->Reserved != 0)
86*06f32e7eSjoerg return false;
87*06f32e7eSjoerg
88*06f32e7eSjoerg // Check the number of buckets. It should be a power of two, and there
89*06f32e7eSjoerg // should be enough space in the file for all of them.
90*06f32e7eSjoerg uint32_t NumBuckets = NeedsByteSwap
91*06f32e7eSjoerg ? llvm::sys::getSwappedBytes(Header->NumBuckets)
92*06f32e7eSjoerg : Header->NumBuckets;
93*06f32e7eSjoerg if (!llvm::isPowerOf2_32(NumBuckets))
94*06f32e7eSjoerg return false;
95*06f32e7eSjoerg if (File.getBufferSize() <
96*06f32e7eSjoerg sizeof(HMapHeader) + sizeof(HMapBucket) * NumBuckets)
97*06f32e7eSjoerg return false;
98*06f32e7eSjoerg
99*06f32e7eSjoerg // Okay, everything looks good.
100*06f32e7eSjoerg return true;
101*06f32e7eSjoerg }
102*06f32e7eSjoerg
103*06f32e7eSjoerg //===----------------------------------------------------------------------===//
104*06f32e7eSjoerg // Utility Methods
105*06f32e7eSjoerg //===----------------------------------------------------------------------===//
106*06f32e7eSjoerg
107*06f32e7eSjoerg
108*06f32e7eSjoerg /// getFileName - Return the filename of the headermap.
getFileName() const109*06f32e7eSjoerg StringRef HeaderMapImpl::getFileName() const {
110*06f32e7eSjoerg return FileBuffer->getBufferIdentifier();
111*06f32e7eSjoerg }
112*06f32e7eSjoerg
getEndianAdjustedWord(unsigned X) const113*06f32e7eSjoerg unsigned HeaderMapImpl::getEndianAdjustedWord(unsigned X) const {
114*06f32e7eSjoerg if (!NeedsBSwap) return X;
115*06f32e7eSjoerg return llvm::ByteSwap_32(X);
116*06f32e7eSjoerg }
117*06f32e7eSjoerg
118*06f32e7eSjoerg /// getHeader - Return a reference to the file header, in unbyte-swapped form.
119*06f32e7eSjoerg /// This method cannot fail.
getHeader() const120*06f32e7eSjoerg const HMapHeader &HeaderMapImpl::getHeader() const {
121*06f32e7eSjoerg // We know the file is at least as big as the header. Return it.
122*06f32e7eSjoerg return *reinterpret_cast<const HMapHeader*>(FileBuffer->getBufferStart());
123*06f32e7eSjoerg }
124*06f32e7eSjoerg
125*06f32e7eSjoerg /// getBucket - Return the specified hash table bucket from the header map,
126*06f32e7eSjoerg /// bswap'ing its fields as appropriate. If the bucket number is not valid,
127*06f32e7eSjoerg /// this return a bucket with an empty key (0).
getBucket(unsigned BucketNo) const128*06f32e7eSjoerg HMapBucket HeaderMapImpl::getBucket(unsigned BucketNo) const {
129*06f32e7eSjoerg assert(FileBuffer->getBufferSize() >=
130*06f32e7eSjoerg sizeof(HMapHeader) + sizeof(HMapBucket) * BucketNo &&
131*06f32e7eSjoerg "Expected bucket to be in range");
132*06f32e7eSjoerg
133*06f32e7eSjoerg HMapBucket Result;
134*06f32e7eSjoerg Result.Key = HMAP_EmptyBucketKey;
135*06f32e7eSjoerg
136*06f32e7eSjoerg const HMapBucket *BucketArray =
137*06f32e7eSjoerg reinterpret_cast<const HMapBucket*>(FileBuffer->getBufferStart() +
138*06f32e7eSjoerg sizeof(HMapHeader));
139*06f32e7eSjoerg const HMapBucket *BucketPtr = BucketArray+BucketNo;
140*06f32e7eSjoerg
141*06f32e7eSjoerg // Load the values, bswapping as needed.
142*06f32e7eSjoerg Result.Key = getEndianAdjustedWord(BucketPtr->Key);
143*06f32e7eSjoerg Result.Prefix = getEndianAdjustedWord(BucketPtr->Prefix);
144*06f32e7eSjoerg Result.Suffix = getEndianAdjustedWord(BucketPtr->Suffix);
145*06f32e7eSjoerg return Result;
146*06f32e7eSjoerg }
147*06f32e7eSjoerg
getString(unsigned StrTabIdx) const148*06f32e7eSjoerg Optional<StringRef> HeaderMapImpl::getString(unsigned StrTabIdx) const {
149*06f32e7eSjoerg // Add the start of the string table to the idx.
150*06f32e7eSjoerg StrTabIdx += getEndianAdjustedWord(getHeader().StringsOffset);
151*06f32e7eSjoerg
152*06f32e7eSjoerg // Check for invalid index.
153*06f32e7eSjoerg if (StrTabIdx >= FileBuffer->getBufferSize())
154*06f32e7eSjoerg return None;
155*06f32e7eSjoerg
156*06f32e7eSjoerg const char *Data = FileBuffer->getBufferStart() + StrTabIdx;
157*06f32e7eSjoerg unsigned MaxLen = FileBuffer->getBufferSize() - StrTabIdx;
158*06f32e7eSjoerg unsigned Len = strnlen(Data, MaxLen);
159*06f32e7eSjoerg
160*06f32e7eSjoerg // Check whether the buffer is null-terminated.
161*06f32e7eSjoerg if (Len == MaxLen && Data[Len - 1])
162*06f32e7eSjoerg return None;
163*06f32e7eSjoerg
164*06f32e7eSjoerg return StringRef(Data, Len);
165*06f32e7eSjoerg }
166*06f32e7eSjoerg
167*06f32e7eSjoerg //===----------------------------------------------------------------------===//
168*06f32e7eSjoerg // The Main Drivers
169*06f32e7eSjoerg //===----------------------------------------------------------------------===//
170*06f32e7eSjoerg
171*06f32e7eSjoerg /// dump - Print the contents of this headermap to stderr.
dump() const172*06f32e7eSjoerg LLVM_DUMP_METHOD void HeaderMapImpl::dump() const {
173*06f32e7eSjoerg const HMapHeader &Hdr = getHeader();
174*06f32e7eSjoerg unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
175*06f32e7eSjoerg
176*06f32e7eSjoerg llvm::dbgs() << "Header Map " << getFileName() << ":\n " << NumBuckets
177*06f32e7eSjoerg << ", " << getEndianAdjustedWord(Hdr.NumEntries) << "\n";
178*06f32e7eSjoerg
179*06f32e7eSjoerg auto getStringOrInvalid = [this](unsigned Id) -> StringRef {
180*06f32e7eSjoerg if (Optional<StringRef> S = getString(Id))
181*06f32e7eSjoerg return *S;
182*06f32e7eSjoerg return "<invalid>";
183*06f32e7eSjoerg };
184*06f32e7eSjoerg
185*06f32e7eSjoerg for (unsigned i = 0; i != NumBuckets; ++i) {
186*06f32e7eSjoerg HMapBucket B = getBucket(i);
187*06f32e7eSjoerg if (B.Key == HMAP_EmptyBucketKey) continue;
188*06f32e7eSjoerg
189*06f32e7eSjoerg StringRef Key = getStringOrInvalid(B.Key);
190*06f32e7eSjoerg StringRef Prefix = getStringOrInvalid(B.Prefix);
191*06f32e7eSjoerg StringRef Suffix = getStringOrInvalid(B.Suffix);
192*06f32e7eSjoerg llvm::dbgs() << " " << i << ". " << Key << " -> '" << Prefix << "' '"
193*06f32e7eSjoerg << Suffix << "'\n";
194*06f32e7eSjoerg }
195*06f32e7eSjoerg }
196*06f32e7eSjoerg
197*06f32e7eSjoerg /// LookupFile - Check to see if the specified relative filename is located in
198*06f32e7eSjoerg /// this HeaderMap. If so, open it and return its FileEntry.
LookupFile(StringRef Filename,FileManager & FM) const199*06f32e7eSjoerg Optional<FileEntryRef> HeaderMap::LookupFile(StringRef Filename,
200*06f32e7eSjoerg FileManager &FM) const {
201*06f32e7eSjoerg
202*06f32e7eSjoerg SmallString<1024> Path;
203*06f32e7eSjoerg StringRef Dest = HeaderMapImpl::lookupFilename(Filename, Path);
204*06f32e7eSjoerg if (Dest.empty())
205*06f32e7eSjoerg return None;
206*06f32e7eSjoerg
207*06f32e7eSjoerg return FM.getOptionalFileRef(Dest);
208*06f32e7eSjoerg }
209*06f32e7eSjoerg
lookupFilename(StringRef Filename,SmallVectorImpl<char> & DestPath) const210*06f32e7eSjoerg StringRef HeaderMapImpl::lookupFilename(StringRef Filename,
211*06f32e7eSjoerg SmallVectorImpl<char> &DestPath) const {
212*06f32e7eSjoerg const HMapHeader &Hdr = getHeader();
213*06f32e7eSjoerg unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets);
214*06f32e7eSjoerg
215*06f32e7eSjoerg // Don't probe infinitely. This should be checked before constructing.
216*06f32e7eSjoerg assert(llvm::isPowerOf2_32(NumBuckets) && "Expected power of 2");
217*06f32e7eSjoerg
218*06f32e7eSjoerg // Linearly probe the hash table.
219*06f32e7eSjoerg for (unsigned Bucket = HashHMapKey(Filename);; ++Bucket) {
220*06f32e7eSjoerg HMapBucket B = getBucket(Bucket & (NumBuckets-1));
221*06f32e7eSjoerg if (B.Key == HMAP_EmptyBucketKey) return StringRef(); // Hash miss.
222*06f32e7eSjoerg
223*06f32e7eSjoerg // See if the key matches. If not, probe on.
224*06f32e7eSjoerg Optional<StringRef> Key = getString(B.Key);
225*06f32e7eSjoerg if (LLVM_UNLIKELY(!Key))
226*06f32e7eSjoerg continue;
227*06f32e7eSjoerg if (!Filename.equals_lower(*Key))
228*06f32e7eSjoerg continue;
229*06f32e7eSjoerg
230*06f32e7eSjoerg // If so, we have a match in the hash table. Construct the destination
231*06f32e7eSjoerg // path.
232*06f32e7eSjoerg Optional<StringRef> Prefix = getString(B.Prefix);
233*06f32e7eSjoerg Optional<StringRef> Suffix = getString(B.Suffix);
234*06f32e7eSjoerg
235*06f32e7eSjoerg DestPath.clear();
236*06f32e7eSjoerg if (LLVM_LIKELY(Prefix && Suffix)) {
237*06f32e7eSjoerg DestPath.append(Prefix->begin(), Prefix->end());
238*06f32e7eSjoerg DestPath.append(Suffix->begin(), Suffix->end());
239*06f32e7eSjoerg }
240*06f32e7eSjoerg return StringRef(DestPath.begin(), DestPath.size());
241*06f32e7eSjoerg }
242*06f32e7eSjoerg }
243