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