262 lines · cpp
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-exception6//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 file27/// format, used to look up keys in the hash table. The hash table uses simple28/// 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 Construction42//===----------------------------------------------------------------------===//43 44/// HeaderMap::Create - This attempts to load the specified file as a header45/// 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 reason47/// 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 and75 // 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 else83 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 there89 // 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 Methods104//===----------------------------------------------------------------------===//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;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(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 Drivers172//===----------------------------------------------------------------------===//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 " << NumBuckets180 << ", " << 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 destination221 // 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)) {250 SmallVector<char, 1024> Buf;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}262