contrib/llvm/tools/clang/lib/AST/CXXInheritance.cpp

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