420 lines · c
1//===- ASTReaderInternals.h - AST Reader Internals --------------*- C++ -*-===//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 provides internal definitions used in the AST reader.10//11//===----------------------------------------------------------------------===//12 13#ifndef LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H14#define LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H15 16#include "MultiOnDiskHashTable.h"17#include "clang/AST/DeclarationName.h"18#include "clang/Basic/LLVM.h"19#include "clang/Serialization/ASTBitCodes.h"20#include "llvm/ADT/DenseSet.h"21#include "llvm/ADT/SmallVector.h"22#include "llvm/ADT/StringRef.h"23#include "llvm/Support/OnDiskHashTable.h"24#include <ctime>25#include <utility>26 27namespace clang {28 29class ASTReader;30class FileEntry;31struct HeaderFileInfo;32class HeaderSearch;33class ObjCMethodDecl;34class Module;35 36namespace serialization {37 38class ModuleFile;39 40namespace reader {41 42class ASTDeclContextNameLookupTraitBase {43protected:44 ASTReader &Reader;45 ModuleFile &F;46 47public:48 // Maximum number of lookup tables we allow before condensing the tables.49 static const int MaxTables = 4;50 51 /// The lookup result is a list of global declaration IDs.52 using data_type = SmallVector<GlobalDeclID, 4>;53 54 struct data_type_builder {55 data_type &Data;56 llvm::DenseSet<GlobalDeclID> Found;57 58 data_type_builder(data_type &D) : Data(D) {}59 60 void insert(GlobalDeclID ID) {61 // Just use a linear scan unless we have more than a few IDs.62 if (Found.empty() && !Data.empty()) {63 if (Data.size() <= 4) {64 for (auto I : Found)65 if (I == ID)66 return;67 Data.push_back(ID);68 return;69 }70 71 // Switch to tracking found IDs in the set.72 Found.insert_range(Data);73 }74 75 if (Found.insert(ID).second)76 Data.push_back(ID);77 }78 };79 using hash_value_type = unsigned;80 using offset_type = unsigned;81 using file_type = ModuleFile *;82 83protected:84 explicit ASTDeclContextNameLookupTraitBase(ASTReader &Reader, ModuleFile &F)85 : Reader(Reader), F(F) {}86 87public:88 static std::pair<unsigned, unsigned>89 ReadKeyDataLength(const unsigned char *&d);90 91 void ReadDataIntoImpl(const unsigned char *d, unsigned DataLen,92 data_type_builder &Val);93 94 static void MergeDataInto(const data_type &From, data_type_builder &To) {95 To.Data.reserve(To.Data.size() + From.size());96 for (GlobalDeclID ID : From)97 To.insert(ID);98 }99 100 file_type ReadFileRef(const unsigned char *&d);101 102 DeclarationNameKey ReadKeyBase(const unsigned char *&d);103};104 105/// Class that performs name lookup into a DeclContext stored106/// in an AST file.107class ASTDeclContextNameLookupTrait : public ASTDeclContextNameLookupTraitBase {108public:109 explicit ASTDeclContextNameLookupTrait(ASTReader &Reader, ModuleFile &F)110 : ASTDeclContextNameLookupTraitBase(Reader, F) {}111 112 using external_key_type = DeclarationName;113 using internal_key_type = DeclarationNameKey;114 115 static bool EqualKey(const internal_key_type &a, const internal_key_type &b) {116 return a == b;117 }118 119 static hash_value_type ComputeHash(const internal_key_type &Key) {120 return Key.getHash();121 }122 123 static internal_key_type GetInternalKey(const external_key_type &Name) {124 return Name;125 }126 127 internal_key_type ReadKey(const unsigned char *d, unsigned);128 129 void ReadDataInto(internal_key_type, const unsigned char *d,130 unsigned DataLen, data_type_builder &Val);131};132 133struct DeclContextLookupTable {134 MultiOnDiskHashTable<ASTDeclContextNameLookupTrait> Table;135};136 137class ModuleLocalNameLookupTrait : public ASTDeclContextNameLookupTraitBase {138public:139 explicit ModuleLocalNameLookupTrait(ASTReader &Reader, ModuleFile &F)140 : ASTDeclContextNameLookupTraitBase(Reader, F) {}141 142 using external_key_type = std::pair<DeclarationName, const Module *>;143 using internal_key_type = std::pair<DeclarationNameKey, unsigned>;144 145 static bool EqualKey(const internal_key_type &a, const internal_key_type &b) {146 return a == b;147 }148 149 static hash_value_type ComputeHash(const internal_key_type &Key);150 static internal_key_type GetInternalKey(const external_key_type &Key);151 152 internal_key_type ReadKey(const unsigned char *d, unsigned);153 154 void ReadDataInto(internal_key_type, const unsigned char *d, unsigned DataLen,155 data_type_builder &Val);156};157 158struct ModuleLocalLookupTable {159 MultiOnDiskHashTable<ModuleLocalNameLookupTrait> Table;160};161 162using LazySpecializationInfo = GlobalDeclID;163 164/// Class that performs lookup to specialized decls.165class LazySpecializationInfoLookupTrait {166 ASTReader &Reader;167 ModuleFile &F;168 169public:170 // Maximum number of lookup tables we allow before condensing the tables.171 static const int MaxTables = 4;172 173 /// The lookup result is a list of global declaration IDs.174 using data_type = SmallVector<LazySpecializationInfo, 4>;175 176 struct data_type_builder {177 data_type &Data;178 llvm::DenseSet<LazySpecializationInfo> Found;179 180 data_type_builder(data_type &D) : Data(D) {}181 182 void insert(LazySpecializationInfo Info) {183 // Just use a linear scan unless we have more than a few IDs.184 if (Found.empty() && !Data.empty()) {185 if (Data.size() <= 4) {186 for (auto I : Found)187 if (I == Info)188 return;189 Data.push_back(Info);190 return;191 }192 193 // Switch to tracking found IDs in the set.194 Found.insert_range(Data);195 }196 197 if (Found.insert(Info).second)198 Data.push_back(Info);199 }200 };201 using hash_value_type = unsigned;202 using offset_type = unsigned;203 using file_type = ModuleFile *;204 205 using external_key_type = unsigned;206 using internal_key_type = unsigned;207 208 explicit LazySpecializationInfoLookupTrait(ASTReader &Reader, ModuleFile &F)209 : Reader(Reader), F(F) {}210 211 static bool EqualKey(const internal_key_type &a, const internal_key_type &b) {212 return a == b;213 }214 215 static hash_value_type ComputeHash(const internal_key_type &Key) {216 return Key;217 }218 219 static internal_key_type GetInternalKey(const external_key_type &Name) {220 return Name;221 }222 223 static std::pair<unsigned, unsigned>224 ReadKeyDataLength(const unsigned char *&d);225 226 internal_key_type ReadKey(const unsigned char *d, unsigned);227 228 void ReadDataInto(internal_key_type, const unsigned char *d, unsigned DataLen,229 data_type_builder &Val);230 231 static void MergeDataInto(const data_type &From, data_type_builder &To) {232 To.Data.reserve(To.Data.size() + From.size());233 for (LazySpecializationInfo Info : From)234 To.insert(Info);235 }236 237 file_type ReadFileRef(const unsigned char *&d);238};239 240struct LazySpecializationInfoLookupTable {241 MultiOnDiskHashTable<LazySpecializationInfoLookupTrait> Table;242};243 244/// Base class for the trait describing the on-disk hash table for the245/// identifiers in an AST file.246///247/// This class is not useful by itself; rather, it provides common248/// functionality for accessing the on-disk hash table of identifiers249/// in an AST file. Different subclasses customize that functionality250/// based on what information they are interested in. Those subclasses251/// must provide the \c data_type type and the ReadData operation, only.252class ASTIdentifierLookupTraitBase {253public:254 using external_key_type = StringRef;255 using internal_key_type = StringRef;256 using hash_value_type = unsigned;257 using offset_type = unsigned;258 259 static bool EqualKey(const internal_key_type& a, const internal_key_type& b) {260 return a == b;261 }262 263 static hash_value_type ComputeHash(const internal_key_type& a);264 265 static std::pair<unsigned, unsigned>266 ReadKeyDataLength(const unsigned char*& d);267 268 // This hopefully will just get inlined and removed by the optimizer.269 static const internal_key_type&270 GetInternalKey(const external_key_type& x) { return x; }271 272 // This hopefully will just get inlined and removed by the optimizer.273 static const external_key_type&274 GetExternalKey(const internal_key_type& x) { return x; }275 276 static internal_key_type ReadKey(const unsigned char* d, unsigned n);277};278 279/// Class that performs lookup for an identifier stored in an AST file.280class ASTIdentifierLookupTrait : public ASTIdentifierLookupTraitBase {281 ASTReader &Reader;282 ModuleFile &F;283 284 // If we know the IdentifierInfo in advance, it is here and we will285 // not build a new one. Used when deserializing information about an286 // identifier that was constructed before the AST file was read.287 IdentifierInfo *KnownII;288 289 bool hasMacroDefinitionInDependencies = false;290 291public:292 using data_type = IdentifierInfo *;293 294 ASTIdentifierLookupTrait(ASTReader &Reader, ModuleFile &F,295 IdentifierInfo *II = nullptr)296 : Reader(Reader), F(F), KnownII(II) {}297 298 data_type ReadData(const internal_key_type& k,299 const unsigned char* d,300 unsigned DataLen);301 302 IdentifierID ReadIdentifierID(const unsigned char *d);303 304 ASTReader &getReader() const { return Reader; }305 306 bool hasMoreInformationInDependencies() const {307 return hasMacroDefinitionInDependencies;308 }309};310 311/// The on-disk hash table used to contain information about312/// all of the identifiers in the program.313using ASTIdentifierLookupTable =314 llvm::OnDiskIterableChainedHashTable<ASTIdentifierLookupTrait>;315 316/// Class that performs lookup for a selector's entries in the global317/// method pool stored in an AST file.318class ASTSelectorLookupTrait {319 ASTReader &Reader;320 ModuleFile &F;321 322public:323 struct data_type {324 SelectorID ID;325 unsigned InstanceBits;326 unsigned FactoryBits;327 bool InstanceHasMoreThanOneDecl;328 bool FactoryHasMoreThanOneDecl;329 SmallVector<ObjCMethodDecl *, 2> Instance;330 SmallVector<ObjCMethodDecl *, 2> Factory;331 };332 333 using external_key_type = Selector;334 using internal_key_type = external_key_type;335 using hash_value_type = unsigned;336 using offset_type = unsigned;337 338 ASTSelectorLookupTrait(ASTReader &Reader, ModuleFile &F)339 : Reader(Reader), F(F) {}340 341 static bool EqualKey(const internal_key_type& a,342 const internal_key_type& b) {343 return a == b;344 }345 346 static hash_value_type ComputeHash(Selector Sel);347 348 static const internal_key_type&349 GetInternalKey(const external_key_type& x) { return x; }350 351 static std::pair<unsigned, unsigned>352 ReadKeyDataLength(const unsigned char*& d);353 354 internal_key_type ReadKey(const unsigned char* d, unsigned);355 data_type ReadData(Selector, const unsigned char* d, unsigned DataLen);356};357 358/// The on-disk hash table used for the global method pool.359using ASTSelectorLookupTable =360 llvm::OnDiskChainedHashTable<ASTSelectorLookupTrait>;361 362/// Trait class used to search the on-disk hash table containing all of363/// the header search information.364///365/// The on-disk hash table contains a mapping from each header path to366/// information about that header (how many times it has been included, its367/// controlling macro, etc.). Note that we actually hash based on the size368/// and mtime, and support "deep" comparisons of file names based on current369/// inode numbers, so that the search can cope with non-normalized path names370/// and symlinks.371class HeaderFileInfoTrait {372 ASTReader &Reader;373 ModuleFile &M;374 375public:376 using external_key_type = FileEntryRef;377 378 struct internal_key_type {379 off_t Size;380 time_t ModTime;381 StringRef Filename;382 bool Imported;383 };384 385 using internal_key_ref = const internal_key_type &;386 387 using data_type = HeaderFileInfo;388 using hash_value_type = unsigned;389 using offset_type = unsigned;390 391 HeaderFileInfoTrait(ASTReader &Reader, ModuleFile &M)392 : Reader(Reader), M(M) {}393 394 static hash_value_type ComputeHash(internal_key_ref ikey);395 internal_key_type GetInternalKey(external_key_type ekey);396 bool EqualKey(internal_key_ref a, internal_key_ref b);397 398 static std::pair<unsigned, unsigned>399 ReadKeyDataLength(const unsigned char*& d);400 401 static internal_key_type ReadKey(const unsigned char *d, unsigned);402 403 data_type ReadData(internal_key_ref,const unsigned char *d, unsigned DataLen);404 405private:406 OptionalFileEntryRef getFile(const internal_key_type &Key);407};408 409/// The on-disk hash table used for known header files.410using HeaderFileInfoLookupTable =411 llvm::OnDiskChainedHashTable<HeaderFileInfoTrait>;412 413} // namespace reader414 415} // namespace serialization416 417} // namespace clang418 419#endif // LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H420