1 //===------ CXXInheritance.cpp - C++ Inheritance ----------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provides routines that help analyzing C++ inheritance hierarchies.
12 //===----------------------------------------------------------------------===//
13 #include "clang/AST/CXXInheritance.h"
14 #include "clang/AST/ASTContext.h"
15 #include "clang/AST/DeclCXX.h"
16 #include "clang/AST/RecordLayout.h"
17 #include "llvm/ADT/SetVector.h"
20 using namespace clang;
22 /// \brief Computes the set of declarations referenced by these base
24 void CXXBasePaths::ComputeDeclsFound() {
25 assert(NumDeclsFound == 0 && !DeclsFound &&
26 "Already computed the set of declarations");
28 llvm::SetVector<NamedDecl *, SmallVector<NamedDecl *, 8> > Decls;
29 for (paths_iterator Path = begin(), PathEnd = end(); Path != PathEnd; ++Path)
30 Decls.insert(Path->Decls.front());
32 NumDeclsFound = Decls.size();
33 DeclsFound = llvm::make_unique<NamedDecl *[]>(NumDeclsFound);
34 std::copy(Decls.begin(), Decls.end(), DeclsFound.get());
37 CXXBasePaths::decl_range CXXBasePaths::found_decls() {
38 if (NumDeclsFound == 0)
41 return decl_range(decl_iterator(DeclsFound.get()),
42 decl_iterator(DeclsFound.get() + NumDeclsFound));
45 /// isAmbiguous - Determines whether the set of paths provided is
46 /// ambiguous, i.e., there are two or more paths that refer to
47 /// different base class subobjects of the same type. BaseType must be
48 /// an unqualified, canonical class type.
49 bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
50 BaseType = BaseType.getUnqualifiedType();
51 std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
52 return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
55 /// clear - Clear out all prior path information.
56 void CXXBasePaths::clear() {
58 ClassSubobjects.clear();
60 DetectedVirtual = nullptr;
63 /// @brief Swaps the contents of this CXXBasePaths structure with the
64 /// contents of Other.
65 void CXXBasePaths::swap(CXXBasePaths &Other) {
66 std::swap(Origin, Other.Origin);
67 Paths.swap(Other.Paths);
68 ClassSubobjects.swap(Other.ClassSubobjects);
69 std::swap(FindAmbiguities, Other.FindAmbiguities);
70 std::swap(RecordPaths, Other.RecordPaths);
71 std::swap(DetectVirtual, Other.DetectVirtual);
72 std::swap(DetectedVirtual, Other.DetectedVirtual);
75 bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const {
76 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
77 /*DetectVirtual=*/false);
78 return isDerivedFrom(Base, Paths);
81 bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base,
82 CXXBasePaths &Paths) const {
83 if (getCanonicalDecl() == Base->getCanonicalDecl())
86 Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
88 const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
89 // FIXME: Capturing 'this' is a workaround for name lookup bugs in GCC 4.7.
91 [this, BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
92 return FindBaseClass(Specifier, Path, BaseDecl);
97 bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const {
101 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
102 /*DetectVirtual=*/false);
104 if (getCanonicalDecl() == Base->getCanonicalDecl())
107 Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
109 const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
110 // FIXME: Capturing 'this' is a workaround for name lookup bugs in GCC 4.7.
111 return lookupInBases(
112 [this, BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
113 return FindVirtualBaseClass(Specifier, Path, BaseDecl);
118 bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
119 const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl();
120 return forallBases([TargetDecl](const CXXRecordDecl *Base) {
121 return Base->getCanonicalDecl() != TargetDecl;
126 CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const {
127 assert(isDependentContext());
129 for (; !CurContext->isFileContext(); CurContext = CurContext->getParent())
130 if (CurContext->Equals(this))
136 bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches,
137 bool AllowShortCircuit) const {
138 SmallVector<const CXXRecordDecl*, 8> Queue;
140 const CXXRecordDecl *Record = this;
141 bool AllMatches = true;
143 for (const auto &I : Record->bases()) {
144 const RecordType *Ty = I.getType()->getAs<RecordType>();
146 if (AllowShortCircuit) return false;
151 CXXRecordDecl *Base =
152 cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition());
154 (Base->isDependentContext() &&
155 !Base->isCurrentInstantiation(Record))) {
156 if (AllowShortCircuit) return false;
161 Queue.push_back(Base);
162 if (!BaseMatches(Base)) {
163 if (AllowShortCircuit) return false;
171 Record = Queue.pop_back_val(); // not actually a queue.
177 bool CXXBasePaths::lookupInBases(
178 ASTContext &Context, const CXXRecordDecl *Record,
179 CXXRecordDecl::BaseMatchesCallback BaseMatches) {
180 bool FoundPath = false;
182 // The access of the path down to this record.
183 AccessSpecifier AccessToHere = ScratchPath.Access;
184 bool IsFirstStep = ScratchPath.empty();
186 for (const auto &BaseSpec : Record->bases()) {
187 // Find the record of the base class subobjects for this type.
189 Context.getCanonicalType(BaseSpec.getType()).getUnqualifiedType();
192 // In the definition of a class template or a member of a class template,
193 // if a base class of the class template depends on a template-parameter,
194 // the base class scope is not examined during unqualified name lookup
195 // either at the point of definition of the class template or member or
196 // during an instantiation of the class tem- plate or member.
197 if (BaseType->isDependentType())
200 // Determine whether we need to visit this base class at all,
201 // updating the count of subobjects appropriately.
202 std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
203 bool VisitBase = true;
204 bool SetVirtual = false;
205 if (BaseSpec.isVirtual()) {
206 VisitBase = !Subobjects.first;
207 Subobjects.first = true;
208 if (isDetectingVirtual() && DetectedVirtual == nullptr) {
209 // If this is the first virtual we find, remember it. If it turns out
210 // there is no base path here, we'll reset it later.
211 DetectedVirtual = BaseType->getAs<RecordType>();
217 if (isRecordingPaths()) {
218 // Add this base specifier to the current path.
219 CXXBasePathElement Element;
220 Element.Base = &BaseSpec;
221 Element.Class = Record;
222 if (BaseSpec.isVirtual())
223 Element.SubobjectNumber = 0;
225 Element.SubobjectNumber = Subobjects.second;
226 ScratchPath.push_back(Element);
228 // Calculate the "top-down" access to this base class.
229 // The spec actually describes this bottom-up, but top-down is
230 // equivalent because the definition works out as follows:
231 // 1. Write down the access along each step in the inheritance
232 // chain, followed by the access of the decl itself.
234 // class A { public: int foo; };
235 // class B : protected A {};
236 // class C : public B {};
237 // class D : private C {};
239 // private public protected public
240 // 2. If 'private' appears anywhere except far-left, access is denied.
241 // 3. Otherwise, overall access is determined by the most restrictive
242 // access in the sequence.
244 ScratchPath.Access = BaseSpec.getAccessSpecifier();
246 ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere,
247 BaseSpec.getAccessSpecifier());
250 // Track whether there's a path involving this specific base.
251 bool FoundPathThroughBase = false;
253 if (BaseMatches(&BaseSpec, ScratchPath)) {
254 // We've found a path that terminates at this base.
255 FoundPath = FoundPathThroughBase = true;
256 if (isRecordingPaths()) {
257 // We have a path. Make a copy of it before moving on.
258 Paths.push_back(ScratchPath);
259 } else if (!isFindingAmbiguities()) {
260 // We found a path and we don't care about ambiguities;
261 // return immediately.
264 } else if (VisitBase) {
265 CXXRecordDecl *BaseRecord
266 = cast<CXXRecordDecl>(BaseSpec.getType()->castAs<RecordType>()
268 if (lookupInBases(Context, BaseRecord, BaseMatches)) {
269 // C++ [class.member.lookup]p2:
270 // A member name f in one sub-object B hides a member name f in
271 // a sub-object A if A is a base class sub-object of B. Any
272 // declarations that are so hidden are eliminated from
275 // There is a path to a base class that meets the criteria. If we're
276 // not collecting paths or finding ambiguities, we're done.
277 FoundPath = FoundPathThroughBase = true;
278 if (!isFindingAmbiguities())
283 // Pop this base specifier off the current path (if we're
284 // collecting paths).
285 if (isRecordingPaths()) {
286 ScratchPath.pop_back();
289 // If we set a virtual earlier, and this isn't a path, forget it again.
290 if (SetVirtual && !FoundPathThroughBase) {
291 DetectedVirtual = nullptr;
295 // Reset the scratch path access.
296 ScratchPath.Access = AccessToHere;
301 bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches,
302 CXXBasePaths &Paths) const {
303 // If we didn't find anything, report that.
304 if (!Paths.lookupInBases(getASTContext(), this, BaseMatches))
307 // If we're not recording paths or we won't ever find ambiguities,
309 if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities())
312 // C++ [class.member.lookup]p6:
313 // When virtual base classes are used, a hidden declaration can be
314 // reached along a path through the sub-object lattice that does
315 // not pass through the hiding declaration. This is not an
316 // ambiguity. The identical use with nonvirtual base classes is an
317 // ambiguity; in that case there is no unique instance of the name
318 // that hides all the others.
320 // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy
321 // way to make it any faster.
322 Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) {
323 for (const CXXBasePathElement &PE : Path) {
324 if (!PE.Base->isVirtual())
327 CXXRecordDecl *VBase = nullptr;
328 if (const RecordType *Record = PE.Base->getType()->getAs<RecordType>())
329 VBase = cast<CXXRecordDecl>(Record->getDecl());
333 // The declaration(s) we found along this path were found in a
334 // subobject of a virtual base. Check whether this virtual
335 // base is a subobject of any other path; if so, then the
336 // declaration in this path are hidden by that patch.
337 for (const CXXBasePath &HidingP : Paths) {
338 CXXRecordDecl *HidingClass = nullptr;
339 if (const RecordType *Record =
340 HidingP.back().Base->getType()->getAs<RecordType>())
341 HidingClass = cast<CXXRecordDecl>(Record->getDecl());
345 if (HidingClass->isVirtuallyDerivedFrom(VBase))
355 bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
357 const CXXRecordDecl *BaseRecord) {
358 assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
359 "User data for FindBaseClass is not canonical!");
360 return Specifier->getType()->castAs<RecordType>()->getDecl()
361 ->getCanonicalDecl() == BaseRecord;
364 bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier,
366 const CXXRecordDecl *BaseRecord) {
367 assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
368 "User data for FindBaseClass is not canonical!");
369 return Specifier->isVirtual() &&
370 Specifier->getType()->castAs<RecordType>()->getDecl()
371 ->getCanonicalDecl() == BaseRecord;
374 bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier,
376 DeclarationName Name) {
377 RecordDecl *BaseRecord =
378 Specifier->getType()->castAs<RecordType>()->getDecl();
380 for (Path.Decls = BaseRecord->lookup(Name);
382 Path.Decls = Path.Decls.slice(1)) {
383 if (Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag))
390 bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier,
392 DeclarationName Name) {
393 RecordDecl *BaseRecord =
394 Specifier->getType()->castAs<RecordType>()->getDecl();
396 const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member;
397 for (Path.Decls = BaseRecord->lookup(Name);
399 Path.Decls = Path.Decls.slice(1)) {
400 if (Path.Decls.front()->isInIdentifierNamespace(IDNS))
407 bool CXXRecordDecl::FindOMPReductionMember(const CXXBaseSpecifier *Specifier,
409 DeclarationName Name) {
410 RecordDecl *BaseRecord =
411 Specifier->getType()->castAs<RecordType>()->getDecl();
413 for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty();
414 Path.Decls = Path.Decls.slice(1)) {
415 if (Path.Decls.front()->isInIdentifierNamespace(IDNS_OMPReduction))
423 FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier,
425 DeclarationName Name) {
426 RecordDecl *BaseRecord =
427 Specifier->getType()->castAs<RecordType>()->getDecl();
429 for (Path.Decls = BaseRecord->lookup(Name);
431 Path.Decls = Path.Decls.slice(1)) {
432 // FIXME: Refactor the "is it a nested-name-specifier?" check
433 if (isa<TypedefNameDecl>(Path.Decls.front()) ||
434 Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag))
441 void OverridingMethods::add(unsigned OverriddenSubobject,
442 UniqueVirtualMethod Overriding) {
443 SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides
444 = Overrides[OverriddenSubobject];
445 if (std::find(SubobjectOverrides.begin(), SubobjectOverrides.end(),
446 Overriding) == SubobjectOverrides.end())
447 SubobjectOverrides.push_back(Overriding);
450 void OverridingMethods::add(const OverridingMethods &Other) {
451 for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I) {
452 for (overriding_const_iterator M = I->second.begin(),
453 MEnd = I->second.end();
460 void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) {
461 for (iterator I = begin(), IEnd = end(); I != IEnd; ++I) {
463 I->second.push_back(Overriding);
469 class FinalOverriderCollector {
470 /// \brief The number of subobjects of a given class type that
471 /// occur within the class hierarchy.
472 llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount;
474 /// \brief Overriders for each virtual base subobject.
475 llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders;
477 CXXFinalOverriderMap FinalOverriders;
480 ~FinalOverriderCollector();
482 void Collect(const CXXRecordDecl *RD, bool VirtualBase,
483 const CXXRecordDecl *InVirtualSubobject,
484 CXXFinalOverriderMap &Overriders);
488 void FinalOverriderCollector::Collect(const CXXRecordDecl *RD,
490 const CXXRecordDecl *InVirtualSubobject,
491 CXXFinalOverriderMap &Overriders) {
492 unsigned SubobjectNumber = 0;
495 = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())];
497 for (const auto &Base : RD->bases()) {
498 if (const RecordType *RT = Base.getType()->getAs<RecordType>()) {
499 const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl());
500 if (!BaseDecl->isPolymorphic())
503 if (Overriders.empty() && !Base.isVirtual()) {
504 // There are no other overriders of virtual member functions,
505 // so let the base class fill in our overriders for us.
506 Collect(BaseDecl, false, InVirtualSubobject, Overriders);
510 // Collect all of the overridders from the base class subobject
511 // and merge them into the set of overridders for this class.
512 // For virtual base classes, populate or use the cached virtual
513 // overrides so that we do not walk the virtual base class (and
514 // its base classes) more than once.
515 CXXFinalOverriderMap ComputedBaseOverriders;
516 CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders;
517 if (Base.isVirtual()) {
518 CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl];
519 BaseOverriders = MyVirtualOverriders;
520 if (!MyVirtualOverriders) {
521 MyVirtualOverriders = new CXXFinalOverriderMap;
523 // Collect may cause VirtualOverriders to reallocate, invalidating the
524 // MyVirtualOverriders reference. Set BaseOverriders to the right
526 BaseOverriders = MyVirtualOverriders;
528 Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders);
531 Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders);
533 // Merge the overriders from this base class into our own set of
535 for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(),
536 OMEnd = BaseOverriders->end();
539 const CXXMethodDecl *CanonOM
540 = cast<CXXMethodDecl>(OM->first->getCanonicalDecl());
541 Overriders[CanonOM].add(OM->second);
546 for (auto *M : RD->methods()) {
547 // We only care about virtual methods.
551 CXXMethodDecl *CanonM = cast<CXXMethodDecl>(M->getCanonicalDecl());
553 if (CanonM->begin_overridden_methods()
554 == CanonM->end_overridden_methods()) {
555 // This is a new virtual function that does not override any
556 // other virtual function. Add it to the map of virtual
557 // functions for which we are tracking overridders.
559 // C++ [class.virtual]p2:
560 // For convenience we say that any virtual function overrides itself.
561 Overriders[CanonM].add(SubobjectNumber,
562 UniqueVirtualMethod(CanonM, SubobjectNumber,
563 InVirtualSubobject));
567 // This virtual method overrides other virtual methods, so it does
568 // not add any new slots into the set of overriders. Instead, we
569 // replace entries in the set of overriders with the new
570 // overrider. To do so, we dig down to the original virtual
571 // functions using data recursion and update all of the methods it
573 typedef llvm::iterator_range<CXXMethodDecl::method_iterator>
575 SmallVector<OverriddenMethods, 4> Stack;
576 Stack.push_back(llvm::make_range(CanonM->begin_overridden_methods(),
577 CanonM->end_overridden_methods()));
578 while (!Stack.empty()) {
579 for (const CXXMethodDecl *OM : Stack.pop_back_val()) {
580 const CXXMethodDecl *CanonOM = OM->getCanonicalDecl();
582 // C++ [class.virtual]p2:
583 // A virtual member function C::vf of a class object S is
584 // a final overrider unless the most derived class (1.8)
585 // of which S is a base class subobject (if any) declares
586 // or inherits another member function that overrides vf.
588 // Treating this object like the most derived class, we
589 // replace any overrides from base classes with this
590 // overriding virtual function.
591 Overriders[CanonOM].replaceAll(
592 UniqueVirtualMethod(CanonM, SubobjectNumber,
593 InVirtualSubobject));
595 if (CanonOM->begin_overridden_methods()
596 == CanonOM->end_overridden_methods())
599 // Continue recursion to the methods that this virtual method
601 Stack.push_back(llvm::make_range(CanonOM->begin_overridden_methods(),
602 CanonOM->end_overridden_methods()));
606 // C++ [class.virtual]p2:
607 // For convenience we say that any virtual function overrides itself.
608 Overriders[CanonM].add(SubobjectNumber,
609 UniqueVirtualMethod(CanonM, SubobjectNumber,
610 InVirtualSubobject));
614 FinalOverriderCollector::~FinalOverriderCollector() {
615 for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator
616 VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end();
623 CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const {
624 FinalOverriderCollector Collector;
625 Collector.Collect(this, false, nullptr, FinalOverriders);
627 // Weed out any final overriders that come from virtual base class
628 // subobjects that were hidden by other subobjects along any path.
629 // This is the final-overrider variant of C++ [class.member.lookup]p10.
630 for (auto &OM : FinalOverriders) {
631 for (auto &SO : OM.second) {
632 SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second;
633 if (Overriding.size() < 2)
636 auto IsHidden = [&Overriding](const UniqueVirtualMethod &M) {
637 if (!M.InVirtualSubobject)
640 // We have an overriding method in a virtual base class
641 // subobject (or non-virtual base class subobject thereof);
642 // determine whether there exists an other overriding method
643 // in a base class subobject that hides the virtual base class
645 for (const UniqueVirtualMethod &OP : Overriding)
647 OP.Method->getParent()->isVirtuallyDerivedFrom(
648 M.InVirtualSubobject))
654 std::remove_if(Overriding.begin(), Overriding.end(), IsHidden),
661 AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context,
662 CXXIndirectPrimaryBaseSet& Bases) {
663 // If the record has a virtual primary base class, add it to our set.
664 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
665 if (Layout.isPrimaryBaseVirtual())
666 Bases.insert(Layout.getPrimaryBase());
668 for (const auto &I : RD->bases()) {
669 assert(!I.getType()->isDependentType() &&
670 "Cannot get indirect primary bases for class with dependent bases.");
672 const CXXRecordDecl *BaseDecl =
673 cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
675 // Only bases with virtual bases participate in computing the
676 // indirect primary virtual base classes.
677 if (BaseDecl->getNumVBases())
678 AddIndirectPrimaryBases(BaseDecl, Context, Bases);
684 CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const {
685 ASTContext &Context = getASTContext();
690 for (const auto &I : bases()) {
691 assert(!I.getType()->isDependentType() &&
692 "Cannot get indirect primary bases for class with dependent bases.");
694 const CXXRecordDecl *BaseDecl =
695 cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
697 // Only bases with virtual bases participate in computing the
698 // indirect primary virtual base classes.
699 if (BaseDecl->getNumVBases())
700 AddIndirectPrimaryBases(BaseDecl, Context, Bases);