clang/lib/AST/CXXInheritance.cpp

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