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
27namespace clang {
28
29class ASTReader;
30class FileEntry;
31struct HeaderFileInfo;
32class HeaderSearch;
33class ObjCMethodDecl;
34class Module;
35
36namespace serialization {
37
38class ModuleFile;
39
40namespace reader {
41
42class ASTDeclContextNameLookupTraitBase {
43protected:
44 ASTReader &Reader;
45 ModuleFile &F;
46
47public:
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
83protected:
84 explicit ASTDeclContextNameLookupTraitBase(ASTReader &Reader, ModuleFile &F)
85 : Reader(Reader), F(F) {}
86
87public:
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.
107class ASTDeclContextNameLookupTrait : public ASTDeclContextNameLookupTraitBase {
108public:
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
133struct DeclContextLookupTable {
134 MultiOnDiskHashTable<ASTDeclContextNameLookupTrait> Table;
135};
136
137class ModuleLocalNameLookupTrait : public ASTDeclContextNameLookupTraitBase {
138public:
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
158struct ModuleLocalLookupTable {
159 MultiOnDiskHashTable<ModuleLocalNameLookupTrait> Table;
160};
161
162using LazySpecializationInfo = GlobalDeclID;
163
164/// Class that performs lookup to specialized decls.
165class LazySpecializationInfoLookupTrait {
166 ASTReader &Reader;
167 ModuleFile &F;
168
169public:
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
240struct 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.
252class ASTIdentifierLookupTraitBase {
253public:
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.
280class 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
291public:
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.
313using 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.
318class ASTSelectorLookupTrait {
319 ASTReader &Reader;
320 ModuleFile &F;
321
322public:
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.
359using 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.
371class HeaderFileInfoTrait {
372 ASTReader &Reader;
373 ModuleFile &M;
374
375public:
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
405private:
406 OptionalFileEntryRef getFile(const internal_key_type &Key);
407};
408
409/// The on-disk hash table used for known header files.
410using 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