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