1226586Sdim//===--- ASTReaderInternals.h - AST Reader Internals ------------*- C++ -*-===// 2226586Sdim// 3226586Sdim// The LLVM Compiler Infrastructure 4226586Sdim// 5226586Sdim// This file is distributed under the University of Illinois Open Source 6226586Sdim// License. See LICENSE.TXT for details. 7226586Sdim// 8226586Sdim//===----------------------------------------------------------------------===// 9226586Sdim// 10226586Sdim// This file provides internal definitions used in the AST reader. 11226586Sdim// 12226586Sdim//===----------------------------------------------------------------------===// 13226586Sdim#ifndef LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H 14226586Sdim#define LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H 15226586Sdim 16226586Sdim#include "clang/AST/DeclarationName.h" 17226586Sdim#include "clang/Serialization/ASTBitCodes.h" 18226586Sdim#include "llvm/ADT/DenseSet.h" 19249423Sdim#include "llvm/ADT/PointerUnion.h" 20276479Sdim#include "llvm/ADT/TinyPtrVector.h" 21249423Sdim#include "llvm/Support/Endian.h" 22249423Sdim#include "llvm/Support/OnDiskHashTable.h" 23226586Sdim#include "MultiOnDiskHashTable.h" 24226586Sdim#include <utility> 25226586Sdim 26226586Sdimnamespace clang { 27226586Sdim 28226586Sdimclass ASTReader; 29226586Sdimclass HeaderSearch; 30226586Sdimstruct HeaderFileInfo; 31226586Sdimclass FileEntry; 32288943Sdim 33288943Sdimnamespace serialization { 34226586Sdim 35288943Sdimclass ModuleFile; 36288943Sdim 37288943Sdimnamespace reader { 38288943Sdim 39288943Sdim/// \brief Class that performs name lookup into a DeclContext stored 40288943Sdim/// in an AST file. 41288943Sdimclass ASTDeclContextNameLookupTrait { 42288943Sdim ASTReader &Reader; 43288943Sdim ModuleFile &F; 44288943Sdim 45288943Sdimpublic: 46226586Sdim // Maximum number of lookup tables we allow before condensing the tables. 47226586Sdim static const int MaxTables = 4; 48226586Sdim 49288943Sdim /// The lookup result is a list of global declaration IDs. 50288943Sdim typedef llvm::SmallVector<DeclID, 4> data_type; 51288943Sdim struct data_type_builder { 52288943Sdim data_type &Data; 53288943Sdim llvm::DenseSet<DeclID> Found; 54288943Sdim 55288943Sdim data_type_builder(data_type &D) : Data(D) {} 56288943Sdim void insert(DeclID ID) { 57288943Sdim // Just use a linear scan unless we have more than a few IDs. 58288943Sdim if (Found.empty() && !Data.empty()) { 59288943Sdim if (Data.size() <= 4) { 60296417Sdim for (auto I : Found) 61296417Sdim if (I == ID) 62296417Sdim return; 63288943Sdim Data.push_back(ID); 64288943Sdim return; 65288943Sdim } 66288943Sdim 67226586Sdim // Switch to tracking found IDs in the set. 68226586Sdim Found.insert(Data.begin(), Data.end()); 69226586Sdim } 70288943Sdim 71288943Sdim if (Found.insert(ID).second) 72288943Sdim Data.push_back(ID); 73288943Sdim } 74288943Sdim }; 75226586Sdim typedef unsigned hash_value_type; 76226586Sdim typedef unsigned offset_type; 77226586Sdim typedef ModuleFile *file_type; 78226586Sdim 79288943Sdim typedef DeclarationName external_key_type; 80288943Sdim typedef DeclarationNameKey internal_key_type; 81288943Sdim 82226586Sdim explicit ASTDeclContextNameLookupTrait(ASTReader &Reader, ModuleFile &F) 83226586Sdim : Reader(Reader), F(F) { } 84226586Sdim 85226586Sdim static bool EqualKey(const internal_key_type &a, const internal_key_type &b) { 86226586Sdim return a == b; 87288943Sdim } 88226586Sdim 89226586Sdim static hash_value_type ComputeHash(const internal_key_type &Key) { 90226586Sdim return Key.getHash(); 91288943Sdim } 92226586Sdim static internal_key_type GetInternalKey(const external_key_type &Name) { 93226586Sdim return Name; 94226586Sdim } 95226586Sdim 96226586Sdim static std::pair<unsigned, unsigned> 97226586Sdim ReadKeyDataLength(const unsigned char *&d); 98226586Sdim 99226586Sdim internal_key_type ReadKey(const unsigned char *d, unsigned); 100226586Sdim 101226586Sdim void ReadDataInto(internal_key_type, const unsigned char *d, 102226586Sdim unsigned DataLen, data_type_builder &Val); 103226586Sdim 104226586Sdim static void MergeDataInto(const data_type &From, data_type_builder &To) { 105226586Sdim To.Data.reserve(To.Data.size() + From.size()); 106226586Sdim for (DeclID ID : From) 107288943Sdim To.insert(ID); 108288943Sdim } 109226586Sdim 110226586Sdim file_type ReadFileRef(const unsigned char *&d); 111288943Sdim}; 112288943Sdim 113288943Sdimstruct DeclContextLookupTable { 114288943Sdim MultiOnDiskHashTable<ASTDeclContextNameLookupTrait> Table; 115288943Sdim 116288943Sdim // These look redundant, but don't remove them -- they work around MSVC 2013's 117288943Sdim // inability to synthesize move operations. Without them, the 118226586Sdim // MultiOnDiskHashTable will be copied (despite being move-only!). 119226586Sdim DeclContextLookupTable() : Table() {} 120249423Sdim DeclContextLookupTable(DeclContextLookupTable &&O) 121226586Sdim : Table(std::move(O.Table)) {} 122226586Sdim DeclContextLookupTable &operator=(DeclContextLookupTable &&O) { 123226586Sdim Table = std::move(O.Table); 124296417Sdim return *this; 125226586Sdim } 126226586Sdim}; 127226586Sdim 128226586Sdim/// \brief Base class for the trait describing the on-disk hash table for the 129288943Sdim/// identifiers in an AST file. 130226586Sdim/// 131226586Sdim/// This class is not useful by itself; rather, it provides common 132226586Sdim/// functionality for accessing the on-disk hash table of identifiers 133226586Sdim/// in an AST file. Different subclasses customize that functionality 134226586Sdim/// based on what information they are interested in. Those subclasses 135226586Sdim/// must provide the \c data_type typedef and the ReadData operation, 136226586Sdim/// only. 137226586Sdimclass ASTIdentifierLookupTraitBase { 138226586Sdimpublic: 139226586Sdim typedef StringRef external_key_type; 140226586Sdim typedef StringRef internal_key_type; 141226586Sdim typedef unsigned hash_value_type; 142226586Sdim typedef unsigned offset_type; 143226586Sdim 144226586Sdim static bool EqualKey(const internal_key_type& a, const internal_key_type& b) { 145249423Sdim return a == b; 146226586Sdim } 147226586Sdim 148226586Sdim static hash_value_type ComputeHash(const internal_key_type& a); 149226586Sdim 150226586Sdim static std::pair<unsigned, unsigned> 151226586Sdim ReadKeyDataLength(const unsigned char*& d); 152226586Sdim 153226586Sdim // This hopefully will just get inlined and removed by the optimizer. 154226586Sdim static const internal_key_type& 155249423Sdim GetInternalKey(const external_key_type& x) { return x; } 156226586Sdim 157226586Sdim // This hopefully will just get inlined and removed by the optimizer. 158226586Sdim static const external_key_type& 159226586Sdim GetExternalKey(const internal_key_type& x) { return x; } 160226586Sdim 161288943Sdim static internal_key_type ReadKey(const unsigned char* d, unsigned n); 162288943Sdim}; 163288943Sdim 164288943Sdim/// \brief Class that performs lookup for an identifier stored in an AST file. 165288943Sdimclass ASTIdentifierLookupTrait : public ASTIdentifierLookupTraitBase { 166288943Sdim ASTReader &Reader; 167288943Sdim ModuleFile &F; 168288943Sdim 169288943Sdim // If we know the IdentifierInfo in advance, it is here and we will 170288943Sdim // not build a new one. Used when deserializing information about an 171288943Sdim // identifier that was constructed before the AST file was read. 172288943Sdim IdentifierInfo *KnownII; 173288943Sdim 174288943Sdimpublic: 175288943Sdim typedef IdentifierInfo * data_type; 176296417Sdim 177288943Sdim ASTIdentifierLookupTrait(ASTReader &Reader, ModuleFile &F, 178288943Sdim IdentifierInfo *II = nullptr) 179288943Sdim : Reader(Reader), F(F), KnownII(II) { } 180288943Sdim 181288943Sdim data_type ReadData(const internal_key_type& k, 182288943Sdim const unsigned char* d, 183288943Sdim unsigned DataLen); 184288943Sdim 185288943Sdim IdentID ReadIdentifierID(const unsigned char *d); 186288943Sdim 187288943Sdim ASTReader &getReader() const { return Reader; } 188288943Sdim}; 189288943Sdim 190288943Sdim/// \brief The on-disk hash table used to contain information about 191288943Sdim/// all of the identifiers in the program. 192288943Sdimtypedef llvm::OnDiskIterableChainedHashTable<ASTIdentifierLookupTrait> 193288943Sdim ASTIdentifierLookupTable; 194288943Sdim 195288943Sdim/// \brief Class that performs lookup for a selector's entries in the global 196288943Sdim/// method pool stored in an AST file. 197288943Sdimclass ASTSelectorLookupTrait { 198288943Sdim ASTReader &Reader; 199288943Sdim ModuleFile &F; 200288943Sdim 201288943Sdimpublic: 202288943Sdim struct data_type { 203288943Sdim SelectorID ID; 204288943Sdim unsigned InstanceBits; 205288943Sdim unsigned FactoryBits; 206288943Sdim bool InstanceHasMoreThanOneDecl; 207288943Sdim bool FactoryHasMoreThanOneDecl; 208288943Sdim SmallVector<ObjCMethodDecl *, 2> Instance; 209288943Sdim SmallVector<ObjCMethodDecl *, 2> Factory; 210288943Sdim }; 211288943Sdim 212288943Sdim typedef Selector external_key_type; 213288943Sdim typedef external_key_type internal_key_type; 214288943Sdim typedef unsigned hash_value_type; 215288943Sdim typedef unsigned offset_type; 216288943Sdim 217288943Sdim ASTSelectorLookupTrait(ASTReader &Reader, ModuleFile &F) 218288943Sdim : Reader(Reader), F(F) { } 219288943Sdim 220288943Sdim static bool EqualKey(const internal_key_type& a, 221288943Sdim const internal_key_type& b) { 222288943Sdim return a == b; 223288943Sdim } 224288943Sdim 225288943Sdim static hash_value_type ComputeHash(Selector Sel); 226288943Sdim 227288943Sdim static const internal_key_type& 228288943Sdim GetInternalKey(const external_key_type& x) { return x; } 229288943Sdim 230288943Sdim static std::pair<unsigned, unsigned> 231288943Sdim ReadKeyDataLength(const unsigned char*& d); 232288943Sdim 233296417Sdim internal_key_type ReadKey(const unsigned char* d, unsigned); 234288943Sdim data_type ReadData(Selector, const unsigned char* d, unsigned DataLen); 235288943Sdim}; 236288943Sdim 237288943Sdim/// \brief The on-disk hash table used for the global method pool. 238288943Sdimtypedef llvm::OnDiskChainedHashTable<ASTSelectorLookupTrait> 239288943Sdim ASTSelectorLookupTable; 240288943Sdim 241288943Sdim/// \brief Trait class used to search the on-disk hash table containing all of 242288943Sdim/// the header search information. 243288943Sdim/// 244288943Sdim/// The on-disk hash table contains a mapping from each header path to 245288943Sdim/// information about that header (how many times it has been included, its 246288943Sdim/// controlling macro, etc.). Note that we actually hash based on the size 247288943Sdim/// and mtime, and support "deep" comparisons of file names based on current 248288943Sdim/// inode numbers, so that the search can cope with non-normalized path names 249288943Sdim/// and symlinks. 250288943Sdimclass HeaderFileInfoTrait { 251288943Sdim ASTReader &Reader; 252288943Sdim ModuleFile &M; 253288943Sdim HeaderSearch *HS; 254288943Sdim const char *FrameworkStrings; 255288943Sdim 256288943Sdimpublic: 257288943Sdim typedef const FileEntry *external_key_type; 258288943Sdim 259288943Sdim struct internal_key_type { 260288943Sdim off_t Size; 261288943Sdim time_t ModTime; 262288943Sdim const char *Filename; 263288943Sdim bool Imported; 264288943Sdim }; 265288943Sdim typedef const internal_key_type &internal_key_ref; 266288943Sdim 267288943Sdim typedef HeaderFileInfo data_type; 268288943Sdim typedef unsigned hash_value_type; 269288943Sdim typedef unsigned offset_type; 270296417Sdim 271296417Sdim HeaderFileInfoTrait(ASTReader &Reader, ModuleFile &M, HeaderSearch *HS, 272288943Sdim const char *FrameworkStrings) 273288943Sdim : Reader(Reader), M(M), HS(HS), FrameworkStrings(FrameworkStrings) { } 274288943Sdim 275288943Sdim static hash_value_type ComputeHash(internal_key_ref ikey); 276288943Sdim internal_key_type GetInternalKey(const FileEntry *FE); 277288943Sdim bool EqualKey(internal_key_ref a, internal_key_ref b); 278288943Sdim 279288943Sdim static std::pair<unsigned, unsigned> 280288943Sdim ReadKeyDataLength(const unsigned char*& d); 281288943Sdim 282288943Sdim static internal_key_type ReadKey(const unsigned char *d, unsigned); 283288943Sdim 284288943Sdim data_type ReadData(internal_key_ref,const unsigned char *d, unsigned DataLen); 285288943Sdim}; 286288943Sdim 287288943Sdim/// \brief The on-disk hash table used for known header files. 288288943Sdimtypedef llvm::OnDiskChainedHashTable<HeaderFileInfoTrait> 289288943Sdim HeaderFileInfoLookupTable; 290288943Sdim 291288943Sdim} // end namespace clang::serialization::reader 292288943Sdim} // end namespace clang::serialization 293288943Sdim} // end namespace clang 294288943Sdim 295288943Sdim 296288943Sdim#endif 297288943Sdim