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

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