| 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::Create(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::checkHeader(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 *Header = 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_32(HMAP_HeaderMagicNumber) && |
| 81 |
Header->Version == llvm::ByteSwap_16(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::getFileName() const { |
| 111 |
return FileBuffer->getBufferIdentifier(); |
| 112 |
} |
| 113 |
|
| 114 |
unsigned HeaderMapImpl::getEndianAdjustedWord(unsigned X) const { |
| 115 |
if (!NeedsBSwap) return X; |
| 116 |
return llvm::ByteSwap_32(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::getHeader() 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::getBucket(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::getString(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::dump() 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::lookupFilename(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::reverseLookupFilename(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 |
} |