CXXInheritance.cpp 29 KB

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