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;
34
35namespace serialization {
36
37class ModuleFile;
38
39namespace reader {
40
41/// Class that performs name lookup into a DeclContext stored
42/// in an AST file.
43class ASTDeclContextNameLookupTrait {
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(I: Data.begin(), E: Data.end());
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 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(N: To.Data.size() + From.size());
111 for (GlobalDeclID ID : From)
112 To.insert(ID);
113 }
114
115 file_type ReadFileRef(const unsigned char *&d);
116};
117
118struct 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.
130class ASTIdentifierLookupTraitBase {
131public:
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.
158class 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
167public:
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 IdentifierID 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.
185using 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.
190class ASTSelectorLookupTrait {
191 ASTReader &Reader;
192 ModuleFile &F;
193
194public:
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.
231using 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.
243class HeaderFileInfoTrait {
244 ASTReader &Reader;
245 ModuleFile &M;
246 HeaderSearch *HS;
247 const char *FrameworkStrings;
248
249public:
250 using external_key_type = FileEntryRef;
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(external_key_type ekey);
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
280private:
281 const FileEntry *getFile(const internal_key_type &Key);
282};
283
284/// The on-disk hash table used for known header files.
285using HeaderFileInfoLookupTable =
286 llvm::OnDiskChainedHashTable<HeaderFileInfoTrait>;
287
288} // namespace reader
289
290} // namespace serialization
291
292} // namespace clang
293
294#endif // LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H
295