CXXInheritance.cpp [plain text]
#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;
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));
}
bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
BaseType = BaseType.getUnqualifiedType();
std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
}
void CXXBasePaths::clear() {
Paths.clear();
ClassSubobjects.clear();
ScratchPath.clear();
DetectedVirtual = nullptr;
}
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(false, false,
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();
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(false, false,
false);
if (getCanonicalDecl() == Base->getCanonicalDecl())
return false;
Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
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(); }
return AllMatches;
}
bool CXXBasePaths::lookupInBases(
ASTContext &Context, const CXXRecordDecl *Record,
CXXRecordDecl::BaseMatchesCallback BaseMatches) {
bool FoundPath = false;
AccessSpecifier AccessToHere = ScratchPath.Access;
bool IsFirstStep = ScratchPath.empty();
for (const auto &BaseSpec : Record->bases()) {
QualType BaseType =
Context.getCanonicalType(BaseSpec.getType()).getUnqualifiedType();
if (BaseType->isDependentType())
continue;
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) {
DetectedVirtual = BaseType->getAs<RecordType>();
SetVirtual = true;
}
} else
++Subobjects.second;
if (isRecordingPaths()) {
CXXBasePathElement Element;
Element.Base = &BaseSpec;
Element.Class = Record;
if (BaseSpec.isVirtual())
Element.SubobjectNumber = 0;
else
Element.SubobjectNumber = Subobjects.second;
ScratchPath.push_back(Element);
if (IsFirstStep)
ScratchPath.Access = BaseSpec.getAccessSpecifier();
else
ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere,
BaseSpec.getAccessSpecifier());
}
bool FoundPathThroughBase = false;
if (BaseMatches(&BaseSpec, ScratchPath)) {
FoundPath = FoundPathThroughBase = true;
if (isRecordingPaths()) {
Paths.push_back(ScratchPath);
} else if (!isFindingAmbiguities()) {
return FoundPath;
}
} else if (VisitBase) {
CXXRecordDecl *BaseRecord
= cast<CXXRecordDecl>(BaseSpec.getType()->castAs<RecordType>()
->getDecl());
if (lookupInBases(Context, BaseRecord, BaseMatches)) {
FoundPath = FoundPathThroughBase = true;
if (!isFindingAmbiguities())
return FoundPath;
}
}
if (isRecordingPaths()) {
ScratchPath.pop_back();
}
if (SetVirtual && !FoundPathThroughBase) {
DetectedVirtual = nullptr;
}
}
ScratchPath.Access = AccessToHere;
return FoundPath;
}
bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches,
CXXBasePaths &Paths) const {
if (!Paths.lookupInBases(getASTContext(), this, BaseMatches))
return false;
if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities())
return true;
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;
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::
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)) {
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 {
llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount;
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()) {
Collect(BaseDecl, false, InVirtualSubobject, Overriders);
continue;
}
CXXFinalOverriderMap ComputedBaseOverriders;
CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders;
if (Base.isVirtual()) {
CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl];
BaseOverriders = MyVirtualOverriders;
if (!MyVirtualOverriders) {
MyVirtualOverriders = new CXXFinalOverriderMap;
BaseOverriders = MyVirtualOverriders;
Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders);
}
} else
Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders);
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()) {
if (!M->isVirtual())
continue;
CXXMethodDecl *CanonM = cast<CXXMethodDecl>(M->getCanonicalDecl());
if (CanonM->begin_overridden_methods()
== CanonM->end_overridden_methods()) {
Overriders[CanonM].add(SubobjectNumber,
UniqueVirtualMethod(CanonM, SubobjectNumber,
InVirtualSubobject));
continue;
}
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();
Overriders[CanonOM].replaceAll(
UniqueVirtualMethod(CanonM, SubobjectNumber,
InVirtualSubobject));
if (CanonOM->begin_overridden_methods()
== CanonOM->end_overridden_methods())
continue;
Stack.push_back(llvm::make_range(CanonOM->begin_overridden_methods(),
CanonOM->end_overridden_methods()));
}
}
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);
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;
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) {
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());
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());
if (BaseDecl->getNumVBases())
AddIndirectPrimaryBases(BaseDecl, Context, Bases);
}
}