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