contrib/llvm/tools/clang/lib/Serialization/ASTReaderInternals.h

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