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