/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/lib/AST/CXXInheritance.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- CXXInheritance.cpp - C++ Inheritance -------------------------------===// |
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 provides routines that help analyzing C++ inheritance hierarchies. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #include "clang/AST/CXXInheritance.h" |
14 | | #include "clang/AST/ASTContext.h" |
15 | | #include "clang/AST/Decl.h" |
16 | | #include "clang/AST/DeclBase.h" |
17 | | #include "clang/AST/DeclCXX.h" |
18 | | #include "clang/AST/DeclTemplate.h" |
19 | | #include "clang/AST/RecordLayout.h" |
20 | | #include "clang/AST/TemplateName.h" |
21 | | #include "clang/AST/Type.h" |
22 | | #include "clang/Basic/LLVM.h" |
23 | | #include "llvm/ADT/DenseMap.h" |
24 | | #include "llvm/ADT/STLExtras.h" |
25 | | #include "llvm/ADT/SetVector.h" |
26 | | #include "llvm/ADT/SmallVector.h" |
27 | | #include "llvm/ADT/iterator_range.h" |
28 | | #include "llvm/Support/Casting.h" |
29 | | #include <algorithm> |
30 | | #include <utility> |
31 | | #include <cassert> |
32 | | #include <vector> |
33 | | |
34 | | using namespace clang; |
35 | | |
36 | | /// Computes the set of declarations referenced by these base |
37 | | /// paths. |
38 | 92.4k | void CXXBasePaths::ComputeDeclsFound() { |
39 | 92.4k | assert(NumDeclsFound == 0 && !DeclsFound && |
40 | 92.4k | "Already computed the set of declarations"); |
41 | 92.4k | |
42 | 92.4k | llvm::SmallSetVector<NamedDecl *, 8> Decls; |
43 | 186k | for (paths_iterator Path = begin(), PathEnd = end(); Path != PathEnd; ++Path94.2k ) |
44 | 94.2k | Decls.insert(Path->Decls.front()); |
45 | 92.4k | |
46 | 92.4k | NumDeclsFound = Decls.size(); |
47 | 92.4k | DeclsFound = llvm::make_unique<NamedDecl *[]>(NumDeclsFound); |
48 | 92.4k | std::copy(Decls.begin(), Decls.end(), DeclsFound.get()); |
49 | 92.4k | } |
50 | | |
51 | 92.4k | CXXBasePaths::decl_range CXXBasePaths::found_decls() { |
52 | 92.4k | if (NumDeclsFound == 0) |
53 | 92.4k | ComputeDeclsFound(); |
54 | 92.4k | |
55 | 92.4k | return decl_range(decl_iterator(DeclsFound.get()), |
56 | 92.4k | decl_iterator(DeclsFound.get() + NumDeclsFound)); |
57 | 92.4k | } |
58 | | |
59 | | /// isAmbiguous - Determines whether the set of paths provided is |
60 | | /// ambiguous, i.e., there are two or more paths that refer to |
61 | | /// different base class subobjects of the same type. BaseType must be |
62 | | /// an unqualified, canonical class type. |
63 | 183k | bool CXXBasePaths::isAmbiguous(CanQualType BaseType) { |
64 | 183k | BaseType = BaseType.getUnqualifiedType(); |
65 | 183k | IsVirtBaseAndNumberNonVirtBases Subobjects = ClassSubobjects[BaseType]; |
66 | 183k | return Subobjects.NumberOfNonVirtBases + (Subobjects.IsVirtBase ? 11.94k : 0181k ) > 1; |
67 | 183k | } |
68 | | |
69 | | /// clear - Clear out all prior path information. |
70 | 48 | void CXXBasePaths::clear() { |
71 | 48 | Paths.clear(); |
72 | 48 | ClassSubobjects.clear(); |
73 | 48 | VisitedDependentRecords.clear(); |
74 | 48 | ScratchPath.clear(); |
75 | 48 | DetectedVirtual = nullptr; |
76 | 48 | } |
77 | | |
78 | | /// Swaps the contents of this CXXBasePaths structure with the |
79 | | /// contents of Other. |
80 | 114 | void CXXBasePaths::swap(CXXBasePaths &Other) { |
81 | 114 | std::swap(Origin, Other.Origin); |
82 | 114 | Paths.swap(Other.Paths); |
83 | 114 | ClassSubobjects.swap(Other.ClassSubobjects); |
84 | 114 | VisitedDependentRecords.swap(Other.VisitedDependentRecords); |
85 | 114 | std::swap(FindAmbiguities, Other.FindAmbiguities); |
86 | 114 | std::swap(RecordPaths, Other.RecordPaths); |
87 | 114 | std::swap(DetectVirtual, Other.DetectVirtual); |
88 | 114 | std::swap(DetectedVirtual, Other.DetectedVirtual); |
89 | 114 | } |
90 | | |
91 | 940k | bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const { |
92 | 940k | CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, |
93 | 940k | /*DetectVirtual=*/false); |
94 | 940k | return isDerivedFrom(Base, Paths); |
95 | 940k | } |
96 | | |
97 | | bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base, |
98 | 1.24M | CXXBasePaths &Paths) const { |
99 | 1.24M | if (getCanonicalDecl() == Base->getCanonicalDecl()) |
100 | 43.1k | return false; |
101 | 1.20M | |
102 | 1.20M | Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); |
103 | 1.20M | |
104 | 1.20M | const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl(); |
105 | 1.20M | return lookupInBases( |
106 | 1.20M | [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
107 | 970k | return FindBaseClass(Specifier, Path, BaseDecl); |
108 | 970k | }, |
109 | 1.20M | Paths); |
110 | 1.20M | } |
111 | | |
112 | 12.9k | bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const { |
113 | 12.9k | if (!getNumVBases()) |
114 | 11.1k | return false; |
115 | 1.83k | |
116 | 1.83k | CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, |
117 | 1.83k | /*DetectVirtual=*/false); |
118 | 1.83k | |
119 | 1.83k | if (getCanonicalDecl() == Base->getCanonicalDecl()) |
120 | 813 | return false; |
121 | 1.02k | |
122 | 1.02k | Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); |
123 | 1.02k | |
124 | 1.02k | const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl(); |
125 | 1.02k | return lookupInBases( |
126 | 3.17k | [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
127 | 3.17k | return FindVirtualBaseClass(Specifier, Path, BaseDecl); |
128 | 3.17k | }, |
129 | 1.02k | Paths); |
130 | 1.02k | } |
131 | | |
132 | 54.6k | bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const { |
133 | 54.6k | const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl(); |
134 | 61.6k | return forallBases([TargetDecl](const CXXRecordDecl *Base) { |
135 | 61.6k | return Base->getCanonicalDecl() != TargetDecl; |
136 | 61.6k | }); |
137 | 54.6k | } |
138 | | |
139 | | bool |
140 | 50.4k | CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const { |
141 | 50.4k | assert(isDependentContext()); |
142 | 50.4k | |
143 | 96.2k | for (; !CurContext->isFileContext(); CurContext = CurContext->getParent()45.8k ) |
144 | 76.0k | if (CurContext->Equals(this)) |
145 | 30.1k | return true; |
146 | 50.4k | |
147 | 50.4k | return false20.2k ; |
148 | 50.4k | } |
149 | | |
150 | | bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches, |
151 | 99.3k | bool AllowShortCircuit) const { |
152 | 99.3k | SmallVector<const CXXRecordDecl*, 8> Queue; |
153 | 99.3k | |
154 | 99.3k | const CXXRecordDecl *Record = this; |
155 | 99.3k | bool AllMatches = true; |
156 | 108k | while (true) { |
157 | 113k | for (const auto &I : Record->bases()) { |
158 | 113k | const RecordType *Ty = I.getType()->getAs<RecordType>(); |
159 | 113k | if (!Ty) { |
160 | 3.25k | if (AllowShortCircuit) return false; |
161 | 0 | AllMatches = false; |
162 | 0 | continue; |
163 | 0 | } |
164 | 110k | |
165 | 110k | CXXRecordDecl *Base = |
166 | 110k | cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition()); |
167 | 110k | if (!Base || |
168 | 110k | (110k Base->isDependentContext()110k && |
169 | 110k | !Base->isCurrentInstantiation(Record)6 )) { |
170 | 8 | if (AllowShortCircuit) return false; |
171 | 0 | AllMatches = false; |
172 | 0 | continue; |
173 | 0 | } |
174 | 110k | |
175 | 110k | Queue.push_back(Base); |
176 | 110k | if (!BaseMatches(Base)) { |
177 | 94.7k | if (AllowShortCircuit) return false; |
178 | 0 | AllMatches = false; |
179 | 0 | continue; |
180 | 0 | } |
181 | 110k | } |
182 | 108k | |
183 | 108k | if (10.8k Queue.empty()10.8k ) |
184 | 1.36k | break; |
185 | 9.52k | Record = Queue.pop_back_val(); // not actually a queue. |
186 | 9.52k | } |
187 | 99.3k | |
188 | 99.3k | return AllMatches1.36k ; |
189 | 99.3k | } |
190 | | |
191 | | bool CXXBasePaths::lookupInBases(ASTContext &Context, |
192 | | const CXXRecordDecl *Record, |
193 | | CXXRecordDecl::BaseMatchesCallback BaseMatches, |
194 | 16.3M | bool LookupInDependent) { |
195 | 16.3M | bool FoundPath = false; |
196 | 16.3M | |
197 | 16.3M | // The access of the path down to this record. |
198 | 16.3M | AccessSpecifier AccessToHere = ScratchPath.Access; |
199 | 16.3M | bool IsFirstStep = ScratchPath.empty(); |
200 | 16.3M | |
201 | 16.3M | for (const auto &BaseSpec : Record->bases()) { |
202 | 6.14M | // Find the record of the base class subobjects for this type. |
203 | 6.14M | QualType BaseType = |
204 | 6.14M | Context.getCanonicalType(BaseSpec.getType()).getUnqualifiedType(); |
205 | 6.14M | |
206 | 6.14M | // C++ [temp.dep]p3: |
207 | 6.14M | // In the definition of a class template or a member of a class template, |
208 | 6.14M | // if a base class of the class template depends on a template-parameter, |
209 | 6.14M | // the base class scope is not examined during unqualified name lookup |
210 | 6.14M | // either at the point of definition of the class template or member or |
211 | 6.14M | // during an instantiation of the class tem- plate or member. |
212 | 6.14M | if (!LookupInDependent && BaseType->isDependentType()6.14M ) |
213 | 895k | continue; |
214 | 5.25M | |
215 | 5.25M | // Determine whether we need to visit this base class at all, |
216 | 5.25M | // updating the count of subobjects appropriately. |
217 | 5.25M | IsVirtBaseAndNumberNonVirtBases &Subobjects = ClassSubobjects[BaseType]; |
218 | 5.25M | bool VisitBase = true; |
219 | 5.25M | bool SetVirtual = false; |
220 | 5.25M | if (BaseSpec.isVirtual()) { |
221 | 97.1k | VisitBase = !Subobjects.IsVirtBase; |
222 | 97.1k | Subobjects.IsVirtBase = true; |
223 | 97.1k | if (isDetectingVirtual() && DetectedVirtual == nullptr65.6k ) { |
224 | 58.6k | // If this is the first virtual we find, remember it. If it turns out |
225 | 58.6k | // there is no base path here, we'll reset it later. |
226 | 58.6k | DetectedVirtual = BaseType->getAs<RecordType>(); |
227 | 58.6k | SetVirtual = true; |
228 | 58.6k | } |
229 | 5.15M | } else { |
230 | 5.15M | ++Subobjects.NumberOfNonVirtBases; |
231 | 5.15M | } |
232 | 5.25M | if (isRecordingPaths()) { |
233 | 4.61M | // Add this base specifier to the current path. |
234 | 4.61M | CXXBasePathElement Element; |
235 | 4.61M | Element.Base = &BaseSpec; |
236 | 4.61M | Element.Class = Record; |
237 | 4.61M | if (BaseSpec.isVirtual()) |
238 | 69.5k | Element.SubobjectNumber = 0; |
239 | 4.54M | else |
240 | 4.54M | Element.SubobjectNumber = Subobjects.NumberOfNonVirtBases; |
241 | 4.61M | ScratchPath.push_back(Element); |
242 | 4.61M | |
243 | 4.61M | // Calculate the "top-down" access to this base class. |
244 | 4.61M | // The spec actually describes this bottom-up, but top-down is |
245 | 4.61M | // equivalent because the definition works out as follows: |
246 | 4.61M | // 1. Write down the access along each step in the inheritance |
247 | 4.61M | // chain, followed by the access of the decl itself. |
248 | 4.61M | // For example, in |
249 | 4.61M | // class A { public: int foo; }; |
250 | 4.61M | // class B : protected A {}; |
251 | 4.61M | // class C : public B {}; |
252 | 4.61M | // class D : private C {}; |
253 | 4.61M | // we would write: |
254 | 4.61M | // private public protected public |
255 | 4.61M | // 2. If 'private' appears anywhere except far-left, access is denied. |
256 | 4.61M | // 3. Otherwise, overall access is determined by the most restrictive |
257 | 4.61M | // access in the sequence. |
258 | 4.61M | if (IsFirstStep) |
259 | 3.35M | ScratchPath.Access = BaseSpec.getAccessSpecifier(); |
260 | 1.25M | else |
261 | 1.25M | ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere, |
262 | 1.25M | BaseSpec.getAccessSpecifier()); |
263 | 4.61M | } |
264 | 5.25M | |
265 | 5.25M | // Track whether there's a path involving this specific base. |
266 | 5.25M | bool FoundPathThroughBase = false; |
267 | 5.25M | |
268 | 5.25M | if (BaseMatches(&BaseSpec, ScratchPath)) { |
269 | 1.53M | // We've found a path that terminates at this base. |
270 | 1.53M | FoundPath = FoundPathThroughBase = true; |
271 | 1.53M | if (isRecordingPaths()) { |
272 | 1.28M | // We have a path. Make a copy of it before moving on. |
273 | 1.28M | Paths.push_back(ScratchPath); |
274 | 1.28M | } else if (245k !isFindingAmbiguities()245k ) { |
275 | 236k | // We found a path and we don't care about ambiguities; |
276 | 236k | // return immediately. |
277 | 236k | return FoundPath; |
278 | 236k | } |
279 | 3.72M | } else if (VisitBase) { |
280 | 3.71M | CXXRecordDecl *BaseRecord; |
281 | 3.71M | if (LookupInDependent) { |
282 | 42 | BaseRecord = nullptr; |
283 | 42 | const TemplateSpecializationType *TST = |
284 | 42 | BaseSpec.getType()->getAs<TemplateSpecializationType>(); |
285 | 42 | if (!TST) { |
286 | 23 | if (auto *RT = BaseSpec.getType()->getAs<RecordType>()) |
287 | 23 | BaseRecord = cast<CXXRecordDecl>(RT->getDecl()); |
288 | 23 | } else { |
289 | 19 | TemplateName TN = TST->getTemplateName(); |
290 | 19 | if (auto *TD = |
291 | 19 | dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl())) |
292 | 19 | BaseRecord = TD->getTemplatedDecl(); |
293 | 19 | } |
294 | 42 | if (BaseRecord) { |
295 | 42 | if (!BaseRecord->hasDefinition() || |
296 | 42 | VisitedDependentRecords.count(BaseRecord)40 ) { |
297 | 3 | BaseRecord = nullptr; |
298 | 39 | } else { |
299 | 39 | VisitedDependentRecords.insert(BaseRecord); |
300 | 39 | } |
301 | 42 | } |
302 | 3.71M | } else { |
303 | 3.71M | BaseRecord = cast<CXXRecordDecl>( |
304 | 3.71M | BaseSpec.getType()->castAs<RecordType>()->getDecl()); |
305 | 3.71M | } |
306 | 3.71M | if (BaseRecord && |
307 | 3.71M | lookupInBases(Context, BaseRecord, BaseMatches, LookupInDependent)3.71M ) { |
308 | 353k | // C++ [class.member.lookup]p2: |
309 | 353k | // A member name f in one sub-object B hides a member name f in |
310 | 353k | // a sub-object A if A is a base class sub-object of B. Any |
311 | 353k | // declarations that are so hidden are eliminated from |
312 | 353k | // consideration. |
313 | 353k | |
314 | 353k | // There is a path to a base class that meets the criteria. If we're |
315 | 353k | // not collecting paths or finding ambiguities, we're done. |
316 | 353k | FoundPath = FoundPathThroughBase = true; |
317 | 353k | if (!isFindingAmbiguities()) |
318 | 50.3k | return FoundPath; |
319 | 4.96M | } |
320 | 3.71M | } |
321 | 4.96M | |
322 | 4.96M | // Pop this base specifier off the current path (if we're |
323 | 4.96M | // collecting paths). |
324 | 4.96M | if (isRecordingPaths()) { |
325 | 4.61M | ScratchPath.pop_back(); |
326 | 4.61M | } |
327 | 4.96M | |
328 | 4.96M | // If we set a virtual earlier, and this isn't a path, forget it again. |
329 | 4.96M | if (SetVirtual && !FoundPathThroughBase58.6k ) { |
330 | 53.6k | DetectedVirtual = nullptr; |
331 | 53.6k | } |
332 | 4.96M | } |
333 | 16.3M | |
334 | 16.3M | // Reset the scratch path access. |
335 | 16.3M | ScratchPath.Access = AccessToHere; |
336 | 16.0M | |
337 | 16.0M | return FoundPath; |
338 | 16.3M | } |
339 | | |
340 | | bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches, |
341 | | CXXBasePaths &Paths, |
342 | 12.6M | bool LookupInDependent) const { |
343 | 12.6M | // If we didn't find anything, report that. |
344 | 12.6M | if (!Paths.lookupInBases(getASTContext(), this, BaseMatches, |
345 | 12.6M | LookupInDependent)) |
346 | 11.1M | return false; |
347 | 1.52M | |
348 | 1.52M | // If we're not recording paths or we won't ever find ambiguities, |
349 | 1.52M | // we're done. |
350 | 1.52M | if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities()1.27M ) |
351 | 248k | return true; |
352 | 1.27M | |
353 | 1.27M | // C++ [class.member.lookup]p6: |
354 | 1.27M | // When virtual base classes are used, a hidden declaration can be |
355 | 1.27M | // reached along a path through the sub-object lattice that does |
356 | 1.27M | // not pass through the hiding declaration. This is not an |
357 | 1.27M | // ambiguity. The identical use with nonvirtual base classes is an |
358 | 1.27M | // ambiguity; in that case there is no unique instance of the name |
359 | 1.27M | // that hides all the others. |
360 | 1.27M | // |
361 | 1.27M | // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy |
362 | 1.27M | // way to make it any faster. |
363 | 1.28M | Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) 1.27M { |
364 | 1.58M | for (const CXXBasePathElement &PE : Path) { |
365 | 1.58M | if (!PE.Base->isVirtual()) |
366 | 1.57M | continue; |
367 | 8.72k | |
368 | 8.72k | CXXRecordDecl *VBase = nullptr; |
369 | 8.72k | if (const RecordType *Record = PE.Base->getType()->getAs<RecordType>()) |
370 | 8.72k | VBase = cast<CXXRecordDecl>(Record->getDecl()); |
371 | 8.72k | if (!VBase) |
372 | 0 | break; |
373 | 8.72k | |
374 | 8.72k | // The declaration(s) we found along this path were found in a |
375 | 8.72k | // subobject of a virtual base. Check whether this virtual |
376 | 8.72k | // base is a subobject of any other path; if so, then the |
377 | 8.72k | // declaration in this path are hidden by that patch. |
378 | 12.8k | for (const CXXBasePath &HidingP : Paths)8.72k { |
379 | 12.8k | CXXRecordDecl *HidingClass = nullptr; |
380 | 12.8k | if (const RecordType *Record = |
381 | 12.8k | HidingP.back().Base->getType()->getAs<RecordType>()) |
382 | 12.8k | HidingClass = cast<CXXRecordDecl>(Record->getDecl()); |
383 | 12.8k | if (!HidingClass) |
384 | 0 | break; |
385 | 12.8k | |
386 | 12.8k | if (HidingClass->isVirtuallyDerivedFrom(VBase)) |
387 | 38 | return true; |
388 | 12.8k | } |
389 | 8.72k | } |
390 | 1.28M | return false1.28M ; |
391 | 1.28M | }); |
392 | 1.27M | |
393 | 1.27M | return true; |
394 | 1.27M | } |
395 | | |
396 | | bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier, |
397 | | CXXBasePath &Path, |
398 | 970k | const CXXRecordDecl *BaseRecord) { |
399 | 970k | assert(BaseRecord->getCanonicalDecl() == BaseRecord && |
400 | 970k | "User data for FindBaseClass is not canonical!"); |
401 | 970k | return Specifier->getType()->castAs<RecordType>()->getDecl() |
402 | 970k | ->getCanonicalDecl() == BaseRecord; |
403 | 970k | } |
404 | | |
405 | | bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier, |
406 | | CXXBasePath &Path, |
407 | 3.17k | const CXXRecordDecl *BaseRecord) { |
408 | 3.17k | assert(BaseRecord->getCanonicalDecl() == BaseRecord && |
409 | 3.17k | "User data for FindBaseClass is not canonical!"); |
410 | 3.17k | return Specifier->isVirtual() && |
411 | 3.17k | Specifier->getType()->castAs<RecordType>()->getDecl() |
412 | 2.11k | ->getCanonicalDecl() == BaseRecord; |
413 | 3.17k | } |
414 | | |
415 | | bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier, |
416 | | CXXBasePath &Path, |
417 | 816 | DeclarationName Name) { |
418 | 816 | RecordDecl *BaseRecord = |
419 | 816 | Specifier->getType()->castAs<RecordType>()->getDecl(); |
420 | 816 | |
421 | 816 | for (Path.Decls = BaseRecord->lookup(Name); |
422 | 829 | !Path.Decls.empty(); |
423 | 816 | Path.Decls = Path.Decls.slice(1)13 ) { |
424 | 47 | if (Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag)) |
425 | 34 | return true; |
426 | 47 | } |
427 | 816 | |
428 | 816 | return false782 ; |
429 | 816 | } |
430 | | |
431 | | static bool findOrdinaryMember(RecordDecl *BaseRecord, CXXBasePath &Path, |
432 | 2.29M | DeclarationName Name) { |
433 | 2.29M | const unsigned IDNS = Decl::IDNS_Ordinary | Decl::IDNS_Tag | |
434 | 2.29M | Decl::IDNS_Member; |
435 | 2.29M | for (Path.Decls = BaseRecord->lookup(Name); |
436 | 2.29M | !Path.Decls.empty(); |
437 | 2.29M | Path.Decls = Path.Decls.slice(1)42 ) { |
438 | 928k | if (Path.Decls.front()->isInIdentifierNamespace(IDNS)) |
439 | 928k | return true; |
440 | 928k | } |
441 | 2.29M | |
442 | 2.29M | return false1.36M ; |
443 | 2.29M | } |
444 | | |
445 | | bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier, |
446 | | CXXBasePath &Path, |
447 | 2.29M | DeclarationName Name) { |
448 | 2.29M | RecordDecl *BaseRecord = |
449 | 2.29M | Specifier->getType()->castAs<RecordType>()->getDecl(); |
450 | 2.29M | return findOrdinaryMember(BaseRecord, Path, Name); |
451 | 2.29M | } |
452 | | |
453 | | bool CXXRecordDecl::FindOrdinaryMemberInDependentClasses( |
454 | | const CXXBaseSpecifier *Specifier, CXXBasePath &Path, |
455 | 21 | DeclarationName Name) { |
456 | 21 | const TemplateSpecializationType *TST = |
457 | 21 | Specifier->getType()->getAs<TemplateSpecializationType>(); |
458 | 21 | if (!TST) { |
459 | 8 | auto *RT = Specifier->getType()->getAs<RecordType>(); |
460 | 8 | if (!RT) |
461 | 0 | return false; |
462 | 8 | return findOrdinaryMember(RT->getDecl(), Path, Name); |
463 | 8 | } |
464 | 13 | TemplateName TN = TST->getTemplateName(); |
465 | 13 | const auto *TD = dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl()); |
466 | 13 | if (!TD) |
467 | 0 | return false; |
468 | 13 | CXXRecordDecl *RD = TD->getTemplatedDecl(); |
469 | 13 | if (!RD) |
470 | 0 | return false; |
471 | 13 | return findOrdinaryMember(RD, Path, Name); |
472 | 13 | } |
473 | | |
474 | | bool CXXRecordDecl::FindOMPReductionMember(const CXXBaseSpecifier *Specifier, |
475 | | CXXBasePath &Path, |
476 | 280 | DeclarationName Name) { |
477 | 280 | RecordDecl *BaseRecord = |
478 | 280 | Specifier->getType()->castAs<RecordType>()->getDecl(); |
479 | 280 | |
480 | 312 | for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty(); |
481 | 280 | Path.Decls = Path.Decls.slice(1)32 ) { |
482 | 32 | if (Path.Decls.front()->isInIdentifierNamespace(IDNS_OMPReduction)) |
483 | 0 | return true; |
484 | 32 | } |
485 | 280 | |
486 | 280 | return false; |
487 | 280 | } |
488 | | |
489 | | bool CXXRecordDecl::FindOMPMapperMember(const CXXBaseSpecifier *Specifier, |
490 | | CXXBasePath &Path, |
491 | 136 | DeclarationName Name) { |
492 | 136 | RecordDecl *BaseRecord = |
493 | 136 | Specifier->getType()->castAs<RecordType>()->getDecl(); |
494 | 136 | |
495 | 136 | for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty(); |
496 | 136 | Path.Decls = Path.Decls.slice(1)0 ) { |
497 | 0 | if (Path.Decls.front()->isInIdentifierNamespace(IDNS_OMPMapper)) |
498 | 0 | return true; |
499 | 0 | } |
500 | 136 | |
501 | 136 | return false; |
502 | 136 | } |
503 | | |
504 | | bool CXXRecordDecl:: |
505 | | FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier, |
506 | | CXXBasePath &Path, |
507 | 192k | DeclarationName Name) { |
508 | 192k | RecordDecl *BaseRecord = |
509 | 192k | Specifier->getType()->castAs<RecordType>()->getDecl(); |
510 | 192k | |
511 | 192k | for (Path.Decls = BaseRecord->lookup(Name); |
512 | 192k | !Path.Decls.empty(); |
513 | 192k | Path.Decls = Path.Decls.slice(1)0 ) { |
514 | 7.47k | // FIXME: Refactor the "is it a nested-name-specifier?" check |
515 | 7.47k | if (isa<TypedefNameDecl>(Path.Decls.front()) || |
516 | 7.47k | Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag)7.47k ) |
517 | 7.47k | return true; |
518 | 7.47k | } |
519 | 192k | |
520 | 192k | return false185k ; |
521 | 192k | } |
522 | | |
523 | | std::vector<const NamedDecl *> CXXRecordDecl::lookupDependentName( |
524 | | const DeclarationName &Name, |
525 | 39 | llvm::function_ref<bool(const NamedDecl *ND)> Filter) { |
526 | 39 | std::vector<const NamedDecl *> Results; |
527 | 39 | // Lookup in the class. |
528 | 39 | DeclContext::lookup_result DirectResult = lookup(Name); |
529 | 39 | if (!DirectResult.empty()) { |
530 | 30 | for (const NamedDecl *ND : DirectResult) { |
531 | 30 | if (Filter(ND)) |
532 | 22 | Results.push_back(ND); |
533 | 30 | } |
534 | 27 | return Results; |
535 | 27 | } |
536 | 12 | // Perform lookup into our base classes. |
537 | 12 | CXXBasePaths Paths; |
538 | 12 | Paths.setOrigin(this); |
539 | 12 | if (!lookupInBases( |
540 | 21 | [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
541 | 21 | return CXXRecordDecl::FindOrdinaryMemberInDependentClasses( |
542 | 21 | Specifier, Path, Name); |
543 | 21 | }, |
544 | 12 | Paths, /*LookupInDependent=*/true)) |
545 | 6 | return Results; |
546 | 6 | for (const NamedDecl *ND : Paths.front().Decls) { |
547 | 6 | if (Filter(ND)) |
548 | 6 | Results.push_back(ND); |
549 | 6 | } |
550 | 6 | return Results; |
551 | 6 | } |
552 | | |
553 | | void OverridingMethods::add(unsigned OverriddenSubobject, |
554 | 262k | UniqueVirtualMethod Overriding) { |
555 | 262k | SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides |
556 | 262k | = Overrides[OverriddenSubobject]; |
557 | 262k | if (llvm::find(SubobjectOverrides, Overriding) == SubobjectOverrides.end()) |
558 | 261k | SubobjectOverrides.push_back(Overriding); |
559 | 262k | } |
560 | | |
561 | 41.2k | void OverridingMethods::add(const OverridingMethods &Other) { |
562 | 82.5k | for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I41.2k ) { |
563 | 41.2k | for (overriding_const_iterator M = I->second.begin(), |
564 | 41.2k | MEnd = I->second.end(); |
565 | 82.5k | M != MEnd; |
566 | 41.2k | ++M) |
567 | 41.2k | add(I->first, *M); |
568 | 41.2k | } |
569 | 41.2k | } |
570 | | |
571 | 140k | void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) { |
572 | 289k | for (iterator I = begin(), IEnd = end(); I != IEnd; ++I148k ) { |
573 | 148k | I->second.clear(); |
574 | 148k | I->second.push_back(Overriding); |
575 | 148k | } |
576 | 140k | } |
577 | | |
578 | | namespace { |
579 | | |
580 | | class FinalOverriderCollector { |
581 | | /// The number of subobjects of a given class type that |
582 | | /// occur within the class hierarchy. |
583 | | llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount; |
584 | | |
585 | | /// Overriders for each virtual base subobject. |
586 | | llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders; |
587 | | |
588 | | CXXFinalOverriderMap FinalOverriders; |
589 | | |
590 | | public: |
591 | | ~FinalOverriderCollector(); |
592 | | |
593 | | void Collect(const CXXRecordDecl *RD, bool VirtualBase, |
594 | | const CXXRecordDecl *InVirtualSubobject, |
595 | | CXXFinalOverriderMap &Overriders); |
596 | | }; |
597 | | |
598 | | } // namespace |
599 | | |
600 | | void FinalOverriderCollector::Collect(const CXXRecordDecl *RD, |
601 | | bool VirtualBase, |
602 | | const CXXRecordDecl *InVirtualSubobject, |
603 | 71.8k | CXXFinalOverriderMap &Overriders) { |
604 | 71.8k | unsigned SubobjectNumber = 0; |
605 | 71.8k | if (!VirtualBase) |
606 | 65.5k | SubobjectNumber |
607 | 65.5k | = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())]; |
608 | 71.8k | |
609 | 71.8k | for (const auto &Base : RD->bases()) { |
610 | 52.2k | if (const RecordType *RT = Base.getType()->getAs<RecordType>()) { |
611 | 52.2k | const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl()); |
612 | 52.2k | if (!BaseDecl->isPolymorphic()) |
613 | 13.0k | continue; |
614 | 39.1k | |
615 | 39.1k | if (Overriders.empty() && !Base.isVirtual()36.3k ) { |
616 | 29.6k | // There are no other overriders of virtual member functions, |
617 | 29.6k | // so let the base class fill in our overriders for us. |
618 | 29.6k | Collect(BaseDecl, false, InVirtualSubobject, Overriders); |
619 | 29.6k | continue; |
620 | 29.6k | } |
621 | 9.53k | |
622 | 9.53k | // Collect all of the overridders from the base class subobject |
623 | 9.53k | // and merge them into the set of overridders for this class. |
624 | 9.53k | // For virtual base classes, populate or use the cached virtual |
625 | 9.53k | // overrides so that we do not walk the virtual base class (and |
626 | 9.53k | // its base classes) more than once. |
627 | 9.53k | CXXFinalOverriderMap ComputedBaseOverriders; |
628 | 9.53k | CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders; |
629 | 9.53k | if (Base.isVirtual()) { |
630 | 7.06k | CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl]; |
631 | 7.06k | BaseOverriders = MyVirtualOverriders; |
632 | 7.06k | if (!MyVirtualOverriders) { |
633 | 6.26k | MyVirtualOverriders = new CXXFinalOverriderMap; |
634 | 6.26k | |
635 | 6.26k | // Collect may cause VirtualOverriders to reallocate, invalidating the |
636 | 6.26k | // MyVirtualOverriders reference. Set BaseOverriders to the right |
637 | 6.26k | // value now. |
638 | 6.26k | BaseOverriders = MyVirtualOverriders; |
639 | 6.26k | |
640 | 6.26k | Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders); |
641 | 6.26k | } |
642 | 7.06k | } else |
643 | 2.46k | Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders); |
644 | 9.53k | |
645 | 9.53k | // Merge the overriders from this base class into our own set of |
646 | 9.53k | // overriders. |
647 | 9.53k | for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(), |
648 | 9.53k | OMEnd = BaseOverriders->end(); |
649 | 50.7k | OM != OMEnd; |
650 | 41.2k | ++OM) { |
651 | 41.2k | const CXXMethodDecl *CanonOM = OM->first->getCanonicalDecl(); |
652 | 41.2k | Overriders[CanonOM].add(OM->second); |
653 | 41.2k | } |
654 | 9.53k | } |
655 | 52.2k | } |
656 | 71.8k | |
657 | 873k | for (auto *M : RD->methods()) { |
658 | 873k | // We only care about virtual methods. |
659 | 873k | if (!M->isVirtual()) |
660 | 652k | continue; |
661 | 220k | |
662 | 220k | CXXMethodDecl *CanonM = M->getCanonicalDecl(); |
663 | 220k | using OverriddenMethodsRange = |
664 | 220k | llvm::iterator_range<CXXMethodDecl::method_iterator>; |
665 | 220k | OverriddenMethodsRange OverriddenMethods = CanonM->overridden_methods(); |
666 | 220k | |
667 | 220k | if (OverriddenMethods.begin() == OverriddenMethods.end()) { |
668 | 129k | // This is a new virtual function that does not override any |
669 | 129k | // other virtual function. Add it to the map of virtual |
670 | 129k | // functions for which we are tracking overridders. |
671 | 129k | |
672 | 129k | // C++ [class.virtual]p2: |
673 | 129k | // For convenience we say that any virtual function overrides itself. |
674 | 129k | Overriders[CanonM].add(SubobjectNumber, |
675 | 129k | UniqueVirtualMethod(CanonM, SubobjectNumber, |
676 | 129k | InVirtualSubobject)); |
677 | 129k | continue; |
678 | 129k | } |
679 | 90.9k | |
680 | 90.9k | // This virtual method overrides other virtual methods, so it does |
681 | 90.9k | // not add any new slots into the set of overriders. Instead, we |
682 | 90.9k | // replace entries in the set of overriders with the new |
683 | 90.9k | // overrider. To do so, we dig down to the original virtual |
684 | 90.9k | // functions using data recursion and update all of the methods it |
685 | 90.9k | // overrides. |
686 | 90.9k | SmallVector<OverriddenMethodsRange, 4> Stack(1, OverriddenMethods); |
687 | 229k | while (!Stack.empty()) { |
688 | 140k | for (const CXXMethodDecl *OM : Stack.pop_back_val()) { |
689 | 140k | const CXXMethodDecl *CanonOM = OM->getCanonicalDecl(); |
690 | 140k | |
691 | 140k | // C++ [class.virtual]p2: |
692 | 140k | // A virtual member function C::vf of a class object S is |
693 | 140k | // a final overrider unless the most derived class (1.8) |
694 | 140k | // of which S is a base class subobject (if any) declares |
695 | 140k | // or inherits another member function that overrides vf. |
696 | 140k | // |
697 | 140k | // Treating this object like the most derived class, we |
698 | 140k | // replace any overrides from base classes with this |
699 | 140k | // overriding virtual function. |
700 | 140k | Overriders[CanonOM].replaceAll( |
701 | 140k | UniqueVirtualMethod(CanonM, SubobjectNumber, |
702 | 140k | InVirtualSubobject)); |
703 | 140k | |
704 | 140k | auto OverriddenMethods = CanonOM->overridden_methods(); |
705 | 140k | if (OverriddenMethods.begin() == OverriddenMethods.end()) |
706 | 93.3k | continue; |
707 | 47.4k | |
708 | 47.4k | // Continue recursion to the methods that this virtual method |
709 | 47.4k | // overrides. |
710 | 47.4k | Stack.push_back(OverriddenMethods); |
711 | 47.4k | } |
712 | 138k | } |
713 | 90.9k | |
714 | 90.9k | // C++ [class.virtual]p2: |
715 | 90.9k | // For convenience we say that any virtual function overrides itself. |
716 | 90.9k | Overriders[CanonM].add(SubobjectNumber, |
717 | 90.9k | UniqueVirtualMethod(CanonM, SubobjectNumber, |
718 | 90.9k | InVirtualSubobject)); |
719 | 90.9k | } |
720 | 71.8k | } |
721 | | |
722 | 33.4k | FinalOverriderCollector::~FinalOverriderCollector() { |
723 | 33.4k | for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator |
724 | 33.4k | VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end(); |
725 | 39.7k | VO != VOEnd; |
726 | 33.4k | ++VO6.26k ) |
727 | 6.26k | delete VO->second; |
728 | 33.4k | } |
729 | | |
730 | | void |
731 | 33.4k | CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const { |
732 | 33.4k | FinalOverriderCollector Collector; |
733 | 33.4k | Collector.Collect(this, false, nullptr, FinalOverriders); |
734 | 33.4k | |
735 | 33.4k | // Weed out any final overriders that come from virtual base class |
736 | 33.4k | // subobjects that were hidden by other subobjects along any path. |
737 | 33.4k | // This is the final-overrider variant of C++ [class.member.lookup]p10. |
738 | 216k | for (auto &OM : FinalOverriders) { |
739 | 220k | for (auto &SO : OM.second) { |
740 | 220k | SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second; |
741 | 220k | if (Overriding.size() < 2) |
742 | 220k | continue; |
743 | 90 | |
744 | 180 | auto IsHidden = [&Overriding](const UniqueVirtualMethod &M) 90 { |
745 | 180 | if (!M.InVirtualSubobject) |
746 | 86 | return false; |
747 | 94 | |
748 | 94 | // We have an overriding method in a virtual base class |
749 | 94 | // subobject (or non-virtual base class subobject thereof); |
750 | 94 | // determine whether there exists an other overriding method |
751 | 94 | // in a base class subobject that hides the virtual base class |
752 | 94 | // subobject. |
753 | 94 | for (const UniqueVirtualMethod &OP : Overriding) |
754 | 146 | if (&M != &OP && |
755 | 146 | OP.Method->getParent()->isVirtuallyDerivedFrom( |
756 | 94 | M.InVirtualSubobject)) |
757 | 88 | return true; |
758 | 94 | return false6 ; |
759 | 94 | }; |
760 | 90 | |
761 | 90 | Overriding.erase( |
762 | 90 | std::remove_if(Overriding.begin(), Overriding.end(), IsHidden), |
763 | 90 | Overriding.end()); |
764 | 90 | } |
765 | 216k | } |
766 | 33.4k | } |
767 | | |
768 | | static void |
769 | | AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context, |
770 | 1.02k | CXXIndirectPrimaryBaseSet& Bases) { |
771 | 1.02k | // If the record has a virtual primary base class, add it to our set. |
772 | 1.02k | const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); |
773 | 1.02k | if (Layout.isPrimaryBaseVirtual()) |
774 | 155 | Bases.insert(Layout.getPrimaryBase()); |
775 | 1.02k | |
776 | 1.45k | for (const auto &I : RD->bases()) { |
777 | 1.45k | assert(!I.getType()->isDependentType() && |
778 | 1.45k | "Cannot get indirect primary bases for class with dependent bases."); |
779 | 1.45k | |
780 | 1.45k | const CXXRecordDecl *BaseDecl = |
781 | 1.45k | cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl()); |
782 | 1.45k | |
783 | 1.45k | // Only bases with virtual bases participate in computing the |
784 | 1.45k | // indirect primary virtual base classes. |
785 | 1.45k | if (BaseDecl->getNumVBases()) |
786 | 480 | AddIndirectPrimaryBases(BaseDecl, Context, Bases); |
787 | 1.45k | } |
788 | 1.02k | |
789 | 1.02k | } |
790 | | |
791 | | void |
792 | 14.5k | CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const { |
793 | 14.5k | ASTContext &Context = getASTContext(); |
794 | 14.5k | |
795 | 14.5k | if (!getNumVBases()) |
796 | 13.4k | return; |
797 | 1.04k | |
798 | 1.33k | for (const auto &I : bases())1.04k { |
799 | 1.33k | assert(!I.getType()->isDependentType() && |
800 | 1.33k | "Cannot get indirect primary bases for class with dependent bases."); |
801 | 1.33k | |
802 | 1.33k | const CXXRecordDecl *BaseDecl = |
803 | 1.33k | cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl()); |
804 | 1.33k | |
805 | 1.33k | // Only bases with virtual bases participate in computing the |
806 | 1.33k | // indirect primary virtual base classes. |
807 | 1.33k | if (BaseDecl->getNumVBases()) |
808 | 544 | AddIndirectPrimaryBases(BaseDecl, Context, Bases); |
809 | 1.33k | } |
810 | 1.04k | } |