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