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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file provides internal definitions used in the AST reader. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H 14 #define LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H 15 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 27 namespace clang { 28 29 class ASTReader; 30 class FileEntry; 31 struct HeaderFileInfo; 32 class HeaderSearch; 33 class ObjCMethodDecl; 34 35 namespace serialization { 36 37 class ModuleFile; 38 39 namespace reader { 40 41 /// Class that performs name lookup into a DeclContext stored 42 /// in an AST file. 43 class ASTDeclContextNameLookupTrait { 44 ASTReader &Reader; 45 ModuleFile &F; 46 47 public: 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<DeclID, 4>; 53 54 struct data_type_builder { 55 data_type &Data; 56 llvm::DenseSet<DeclID> Found; 57 58 data_type_builder(data_type &D) : Data(D) {} 59 60 void insert(DeclID 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(Data.begin(), Data.end()); 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 83 using external_key_type = DeclarationName; 84 using internal_key_type = DeclarationNameKey; 85 86 explicit ASTDeclContextNameLookupTrait(ASTReader &Reader, ModuleFile &F) 87 : Reader(Reader), F(F) {} 88 89 static bool EqualKey(const internal_key_type &a, const internal_key_type &b) { 90 return a == b; 91 } 92 93 static hash_value_type ComputeHash(const internal_key_type &Key) { 94 return Key.getHash(); 95 } 96 97 static internal_key_type GetInternalKey(const external_key_type &Name) { 98 return Name; 99 } 100 101 static std::pair<unsigned, unsigned> 102 ReadKeyDataLength(const unsigned char *&d); 103 104 internal_key_type ReadKey(const unsigned char *d, unsigned); 105 106 void ReadDataInto(internal_key_type, const unsigned char *d, 107 unsigned DataLen, data_type_builder &Val); 108 109 static void MergeDataInto(const data_type &From, data_type_builder &To) { 110 To.Data.reserve(To.Data.size() + From.size()); 111 for (DeclID ID : From) 112 To.insert(ID); 113 } 114 115 file_type ReadFileRef(const unsigned char *&d); 116 }; 117 118 struct DeclContextLookupTable { 119 MultiOnDiskHashTable<ASTDeclContextNameLookupTrait> Table; 120 }; 121 122 /// Base class for the trait describing the on-disk hash table for the 123 /// identifiers in an AST file. 124 /// 125 /// This class is not useful by itself; rather, it provides common 126 /// functionality for accessing the on-disk hash table of identifiers 127 /// in an AST file. Different subclasses customize that functionality 128 /// based on what information they are interested in. Those subclasses 129 /// must provide the \c data_type type and the ReadData operation, only. 130 class ASTIdentifierLookupTraitBase { 131 public: 132 using external_key_type = StringRef; 133 using internal_key_type = StringRef; 134 using hash_value_type = unsigned; 135 using offset_type = unsigned; 136 137 static bool EqualKey(const internal_key_type& a, const internal_key_type& b) { 138 return a == b; 139 } 140 141 static hash_value_type ComputeHash(const internal_key_type& a); 142 143 static std::pair<unsigned, unsigned> 144 ReadKeyDataLength(const unsigned char*& d); 145 146 // This hopefully will just get inlined and removed by the optimizer. 147 static const internal_key_type& 148 GetInternalKey(const external_key_type& x) { return x; } 149 150 // This hopefully will just get inlined and removed by the optimizer. 151 static const external_key_type& 152 GetExternalKey(const internal_key_type& x) { return x; } 153 154 static internal_key_type ReadKey(const unsigned char* d, unsigned n); 155 }; 156 157 /// Class that performs lookup for an identifier stored in an AST file. 158 class ASTIdentifierLookupTrait : public ASTIdentifierLookupTraitBase { 159 ASTReader &Reader; 160 ModuleFile &F; 161 162 // If we know the IdentifierInfo in advance, it is here and we will 163 // not build a new one. Used when deserializing information about an 164 // identifier that was constructed before the AST file was read. 165 IdentifierInfo *KnownII; 166 167 public: 168 using data_type = IdentifierInfo *; 169 170 ASTIdentifierLookupTrait(ASTReader &Reader, ModuleFile &F, 171 IdentifierInfo *II = nullptr) 172 : Reader(Reader), F(F), KnownII(II) {} 173 174 data_type ReadData(const internal_key_type& k, 175 const unsigned char* d, 176 unsigned DataLen); 177 178 IdentID ReadIdentifierID(const unsigned char *d); 179 180 ASTReader &getReader() const { return Reader; } 181 }; 182 183 /// The on-disk hash table used to contain information about 184 /// all of the identifiers in the program. 185 using ASTIdentifierLookupTable = 186 llvm::OnDiskIterableChainedHashTable<ASTIdentifierLookupTrait>; 187 188 /// Class that performs lookup for a selector's entries in the global 189 /// method pool stored in an AST file. 190 class ASTSelectorLookupTrait { 191 ASTReader &Reader; 192 ModuleFile &F; 193 194 public: 195 struct data_type { 196 SelectorID ID; 197 unsigned InstanceBits; 198 unsigned FactoryBits; 199 bool InstanceHasMoreThanOneDecl; 200 bool FactoryHasMoreThanOneDecl; 201 SmallVector<ObjCMethodDecl *, 2> Instance; 202 SmallVector<ObjCMethodDecl *, 2> Factory; 203 }; 204 205 using external_key_type = Selector; 206 using internal_key_type = external_key_type; 207 using hash_value_type = unsigned; 208 using offset_type = unsigned; 209 210 ASTSelectorLookupTrait(ASTReader &Reader, ModuleFile &F) 211 : Reader(Reader), F(F) {} 212 213 static bool EqualKey(const internal_key_type& a, 214 const internal_key_type& b) { 215 return a == b; 216 } 217 218 static hash_value_type ComputeHash(Selector Sel); 219 220 static const internal_key_type& 221 GetInternalKey(const external_key_type& x) { return x; } 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 data_type ReadData(Selector, const unsigned char* d, unsigned DataLen); 228 }; 229 230 /// The on-disk hash table used for the global method pool. 231 using ASTSelectorLookupTable = 232 llvm::OnDiskChainedHashTable<ASTSelectorLookupTrait>; 233 234 /// Trait class used to search the on-disk hash table containing all of 235 /// the header search information. 236 /// 237 /// The on-disk hash table contains a mapping from each header path to 238 /// information about that header (how many times it has been included, its 239 /// controlling macro, etc.). Note that we actually hash based on the size 240 /// and mtime, and support "deep" comparisons of file names based on current 241 /// inode numbers, so that the search can cope with non-normalized path names 242 /// and symlinks. 243 class HeaderFileInfoTrait { 244 ASTReader &Reader; 245 ModuleFile &M; 246 HeaderSearch *HS; 247 const char *FrameworkStrings; 248 249 public: 250 using external_key_type = const FileEntry *; 251 252 struct internal_key_type { 253 off_t Size; 254 time_t ModTime; 255 StringRef Filename; 256 bool Imported; 257 }; 258 259 using internal_key_ref = const internal_key_type &; 260 261 using data_type = HeaderFileInfo; 262 using hash_value_type = unsigned; 263 using offset_type = unsigned; 264 265 HeaderFileInfoTrait(ASTReader &Reader, ModuleFile &M, HeaderSearch *HS, 266 const char *FrameworkStrings) 267 : Reader(Reader), M(M), HS(HS), FrameworkStrings(FrameworkStrings) {} 268 269 static hash_value_type ComputeHash(internal_key_ref ikey); 270 internal_key_type GetInternalKey(const FileEntry *FE); 271 bool EqualKey(internal_key_ref a, internal_key_ref b); 272 273 static std::pair<unsigned, unsigned> 274 ReadKeyDataLength(const unsigned char*& d); 275 276 static internal_key_type ReadKey(const unsigned char *d, unsigned); 277 278 data_type ReadData(internal_key_ref,const unsigned char *d, unsigned DataLen); 279 280 private: 281 const FileEntry *getFile(const internal_key_type &Key); 282 }; 283 284 /// The on-disk hash table used for known header files. 285 using HeaderFileInfoLookupTable = 286 llvm::OnDiskChainedHashTable<HeaderFileInfoTrait>; 287 288 } // namespace reader 289 290 } // namespace serialization 291 292 } // namespace clang 293 294 #endif // LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H 295