blob: cf3913bac00816311082f914d8d9b9464415f878 [file] [log] [blame]
Douglas Gregora8f32e02009-10-06 17:59:45 +00001//===------ CXXInheritance.cpp - C++ Inheritance ----------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file provides routines that help analyzing C++ inheritance hierarchies.
11//
12//===----------------------------------------------------------------------===//
13#include "clang/AST/CXXInheritance.h"
Benjamin Kramerd4f51982012-07-04 18:45:14 +000014#include "clang/AST/ASTContext.h"
Anders Carlsson46170f92010-11-24 22:50:27 +000015#include "clang/AST/RecordLayout.h"
Douglas Gregora8f32e02009-10-06 17:59:45 +000016#include "clang/AST/DeclCXX.h"
17#include <algorithm>
18#include <set>
19
20using namespace clang;
21
22/// \brief Computes the set of declarations referenced by these base
23/// paths.
24void CXXBasePaths::ComputeDeclsFound() {
25 assert(NumDeclsFound == 0 && !DeclsFound &&
26 "Already computed the set of declarations");
Benjamin Kramerd0e49e52012-02-23 15:18:31 +000027
28 SmallVector<NamedDecl *, 8> Decls;
29 for (paths_iterator Path = begin(), PathEnd = end(); Path != PathEnd; ++Path)
30 Decls.push_back(*Path->Decls.first);
31
32 // Eliminate duplicated decls.
33 llvm::array_pod_sort(Decls.begin(), Decls.end());
Benjamin Kramereb2f2202012-02-23 18:35:56 +000034 Decls.erase(std::unique(Decls.begin(), Decls.end()), Decls.end());
Benjamin Kramerd0e49e52012-02-23 15:18:31 +000035
Douglas Gregora8f32e02009-10-06 17:59:45 +000036 NumDeclsFound = Decls.size();
37 DeclsFound = new NamedDecl * [NumDeclsFound];
38 std::copy(Decls.begin(), Decls.end(), DeclsFound);
39}
40
41CXXBasePaths::decl_iterator CXXBasePaths::found_decls_begin() {
42 if (NumDeclsFound == 0)
43 ComputeDeclsFound();
44 return DeclsFound;
45}
46
47CXXBasePaths::decl_iterator CXXBasePaths::found_decls_end() {
48 if (NumDeclsFound == 0)
49 ComputeDeclsFound();
50 return DeclsFound + NumDeclsFound;
51}
52
53/// isAmbiguous - Determines whether the set of paths provided is
54/// ambiguous, i.e., there are two or more paths that refer to
55/// different base class subobjects of the same type. BaseType must be
56/// an unqualified, canonical class type.
Douglas Gregore0d5fe22010-05-21 20:29:55 +000057bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
58 BaseType = BaseType.getUnqualifiedType();
Douglas Gregora8f32e02009-10-06 17:59:45 +000059 std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
60 return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
61}
62
63/// clear - Clear out all prior path information.
64void CXXBasePaths::clear() {
65 Paths.clear();
66 ClassSubobjects.clear();
67 ScratchPath.clear();
68 DetectedVirtual = 0;
69}
70
71/// @brief Swaps the contents of this CXXBasePaths structure with the
72/// contents of Other.
73void CXXBasePaths::swap(CXXBasePaths &Other) {
74 std::swap(Origin, Other.Origin);
75 Paths.swap(Other.Paths);
76 ClassSubobjects.swap(Other.ClassSubobjects);
77 std::swap(FindAmbiguities, Other.FindAmbiguities);
78 std::swap(RecordPaths, Other.RecordPaths);
79 std::swap(DetectVirtual, Other.DetectVirtual);
80 std::swap(DetectedVirtual, Other.DetectedVirtual);
81}
82
John McCalld89d30f2011-01-28 22:02:36 +000083bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const {
Douglas Gregora8f32e02009-10-06 17:59:45 +000084 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
85 /*DetectVirtual=*/false);
86 return isDerivedFrom(Base, Paths);
87}
88
John McCalld89d30f2011-01-28 22:02:36 +000089bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base,
90 CXXBasePaths &Paths) const {
Douglas Gregora8f32e02009-10-06 17:59:45 +000091 if (getCanonicalDecl() == Base->getCanonicalDecl())
92 return false;
93
John McCallaf8e6ed2009-11-12 03:15:40 +000094 Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
John McCalld89d30f2011-01-28 22:02:36 +000095 return lookupInBases(&FindBaseClass,
96 const_cast<CXXRecordDecl*>(Base->getCanonicalDecl()),
97 Paths);
Douglas Gregora8f32e02009-10-06 17:59:45 +000098}
99
Jordan Rose2aa800a2012-08-08 18:23:20 +0000100bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const {
Anders Carlsson1c4c3972010-06-04 01:40:08 +0000101 if (!getNumVBases())
102 return false;
103
Douglas Gregor4e6ba4b2010-03-03 04:38:46 +0000104 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
105 /*DetectVirtual=*/false);
106
107 if (getCanonicalDecl() == Base->getCanonicalDecl())
108 return false;
109
Jordan Rose2aa800a2012-08-08 18:23:20 +0000110 Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
111
112 const void *BasePtr = static_cast<const void*>(Base->getCanonicalDecl());
113 return lookupInBases(&FindVirtualBaseClass,
114 const_cast<void *>(BasePtr),
115 Paths);
Douglas Gregor4e6ba4b2010-03-03 04:38:46 +0000116}
117
John McCalle8174bc2009-12-08 07:42:38 +0000118static bool BaseIsNot(const CXXRecordDecl *Base, void *OpaqueTarget) {
119 // OpaqueTarget is a CXXRecordDecl*.
120 return Base->getCanonicalDecl() != (const CXXRecordDecl*) OpaqueTarget;
121}
122
123bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
124 return forallBases(BaseIsNot, (void*) Base->getCanonicalDecl());
125}
126
127bool CXXRecordDecl::forallBases(ForallBasesCallback *BaseMatches,
128 void *OpaqueData,
129 bool AllowShortCircuit) const {
Chris Lattner5f9e2722011-07-23 10:55:15 +0000130 SmallVector<const CXXRecordDecl*, 8> Queue;
John McCalle8174bc2009-12-08 07:42:38 +0000131
132 const CXXRecordDecl *Record = this;
133 bool AllMatches = true;
134 while (true) {
135 for (CXXRecordDecl::base_class_const_iterator
136 I = Record->bases_begin(), E = Record->bases_end(); I != E; ++I) {
137 const RecordType *Ty = I->getType()->getAs<RecordType>();
138 if (!Ty) {
139 if (AllowShortCircuit) return false;
140 AllMatches = false;
141 continue;
142 }
143
Anders Carlssonca910e82009-12-09 04:26:02 +0000144 CXXRecordDecl *Base =
Douglas Gregor952b0172010-02-11 01:04:33 +0000145 cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition());
John McCalle8174bc2009-12-08 07:42:38 +0000146 if (!Base) {
147 if (AllowShortCircuit) return false;
148 AllMatches = false;
149 continue;
150 }
151
Anders Carlssonca910e82009-12-09 04:26:02 +0000152 Queue.push_back(Base);
153 if (!BaseMatches(Base, OpaqueData)) {
John McCalle8174bc2009-12-08 07:42:38 +0000154 if (AllowShortCircuit) return false;
155 AllMatches = false;
156 continue;
157 }
158 }
159
160 if (Queue.empty()) break;
161 Record = Queue.back(); // not actually a queue.
162 Queue.pop_back();
163 }
164
165 return AllMatches;
166}
167
Jordan Rose2aa800a2012-08-08 18:23:20 +0000168bool CXXBasePaths::lookupInBases(ASTContext &Context,
Douglas Gregor89b77022010-03-03 02:18:00 +0000169 const CXXRecordDecl *Record,
170 CXXRecordDecl::BaseMatchesCallback *BaseMatches,
171 void *UserData) {
Douglas Gregora8f32e02009-10-06 17:59:45 +0000172 bool FoundPath = false;
John McCall46460a62010-01-20 21:53:11 +0000173
John McCall92f88312010-01-23 00:46:32 +0000174 // The access of the path down to this record.
Douglas Gregor89b77022010-03-03 02:18:00 +0000175 AccessSpecifier AccessToHere = ScratchPath.Access;
176 bool IsFirstStep = ScratchPath.empty();
John McCall92f88312010-01-23 00:46:32 +0000177
Douglas Gregor89b77022010-03-03 02:18:00 +0000178 for (CXXRecordDecl::base_class_const_iterator BaseSpec = Record->bases_begin(),
179 BaseSpecEnd = Record->bases_end();
180 BaseSpec != BaseSpecEnd;
181 ++BaseSpec) {
Douglas Gregora8f32e02009-10-06 17:59:45 +0000182 // Find the record of the base class subobjects for this type.
Douglas Gregora4923eb2009-11-16 21:35:15 +0000183 QualType BaseType = Context.getCanonicalType(BaseSpec->getType())
184 .getUnqualifiedType();
Douglas Gregora8f32e02009-10-06 17:59:45 +0000185
186 // C++ [temp.dep]p3:
187 // In the definition of a class template or a member of a class template,
188 // if a base class of the class template depends on a template-parameter,
189 // the base class scope is not examined during unqualified name lookup
190 // either at the point of definition of the class template or member or
191 // during an instantiation of the class tem- plate or member.
192 if (BaseType->isDependentType())
193 continue;
194
195 // Determine whether we need to visit this base class at all,
196 // updating the count of subobjects appropriately.
Douglas Gregor89b77022010-03-03 02:18:00 +0000197 std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
Douglas Gregora8f32e02009-10-06 17:59:45 +0000198 bool VisitBase = true;
199 bool SetVirtual = false;
200 if (BaseSpec->isVirtual()) {
201 VisitBase = !Subobjects.first;
202 Subobjects.first = true;
Douglas Gregor89b77022010-03-03 02:18:00 +0000203 if (isDetectingVirtual() && DetectedVirtual == 0) {
Douglas Gregora8f32e02009-10-06 17:59:45 +0000204 // If this is the first virtual we find, remember it. If it turns out
205 // there is no base path here, we'll reset it later.
Douglas Gregor89b77022010-03-03 02:18:00 +0000206 DetectedVirtual = BaseType->getAs<RecordType>();
Douglas Gregora8f32e02009-10-06 17:59:45 +0000207 SetVirtual = true;
208 }
209 } else
210 ++Subobjects.second;
211
Douglas Gregor89b77022010-03-03 02:18:00 +0000212 if (isRecordingPaths()) {
Douglas Gregora8f32e02009-10-06 17:59:45 +0000213 // Add this base specifier to the current path.
214 CXXBasePathElement Element;
215 Element.Base = &*BaseSpec;
Douglas Gregor89b77022010-03-03 02:18:00 +0000216 Element.Class = Record;
Douglas Gregora8f32e02009-10-06 17:59:45 +0000217 if (BaseSpec->isVirtual())
218 Element.SubobjectNumber = 0;
219 else
220 Element.SubobjectNumber = Subobjects.second;
Douglas Gregor89b77022010-03-03 02:18:00 +0000221 ScratchPath.push_back(Element);
John McCall46460a62010-01-20 21:53:11 +0000222
John McCall92f88312010-01-23 00:46:32 +0000223 // Calculate the "top-down" access to this base class.
224 // The spec actually describes this bottom-up, but top-down is
225 // equivalent because the definition works out as follows:
226 // 1. Write down the access along each step in the inheritance
227 // chain, followed by the access of the decl itself.
228 // For example, in
229 // class A { public: int foo; };
230 // class B : protected A {};
231 // class C : public B {};
232 // class D : private C {};
233 // we would write:
234 // private public protected public
235 // 2. If 'private' appears anywhere except far-left, access is denied.
236 // 3. Otherwise, overall access is determined by the most restrictive
237 // access in the sequence.
238 if (IsFirstStep)
Douglas Gregor89b77022010-03-03 02:18:00 +0000239 ScratchPath.Access = BaseSpec->getAccessSpecifier();
John McCall92f88312010-01-23 00:46:32 +0000240 else
Douglas Gregor89b77022010-03-03 02:18:00 +0000241 ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere,
242 BaseSpec->getAccessSpecifier());
Douglas Gregora8f32e02009-10-06 17:59:45 +0000243 }
John McCalled814cc2010-02-09 00:57:12 +0000244
245 // Track whether there's a path involving this specific base.
246 bool FoundPathThroughBase = false;
247
Douglas Gregor89b77022010-03-03 02:18:00 +0000248 if (BaseMatches(BaseSpec, ScratchPath, UserData)) {
John McCall92f88312010-01-23 00:46:32 +0000249 // We've found a path that terminates at this base.
John McCalled814cc2010-02-09 00:57:12 +0000250 FoundPath = FoundPathThroughBase = true;
Douglas Gregor89b77022010-03-03 02:18:00 +0000251 if (isRecordingPaths()) {
Douglas Gregora8f32e02009-10-06 17:59:45 +0000252 // We have a path. Make a copy of it before moving on.
Douglas Gregor89b77022010-03-03 02:18:00 +0000253 Paths.push_back(ScratchPath);
254 } else if (!isFindingAmbiguities()) {
Douglas Gregora8f32e02009-10-06 17:59:45 +0000255 // We found a path and we don't care about ambiguities;
256 // return immediately.
257 return FoundPath;
258 }
259 } else if (VisitBase) {
260 CXXRecordDecl *BaseRecord
261 = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>()
262 ->getDecl());
Douglas Gregor89b77022010-03-03 02:18:00 +0000263 if (lookupInBases(Context, BaseRecord, BaseMatches, UserData)) {
Douglas Gregora8f32e02009-10-06 17:59:45 +0000264 // C++ [class.member.lookup]p2:
265 // A member name f in one sub-object B hides a member name f in
266 // a sub-object A if A is a base class sub-object of B. Any
267 // declarations that are so hidden are eliminated from
268 // consideration.
269
270 // There is a path to a base class that meets the criteria. If we're
271 // not collecting paths or finding ambiguities, we're done.
John McCalled814cc2010-02-09 00:57:12 +0000272 FoundPath = FoundPathThroughBase = true;
Douglas Gregor89b77022010-03-03 02:18:00 +0000273 if (!isFindingAmbiguities())
Douglas Gregora8f32e02009-10-06 17:59:45 +0000274 return FoundPath;
275 }
276 }
277
278 // Pop this base specifier off the current path (if we're
279 // collecting paths).
Douglas Gregor89b77022010-03-03 02:18:00 +0000280 if (isRecordingPaths()) {
281 ScratchPath.pop_back();
John McCall46460a62010-01-20 21:53:11 +0000282 }
283
Douglas Gregora8f32e02009-10-06 17:59:45 +0000284 // If we set a virtual earlier, and this isn't a path, forget it again.
John McCalled814cc2010-02-09 00:57:12 +0000285 if (SetVirtual && !FoundPathThroughBase) {
Douglas Gregor89b77022010-03-03 02:18:00 +0000286 DetectedVirtual = 0;
Douglas Gregora8f32e02009-10-06 17:59:45 +0000287 }
288 }
John McCall92f88312010-01-23 00:46:32 +0000289
290 // Reset the scratch path access.
Douglas Gregor89b77022010-03-03 02:18:00 +0000291 ScratchPath.Access = AccessToHere;
Douglas Gregora8f32e02009-10-06 17:59:45 +0000292
293 return FoundPath;
294}
295
Douglas Gregor89b77022010-03-03 02:18:00 +0000296bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches,
297 void *UserData,
298 CXXBasePaths &Paths) const {
Douglas Gregor4e6ba4b2010-03-03 04:38:46 +0000299 // If we didn't find anything, report that.
300 if (!Paths.lookupInBases(getASTContext(), this, BaseMatches, UserData))
301 return false;
302
303 // If we're not recording paths or we won't ever find ambiguities,
304 // we're done.
305 if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities())
306 return true;
307
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 for (CXXBasePaths::paths_iterator P = Paths.begin(), PEnd = Paths.end();
319 P != PEnd; /* increment in loop */) {
320 bool Hidden = false;
321
322 for (CXXBasePath::iterator PE = P->begin(), PEEnd = P->end();
323 PE != PEEnd && !Hidden; ++PE) {
324 if (PE->Base->isVirtual()) {
325 CXXRecordDecl *VBase = 0;
326 if (const RecordType *Record = PE->Base->getType()->getAs<RecordType>())
327 VBase = cast<CXXRecordDecl>(Record->getDecl());
328 if (!VBase)
329 break;
330
331 // The declaration(s) we found along this path were found in a
332 // subobject of a virtual base. Check whether this virtual
333 // base is a subobject of any other path; if so, then the
334 // declaration in this path are hidden by that patch.
335 for (CXXBasePaths::paths_iterator HidingP = Paths.begin(),
336 HidingPEnd = Paths.end();
337 HidingP != HidingPEnd;
338 ++HidingP) {
339 CXXRecordDecl *HidingClass = 0;
340 if (const RecordType *Record
341 = HidingP->back().Base->getType()->getAs<RecordType>())
342 HidingClass = cast<CXXRecordDecl>(Record->getDecl());
343 if (!HidingClass)
344 break;
345
346 if (HidingClass->isVirtuallyDerivedFrom(VBase)) {
347 Hidden = true;
348 break;
349 }
350 }
351 }
352 }
353
354 if (Hidden)
355 P = Paths.Paths.erase(P);
356 else
357 ++P;
358 }
359
360 return true;
Douglas Gregor89b77022010-03-03 02:18:00 +0000361}
362
John McCallaf8e6ed2009-11-12 03:15:40 +0000363bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
Douglas Gregora8f32e02009-10-06 17:59:45 +0000364 CXXBasePath &Path,
365 void *BaseRecord) {
366 assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord &&
367 "User data for FindBaseClass is not canonical!");
368 return Specifier->getType()->getAs<RecordType>()->getDecl()
369 ->getCanonicalDecl() == BaseRecord;
370}
371
Douglas Gregor4e6ba4b2010-03-03 04:38:46 +0000372bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier,
373 CXXBasePath &Path,
374 void *BaseRecord) {
375 assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord &&
376 "User data for FindBaseClass is not canonical!");
377 return Specifier->isVirtual() &&
378 Specifier->getType()->getAs<RecordType>()->getDecl()
379 ->getCanonicalDecl() == BaseRecord;
380}
381
John McCallaf8e6ed2009-11-12 03:15:40 +0000382bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier,
Douglas Gregora8f32e02009-10-06 17:59:45 +0000383 CXXBasePath &Path,
384 void *Name) {
385 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
386
387 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
388 for (Path.Decls = BaseRecord->lookup(N);
389 Path.Decls.first != Path.Decls.second;
390 ++Path.Decls.first) {
391 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
392 return true;
393 }
394
395 return false;
396}
397
John McCallaf8e6ed2009-11-12 03:15:40 +0000398bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier,
Douglas Gregora8f32e02009-10-06 17:59:45 +0000399 CXXBasePath &Path,
400 void *Name) {
401 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
402
403 const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member;
404 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
405 for (Path.Decls = BaseRecord->lookup(N);
406 Path.Decls.first != Path.Decls.second;
407 ++Path.Decls.first) {
408 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS))
409 return true;
410 }
411
412 return false;
413}
414
John McCallaf8e6ed2009-11-12 03:15:40 +0000415bool CXXRecordDecl::
416FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier,
417 CXXBasePath &Path,
418 void *Name) {
Douglas Gregora8f32e02009-10-06 17:59:45 +0000419 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
420
421 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
422 for (Path.Decls = BaseRecord->lookup(N);
423 Path.Decls.first != Path.Decls.second;
424 ++Path.Decls.first) {
425 // FIXME: Refactor the "is it a nested-name-specifier?" check
Richard Smith162e1c12011-04-15 14:24:37 +0000426 if (isa<TypedefNameDecl>(*Path.Decls.first) ||
Douglas Gregora8f32e02009-10-06 17:59:45 +0000427 (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
428 return true;
429 }
430
431 return false;
Mike Stump82109bd2009-10-06 23:38:59 +0000432}
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000433
434void OverridingMethods::add(unsigned OverriddenSubobject,
435 UniqueVirtualMethod Overriding) {
Chris Lattner5f9e2722011-07-23 10:55:15 +0000436 SmallVector<UniqueVirtualMethod, 4> &SubobjectOverrides
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000437 = Overrides[OverriddenSubobject];
438 if (std::find(SubobjectOverrides.begin(), SubobjectOverrides.end(),
439 Overriding) == SubobjectOverrides.end())
440 SubobjectOverrides.push_back(Overriding);
441}
442
443void OverridingMethods::add(const OverridingMethods &Other) {
444 for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I) {
445 for (overriding_const_iterator M = I->second.begin(),
446 MEnd = I->second.end();
447 M != MEnd;
448 ++M)
449 add(I->first, *M);
450 }
451}
452
453void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) {
454 for (iterator I = begin(), IEnd = end(); I != IEnd; ++I) {
455 I->second.clear();
456 I->second.push_back(Overriding);
457 }
458}
459
460
461namespace {
462 class FinalOverriderCollector {
463 /// \brief The number of subobjects of a given class type that
464 /// occur within the class hierarchy.
465 llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount;
466
467 /// \brief Overriders for each virtual base subobject.
468 llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders;
469
470 CXXFinalOverriderMap FinalOverriders;
471
472 public:
473 ~FinalOverriderCollector();
474
475 void Collect(const CXXRecordDecl *RD, bool VirtualBase,
476 const CXXRecordDecl *InVirtualSubobject,
477 CXXFinalOverriderMap &Overriders);
478 };
479}
480
481void FinalOverriderCollector::Collect(const CXXRecordDecl *RD,
482 bool VirtualBase,
483 const CXXRecordDecl *InVirtualSubobject,
484 CXXFinalOverriderMap &Overriders) {
485 unsigned SubobjectNumber = 0;
486 if (!VirtualBase)
487 SubobjectNumber
488 = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())];
489
490 for (CXXRecordDecl::base_class_const_iterator Base = RD->bases_begin(),
491 BaseEnd = RD->bases_end(); Base != BaseEnd; ++Base) {
492 if (const RecordType *RT = Base->getType()->getAs<RecordType>()) {
493 const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl());
494 if (!BaseDecl->isPolymorphic())
495 continue;
496
497 if (Overriders.empty() && !Base->isVirtual()) {
498 // There are no other overriders of virtual member functions,
499 // so let the base class fill in our overriders for us.
500 Collect(BaseDecl, false, InVirtualSubobject, Overriders);
501 continue;
502 }
503
504 // Collect all of the overridders from the base class subobject
505 // and merge them into the set of overridders for this class.
506 // For virtual base classes, populate or use the cached virtual
507 // overrides so that we do not walk the virtual base class (and
508 // its base classes) more than once.
509 CXXFinalOverriderMap ComputedBaseOverriders;
510 CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders;
511 if (Base->isVirtual()) {
512 CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl];
Benjamin Kramere0cf31d2012-05-27 22:41:08 +0000513 BaseOverriders = MyVirtualOverriders;
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000514 if (!MyVirtualOverriders) {
515 MyVirtualOverriders = new CXXFinalOverriderMap;
Benjamin Kramere0cf31d2012-05-27 22:41:08 +0000516
517 // Collect may cause VirtualOverriders to reallocate, invalidating the
518 // MyVirtualOverriders reference. Set BaseOverriders to the right
519 // value now.
520 BaseOverriders = MyVirtualOverriders;
521
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000522 Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders);
523 }
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000524 } else
525 Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders);
526
527 // Merge the overriders from this base class into our own set of
528 // overriders.
529 for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(),
530 OMEnd = BaseOverriders->end();
531 OM != OMEnd;
532 ++OM) {
533 const CXXMethodDecl *CanonOM
534 = cast<CXXMethodDecl>(OM->first->getCanonicalDecl());
535 Overriders[CanonOM].add(OM->second);
536 }
537 }
538 }
539
540 for (CXXRecordDecl::method_iterator M = RD->method_begin(),
541 MEnd = RD->method_end();
542 M != MEnd;
543 ++M) {
544 // We only care about virtual methods.
545 if (!M->isVirtual())
546 continue;
547
548 CXXMethodDecl *CanonM = cast<CXXMethodDecl>(M->getCanonicalDecl());
549
550 if (CanonM->begin_overridden_methods()
551 == CanonM->end_overridden_methods()) {
552 // This is a new virtual function that does not override any
553 // other virtual function. Add it to the map of virtual
554 // functions for which we are tracking overridders.
555
556 // C++ [class.virtual]p2:
557 // For convenience we say that any virtual function overrides itself.
558 Overriders[CanonM].add(SubobjectNumber,
559 UniqueVirtualMethod(CanonM, SubobjectNumber,
560 InVirtualSubobject));
561 continue;
562 }
563
564 // This virtual method overrides other virtual methods, so it does
565 // not add any new slots into the set of overriders. Instead, we
566 // replace entries in the set of overriders with the new
567 // overrider. To do so, we dig down to the original virtual
568 // functions using data recursion and update all of the methods it
569 // overrides.
570 typedef std::pair<CXXMethodDecl::method_iterator,
571 CXXMethodDecl::method_iterator> OverriddenMethods;
Chris Lattner5f9e2722011-07-23 10:55:15 +0000572 SmallVector<OverriddenMethods, 4> Stack;
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000573 Stack.push_back(std::make_pair(CanonM->begin_overridden_methods(),
574 CanonM->end_overridden_methods()));
575 while (!Stack.empty()) {
576 OverriddenMethods OverMethods = Stack.back();
577 Stack.pop_back();
578
579 for (; OverMethods.first != OverMethods.second; ++OverMethods.first) {
580 const CXXMethodDecl *CanonOM
581 = cast<CXXMethodDecl>((*OverMethods.first)->getCanonicalDecl());
Anders Carlssonffdb2d22010-06-03 01:00:02 +0000582
583 // C++ [class.virtual]p2:
584 // A virtual member function C::vf of a class object S is
585 // a final overrider unless the most derived class (1.8)
586 // of which S is a base class subobject (if any) declares
587 // or inherits another member function that overrides vf.
588 //
589 // Treating this object like the most derived class, we
590 // replace any overrides from base classes with this
591 // overriding virtual function.
592 Overriders[CanonOM].replaceAll(
593 UniqueVirtualMethod(CanonM, SubobjectNumber,
594 InVirtualSubobject));
595
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000596 if (CanonOM->begin_overridden_methods()
Anders Carlssonffdb2d22010-06-03 01:00:02 +0000597 == CanonOM->end_overridden_methods())
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000598 continue;
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000599
600 // Continue recursion to the methods that this virtual method
601 // overrides.
602 Stack.push_back(std::make_pair(CanonOM->begin_overridden_methods(),
603 CanonOM->end_overridden_methods()));
604 }
605 }
Anders Carlssonffdb2d22010-06-03 01:00:02 +0000606
607 // C++ [class.virtual]p2:
608 // For convenience we say that any virtual function overrides itself.
609 Overriders[CanonM].add(SubobjectNumber,
610 UniqueVirtualMethod(CanonM, SubobjectNumber,
611 InVirtualSubobject));
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000612 }
613}
614
615FinalOverriderCollector::~FinalOverriderCollector() {
616 for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator
617 VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end();
618 VO != VOEnd;
619 ++VO)
620 delete VO->second;
621}
622
623void
624CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const {
625 FinalOverriderCollector Collector;
626 Collector.Collect(this, false, 0, FinalOverriders);
627
628 // Weed out any final overriders that come from virtual base class
629 // subobjects that were hidden by other subobjects along any path.
630 // This is the final-overrider variant of C++ [class.member.lookup]p10.
631 for (CXXFinalOverriderMap::iterator OM = FinalOverriders.begin(),
632 OMEnd = FinalOverriders.end();
633 OM != OMEnd;
634 ++OM) {
635 for (OverridingMethods::iterator SO = OM->second.begin(),
636 SOEnd = OM->second.end();
637 SO != SOEnd;
638 ++SO) {
Chris Lattner5f9e2722011-07-23 10:55:15 +0000639 SmallVector<UniqueVirtualMethod, 4> &Overriding = SO->second;
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000640 if (Overriding.size() < 2)
641 continue;
642
Chris Lattner5f9e2722011-07-23 10:55:15 +0000643 for (SmallVector<UniqueVirtualMethod, 4>::iterator
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000644 Pos = Overriding.begin(), PosEnd = Overriding.end();
645 Pos != PosEnd;
646 /* increment in loop */) {
647 if (!Pos->InVirtualSubobject) {
648 ++Pos;
649 continue;
650 }
651
652 // We have an overriding method in a virtual base class
653 // subobject (or non-virtual base class subobject thereof);
654 // determine whether there exists an other overriding method
655 // in a base class subobject that hides the virtual base class
656 // subobject.
657 bool Hidden = false;
Chris Lattner5f9e2722011-07-23 10:55:15 +0000658 for (SmallVector<UniqueVirtualMethod, 4>::iterator
Douglas Gregor7b2fc9d2010-03-23 23:47:56 +0000659 OP = Overriding.begin(), OPEnd = Overriding.end();
660 OP != OPEnd && !Hidden;
661 ++OP) {
662 if (Pos == OP)
663 continue;
664
665 if (OP->Method->getParent()->isVirtuallyDerivedFrom(
666 const_cast<CXXRecordDecl *>(Pos->InVirtualSubobject)))
667 Hidden = true;
668 }
669
670 if (Hidden) {
671 // The current overriding function is hidden by another
672 // overriding function; remove this one.
673 Pos = Overriding.erase(Pos);
674 PosEnd = Overriding.end();
675 } else {
676 ++Pos;
677 }
678 }
679 }
680 }
681}
Anders Carlsson46170f92010-11-24 22:50:27 +0000682
683static void
684AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context,
685 CXXIndirectPrimaryBaseSet& Bases) {
686 // If the record has a virtual primary base class, add it to our set.
687 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
Anders Carlssonc9e814b2010-11-24 23:12:57 +0000688 if (Layout.isPrimaryBaseVirtual())
Anders Carlsson46170f92010-11-24 22:50:27 +0000689 Bases.insert(Layout.getPrimaryBase());
690
691 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
692 E = RD->bases_end(); I != E; ++I) {
Anders Carlsson3a037652010-11-24 22:55:29 +0000693 assert(!I->getType()->isDependentType() &&
Anders Carlsson46170f92010-11-24 22:50:27 +0000694 "Cannot get indirect primary bases for class with dependent bases.");
695
696 const CXXRecordDecl *BaseDecl =
697 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
698
699 // Only bases with virtual bases participate in computing the
700 // indirect primary virtual base classes.
701 if (BaseDecl->getNumVBases())
702 AddIndirectPrimaryBases(BaseDecl, Context, Bases);
703 }
704
705}
706
707void
708CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const {
709 ASTContext &Context = getASTContext();
710
711 if (!getNumVBases())
712 return;
713
714 for (CXXRecordDecl::base_class_const_iterator I = bases_begin(),
715 E = bases_end(); I != E; ++I) {
Anders Carlsson3a037652010-11-24 22:55:29 +0000716 assert(!I->getType()->isDependentType() &&
Anders Carlsson46170f92010-11-24 22:50:27 +0000717 "Cannot get indirect primary bases for class with dependent bases.");
718
719 const CXXRecordDecl *BaseDecl =
720 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
721
722 // Only bases with virtual bases participate in computing the
723 // indirect primary virtual base classes.
724 if (BaseDecl->getNumVBases())
725 AddIndirectPrimaryBases(BaseDecl, Context, Bases);
726 }
727}
728