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