clang/lib/Serialization/ASTReaderInternals.h

   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<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(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 (GlobalDeclID 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   IdentifierID 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
 247 public:
 248   using external_key_type = FileEntryRef;
 249
 250   struct internal_key_type {
 251     off_t Size;
 252     time_t ModTime;
 253     StringRef Filename;
 254     bool Imported;
 255   };
 256
 257   using internal_key_ref = const internal_key_type &;
 258
 259   using data_type = HeaderFileInfo;
 260   using hash_value_type = unsigned;
 261   using offset_type = unsigned;
 262
 263   HeaderFileInfoTrait(ASTReader &Reader, ModuleFile &M)
 264       : Reader(Reader), M(M) {}
 265
 266   static hash_value_type ComputeHash(internal_key_ref ikey);
 267   internal_key_type GetInternalKey(external_key_type ekey);
 268   bool EqualKey(internal_key_ref a, internal_key_ref b);
 269
 270   static std::pair<unsigned, unsigned>
 271   ReadKeyDataLength(const unsigned char*& d);
 272
 273   static internal_key_type ReadKey(const unsigned char *d, unsigned);
 274
 275   data_type ReadData(internal_key_ref,const unsigned char *d, unsigned DataLen);
 276
 277 private:
 278   OptionalFileEntryRef getFile(const internal_key_type &Key);
 279 };
 280
 281 /// The on-disk hash table used for known header files.
 282 using HeaderFileInfoLookupTable =
 283     llvm::OnDiskChainedHashTable<HeaderFileInfoTrait>;
 284
 285 } // namespace reader
 286
 287 } // namespace serialization
 288
 289 } // namespace clang
 290
 291 #endif // LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H