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