1 | //===- DeclContextInternals.h - DeclContext Representation ------*- 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 defines the data structures used in the implementation |
10 | // of DeclContext. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H |
15 | #define LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H |
16 | |
17 | #include "clang/AST/ASTContext.h" |
18 | #include "clang/AST/Decl.h" |
19 | #include "clang/AST/DeclBase.h" |
20 | #include "clang/AST/DeclCXX.h" |
21 | #include "clang/AST/DeclarationName.h" |
22 | #include "llvm/ADT/DenseMap.h" |
23 | #include "llvm/ADT/PointerIntPair.h" |
24 | #include "llvm/ADT/PointerUnion.h" |
25 | #include <cassert> |
26 | |
27 | namespace clang { |
28 | |
29 | class DependentDiagnostic; |
30 | |
31 | /// An array of decls optimized for the common case of only containing |
32 | /// one entry. |
33 | class StoredDeclsList { |
34 | using Decls = DeclListNode::Decls; |
35 | |
36 | /// A collection of declarations, with a flag to indicate if we have |
37 | /// further external declarations. |
38 | using DeclsAndHasExternalTy = llvm::PointerIntPair<Decls, 1, bool>; |
39 | |
40 | /// The stored data, which will be either a pointer to a NamedDecl, |
41 | /// or a pointer to a list with a flag to indicate if there are further |
42 | /// external declarations. |
43 | DeclsAndHasExternalTy Data; |
44 | |
45 | template<typename Fn> |
46 | void erase_if(Fn ShouldErase) { |
47 | Decls List = Data.getPointer(); |
48 | if (!List) |
49 | return; |
50 | ASTContext &C = getASTContext(); |
51 | DeclListNode::Decls NewHead = nullptr; |
52 | DeclListNode::Decls *NewLast = nullptr; |
53 | DeclListNode::Decls *NewTail = &NewHead; |
54 | while (true) { |
55 | if (!ShouldErase(*DeclListNode::iterator(List))) { |
56 | NewLast = NewTail; |
57 | *NewTail = List; |
58 | if (auto *Node = List.dyn_cast<DeclListNode*>()) { |
59 | NewTail = &Node->Rest; |
60 | List = Node->Rest; |
61 | } else { |
62 | break; |
63 | } |
64 | } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) { |
65 | List = N->Rest; |
66 | C.DeallocateDeclListNode(N); |
67 | } else { |
68 | // We're discarding the last declaration in the list. The last node we |
69 | // want to keep (if any) will be of the form DeclListNode(D, <rest>); |
70 | // replace it with just D. |
71 | if (NewLast) { |
72 | DeclListNode *Node = NewLast->get<DeclListNode*>(); |
73 | *NewLast = Node->D; |
74 | C.DeallocateDeclListNode(N: Node); |
75 | } |
76 | break; |
77 | } |
78 | } |
79 | Data.setPointer(NewHead); |
80 | |
81 | assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!" ); |
82 | } |
83 | |
84 | void erase(NamedDecl *ND) { |
85 | erase_if(ShouldErase: [ND](NamedDecl *D) { return D == ND; }); |
86 | } |
87 | |
88 | public: |
89 | StoredDeclsList() = default; |
90 | |
91 | StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) { |
92 | RHS.Data.setPointer(nullptr); |
93 | RHS.Data.setInt(false); |
94 | } |
95 | |
96 | void MaybeDeallocList() { |
97 | if (isNull()) |
98 | return; |
99 | // If this is a list-form, free the list. |
100 | ASTContext &C = getASTContext(); |
101 | Decls List = Data.getPointer(); |
102 | while (DeclListNode *ToDealloc = List.dyn_cast<DeclListNode *>()) { |
103 | List = ToDealloc->Rest; |
104 | C.DeallocateDeclListNode(N: ToDealloc); |
105 | } |
106 | } |
107 | |
108 | ~StoredDeclsList() { |
109 | MaybeDeallocList(); |
110 | } |
111 | |
112 | StoredDeclsList &operator=(StoredDeclsList &&RHS) { |
113 | MaybeDeallocList(); |
114 | |
115 | Data = RHS.Data; |
116 | RHS.Data.setPointer(nullptr); |
117 | RHS.Data.setInt(false); |
118 | return *this; |
119 | } |
120 | |
121 | bool isNull() const { return Data.getPointer().isNull(); } |
122 | |
123 | ASTContext &getASTContext() { |
124 | assert(!isNull() && "No ASTContext." ); |
125 | if (NamedDecl *ND = getAsDecl()) |
126 | return ND->getASTContext(); |
127 | return getAsList()->D->getASTContext(); |
128 | } |
129 | |
130 | DeclsAndHasExternalTy getAsListAndHasExternal() const { return Data; } |
131 | |
132 | NamedDecl *getAsDecl() const { |
133 | return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>(); |
134 | } |
135 | |
136 | DeclListNode *getAsList() const { |
137 | return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>(); |
138 | } |
139 | |
140 | bool hasExternalDecls() const { |
141 | return getAsListAndHasExternal().getInt(); |
142 | } |
143 | |
144 | void setHasExternalDecls() { |
145 | Data.setInt(true); |
146 | } |
147 | |
148 | void remove(NamedDecl *D) { |
149 | assert(!isNull() && "removing from empty list" ); |
150 | erase(ND: D); |
151 | } |
152 | |
153 | /// Remove any declarations which were imported from an external AST source. |
154 | void removeExternalDecls() { |
155 | erase_if(ShouldErase: [](NamedDecl *ND) { return ND->isFromASTFile(); }); |
156 | |
157 | // Don't have any pending external decls any more. |
158 | Data.setInt(false); |
159 | } |
160 | |
161 | void replaceExternalDecls(ArrayRef<NamedDecl*> Decls) { |
162 | // Remove all declarations that are either external or are replaced with |
163 | // external declarations. |
164 | erase_if(ShouldErase: [Decls](NamedDecl *ND) { |
165 | if (ND->isFromASTFile()) |
166 | return true; |
167 | for (NamedDecl *D : Decls) |
168 | if (D->declarationReplaces(OldD: ND, /*IsKnownNewer=*/IsKnownNewer: false)) |
169 | return true; |
170 | return false; |
171 | }); |
172 | |
173 | // Don't have any pending external decls any more. |
174 | Data.setInt(false); |
175 | |
176 | if (Decls.empty()) |
177 | return; |
178 | |
179 | // Convert Decls into a list, in order. |
180 | ASTContext &C = Decls.front()->getASTContext(); |
181 | DeclListNode::Decls DeclsAsList = Decls.back(); |
182 | for (size_t I = Decls.size() - 1; I != 0; --I) { |
183 | DeclListNode *Node = C.AllocateDeclListNode(ND: Decls[I - 1]); |
184 | Node->Rest = DeclsAsList; |
185 | DeclsAsList = Node; |
186 | } |
187 | |
188 | DeclListNode::Decls Head = Data.getPointer(); |
189 | if (Head.isNull()) { |
190 | Data.setPointer(DeclsAsList); |
191 | return; |
192 | } |
193 | |
194 | // Find the end of the existing list. |
195 | // FIXME: It would be possible to preserve information from erase_if to |
196 | // avoid this rescan looking for the end of the list. |
197 | DeclListNode::Decls *Tail = &Head; |
198 | while (DeclListNode *Node = Tail->dyn_cast<DeclListNode *>()) |
199 | Tail = &Node->Rest; |
200 | |
201 | // Append the Decls. |
202 | DeclListNode *Node = C.AllocateDeclListNode(ND: Tail->get<NamedDecl *>()); |
203 | Node->Rest = DeclsAsList; |
204 | *Tail = Node; |
205 | Data.setPointer(Head); |
206 | } |
207 | |
208 | /// Return an array of all the decls that this list represents. |
209 | DeclContext::lookup_result getLookupResult() const { |
210 | return DeclContext::lookup_result(Data.getPointer()); |
211 | } |
212 | |
213 | /// If this is a redeclaration of an existing decl, replace the old one with |
214 | /// D. Otherwise, append D. |
215 | void addOrReplaceDecl(NamedDecl *D) { |
216 | const bool IsKnownNewer = true; |
217 | |
218 | if (isNull()) { |
219 | Data.setPointer(D); |
220 | return; |
221 | } |
222 | |
223 | // Most decls only have one entry in their list, special case it. |
224 | if (NamedDecl *OldD = getAsDecl()) { |
225 | if (D->declarationReplaces(OldD, IsKnownNewer)) { |
226 | Data.setPointer(D); |
227 | return; |
228 | } |
229 | |
230 | // Add D after OldD. |
231 | ASTContext &C = D->getASTContext(); |
232 | DeclListNode *Node = C.AllocateDeclListNode(ND: OldD); |
233 | Node->Rest = D; |
234 | Data.setPointer(Node); |
235 | return; |
236 | } |
237 | |
238 | // FIXME: Move the assert before the single decl case when we fix the |
239 | // duplication coming from the ASTReader reading builtin types. |
240 | assert(!llvm::is_contained(getLookupResult(), D) && "Already exists!" ); |
241 | // Determine if this declaration is actually a redeclaration. |
242 | for (DeclListNode *N = getAsList(); /*return in loop*/; |
243 | N = N->Rest.dyn_cast<DeclListNode *>()) { |
244 | if (D->declarationReplaces(OldD: N->D, IsKnownNewer)) { |
245 | N->D = D; |
246 | return; |
247 | } |
248 | if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) { |
249 | if (D->declarationReplaces(OldD: ND, IsKnownNewer)) { |
250 | N->Rest = D; |
251 | return; |
252 | } |
253 | |
254 | // Add D after ND. |
255 | ASTContext &C = D->getASTContext(); |
256 | DeclListNode *Node = C.AllocateDeclListNode(ND); |
257 | N->Rest = Node; |
258 | Node->Rest = D; |
259 | return; |
260 | } |
261 | } |
262 | } |
263 | |
264 | /// Add a declaration to the list without checking if it replaces anything. |
265 | void prependDeclNoReplace(NamedDecl *D) { |
266 | if (isNull()) { |
267 | Data.setPointer(D); |
268 | return; |
269 | } |
270 | |
271 | ASTContext &C = D->getASTContext(); |
272 | DeclListNode *Node = C.AllocateDeclListNode(ND: D); |
273 | Node->Rest = Data.getPointer(); |
274 | Data.setPointer(Node); |
275 | } |
276 | |
277 | LLVM_DUMP_METHOD void dump() const { |
278 | Decls D = Data.getPointer(); |
279 | if (!D) { |
280 | llvm::errs() << "<null>\n" ; |
281 | return; |
282 | } |
283 | |
284 | while (true) { |
285 | if (auto *Node = D.dyn_cast<DeclListNode*>()) { |
286 | llvm::errs() << '[' << Node->D << "] -> " ; |
287 | D = Node->Rest; |
288 | } else { |
289 | llvm::errs() << '[' << D.get<NamedDecl*>() << "]\n" ; |
290 | return; |
291 | } |
292 | } |
293 | } |
294 | }; |
295 | |
296 | class StoredDeclsMap |
297 | : public llvm::SmallDenseMap<DeclarationName, StoredDeclsList, 4> { |
298 | friend class ASTContext; // walks the chain deleting these |
299 | friend class DeclContext; |
300 | |
301 | llvm::PointerIntPair<StoredDeclsMap*, 1> Previous; |
302 | public: |
303 | static void DestroyAll(StoredDeclsMap *Map, bool Dependent); |
304 | }; |
305 | |
306 | class DependentStoredDeclsMap : public StoredDeclsMap { |
307 | friend class DeclContext; // iterates over diagnostics |
308 | friend class DependentDiagnostic; |
309 | |
310 | DependentDiagnostic *FirstDiagnostic = nullptr; |
311 | public: |
312 | DependentStoredDeclsMap() = default; |
313 | }; |
314 | |
315 | } // namespace clang |
316 | |
317 | #endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H |
318 | |