/Users/buildslave/jenkins/workspace/coverage/llvm-project/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 | | /// isAmbiguous - Determines whether the set of paths provided is |
37 | | /// ambiguous, i.e., there are two or more paths that refer to |
38 | | /// different base class subobjects of the same type. BaseType must be |
39 | | /// an unqualified, canonical class type. |
40 | 37.4k | bool CXXBasePaths::isAmbiguous(CanQualType BaseType) { |
41 | 37.4k | BaseType = BaseType.getUnqualifiedType(); |
42 | 37.4k | IsVirtBaseAndNumberNonVirtBases Subobjects = ClassSubobjects[BaseType]; |
43 | 37.4k | return Subobjects.NumberOfNonVirtBases + (Subobjects.IsVirtBase ? 11.21k : 036.2k ) > 1; |
44 | 37.4k | } |
45 | | |
46 | | /// clear - Clear out all prior path information. |
47 | 56 | void CXXBasePaths::clear() { |
48 | 56 | Paths.clear(); |
49 | 56 | ClassSubobjects.clear(); |
50 | 56 | VisitedDependentRecords.clear(); |
51 | 56 | ScratchPath.clear(); |
52 | 56 | DetectedVirtual = nullptr; |
53 | 56 | } |
54 | | |
55 | | /// Swaps the contents of this CXXBasePaths structure with the |
56 | | /// contents of Other. |
57 | 122 | void CXXBasePaths::swap(CXXBasePaths &Other) { |
58 | 122 | std::swap(Origin, Other.Origin); |
59 | 122 | Paths.swap(Other.Paths); |
60 | 122 | ClassSubobjects.swap(Other.ClassSubobjects); |
61 | 122 | VisitedDependentRecords.swap(Other.VisitedDependentRecords); |
62 | 122 | std::swap(FindAmbiguities, Other.FindAmbiguities); |
63 | 122 | std::swap(RecordPaths, Other.RecordPaths); |
64 | 122 | std::swap(DetectVirtual, Other.DetectVirtual); |
65 | 122 | std::swap(DetectedVirtual, Other.DetectedVirtual); |
66 | 122 | } |
67 | | |
68 | 581k | bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const { |
69 | 581k | CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, |
70 | 581k | /*DetectVirtual=*/false); |
71 | 581k | return isDerivedFrom(Base, Paths); |
72 | 581k | } |
73 | | |
74 | | bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base, |
75 | 688k | CXXBasePaths &Paths) const { |
76 | 688k | if (getCanonicalDecl() == Base->getCanonicalDecl()) |
77 | 32.0k | return false; |
78 | | |
79 | 656k | Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); |
80 | | |
81 | 656k | const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl(); |
82 | 656k | return lookupInBases( |
83 | 656k | [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
84 | 276k | return FindBaseClass(Specifier, Path, BaseDecl); |
85 | 276k | }, |
86 | 656k | Paths); |
87 | 688k | } |
88 | | |
89 | 8.74k | bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const { |
90 | 8.74k | if (!getNumVBases()) |
91 | 6.85k | return false; |
92 | | |
93 | 1.89k | CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, |
94 | 1.89k | /*DetectVirtual=*/false); |
95 | | |
96 | 1.89k | if (getCanonicalDecl() == Base->getCanonicalDecl()) |
97 | 735 | return false; |
98 | | |
99 | 1.15k | Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); |
100 | | |
101 | 1.15k | const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl(); |
102 | 1.15k | return lookupInBases( |
103 | 3.40k | [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
104 | 3.40k | return FindVirtualBaseClass(Specifier, Path, BaseDecl); |
105 | 3.40k | }, |
106 | 1.15k | Paths); |
107 | 1.89k | } |
108 | | |
109 | 13.4k | bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const { |
110 | 13.4k | const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl(); |
111 | 14.0k | return forallBases([TargetDecl](const CXXRecordDecl *Base) { |
112 | 14.0k | return Base->getCanonicalDecl() != TargetDecl; |
113 | 14.0k | }); |
114 | 13.4k | } |
115 | | |
116 | | bool |
117 | 779k | CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const { |
118 | 779k | assert(isDependentContext()); |
119 | | |
120 | 804k | for (; !CurContext->isFileContext(); CurContext = CurContext->getParent()25.1k ) |
121 | 789k | if (CurContext->Equals(this)) |
122 | 764k | return true; |
123 | | |
124 | 15.7k | return false; |
125 | 779k | } |
126 | | |
127 | 22.0k | bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches) const { |
128 | 22.0k | SmallVector<const CXXRecordDecl*, 8> Queue; |
129 | | |
130 | 22.0k | const CXXRecordDecl *Record = this; |
131 | 23.6k | while (true) { |
132 | 23.6k | for (const auto &I : Record->bases()) { |
133 | 23.2k | const RecordType *Ty = I.getType()->getAs<RecordType>(); |
134 | 23.2k | if (!Ty) |
135 | 685 | return false; |
136 | | |
137 | 22.5k | CXXRecordDecl *Base = |
138 | 22.5k | cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition()); |
139 | 22.5k | if (!Base || |
140 | 22.5k | (22.5k Base->isDependentContext()22.5k && |
141 | 22.5k | !Base->isCurrentInstantiation(Record)6 )) { |
142 | 8 | return false; |
143 | 8 | } |
144 | | |
145 | 22.5k | Queue.push_back(Base); |
146 | 22.5k | if (!BaseMatches(Base)) |
147 | 20.1k | return false; |
148 | 22.5k | } |
149 | | |
150 | 2.78k | if (Queue.empty()) |
151 | 1.25k | break; |
152 | 1.52k | Record = Queue.pop_back_val(); // not actually a queue. |
153 | 1.52k | } |
154 | | |
155 | 1.25k | return true; |
156 | 22.0k | } |
157 | | |
158 | | bool CXXBasePaths::lookupInBases(ASTContext &Context, |
159 | | const CXXRecordDecl *Record, |
160 | | CXXRecordDecl::BaseMatchesCallback BaseMatches, |
161 | 12.3M | bool LookupInDependent) { |
162 | 12.3M | bool FoundPath = false; |
163 | | |
164 | | // The access of the path down to this record. |
165 | 12.3M | AccessSpecifier AccessToHere = ScratchPath.Access; |
166 | 12.3M | bool IsFirstStep = ScratchPath.empty(); |
167 | | |
168 | 12.3M | for (const auto &BaseSpec : Record->bases()) { |
169 | | // Find the record of the base class subobjects for this type. |
170 | 5.09M | QualType BaseType = |
171 | 5.09M | Context.getCanonicalType(BaseSpec.getType()).getUnqualifiedType(); |
172 | | |
173 | | // C++ [temp.dep]p3: |
174 | | // In the definition of a class template or a member of a class template, |
175 | | // if a base class of the class template depends on a template-parameter, |
176 | | // the base class scope is not examined during unqualified name lookup |
177 | | // either at the point of definition of the class template or member or |
178 | | // during an instantiation of the class tem- plate or member. |
179 | 5.09M | if (!LookupInDependent && BaseType->isDependentType()5.09M ) |
180 | 820k | continue; |
181 | | |
182 | | // Determine whether we need to visit this base class at all, |
183 | | // updating the count of subobjects appropriately. |
184 | 4.27M | IsVirtBaseAndNumberNonVirtBases &Subobjects = ClassSubobjects[BaseType]; |
185 | 4.27M | bool VisitBase = true; |
186 | 4.27M | bool SetVirtual = false; |
187 | 4.27M | if (BaseSpec.isVirtual()) { |
188 | 50.3k | VisitBase = !Subobjects.IsVirtBase; |
189 | 50.3k | Subobjects.IsVirtBase = true; |
190 | 50.3k | if (isDetectingVirtual() && DetectedVirtual == nullptr7.34k ) { |
191 | | // If this is the first virtual we find, remember it. If it turns out |
192 | | // there is no base path here, we'll reset it later. |
193 | 6.00k | DetectedVirtual = BaseType->getAs<RecordType>(); |
194 | 6.00k | SetVirtual = true; |
195 | 6.00k | } |
196 | 4.22M | } else { |
197 | 4.22M | ++Subobjects.NumberOfNonVirtBases; |
198 | 4.22M | } |
199 | 4.27M | if (isRecordingPaths()) { |
200 | | // Add this base specifier to the current path. |
201 | 1.33M | CXXBasePathElement Element; |
202 | 1.33M | Element.Base = &BaseSpec; |
203 | 1.33M | Element.Class = Record; |
204 | 1.33M | if (BaseSpec.isVirtual()) |
205 | 9.27k | Element.SubobjectNumber = 0; |
206 | 1.32M | else |
207 | 1.32M | Element.SubobjectNumber = Subobjects.NumberOfNonVirtBases; |
208 | 1.33M | ScratchPath.push_back(Element); |
209 | | |
210 | | // Calculate the "top-down" access to this base class. |
211 | | // The spec actually describes this bottom-up, but top-down is |
212 | | // equivalent because the definition works out as follows: |
213 | | // 1. Write down the access along each step in the inheritance |
214 | | // chain, followed by the access of the decl itself. |
215 | | // For example, in |
216 | | // class A { public: int foo; }; |
217 | | // class B : protected A {}; |
218 | | // class C : public B {}; |
219 | | // class D : private C {}; |
220 | | // we would write: |
221 | | // private public protected public |
222 | | // 2. If 'private' appears anywhere except far-left, access is denied. |
223 | | // 3. Otherwise, overall access is determined by the most restrictive |
224 | | // access in the sequence. |
225 | 1.33M | if (IsFirstStep) |
226 | 1.05M | ScratchPath.Access = BaseSpec.getAccessSpecifier(); |
227 | 276k | else |
228 | 276k | ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere, |
229 | 276k | BaseSpec.getAccessSpecifier()); |
230 | 1.33M | } |
231 | | |
232 | | // Track whether there's a path involving this specific base. |
233 | 4.27M | bool FoundPathThroughBase = false; |
234 | | |
235 | 4.27M | if (BaseMatches(&BaseSpec, ScratchPath)) { |
236 | | // We've found a path that terminates at this base. |
237 | 893k | FoundPath = FoundPathThroughBase = true; |
238 | 893k | if (isRecordingPaths()) { |
239 | | // We have a path. Make a copy of it before moving on. |
240 | 792k | Paths.push_back(ScratchPath); |
241 | 792k | } else if (100k !isFindingAmbiguities()100k ) { |
242 | | // We found a path and we don't care about ambiguities; |
243 | | // return immediately. |
244 | 65.2k | return FoundPath; |
245 | 65.2k | } |
246 | 3.37M | } else if (VisitBase) { |
247 | 3.37M | CXXRecordDecl *BaseRecord; |
248 | 3.37M | if (LookupInDependent) { |
249 | 245 | BaseRecord = nullptr; |
250 | 245 | const TemplateSpecializationType *TST = |
251 | 245 | BaseSpec.getType()->getAs<TemplateSpecializationType>(); |
252 | 245 | if (!TST) { |
253 | 235 | if (auto *RT = BaseSpec.getType()->getAs<RecordType>()) |
254 | 231 | BaseRecord = cast<CXXRecordDecl>(RT->getDecl()); |
255 | 235 | } else { |
256 | 10 | TemplateName TN = TST->getTemplateName(); |
257 | 10 | if (auto *TD = |
258 | 10 | dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl())) |
259 | 10 | BaseRecord = TD->getTemplatedDecl(); |
260 | 10 | } |
261 | 245 | if (BaseRecord) { |
262 | 241 | if (!BaseRecord->hasDefinition() || |
263 | 241 | VisitedDependentRecords.count(BaseRecord)239 ) { |
264 | 3 | BaseRecord = nullptr; |
265 | 238 | } else { |
266 | 238 | VisitedDependentRecords.insert(BaseRecord); |
267 | 238 | } |
268 | 241 | } |
269 | 3.37M | } else { |
270 | 3.37M | BaseRecord = cast<CXXRecordDecl>( |
271 | 3.37M | BaseSpec.getType()->castAs<RecordType>()->getDecl()); |
272 | 3.37M | } |
273 | 3.37M | if (BaseRecord && |
274 | 3.37M | lookupInBases(Context, BaseRecord, BaseMatches, LookupInDependent)3.37M ) { |
275 | | // C++ [class.member.lookup]p2: |
276 | | // A member name f in one sub-object B hides a member name f in |
277 | | // a sub-object A if A is a base class sub-object of B. Any |
278 | | // declarations that are so hidden are eliminated from |
279 | | // consideration. |
280 | | |
281 | | // There is a path to a base class that meets the criteria. If we're |
282 | | // not collecting paths or finding ambiguities, we're done. |
283 | 150k | FoundPath = FoundPathThroughBase = true; |
284 | 150k | if (!isFindingAmbiguities()) |
285 | 18.7k | return FoundPath; |
286 | 150k | } |
287 | 3.37M | } |
288 | | |
289 | | // Pop this base specifier off the current path (if we're |
290 | | // collecting paths). |
291 | 4.18M | if (isRecordingPaths()) { |
292 | 1.33M | ScratchPath.pop_back(); |
293 | 1.33M | } |
294 | | |
295 | | // If we set a virtual earlier, and this isn't a path, forget it again. |
296 | 4.18M | if (SetVirtual && !FoundPathThroughBase6.00k ) { |
297 | 3.62k | DetectedVirtual = nullptr; |
298 | 3.62k | } |
299 | 4.18M | } |
300 | | |
301 | | // Reset the scratch path access. |
302 | 12.2M | ScratchPath.Access = AccessToHere; |
303 | | |
304 | 12.2M | return FoundPath; |
305 | 12.3M | } |
306 | | |
307 | | bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches, |
308 | | CXXBasePaths &Paths, |
309 | 8.95M | bool LookupInDependent) const { |
310 | | // If we didn't find anything, report that. |
311 | 8.95M | if (!Paths.lookupInBases(getASTContext(), this, BaseMatches, |
312 | 8.95M | LookupInDependent)) |
313 | 8.06M | return false; |
314 | | |
315 | | // If we're not recording paths or we won't ever find ambiguities, |
316 | | // we're done. |
317 | 891k | if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities()790k ) |
318 | 100k | return true; |
319 | | |
320 | | // C++ [class.member.lookup]p6: |
321 | | // When virtual base classes are used, a hidden declaration can be |
322 | | // reached along a path through the sub-object lattice that does |
323 | | // not pass through the hiding declaration. This is not an |
324 | | // ambiguity. The identical use with nonvirtual base classes is an |
325 | | // ambiguity; in that case there is no unique instance of the name |
326 | | // that hides all the others. |
327 | | // |
328 | | // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy |
329 | | // way to make it any faster. |
330 | 792k | Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) 790k { |
331 | 922k | for (const CXXBasePathElement &PE : Path) { |
332 | 922k | if (!PE.Base->isVirtual()) |
333 | 917k | continue; |
334 | | |
335 | 4.78k | CXXRecordDecl *VBase = nullptr; |
336 | 4.78k | if (const RecordType *Record = PE.Base->getType()->getAs<RecordType>()) |
337 | 4.78k | VBase = cast<CXXRecordDecl>(Record->getDecl()); |
338 | 4.78k | if (!VBase) |
339 | 0 | break; |
340 | | |
341 | | // The declaration(s) we found along this path were found in a |
342 | | // subobject of a virtual base. Check whether this virtual |
343 | | // base is a subobject of any other path; if so, then the |
344 | | // declaration in this path are hidden by that patch. |
345 | 8.45k | for (const CXXBasePath &HidingP : Paths)4.78k { |
346 | 8.45k | CXXRecordDecl *HidingClass = nullptr; |
347 | 8.45k | if (const RecordType *Record = |
348 | 8.45k | HidingP.back().Base->getType()->getAs<RecordType>()) |
349 | 8.45k | HidingClass = cast<CXXRecordDecl>(Record->getDecl()); |
350 | 8.45k | if (!HidingClass) |
351 | 0 | break; |
352 | | |
353 | 8.45k | if (HidingClass->isVirtuallyDerivedFrom(VBase)) |
354 | 21 | return true; |
355 | 8.45k | } |
356 | 4.78k | } |
357 | 792k | return false; |
358 | 792k | }); |
359 | | |
360 | 790k | return true; |
361 | 891k | } |
362 | | |
363 | | bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier, |
364 | | CXXBasePath &Path, |
365 | 276k | const CXXRecordDecl *BaseRecord) { |
366 | 276k | assert(BaseRecord->getCanonicalDecl() == BaseRecord && |
367 | 276k | "User data for FindBaseClass is not canonical!"); |
368 | 0 | return Specifier->getType()->castAs<RecordType>()->getDecl() |
369 | 276k | ->getCanonicalDecl() == BaseRecord; |
370 | 276k | } |
371 | | |
372 | | bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier, |
373 | | CXXBasePath &Path, |
374 | 3.40k | const CXXRecordDecl *BaseRecord) { |
375 | 3.40k | assert(BaseRecord->getCanonicalDecl() == BaseRecord && |
376 | 3.40k | "User data for FindBaseClass is not canonical!"); |
377 | 3.40k | return Specifier->isVirtual() && |
378 | 3.40k | Specifier->getType()->castAs<RecordType>()->getDecl() |
379 | 2.29k | ->getCanonicalDecl() == BaseRecord; |
380 | 3.40k | } |
381 | | |
382 | 285 | static bool isOrdinaryMember(const NamedDecl *ND) { |
383 | 285 | return ND->isInIdentifierNamespace(Decl::IDNS_Ordinary | Decl::IDNS_Tag | |
384 | 285 | Decl::IDNS_Member); |
385 | 285 | } |
386 | | |
387 | | static bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path, |
388 | 586 | DeclarationName Name) { |
389 | 586 | Path.Decls = RD->lookup(Name).begin(); |
390 | 586 | for (DeclContext::lookup_iterator I = Path.Decls, E = I.end(); I != E; ++I0 ) |
391 | 243 | if (isOrdinaryMember(*I)) |
392 | 243 | return true; |
393 | | |
394 | 343 | return false; |
395 | 586 | } |
396 | | |
397 | 530 | bool CXXRecordDecl::hasMemberName(DeclarationName Name) const { |
398 | 530 | CXXBasePath P; |
399 | 530 | if (findOrdinaryMember(this, P, Name)) |
400 | 229 | return true; |
401 | | |
402 | 301 | CXXBasePaths Paths(false, false, false); |
403 | 301 | return lookupInBases( |
404 | 301 | [Name](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
405 | 33 | return findOrdinaryMember(Specifier->getType()->getAsCXXRecordDecl(), |
406 | 33 | Path, Name); |
407 | 33 | }, |
408 | 301 | Paths); |
409 | 530 | } |
410 | | |
411 | | static bool |
412 | | findOrdinaryMemberInDependentClasses(const CXXBaseSpecifier *Specifier, |
413 | 23 | CXXBasePath &Path, DeclarationName Name) { |
414 | 23 | const TemplateSpecializationType *TST = |
415 | 23 | Specifier->getType()->getAs<TemplateSpecializationType>(); |
416 | 23 | if (!TST) { |
417 | 10 | auto *RT = Specifier->getType()->getAs<RecordType>(); |
418 | 10 | if (!RT) |
419 | 0 | return false; |
420 | 10 | return findOrdinaryMember(cast<CXXRecordDecl>(RT->getDecl()), Path, Name); |
421 | 10 | } |
422 | 13 | TemplateName TN = TST->getTemplateName(); |
423 | 13 | const auto *TD = dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl()); |
424 | 13 | if (!TD) |
425 | 0 | return false; |
426 | 13 | CXXRecordDecl *RD = TD->getTemplatedDecl(); |
427 | 13 | if (!RD) |
428 | 0 | return false; |
429 | 13 | return findOrdinaryMember(RD, Path, Name); |
430 | 13 | } |
431 | | |
432 | | std::vector<const NamedDecl *> CXXRecordDecl::lookupDependentName( |
433 | | DeclarationName Name, |
434 | 45 | llvm::function_ref<bool(const NamedDecl *ND)> Filter) { |
435 | 45 | std::vector<const NamedDecl *> Results; |
436 | | // Lookup in the class. |
437 | 45 | bool AnyOrdinaryMembers = false; |
438 | 45 | for (const NamedDecl *ND : lookup(Name)) { |
439 | 34 | if (isOrdinaryMember(ND)) |
440 | 34 | AnyOrdinaryMembers = true; |
441 | 34 | if (Filter(ND)) |
442 | 26 | Results.push_back(ND); |
443 | 34 | } |
444 | 45 | if (AnyOrdinaryMembers) |
445 | 31 | return Results; |
446 | | |
447 | | // Perform lookup into our base classes. |
448 | 14 | CXXBasePaths Paths; |
449 | 14 | Paths.setOrigin(this); |
450 | 14 | if (!lookupInBases( |
451 | 23 | [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
452 | 23 | return findOrdinaryMemberInDependentClasses(Specifier, Path, Name); |
453 | 23 | }, |
454 | 14 | Paths, /*LookupInDependent=*/true)) |
455 | 6 | return Results; |
456 | 8 | for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end(); |
457 | 16 | I != E; ++I8 ) { |
458 | 8 | if (isOrdinaryMember(*I) && Filter(*I)) |
459 | 8 | Results.push_back(*I); |
460 | 8 | } |
461 | 8 | return Results; |
462 | 14 | } |
463 | | |
464 | | void OverridingMethods::add(unsigned OverriddenSubobject, |
465 | 77.8k | UniqueVirtualMethod Overriding) { |
466 | 77.8k | SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides |
467 | 77.8k | = Overrides[OverriddenSubobject]; |
468 | 77.8k | if (!llvm::is_contained(SubobjectOverrides, Overriding)) |
469 | 77.6k | SubobjectOverrides.push_back(Overriding); |
470 | 77.8k | } |
471 | | |
472 | 31.4k | void OverridingMethods::add(const OverridingMethods &Other) { |
473 | 63.0k | for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I31.5k ) { |
474 | 31.5k | for (overriding_const_iterator M = I->second.begin(), |
475 | 31.5k | MEnd = I->second.end(); |
476 | 63.1k | M != MEnd; |
477 | 31.5k | ++M) |
478 | 31.5k | add(I->first, *M); |
479 | 31.5k | } |
480 | 31.4k | } |
481 | | |
482 | 42.4k | void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) { |
483 | 85.0k | for (iterator I = begin(), IEnd = end(); I != IEnd; ++I42.6k ) { |
484 | 42.6k | I->second.clear(); |
485 | 42.6k | I->second.push_back(Overriding); |
486 | 42.6k | } |
487 | 42.4k | } |
488 | | |
489 | | namespace { |
490 | | |
491 | | class FinalOverriderCollector { |
492 | | /// The number of subobjects of a given class type that |
493 | | /// occur within the class hierarchy. |
494 | | llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount; |
495 | | |
496 | | /// Overriders for each virtual base subobject. |
497 | | llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders; |
498 | | |
499 | | CXXFinalOverriderMap FinalOverriders; |
500 | | |
501 | | public: |
502 | | ~FinalOverriderCollector(); |
503 | | |
504 | | void Collect(const CXXRecordDecl *RD, bool VirtualBase, |
505 | | const CXXRecordDecl *InVirtualSubobject, |
506 | | CXXFinalOverriderMap &Overriders); |
507 | | }; |
508 | | |
509 | | } // namespace |
510 | | |
511 | | void FinalOverriderCollector::Collect(const CXXRecordDecl *RD, |
512 | | bool VirtualBase, |
513 | | const CXXRecordDecl *InVirtualSubobject, |
514 | 42.3k | CXXFinalOverriderMap &Overriders) { |
515 | 42.3k | unsigned SubobjectNumber = 0; |
516 | 42.3k | if (!VirtualBase) |
517 | 37.3k | SubobjectNumber |
518 | 37.3k | = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())]; |
519 | | |
520 | 42.3k | for (const auto &Base : RD->bases()) { |
521 | 38.1k | if (const RecordType *RT = Base.getType()->getAs<RecordType>()) { |
522 | 38.1k | const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl()); |
523 | 38.1k | if (!BaseDecl->isPolymorphic()) |
524 | 22.3k | continue; |
525 | | |
526 | 15.7k | if (Overriders.empty() && !Base.isVirtual()13.9k ) { |
527 | | // There are no other overriders of virtual member functions, |
528 | | // so let the base class fill in our overriders for us. |
529 | 8.89k | Collect(BaseDecl, false, InVirtualSubobject, Overriders); |
530 | 8.89k | continue; |
531 | 8.89k | } |
532 | | |
533 | | // Collect all of the overridders from the base class subobject |
534 | | // and merge them into the set of overridders for this class. |
535 | | // For virtual base classes, populate or use the cached virtual |
536 | | // overrides so that we do not walk the virtual base class (and |
537 | | // its base classes) more than once. |
538 | 6.85k | CXXFinalOverriderMap ComputedBaseOverriders; |
539 | 6.85k | CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders; |
540 | 6.85k | if (Base.isVirtual()) { |
541 | 5.44k | CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl]; |
542 | 5.44k | BaseOverriders = MyVirtualOverriders; |
543 | 5.44k | if (!MyVirtualOverriders) { |
544 | 5.02k | MyVirtualOverriders = new CXXFinalOverriderMap; |
545 | | |
546 | | // Collect may cause VirtualOverriders to reallocate, invalidating the |
547 | | // MyVirtualOverriders reference. Set BaseOverriders to the right |
548 | | // value now. |
549 | 5.02k | BaseOverriders = MyVirtualOverriders; |
550 | | |
551 | 5.02k | Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders); |
552 | 5.02k | } |
553 | 5.44k | } else |
554 | 1.41k | Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders); |
555 | | |
556 | | // Merge the overriders from this base class into our own set of |
557 | | // overriders. |
558 | 6.85k | for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(), |
559 | 6.85k | OMEnd = BaseOverriders->end(); |
560 | 38.3k | OM != OMEnd; |
561 | 31.4k | ++OM) { |
562 | 31.4k | const CXXMethodDecl *CanonOM = OM->first->getCanonicalDecl(); |
563 | 31.4k | Overriders[CanonOM].add(OM->second); |
564 | 31.4k | } |
565 | 6.85k | } |
566 | 38.1k | } |
567 | | |
568 | 322k | for (auto *M : RD->methods()) { |
569 | | // We only care about virtual methods. |
570 | 322k | if (!M->isVirtual()) |
571 | 276k | continue; |
572 | | |
573 | 46.2k | CXXMethodDecl *CanonM = M->getCanonicalDecl(); |
574 | 46.2k | using OverriddenMethodsRange = |
575 | 46.2k | llvm::iterator_range<CXXMethodDecl::method_iterator>; |
576 | 46.2k | OverriddenMethodsRange OverriddenMethods = CanonM->overridden_methods(); |
577 | | |
578 | 46.2k | if (OverriddenMethods.begin() == OverriddenMethods.end()) { |
579 | | // This is a new virtual function that does not override any |
580 | | // other virtual function. Add it to the map of virtual |
581 | | // functions for which we are tracking overridders. |
582 | | |
583 | | // C++ [class.virtual]p2: |
584 | | // For convenience we say that any virtual function overrides itself. |
585 | 29.5k | Overriders[CanonM].add(SubobjectNumber, |
586 | 29.5k | UniqueVirtualMethod(CanonM, SubobjectNumber, |
587 | 29.5k | InVirtualSubobject)); |
588 | 29.5k | continue; |
589 | 29.5k | } |
590 | | |
591 | | // This virtual method overrides other virtual methods, so it does |
592 | | // not add any new slots into the set of overriders. Instead, we |
593 | | // replace entries in the set of overriders with the new |
594 | | // overrider. To do so, we dig down to the original virtual |
595 | | // functions using data recursion and update all of the methods it |
596 | | // overrides. |
597 | 16.7k | SmallVector<OverriddenMethodsRange, 4> Stack(1, OverriddenMethods); |
598 | 58.2k | while (!Stack.empty()) { |
599 | 42.4k | for (const CXXMethodDecl *OM : Stack.pop_back_val()) { |
600 | 42.4k | const CXXMethodDecl *CanonOM = OM->getCanonicalDecl(); |
601 | | |
602 | | // C++ [class.virtual]p2: |
603 | | // A virtual member function C::vf of a class object S is |
604 | | // a final overrider unless the most derived class (1.8) |
605 | | // of which S is a base class subobject (if any) declares |
606 | | // or inherits another member function that overrides vf. |
607 | | // |
608 | | // Treating this object like the most derived class, we |
609 | | // replace any overrides from base classes with this |
610 | | // overriding virtual function. |
611 | 42.4k | Overriders[CanonOM].replaceAll( |
612 | 42.4k | UniqueVirtualMethod(CanonM, SubobjectNumber, |
613 | 42.4k | InVirtualSubobject)); |
614 | | |
615 | 42.4k | auto OverriddenMethods = CanonOM->overridden_methods(); |
616 | 42.4k | if (OverriddenMethods.begin() == OverriddenMethods.end()) |
617 | 17.6k | continue; |
618 | | |
619 | | // Continue recursion to the methods that this virtual method |
620 | | // overrides. |
621 | 24.7k | Stack.push_back(OverriddenMethods); |
622 | 24.7k | } |
623 | 41.4k | } |
624 | | |
625 | | // C++ [class.virtual]p2: |
626 | | // For convenience we say that any virtual function overrides itself. |
627 | 16.7k | Overriders[CanonM].add(SubobjectNumber, |
628 | 16.7k | UniqueVirtualMethod(CanonM, SubobjectNumber, |
629 | 16.7k | InVirtualSubobject)); |
630 | 16.7k | } |
631 | 42.3k | } |
632 | | |
633 | 27.0k | FinalOverriderCollector::~FinalOverriderCollector() { |
634 | 27.0k | for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator |
635 | 27.0k | VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end(); |
636 | 32.0k | VO != VOEnd; |
637 | 27.0k | ++VO5.02k ) |
638 | 5.02k | delete VO->second; |
639 | 27.0k | } |
640 | | |
641 | | void |
642 | 27.0k | CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const { |
643 | 27.0k | FinalOverriderCollector Collector; |
644 | 27.0k | Collector.Collect(this, false, nullptr, FinalOverriders); |
645 | | |
646 | | // Weed out any final overriders that come from virtual base class |
647 | | // subobjects that were hidden by other subobjects along any path. |
648 | | // This is the final-overrider variant of C++ [class.member.lookup]p10. |
649 | 45.8k | for (auto &OM : FinalOverriders) { |
650 | 46.2k | for (auto &SO : OM.second) { |
651 | 46.2k | SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second; |
652 | 46.2k | if (Overriding.size() < 2) |
653 | 46.1k | continue; |
654 | | |
655 | 196 | auto IsHidden = [&Overriding](const UniqueVirtualMethod &M) 98 { |
656 | 196 | if (!M.InVirtualSubobject) |
657 | 94 | return false; |
658 | | |
659 | | // We have an overriding method in a virtual base class |
660 | | // subobject (or non-virtual base class subobject thereof); |
661 | | // determine whether there exists an other overriding method |
662 | | // in a base class subobject that hides the virtual base class |
663 | | // subobject. |
664 | 102 | for (const UniqueVirtualMethod &OP : Overriding) |
665 | 158 | if (&M != &OP && |
666 | 158 | OP.Method->getParent()->isVirtuallyDerivedFrom( |
667 | 102 | M.InVirtualSubobject)) |
668 | 96 | return true; |
669 | 6 | return false; |
670 | 102 | }; |
671 | | |
672 | | // FIXME: IsHidden reads from Overriding from the middle of a remove_if |
673 | | // over the same sequence! Is this guaranteed to work? |
674 | 98 | llvm::erase_if(Overriding, IsHidden); |
675 | 98 | } |
676 | 45.8k | } |
677 | 27.0k | } |
678 | | |
679 | | static void |
680 | | AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context, |
681 | 1.13k | CXXIndirectPrimaryBaseSet& Bases) { |
682 | | // If the record has a virtual primary base class, add it to our set. |
683 | 1.13k | const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); |
684 | 1.13k | if (Layout.isPrimaryBaseVirtual()) |
685 | 215 | Bases.insert(Layout.getPrimaryBase()); |
686 | | |
687 | 1.56k | for (const auto &I : RD->bases()) { |
688 | 1.56k | assert(!I.getType()->isDependentType() && |
689 | 1.56k | "Cannot get indirect primary bases for class with dependent bases."); |
690 | | |
691 | 0 | const CXXRecordDecl *BaseDecl = |
692 | 1.56k | cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl()); |
693 | | |
694 | | // Only bases with virtual bases participate in computing the |
695 | | // indirect primary virtual base classes. |
696 | 1.56k | if (BaseDecl->getNumVBases()) |
697 | 486 | AddIndirectPrimaryBases(BaseDecl, Context, Bases); |
698 | 1.56k | } |
699 | | |
700 | 1.13k | } |
701 | | |
702 | | void |
703 | 17.3k | CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const { |
704 | 17.3k | ASTContext &Context = getASTContext(); |
705 | | |
706 | 17.3k | if (!getNumVBases()) |
707 | 16.0k | return; |
708 | | |
709 | 1.70k | for (const auto &I : bases())1.27k { |
710 | 1.70k | assert(!I.getType()->isDependentType() && |
711 | 1.70k | "Cannot get indirect primary bases for class with dependent bases."); |
712 | | |
713 | 0 | const CXXRecordDecl *BaseDecl = |
714 | 1.70k | cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl()); |
715 | | |
716 | | // Only bases with virtual bases participate in computing the |
717 | | // indirect primary virtual base classes. |
718 | 1.70k | if (BaseDecl->getNumVBases()) |
719 | 649 | AddIndirectPrimaryBases(BaseDecl, Context, Bases); |
720 | 1.70k | } |
721 | 1.27k | } |