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
284