Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 1 | //===------ CXXInheritance.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 routines that help analyzing C++ inheritance hierarchies. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | #include "clang/AST/CXXInheritance.h" |
Anders Carlsson | 46170f9 | 2010-11-24 22:50:27 +0000 | [diff] [blame] | 14 | #include "clang/AST/RecordLayout.h" |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 15 | #include "clang/AST/DeclCXX.h" |
| 16 | #include <algorithm> |
| 17 | #include <set> |
| 18 | |
| 19 | using namespace clang; |
| 20 | |
| 21 | /// \brief Computes the set of declarations referenced by these base |
| 22 | /// paths. |
| 23 | void CXXBasePaths::ComputeDeclsFound() { |
| 24 | assert(NumDeclsFound == 0 && !DeclsFound && |
| 25 | "Already computed the set of declarations"); |
| 26 | |
| 27 | std::set<NamedDecl *> Decls; |
| 28 | for (CXXBasePaths::paths_iterator Path = begin(), PathEnd = end(); |
| 29 | Path != PathEnd; ++Path) |
| 30 | Decls.insert(*Path->Decls.first); |
| 31 | |
| 32 | NumDeclsFound = Decls.size(); |
| 33 | DeclsFound = new NamedDecl * [NumDeclsFound]; |
| 34 | std::copy(Decls.begin(), Decls.end(), DeclsFound); |
| 35 | } |
| 36 | |
| 37 | CXXBasePaths::decl_iterator CXXBasePaths::found_decls_begin() { |
| 38 | if (NumDeclsFound == 0) |
| 39 | ComputeDeclsFound(); |
| 40 | return DeclsFound; |
| 41 | } |
| 42 | |
| 43 | CXXBasePaths::decl_iterator CXXBasePaths::found_decls_end() { |
| 44 | if (NumDeclsFound == 0) |
| 45 | ComputeDeclsFound(); |
| 46 | return DeclsFound + NumDeclsFound; |
| 47 | } |
| 48 | |
| 49 | /// isAmbiguous - Determines whether the set of paths provided is |
| 50 | /// ambiguous, i.e., there are two or more paths that refer to |
| 51 | /// different base class subobjects of the same type. BaseType must be |
| 52 | /// an unqualified, canonical class type. |
Douglas Gregor | e0d5fe2 | 2010-05-21 20:29:55 +0000 | [diff] [blame] | 53 | bool CXXBasePaths::isAmbiguous(CanQualType BaseType) { |
| 54 | BaseType = BaseType.getUnqualifiedType(); |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 55 | std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType]; |
| 56 | return Subobjects.second + (Subobjects.first? 1 : 0) > 1; |
| 57 | } |
| 58 | |
| 59 | /// clear - Clear out all prior path information. |
| 60 | void CXXBasePaths::clear() { |
| 61 | Paths.clear(); |
| 62 | ClassSubobjects.clear(); |
| 63 | ScratchPath.clear(); |
| 64 | DetectedVirtual = 0; |
| 65 | } |
| 66 | |
| 67 | /// @brief Swaps the contents of this CXXBasePaths structure with the |
| 68 | /// contents of Other. |
| 69 | void CXXBasePaths::swap(CXXBasePaths &Other) { |
| 70 | std::swap(Origin, Other.Origin); |
| 71 | Paths.swap(Other.Paths); |
| 72 | ClassSubobjects.swap(Other.ClassSubobjects); |
| 73 | std::swap(FindAmbiguities, Other.FindAmbiguities); |
| 74 | std::swap(RecordPaths, Other.RecordPaths); |
| 75 | std::swap(DetectVirtual, Other.DetectVirtual); |
| 76 | std::swap(DetectedVirtual, Other.DetectedVirtual); |
| 77 | } |
| 78 | |
John McCall | d89d30f | 2011-01-28 22:02:36 +0000 | [diff] [blame] | 79 | bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const { |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 80 | CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, |
| 81 | /*DetectVirtual=*/false); |
| 82 | return isDerivedFrom(Base, Paths); |
| 83 | } |
| 84 | |
John McCall | d89d30f | 2011-01-28 22:02:36 +0000 | [diff] [blame] | 85 | bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base, |
| 86 | CXXBasePaths &Paths) const { |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 87 | if (getCanonicalDecl() == Base->getCanonicalDecl()) |
| 88 | return false; |
| 89 | |
John McCall | af8e6ed | 2009-11-12 03:15:40 +0000 | [diff] [blame] | 90 | Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); |
John McCall | d89d30f | 2011-01-28 22:02:36 +0000 | [diff] [blame] | 91 | return lookupInBases(&FindBaseClass, |
| 92 | const_cast<CXXRecordDecl*>(Base->getCanonicalDecl()), |
| 93 | Paths); |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 94 | } |
| 95 | |
Douglas Gregor | 4e6ba4b | 2010-03-03 04:38:46 +0000 | [diff] [blame] | 96 | bool CXXRecordDecl::isVirtuallyDerivedFrom(CXXRecordDecl *Base) const { |
Anders Carlsson | 1c4c397 | 2010-06-04 01:40:08 +0000 | [diff] [blame] | 97 | if (!getNumVBases()) |
| 98 | return false; |
| 99 | |
Douglas Gregor | 4e6ba4b | 2010-03-03 04:38:46 +0000 | [diff] [blame] | 100 | CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, |
| 101 | /*DetectVirtual=*/false); |
| 102 | |
| 103 | if (getCanonicalDecl() == Base->getCanonicalDecl()) |
| 104 | return false; |
| 105 | |
| 106 | Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); |
| 107 | return lookupInBases(&FindVirtualBaseClass, Base->getCanonicalDecl(), Paths); |
| 108 | } |
| 109 | |
John McCall | e8174bc | 2009-12-08 07:42:38 +0000 | [diff] [blame] | 110 | static bool BaseIsNot(const CXXRecordDecl *Base, void *OpaqueTarget) { |
| 111 | // OpaqueTarget is a CXXRecordDecl*. |
| 112 | return Base->getCanonicalDecl() != (const CXXRecordDecl*) OpaqueTarget; |
| 113 | } |
| 114 | |
| 115 | bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const { |
| 116 | return forallBases(BaseIsNot, (void*) Base->getCanonicalDecl()); |
| 117 | } |
| 118 | |
| 119 | bool CXXRecordDecl::forallBases(ForallBasesCallback *BaseMatches, |
| 120 | void *OpaqueData, |
| 121 | bool AllowShortCircuit) const { |
Chris Lattner | 5f9e272 | 2011-07-23 10:55:15 +0000 | [diff] [blame] | 122 | SmallVector<const CXXRecordDecl*, 8> Queue; |
John McCall | e8174bc | 2009-12-08 07:42:38 +0000 | [diff] [blame] | 123 | |
| 124 | const CXXRecordDecl *Record = this; |
| 125 | bool AllMatches = true; |
| 126 | while (true) { |
| 127 | for (CXXRecordDecl::base_class_const_iterator |
| 128 | I = Record->bases_begin(), E = Record->bases_end(); I != E; ++I) { |
| 129 | const RecordType *Ty = I->getType()->getAs<RecordType>(); |
| 130 | if (!Ty) { |
| 131 | if (AllowShortCircuit) return false; |
| 132 | AllMatches = false; |
| 133 | continue; |
| 134 | } |
| 135 | |
Anders Carlsson | ca910e8 | 2009-12-09 04:26:02 +0000 | [diff] [blame] | 136 | CXXRecordDecl *Base = |
Douglas Gregor | 952b017 | 2010-02-11 01:04:33 +0000 | [diff] [blame] | 137 | cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition()); |
John McCall | e8174bc | 2009-12-08 07:42:38 +0000 | [diff] [blame] | 138 | if (!Base) { |
| 139 | if (AllowShortCircuit) return false; |
| 140 | AllMatches = false; |
| 141 | continue; |
| 142 | } |
| 143 | |
Anders Carlsson | ca910e8 | 2009-12-09 04:26:02 +0000 | [diff] [blame] | 144 | Queue.push_back(Base); |
| 145 | if (!BaseMatches(Base, OpaqueData)) { |
John McCall | e8174bc | 2009-12-08 07:42:38 +0000 | [diff] [blame] | 146 | if (AllowShortCircuit) return false; |
| 147 | AllMatches = false; |
| 148 | continue; |
| 149 | } |
| 150 | } |
| 151 | |
| 152 | if (Queue.empty()) break; |
| 153 | Record = Queue.back(); // not actually a queue. |
| 154 | Queue.pop_back(); |
| 155 | } |
| 156 | |
| 157 | return AllMatches; |
| 158 | } |
| 159 | |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 160 | bool CXXBasePaths::lookupInBases(ASTContext &Context, |
| 161 | const CXXRecordDecl *Record, |
| 162 | CXXRecordDecl::BaseMatchesCallback *BaseMatches, |
| 163 | void *UserData) { |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 164 | bool FoundPath = false; |
John McCall | 46460a6 | 2010-01-20 21:53:11 +0000 | [diff] [blame] | 165 | |
John McCall | 92f8831 | 2010-01-23 00:46:32 +0000 | [diff] [blame] | 166 | // The access of the path down to this record. |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 167 | AccessSpecifier AccessToHere = ScratchPath.Access; |
| 168 | bool IsFirstStep = ScratchPath.empty(); |
John McCall | 92f8831 | 2010-01-23 00:46:32 +0000 | [diff] [blame] | 169 | |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 170 | for (CXXRecordDecl::base_class_const_iterator BaseSpec = Record->bases_begin(), |
| 171 | BaseSpecEnd = Record->bases_end(); |
| 172 | BaseSpec != BaseSpecEnd; |
| 173 | ++BaseSpec) { |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 174 | // Find the record of the base class subobjects for this type. |
Douglas Gregor | a4923eb | 2009-11-16 21:35:15 +0000 | [diff] [blame] | 175 | QualType BaseType = Context.getCanonicalType(BaseSpec->getType()) |
| 176 | .getUnqualifiedType(); |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 177 | |
| 178 | // C++ [temp.dep]p3: |
| 179 | // In the definition of a class template or a member of a class template, |
| 180 | // if a base class of the class template depends on a template-parameter, |
| 181 | // the base class scope is not examined during unqualified name lookup |
| 182 | // either at the point of definition of the class template or member or |
| 183 | // during an instantiation of the class tem- plate or member. |
| 184 | if (BaseType->isDependentType()) |
| 185 | continue; |
| 186 | |
| 187 | // Determine whether we need to visit this base class at all, |
| 188 | // updating the count of subobjects appropriately. |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 189 | std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType]; |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 190 | bool VisitBase = true; |
| 191 | bool SetVirtual = false; |
| 192 | if (BaseSpec->isVirtual()) { |
| 193 | VisitBase = !Subobjects.first; |
| 194 | Subobjects.first = true; |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 195 | if (isDetectingVirtual() && DetectedVirtual == 0) { |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 196 | // If this is the first virtual we find, remember it. If it turns out |
| 197 | // there is no base path here, we'll reset it later. |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 198 | DetectedVirtual = BaseType->getAs<RecordType>(); |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 199 | SetVirtual = true; |
| 200 | } |
| 201 | } else |
| 202 | ++Subobjects.second; |
| 203 | |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 204 | if (isRecordingPaths()) { |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 205 | // Add this base specifier to the current path. |
| 206 | CXXBasePathElement Element; |
| 207 | Element.Base = &*BaseSpec; |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 208 | Element.Class = Record; |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 209 | if (BaseSpec->isVirtual()) |
| 210 | Element.SubobjectNumber = 0; |
| 211 | else |
| 212 | Element.SubobjectNumber = Subobjects.second; |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 213 | ScratchPath.push_back(Element); |
John McCall | 46460a6 | 2010-01-20 21:53:11 +0000 | [diff] [blame] | 214 | |
John McCall | 92f8831 | 2010-01-23 00:46:32 +0000 | [diff] [blame] | 215 | // Calculate the "top-down" access to this base class. |
| 216 | // The spec actually describes this bottom-up, but top-down is |
| 217 | // equivalent because the definition works out as follows: |
| 218 | // 1. Write down the access along each step in the inheritance |
| 219 | // chain, followed by the access of the decl itself. |
| 220 | // For example, in |
| 221 | // class A { public: int foo; }; |
| 222 | // class B : protected A {}; |
| 223 | // class C : public B {}; |
| 224 | // class D : private C {}; |
| 225 | // we would write: |
| 226 | // private public protected public |
| 227 | // 2. If 'private' appears anywhere except far-left, access is denied. |
| 228 | // 3. Otherwise, overall access is determined by the most restrictive |
| 229 | // access in the sequence. |
| 230 | if (IsFirstStep) |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 231 | ScratchPath.Access = BaseSpec->getAccessSpecifier(); |
John McCall | 92f8831 | 2010-01-23 00:46:32 +0000 | [diff] [blame] | 232 | else |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 233 | ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere, |
| 234 | BaseSpec->getAccessSpecifier()); |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 235 | } |
John McCall | ed814cc | 2010-02-09 00:57:12 +0000 | [diff] [blame] | 236 | |
| 237 | // Track whether there's a path involving this specific base. |
| 238 | bool FoundPathThroughBase = false; |
| 239 | |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 240 | if (BaseMatches(BaseSpec, ScratchPath, UserData)) { |
John McCall | 92f8831 | 2010-01-23 00:46:32 +0000 | [diff] [blame] | 241 | // We've found a path that terminates at this base. |
John McCall | ed814cc | 2010-02-09 00:57:12 +0000 | [diff] [blame] | 242 | FoundPath = FoundPathThroughBase = true; |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 243 | if (isRecordingPaths()) { |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 244 | // We have a path. Make a copy of it before moving on. |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 245 | Paths.push_back(ScratchPath); |
| 246 | } else if (!isFindingAmbiguities()) { |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 247 | // We found a path and we don't care about ambiguities; |
| 248 | // return immediately. |
| 249 | return FoundPath; |
| 250 | } |
| 251 | } else if (VisitBase) { |
| 252 | CXXRecordDecl *BaseRecord |
| 253 | = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>() |
| 254 | ->getDecl()); |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 255 | if (lookupInBases(Context, BaseRecord, BaseMatches, UserData)) { |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 256 | // C++ [class.member.lookup]p2: |
| 257 | // A member name f in one sub-object B hides a member name f in |
| 258 | // a sub-object A if A is a base class sub-object of B. Any |
| 259 | // declarations that are so hidden are eliminated from |
| 260 | // consideration. |
| 261 | |
| 262 | // There is a path to a base class that meets the criteria. If we're |
| 263 | // not collecting paths or finding ambiguities, we're done. |
John McCall | ed814cc | 2010-02-09 00:57:12 +0000 | [diff] [blame] | 264 | FoundPath = FoundPathThroughBase = true; |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 265 | if (!isFindingAmbiguities()) |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 266 | return FoundPath; |
| 267 | } |
| 268 | } |
| 269 | |
| 270 | // Pop this base specifier off the current path (if we're |
| 271 | // collecting paths). |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 272 | if (isRecordingPaths()) { |
| 273 | ScratchPath.pop_back(); |
John McCall | 46460a6 | 2010-01-20 21:53:11 +0000 | [diff] [blame] | 274 | } |
| 275 | |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 276 | // If we set a virtual earlier, and this isn't a path, forget it again. |
John McCall | ed814cc | 2010-02-09 00:57:12 +0000 | [diff] [blame] | 277 | if (SetVirtual && !FoundPathThroughBase) { |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 278 | DetectedVirtual = 0; |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 279 | } |
| 280 | } |
John McCall | 92f8831 | 2010-01-23 00:46:32 +0000 | [diff] [blame] | 281 | |
| 282 | // Reset the scratch path access. |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 283 | ScratchPath.Access = AccessToHere; |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 284 | |
| 285 | return FoundPath; |
| 286 | } |
| 287 | |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 288 | bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches, |
| 289 | void *UserData, |
| 290 | CXXBasePaths &Paths) const { |
Douglas Gregor | 4e6ba4b | 2010-03-03 04:38:46 +0000 | [diff] [blame] | 291 | // If we didn't find anything, report that. |
| 292 | if (!Paths.lookupInBases(getASTContext(), this, BaseMatches, UserData)) |
| 293 | return false; |
| 294 | |
| 295 | // If we're not recording paths or we won't ever find ambiguities, |
| 296 | // we're done. |
| 297 | if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities()) |
| 298 | return true; |
| 299 | |
| 300 | // C++ [class.member.lookup]p6: |
| 301 | // When virtual base classes are used, a hidden declaration can be |
| 302 | // reached along a path through the sub-object lattice that does |
| 303 | // not pass through the hiding declaration. This is not an |
| 304 | // ambiguity. The identical use with nonvirtual base classes is an |
| 305 | // ambiguity; in that case there is no unique instance of the name |
| 306 | // that hides all the others. |
| 307 | // |
| 308 | // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy |
| 309 | // way to make it any faster. |
| 310 | for (CXXBasePaths::paths_iterator P = Paths.begin(), PEnd = Paths.end(); |
| 311 | P != PEnd; /* increment in loop */) { |
| 312 | bool Hidden = false; |
| 313 | |
| 314 | for (CXXBasePath::iterator PE = P->begin(), PEEnd = P->end(); |
| 315 | PE != PEEnd && !Hidden; ++PE) { |
| 316 | if (PE->Base->isVirtual()) { |
| 317 | CXXRecordDecl *VBase = 0; |
| 318 | if (const RecordType *Record = PE->Base->getType()->getAs<RecordType>()) |
| 319 | VBase = cast<CXXRecordDecl>(Record->getDecl()); |
| 320 | if (!VBase) |
| 321 | break; |
| 322 | |
| 323 | // The declaration(s) we found along this path were found in a |
| 324 | // subobject of a virtual base. Check whether this virtual |
| 325 | // base is a subobject of any other path; if so, then the |
| 326 | // declaration in this path are hidden by that patch. |
| 327 | for (CXXBasePaths::paths_iterator HidingP = Paths.begin(), |
| 328 | HidingPEnd = Paths.end(); |
| 329 | HidingP != HidingPEnd; |
| 330 | ++HidingP) { |
| 331 | CXXRecordDecl *HidingClass = 0; |
| 332 | if (const RecordType *Record |
| 333 | = HidingP->back().Base->getType()->getAs<RecordType>()) |
| 334 | HidingClass = cast<CXXRecordDecl>(Record->getDecl()); |
| 335 | if (!HidingClass) |
| 336 | break; |
| 337 | |
| 338 | if (HidingClass->isVirtuallyDerivedFrom(VBase)) { |
| 339 | Hidden = true; |
| 340 | break; |
| 341 | } |
| 342 | } |
| 343 | } |
| 344 | } |
| 345 | |
| 346 | if (Hidden) |
| 347 | P = Paths.Paths.erase(P); |
| 348 | else |
| 349 | ++P; |
| 350 | } |
| 351 | |
| 352 | return true; |
Douglas Gregor | 89b7702 | 2010-03-03 02:18:00 +0000 | [diff] [blame] | 353 | } |
| 354 | |
John McCall | af8e6ed | 2009-11-12 03:15:40 +0000 | [diff] [blame] | 355 | bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier, |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 356 | CXXBasePath &Path, |
| 357 | void *BaseRecord) { |
| 358 | assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord && |
| 359 | "User data for FindBaseClass is not canonical!"); |
| 360 | return Specifier->getType()->getAs<RecordType>()->getDecl() |
| 361 | ->getCanonicalDecl() == BaseRecord; |
| 362 | } |
| 363 | |
Douglas Gregor | 4e6ba4b | 2010-03-03 04:38:46 +0000 | [diff] [blame] | 364 | bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier, |
| 365 | CXXBasePath &Path, |
| 366 | void *BaseRecord) { |
| 367 | assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord && |
| 368 | "User data for FindBaseClass is not canonical!"); |
| 369 | return Specifier->isVirtual() && |
| 370 | Specifier->getType()->getAs<RecordType>()->getDecl() |
| 371 | ->getCanonicalDecl() == BaseRecord; |
| 372 | } |
| 373 | |
John McCall | af8e6ed | 2009-11-12 03:15:40 +0000 | [diff] [blame] | 374 | bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier, |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 375 | CXXBasePath &Path, |
| 376 | void *Name) { |
| 377 | RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); |
| 378 | |
| 379 | DeclarationName N = DeclarationName::getFromOpaquePtr(Name); |
| 380 | for (Path.Decls = BaseRecord->lookup(N); |
| 381 | Path.Decls.first != Path.Decls.second; |
| 382 | ++Path.Decls.first) { |
| 383 | if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) |
| 384 | return true; |
| 385 | } |
| 386 | |
| 387 | return false; |
| 388 | } |
| 389 | |
John McCall | af8e6ed | 2009-11-12 03:15:40 +0000 | [diff] [blame] | 390 | bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier, |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 391 | CXXBasePath &Path, |
| 392 | void *Name) { |
| 393 | RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); |
| 394 | |
| 395 | const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member; |
| 396 | DeclarationName N = DeclarationName::getFromOpaquePtr(Name); |
| 397 | for (Path.Decls = BaseRecord->lookup(N); |
| 398 | Path.Decls.first != Path.Decls.second; |
| 399 | ++Path.Decls.first) { |
| 400 | if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS)) |
| 401 | return true; |
| 402 | } |
| 403 | |
| 404 | return false; |
| 405 | } |
| 406 | |
John McCall | af8e6ed | 2009-11-12 03:15:40 +0000 | [diff] [blame] | 407 | bool CXXRecordDecl:: |
| 408 | FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier, |
| 409 | CXXBasePath &Path, |
| 410 | void *Name) { |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 411 | RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); |
| 412 | |
| 413 | DeclarationName N = DeclarationName::getFromOpaquePtr(Name); |
| 414 | for (Path.Decls = BaseRecord->lookup(N); |
| 415 | Path.Decls.first != Path.Decls.second; |
| 416 | ++Path.Decls.first) { |
| 417 | // FIXME: Refactor the "is it a nested-name-specifier?" check |
Richard Smith | 162e1c1 | 2011-04-15 14:24:37 +0000 | [diff] [blame] | 418 | if (isa<TypedefNameDecl>(*Path.Decls.first) || |
Douglas Gregor | a8f32e0 | 2009-10-06 17:59:45 +0000 | [diff] [blame] | 419 | (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) |
| 420 | return true; |
| 421 | } |
| 422 | |
| 423 | return false; |
Mike Stump | 82109bd | 2009-10-06 23:38:59 +0000 | [diff] [blame] | 424 | } |
Douglas Gregor | 7b2fc9d | 2010-03-23 23:47:56 +0000 | [diff] [blame] | 425 | |
| 426 | void OverridingMethods::add(unsigned OverriddenSubobject, |
| 427 | UniqueVirtualMethod Overriding) { |
Chris Lattner | 5f9e272 | 2011-07-23 10:55:15 +0000 | [diff] [blame] | 428 | SmallVector<UniqueVirtualMethod, 4> &SubobjectOverrides |
Douglas Gregor | 7b2fc9d | 2010-03-23 23:47:56 +0000 | [diff] [blame] | 429 | = Overrides[OverriddenSubobject]; |
| 430 | if (std::find(SubobjectOverrides.begin(), SubobjectOverrides.end(), |
| 431 | Overriding) == SubobjectOverrides.end()) |
| 432 | SubobjectOverrides.push_back(Overriding); |
| 433 | } |
| 434 | |
| 435 | void OverridingMethods::add(const OverridingMethods &Other) { |
| 436 | for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I) { |
| 437 | for (overriding_const_iterator M = I->second.begin(), |
| 438 | MEnd = I->second.end(); |
| 439 | M != MEnd; |
| 440 | ++M) |
| 441 | add(I->first, *M); |
| 442 | } |
| 443 | } |
| 444 | |
| 445 | void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) { |
| 446 | for (iterator I = begin(), IEnd = end(); I != IEnd; ++I) { |
| 447 | I->second.clear(); |
| 448 | I->second.push_back(Overriding); |
| 449 | } |
| 450 | } |
| 451 | |
| 452 | |
| 453 | namespace { |
| 454 | class FinalOverriderCollector { |
| 455 | /// \brief The number of subobjects of a given class type that |
| 456 | /// occur within the class hierarchy. |
| 457 | llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount; |
| 458 | |
| 459 | /// \brief Overriders for each virtual base subobject. |
| 460 | llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders; |
| 461 | |
| 462 | CXXFinalOverriderMap FinalOverriders; |
| 463 | |
| 464 | public: |
| 465 | ~FinalOverriderCollector(); |
| 466 | |
| 467 | void Collect(const CXXRecordDecl *RD, bool VirtualBase, |
| 468 | const CXXRecordDecl *InVirtualSubobject, |
| 469 | CXXFinalOverriderMap &Overriders); |
| 470 | }; |
| 471 | } |
| 472 | |
| 473 | void FinalOverriderCollector::Collect(const CXXRecordDecl *RD, |
| 474 | bool VirtualBase, |
| 475 | const CXXRecordDecl *InVirtualSubobject, |
| 476 | CXXFinalOverriderMap &Overriders) { |
| 477 | unsigned SubobjectNumber = 0; |
| 478 | if (!VirtualBase) |
| 479 | SubobjectNumber |
| 480 | = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())]; |
| 481 | |
| 482 | for (CXXRecordDecl::base_class_const_iterator Base = RD->bases_begin(), |
| 483 | BaseEnd = RD->bases_end(); Base != BaseEnd; ++Base) { |
| 484 | if (const RecordType *RT = Base->getType()->getAs<RecordType>()) { |
| 485 | const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl()); |
| 486 | if (!BaseDecl->isPolymorphic()) |
| 487 | continue; |
| 488 | |
| 489 | if (Overriders.empty() && !Base->isVirtual()) { |
| 490 | // There are no other overriders of virtual member functions, |
| 491 | // so let the base class fill in our overriders for us. |
| 492 | Collect(BaseDecl, false, InVirtualSubobject, Overriders); |
| 493 | continue; |
| 494 | } |
| 495 | |
| 496 | // Collect all of the overridders from the base class subobject |
| 497 | // and merge them into the set of overridders for this class. |
| 498 | // For virtual base classes, populate or use the cached virtual |
| 499 | // overrides so that we do not walk the virtual base class (and |
| 500 | // its base classes) more than once. |
| 501 | CXXFinalOverriderMap ComputedBaseOverriders; |
| 502 | CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders; |
| 503 | if (Base->isVirtual()) { |
| 504 | CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl]; |
| 505 | if (!MyVirtualOverriders) { |
| 506 | MyVirtualOverriders = new CXXFinalOverriderMap; |
| 507 | Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders); |
| 508 | } |
| 509 | |
| 510 | BaseOverriders = MyVirtualOverriders; |
| 511 | } else |
| 512 | Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders); |
| 513 | |
| 514 | // Merge the overriders from this base class into our own set of |
| 515 | // overriders. |
| 516 | for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(), |
| 517 | OMEnd = BaseOverriders->end(); |
| 518 | OM != OMEnd; |
| 519 | ++OM) { |
| 520 | const CXXMethodDecl *CanonOM |
| 521 | = cast<CXXMethodDecl>(OM->first->getCanonicalDecl()); |
| 522 | Overriders[CanonOM].add(OM->second); |
| 523 | } |
| 524 | } |
| 525 | } |
| 526 | |
| 527 | for (CXXRecordDecl::method_iterator M = RD->method_begin(), |
| 528 | MEnd = RD->method_end(); |
| 529 | M != MEnd; |
| 530 | ++M) { |
| 531 | // We only care about virtual methods. |
| 532 | if (!M->isVirtual()) |
| 533 | continue; |
| 534 | |
| 535 | CXXMethodDecl *CanonM = cast<CXXMethodDecl>(M->getCanonicalDecl()); |
| 536 | |
| 537 | if (CanonM->begin_overridden_methods() |
| 538 | == CanonM->end_overridden_methods()) { |
| 539 | // This is a new virtual function that does not override any |
| 540 | // other virtual function. Add it to the map of virtual |
| 541 | // functions for which we are tracking overridders. |
| 542 | |
| 543 | // C++ [class.virtual]p2: |
| 544 | // For convenience we say that any virtual function overrides itself. |
| 545 | Overriders[CanonM].add(SubobjectNumber, |
| 546 | UniqueVirtualMethod(CanonM, SubobjectNumber, |
| 547 | InVirtualSubobject)); |
| 548 | continue; |
| 549 | } |
| 550 | |
| 551 | // This virtual method overrides other virtual methods, so it does |
| 552 | // not add any new slots into the set of overriders. Instead, we |
| 553 | // replace entries in the set of overriders with the new |
| 554 | // overrider. To do so, we dig down to the original virtual |
| 555 | // functions using data recursion and update all of the methods it |
| 556 | // overrides. |
| 557 | typedef std::pair<CXXMethodDecl::method_iterator, |
| 558 | CXXMethodDecl::method_iterator> OverriddenMethods; |
Chris Lattner | 5f9e272 | 2011-07-23 10:55:15 +0000 | [diff] [blame] | 559 | SmallVector<OverriddenMethods, 4> Stack; |
Douglas Gregor | 7b2fc9d | 2010-03-23 23:47:56 +0000 | [diff] [blame] | 560 | Stack.push_back(std::make_pair(CanonM->begin_overridden_methods(), |
| 561 | CanonM->end_overridden_methods())); |
| 562 | while (!Stack.empty()) { |
| 563 | OverriddenMethods OverMethods = Stack.back(); |
| 564 | Stack.pop_back(); |
| 565 | |
| 566 | for (; OverMethods.first != OverMethods.second; ++OverMethods.first) { |
| 567 | const CXXMethodDecl *CanonOM |
| 568 | = cast<CXXMethodDecl>((*OverMethods.first)->getCanonicalDecl()); |
Anders Carlsson | ffdb2d2 | 2010-06-03 01:00:02 +0000 | [diff] [blame] | 569 | |
| 570 | // C++ [class.virtual]p2: |
| 571 | // A virtual member function C::vf of a class object S is |
| 572 | // a final overrider unless the most derived class (1.8) |
| 573 | // of which S is a base class subobject (if any) declares |
| 574 | // or inherits another member function that overrides vf. |
| 575 | // |
| 576 | // Treating this object like the most derived class, we |
| 577 | // replace any overrides from base classes with this |
| 578 | // overriding virtual function. |
| 579 | Overriders[CanonOM].replaceAll( |
| 580 | UniqueVirtualMethod(CanonM, SubobjectNumber, |
| 581 | InVirtualSubobject)); |
| 582 | |
Douglas Gregor | 7b2fc9d | 2010-03-23 23:47:56 +0000 | [diff] [blame] | 583 | if (CanonOM->begin_overridden_methods() |
Anders Carlsson | ffdb2d2 | 2010-06-03 01:00:02 +0000 | [diff] [blame] | 584 | == CanonOM->end_overridden_methods()) |
Douglas Gregor | 7b2fc9d | 2010-03-23 23:47:56 +0000 | [diff] [blame] | 585 | continue; |
Douglas Gregor | 7b2fc9d | 2010-03-23 23:47:56 +0000 | [diff] [blame] | 586 | |
| 587 | // Continue recursion to the methods that this virtual method |
| 588 | // overrides. |
| 589 | Stack.push_back(std::make_pair(CanonOM->begin_overridden_methods(), |
| 590 | CanonOM->end_overridden_methods())); |
| 591 | } |
| 592 | } |
Anders Carlsson | ffdb2d2 | 2010-06-03 01:00:02 +0000 | [diff] [blame] | 593 | |
| 594 | // C++ [class.virtual]p2: |
| 595 | // For convenience we say that any virtual function overrides itself. |
| 596 | Overriders[CanonM].add(SubobjectNumber, |
| 597 | UniqueVirtualMethod(CanonM, SubobjectNumber, |
| 598 | InVirtualSubobject)); |
Douglas Gregor | 7b2fc9d | 2010-03-23 23:47:56 +0000 | [diff] [blame] | 599 | } |
| 600 | } |
| 601 | |
| 602 | FinalOverriderCollector::~FinalOverriderCollector() { |
| 603 | for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator |
| 604 | VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end(); |
| 605 | VO != VOEnd; |
| 606 | ++VO) |
| 607 | delete VO->second; |
| 608 | } |
| 609 | |
| 610 | void |
| 611 | CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const { |
| 612 | FinalOverriderCollector Collector; |
| 613 | Collector.Collect(this, false, 0, FinalOverriders); |
| 614 | |
| 615 | // Weed out any final overriders that come from virtual base class |
| 616 | // subobjects that were hidden by other subobjects along any path. |
| 617 | // This is the final-overrider variant of C++ [class.member.lookup]p10. |
| 618 | for (CXXFinalOverriderMap::iterator OM = FinalOverriders.begin(), |
| 619 | OMEnd = FinalOverriders.end(); |
| 620 | OM != OMEnd; |
| 621 | ++OM) { |
| 622 | for (OverridingMethods::iterator SO = OM->second.begin(), |
| 623 | SOEnd = OM->second.end(); |
| 624 | SO != SOEnd; |
| 625 | ++SO) { |
Chris Lattner | 5f9e272 | 2011-07-23 10:55:15 +0000 | [diff] [blame] | 626 | SmallVector<UniqueVirtualMethod, 4> &Overriding = SO->second; |
Douglas Gregor | 7b2fc9d | 2010-03-23 23:47:56 +0000 | [diff] [blame] | 627 | if (Overriding.size() < 2) |
| 628 | continue; |
| 629 | |
Chris Lattner | 5f9e272 | 2011-07-23 10:55:15 +0000 | [diff] [blame] | 630 | for (SmallVector<UniqueVirtualMethod, 4>::iterator |
Douglas Gregor | 7b2fc9d | 2010-03-23 23:47:56 +0000 | [diff] [blame] | 631 | Pos = Overriding.begin(), PosEnd = Overriding.end(); |
| 632 | Pos != PosEnd; |
| 633 | /* increment in loop */) { |
| 634 | if (!Pos->InVirtualSubobject) { |
| 635 | ++Pos; |
| 636 | continue; |
| 637 | } |
| 638 | |
| 639 | // We have an overriding method in a virtual base class |
| 640 | // subobject (or non-virtual base class subobject thereof); |
| 641 | // determine whether there exists an other overriding method |
| 642 | // in a base class subobject that hides the virtual base class |
| 643 | // subobject. |
| 644 | bool Hidden = false; |
Chris Lattner | 5f9e272 | 2011-07-23 10:55:15 +0000 | [diff] [blame] | 645 | for (SmallVector<UniqueVirtualMethod, 4>::iterator |
Douglas Gregor | 7b2fc9d | 2010-03-23 23:47:56 +0000 | [diff] [blame] | 646 | OP = Overriding.begin(), OPEnd = Overriding.end(); |
| 647 | OP != OPEnd && !Hidden; |
| 648 | ++OP) { |
| 649 | if (Pos == OP) |
| 650 | continue; |
| 651 | |
| 652 | if (OP->Method->getParent()->isVirtuallyDerivedFrom( |
| 653 | const_cast<CXXRecordDecl *>(Pos->InVirtualSubobject))) |
| 654 | Hidden = true; |
| 655 | } |
| 656 | |
| 657 | if (Hidden) { |
| 658 | // The current overriding function is hidden by another |
| 659 | // overriding function; remove this one. |
| 660 | Pos = Overriding.erase(Pos); |
| 661 | PosEnd = Overriding.end(); |
| 662 | } else { |
| 663 | ++Pos; |
| 664 | } |
| 665 | } |
| 666 | } |
| 667 | } |
| 668 | } |
Anders Carlsson | 46170f9 | 2010-11-24 22:50:27 +0000 | [diff] [blame] | 669 | |
| 670 | static void |
| 671 | AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context, |
| 672 | CXXIndirectPrimaryBaseSet& Bases) { |
| 673 | // If the record has a virtual primary base class, add it to our set. |
| 674 | const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); |
Anders Carlsson | c9e814b | 2010-11-24 23:12:57 +0000 | [diff] [blame] | 675 | if (Layout.isPrimaryBaseVirtual()) |
Anders Carlsson | 46170f9 | 2010-11-24 22:50:27 +0000 | [diff] [blame] | 676 | Bases.insert(Layout.getPrimaryBase()); |
| 677 | |
| 678 | for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), |
| 679 | E = RD->bases_end(); I != E; ++I) { |
Anders Carlsson | 3a03765 | 2010-11-24 22:55:29 +0000 | [diff] [blame] | 680 | assert(!I->getType()->isDependentType() && |
Anders Carlsson | 46170f9 | 2010-11-24 22:50:27 +0000 | [diff] [blame] | 681 | "Cannot get indirect primary bases for class with dependent bases."); |
| 682 | |
| 683 | const CXXRecordDecl *BaseDecl = |
| 684 | cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); |
| 685 | |
| 686 | // Only bases with virtual bases participate in computing the |
| 687 | // indirect primary virtual base classes. |
| 688 | if (BaseDecl->getNumVBases()) |
| 689 | AddIndirectPrimaryBases(BaseDecl, Context, Bases); |
| 690 | } |
| 691 | |
| 692 | } |
| 693 | |
| 694 | void |
| 695 | CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const { |
| 696 | ASTContext &Context = getASTContext(); |
| 697 | |
| 698 | if (!getNumVBases()) |
| 699 | return; |
| 700 | |
| 701 | for (CXXRecordDecl::base_class_const_iterator I = bases_begin(), |
| 702 | E = bases_end(); I != E; ++I) { |
Anders Carlsson | 3a03765 | 2010-11-24 22:55:29 +0000 | [diff] [blame] | 703 | assert(!I->getType()->isDependentType() && |
Anders Carlsson | 46170f9 | 2010-11-24 22:50:27 +0000 | [diff] [blame] | 704 | "Cannot get indirect primary bases for class with dependent bases."); |
| 705 | |
| 706 | const CXXRecordDecl *BaseDecl = |
| 707 | cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); |
| 708 | |
| 709 | // Only bases with virtual bases participate in computing the |
| 710 | // indirect primary virtual base classes. |
| 711 | if (BaseDecl->getNumVBases()) |
| 712 | AddIndirectPrimaryBases(BaseDecl, Context, Bases); |
| 713 | } |
| 714 | } |
| 715 | |