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