CXXInheritance.cpp 28 KB

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