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