//===------ CXXInheritance.cpp - C++ Inheritance ----------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file provides routines that help analyzing C++ inheritance hierarchies. // //===----------------------------------------------------------------------===// #include "clang/AST/CXXInheritance.h" #include "clang/AST/ASTContext.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/RecordLayout.h" #include "llvm/ADT/SetVector.h" #include <algorithm> #include <set> using namespace clang; /// \brief Computes the set of declarations referenced by these base /// paths. void CXXBasePaths::ComputeDeclsFound() { assert(NumDeclsFound == 0 && !DeclsFound && "Already computed the set of declarations"); llvm::SetVector<NamedDecl *, SmallVector<NamedDecl *, 8> > Decls; for (paths_iterator Path = begin(), PathEnd = end(); Path != PathEnd; ++Path) Decls.insert(Path->Decls.front()); NumDeclsFound = Decls.size(); DeclsFound = llvm::make_unique<NamedDecl *[]>(NumDeclsFound); std::copy(Decls.begin(), Decls.end(), DeclsFound.get()); } CXXBasePaths::decl_range CXXBasePaths::found_decls() { if (NumDeclsFound == 0) ComputeDeclsFound(); return decl_range(decl_iterator(DeclsFound.get()), decl_iterator(DeclsFound.get() + NumDeclsFound)); } /// isAmbiguous - Determines whether the set of paths provided is /// ambiguous, i.e., there are two or more paths that refer to /// different base class subobjects of the same type. BaseType must be /// an unqualified, canonical class type. bool CXXBasePaths::isAmbiguous(CanQualType BaseType) { BaseType = BaseType.getUnqualifiedType(); std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType]; return Subobjects.second + (Subobjects.first? 1 : 0) > 1; } /// clear - Clear out all prior path information. void CXXBasePaths::clear() { Paths.clear(); ClassSubobjects.clear(); ScratchPath.clear(); DetectedVirtual = nullptr; } /// @brief Swaps the contents of this CXXBasePaths structure with the /// contents of Other. void CXXBasePaths::swap(CXXBasePaths &Other) { std::swap(Origin, Other.Origin); Paths.swap(Other.Paths); ClassSubobjects.swap(Other.ClassSubobjects); std::swap(FindAmbiguities, Other.FindAmbiguities); std::swap(RecordPaths, Other.RecordPaths); std::swap(DetectVirtual, Other.DetectVirtual); std::swap(DetectedVirtual, Other.DetectedVirtual); } bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const { CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, /*DetectVirtual=*/false); return isDerivedFrom(Base, Paths); } bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base, CXXBasePaths &Paths) const { if (getCanonicalDecl() == Base->getCanonicalDecl()) return false; Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl(); // FIXME: Capturing 'this' is a workaround for name lookup bugs in GCC 4.7. return lookupInBases( [this, BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { return FindBaseClass(Specifier, Path, BaseDecl); }, Paths); } bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const { if (!getNumVBases()) return false; CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, /*DetectVirtual=*/false); if (getCanonicalDecl() == Base->getCanonicalDecl()) return false; Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl(); // FIXME: Capturing 'this' is a workaround for name lookup bugs in GCC 4.7. return lookupInBases( [this, BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { return FindVirtualBaseClass(Specifier, Path, BaseDecl); }, Paths); } bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const { const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl(); return forallBases([TargetDecl](const CXXRecordDecl *Base) { return Base->getCanonicalDecl() != TargetDecl; }); } bool CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const { assert(isDependentContext()); for (; !CurContext->isFileContext(); CurContext = CurContext->getParent()) if (CurContext->Equals(this)) return true; return false; } bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches, bool AllowShortCircuit) const { SmallVector<const CXXRecordDecl*, 8> Queue; const CXXRecordDecl *Record = this; bool AllMatches = true; while (true) { for (const auto &I : Record->bases()) { const RecordType *Ty = I.getType()->getAs<RecordType>(); if (!Ty) { if (AllowShortCircuit) return false; AllMatches = false; continue; } CXXRecordDecl *Base = cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition()); if (!Base || (Base->isDependentContext() && !Base->isCurrentInstantiation(Record))) { if (AllowShortCircuit) return false; AllMatches = false; continue; } Queue.push_back(Base); if (!BaseMatches(Base)) { if (AllowShortCircuit) return false; AllMatches = false; continue; } } if (Queue.empty()) break; Record = Queue.pop_back_val(); // not actually a queue. } return AllMatches; } bool CXXBasePaths::lookupInBases( ASTContext &Context, const CXXRecordDecl *Record, CXXRecordDecl::BaseMatchesCallback BaseMatches) { bool FoundPath = false; // The access of the path down to this record. AccessSpecifier AccessToHere = ScratchPath.Access; bool IsFirstStep = ScratchPath.empty(); for (const auto &BaseSpec : Record->bases()) { // Find the record of the base class subobjects for this type. QualType BaseType = Context.getCanonicalType(BaseSpec.getType()).getUnqualifiedType(); // C++ [temp.dep]p3: // In the definition of a class template or a member of a class template, // if a base class of the class template depends on a template-parameter, // the base class scope is not examined during unqualified name lookup // either at the point of definition of the class template or member or // during an instantiation of the class tem- plate or member. if (BaseType->isDependentType()) continue; // Determine whether we need to visit this base class at all, // updating the count of subobjects appropriately. std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType]; bool VisitBase = true; bool SetVirtual = false; if (BaseSpec.isVirtual()) { VisitBase = !Subobjects.first; Subobjects.first = true; if (isDetectingVirtual() && DetectedVirtual == nullptr) { // If this is the first virtual we find, remember it. If it turns out // there is no base path here, we'll reset it later. DetectedVirtual = BaseType->getAs<RecordType>(); SetVirtual = true; } } else ++Subobjects.second; if (isRecordingPaths()) { // Add this base specifier to the current path. CXXBasePathElement Element; Element.Base = &BaseSpec; Element.Class = Record; if (BaseSpec.isVirtual()) Element.SubobjectNumber = 0; else Element.SubobjectNumber = Subobjects.second; ScratchPath.push_back(Element); // Calculate the "top-down" access to this base class. // The spec actually describes this bottom-up, but top-down is // equivalent because the definition works out as follows: // 1. Write down the access along each step in the inheritance // chain, followed by the access of the decl itself. // For example, in // class A { public: int foo; }; // class B : protected A {}; // class C : public B {}; // class D : private C {}; // we would write: // private public protected public // 2. If 'private' appears anywhere except far-left, access is denied. // 3. Otherwise, overall access is determined by the most restrictive // access in the sequence. if (IsFirstStep) ScratchPath.Access = BaseSpec.getAccessSpecifier(); else ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere, BaseSpec.getAccessSpecifier()); } // Track whether there's a path involving this specific base. bool FoundPathThroughBase = false; if (BaseMatches(&BaseSpec, ScratchPath)) { // We've found a path that terminates at this base. FoundPath = FoundPathThroughBase = true; if (isRecordingPaths()) { // We have a path. Make a copy of it before moving on. Paths.push_back(ScratchPath); } else if (!isFindingAmbiguities()) { // We found a path and we don't care about ambiguities; // return immediately. return FoundPath; } } else if (VisitBase) { CXXRecordDecl *BaseRecord = cast<CXXRecordDecl>(BaseSpec.getType()->castAs<RecordType>() ->getDecl()); if (lookupInBases(Context, BaseRecord, BaseMatches)) { // C++ [class.member.lookup]p2: // A member name f in one sub-object B hides a member name f in // a sub-object A if A is a base class sub-object of B. Any // declarations that are so hidden are eliminated from // consideration. // There is a path to a base class that meets the criteria. If we're // not collecting paths or finding ambiguities, we're done. FoundPath = FoundPathThroughBase = true; if (!isFindingAmbiguities()) return FoundPath; } } // Pop this base specifier off the current path (if we're // collecting paths). if (isRecordingPaths()) { ScratchPath.pop_back(); } // If we set a virtual earlier, and this isn't a path, forget it again. if (SetVirtual && !FoundPathThroughBase) { DetectedVirtual = nullptr; } } // Reset the scratch path access. ScratchPath.Access = AccessToHere; return FoundPath; } bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches, CXXBasePaths &Paths) const { // If we didn't find anything, report that. if (!Paths.lookupInBases(getASTContext(), this, BaseMatches)) return false; // If we're not recording paths or we won't ever find ambiguities, // we're done. if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities()) return true; // C++ [class.member.lookup]p6: // When virtual base classes are used, a hidden declaration can be // reached along a path through the sub-object lattice that does // not pass through the hiding declaration. This is not an // ambiguity. The identical use with nonvirtual base classes is an // ambiguity; in that case there is no unique instance of the name // that hides all the others. // // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy // way to make it any faster. Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) { for (const CXXBasePathElement &PE : Path) { if (!PE.Base->isVirtual()) continue; CXXRecordDecl *VBase = nullptr; if (const RecordType *Record = PE.Base->getType()->getAs<RecordType>()) VBase = cast<CXXRecordDecl>(Record->getDecl()); if (!VBase) break; // The declaration(s) we found along this path were found in a // subobject of a virtual base. Check whether this virtual // base is a subobject of any other path; if so, then the // declaration in this path are hidden by that patch. for (const CXXBasePath &HidingP : Paths) { CXXRecordDecl *HidingClass = nullptr; if (const RecordType *Record = HidingP.back().Base->getType()->getAs<RecordType>()) HidingClass = cast<CXXRecordDecl>(Record->getDecl()); if (!HidingClass) break; if (HidingClass->isVirtuallyDerivedFrom(VBase)) return true; } } return false; }); return true; } bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier, CXXBasePath &Path, const CXXRecordDecl *BaseRecord) { assert(BaseRecord->getCanonicalDecl() == BaseRecord && "User data for FindBaseClass is not canonical!"); return Specifier->getType()->castAs<RecordType>()->getDecl() ->getCanonicalDecl() == BaseRecord; } bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier, CXXBasePath &Path, const CXXRecordDecl *BaseRecord) { assert(BaseRecord->getCanonicalDecl() == BaseRecord && "User data for FindBaseClass is not canonical!"); return Specifier->isVirtual() && Specifier->getType()->castAs<RecordType>()->getDecl() ->getCanonicalDecl() == BaseRecord; } bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier, CXXBasePath &Path, DeclarationName Name) { RecordDecl *BaseRecord = Specifier->getType()->castAs<RecordType>()->getDecl(); for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty(); Path.Decls = Path.Decls.slice(1)) { if (Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag)) return true; } return false; } bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier, CXXBasePath &Path, DeclarationName Name) { RecordDecl *BaseRecord = Specifier->getType()->castAs<RecordType>()->getDecl(); const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member; for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty(); Path.Decls = Path.Decls.slice(1)) { if (Path.Decls.front()->isInIdentifierNamespace(IDNS)) return true; } return false; } bool CXXRecordDecl::FindOMPReductionMember(const CXXBaseSpecifier *Specifier, CXXBasePath &Path, DeclarationName Name) { RecordDecl *BaseRecord = Specifier->getType()->castAs<RecordType>()->getDecl(); for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty(); Path.Decls = Path.Decls.slice(1)) { if (Path.Decls.front()->isInIdentifierNamespace(IDNS_OMPReduction)) return true; } return false; } bool CXXRecordDecl:: FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier, CXXBasePath &Path, DeclarationName Name) { RecordDecl *BaseRecord = Specifier->getType()->castAs<RecordType>()->getDecl(); for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty(); Path.Decls = Path.Decls.slice(1)) { // FIXME: Refactor the "is it a nested-name-specifier?" check if (isa<TypedefNameDecl>(Path.Decls.front()) || Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag)) return true; } return false; } void OverridingMethods::add(unsigned OverriddenSubobject, UniqueVirtualMethod Overriding) { SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides = Overrides[OverriddenSubobject]; if (std::find(SubobjectOverrides.begin(), SubobjectOverrides.end(), Overriding) == SubobjectOverrides.end()) SubobjectOverrides.push_back(Overriding); } void OverridingMethods::add(const OverridingMethods &Other) { for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I) { for (overriding_const_iterator M = I->second.begin(), MEnd = I->second.end(); M != MEnd; ++M) add(I->first, *M); } } void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) { for (iterator I = begin(), IEnd = end(); I != IEnd; ++I) { I->second.clear(); I->second.push_back(Overriding); } } namespace { class FinalOverriderCollector { /// \brief The number of subobjects of a given class type that /// occur within the class hierarchy. llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount; /// \brief Overriders for each virtual base subobject. llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders; CXXFinalOverriderMap FinalOverriders; public: ~FinalOverriderCollector(); void Collect(const CXXRecordDecl *RD, bool VirtualBase, const CXXRecordDecl *InVirtualSubobject, CXXFinalOverriderMap &Overriders); }; } void FinalOverriderCollector::Collect(const CXXRecordDecl *RD, bool VirtualBase, const CXXRecordDecl *InVirtualSubobject, CXXFinalOverriderMap &Overriders) { unsigned SubobjectNumber = 0; if (!VirtualBase) SubobjectNumber = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())]; for (const auto &Base : RD->bases()) { if (const RecordType *RT = Base.getType()->getAs<RecordType>()) { const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl()); if (!BaseDecl->isPolymorphic()) continue; if (Overriders.empty() && !Base.isVirtual()) { // There are no other overriders of virtual member functions, // so let the base class fill in our overriders for us. Collect(BaseDecl, false, InVirtualSubobject, Overriders); continue; } // Collect all of the overridders from the base class subobject // and merge them into the set of overridders for this class. // For virtual base classes, populate or use the cached virtual // overrides so that we do not walk the virtual base class (and // its base classes) more than once. CXXFinalOverriderMap ComputedBaseOverriders; CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders; if (Base.isVirtual()) { CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl]; BaseOverriders = MyVirtualOverriders; if (!MyVirtualOverriders) { MyVirtualOverriders = new CXXFinalOverriderMap; // Collect may cause VirtualOverriders to reallocate, invalidating the // MyVirtualOverriders reference. Set BaseOverriders to the right // value now. BaseOverriders = MyVirtualOverriders; Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders); } } else Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders); // Merge the overriders from this base class into our own set of // overriders. for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(), OMEnd = BaseOverriders->end(); OM != OMEnd; ++OM) { const CXXMethodDecl *CanonOM = cast<CXXMethodDecl>(OM->first->getCanonicalDecl()); Overriders[CanonOM].add(OM->second); } } } for (auto *M : RD->methods()) { // We only care about virtual methods. if (!M->isVirtual()) continue; CXXMethodDecl *CanonM = cast<CXXMethodDecl>(M->getCanonicalDecl()); if (CanonM->begin_overridden_methods() == CanonM->end_overridden_methods()) { // This is a new virtual function that does not override any // other virtual function. Add it to the map of virtual // functions for which we are tracking overridders. // C++ [class.virtual]p2: // For convenience we say that any virtual function overrides itself. Overriders[CanonM].add(SubobjectNumber, UniqueVirtualMethod(CanonM, SubobjectNumber, InVirtualSubobject)); continue; } // This virtual method overrides other virtual methods, so it does // not add any new slots into the set of overriders. Instead, we // replace entries in the set of overriders with the new // overrider. To do so, we dig down to the original virtual // functions using data recursion and update all of the methods it // overrides. typedef llvm::iterator_range<CXXMethodDecl::method_iterator> OverriddenMethods; SmallVector<OverriddenMethods, 4> Stack; Stack.push_back(llvm::make_range(CanonM->begin_overridden_methods(), CanonM->end_overridden_methods())); while (!Stack.empty()) { for (const CXXMethodDecl *OM : Stack.pop_back_val()) { const CXXMethodDecl *CanonOM = OM->getCanonicalDecl(); // C++ [class.virtual]p2: // A virtual member function C::vf of a class object S is // a final overrider unless the most derived class (1.8) // of which S is a base class subobject (if any) declares // or inherits another member function that overrides vf. // // Treating this object like the most derived class, we // replace any overrides from base classes with this // overriding virtual function. Overriders[CanonOM].replaceAll( UniqueVirtualMethod(CanonM, SubobjectNumber, InVirtualSubobject)); if (CanonOM->begin_overridden_methods() == CanonOM->end_overridden_methods()) continue; // Continue recursion to the methods that this virtual method // overrides. Stack.push_back(llvm::make_range(CanonOM->begin_overridden_methods(), CanonOM->end_overridden_methods())); } } // C++ [class.virtual]p2: // For convenience we say that any virtual function overrides itself. Overriders[CanonM].add(SubobjectNumber, UniqueVirtualMethod(CanonM, SubobjectNumber, InVirtualSubobject)); } } FinalOverriderCollector::~FinalOverriderCollector() { for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end(); VO != VOEnd; ++VO) delete VO->second; } void CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const { FinalOverriderCollector Collector; Collector.Collect(this, false, nullptr, FinalOverriders); // Weed out any final overriders that come from virtual base class // subobjects that were hidden by other subobjects along any path. // This is the final-overrider variant of C++ [class.member.lookup]p10. for (auto &OM : FinalOverriders) { for (auto &SO : OM.second) { SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second; if (Overriding.size() < 2) continue; auto IsHidden = [&Overriding](const UniqueVirtualMethod &M) { if (!M.InVirtualSubobject) return false; // We have an overriding method in a virtual base class // subobject (or non-virtual base class subobject thereof); // determine whether there exists an other overriding method // in a base class subobject that hides the virtual base class // subobject. for (const UniqueVirtualMethod &OP : Overriding) if (&M != &OP && OP.Method->getParent()->isVirtuallyDerivedFrom( M.InVirtualSubobject)) return true; return false; }; Overriding.erase( std::remove_if(Overriding.begin(), Overriding.end(), IsHidden), Overriding.end()); } } } static void AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context, CXXIndirectPrimaryBaseSet& Bases) { // If the record has a virtual primary base class, add it to our set. const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); if (Layout.isPrimaryBaseVirtual()) Bases.insert(Layout.getPrimaryBase()); for (const auto &I : RD->bases()) { assert(!I.getType()->isDependentType() && "Cannot get indirect primary bases for class with dependent bases."); const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl()); // Only bases with virtual bases participate in computing the // indirect primary virtual base classes. if (BaseDecl->getNumVBases()) AddIndirectPrimaryBases(BaseDecl, Context, Bases); } } void CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const { ASTContext &Context = getASTContext(); if (!getNumVBases()) return; for (const auto &I : bases()) { assert(!I.getType()->isDependentType() && "Cannot get indirect primary bases for class with dependent bases."); const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl()); // Only bases with virtual bases participate in computing the // indirect primary virtual base classes. if (BaseDecl->getNumVBases()) AddIndirectPrimaryBases(BaseDecl, Context, Bases); } }