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(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([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(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(D);
151   }
152 
153   /// Remove any declarations which were imported from an external AST source.
154   void removeExternalDecls() {
155     erase_if([](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([Decls](NamedDecl *ND) {
165       if (ND->isFromASTFile())
166         return true;
167       for (NamedDecl *D : Decls)
168         if (D->declarationReplaces(ND, /*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(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(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(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(N->D, IsKnownNewer)) {
245         N->D = D;
246         return;
247       }
248       if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) {
249         if (D->declarationReplaces(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(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