|  | //===---- 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) | 
|  | Decls.insert(*Path->Decls.first); | 
|  |  | 
|  | NumDeclsFound = Decls.size(); | 
|  | DeclsFound = new NamedDecl * [NumDeclsFound]; | 
|  | std::copy(Decls.begin(), Decls.end(), DeclsFound); | 
|  | } | 
|  |  | 
|  | NamedDecl **BasePaths::found_decls_begin() { | 
|  | if (NumDeclsFound == 0) | 
|  | ComputeDeclsFound(); | 
|  | return DeclsFound; | 
|  | } | 
|  |  | 
|  | NamedDecl **BasePaths::found_decls_end() { | 
|  | if (NumDeclsFound == 0) | 
|  | ComputeDeclsFound(); | 
|  | 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() { | 
|  | Paths.clear(); | 
|  | ClassSubobjects.clear(); | 
|  | ScratchPath.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); | 
|  | 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); | 
|  | } | 
|  |  | 
|  | /// 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, | 
|  | /*DetectVirtual=*/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; | 
|  |  | 
|  | Paths.setOrigin(Derived); | 
|  | return LookupInBases(cast<CXXRecordDecl>(Derived->getAsRecordType()->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(); | 
|  |  | 
|  | // 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->getAsRecordType(); | 
|  | SetVirtual = true; | 
|  | } | 
|  | } else | 
|  | ++Subobjects.second; | 
|  |  | 
|  | 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; | 
|  | else | 
|  | Element.SubobjectNumber = Subobjects.second; | 
|  | Paths.ScratchPath.push_back(Element); | 
|  | } | 
|  |  | 
|  | CXXRecordDecl *BaseRecord | 
|  | = cast<CXXRecordDecl>(BaseSpec->getType()->getAsRecordType()->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; | 
|  | if (Criteria.LookupBase) { | 
|  | FoundPathToThisBase | 
|  | = (Context.getCanonicalType(BaseSpec->getType()) == Criteria.Base); | 
|  | } else { | 
|  | Paths.ScratchPath.Decls = BaseRecord->lookup(Context, Criteria.Name); | 
|  | while (Paths.ScratchPath.Decls.first != Paths.ScratchPath.Decls.second) { | 
|  | if (isAcceptableLookupResult(*Paths.ScratchPath.Decls.first, | 
|  | Criteria.NameKind, Criteria.IDNS)) { | 
|  | FoundPathToThisBase = true; | 
|  | break; | 
|  | } | 
|  | ++Paths.ScratchPath.Decls.first; | 
|  | } | 
|  | } | 
|  |  | 
|  | 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. | 
|  | Paths.Paths.push_back(Paths.ScratchPath); | 
|  | } else if (!Paths.isFindingAmbiguities()) { | 
|  | // We found a path and we don't care about ambiguities; | 
|  | // return immediately. | 
|  | return FoundPath; | 
|  | } | 
|  | } | 
|  | // 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. | 
|  | else if (VisitBase && LookupInBases(BaseRecord, Criteria, Paths)) { | 
|  | // 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()) | 
|  | Paths.ScratchPath.pop_back(); | 
|  | // 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. | 
|  | bool | 
|  | Sema::CheckDerivedToBaseConversion(QualType Derived, QualType Base, | 
|  | SourceLocation Loc, SourceRange Range) { | 
|  | // 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, | 
|  | /*DetectVirtual=*/false); | 
|  | bool DerivationOkay = IsDerivedFrom(Derived, Base, Paths); | 
|  | assert(DerivationOkay && | 
|  | "Can only be used with a derived-to-base conversion"); | 
|  | (void)DerivationOkay; | 
|  |  | 
|  | if (!Paths.isAmbiguous(Context.getCanonicalType(Base).getUnqualifiedType())) { | 
|  | // Check that the base class can be accessed. | 
|  | return CheckBaseClassAccess(Derived, Base, 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. | 
|  | Paths.clear(); | 
|  | Paths.setRecordingPaths(true); | 
|  | bool StillOkay = IsDerivedFrom(Derived, Base, Paths); | 
|  | assert(StillOkay && "Can only be used with a derived-to-base conversion"); | 
|  | (void)StillOkay; | 
|  |  | 
|  | // 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, diag::err_ambiguous_derived_to_base_conv) | 
|  | << Derived << Base << PathDisplayStr << Range; | 
|  | return true; | 
|  | } | 
|  |  | 
|  | /// @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; | 
|  | } |