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