• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
data_type_builderdata_type_builder55     data_type_builder(data_type &D) : Data(D) {}
insertdata_type_builder56     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 
ASTDeclContextNameLookupTrait(ASTReader & Reader,ModuleFile & F)82   explicit ASTDeclContextNameLookupTrait(ASTReader &Reader, ModuleFile &F)
83     : Reader(Reader), F(F) { }
84 
EqualKey(const internal_key_type & a,const internal_key_type & b)85   static bool EqualKey(const internal_key_type &a, const internal_key_type &b) {
86     return a == b;
87   }
88 
ComputeHash(const internal_key_type & Key)89   static hash_value_type ComputeHash(const internal_key_type &Key) {
90     return Key.getHash();
91   }
GetInternalKey(const external_key_type & Name)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 
MergeDataInto(const data_type & From,data_type_builder & To)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!).
DeclContextLookupTableDeclContextLookupTable119   DeclContextLookupTable() : Table() {}
DeclContextLookupTableDeclContextLookupTable120   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 
EqualKey(const internal_key_type & a,const internal_key_type & b)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&
GetInternalKey(const external_key_type & x)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&
GetExternalKey(const internal_key_type & x)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)
Reader(Reader)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 
getReader()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 
ASTSelectorLookupTrait(ASTReader & Reader,ModuleFile & F)217   ASTSelectorLookupTrait(ASTReader &Reader, ModuleFile &F)
218     : Reader(Reader), F(F) { }
219 
EqualKey(const internal_key_type & a,const internal_key_type & b)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&
GetInternalKey(const external_key_type & x)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 
HeaderFileInfoTrait(ASTReader & Reader,ModuleFile & M,HeaderSearch * HS,const char * FrameworkStrings)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
297