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 | class Module; |
35 | |
36 | namespace serialization { |
37 | |
38 | class ModuleFile; |
39 | |
40 | namespace reader { |
41 | |
42 | class ASTDeclContextNameLookupTraitBase { |
43 | protected: |
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<GlobalDeclID, 4>; |
53 | |
54 | struct data_type_builder { |
55 | data_type &Data; |
56 | llvm::DenseSet<GlobalDeclID> Found; |
57 | |
58 | data_type_builder(data_type &D) : Data(D) {} |
59 | |
60 | void insert(GlobalDeclID 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(Elt: ID); |
68 | return; |
69 | } |
70 | |
71 | // Switch to tracking found IDs in the set. |
72 | Found.insert_range(R&: Data); |
73 | } |
74 | |
75 | if (Found.insert(V: ID).second) |
76 | Data.push_back(Elt: ID); |
77 | } |
78 | }; |
79 | using hash_value_type = unsigned; |
80 | using offset_type = unsigned; |
81 | using file_type = ModuleFile *; |
82 | |
83 | protected: |
84 | explicit ASTDeclContextNameLookupTraitBase(ASTReader &Reader, ModuleFile &F) |
85 | : Reader(Reader), F(F) {} |
86 | |
87 | public: |
88 | static std::pair<unsigned, unsigned> |
89 | ReadKeyDataLength(const unsigned char *&d); |
90 | |
91 | void ReadDataIntoImpl(const unsigned char *d, unsigned DataLen, |
92 | data_type_builder &Val); |
93 | |
94 | static void MergeDataInto(const data_type &From, data_type_builder &To) { |
95 | To.Data.reserve(N: To.Data.size() + From.size()); |
96 | for (GlobalDeclID ID : From) |
97 | To.insert(ID); |
98 | } |
99 | |
100 | file_type ReadFileRef(const unsigned char *&d); |
101 | |
102 | DeclarationNameKey ReadKeyBase(const unsigned char *&d); |
103 | }; |
104 | |
105 | /// Class that performs name lookup into a DeclContext stored |
106 | /// in an AST file. |
107 | class ASTDeclContextNameLookupTrait : public ASTDeclContextNameLookupTraitBase { |
108 | public: |
109 | explicit ASTDeclContextNameLookupTrait(ASTReader &Reader, ModuleFile &F) |
110 | : ASTDeclContextNameLookupTraitBase(Reader, F) {} |
111 | |
112 | using external_key_type = DeclarationName; |
113 | using internal_key_type = DeclarationNameKey; |
114 | |
115 | static bool EqualKey(const internal_key_type &a, const internal_key_type &b) { |
116 | return a == b; |
117 | } |
118 | |
119 | static hash_value_type ComputeHash(const internal_key_type &Key) { |
120 | return Key.getHash(); |
121 | } |
122 | |
123 | static internal_key_type GetInternalKey(const external_key_type &Name) { |
124 | return Name; |
125 | } |
126 | |
127 | internal_key_type ReadKey(const unsigned char *d, unsigned); |
128 | |
129 | void ReadDataInto(internal_key_type, const unsigned char *d, |
130 | unsigned DataLen, data_type_builder &Val); |
131 | }; |
132 | |
133 | struct DeclContextLookupTable { |
134 | MultiOnDiskHashTable<ASTDeclContextNameLookupTrait> Table; |
135 | }; |
136 | |
137 | class ModuleLocalNameLookupTrait : public ASTDeclContextNameLookupTraitBase { |
138 | public: |
139 | explicit ModuleLocalNameLookupTrait(ASTReader &Reader, ModuleFile &F) |
140 | : ASTDeclContextNameLookupTraitBase(Reader, F) {} |
141 | |
142 | using external_key_type = std::pair<DeclarationName, const Module *>; |
143 | using internal_key_type = std::pair<DeclarationNameKey, unsigned>; |
144 | |
145 | static bool EqualKey(const internal_key_type &a, const internal_key_type &b) { |
146 | return a == b; |
147 | } |
148 | |
149 | static hash_value_type ComputeHash(const internal_key_type &Key); |
150 | static internal_key_type GetInternalKey(const external_key_type &Key); |
151 | |
152 | internal_key_type ReadKey(const unsigned char *d, unsigned); |
153 | |
154 | void ReadDataInto(internal_key_type, const unsigned char *d, unsigned DataLen, |
155 | data_type_builder &Val); |
156 | }; |
157 | |
158 | struct ModuleLocalLookupTable { |
159 | MultiOnDiskHashTable<ModuleLocalNameLookupTrait> Table; |
160 | }; |
161 | |
162 | using LazySpecializationInfo = GlobalDeclID; |
163 | |
164 | /// Class that performs lookup to specialized decls. |
165 | class LazySpecializationInfoLookupTrait { |
166 | ASTReader &Reader; |
167 | ModuleFile &F; |
168 | |
169 | public: |
170 | // Maximum number of lookup tables we allow before condensing the tables. |
171 | static const int MaxTables = 4; |
172 | |
173 | /// The lookup result is a list of global declaration IDs. |
174 | using data_type = SmallVector<LazySpecializationInfo, 4>; |
175 | |
176 | struct data_type_builder { |
177 | data_type &Data; |
178 | llvm::DenseSet<LazySpecializationInfo> Found; |
179 | |
180 | data_type_builder(data_type &D) : Data(D) {} |
181 | |
182 | void insert(LazySpecializationInfo Info) { |
183 | // Just use a linear scan unless we have more than a few IDs. |
184 | if (Found.empty() && !Data.empty()) { |
185 | if (Data.size() <= 4) { |
186 | for (auto I : Found) |
187 | if (I == Info) |
188 | return; |
189 | Data.push_back(Elt: Info); |
190 | return; |
191 | } |
192 | |
193 | // Switch to tracking found IDs in the set. |
194 | Found.insert_range(R&: Data); |
195 | } |
196 | |
197 | if (Found.insert(V: Info).second) |
198 | Data.push_back(Elt: Info); |
199 | } |
200 | }; |
201 | using hash_value_type = unsigned; |
202 | using offset_type = unsigned; |
203 | using file_type = ModuleFile *; |
204 | |
205 | using external_key_type = unsigned; |
206 | using internal_key_type = unsigned; |
207 | |
208 | explicit LazySpecializationInfoLookupTrait(ASTReader &Reader, ModuleFile &F) |
209 | : Reader(Reader), F(F) {} |
210 | |
211 | static bool EqualKey(const internal_key_type &a, const internal_key_type &b) { |
212 | return a == b; |
213 | } |
214 | |
215 | static hash_value_type ComputeHash(const internal_key_type &Key) { |
216 | return Key; |
217 | } |
218 | |
219 | static internal_key_type GetInternalKey(const external_key_type &Name) { |
220 | return Name; |
221 | } |
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 | |
228 | void ReadDataInto(internal_key_type, const unsigned char *d, unsigned DataLen, |
229 | data_type_builder &Val); |
230 | |
231 | static void MergeDataInto(const data_type &From, data_type_builder &To) { |
232 | To.Data.reserve(N: To.Data.size() + From.size()); |
233 | for (LazySpecializationInfo Info : From) |
234 | To.insert(Info); |
235 | } |
236 | |
237 | file_type ReadFileRef(const unsigned char *&d); |
238 | }; |
239 | |
240 | struct LazySpecializationInfoLookupTable { |
241 | MultiOnDiskHashTable<LazySpecializationInfoLookupTrait> Table; |
242 | }; |
243 | |
244 | /// Base class for the trait describing the on-disk hash table for the |
245 | /// identifiers in an AST file. |
246 | /// |
247 | /// This class is not useful by itself; rather, it provides common |
248 | /// functionality for accessing the on-disk hash table of identifiers |
249 | /// in an AST file. Different subclasses customize that functionality |
250 | /// based on what information they are interested in. Those subclasses |
251 | /// must provide the \c data_type type and the ReadData operation, only. |
252 | class ASTIdentifierLookupTraitBase { |
253 | public: |
254 | using external_key_type = StringRef; |
255 | using internal_key_type = StringRef; |
256 | using hash_value_type = unsigned; |
257 | using offset_type = unsigned; |
258 | |
259 | static bool EqualKey(const internal_key_type& a, const internal_key_type& b) { |
260 | return a == b; |
261 | } |
262 | |
263 | static hash_value_type ComputeHash(const internal_key_type& a); |
264 | |
265 | static std::pair<unsigned, unsigned> |
266 | ReadKeyDataLength(const unsigned char*& d); |
267 | |
268 | // This hopefully will just get inlined and removed by the optimizer. |
269 | static const internal_key_type& |
270 | GetInternalKey(const external_key_type& x) { return x; } |
271 | |
272 | // This hopefully will just get inlined and removed by the optimizer. |
273 | static const external_key_type& |
274 | GetExternalKey(const internal_key_type& x) { return x; } |
275 | |
276 | static internal_key_type ReadKey(const unsigned char* d, unsigned n); |
277 | }; |
278 | |
279 | /// Class that performs lookup for an identifier stored in an AST file. |
280 | class ASTIdentifierLookupTrait : public ASTIdentifierLookupTraitBase { |
281 | ASTReader &Reader; |
282 | ModuleFile &F; |
283 | |
284 | // If we know the IdentifierInfo in advance, it is here and we will |
285 | // not build a new one. Used when deserializing information about an |
286 | // identifier that was constructed before the AST file was read. |
287 | IdentifierInfo *KnownII; |
288 | |
289 | bool hasMacroDefinitionInDependencies = false; |
290 | |
291 | public: |
292 | using data_type = IdentifierInfo *; |
293 | |
294 | ASTIdentifierLookupTrait(ASTReader &Reader, ModuleFile &F, |
295 | IdentifierInfo *II = nullptr) |
296 | : Reader(Reader), F(F), KnownII(II) {} |
297 | |
298 | data_type ReadData(const internal_key_type& k, |
299 | const unsigned char* d, |
300 | unsigned DataLen); |
301 | |
302 | IdentifierID ReadIdentifierID(const unsigned char *d); |
303 | |
304 | ASTReader &getReader() const { return Reader; } |
305 | |
306 | bool hasMoreInformationInDependencies() const { |
307 | return hasMacroDefinitionInDependencies; |
308 | } |
309 | }; |
310 | |
311 | /// The on-disk hash table used to contain information about |
312 | /// all of the identifiers in the program. |
313 | using ASTIdentifierLookupTable = |
314 | llvm::OnDiskIterableChainedHashTable<ASTIdentifierLookupTrait>; |
315 | |
316 | /// Class that performs lookup for a selector's entries in the global |
317 | /// method pool stored in an AST file. |
318 | class ASTSelectorLookupTrait { |
319 | ASTReader &Reader; |
320 | ModuleFile &F; |
321 | |
322 | public: |
323 | struct data_type { |
324 | SelectorID ID; |
325 | unsigned InstanceBits; |
326 | unsigned FactoryBits; |
327 | bool InstanceHasMoreThanOneDecl; |
328 | bool FactoryHasMoreThanOneDecl; |
329 | SmallVector<ObjCMethodDecl *, 2> Instance; |
330 | SmallVector<ObjCMethodDecl *, 2> Factory; |
331 | }; |
332 | |
333 | using external_key_type = Selector; |
334 | using internal_key_type = external_key_type; |
335 | using hash_value_type = unsigned; |
336 | using offset_type = unsigned; |
337 | |
338 | ASTSelectorLookupTrait(ASTReader &Reader, ModuleFile &F) |
339 | : Reader(Reader), F(F) {} |
340 | |
341 | static bool EqualKey(const internal_key_type& a, |
342 | const internal_key_type& b) { |
343 | return a == b; |
344 | } |
345 | |
346 | static hash_value_type ComputeHash(Selector Sel); |
347 | |
348 | static const internal_key_type& |
349 | GetInternalKey(const external_key_type& x) { return x; } |
350 | |
351 | static std::pair<unsigned, unsigned> |
352 | ReadKeyDataLength(const unsigned char*& d); |
353 | |
354 | internal_key_type ReadKey(const unsigned char* d, unsigned); |
355 | data_type ReadData(Selector, const unsigned char* d, unsigned DataLen); |
356 | }; |
357 | |
358 | /// The on-disk hash table used for the global method pool. |
359 | using ASTSelectorLookupTable = |
360 | llvm::OnDiskChainedHashTable<ASTSelectorLookupTrait>; |
361 | |
362 | /// Trait class used to search the on-disk hash table containing all of |
363 | /// the header search information. |
364 | /// |
365 | /// The on-disk hash table contains a mapping from each header path to |
366 | /// information about that header (how many times it has been included, its |
367 | /// controlling macro, etc.). Note that we actually hash based on the size |
368 | /// and mtime, and support "deep" comparisons of file names based on current |
369 | /// inode numbers, so that the search can cope with non-normalized path names |
370 | /// and symlinks. |
371 | class HeaderFileInfoTrait { |
372 | ASTReader &Reader; |
373 | ModuleFile &M; |
374 | |
375 | public: |
376 | using external_key_type = FileEntryRef; |
377 | |
378 | struct internal_key_type { |
379 | off_t Size; |
380 | time_t ModTime; |
381 | StringRef Filename; |
382 | bool Imported; |
383 | }; |
384 | |
385 | using internal_key_ref = const internal_key_type &; |
386 | |
387 | using data_type = HeaderFileInfo; |
388 | using hash_value_type = unsigned; |
389 | using offset_type = unsigned; |
390 | |
391 | HeaderFileInfoTrait(ASTReader &Reader, ModuleFile &M) |
392 | : Reader(Reader), M(M) {} |
393 | |
394 | static hash_value_type ComputeHash(internal_key_ref ikey); |
395 | internal_key_type GetInternalKey(external_key_type ekey); |
396 | bool EqualKey(internal_key_ref a, internal_key_ref b); |
397 | |
398 | static std::pair<unsigned, unsigned> |
399 | ReadKeyDataLength(const unsigned char*& d); |
400 | |
401 | static internal_key_type ReadKey(const unsigned char *d, unsigned); |
402 | |
403 | data_type ReadData(internal_key_ref,const unsigned char *d, unsigned DataLen); |
404 | |
405 | private: |
406 | OptionalFileEntryRef getFile(const internal_key_type &Key); |
407 | }; |
408 | |
409 | /// The on-disk hash table used for known header files. |
410 | using HeaderFileInfoLookupTable = |
411 | llvm::OnDiskChainedHashTable<HeaderFileInfoTrait>; |
412 | |
413 | } // namespace reader |
414 | |
415 | } // namespace serialization |
416 | |
417 | } // namespace clang |
418 | |
419 | #endif // LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H |
420 |
Definitions
- ASTDeclContextNameLookupTraitBase
- data_type_builder
- data_type_builder
- insert
- ASTDeclContextNameLookupTraitBase
- MergeDataInto
- ASTDeclContextNameLookupTrait
- ASTDeclContextNameLookupTrait
- EqualKey
- ComputeHash
- GetInternalKey
- DeclContextLookupTable
- ModuleLocalNameLookupTrait
- ModuleLocalNameLookupTrait
- EqualKey
- ModuleLocalLookupTable
- LazySpecializationInfoLookupTrait
- data_type_builder
- data_type_builder
- insert
- LazySpecializationInfoLookupTrait
- EqualKey
- ComputeHash
- GetInternalKey
- MergeDataInto
- LazySpecializationInfoLookupTable
- ASTIdentifierLookupTraitBase
- EqualKey
- GetInternalKey
- GetExternalKey
- ASTIdentifierLookupTrait
- ASTIdentifierLookupTrait
- getReader
- hasMoreInformationInDependencies
- ASTSelectorLookupTrait
- data_type
- ASTSelectorLookupTrait
- EqualKey
- GetInternalKey
- HeaderFileInfoTrait
- internal_key_type
Improve your Profiling and Debugging skills
Find out more