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