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

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