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