external/bsd/llvm/dist/clang/lib/AST/CXXInheritance.cpp

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