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