CXXInheritance.cpp revision 204643
151078Speter//===------ CXXInheritance.cpp - C++ Inheritance ----------------*- C++ -*-===// 251078Speter// 351078Speter// The LLVM Compiler Infrastructure 451078Speter// 551078Speter// This file is distributed under the University of Illinois Open Source 651078Speter// License. See LICENSE.TXT for details. 751078Speter// 851078Speter//===----------------------------------------------------------------------===// 951078Speter// 1051078Speter// This file provides routines that help analyzing C++ inheritance hierarchies. 1151078Speter// 1251078Speter//===----------------------------------------------------------------------===// 1351078Speter#include "clang/AST/CXXInheritance.h" 1451078Speter#include "clang/AST/DeclCXX.h" 1551078Speter#include <algorithm> 1651078Speter#include <set> 1751078Speter 1851078Speterusing namespace clang; 1951078Speter 2051078Speter/// \brief Computes the set of declarations referenced by these base 2151078Speter/// paths. 2251078Spetervoid CXXBasePaths::ComputeDeclsFound() { 2351078Speter assert(NumDeclsFound == 0 && !DeclsFound && 2451078Speter "Already computed the set of declarations"); 2551078Speter 2651078Speter std::set<NamedDecl *> Decls; 2751078Speter for (CXXBasePaths::paths_iterator Path = begin(), PathEnd = end(); 2851078Speter Path != PathEnd; ++Path) 2951078Speter Decls.insert(*Path->Decls.first); 3051078Speter 3151078Speter NumDeclsFound = Decls.size(); 3251078Speter DeclsFound = new NamedDecl * [NumDeclsFound]; 3351078Speter std::copy(Decls.begin(), Decls.end(), DeclsFound); 3451078Speter} 3551078Speter 3651078SpeterCXXBasePaths::decl_iterator CXXBasePaths::found_decls_begin() { 3751078Speter if (NumDeclsFound == 0) 3851078Speter ComputeDeclsFound(); 3951078Speter return DeclsFound; 4051078Speter} 4151078Speter 4251078SpeterCXXBasePaths::decl_iterator CXXBasePaths::found_decls_end() { 4351078Speter if (NumDeclsFound == 0) 4451078Speter ComputeDeclsFound(); 4551078Speter return DeclsFound + NumDeclsFound; 4651078Speter} 4751078Speter 4851078Speter/// isAmbiguous - Determines whether the set of paths provided is 4951078Speter/// ambiguous, i.e., there are two or more paths that refer to 5051078Speter/// different base class subobjects of the same type. BaseType must be 5151078Speter/// an unqualified, canonical class type. 5251078Speterbool CXXBasePaths::isAmbiguous(QualType BaseType) { 5376166Smarkm assert(BaseType.isCanonical() && "Base type must be the canonical type"); 5465822Sjhb assert(BaseType.hasQualifiers() == 0 && "Base type must be unqualified"); 5551078Speter std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType]; 5651078Speter return Subobjects.second + (Subobjects.first? 1 : 0) > 1; 5751078Speter} 5851078Speter 5951078Speter/// clear - Clear out all prior path information. 6076166Smarkmvoid CXXBasePaths::clear() { 6176166Smarkm Paths.clear(); 6276166Smarkm ClassSubobjects.clear(); 6376166Smarkm ScratchPath.clear(); 6476166Smarkm DetectedVirtual = 0; 6576166Smarkm} 6676166Smarkm 6751078Speter/// @brief Swaps the contents of this CXXBasePaths structure with the 6876166Smarkm/// contents of Other. 6960471Snyanvoid CXXBasePaths::swap(CXXBasePaths &Other) { 7051078Speter std::swap(Origin, Other.Origin); 7151078Speter Paths.swap(Other.Paths); 7258377Sphk ClassSubobjects.swap(Other.ClassSubobjects); 7351078Speter std::swap(FindAmbiguities, Other.FindAmbiguities); 7451078Speter std::swap(RecordPaths, Other.RecordPaths); 7586909Simp std::swap(DetectVirtual, Other.DetectVirtual); 7686909Simp std::swap(DetectedVirtual, Other.DetectedVirtual); 7751078Speter} 7851078Speter 7985302Simpbool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base) const { 8085365Simp CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, 8151078Speter /*DetectVirtual=*/false); 8251078Speter return isDerivedFrom(Base, Paths); 8377726Sjoerg} 8451078Speter 8577726Sjoergbool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base, CXXBasePaths &Paths) const { 8651078Speter if (getCanonicalDecl() == Base->getCanonicalDecl()) 8751078Speter return false; 8851078Speter 8951078Speter Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); 9051078Speter return lookupInBases(&FindBaseClass, Base->getCanonicalDecl(), Paths); 9151078Speter} 9251078Speter 9351078Speterbool CXXRecordDecl::isVirtuallyDerivedFrom(CXXRecordDecl *Base) const { 9451078Speter CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, 9551078Speter /*DetectVirtual=*/false); 9651078Speter 9751078Speter if (getCanonicalDecl() == Base->getCanonicalDecl()) 9851078Speter return false; 9951078Speter 10051078Speter Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); 10151078Speter return lookupInBases(&FindVirtualBaseClass, Base->getCanonicalDecl(), Paths); 10251078Speter} 10351078Speter 10451078Speterstatic bool BaseIsNot(const CXXRecordDecl *Base, void *OpaqueTarget) { 10551078Speter // OpaqueTarget is a CXXRecordDecl*. 10651078Speter return Base->getCanonicalDecl() != (const CXXRecordDecl*) OpaqueTarget; 10751078Speter} 10851078Speter 10951078Speterbool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const { 11051078Speter return forallBases(BaseIsNot, (void*) Base->getCanonicalDecl()); 11151078Speter} 11251078Speter 11386909Simpbool CXXRecordDecl::forallBases(ForallBasesCallback *BaseMatches, 11486909Simp void *OpaqueData, 11551078Speter bool AllowShortCircuit) const { 11651078Speter llvm::SmallVector<const CXXRecordDecl*, 8> Queue; 11751078Speter 11851078Speter const CXXRecordDecl *Record = this; 11951078Speter bool AllMatches = true; 12051078Speter while (true) { 12160471Snyan for (CXXRecordDecl::base_class_const_iterator 12260471Snyan I = Record->bases_begin(), E = Record->bases_end(); I != E; ++I) { 12360471Snyan const RecordType *Ty = I->getType()->getAs<RecordType>(); 12460471Snyan if (!Ty) { 12560471Snyan if (AllowShortCircuit) return false; 12651078Speter AllMatches = false; 12751078Speter continue; 12851078Speter } 12951078Speter 13051078Speter CXXRecordDecl *Base = 13151078Speter cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition()); 13251078Speter if (!Base) { 13351078Speter if (AllowShortCircuit) return false; 13453344Speter AllMatches = false; 13551078Speter continue; 13651078Speter } 13751078Speter 13851078Speter Queue.push_back(Base); 13951078Speter if (!BaseMatches(Base, OpaqueData)) { 14051078Speter if (AllowShortCircuit) return false; 14151078Speter AllMatches = false; 14251078Speter continue; 14351078Speter } 14451078Speter } 14551078Speter 14651078Speter if (Queue.empty()) break; 14751078Speter Record = Queue.back(); // not actually a queue. 14851078Speter Queue.pop_back(); 14951078Speter } 15051078Speter 15151078Speter return AllMatches; 15251078Speter} 15351078Speter 15451078Speterbool CXXBasePaths::lookupInBases(ASTContext &Context, 15551078Speter const CXXRecordDecl *Record, 15651078Speter CXXRecordDecl::BaseMatchesCallback *BaseMatches, 15751078Speter void *UserData) { 15851078Speter bool FoundPath = false; 15951078Speter 16051078Speter // The access of the path down to this record. 16186909Simp AccessSpecifier AccessToHere = ScratchPath.Access; 16251078Speter bool IsFirstStep = ScratchPath.empty(); 16351078Speter 16486909Simp for (CXXRecordDecl::base_class_const_iterator BaseSpec = Record->bases_begin(), 16586909Simp BaseSpecEnd = Record->bases_end(); 16686909Simp BaseSpec != BaseSpecEnd; 16786909Simp ++BaseSpec) { 16886909Simp // Find the record of the base class subobjects for this type. 16986909Simp QualType BaseType = Context.getCanonicalType(BaseSpec->getType()) 17086909Simp .getUnqualifiedType(); 17186909Simp 17286909Simp // C++ [temp.dep]p3: 17386909Simp // In the definition of a class template or a member of a class template, 17486909Simp // if a base class of the class template depends on a template-parameter, 17586909Simp // the base class scope is not examined during unqualified name lookup 17686909Simp // either at the point of definition of the class template or member or 17786909Simp // during an instantiation of the class tem- plate or member. 17886909Simp if (BaseType->isDependentType()) 17986909Simp continue; 18086909Simp 18186909Simp // Determine whether we need to visit this base class at all, 18251078Speter // updating the count of subobjects appropriately. 18386909Simp std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType]; 18486909Simp bool VisitBase = true; 18586909Simp bool SetVirtual = false; 18686909Simp if (BaseSpec->isVirtual()) { 18786909Simp VisitBase = !Subobjects.first; 18886909Simp Subobjects.first = true; 18986909Simp if (isDetectingVirtual() && DetectedVirtual == 0) { 19086909Simp // If this is the first virtual we find, remember it. If it turns out 19186909Simp // there is no base path here, we'll reset it later. 19286909Simp DetectedVirtual = BaseType->getAs<RecordType>(); 19386909Simp SetVirtual = true; 19486909Simp } 19586909Simp } else 19686909Simp ++Subobjects.second; 19786909Simp 19886909Simp if (isRecordingPaths()) { 19986909Simp // Add this base specifier to the current path. 20086909Simp CXXBasePathElement Element; 20186909Simp Element.Base = &*BaseSpec; 20286909Simp Element.Class = Record; 20386909Simp if (BaseSpec->isVirtual()) 20486909Simp Element.SubobjectNumber = 0; 20586909Simp else 20686909Simp Element.SubobjectNumber = Subobjects.second; 20786909Simp ScratchPath.push_back(Element); 20886909Simp 20986909Simp // Calculate the "top-down" access to this base class. 21086909Simp // The spec actually describes this bottom-up, but top-down is 21186909Simp // equivalent because the definition works out as follows: 21286909Simp // 1. Write down the access along each step in the inheritance 21386909Simp // chain, followed by the access of the decl itself. 21486909Simp // For example, in 21586909Simp // class A { public: int foo; }; 21686909Simp // class B : protected A {}; 21786909Simp // class C : public B {}; 21886909Simp // class D : private C {}; 21986909Simp // we would write: 22086909Simp // private public protected public 22186909Simp // 2. If 'private' appears anywhere except far-left, access is denied. 22286909Simp // 3. Otherwise, overall access is determined by the most restrictive 22386909Simp // access in the sequence. 22486909Simp if (IsFirstStep) 22586909Simp ScratchPath.Access = BaseSpec->getAccessSpecifier(); 22686909Simp else 22786909Simp ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere, 22886909Simp BaseSpec->getAccessSpecifier()); 22986909Simp } 23086909Simp 23186909Simp // Track whether there's a path involving this specific base. 23286909Simp bool FoundPathThroughBase = false; 23386909Simp 23486909Simp if (BaseMatches(BaseSpec, ScratchPath, UserData)) { 23586909Simp // We've found a path that terminates at this base. 23686909Simp FoundPath = FoundPathThroughBase = true; 23786909Simp if (isRecordingPaths()) { 23886909Simp // We have a path. Make a copy of it before moving on. 23986909Simp Paths.push_back(ScratchPath); 24086909Simp } else if (!isFindingAmbiguities()) { 24186909Simp // We found a path and we don't care about ambiguities; 24286909Simp // return immediately. 24386909Simp return FoundPath; 24486909Simp } 24586909Simp } else if (VisitBase) { 24686909Simp CXXRecordDecl *BaseRecord 24786909Simp = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>() 24886909Simp ->getDecl()); 24986909Simp if (lookupInBases(Context, BaseRecord, BaseMatches, UserData)) { 25086909Simp // C++ [class.member.lookup]p2: 25186909Simp // A member name f in one sub-object B hides a member name f in 25286909Simp // a sub-object A if A is a base class sub-object of B. Any 25386909Simp // declarations that are so hidden are eliminated from 25486909Simp // consideration. 25586909Simp 25686909Simp // There is a path to a base class that meets the criteria. If we're 25786909Simp // not collecting paths or finding ambiguities, we're done. 25886909Simp FoundPath = FoundPathThroughBase = true; 25986909Simp if (!isFindingAmbiguities()) 26086909Simp return FoundPath; 26186909Simp } 26286909Simp } 26386909Simp 26486909Simp // Pop this base specifier off the current path (if we're 26586909Simp // collecting paths). 26686909Simp if (isRecordingPaths()) { 26786909Simp ScratchPath.pop_back(); 26886909Simp } 26986909Simp 27086909Simp // If we set a virtual earlier, and this isn't a path, forget it again. 27186909Simp if (SetVirtual && !FoundPathThroughBase) { 27251078Speter DetectedVirtual = 0; 27351078Speter } 27451078Speter } 27551078Speter 27651078Speter // Reset the scratch path access. 27751078Speter ScratchPath.Access = AccessToHere; 27851078Speter 27951078Speter return FoundPath; 28051078Speter} 28151078Speter 28251078Speterbool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches, 28367551Sjhb void *UserData, 28451078Speter CXXBasePaths &Paths) const { 28565605Sjhb // If we didn't find anything, report that. 28651078Speter if (!Paths.lookupInBases(getASTContext(), this, BaseMatches, UserData)) 28751654Sphk return false; 28851078Speter 28951078Speter // If we're not recording paths or we won't ever find ambiguities, 29051078Speter // we're done. 29151078Speter if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities()) 29285365Simp return true; 29370174Sjhb 29470174Sjhb // C++ [class.member.lookup]p6: 29551078Speter // When virtual base classes are used, a hidden declaration can be 29651078Speter // reached along a path through the sub-object lattice that does 29785365Simp // not pass through the hiding declaration. This is not an 29851078Speter // ambiguity. The identical use with nonvirtual base classes is an 29986909Simp // ambiguity; in that case there is no unique instance of the name 30051078Speter // that hides all the others. 30151078Speter // 30251078Speter // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy 30351078Speter // way to make it any faster. 30451078Speter for (CXXBasePaths::paths_iterator P = Paths.begin(), PEnd = Paths.end(); 30551078Speter P != PEnd; /* increment in loop */) { 30651078Speter bool Hidden = false; 30751078Speter 30851078Speter for (CXXBasePath::iterator PE = P->begin(), PEEnd = P->end(); 30951078Speter PE != PEEnd && !Hidden; ++PE) { 31051078Speter if (PE->Base->isVirtual()) { 31151078Speter CXXRecordDecl *VBase = 0; 31251078Speter if (const RecordType *Record = PE->Base->getType()->getAs<RecordType>()) 31351078Speter VBase = cast<CXXRecordDecl>(Record->getDecl()); 31451654Sphk if (!VBase) 31551078Speter break; 31651078Speter 31785365Simp // The declaration(s) we found along this path were found in a 31851078Speter // subobject of a virtual base. Check whether this virtual 31951078Speter // base is a subobject of any other path; if so, then the 32051078Speter // declaration in this path are hidden by that patch. 32172521Sjlemon for (CXXBasePaths::paths_iterator HidingP = Paths.begin(), 32272521Sjlemon HidingPEnd = Paths.end(); 32351078Speter HidingP != HidingPEnd; 32451078Speter ++HidingP) { 32551078Speter CXXRecordDecl *HidingClass = 0; 32651078Speter if (const RecordType *Record 32751078Speter = HidingP->back().Base->getType()->getAs<RecordType>()) 32851078Speter HidingClass = cast<CXXRecordDecl>(Record->getDecl()); 32951078Speter if (!HidingClass) 33051078Speter break; 33151078Speter 33266230Sjhb if (HidingClass->isVirtuallyDerivedFrom(VBase)) { 33351078Speter Hidden = true; 33466230Sjhb break; 33551078Speter } 33651078Speter } 33772238Sjhb } 33872238Sjhb } 33951078Speter 34051078Speter if (Hidden) 34151078Speter P = Paths.Paths.erase(P); 34251078Speter else 34353344Speter ++P; 34451078Speter } 34551078Speter 34651078Speter return true; 34751078Speter} 34851078Speter 34951078Speterbool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier, 35051078Speter CXXBasePath &Path, 35151078Speter void *BaseRecord) { 35251078Speter assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord && 35351078Speter "User data for FindBaseClass is not canonical!"); 35451078Speter return Specifier->getType()->getAs<RecordType>()->getDecl() 35551078Speter ->getCanonicalDecl() == BaseRecord; 35651078Speter} 35751078Speter 35851078Speterbool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier, 35951078Speter CXXBasePath &Path, 36051078Speter void *BaseRecord) { 36184103Sjlemon assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord && 36251078Speter "User data for FindBaseClass is not canonical!"); 36351078Speter return Specifier->isVirtual() && 36451078Speter Specifier->getType()->getAs<RecordType>()->getDecl() 36551078Speter ->getCanonicalDecl() == BaseRecord; 36651078Speter} 36751078Speter 36851078Speterbool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier, 36951078Speter CXXBasePath &Path, 37086909Simp void *Name) { 37151078Speter RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 37251078Speter 37351078Speter DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 37451078Speter for (Path.Decls = BaseRecord->lookup(N); 37551078Speter Path.Decls.first != Path.Decls.second; 37651078Speter ++Path.Decls.first) { 37751078Speter if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 37851078Speter return true; 37951078Speter } 38051078Speter 38151078Speter return false; 38251078Speter} 38351078Speter 38451078Speterbool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier, 38551078Speter CXXBasePath &Path, 38662573Sphk void *Name) { 38751078Speter RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 38851078Speter 38951078Speter const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member; 39051078Speter DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 39151078Speter for (Path.Decls = BaseRecord->lookup(N); 39251078Speter Path.Decls.first != Path.Decls.second; 39351078Speter ++Path.Decls.first) { 39451078Speter if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS)) 39551078Speter return true; 39651078Speter } 39751078Speter 39851078Speter return false; 39951078Speter} 40051078Speter 40151078Speterbool CXXRecordDecl:: 40251078SpeterFindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier, 40351078Speter CXXBasePath &Path, 40451078Speter void *Name) { 40557915Simp RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 40651078Speter 40751078Speter DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 40851078Speter for (Path.Decls = BaseRecord->lookup(N); 40951078Speter Path.Decls.first != Path.Decls.second; 41051078Speter ++Path.Decls.first) { 41151078Speter // FIXME: Refactor the "is it a nested-name-specifier?" check 41251078Speter if (isa<TypedefDecl>(*Path.Decls.first) || 41351078Speter (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 41451078Speter return true; 41551078Speter } 41651078Speter 41751078Speter return false; 41851078Speter} 41951078Speter