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/RecordLayout.h"
15 #include "clang/AST/DeclCXX.h"
19 using namespace clang;
21 /// \brief Computes the set of declarations referenced by these base
23 void CXXBasePaths::ComputeDeclsFound() {
24 assert(NumDeclsFound == 0 && !DeclsFound &&
25 "Already computed the set of declarations");
27 std::set<NamedDecl *> Decls;
28 for (CXXBasePaths::paths_iterator Path = begin(), PathEnd = end();
29 Path != PathEnd; ++Path)
30 Decls.insert(*Path->Decls.first);
32 NumDeclsFound = Decls.size();
33 DeclsFound = new NamedDecl * [NumDeclsFound];
34 std::copy(Decls.begin(), Decls.end(), DeclsFound);
37 CXXBasePaths::decl_iterator CXXBasePaths::found_decls_begin() {
38 if (NumDeclsFound == 0)
43 CXXBasePaths::decl_iterator CXXBasePaths::found_decls_end() {
44 if (NumDeclsFound == 0)
46 return DeclsFound + NumDeclsFound;
49 /// isAmbiguous - Determines whether the set of paths provided is
50 /// ambiguous, i.e., there are two or more paths that refer to
51 /// different base class subobjects of the same type. BaseType must be
52 /// an unqualified, canonical class type.
53 bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
54 BaseType = BaseType.getUnqualifiedType();
55 std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
56 return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
59 /// clear - Clear out all prior path information.
60 void CXXBasePaths::clear() {
62 ClassSubobjects.clear();
67 /// @brief Swaps the contents of this CXXBasePaths structure with the
68 /// contents of Other.
69 void CXXBasePaths::swap(CXXBasePaths &Other) {
70 std::swap(Origin, Other.Origin);
71 Paths.swap(Other.Paths);
72 ClassSubobjects.swap(Other.ClassSubobjects);
73 std::swap(FindAmbiguities, Other.FindAmbiguities);
74 std::swap(RecordPaths, Other.RecordPaths);
75 std::swap(DetectVirtual, Other.DetectVirtual);
76 std::swap(DetectedVirtual, Other.DetectedVirtual);
79 bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const {
80 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
81 /*DetectVirtual=*/false);
82 return isDerivedFrom(Base, Paths);
85 bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base,
86 CXXBasePaths &Paths) const {
87 if (getCanonicalDecl() == Base->getCanonicalDecl())
90 Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
91 return lookupInBases(&FindBaseClass,
92 const_cast<CXXRecordDecl*>(Base->getCanonicalDecl()),
96 bool CXXRecordDecl::isVirtuallyDerivedFrom(CXXRecordDecl *Base) const {
100 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
101 /*DetectVirtual=*/false);
103 if (getCanonicalDecl() == Base->getCanonicalDecl())
106 Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
107 return lookupInBases(&FindVirtualBaseClass, Base->getCanonicalDecl(), Paths);
110 static bool BaseIsNot(const CXXRecordDecl *Base, void *OpaqueTarget) {
111 // OpaqueTarget is a CXXRecordDecl*.
112 return Base->getCanonicalDecl() != (const CXXRecordDecl*) OpaqueTarget;
115 bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
116 return forallBases(BaseIsNot, (void*) Base->getCanonicalDecl());
119 bool CXXRecordDecl::forallBases(ForallBasesCallback *BaseMatches,
121 bool AllowShortCircuit) const {
122 SmallVector<const CXXRecordDecl*, 8> Queue;
124 const CXXRecordDecl *Record = this;
125 bool AllMatches = true;
127 for (CXXRecordDecl::base_class_const_iterator
128 I = Record->bases_begin(), E = Record->bases_end(); I != E; ++I) {
129 const RecordType *Ty = I->getType()->getAs<RecordType>();
131 if (AllowShortCircuit) return false;
136 CXXRecordDecl *Base =
137 cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition());
139 if (AllowShortCircuit) return false;
144 Queue.push_back(Base);
145 if (!BaseMatches(Base, OpaqueData)) {
146 if (AllowShortCircuit) return false;
152 if (Queue.empty()) break;
153 Record = Queue.back(); // not actually a queue.
160 bool CXXBasePaths::lookupInBases(ASTContext &Context,
161 const CXXRecordDecl *Record,
162 CXXRecordDecl::BaseMatchesCallback *BaseMatches,
164 bool FoundPath = false;
166 // The access of the path down to this record.
167 AccessSpecifier AccessToHere = ScratchPath.Access;
168 bool IsFirstStep = ScratchPath.empty();
170 for (CXXRecordDecl::base_class_const_iterator BaseSpec = Record->bases_begin(),
171 BaseSpecEnd = Record->bases_end();
172 BaseSpec != BaseSpecEnd;
174 // Find the record of the base class subobjects for this type.
175 QualType BaseType = Context.getCanonicalType(BaseSpec->getType())
176 .getUnqualifiedType();
179 // In the definition of a class template or a member of a class template,
180 // if a base class of the class template depends on a template-parameter,
181 // the base class scope is not examined during unqualified name lookup
182 // either at the point of definition of the class template or member or
183 // during an instantiation of the class tem- plate or member.
184 if (BaseType->isDependentType())
187 // Determine whether we need to visit this base class at all,
188 // updating the count of subobjects appropriately.
189 std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
190 bool VisitBase = true;
191 bool SetVirtual = false;
192 if (BaseSpec->isVirtual()) {
193 VisitBase = !Subobjects.first;
194 Subobjects.first = true;
195 if (isDetectingVirtual() && DetectedVirtual == 0) {
196 // If this is the first virtual we find, remember it. If it turns out
197 // there is no base path here, we'll reset it later.
198 DetectedVirtual = BaseType->getAs<RecordType>();
204 if (isRecordingPaths()) {
205 // Add this base specifier to the current path.
206 CXXBasePathElement Element;
207 Element.Base = &*BaseSpec;
208 Element.Class = Record;
209 if (BaseSpec->isVirtual())
210 Element.SubobjectNumber = 0;
212 Element.SubobjectNumber = Subobjects.second;
213 ScratchPath.push_back(Element);
215 // Calculate the "top-down" access to this base class.
216 // The spec actually describes this bottom-up, but top-down is
217 // equivalent because the definition works out as follows:
218 // 1. Write down the access along each step in the inheritance
219 // chain, followed by the access of the decl itself.
221 // class A { public: int foo; };
222 // class B : protected A {};
223 // class C : public B {};
224 // class D : private C {};
226 // private public protected public
227 // 2. If 'private' appears anywhere except far-left, access is denied.
228 // 3. Otherwise, overall access is determined by the most restrictive
229 // access in the sequence.
231 ScratchPath.Access = BaseSpec->getAccessSpecifier();
233 ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere,
234 BaseSpec->getAccessSpecifier());
237 // Track whether there's a path involving this specific base.
238 bool FoundPathThroughBase = false;
240 if (BaseMatches(BaseSpec, ScratchPath, UserData)) {
241 // We've found a path that terminates at this base.
242 FoundPath = FoundPathThroughBase = true;
243 if (isRecordingPaths()) {
244 // We have a path. Make a copy of it before moving on.
245 Paths.push_back(ScratchPath);
246 } else if (!isFindingAmbiguities()) {
247 // We found a path and we don't care about ambiguities;
248 // return immediately.
251 } else if (VisitBase) {
252 CXXRecordDecl *BaseRecord
253 = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>()
255 if (lookupInBases(Context, BaseRecord, BaseMatches, UserData)) {
256 // C++ [class.member.lookup]p2:
257 // A member name f in one sub-object B hides a member name f in
258 // a sub-object A if A is a base class sub-object of B. Any
259 // declarations that are so hidden are eliminated from
262 // There is a path to a base class that meets the criteria. If we're
263 // not collecting paths or finding ambiguities, we're done.
264 FoundPath = FoundPathThroughBase = true;
265 if (!isFindingAmbiguities())
270 // Pop this base specifier off the current path (if we're
271 // collecting paths).
272 if (isRecordingPaths()) {
273 ScratchPath.pop_back();
276 // If we set a virtual earlier, and this isn't a path, forget it again.
277 if (SetVirtual && !FoundPathThroughBase) {
282 // Reset the scratch path access.
283 ScratchPath.Access = AccessToHere;
288 bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches,
290 CXXBasePaths &Paths) const {
291 // If we didn't find anything, report that.
292 if (!Paths.lookupInBases(getASTContext(), this, BaseMatches, UserData))
295 // If we're not recording paths or we won't ever find ambiguities,
297 if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities())
300 // C++ [class.member.lookup]p6:
301 // When virtual base classes are used, a hidden declaration can be
302 // reached along a path through the sub-object lattice that does
303 // not pass through the hiding declaration. This is not an
304 // ambiguity. The identical use with nonvirtual base classes is an
305 // ambiguity; in that case there is no unique instance of the name
306 // that hides all the others.
308 // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy
309 // way to make it any faster.
310 for (CXXBasePaths::paths_iterator P = Paths.begin(), PEnd = Paths.end();
311 P != PEnd; /* increment in loop */) {
314 for (CXXBasePath::iterator PE = P->begin(), PEEnd = P->end();
315 PE != PEEnd && !Hidden; ++PE) {
316 if (PE->Base->isVirtual()) {
317 CXXRecordDecl *VBase = 0;
318 if (const RecordType *Record = PE->Base->getType()->getAs<RecordType>())
319 VBase = cast<CXXRecordDecl>(Record->getDecl());
323 // The declaration(s) we found along this path were found in a
324 // subobject of a virtual base. Check whether this virtual
325 // base is a subobject of any other path; if so, then the
326 // declaration in this path are hidden by that patch.
327 for (CXXBasePaths::paths_iterator HidingP = Paths.begin(),
328 HidingPEnd = Paths.end();
329 HidingP != HidingPEnd;
331 CXXRecordDecl *HidingClass = 0;
332 if (const RecordType *Record
333 = HidingP->back().Base->getType()->getAs<RecordType>())
334 HidingClass = cast<CXXRecordDecl>(Record->getDecl());
338 if (HidingClass->isVirtuallyDerivedFrom(VBase)) {
347 P = Paths.Paths.erase(P);
355 bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
358 assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord &&
359 "User data for FindBaseClass is not canonical!");
360 return Specifier->getType()->getAs<RecordType>()->getDecl()
361 ->getCanonicalDecl() == BaseRecord;
364 bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier,
367 assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord &&
368 "User data for FindBaseClass is not canonical!");
369 return Specifier->isVirtual() &&
370 Specifier->getType()->getAs<RecordType>()->getDecl()
371 ->getCanonicalDecl() == BaseRecord;
374 bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier,
377 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
379 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
380 for (Path.Decls = BaseRecord->lookup(N);
381 Path.Decls.first != Path.Decls.second;
382 ++Path.Decls.first) {
383 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
390 bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier,
393 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
395 const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member;
396 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
397 for (Path.Decls = BaseRecord->lookup(N);
398 Path.Decls.first != Path.Decls.second;
399 ++Path.Decls.first) {
400 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS))
408 FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier,
411 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
413 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
414 for (Path.Decls = BaseRecord->lookup(N);
415 Path.Decls.first != Path.Decls.second;
416 ++Path.Decls.first) {
417 // FIXME: Refactor the "is it a nested-name-specifier?" check
418 if (isa<TypedefNameDecl>(*Path.Decls.first) ||
419 (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
426 void OverridingMethods::add(unsigned OverriddenSubobject,
427 UniqueVirtualMethod Overriding) {
428 SmallVector<UniqueVirtualMethod, 4> &SubobjectOverrides
429 = Overrides[OverriddenSubobject];
430 if (std::find(SubobjectOverrides.begin(), SubobjectOverrides.end(),
431 Overriding) == SubobjectOverrides.end())
432 SubobjectOverrides.push_back(Overriding);
435 void OverridingMethods::add(const OverridingMethods &Other) {
436 for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I) {
437 for (overriding_const_iterator M = I->second.begin(),
438 MEnd = I->second.end();
445 void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) {
446 for (iterator I = begin(), IEnd = end(); I != IEnd; ++I) {
448 I->second.push_back(Overriding);
454 class FinalOverriderCollector {
455 /// \brief The number of subobjects of a given class type that
456 /// occur within the class hierarchy.
457 llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount;
459 /// \brief Overriders for each virtual base subobject.
460 llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders;
462 CXXFinalOverriderMap FinalOverriders;
465 ~FinalOverriderCollector();
467 void Collect(const CXXRecordDecl *RD, bool VirtualBase,
468 const CXXRecordDecl *InVirtualSubobject,
469 CXXFinalOverriderMap &Overriders);
473 void FinalOverriderCollector::Collect(const CXXRecordDecl *RD,
475 const CXXRecordDecl *InVirtualSubobject,
476 CXXFinalOverriderMap &Overriders) {
477 unsigned SubobjectNumber = 0;
480 = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())];
482 for (CXXRecordDecl::base_class_const_iterator Base = RD->bases_begin(),
483 BaseEnd = RD->bases_end(); Base != BaseEnd; ++Base) {
484 if (const RecordType *RT = Base->getType()->getAs<RecordType>()) {
485 const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl());
486 if (!BaseDecl->isPolymorphic())
489 if (Overriders.empty() && !Base->isVirtual()) {
490 // There are no other overriders of virtual member functions,
491 // so let the base class fill in our overriders for us.
492 Collect(BaseDecl, false, InVirtualSubobject, Overriders);
496 // Collect all of the overridders from the base class subobject
497 // and merge them into the set of overridders for this class.
498 // For virtual base classes, populate or use the cached virtual
499 // overrides so that we do not walk the virtual base class (and
500 // its base classes) more than once.
501 CXXFinalOverriderMap ComputedBaseOverriders;
502 CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders;
503 if (Base->isVirtual()) {
504 CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl];
505 if (!MyVirtualOverriders) {
506 MyVirtualOverriders = new CXXFinalOverriderMap;
507 Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders);
510 BaseOverriders = MyVirtualOverriders;
512 Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders);
514 // Merge the overriders from this base class into our own set of
516 for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(),
517 OMEnd = BaseOverriders->end();
520 const CXXMethodDecl *CanonOM
521 = cast<CXXMethodDecl>(OM->first->getCanonicalDecl());
522 Overriders[CanonOM].add(OM->second);
527 for (CXXRecordDecl::method_iterator M = RD->method_begin(),
528 MEnd = RD->method_end();
531 // We only care about virtual methods.
535 CXXMethodDecl *CanonM = cast<CXXMethodDecl>(M->getCanonicalDecl());
537 if (CanonM->begin_overridden_methods()
538 == CanonM->end_overridden_methods()) {
539 // This is a new virtual function that does not override any
540 // other virtual function. Add it to the map of virtual
541 // functions for which we are tracking overridders.
543 // C++ [class.virtual]p2:
544 // For convenience we say that any virtual function overrides itself.
545 Overriders[CanonM].add(SubobjectNumber,
546 UniqueVirtualMethod(CanonM, SubobjectNumber,
547 InVirtualSubobject));
551 // This virtual method overrides other virtual methods, so it does
552 // not add any new slots into the set of overriders. Instead, we
553 // replace entries in the set of overriders with the new
554 // overrider. To do so, we dig down to the original virtual
555 // functions using data recursion and update all of the methods it
557 typedef std::pair<CXXMethodDecl::method_iterator,
558 CXXMethodDecl::method_iterator> OverriddenMethods;
559 SmallVector<OverriddenMethods, 4> Stack;
560 Stack.push_back(std::make_pair(CanonM->begin_overridden_methods(),
561 CanonM->end_overridden_methods()));
562 while (!Stack.empty()) {
563 OverriddenMethods OverMethods = Stack.back();
566 for (; OverMethods.first != OverMethods.second; ++OverMethods.first) {
567 const CXXMethodDecl *CanonOM
568 = cast<CXXMethodDecl>((*OverMethods.first)->getCanonicalDecl());
570 // C++ [class.virtual]p2:
571 // A virtual member function C::vf of a class object S is
572 // a final overrider unless the most derived class (1.8)
573 // of which S is a base class subobject (if any) declares
574 // or inherits another member function that overrides vf.
576 // Treating this object like the most derived class, we
577 // replace any overrides from base classes with this
578 // overriding virtual function.
579 Overriders[CanonOM].replaceAll(
580 UniqueVirtualMethod(CanonM, SubobjectNumber,
581 InVirtualSubobject));
583 if (CanonOM->begin_overridden_methods()
584 == CanonOM->end_overridden_methods())
587 // Continue recursion to the methods that this virtual method
589 Stack.push_back(std::make_pair(CanonOM->begin_overridden_methods(),
590 CanonOM->end_overridden_methods()));
594 // C++ [class.virtual]p2:
595 // For convenience we say that any virtual function overrides itself.
596 Overriders[CanonM].add(SubobjectNumber,
597 UniqueVirtualMethod(CanonM, SubobjectNumber,
598 InVirtualSubobject));
602 FinalOverriderCollector::~FinalOverriderCollector() {
603 for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator
604 VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end();
611 CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const {
612 FinalOverriderCollector Collector;
613 Collector.Collect(this, false, 0, FinalOverriders);
615 // Weed out any final overriders that come from virtual base class
616 // subobjects that were hidden by other subobjects along any path.
617 // This is the final-overrider variant of C++ [class.member.lookup]p10.
618 for (CXXFinalOverriderMap::iterator OM = FinalOverriders.begin(),
619 OMEnd = FinalOverriders.end();
622 for (OverridingMethods::iterator SO = OM->second.begin(),
623 SOEnd = OM->second.end();
626 SmallVector<UniqueVirtualMethod, 4> &Overriding = SO->second;
627 if (Overriding.size() < 2)
630 for (SmallVector<UniqueVirtualMethod, 4>::iterator
631 Pos = Overriding.begin(), PosEnd = Overriding.end();
633 /* increment in loop */) {
634 if (!Pos->InVirtualSubobject) {
639 // We have an overriding method in a virtual base class
640 // subobject (or non-virtual base class subobject thereof);
641 // determine whether there exists an other overriding method
642 // in a base class subobject that hides the virtual base class
645 for (SmallVector<UniqueVirtualMethod, 4>::iterator
646 OP = Overriding.begin(), OPEnd = Overriding.end();
647 OP != OPEnd && !Hidden;
652 if (OP->Method->getParent()->isVirtuallyDerivedFrom(
653 const_cast<CXXRecordDecl *>(Pos->InVirtualSubobject)))
658 // The current overriding function is hidden by another
659 // overriding function; remove this one.
660 Pos = Overriding.erase(Pos);
661 PosEnd = Overriding.end();
671 AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context,
672 CXXIndirectPrimaryBaseSet& Bases) {
673 // If the record has a virtual primary base class, add it to our set.
674 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
675 if (Layout.isPrimaryBaseVirtual())
676 Bases.insert(Layout.getPrimaryBase());
678 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
679 E = RD->bases_end(); I != E; ++I) {
680 assert(!I->getType()->isDependentType() &&
681 "Cannot get indirect primary bases for class with dependent bases.");
683 const CXXRecordDecl *BaseDecl =
684 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
686 // Only bases with virtual bases participate in computing the
687 // indirect primary virtual base classes.
688 if (BaseDecl->getNumVBases())
689 AddIndirectPrimaryBases(BaseDecl, Context, Bases);
695 CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const {
696 ASTContext &Context = getASTContext();
701 for (CXXRecordDecl::base_class_const_iterator I = bases_begin(),
702 E = bases_end(); I != E; ++I) {
703 assert(!I->getType()->isDependentType() &&
704 "Cannot get indirect primary bases for class with dependent bases.");
706 const CXXRecordDecl *BaseDecl =
707 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
709 // Only bases with virtual bases participate in computing the
710 // indirect primary virtual base classes.
711 if (BaseDecl->getNumVBases())
712 AddIndirectPrimaryBases(BaseDecl, Context, Bases);