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