/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/AST/DeclContextInternals.h
Line | Count | Source (jump to first uncovered line) |
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 | 2.24M | void erase_if(Fn ShouldErase) { |
47 | 2.24M | Decls List = Data.getPointer(); |
48 | 2.24M | if (!List) |
49 | 1.24M | return; |
50 | 996k | ASTContext &C = getASTContext(); |
51 | 996k | DeclListNode::Decls NewHead = nullptr; |
52 | 996k | DeclListNode::Decls *NewLast = nullptr; |
53 | 996k | DeclListNode::Decls *NewTail = &NewHead; |
54 | 1.47M | while (true) { |
55 | 1.47M | if (!ShouldErase(*DeclListNode::iterator(List))) { |
56 | 105k | NewLast = NewTail; |
57 | 105k | *NewTail = List; |
58 | 105k | if (auto *Node = List.dyn_cast<DeclListNode*>()) { |
59 | 8.85k | NewTail = &Node->Rest; |
60 | 8.85k | List = Node->Rest; |
61 | 96.8k | } else { |
62 | 96.8k | break; |
63 | 96.8k | } |
64 | 1.37M | } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) { |
65 | 472k | List = N->Rest; |
66 | 472k | C.DeallocateDeclListNode(N); |
67 | 900k | } 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 | 900k | if (NewLast) { |
72 | 250 | DeclListNode *Node = NewLast->get<DeclListNode*>(); |
73 | 250 | *NewLast = Node->D; |
74 | 250 | C.DeallocateDeclListNode(Node); |
75 | 250 | } |
76 | 900k | break; |
77 | 900k | } |
78 | 1.47M | } |
79 | 996k | Data.setPointer(NewHead); |
80 | | |
81 | 996k | assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!"); |
82 | 996k | } void clang::StoredDeclsList::erase_if<clang::StoredDeclsList::erase(clang::NamedDecl*)::'lambda'(clang::NamedDecl*)>(clang::StoredDeclsList::erase(clang::NamedDecl*)::'lambda'(clang::NamedDecl*)) Line | Count | Source | 46 | 58.6k | void erase_if(Fn ShouldErase) { | 47 | 58.6k | Decls List = Data.getPointer(); | 48 | 58.6k | if (!List) | 49 | 0 | return; | 50 | 58.6k | ASTContext &C = getASTContext(); | 51 | 58.6k | DeclListNode::Decls NewHead = nullptr; | 52 | 58.6k | DeclListNode::Decls *NewLast = nullptr; | 53 | 58.6k | DeclListNode::Decls *NewTail = &NewHead; | 54 | 60.7k | while (true) { | 55 | 60.7k | if (!ShouldErase(*DeclListNode::iterator(List))) { | 56 | 2.09k | NewLast = NewTail; | 57 | 2.09k | *NewTail = List; | 58 | 2.09k | if (auto *Node = List.dyn_cast<DeclListNode*>()) { | 59 | 1.82k | NewTail = &Node->Rest; | 60 | 1.82k | List = Node->Rest; | 61 | 1.82k | } else { | 62 | 276 | break; | 63 | 276 | } | 64 | 58.6k | } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) { | 65 | 275 | List = N->Rest; | 66 | 275 | C.DeallocateDeclListNode(N); | 67 | 58.4k | } 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 | 58.4k | if (NewLast) { | 72 | 49 | DeclListNode *Node = NewLast->get<DeclListNode*>(); | 73 | 49 | *NewLast = Node->D; | 74 | 49 | C.DeallocateDeclListNode(Node); | 75 | 49 | } | 76 | 58.4k | break; | 77 | 58.4k | } | 78 | 60.7k | } | 79 | 58.6k | Data.setPointer(NewHead); | 80 | | | 81 | 58.6k | assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!"); | 82 | 58.6k | } |
void clang::StoredDeclsList::erase_if<clang::StoredDeclsList::removeExternalDecls()::'lambda'(clang::NamedDecl*)>(clang::StoredDeclsList::removeExternalDecls()::'lambda'(clang::NamedDecl*)) Line | Count | Source | 46 | 411k | void erase_if(Fn ShouldErase) { | 47 | 411k | Decls List = Data.getPointer(); | 48 | 411k | if (!List) | 49 | 409k | return; | 50 | 1.25k | ASTContext &C = getASTContext(); | 51 | 1.25k | DeclListNode::Decls NewHead = nullptr; | 52 | 1.25k | DeclListNode::Decls *NewLast = nullptr; | 53 | 1.25k | DeclListNode::Decls *NewTail = &NewHead; | 54 | 5.86k | while (true) { | 55 | 5.86k | if (!ShouldErase(*DeclListNode::iterator(List))) { | 56 | 5.86k | NewLast = NewTail; | 57 | 5.86k | *NewTail = List; | 58 | 5.86k | if (auto *Node = List.dyn_cast<DeclListNode*>()) { | 59 | 4.60k | NewTail = &Node->Rest; | 60 | 4.60k | List = Node->Rest; | 61 | 4.60k | } else { | 62 | 1.25k | break; | 63 | 1.25k | } | 64 | 5.86k | } else if (DeclListNode *0 N0 = List.dyn_cast<DeclListNode*>()) { | 65 | 0 | List = N->Rest; | 66 | 0 | C.DeallocateDeclListNode(N); | 67 | 0 | } 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 | 0 | if (NewLast) { | 72 | 0 | DeclListNode *Node = NewLast->get<DeclListNode*>(); | 73 | 0 | *NewLast = Node->D; | 74 | 0 | C.DeallocateDeclListNode(Node); | 75 | 0 | } | 76 | 0 | break; | 77 | 0 | } | 78 | 5.86k | } | 79 | 1.25k | Data.setPointer(NewHead); | 80 | | | 81 | 1.25k | assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!"); | 82 | 1.25k | } |
void clang::StoredDeclsList::erase_if<clang::StoredDeclsList::replaceExternalDecls(llvm::ArrayRef<clang::NamedDecl*>)::'lambda'(clang::NamedDecl*)>(clang::StoredDeclsList::replaceExternalDecls(llvm::ArrayRef<clang::NamedDecl*>)::'lambda'(clang::NamedDecl*)) Line | Count | Source | 46 | 1.77M | void erase_if(Fn ShouldErase) { | 47 | 1.77M | Decls List = Data.getPointer(); | 48 | 1.77M | if (!List) | 49 | 840k | return; | 50 | 936k | ASTContext &C = getASTContext(); | 51 | 936k | DeclListNode::Decls NewHead = nullptr; | 52 | 936k | DeclListNode::Decls *NewLast = nullptr; | 53 | 936k | DeclListNode::Decls *NewTail = &NewHead; | 54 | 1.41M | while (true) { | 55 | 1.41M | if (!ShouldErase(*DeclListNode::iterator(List))) { | 56 | 97.7k | NewLast = NewTail; | 57 | 97.7k | *NewTail = List; | 58 | 97.7k | if (auto *Node = List.dyn_cast<DeclListNode*>()) { | 59 | 2.42k | NewTail = &Node->Rest; | 60 | 2.42k | List = Node->Rest; | 61 | 95.2k | } else { | 62 | 95.2k | break; | 63 | 95.2k | } | 64 | 1.31M | } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) { | 65 | 472k | List = N->Rest; | 66 | 472k | C.DeallocateDeclListNode(N); | 67 | 841k | } 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 | 841k | if (NewLast) { | 72 | 201 | DeclListNode *Node = NewLast->get<DeclListNode*>(); | 73 | 201 | *NewLast = Node->D; | 74 | 201 | C.DeallocateDeclListNode(Node); | 75 | 201 | } | 76 | 841k | break; | 77 | 841k | } | 78 | 1.41M | } | 79 | 936k | Data.setPointer(NewHead); | 80 | | | 81 | 936k | assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!"); | 82 | 936k | } |
|
83 | | |
84 | 58.6k | void erase(NamedDecl *ND) { |
85 | 62.8k | erase_if([ND](NamedDecl *D) { return D == ND; }); |
86 | 58.6k | } |
87 | | |
88 | | public: |
89 | 29.4M | StoredDeclsList() = default; |
90 | | |
91 | 30.1M | StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) { |
92 | 30.1M | RHS.Data.setPointer(nullptr); |
93 | 30.1M | RHS.Data.setInt(false); |
94 | 30.1M | } |
95 | | |
96 | 59.5M | void MaybeDeallocList() { |
97 | 59.5M | if (isNull()) |
98 | 38.4M | return; |
99 | | // If this is a list-form, free the list. |
100 | 21.0M | ASTContext &C = getASTContext(); |
101 | 21.0M | Decls List = Data.getPointer(); |
102 | 27.9M | while (DeclListNode *ToDealloc = List.dyn_cast<DeclListNode *>()) { |
103 | 6.85M | List = ToDealloc->Rest; |
104 | 6.85M | C.DeallocateDeclListNode(ToDealloc); |
105 | 6.85M | } |
106 | 21.0M | } |
107 | | |
108 | 59.5M | ~StoredDeclsList() { |
109 | 59.5M | MaybeDeallocList(); |
110 | 59.5M | } |
111 | | |
112 | 0 | StoredDeclsList &operator=(StoredDeclsList &&RHS) { |
113 | 0 | MaybeDeallocList(); |
114 | 0 |
|
115 | 0 | Data = RHS.Data; |
116 | 0 | RHS.Data.setPointer(nullptr); |
117 | 0 | RHS.Data.setInt(false); |
118 | 0 | return *this; |
119 | 0 | } |
120 | | |
121 | 110M | bool isNull() const { return Data.getPointer().isNull(); } |
122 | | |
123 | 22.0M | ASTContext &getASTContext() { |
124 | 22.0M | assert(!isNull() && "No ASTContext."); |
125 | 22.0M | if (NamedDecl *ND = getAsDecl()) |
126 | 19.8M | return ND->getASTContext(); |
127 | 2.26M | return getAsList()->D->getASTContext(); |
128 | 22.0M | } |
129 | | |
130 | 43.9M | DeclsAndHasExternalTy getAsListAndHasExternal() const { return Data; } |
131 | | |
132 | 28.5M | NamedDecl *getAsDecl() const { |
133 | 28.5M | return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>(); |
134 | 28.5M | } |
135 | | |
136 | 6.42M | DeclListNode *getAsList() const { |
137 | 6.42M | return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>(); |
138 | 6.42M | } |
139 | | |
140 | 8.96M | bool hasExternalDecls() const { |
141 | 8.96M | return getAsListAndHasExternal().getInt(); |
142 | 8.96M | } |
143 | | |
144 | 4.88M | void setHasExternalDecls() { |
145 | 4.88M | Data.setInt(true); |
146 | 4.88M | } |
147 | | |
148 | 58.6k | void remove(NamedDecl *D) { |
149 | 58.6k | assert(!isNull() && "removing from empty list"); |
150 | 0 | erase(D); |
151 | 58.6k | } |
152 | | |
153 | | /// Remove any declarations which were imported from an external AST source. |
154 | 411k | void removeExternalDecls() { |
155 | 411k | erase_if([](NamedDecl *ND) { return ND->isFromASTFile(); }11.7k ); |
156 | | |
157 | | // Don't have any pending external decls any more. |
158 | 411k | Data.setInt(false); |
159 | 411k | } |
160 | | |
161 | 1.77M | void replaceExternalDecls(ArrayRef<NamedDecl*> Decls) { |
162 | | // Remove all declarations that are either external or are replaced with |
163 | | // external declarations. |
164 | 1.77M | erase_if([Decls](NamedDecl *ND) { |
165 | 1.50M | if (ND->isFromASTFile()) |
166 | 1.30M | return true; |
167 | 208k | for (NamedDecl *D : Decls) |
168 | 22.1k | if (D->declarationReplaces(ND, /*IsKnownNewer=*/false)) |
169 | 13.2k | return true; |
170 | 195k | return false; |
171 | 208k | }); |
172 | | |
173 | | // Don't have any pending external decls any more. |
174 | 1.77M | Data.setInt(false); |
175 | | |
176 | 1.77M | if (Decls.empty()) |
177 | 851k | return; |
178 | | |
179 | | // Convert Decls into a list, in order. |
180 | 925k | ASTContext &C = Decls.front()->getASTContext(); |
181 | 925k | DeclListNode::Decls DeclsAsList = Decls.back(); |
182 | 1.45M | for (size_t I = Decls.size() - 1; I != 0; --I530k ) { |
183 | 530k | DeclListNode *Node = C.AllocateDeclListNode(Decls[I - 1]); |
184 | 530k | Node->Rest = DeclsAsList; |
185 | 530k | DeclsAsList = Node; |
186 | 530k | } |
187 | | |
188 | 925k | DeclListNode::Decls Head = Data.getPointer(); |
189 | 925k | if (Head.isNull()) { |
190 | 924k | Data.setPointer(DeclsAsList); |
191 | 924k | return; |
192 | 924k | } |
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 | 1.08k | DeclListNode::Decls *Tail = &Head; |
198 | 1.16k | while (DeclListNode *Node = Tail->dyn_cast<DeclListNode *>()) |
199 | 77 | Tail = &Node->Rest; |
200 | | |
201 | | // Append the Decls. |
202 | 1.08k | DeclListNode *Node = C.AllocateDeclListNode(Tail->get<NamedDecl *>()); |
203 | 1.08k | Node->Rest = DeclsAsList; |
204 | 1.08k | *Tail = Node; |
205 | 1.08k | Data.setPointer(Head); |
206 | 1.08k | } |
207 | | |
208 | | /// Return an array of all the decls that this list represents. |
209 | 101M | DeclContext::lookup_result getLookupResult() const { |
210 | 101M | return DeclContext::lookup_result(Data.getPointer()); |
211 | 101M | } |
212 | | |
213 | | /// If this is a redeclaration of an existing decl, replace the old one with |
214 | | /// D. Otherwise, append D. |
215 | 25.2M | void addOrReplaceDecl(NamedDecl *D) { |
216 | 25.2M | const bool IsKnownNewer = true; |
217 | | |
218 | 25.2M | if (isNull()) { |
219 | 18.7M | Data.setPointer(D); |
220 | 18.7M | return; |
221 | 18.7M | } |
222 | | |
223 | | // Most decls only have one entry in their list, special case it. |
224 | 6.52M | if (NamedDecl *OldD = getAsDecl()) { |
225 | 2.37M | if (D->declarationReplaces(OldD, IsKnownNewer)) { |
226 | 684k | Data.setPointer(D); |
227 | 684k | return; |
228 | 684k | } |
229 | | |
230 | | // Add D after OldD. |
231 | 1.68M | ASTContext &C = D->getASTContext(); |
232 | 1.68M | DeclListNode *Node = C.AllocateDeclListNode(OldD); |
233 | 1.68M | Node->Rest = D; |
234 | 1.68M | Data.setPointer(Node); |
235 | 1.68M | return; |
236 | 2.37M | } |
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 | 4.15M | assert(!llvm::is_contained(getLookupResult(), D) && "Already exists!"); |
241 | | // Determine if this declaration is actually a redeclaration. |
242 | 0 | for (DeclListNode *N = getAsList(); /*return in loop*/; |
243 | 26.2M | N = N->Rest.dyn_cast<DeclListNode *>()22.0M ) { |
244 | 26.2M | if (D->declarationReplaces(N->D, IsKnownNewer)) { |
245 | 144k | N->D = D; |
246 | 144k | return; |
247 | 144k | } |
248 | 26.1M | if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) { |
249 | 4.01M | if (D->declarationReplaces(ND, IsKnownNewer)) { |
250 | 45.0k | N->Rest = D; |
251 | 45.0k | return; |
252 | 45.0k | } |
253 | | |
254 | | // Add D after ND. |
255 | 3.96M | ASTContext &C = D->getASTContext(); |
256 | 3.96M | DeclListNode *Node = C.AllocateDeclListNode(ND); |
257 | 3.96M | N->Rest = Node; |
258 | 3.96M | Node->Rest = D; |
259 | 3.96M | return; |
260 | 4.01M | } |
261 | 26.1M | } |
262 | 4.15M | } |
263 | | |
264 | | /// Add a declaration to the list without checking if it replaces anything. |
265 | 3.49M | void prependDeclNoReplace(NamedDecl *D) { |
266 | 3.49M | if (isNull()) { |
267 | 2.35M | Data.setPointer(D); |
268 | 2.35M | return; |
269 | 2.35M | } |
270 | | |
271 | 1.14M | ASTContext &C = D->getASTContext(); |
272 | 1.14M | DeclListNode *Node = C.AllocateDeclListNode(D); |
273 | 1.14M | Node->Rest = Data.getPointer(); |
274 | 1.14M | Data.setPointer(Node); |
275 | 1.14M | } |
276 | | |
277 | 0 | LLVM_DUMP_METHOD void dump() const { |
278 | 0 | Decls D = Data.getPointer(); |
279 | 0 | if (!D) { |
280 | 0 | llvm::errs() << "<null>\n"; |
281 | 0 | return; |
282 | 0 | } |
283 | | |
284 | 0 | while (true) { |
285 | 0 | if (auto *Node = D.dyn_cast<DeclListNode*>()) { |
286 | 0 | llvm::errs() << '[' << Node->D << "] -> "; |
287 | 0 | D = Node->Rest; |
288 | 0 | } else { |
289 | 0 | llvm::errs() << '[' << D.get<NamedDecl*>() << "]\n"; |
290 | 0 | return; |
291 | 0 | } |
292 | 0 | } |
293 | 0 | } |
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 | 545k | DependentStoredDeclsMap() = default; |
313 | | }; |
314 | | |
315 | | } // namespace clang |
316 | | |
317 | | #endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H |