CXXInheritance.cpp revision 203955
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) { 5351078Speter assert(BaseType.isCanonical() && "Base type must be the canonical type"); 5451078Speter 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. 6051078Spetervoid CXXBasePaths::clear() { 6151078Speter Paths.clear(); 6251078Speter ClassSubobjects.clear(); 6351078Speter ScratchPath.clear(); 6451078Speter DetectedVirtual = 0; 6551078Speter} 6651078Speter 6751078Speter/// @brief Swaps the contents of this CXXBasePaths structure with the 6851078Speter/// contents of Other. 6951078Spetervoid CXXBasePaths::swap(CXXBasePaths &Other) { 7051078Speter std::swap(Origin, Other.Origin); 7151078Speter Paths.swap(Other.Paths); 7251078Speter ClassSubobjects.swap(Other.ClassSubobjects); 7351078Speter std::swap(FindAmbiguities, Other.FindAmbiguities); 7451078Speter std::swap(RecordPaths, Other.RecordPaths); 7551078Speter std::swap(DetectVirtual, Other.DetectVirtual); 7651078Speter std::swap(DetectedVirtual, Other.DetectedVirtual); 7751078Speter} 7851078Speter 7951078Speterbool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base) const { 8051078Speter CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, 8151078Speter /*DetectVirtual=*/false); 8251078Speter return isDerivedFrom(Base, Paths); 8351078Speter} 8451078Speter 8551078Speterbool 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 9351078Speterstatic bool BaseIsNot(const CXXRecordDecl *Base, void *OpaqueTarget) { 9451078Speter // OpaqueTarget is a CXXRecordDecl*. 9551078Speter return Base->getCanonicalDecl() != (const CXXRecordDecl*) OpaqueTarget; 9651078Speter} 9751078Speter 9851078Speterbool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const { 9951078Speter return forallBases(BaseIsNot, (void*) Base->getCanonicalDecl()); 10051078Speter} 10151078Speter 10251078Speterbool CXXRecordDecl::forallBases(ForallBasesCallback *BaseMatches, 10351078Speter void *OpaqueData, 10451078Speter bool AllowShortCircuit) const { 10551078Speter llvm::SmallVector<const CXXRecordDecl*, 8> Queue; 10651078Speter 10751078Speter const CXXRecordDecl *Record = this; 10851078Speter bool AllMatches = true; 10951078Speter while (true) { 11051078Speter for (CXXRecordDecl::base_class_const_iterator 11151078Speter I = Record->bases_begin(), E = Record->bases_end(); I != E; ++I) { 11251078Speter const RecordType *Ty = I->getType()->getAs<RecordType>(); 11351078Speter if (!Ty) { 11451078Speter if (AllowShortCircuit) return false; 11551078Speter AllMatches = false; 11651078Speter continue; 11751078Speter } 11851078Speter 11951078Speter CXXRecordDecl *Base = 12051078Speter cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition()); 12151078Speter if (!Base) { 12251078Speter if (AllowShortCircuit) return false; 12351078Speter AllMatches = false; 12451078Speter continue; 12551078Speter } 12651078Speter 12751078Speter Queue.push_back(Base); 12851078Speter if (!BaseMatches(Base, OpaqueData)) { 12951078Speter if (AllowShortCircuit) return false; 13051078Speter AllMatches = false; 13151078Speter continue; 13251078Speter } 13351078Speter } 13451078Speter 13551078Speter if (Queue.empty()) break; 13651078Speter Record = Queue.back(); // not actually a queue. 13751078Speter Queue.pop_back(); 13851078Speter } 13951078Speter 14051078Speter return AllMatches; 14151078Speter} 14251078Speter 14351078Speterbool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches, 14451078Speter void *UserData, 14551078Speter CXXBasePaths &Paths) const { 14651078Speter bool FoundPath = false; 14751078Speter 14851078Speter // The access of the path down to this record. 14951078Speter AccessSpecifier AccessToHere = Paths.ScratchPath.Access; 15051078Speter bool IsFirstStep = Paths.ScratchPath.empty(); 15151078Speter 15251078Speter ASTContext &Context = getASTContext(); 15351078Speter for (base_class_const_iterator BaseSpec = bases_begin(), 15451078Speter BaseSpecEnd = bases_end(); BaseSpec != BaseSpecEnd; ++BaseSpec) { 15551078Speter // Find the record of the base class subobjects for this type. 15651078Speter QualType BaseType = Context.getCanonicalType(BaseSpec->getType()) 15751078Speter .getUnqualifiedType(); 15851078Speter 15951078Speter // C++ [temp.dep]p3: 16051078Speter // In the definition of a class template or a member of a class template, 16151078Speter // if a base class of the class template depends on a template-parameter, 16251078Speter // the base class scope is not examined during unqualified name lookup 16351078Speter // either at the point of definition of the class template or member or 16451078Speter // during an instantiation of the class tem- plate or member. 16551078Speter if (BaseType->isDependentType()) 16651078Speter continue; 16751078Speter 16851078Speter // Determine whether we need to visit this base class at all, 16951078Speter // updating the count of subobjects appropriately. 17051078Speter std::pair<bool, unsigned>& Subobjects = Paths.ClassSubobjects[BaseType]; 17151078Speter bool VisitBase = true; 17251078Speter bool SetVirtual = false; 17351078Speter if (BaseSpec->isVirtual()) { 17451078Speter VisitBase = !Subobjects.first; 17551078Speter Subobjects.first = true; 17651078Speter if (Paths.isDetectingVirtual() && Paths.DetectedVirtual == 0) { 17751078Speter // If this is the first virtual we find, remember it. If it turns out 17851078Speter // there is no base path here, we'll reset it later. 17951078Speter Paths.DetectedVirtual = BaseType->getAs<RecordType>(); 18051078Speter SetVirtual = true; 18151078Speter } 18251078Speter } else 18351078Speter ++Subobjects.second; 18451078Speter 18551078Speter if (Paths.isRecordingPaths()) { 18651078Speter // Add this base specifier to the current path. 18751078Speter CXXBasePathElement Element; 18851078Speter Element.Base = &*BaseSpec; 18951078Speter Element.Class = this; 19051078Speter if (BaseSpec->isVirtual()) 19151078Speter Element.SubobjectNumber = 0; 19251078Speter else 19351078Speter Element.SubobjectNumber = Subobjects.second; 19451078Speter Paths.ScratchPath.push_back(Element); 19551078Speter 19651078Speter // Calculate the "top-down" access to this base class. 19751078Speter // The spec actually describes this bottom-up, but top-down is 19851078Speter // equivalent because the definition works out as follows: 19951078Speter // 1. Write down the access along each step in the inheritance 20051078Speter // chain, followed by the access of the decl itself. 20151078Speter // For example, in 20251078Speter // class A { public: int foo; }; 20351078Speter // class B : protected A {}; 20451078Speter // class C : public B {}; 20551078Speter // class D : private C {}; 20651078Speter // we would write: 20751078Speter // private public protected public 20851078Speter // 2. If 'private' appears anywhere except far-left, access is denied. 20951078Speter // 3. Otherwise, overall access is determined by the most restrictive 21051078Speter // access in the sequence. 21151078Speter if (IsFirstStep) 21251078Speter Paths.ScratchPath.Access = BaseSpec->getAccessSpecifier(); 21351078Speter else 21451078Speter Paths.ScratchPath.Access 21551078Speter = MergeAccess(AccessToHere, BaseSpec->getAccessSpecifier()); 21651078Speter } 21751078Speter 21851078Speter // Track whether there's a path involving this specific base. 21951078Speter bool FoundPathThroughBase = false; 22051078Speter 22151078Speter if (BaseMatches(BaseSpec, Paths.ScratchPath, UserData)) { 22251078Speter // We've found a path that terminates at this base. 22351078Speter FoundPath = FoundPathThroughBase = true; 22451078Speter if (Paths.isRecordingPaths()) { 22551078Speter // We have a path. Make a copy of it before moving on. 22651078Speter Paths.Paths.push_back(Paths.ScratchPath); 22751078Speter } else if (!Paths.isFindingAmbiguities()) { 22851078Speter // We found a path and we don't care about ambiguities; 22951078Speter // return immediately. 23051078Speter return FoundPath; 23151078Speter } 23251078Speter } else if (VisitBase) { 23351078Speter CXXRecordDecl *BaseRecord 23451078Speter = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>() 23551078Speter ->getDecl()); 23651078Speter if (BaseRecord->lookupInBases(BaseMatches, UserData, Paths)) { 23751078Speter // C++ [class.member.lookup]p2: 23851078Speter // A member name f in one sub-object B hides a member name f in 23951078Speter // a sub-object A if A is a base class sub-object of B. Any 24051078Speter // declarations that are so hidden are eliminated from 24151078Speter // consideration. 24251078Speter 24351078Speter // There is a path to a base class that meets the criteria. If we're 24451078Speter // not collecting paths or finding ambiguities, we're done. 24551078Speter FoundPath = FoundPathThroughBase = true; 24651078Speter if (!Paths.isFindingAmbiguities()) 24751078Speter return FoundPath; 24851078Speter } 24951078Speter } 25051078Speter 25151078Speter // Pop this base specifier off the current path (if we're 25251078Speter // collecting paths). 25351078Speter if (Paths.isRecordingPaths()) { 25451078Speter Paths.ScratchPath.pop_back(); 25551078Speter } 25651078Speter 25751078Speter // If we set a virtual earlier, and this isn't a path, forget it again. 25851078Speter if (SetVirtual && !FoundPathThroughBase) { 25951078Speter Paths.DetectedVirtual = 0; 26051078Speter } 26151078Speter } 26251078Speter 26351078Speter // Reset the scratch path access. 26451078Speter Paths.ScratchPath.Access = AccessToHere; 26551078Speter 26651078Speter return FoundPath; 26751078Speter} 26851078Speter 26951078Speterbool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier, 27051078Speter CXXBasePath &Path, 27151078Speter void *BaseRecord) { 27251078Speter assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord && 27351078Speter "User data for FindBaseClass is not canonical!"); 27451078Speter return Specifier->getType()->getAs<RecordType>()->getDecl() 27551078Speter ->getCanonicalDecl() == BaseRecord; 27651078Speter} 27751078Speter 27851078Speterbool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier, 27951078Speter CXXBasePath &Path, 28051078Speter void *Name) { 28151078Speter RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 28251078Speter 28351078Speter DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 28451078Speter for (Path.Decls = BaseRecord->lookup(N); 28551078Speter Path.Decls.first != Path.Decls.second; 28651078Speter ++Path.Decls.first) { 28751078Speter if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 28851078Speter return true; 28951078Speter } 29051078Speter 29151078Speter return false; 29251078Speter} 29351078Speter 29451078Speterbool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier, 29551078Speter CXXBasePath &Path, 29651078Speter void *Name) { 29751078Speter RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 29851078Speter 29951078Speter const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member; 30051078Speter DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 30151078Speter for (Path.Decls = BaseRecord->lookup(N); 30251078Speter Path.Decls.first != Path.Decls.second; 30351078Speter ++Path.Decls.first) { 30451078Speter if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS)) 30551078Speter return true; 30651078Speter } 30751078Speter 30851078Speter return false; 30951078Speter} 31051078Speter 31151078Speterbool CXXRecordDecl:: 31251078SpeterFindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier, 31351078Speter CXXBasePath &Path, 31451078Speter void *Name) { 31551078Speter RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 31651078Speter 31751078Speter DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 31851078Speter for (Path.Decls = BaseRecord->lookup(N); 31951078Speter Path.Decls.first != Path.Decls.second; 32051078Speter ++Path.Decls.first) { 32151078Speter // FIXME: Refactor the "is it a nested-name-specifier?" check 32251078Speter if (isa<TypedefDecl>(*Path.Decls.first) || 32351078Speter (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 32451078Speter return true; 32551078Speter } 32651078Speter 32751078Speter return false; 32851078Speter} 32951078Speter