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/SmallVector.h"
26#include "llvm/ADT/iterator_range.h"
27#include "llvm/Support/Casting.h"
28#include <algorithm>
29#include <utility>
30#include <cassert>
31#include <vector>
32
33using namespace clang;
34
35/// isAmbiguous - Determines whether the set of paths provided is
36/// ambiguous, i.e., there are two or more paths that refer to
37/// different base class subobjects of the same type. BaseType must be
38/// an unqualified, canonical class type.
39bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
40 BaseType = BaseType.getUnqualifiedType();
41 IsVirtBaseAndNumberNonVirtBases Subobjects = ClassSubobjects[BaseType];
42 return Subobjects.NumberOfNonVirtBases + (Subobjects.IsVirtBase ? 1 : 0) > 1;
43}
44
45/// clear - Clear out all prior path information.
46void CXXBasePaths::clear() {
47 Paths.clear();
48 ClassSubobjects.clear();
49 VisitedDependentRecords.clear();
50 ScratchPath.clear();
51 DetectedVirtual = nullptr;
52}
53
54/// Swaps the contents of this CXXBasePaths structure with the
55/// contents of Other.
56void CXXBasePaths::swap(CXXBasePaths &Other) {
57 std::swap(a&: Origin, b&: Other.Origin);
58 Paths.swap(x&: Other.Paths);
59 ClassSubobjects.swap(RHS&: Other.ClassSubobjects);
60 VisitedDependentRecords.swap(RHS&: Other.VisitedDependentRecords);
61 std::swap(a&: FindAmbiguities, b&: Other.FindAmbiguities);
62 std::swap(a&: RecordPaths, b&: Other.RecordPaths);
63 std::swap(a&: DetectVirtual, b&: Other.DetectVirtual);
64 std::swap(a&: DetectedVirtual, b&: Other.DetectedVirtual);
65}
66
67bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const {
68 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
69 /*DetectVirtual=*/false);
70 return isDerivedFrom(Base, Paths);
71}
72
73bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base,
74 CXXBasePaths &Paths) const {
75 if (getCanonicalDecl() == Base->getCanonicalDecl())
76 return false;
77
78 Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
79
80 const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
81 return lookupInBases(
82 BaseMatches: [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
83 return Specifier->getType()->getAsRecordDecl() &&
84 FindBaseClass(Specifier, Path, BaseRecord: BaseDecl);
85 },
86 Paths);
87}
88
89bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const {
90 if (!getNumVBases())
91 return false;
92
93 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
94 /*DetectVirtual=*/false);
95
96 if (getCanonicalDecl() == Base->getCanonicalDecl())
97 return false;
98
99 Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
100
101 const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
102 return lookupInBases(
103 BaseMatches: [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
104 return FindVirtualBaseClass(Specifier, Path, BaseRecord: BaseDecl);
105 },
106 Paths);
107}
108
109bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
110 const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl();
111 return forallBases(BaseMatches: [TargetDecl](const CXXRecordDecl *Base) {
112 return Base->getCanonicalDecl() != TargetDecl;
113 });
114}
115
116bool
117CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const {
118 assert(isDependentContext());
119
120 for (; !CurContext->isFileContext(); CurContext = CurContext->getParent())
121 if (CurContext->Equals(DC: this))
122 return true;
123
124 return false;
125}
126
127bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches) const {
128 SmallVector<const CXXRecordDecl*, 8> Queue;
129
130 const CXXRecordDecl *Record = this;
131 while (true) {
132 for (const auto &I : Record->bases()) {
133 const RecordType *Ty = I.getType()->getAs<RecordType>();
134 if (!Ty)
135 return false;
136
137 CXXRecordDecl *Base =
138 cast_or_null<CXXRecordDecl>(Val: Ty->getDecl()->getDefinition());
139 if (!Base ||
140 (Base->isDependentContext() &&
141 !Base->isCurrentInstantiation(CurContext: Record))) {
142 return false;
143 }
144
145 Queue.push_back(Elt: Base);
146 if (!BaseMatches(Base))
147 return false;
148 }
149
150 if (Queue.empty())
151 break;
152 Record = Queue.pop_back_val(); // not actually a queue.
153 }
154
155 return true;
156}
157
158bool CXXBasePaths::lookupInBases(ASTContext &Context,
159 const CXXRecordDecl *Record,
160 CXXRecordDecl::BaseMatchesCallback BaseMatches,
161 bool LookupInDependent) {
162 bool FoundPath = false;
163
164 // The access of the path down to this record.
165 AccessSpecifier AccessToHere = ScratchPath.Access;
166 bool IsFirstStep = ScratchPath.empty();
167
168 for (const auto &BaseSpec : Record->bases()) {
169 // Find the record of the base class subobjects for this type.
170 QualType BaseType =
171 Context.getCanonicalType(T: 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 if (!LookupInDependent && BaseType->isDependentType())
180 continue;
181
182 // Determine whether we need to visit this base class at all,
183 // updating the count of subobjects appropriately.
184 IsVirtBaseAndNumberNonVirtBases &Subobjects = ClassSubobjects[BaseType];
185 bool VisitBase = true;
186 bool SetVirtual = false;
187 if (BaseSpec.isVirtual()) {
188 VisitBase = !Subobjects.IsVirtBase;
189 Subobjects.IsVirtBase = true;
190 if (isDetectingVirtual() && DetectedVirtual == nullptr) {
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 DetectedVirtual = BaseType->getAs<RecordType>();
194 SetVirtual = true;
195 }
196 } else {
197 ++Subobjects.NumberOfNonVirtBases;
198 }
199 if (isRecordingPaths()) {
200 // Add this base specifier to the current path.
201 CXXBasePathElement Element;
202 Element.Base = &BaseSpec;
203 Element.Class = Record;
204 if (BaseSpec.isVirtual())
205 Element.SubobjectNumber = 0;
206 else
207 Element.SubobjectNumber = Subobjects.NumberOfNonVirtBases;
208 ScratchPath.push_back(Elt: 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 if (IsFirstStep)
226 ScratchPath.Access = BaseSpec.getAccessSpecifier();
227 else
228 ScratchPath.Access = CXXRecordDecl::MergeAccess(PathAccess: AccessToHere,
229 DeclAccess: BaseSpec.getAccessSpecifier());
230 }
231
232 // Track whether there's a path involving this specific base.
233 bool FoundPathThroughBase = false;
234
235 if (BaseMatches(&BaseSpec, ScratchPath)) {
236 // We've found a path that terminates at this base.
237 FoundPath = FoundPathThroughBase = true;
238 if (isRecordingPaths()) {
239 // We have a path. Make a copy of it before moving on.
240 Paths.push_back(x: ScratchPath);
241 } else if (!isFindingAmbiguities()) {
242 // We found a path and we don't care about ambiguities;
243 // return immediately.
244 return FoundPath;
245 }
246 } else if (VisitBase) {
247 CXXRecordDecl *BaseRecord;
248 if (LookupInDependent) {
249 BaseRecord = nullptr;
250 const TemplateSpecializationType *TST =
251 BaseSpec.getType()->getAs<TemplateSpecializationType>();
252 if (!TST) {
253 if (auto *RT = BaseSpec.getType()->getAs<RecordType>())
254 BaseRecord = cast<CXXRecordDecl>(Val: RT->getDecl());
255 } else {
256 TemplateName TN = TST->getTemplateName();
257 if (auto *TD =
258 dyn_cast_or_null<ClassTemplateDecl>(Val: TN.getAsTemplateDecl()))
259 BaseRecord = TD->getTemplatedDecl();
260 }
261 if (BaseRecord) {
262 if (!BaseRecord->hasDefinition() ||
263 VisitedDependentRecords.count(Ptr: BaseRecord)) {
264 BaseRecord = nullptr;
265 } else {
266 VisitedDependentRecords.insert(Ptr: BaseRecord);
267 }
268 }
269 } else {
270 BaseRecord = cast<CXXRecordDecl>(
271 Val: BaseSpec.getType()->castAs<RecordType>()->getDecl());
272 }
273 if (BaseRecord &&
274 lookupInBases(Context, Record: BaseRecord, BaseMatches, LookupInDependent)) {
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 FoundPath = FoundPathThroughBase = true;
284 if (!isFindingAmbiguities())
285 return FoundPath;
286 }
287 }
288
289 // Pop this base specifier off the current path (if we're
290 // collecting paths).
291 if (isRecordingPaths()) {
292 ScratchPath.pop_back();
293 }
294
295 // If we set a virtual earlier, and this isn't a path, forget it again.
296 if (SetVirtual && !FoundPathThroughBase) {
297 DetectedVirtual = nullptr;
298 }
299 }
300
301 // Reset the scratch path access.
302 ScratchPath.Access = AccessToHere;
303
304 return FoundPath;
305}
306
307bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches,
308 CXXBasePaths &Paths,
309 bool LookupInDependent) const {
310 // If we didn't find anything, report that.
311 if (!Paths.lookupInBases(Context&: getASTContext(), Record: this, BaseMatches,
312 LookupInDependent))
313 return false;
314
315 // If we're not recording paths or we won't ever find ambiguities,
316 // we're done.
317 if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities())
318 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 Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) {
331 for (const CXXBasePathElement &PE : Path) {
332 if (!PE.Base->isVirtual())
333 continue;
334
335 CXXRecordDecl *VBase = nullptr;
336 if (const RecordType *Record = PE.Base->getType()->getAs<RecordType>())
337 VBase = cast<CXXRecordDecl>(Val: Record->getDecl());
338 if (!VBase)
339 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 for (const CXXBasePath &HidingP : Paths) {
346 CXXRecordDecl *HidingClass = nullptr;
347 if (const RecordType *Record =
348 HidingP.back().Base->getType()->getAs<RecordType>())
349 HidingClass = cast<CXXRecordDecl>(Val: Record->getDecl());
350 if (!HidingClass)
351 break;
352
353 if (HidingClass->isVirtuallyDerivedFrom(Base: VBase))
354 return true;
355 }
356 }
357 return false;
358 });
359
360 return true;
361}
362
363bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
364 CXXBasePath &Path,
365 const CXXRecordDecl *BaseRecord) {
366 assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
367 "User data for FindBaseClass is not canonical!");
368 return Specifier->getType()->castAs<RecordType>()->getDecl()
369 ->getCanonicalDecl() == BaseRecord;
370}
371
372bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier,
373 CXXBasePath &Path,
374 const CXXRecordDecl *BaseRecord) {
375 assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
376 "User data for FindBaseClass is not canonical!");
377 return Specifier->isVirtual() &&
378 Specifier->getType()->castAs<RecordType>()->getDecl()
379 ->getCanonicalDecl() == BaseRecord;
380}
381
382static bool isOrdinaryMember(const NamedDecl *ND) {
383 return ND->isInIdentifierNamespace(NS: Decl::IDNS_Ordinary | Decl::IDNS_Tag |
384 Decl::IDNS_Member);
385}
386
387static bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path,
388 DeclarationName Name) {
389 Path.Decls = RD->lookup(Name).begin();
390 for (DeclContext::lookup_iterator I = Path.Decls, E = I.end(); I != E; ++I)
391 if (isOrdinaryMember(ND: *I))
392 return true;
393
394 return false;
395}
396
397bool CXXRecordDecl::hasMemberName(DeclarationName Name) const {
398 CXXBasePath P;
399 if (findOrdinaryMember(RD: this, Path&: P, Name))
400 return true;
401
402 CXXBasePaths Paths(false, false, false);
403 return lookupInBases(
404 BaseMatches: [Name](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
405 return findOrdinaryMember(RD: Specifier->getType()->getAsCXXRecordDecl(),
406 Path, Name);
407 },
408 Paths);
409}
410
411static bool
412findOrdinaryMemberInDependentClasses(const CXXBaseSpecifier *Specifier,
413 CXXBasePath &Path, DeclarationName Name) {
414 const TemplateSpecializationType *TST =
415 Specifier->getType()->getAs<TemplateSpecializationType>();
416 if (!TST) {
417 auto *RT = Specifier->getType()->getAs<RecordType>();
418 if (!RT)
419 return false;
420 return findOrdinaryMember(RD: cast<CXXRecordDecl>(Val: RT->getDecl()), Path, Name);
421 }
422 TemplateName TN = TST->getTemplateName();
423 const auto *TD = dyn_cast_or_null<ClassTemplateDecl>(Val: TN.getAsTemplateDecl());
424 if (!TD)
425 return false;
426 CXXRecordDecl *RD = TD->getTemplatedDecl();
427 if (!RD)
428 return false;
429 return findOrdinaryMember(RD, Path, Name);
430}
431
432std::vector<const NamedDecl *> CXXRecordDecl::lookupDependentName(
433 DeclarationName Name,
434 llvm::function_ref<bool(const NamedDecl *ND)> Filter) {
435 std::vector<const NamedDecl *> Results;
436 // Lookup in the class.
437 bool AnyOrdinaryMembers = false;
438 for (const NamedDecl *ND : lookup(Name)) {
439 if (isOrdinaryMember(ND))
440 AnyOrdinaryMembers = true;
441 if (Filter(ND))
442 Results.push_back(x: ND);
443 }
444 if (AnyOrdinaryMembers)
445 return Results;
446
447 // Perform lookup into our base classes.
448 CXXBasePaths Paths;
449 Paths.setOrigin(this);
450 if (!lookupInBases(
451 BaseMatches: [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
452 return findOrdinaryMemberInDependentClasses(Specifier, Path, Name);
453 },
454 Paths, /*LookupInDependent=*/true))
455 return Results;
456 for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end();
457 I != E; ++I) {
458 if (isOrdinaryMember(ND: *I) && Filter(*I))
459 Results.push_back(x: *I);
460 }
461 return Results;
462}
463
464void OverridingMethods::add(unsigned OverriddenSubobject,
465 UniqueVirtualMethod Overriding) {
466 SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides
467 = Overrides[OverriddenSubobject];
468 if (!llvm::is_contained(Range&: SubobjectOverrides, Element: Overriding))
469 SubobjectOverrides.push_back(Elt: Overriding);
470}
471
472void OverridingMethods::add(const OverridingMethods &Other) {
473 for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I) {
474 for (overriding_const_iterator M = I->second.begin(),
475 MEnd = I->second.end();
476 M != MEnd;
477 ++M)
478 add(OverriddenSubobject: I->first, Overriding: *M);
479 }
480}
481
482void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) {
483 for (iterator I = begin(), IEnd = end(); I != IEnd; ++I) {
484 I->second.clear();
485 I->second.push_back(Elt: Overriding);
486 }
487}
488
489namespace {
490
491class 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
501public:
502 ~FinalOverriderCollector();
503
504 void Collect(const CXXRecordDecl *RD, bool VirtualBase,
505 const CXXRecordDecl *InVirtualSubobject,
506 CXXFinalOverriderMap &Overriders);
507};
508
509} // namespace
510
511void FinalOverriderCollector::Collect(const CXXRecordDecl *RD,
512 bool VirtualBase,
513 const CXXRecordDecl *InVirtualSubobject,
514 CXXFinalOverriderMap &Overriders) {
515 unsigned SubobjectNumber = 0;
516 if (!VirtualBase)
517 SubobjectNumber
518 = ++SubobjectCount[cast<CXXRecordDecl>(Val: RD->getCanonicalDecl())];
519
520 for (const auto &Base : RD->bases()) {
521 if (const RecordType *RT = Base.getType()->getAs<RecordType>()) {
522 const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(Val: RT->getDecl());
523 if (!BaseDecl->isPolymorphic())
524 continue;
525
526 if (Overriders.empty() && !Base.isVirtual()) {
527 // There are no other overriders of virtual member functions,
528 // so let the base class fill in our overriders for us.
529 Collect(RD: BaseDecl, VirtualBase: false, InVirtualSubobject, Overriders);
530 continue;
531 }
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 CXXFinalOverriderMap ComputedBaseOverriders;
539 CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders;
540 if (Base.isVirtual()) {
541 CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl];
542 BaseOverriders = MyVirtualOverriders;
543 if (!MyVirtualOverriders) {
544 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 BaseOverriders = MyVirtualOverriders;
550
551 Collect(RD: BaseDecl, VirtualBase: true, InVirtualSubobject: BaseDecl, Overriders&: *MyVirtualOverriders);
552 }
553 } else
554 Collect(RD: BaseDecl, VirtualBase: false, InVirtualSubobject, Overriders&: ComputedBaseOverriders);
555
556 // Merge the overriders from this base class into our own set of
557 // overriders.
558 for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(),
559 OMEnd = BaseOverriders->end();
560 OM != OMEnd;
561 ++OM) {
562 const CXXMethodDecl *CanonOM = OM->first->getCanonicalDecl();
563 Overriders[CanonOM].add(Other: OM->second);
564 }
565 }
566 }
567
568 for (auto *M : RD->methods()) {
569 // We only care about virtual methods.
570 if (!M->isVirtual())
571 continue;
572
573 CXXMethodDecl *CanonM = M->getCanonicalDecl();
574 using OverriddenMethodsRange =
575 llvm::iterator_range<CXXMethodDecl::method_iterator>;
576 OverriddenMethodsRange OverriddenMethods = CanonM->overridden_methods();
577
578 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 Overriders[CanonM].add(OverriddenSubobject: SubobjectNumber,
586 Overriding: UniqueVirtualMethod(CanonM, SubobjectNumber,
587 InVirtualSubobject));
588 continue;
589 }
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 SmallVector<OverriddenMethodsRange, 4> Stack(1, OverriddenMethods);
598 while (!Stack.empty()) {
599 for (const CXXMethodDecl *OM : Stack.pop_back_val()) {
600 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 Overriders[CanonOM].replaceAll(
612 Overriding: UniqueVirtualMethod(CanonM, SubobjectNumber,
613 InVirtualSubobject));
614
615 auto OverriddenMethods = CanonOM->overridden_methods();
616 if (OverriddenMethods.begin() == OverriddenMethods.end())
617 continue;
618
619 // Continue recursion to the methods that this virtual method
620 // overrides.
621 Stack.push_back(Elt: OverriddenMethods);
622 }
623 }
624
625 // C++ [class.virtual]p2:
626 // For convenience we say that any virtual function overrides itself.
627 Overriders[CanonM].add(OverriddenSubobject: SubobjectNumber,
628 Overriding: UniqueVirtualMethod(CanonM, SubobjectNumber,
629 InVirtualSubobject));
630 }
631}
632
633FinalOverriderCollector::~FinalOverriderCollector() {
634 for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator
635 VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end();
636 VO != VOEnd;
637 ++VO)
638 delete VO->second;
639}
640
641void
642CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const {
643 FinalOverriderCollector Collector;
644 Collector.Collect(RD: this, VirtualBase: false, InVirtualSubobject: nullptr, Overriders&: 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 for (auto &OM : FinalOverriders) {
650 for (auto &SO : OM.second) {
651 SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second;
652 if (Overriding.size() < 2)
653 continue;
654
655 auto IsHidden = [&Overriding](const UniqueVirtualMethod &M) {
656 if (!M.InVirtualSubobject)
657 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 for (const UniqueVirtualMethod &OP : Overriding)
665 if (&M != &OP &&
666 OP.Method->getParent()->isVirtuallyDerivedFrom(
667 Base: M.InVirtualSubobject))
668 return true;
669 return false;
670 };
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 llvm::erase_if(C&: Overriding, P: IsHidden);
675 }
676 }
677}
678
679static void
680AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context,
681 CXXIndirectPrimaryBaseSet& Bases) {
682 // If the record has a virtual primary base class, add it to our set.
683 const ASTRecordLayout &Layout = Context.getASTRecordLayout(D: RD);
684 if (Layout.isPrimaryBaseVirtual())
685 Bases.insert(Ptr: Layout.getPrimaryBase());
686
687 for (const auto &I : RD->bases()) {
688 assert(!I.getType()->isDependentType() &&
689 "Cannot get indirect primary bases for class with dependent bases.");
690
691 const CXXRecordDecl *BaseDecl =
692 cast<CXXRecordDecl>(Val: I.getType()->castAs<RecordType>()->getDecl());
693
694 // Only bases with virtual bases participate in computing the
695 // indirect primary virtual base classes.
696 if (BaseDecl->getNumVBases())
697 AddIndirectPrimaryBases(RD: BaseDecl, Context, Bases);
698 }
699
700}
701
702void
703CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const {
704 ASTContext &Context = getASTContext();
705
706 if (!getNumVBases())
707 return;
708
709 for (const auto &I : bases()) {
710 assert(!I.getType()->isDependentType() &&
711 "Cannot get indirect primary bases for class with dependent bases.");
712
713 const CXXRecordDecl *BaseDecl =
714 cast<CXXRecordDecl>(Val: I.getType()->castAs<RecordType>()->getDecl());
715
716 // Only bases with virtual bases participate in computing the
717 // indirect primary virtual base classes.
718 if (BaseDecl->getNumVBases())
719 AddIndirectPrimaryBases(RD: BaseDecl, Context, Bases);
720 }
721}
722