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
27namespace clang {
28
29class DependentDiagnostic;
30
31/// An array of decls optimized for the common case of only containing
32/// one entry.
33class 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
88public:
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
296class 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;
302public:
303 static void DestroyAll(StoredDeclsMap *Map, bool Dependent);
304};
305
306class DependentStoredDeclsMap : public StoredDeclsMap {
307 friend class DeclContext; // iterates over diagnostics
308 friend class DependentDiagnostic;
309
310 DependentDiagnostic *FirstDiagnostic = nullptr;
311public:
312 DependentStoredDeclsMap() = default;
313};
314
315} // namespace clang
316
317#endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H
318

source code of clang/include/clang/AST/DeclContextInternals.h