Douglas Gregor | bc0805a | 2008-10-23 00:40:37 +0000 | [diff] [blame] | 1 | //===---- SemaInherit.cpp - C++ Inheritance ---------------------*- C++ -*-===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file provides Sema routines for C++ inheritance semantics, |
Anders Carlsson | 60d6b0d | 2009-03-27 04:43:36 +0000 | [diff] [blame] | 11 | // including searching the inheritance hierarchy. |
Douglas Gregor | bc0805a | 2008-10-23 00:40:37 +0000 | [diff] [blame] | 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 15 | #include "SemaInherit.h" |
Sebastian Redl | 7c8bd60 | 2009-02-07 20:10:22 +0000 | [diff] [blame] | 16 | #include "Sema.h" |
Douglas Gregor | bc0805a | 2008-10-23 00:40:37 +0000 | [diff] [blame] | 17 | #include "clang/AST/ASTContext.h" |
| 18 | #include "clang/AST/DeclCXX.h" |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 19 | #include "clang/AST/Type.h" |
| 20 | #include "clang/AST/TypeOrdering.h" |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 21 | #include <algorithm> |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 22 | #include <memory> |
| 23 | #include <set> |
| 24 | #include <string> |
Douglas Gregor | bc0805a | 2008-10-23 00:40:37 +0000 | [diff] [blame] | 25 | |
Douglas Gregor | 0575d4a | 2008-10-24 16:17:19 +0000 | [diff] [blame] | 26 | using namespace clang; |
Douglas Gregor | bc0805a | 2008-10-23 00:40:37 +0000 | [diff] [blame] | 27 | |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 28 | /// isAmbiguous - Determines whether the set of paths provided is |
| 29 | /// ambiguous, i.e., there are two or more paths that refer to |
| 30 | /// different base class subobjects of the same type. BaseType must be |
| 31 | /// an unqualified, canonical class type. |
| 32 | bool BasePaths::isAmbiguous(QualType BaseType) { |
Douglas Gregor | 0575d4a | 2008-10-24 16:17:19 +0000 | [diff] [blame] | 33 | assert(BaseType->isCanonical() && "Base type must be the canonical type"); |
| 34 | assert(BaseType.getCVRQualifiers() == 0 && "Base type must be unqualified"); |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 35 | std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType]; |
| 36 | return Subobjects.second + (Subobjects.first? 1 : 0) > 1; |
| 37 | } |
| 38 | |
| 39 | /// clear - Clear out all prior path information. |
| 40 | void BasePaths::clear() { |
| 41 | Paths.clear(); |
| 42 | ClassSubobjects.clear(); |
| 43 | ScratchPath.clear(); |
Sebastian Redl | 0777972 | 2008-10-31 14:43:28 +0000 | [diff] [blame] | 44 | DetectedVirtual = 0; |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 45 | } |
| 46 | |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 47 | /// @brief Swaps the contents of this BasePaths structure with the |
| 48 | /// contents of Other. |
| 49 | void BasePaths::swap(BasePaths &Other) { |
Douglas Gregor | 4dc6b1c | 2009-01-16 00:38:09 +0000 | [diff] [blame] | 50 | std::swap(Origin, Other.Origin); |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 51 | Paths.swap(Other.Paths); |
| 52 | ClassSubobjects.swap(Other.ClassSubobjects); |
| 53 | std::swap(FindAmbiguities, Other.FindAmbiguities); |
| 54 | std::swap(RecordPaths, Other.RecordPaths); |
| 55 | std::swap(DetectVirtual, Other.DetectVirtual); |
| 56 | std::swap(DetectedVirtual, Other.DetectedVirtual); |
| 57 | } |
| 58 | |
Douglas Gregor | 27c8dc0 | 2008-10-29 00:13:59 +0000 | [diff] [blame] | 59 | /// IsDerivedFrom - Determine whether the type Derived is derived from |
| 60 | /// the type Base, ignoring qualifiers on Base and Derived. This |
| 61 | /// routine does not assess whether an actual conversion from a |
| 62 | /// Derived* to a Base* is legal, because it does not account for |
| 63 | /// ambiguous conversions or conversions to private/protected bases. |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 64 | bool Sema::IsDerivedFrom(QualType Derived, QualType Base) { |
Sebastian Redl | 0777972 | 2008-10-31 14:43:28 +0000 | [diff] [blame] | 65 | BasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, |
| 66 | /*DetectVirtual=*/false); |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 67 | return IsDerivedFrom(Derived, Base, Paths); |
| 68 | } |
| 69 | |
Douglas Gregor | 27c8dc0 | 2008-10-29 00:13:59 +0000 | [diff] [blame] | 70 | /// IsDerivedFrom - Determine whether the type Derived is derived from |
| 71 | /// the type Base, ignoring qualifiers on Base and Derived. This |
| 72 | /// routine does not assess whether an actual conversion from a |
| 73 | /// Derived* to a Base* is legal, because it does not account for |
| 74 | /// ambiguous conversions or conversions to private/protected |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 75 | /// bases. This routine will use Paths to determine if there are |
| 76 | /// ambiguous paths (if @c Paths.isFindingAmbiguities()) and record |
Douglas Gregor | 27c8dc0 | 2008-10-29 00:13:59 +0000 | [diff] [blame] | 77 | /// information about all of the paths (if @c Paths.isRecordingPaths()). |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 78 | bool Sema::IsDerivedFrom(QualType Derived, QualType Base, BasePaths &Paths) { |
Douglas Gregor | bc0805a | 2008-10-23 00:40:37 +0000 | [diff] [blame] | 79 | Derived = Context.getCanonicalType(Derived).getUnqualifiedType(); |
| 80 | Base = Context.getCanonicalType(Base).getUnqualifiedType(); |
Sebastian Redl | 0777972 | 2008-10-31 14:43:28 +0000 | [diff] [blame] | 81 | |
Douglas Gregor | 27c8dc0 | 2008-10-29 00:13:59 +0000 | [diff] [blame] | 82 | if (!Derived->isRecordType() || !Base->isRecordType()) |
| 83 | return false; |
Douglas Gregor | bc0805a | 2008-10-23 00:40:37 +0000 | [diff] [blame] | 84 | |
| 85 | if (Derived == Base) |
| 86 | return false; |
| 87 | |
Douglas Gregor | 4dc6b1c | 2009-01-16 00:38:09 +0000 | [diff] [blame] | 88 | Paths.setOrigin(Derived); |
Douglas Gregor | c1efaec | 2009-02-28 01:32:25 +0000 | [diff] [blame] | 89 | return LookupInBases(cast<CXXRecordDecl>(Derived->getAsRecordType()->getDecl()), |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 90 | MemberLookupCriteria(Base), Paths); |
| 91 | } |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 92 | |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 93 | /// LookupInBases - Look for something that meets the specified |
| 94 | /// Criteria within the base classes of Class (or any of its base |
| 95 | /// classes, transitively). This routine populates BasePaths with the |
| 96 | /// list of paths that one can take to find the entity that meets the |
| 97 | /// search criteria, and returns true if any such entity is found. The |
| 98 | /// various options passed to the BasePath constructor will affect the |
| 99 | /// behavior of this lookup, e.g., whether it finds ambiguities, |
| 100 | /// records paths, or attempts to detect the use of virtual base |
| 101 | /// classes. |
| 102 | bool Sema::LookupInBases(CXXRecordDecl *Class, |
| 103 | const MemberLookupCriteria& Criteria, |
| 104 | BasePaths &Paths) { |
| 105 | bool FoundPath = false; |
| 106 | |
| 107 | for (CXXRecordDecl::base_class_const_iterator BaseSpec = Class->bases_begin(), |
| 108 | BaseSpecEnd = Class->bases_end(); |
| 109 | BaseSpec != BaseSpecEnd; ++BaseSpec) { |
| 110 | // Find the record of the base class subobjects for this type. |
| 111 | QualType BaseType = Context.getCanonicalType(BaseSpec->getType()); |
| 112 | BaseType = BaseType.getUnqualifiedType(); |
| 113 | |
| 114 | // Determine whether we need to visit this base class at all, |
| 115 | // updating the count of subobjects appropriately. |
| 116 | std::pair<bool, unsigned>& Subobjects = Paths.ClassSubobjects[BaseType]; |
| 117 | bool VisitBase = true; |
| 118 | bool SetVirtual = false; |
| 119 | if (BaseSpec->isVirtual()) { |
| 120 | VisitBase = !Subobjects.first; |
| 121 | Subobjects.first = true; |
| 122 | if (Paths.isDetectingVirtual() && Paths.DetectedVirtual == 0) { |
| 123 | // If this is the first virtual we find, remember it. If it turns out |
| 124 | // there is no base path here, we'll reset it later. |
Douglas Gregor | c1efaec | 2009-02-28 01:32:25 +0000 | [diff] [blame] | 125 | Paths.DetectedVirtual = BaseType->getAsRecordType(); |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 126 | SetVirtual = true; |
| 127 | } |
| 128 | } else |
| 129 | ++Subobjects.second; |
| 130 | |
| 131 | if (Paths.isRecordingPaths()) { |
| 132 | // Add this base specifier to the current path. |
| 133 | BasePathElement Element; |
| 134 | Element.Base = &*BaseSpec; |
Anders Carlsson | 77bd57c | 2009-03-27 18:54:29 +0000 | [diff] [blame^] | 135 | Element.Class = Class; |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 136 | if (BaseSpec->isVirtual()) |
| 137 | Element.SubobjectNumber = 0; |
| 138 | else |
| 139 | Element.SubobjectNumber = Subobjects.second; |
| 140 | Paths.ScratchPath.push_back(Element); |
| 141 | } |
| 142 | |
| 143 | CXXRecordDecl *BaseRecord |
| 144 | = cast<CXXRecordDecl>(BaseSpec->getType()->getAsRecordType()->getDecl()); |
| 145 | |
| 146 | // Either look at the base class type or look into the base class |
| 147 | // type to see if we've found a member that meets the search |
| 148 | // criteria. |
| 149 | bool FoundPathToThisBase = false; |
| 150 | if (Criteria.LookupBase) { |
| 151 | FoundPathToThisBase |
| 152 | = (Context.getCanonicalType(BaseSpec->getType()) == Criteria.Base); |
| 153 | } else { |
| 154 | Paths.ScratchPath.Decls = BaseRecord->lookup(Criteria.Name); |
| 155 | while (Paths.ScratchPath.Decls.first != Paths.ScratchPath.Decls.second) { |
Douglas Gregor | 4c921ae | 2009-01-30 01:04:22 +0000 | [diff] [blame] | 156 | if (isAcceptableLookupResult(*Paths.ScratchPath.Decls.first, |
| 157 | Criteria.NameKind, Criteria.IDNS)) { |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 158 | FoundPathToThisBase = true; |
| 159 | break; |
| 160 | } |
| 161 | ++Paths.ScratchPath.Decls.first; |
| 162 | } |
| 163 | } |
| 164 | |
| 165 | if (FoundPathToThisBase) { |
| 166 | // We've found a path that terminates that this base. |
| 167 | FoundPath = true; |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 168 | if (Paths.isRecordingPaths()) { |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 169 | // We have a path. Make a copy of it before moving on. |
| 170 | Paths.Paths.push_back(Paths.ScratchPath); |
| 171 | } else if (!Paths.isFindingAmbiguities()) { |
| 172 | // We found a path and we don't care about ambiguities; |
| 173 | // return immediately. |
| 174 | return FoundPath; |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 175 | } |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 176 | } |
| 177 | // C++ [class.member.lookup]p2: |
| 178 | // A member name f in one sub-object B hides a member name f in |
| 179 | // a sub-object A if A is a base class sub-object of B. Any |
| 180 | // declarations that are so hidden are eliminated from |
| 181 | // consideration. |
| 182 | else if (VisitBase && LookupInBases(BaseRecord, Criteria, Paths)) { |
| 183 | // There is a path to a base class that meets the criteria. If we're not |
| 184 | // collecting paths or finding ambiguities, we're done. |
| 185 | FoundPath = true; |
| 186 | if (!Paths.isFindingAmbiguities()) |
| 187 | return FoundPath; |
| 188 | } |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 189 | |
Douglas Gregor | 7176fff | 2009-01-15 00:26:24 +0000 | [diff] [blame] | 190 | // Pop this base specifier off the current path (if we're |
| 191 | // collecting paths). |
| 192 | if (Paths.isRecordingPaths()) |
| 193 | Paths.ScratchPath.pop_back(); |
| 194 | // If we set a virtual earlier, and this isn't a path, forget it again. |
| 195 | if (SetVirtual && !FoundPath) { |
| 196 | Paths.DetectedVirtual = 0; |
Douglas Gregor | bc0805a | 2008-10-23 00:40:37 +0000 | [diff] [blame] | 197 | } |
| 198 | } |
| 199 | |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 200 | return FoundPath; |
| 201 | } |
| 202 | |
| 203 | /// CheckDerivedToBaseConversion - Check whether the Derived-to-Base |
| 204 | /// conversion (where Derived and Base are class types) is |
| 205 | /// well-formed, meaning that the conversion is unambiguous (and |
Anders Carlsson | 29f006b | 2009-03-27 05:05:05 +0000 | [diff] [blame] | 206 | /// that all of the base classes are accessible). Returns true |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 207 | /// and emits a diagnostic if the code is ill-formed, returns false |
| 208 | /// otherwise. Loc is the location where this routine should point to |
| 209 | /// if there is an error, and Range is the source range to highlight |
| 210 | /// if there is an error. |
| 211 | bool |
Douglas Gregor | 0575d4a | 2008-10-24 16:17:19 +0000 | [diff] [blame] | 212 | Sema::CheckDerivedToBaseConversion(QualType Derived, QualType Base, |
| 213 | SourceLocation Loc, SourceRange Range) { |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 214 | // First, determine whether the path from Derived to Base is |
| 215 | // ambiguous. This is slightly more expensive than checking whether |
| 216 | // the Derived to Base conversion exists, because here we need to |
| 217 | // explore multiple paths to determine if there is an ambiguity. |
Anders Carlsson | 29f006b | 2009-03-27 05:05:05 +0000 | [diff] [blame] | 218 | BasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true, |
Sebastian Redl | 0777972 | 2008-10-31 14:43:28 +0000 | [diff] [blame] | 219 | /*DetectVirtual=*/false); |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 220 | bool DerivationOkay = IsDerivedFrom(Derived, Base, Paths); |
Sebastian Redl | 21593ac | 2009-01-28 18:33:18 +0000 | [diff] [blame] | 221 | assert(DerivationOkay && |
| 222 | "Can only be used with a derived-to-base conversion"); |
| 223 | (void)DerivationOkay; |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 224 | |
Anders Carlsson | 29f006b | 2009-03-27 05:05:05 +0000 | [diff] [blame] | 225 | if (!Paths.isAmbiguous(Context.getCanonicalType(Base).getUnqualifiedType())) { |
| 226 | // Check that the base class can be accessed. |
| 227 | return CheckBaseClassAccess(Derived, Base, Paths, Loc); |
| 228 | } |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 229 | |
Douglas Gregor | 0575d4a | 2008-10-24 16:17:19 +0000 | [diff] [blame] | 230 | // We know that the derived-to-base conversion is ambiguous, and |
| 231 | // we're going to produce a diagnostic. Perform the derived-to-base |
| 232 | // search just one more time to compute all of the possible paths so |
| 233 | // that we can print them out. This is more expensive than any of |
| 234 | // the previous derived-to-base checks we've done, but at this point |
| 235 | // performance isn't as much of an issue. |
| 236 | Paths.clear(); |
| 237 | Paths.setRecordingPaths(true); |
| 238 | bool StillOkay = IsDerivedFrom(Derived, Base, Paths); |
| 239 | assert(StillOkay && "Can only be used with a derived-to-base conversion"); |
Sebastian Redl | 21593ac | 2009-01-28 18:33:18 +0000 | [diff] [blame] | 240 | (void)StillOkay; |
Douglas Gregor | 0575d4a | 2008-10-24 16:17:19 +0000 | [diff] [blame] | 241 | |
| 242 | // Build up a textual representation of the ambiguous paths, e.g., |
| 243 | // D -> B -> A, that will be used to illustrate the ambiguous |
| 244 | // conversions in the diagnostic. We only print one of the paths |
| 245 | // to each base class subobject. |
Douglas Gregor | 4dc6b1c | 2009-01-16 00:38:09 +0000 | [diff] [blame] | 246 | std::string PathDisplayStr = getAmbiguousPathsDisplayString(Paths); |
| 247 | |
| 248 | Diag(Loc, diag::err_ambiguous_derived_to_base_conv) |
| 249 | << Derived << Base << PathDisplayStr << Range; |
| 250 | return true; |
| 251 | } |
| 252 | |
| 253 | /// @brief Builds a string representing ambiguous paths from a |
| 254 | /// specific derived class to different subobjects of the same base |
| 255 | /// class. |
| 256 | /// |
| 257 | /// This function builds a string that can be used in error messages |
| 258 | /// to show the different paths that one can take through the |
| 259 | /// inheritance hierarchy to go from the derived class to different |
| 260 | /// subobjects of a base class. The result looks something like this: |
| 261 | /// @code |
| 262 | /// struct D -> struct B -> struct A |
| 263 | /// struct D -> struct C -> struct A |
| 264 | /// @endcode |
| 265 | std::string Sema::getAmbiguousPathsDisplayString(BasePaths &Paths) { |
Douglas Gregor | 0575d4a | 2008-10-24 16:17:19 +0000 | [diff] [blame] | 266 | std::string PathDisplayStr; |
| 267 | std::set<unsigned> DisplayedPaths; |
| 268 | for (BasePaths::paths_iterator Path = Paths.begin(); |
| 269 | Path != Paths.end(); ++Path) { |
| 270 | if (DisplayedPaths.insert(Path->back().SubobjectNumber).second) { |
| 271 | // We haven't displayed a path to this particular base |
| 272 | // class subobject yet. |
| 273 | PathDisplayStr += "\n "; |
Douglas Gregor | 4dc6b1c | 2009-01-16 00:38:09 +0000 | [diff] [blame] | 274 | PathDisplayStr += Paths.getOrigin().getAsString(); |
Douglas Gregor | 0575d4a | 2008-10-24 16:17:19 +0000 | [diff] [blame] | 275 | for (BasePath::const_iterator Element = Path->begin(); |
| 276 | Element != Path->end(); ++Element) |
| 277 | PathDisplayStr += " -> " + Element->Base->getType().getAsString(); |
| 278 | } |
Douglas Gregor | 94b1dd2 | 2008-10-24 04:54:22 +0000 | [diff] [blame] | 279 | } |
Douglas Gregor | 4dc6b1c | 2009-01-16 00:38:09 +0000 | [diff] [blame] | 280 | |
| 281 | return PathDisplayStr; |
Douglas Gregor | bc0805a | 2008-10-23 00:40:37 +0000 | [diff] [blame] | 282 | } |