blob: c48e3bc79eb1b1950ce0f70dca07ea24467808ec [file] [log] [blame]
//===---- SemaInherit.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 Sema routines for C++ inheritance semantics,
// including searching the inheritance hierarchy.
#include "SemaInherit.h"
#include "Sema.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/Type.h"
#include "clang/AST/TypeOrdering.h"
#include <algorithm>
#include <memory>
#include <set>
#include <string>
using namespace clang;
/// \brief Computes the set of declarations referenced by these base
/// paths.
void BasePaths::ComputeDeclsFound() {
assert(NumDeclsFound == 0 && !DeclsFound &&
"Already computed the set of declarations");
std::set<NamedDecl *> Decls;
for (BasePaths::paths_iterator Path = begin(), PathEnd = end();
Path != PathEnd; ++Path)
NumDeclsFound = Decls.size();
DeclsFound = new NamedDecl * [NumDeclsFound];
std::copy(Decls.begin(), Decls.end(), DeclsFound);
BasePaths::decl_iterator BasePaths::found_decls_begin() {
if (NumDeclsFound == 0)
return DeclsFound;
BasePaths::decl_iterator BasePaths::found_decls_end() {
if (NumDeclsFound == 0)
return DeclsFound + 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 BasePaths::isAmbiguous(QualType BaseType) {
assert(BaseType->isCanonical() && "Base type must be the canonical type");
assert(BaseType.getCVRQualifiers() == 0 && "Base type must be unqualified");
std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
/// clear - Clear out all prior path information.
void BasePaths::clear() {
DetectedVirtual = 0;
/// @brief Swaps the contents of this BasePaths structure with the
/// contents of Other.
void BasePaths::swap(BasePaths &Other) {
std::swap(Origin, Other.Origin);
std::swap(FindAmbiguities, Other.FindAmbiguities);
std::swap(RecordPaths, Other.RecordPaths);
std::swap(DetectVirtual, Other.DetectVirtual);
std::swap(DetectedVirtual, Other.DetectedVirtual);
/// IsDerivedFrom - Determine whether the type Derived is derived from
/// the type Base, ignoring qualifiers on Base and Derived. This
/// routine does not assess whether an actual conversion from a
/// Derived* to a Base* is legal, because it does not account for
/// ambiguous conversions or conversions to private/protected bases.
bool Sema::IsDerivedFrom(QualType Derived, QualType Base) {
BasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
return IsDerivedFrom(Derived, Base, Paths);
/// IsDerivedFrom - Determine whether the type Derived is derived from
/// the type Base, ignoring qualifiers on Base and Derived. This
/// routine does not assess whether an actual conversion from a
/// Derived* to a Base* is legal, because it does not account for
/// ambiguous conversions or conversions to private/protected
/// bases. This routine will use Paths to determine if there are
/// ambiguous paths (if @c Paths.isFindingAmbiguities()) and record
/// information about all of the paths (if @c Paths.isRecordingPaths()).
bool Sema::IsDerivedFrom(QualType Derived, QualType Base, BasePaths &Paths) {
Derived = Context.getCanonicalType(Derived).getUnqualifiedType();
Base = Context.getCanonicalType(Base).getUnqualifiedType();
if (!Derived->isRecordType() || !Base->isRecordType())
return false;
if (Derived == Base)
return false;
return LookupInBases(cast<CXXRecordDecl>(Derived->getAs<RecordType>()->getDecl()),
MemberLookupCriteria(Base), Paths);
/// LookupInBases - Look for something that meets the specified
/// Criteria within the base classes of Class (or any of its base
/// classes, transitively). This routine populates BasePaths with the
/// list of paths that one can take to find the entity that meets the
/// search criteria, and returns true if any such entity is found. The
/// various options passed to the BasePath constructor will affect the
/// behavior of this lookup, e.g., whether it finds ambiguities,
/// records paths, or attempts to detect the use of virtual base
/// classes.
bool Sema::LookupInBases(CXXRecordDecl *Class,
const MemberLookupCriteria& Criteria,
BasePaths &Paths) {
bool FoundPath = false;
for (CXXRecordDecl::base_class_const_iterator BaseSpec = Class->bases_begin(),
BaseSpecEnd = Class->bases_end();
BaseSpec != BaseSpecEnd; ++BaseSpec) {
// Find the record of the base class subobjects for this type.
QualType BaseType = Context.getCanonicalType(BaseSpec->getType());
BaseType = BaseType.getUnqualifiedType();
// If a base class of the class template depends on a template-parameter,
// the base class scope is not examined during unqualified name lookup.
// [temp.dep]p3.
if (BaseType->isDependentType())
// Determine whether we need to visit this base class at all,
// updating the count of subobjects appropriately.
std::pair<bool, unsigned>& Subobjects = Paths.ClassSubobjects[BaseType];
bool VisitBase = true;
bool SetVirtual = false;
if (BaseSpec->isVirtual()) {
VisitBase = !Subobjects.first;
Subobjects.first = true;
if (Paths.isDetectingVirtual() && Paths.DetectedVirtual == 0) {
// 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.
Paths.DetectedVirtual = BaseType->getAs<RecordType>();
SetVirtual = true;
} else
if (Paths.isRecordingPaths()) {
// Add this base specifier to the current path.
BasePathElement Element;
Element.Base = &*BaseSpec;
Element.Class = Class;
if (BaseSpec->isVirtual())
Element.SubobjectNumber = 0;
Element.SubobjectNumber = Subobjects.second;
CXXRecordDecl *BaseRecord
= cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>()->getDecl());
// Either look at the base class type or look into the base class
// type to see if we've found a member that meets the search
// criteria.
bool FoundPathToThisBase = false;
switch (Criteria.Kind) {
case MemberLookupCriteria::LK_Base:
= (Context.getCanonicalType(BaseSpec->getType()) == Criteria.Base);
case MemberLookupCriteria::LK_NamedMember:
Paths.ScratchPath.Decls = BaseRecord->lookup(Criteria.Name);
while (Paths.ScratchPath.Decls.first != Paths.ScratchPath.Decls.second) {
if (isAcceptableLookupResult(*Paths.ScratchPath.Decls.first,
Criteria.NameKind, Criteria.IDNS)) {
FoundPathToThisBase = true;
case MemberLookupCriteria::LK_OverriddenMember:
Paths.ScratchPath.Decls =
while (Paths.ScratchPath.Decls.first != Paths.ScratchPath.Decls.second) {
if (CXXMethodDecl *MD =
dyn_cast<CXXMethodDecl>(*Paths.ScratchPath.Decls.first)) {
OverloadedFunctionDecl::function_iterator MatchedDecl;
if (MD->isVirtual() &&
!IsOverload(Criteria.Method, MD, MatchedDecl)) {
FoundPathToThisBase = true;
if (FoundPathToThisBase) {
// We've found a path that terminates that this base.
FoundPath = true;
if (Paths.isRecordingPaths()) {
// We have a path. Make a copy of it before moving on.
} else if (!Paths.isFindingAmbiguities()) {
// We found a path and we don't care about ambiguities;
// return immediately.
return FoundPath;
} else if (VisitBase && LookupInBases(BaseRecord, Criteria, Paths)) {
// 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 = true;
if (!Paths.isFindingAmbiguities())
return FoundPath;
// Pop this base specifier off the current path (if we're
// collecting paths).
if (Paths.isRecordingPaths())
// If we set a virtual earlier, and this isn't a path, forget it again.
if (SetVirtual && !FoundPath) {
Paths.DetectedVirtual = 0;
return FoundPath;
/// CheckDerivedToBaseConversion - Check whether the Derived-to-Base
/// conversion (where Derived and Base are class types) is
/// well-formed, meaning that the conversion is unambiguous (and
/// that all of the base classes are accessible). Returns true
/// and emits a diagnostic if the code is ill-formed, returns false
/// otherwise. Loc is the location where this routine should point to
/// if there is an error, and Range is the source range to highlight
/// if there is an error.
Sema::CheckDerivedToBaseConversion(QualType Derived, QualType Base,
unsigned InaccessibleBaseID,
unsigned AmbigiousBaseConvID,
SourceLocation Loc, SourceRange Range,
DeclarationName Name) {
// First, determine whether the path from Derived to Base is
// ambiguous. This is slightly more expensive than checking whether
// the Derived to Base conversion exists, because here we need to
// explore multiple paths to determine if there is an ambiguity.
BasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true,
bool DerivationOkay = IsDerivedFrom(Derived, Base, Paths);
assert(DerivationOkay &&
"Can only be used with a derived-to-base conversion");
if (!Paths.isAmbiguous(Context.getCanonicalType(Base).getUnqualifiedType())) {
// Check that the base class can be accessed.
return CheckBaseClassAccess(Derived, Base, InaccessibleBaseID, Paths, Loc,
// We know that the derived-to-base conversion is ambiguous, and
// we're going to produce a diagnostic. Perform the derived-to-base
// search just one more time to compute all of the possible paths so
// that we can print them out. This is more expensive than any of
// the previous derived-to-base checks we've done, but at this point
// performance isn't as much of an issue.
bool StillOkay = IsDerivedFrom(Derived, Base, Paths);
assert(StillOkay && "Can only be used with a derived-to-base conversion");
// Build up a textual representation of the ambiguous paths, e.g.,
// D -> B -> A, that will be used to illustrate the ambiguous
// conversions in the diagnostic. We only print one of the paths
// to each base class subobject.
std::string PathDisplayStr = getAmbiguousPathsDisplayString(Paths);
Diag(Loc, AmbigiousBaseConvID)
<< Derived << Base << PathDisplayStr << Range << Name;
return true;
Sema::CheckDerivedToBaseConversion(QualType Derived, QualType Base,
SourceLocation Loc, SourceRange Range) {
return CheckDerivedToBaseConversion(Derived, Base,
Loc, Range, DeclarationName());
/// @brief Builds a string representing ambiguous paths from a
/// specific derived class to different subobjects of the same base
/// class.
/// This function builds a string that can be used in error messages
/// to show the different paths that one can take through the
/// inheritance hierarchy to go from the derived class to different
/// subobjects of a base class. The result looks something like this:
/// @code
/// struct D -> struct B -> struct A
/// struct D -> struct C -> struct A
/// @endcode
std::string Sema::getAmbiguousPathsDisplayString(BasePaths &Paths) {
std::string PathDisplayStr;
std::set<unsigned> DisplayedPaths;
for (BasePaths::paths_iterator Path = Paths.begin();
Path != Paths.end(); ++Path) {
if (DisplayedPaths.insert(Path->back().SubobjectNumber).second) {
// We haven't displayed a path to this particular base
// class subobject yet.
PathDisplayStr += "\n ";
PathDisplayStr += Paths.getOrigin().getAsString();
for (BasePath::const_iterator Element = Path->begin();
Element != Path->end(); ++Element)
PathDisplayStr += " -> " + Element->Base->getType().getAsString();
return PathDisplayStr;