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::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 
89 public:
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 
297 class 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;
303 public:
304   static void DestroyAll(StoredDeclsMap *Map, bool Dependent);
305 };
306 
307 class DependentStoredDeclsMap : public StoredDeclsMap {
308   friend class DeclContext; // iterates over diagnostics
309   friend class DependentDiagnostic;
310 
311   DependentDiagnostic *FirstDiagnostic = nullptr;
312 public:
313   DependentStoredDeclsMap() = default;
314 };
315 
316 } // namespace clang
317 
318 #endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H
319