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

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