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