xref: /freebsd/contrib/llvm-project/clang/lib/AST/CXXInheritance.cpp (revision 7fdf597e96a02165cfe22ff357b857d5fa15ed8a)
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 
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/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 
33 using namespace clang;
34 
35 /// isAmbiguous - Determines whether the set of paths provided is
36 /// ambiguous, i.e., there are two or more paths that refer to
37 /// different base class subobjects of the same type. BaseType must be
38 /// an unqualified, canonical class type.
39 bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
40   BaseType = BaseType.getUnqualifiedType();
41   IsVirtBaseAndNumberNonVirtBases Subobjects = ClassSubobjects[BaseType];
42   return Subobjects.NumberOfNonVirtBases + (Subobjects.IsVirtBase ? 1 : 0) > 1;
43 }
44 
45 /// clear - Clear out all prior path information.
46 void CXXBasePaths::clear() {
47   Paths.clear();
48   ClassSubobjects.clear();
49   VisitedDependentRecords.clear();
50   ScratchPath.clear();
51   DetectedVirtual = nullptr;
52 }
53 
54 /// Swaps the contents of this CXXBasePaths structure with the
55 /// contents of Other.
56 void CXXBasePaths::swap(CXXBasePaths &Other) {
57   std::swap(Origin, Other.Origin);
58   Paths.swap(Other.Paths);
59   ClassSubobjects.swap(Other.ClassSubobjects);
60   VisitedDependentRecords.swap(Other.VisitedDependentRecords);
61   std::swap(FindAmbiguities, Other.FindAmbiguities);
62   std::swap(RecordPaths, Other.RecordPaths);
63   std::swap(DetectVirtual, Other.DetectVirtual);
64   std::swap(DetectedVirtual, Other.DetectedVirtual);
65 }
66 
67 bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const {
68   CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
69                      /*DetectVirtual=*/false);
70   return isDerivedFrom(Base, Paths);
71 }
72 
73 bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base,
74                                   CXXBasePaths &Paths) const {
75   if (getCanonicalDecl() == Base->getCanonicalDecl())
76     return false;
77 
78   Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
79 
80   const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
81   return lookupInBases(
82       [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
83         return Specifier->getType()->getAsRecordDecl() &&
84                FindBaseClass(Specifier, Path, BaseDecl);
85       },
86       Paths);
87 }
88 
89 bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const {
90   if (!getNumVBases())
91     return false;
92 
93   CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
94                      /*DetectVirtual=*/false);
95 
96   if (getCanonicalDecl() == Base->getCanonicalDecl())
97     return false;
98 
99   Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
100 
101   const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
102   return lookupInBases(
103       [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
104         return FindVirtualBaseClass(Specifier, Path, BaseDecl);
105       },
106       Paths);
107 }
108 
109 bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
110   const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl();
111   return forallBases([TargetDecl](const CXXRecordDecl *Base) {
112     return Base->getCanonicalDecl() != TargetDecl;
113   });
114 }
115 
116 bool
117 CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const {
118   assert(isDependentContext());
119 
120   for (; !CurContext->isFileContext(); CurContext = CurContext->getParent())
121     if (CurContext->Equals(this))
122       return true;
123 
124   return false;
125 }
126 
127 bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches) const {
128   SmallVector<const CXXRecordDecl*, 8> Queue;
129 
130   const CXXRecordDecl *Record = this;
131   while (true) {
132     for (const auto &I : Record->bases()) {
133       const RecordType *Ty = I.getType()->getAs<RecordType>();
134       if (!Ty)
135         return false;
136 
137       CXXRecordDecl *Base =
138             cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition());
139       if (!Base ||
140           (Base->isDependentContext() &&
141            !Base->isCurrentInstantiation(Record))) {
142         return false;
143       }
144 
145       Queue.push_back(Base);
146       if (!BaseMatches(Base))
147         return false;
148     }
149 
150     if (Queue.empty())
151       break;
152     Record = Queue.pop_back_val(); // not actually a queue.
153   }
154 
155   return true;
156 }
157 
158 bool CXXBasePaths::lookupInBases(ASTContext &Context,
159                                  const CXXRecordDecl *Record,
160                                  CXXRecordDecl::BaseMatchesCallback BaseMatches,
161                                  bool LookupInDependent) {
162   bool FoundPath = false;
163 
164   // The access of the path down to this record.
165   AccessSpecifier AccessToHere = ScratchPath.Access;
166   bool IsFirstStep = ScratchPath.empty();
167 
168   for (const auto &BaseSpec : Record->bases()) {
169     // Find the record of the base class subobjects for this type.
170     QualType BaseType =
171         Context.getCanonicalType(BaseSpec.getType()).getUnqualifiedType();
172 
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 
182     // Determine whether we need to visit this base class at all,
183     // updating the count of subobjects appropriately.
184     IsVirtBaseAndNumberNonVirtBases &Subobjects = ClassSubobjects[BaseType];
185     bool VisitBase = true;
186     bool SetVirtual = false;
187     if (BaseSpec.isVirtual()) {
188       VisitBase = !Subobjects.IsVirtBase;
189       Subobjects.IsVirtBase = true;
190       if (isDetectingVirtual() && DetectedVirtual == nullptr) {
191         // If this is the first virtual we find, remember it. If it turns out
192         // there is no base path here, we'll reset it later.
193         DetectedVirtual = BaseType->getAs<RecordType>();
194         SetVirtual = true;
195       }
196     } else {
197       ++Subobjects.NumberOfNonVirtBases;
198     }
199     if (isRecordingPaths()) {
200       // Add this base specifier to the current path.
201       CXXBasePathElement Element;
202       Element.Base = &BaseSpec;
203       Element.Class = Record;
204       if (BaseSpec.isVirtual())
205         Element.SubobjectNumber = 0;
206       else
207         Element.SubobjectNumber = Subobjects.NumberOfNonVirtBases;
208       ScratchPath.push_back(Element);
209 
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 
232     // Track whether there's a path involving this specific base.
233     bool FoundPathThroughBase = false;
234 
235     if (BaseMatches(&BaseSpec, ScratchPath)) {
236       // We've found a path that terminates at this base.
237       FoundPath = FoundPathThroughBase = true;
238       if (isRecordingPaths()) {
239         // We have a path. Make a copy of it before moving on.
240         Paths.push_back(ScratchPath);
241       } else if (!isFindingAmbiguities()) {
242         // We found a path and we don't care about ambiguities;
243         // return immediately.
244         return FoundPath;
245       }
246     } else if (VisitBase) {
247       CXXRecordDecl *BaseRecord;
248       if (LookupInDependent) {
249         BaseRecord = nullptr;
250         const TemplateSpecializationType *TST =
251             BaseSpec.getType()->getAs<TemplateSpecializationType>();
252         if (!TST) {
253           if (auto *RT = BaseSpec.getType()->getAs<RecordType>())
254             BaseRecord = cast<CXXRecordDecl>(RT->getDecl());
255         } else {
256           TemplateName TN = TST->getTemplateName();
257           if (auto *TD =
258                   dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl()))
259             BaseRecord = TD->getTemplatedDecl();
260         }
261         if (BaseRecord) {
262           if (!BaseRecord->hasDefinition() ||
263               VisitedDependentRecords.count(BaseRecord)) {
264             BaseRecord = nullptr;
265           } else {
266             VisitedDependentRecords.insert(BaseRecord);
267           }
268         }
269       } else {
270         BaseRecord = cast<CXXRecordDecl>(
271             BaseSpec.getType()->castAs<RecordType>()->getDecl());
272       }
273       if (BaseRecord &&
274           lookupInBases(Context, BaseRecord, BaseMatches, LookupInDependent)) {
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 = nullptr;
298     }
299   }
300 
301   // Reset the scratch path access.
302   ScratchPath.Access = AccessToHere;
303 
304   return FoundPath;
305 }
306 
307 bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches,
308                                   CXXBasePaths &Paths,
309                                   bool LookupInDependent) const {
310   // If we didn't find anything, report that.
311   if (!Paths.lookupInBases(getASTContext(), this, BaseMatches,
312                            LookupInDependent))
313     return false;
314 
315   // If we're not recording paths or we won't ever find ambiguities,
316   // we're done.
317   if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities())
318     return true;
319 
320   // C++ [class.member.lookup]p6:
321   //   When virtual base classes are used, a hidden declaration can be
322   //   reached along a path through the sub-object lattice that does
323   //   not pass through the hiding declaration. This is not an
324   //   ambiguity. The identical use with nonvirtual base classes is an
325   //   ambiguity; in that case there is no unique instance of the name
326   //   that hides all the others.
327   //
328   // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy
329   // way to make it any faster.
330   Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) {
331     for (const CXXBasePathElement &PE : Path) {
332       if (!PE.Base->isVirtual())
333         continue;
334 
335       CXXRecordDecl *VBase = nullptr;
336       if (const RecordType *Record = PE.Base->getType()->getAs<RecordType>())
337         VBase = cast<CXXRecordDecl>(Record->getDecl());
338       if (!VBase)
339         break;
340 
341       // The declaration(s) we found along this path were found in a
342       // subobject of a virtual base. Check whether this virtual
343       // base is a subobject of any other path; if so, then the
344       // declaration in this path are hidden by that patch.
345       for (const CXXBasePath &HidingP : Paths) {
346         CXXRecordDecl *HidingClass = nullptr;
347         if (const RecordType *Record =
348                 HidingP.back().Base->getType()->getAs<RecordType>())
349           HidingClass = cast<CXXRecordDecl>(Record->getDecl());
350         if (!HidingClass)
351           break;
352 
353         if (HidingClass->isVirtuallyDerivedFrom(VBase))
354           return true;
355       }
356     }
357     return false;
358   });
359 
360   return true;
361 }
362 
363 bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
364                                   CXXBasePath &Path,
365                                   const CXXRecordDecl *BaseRecord) {
366   assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
367          "User data for FindBaseClass is not canonical!");
368   return Specifier->getType()->castAs<RecordType>()->getDecl()
369             ->getCanonicalDecl() == BaseRecord;
370 }
371 
372 bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier,
373                                          CXXBasePath &Path,
374                                          const CXXRecordDecl *BaseRecord) {
375   assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
376          "User data for FindBaseClass is not canonical!");
377   return Specifier->isVirtual() &&
378          Specifier->getType()->castAs<RecordType>()->getDecl()
379             ->getCanonicalDecl() == BaseRecord;
380 }
381 
382 static bool isOrdinaryMember(const NamedDecl *ND) {
383   return ND->isInIdentifierNamespace(Decl::IDNS_Ordinary | Decl::IDNS_Tag |
384                                      Decl::IDNS_Member);
385 }
386 
387 static bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path,
388                                DeclarationName Name) {
389   Path.Decls = RD->lookup(Name).begin();
390   for (DeclContext::lookup_iterator I = Path.Decls, E = I.end(); I != E; ++I)
391     if (isOrdinaryMember(*I))
392       return true;
393 
394   return false;
395 }
396 
397 bool CXXRecordDecl::hasMemberName(DeclarationName Name) const {
398   CXXBasePath P;
399   if (findOrdinaryMember(this, P, Name))
400     return true;
401 
402   CXXBasePaths Paths(false, false, false);
403   return lookupInBases(
404       [Name](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
405         return findOrdinaryMember(Specifier->getType()->getAsCXXRecordDecl(),
406                                   Path, Name);
407       },
408       Paths);
409 }
410 
411 static bool
412 findOrdinaryMemberInDependentClasses(const CXXBaseSpecifier *Specifier,
413                                      CXXBasePath &Path, DeclarationName Name) {
414   const TemplateSpecializationType *TST =
415       Specifier->getType()->getAs<TemplateSpecializationType>();
416   if (!TST) {
417     auto *RT = Specifier->getType()->getAs<RecordType>();
418     if (!RT)
419       return false;
420     return findOrdinaryMember(cast<CXXRecordDecl>(RT->getDecl()), Path, Name);
421   }
422   TemplateName TN = TST->getTemplateName();
423   const auto *TD = dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl());
424   if (!TD)
425     return false;
426   CXXRecordDecl *RD = TD->getTemplatedDecl();
427   if (!RD)
428     return false;
429   return findOrdinaryMember(RD, Path, Name);
430 }
431 
432 std::vector<const NamedDecl *> CXXRecordDecl::lookupDependentName(
433     DeclarationName Name,
434     llvm::function_ref<bool(const NamedDecl *ND)> Filter) {
435   std::vector<const NamedDecl *> Results;
436   // Lookup in the class.
437   bool AnyOrdinaryMembers = false;
438   for (const NamedDecl *ND : lookup(Name)) {
439     if (isOrdinaryMember(ND))
440       AnyOrdinaryMembers = true;
441     if (Filter(ND))
442       Results.push_back(ND);
443   }
444   if (AnyOrdinaryMembers)
445     return Results;
446 
447   // Perform lookup into our base classes.
448   CXXBasePaths Paths;
449   Paths.setOrigin(this);
450   if (!lookupInBases(
451           [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
452             return findOrdinaryMemberInDependentClasses(Specifier, Path, Name);
453           },
454           Paths, /*LookupInDependent=*/true))
455     return Results;
456   for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end();
457        I != E; ++I) {
458     if (isOrdinaryMember(*I) && Filter(*I))
459       Results.push_back(*I);
460   }
461   return Results;
462 }
463 
464 void OverridingMethods::add(unsigned OverriddenSubobject,
465                             UniqueVirtualMethod Overriding) {
466   SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides
467     = Overrides[OverriddenSubobject];
468   if (!llvm::is_contained(SubobjectOverrides, Overriding))
469     SubobjectOverrides.push_back(Overriding);
470 }
471 
472 void OverridingMethods::add(const OverridingMethods &Other) {
473   for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I) {
474     for (overriding_const_iterator M = I->second.begin(),
475                                 MEnd = I->second.end();
476          M != MEnd;
477          ++M)
478       add(I->first, *M);
479   }
480 }
481 
482 void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) {
483   for (iterator I = begin(), IEnd = end(); I != IEnd; ++I) {
484     I->second.clear();
485     I->second.push_back(Overriding);
486   }
487 }
488 
489 namespace {
490 
491 class FinalOverriderCollector {
492   /// The number of subobjects of a given class type that
493   /// occur within the class hierarchy.
494   llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount;
495 
496   /// Overriders for each virtual base subobject.
497   llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders;
498 
499   CXXFinalOverriderMap FinalOverriders;
500 
501 public:
502   ~FinalOverriderCollector();
503 
504   void Collect(const CXXRecordDecl *RD, bool VirtualBase,
505                const CXXRecordDecl *InVirtualSubobject,
506                CXXFinalOverriderMap &Overriders);
507 };
508 
509 } // namespace
510 
511 void FinalOverriderCollector::Collect(const CXXRecordDecl *RD,
512                                       bool VirtualBase,
513                                       const CXXRecordDecl *InVirtualSubobject,
514                                       CXXFinalOverriderMap &Overriders) {
515   unsigned SubobjectNumber = 0;
516   if (!VirtualBase)
517     SubobjectNumber
518       = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())];
519 
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 
526       if (Overriders.empty() && !Base.isVirtual()) {
527         // There are no other overriders of virtual member functions,
528         // so let the base class fill in our overriders for us.
529         Collect(BaseDecl, false, InVirtualSubobject, Overriders);
530         continue;
531       }
532 
533       // Collect all of the overridders from the base class subobject
534       // and merge them into the set of overridders for this class.
535       // For virtual base classes, populate or use the cached virtual
536       // overrides so that we do not walk the virtual base class (and
537       // its base classes) more than once.
538       CXXFinalOverriderMap ComputedBaseOverriders;
539       CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders;
540       if (Base.isVirtual()) {
541         CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl];
542         BaseOverriders = MyVirtualOverriders;
543         if (!MyVirtualOverriders) {
544           MyVirtualOverriders = new CXXFinalOverriderMap;
545 
546           // Collect may cause VirtualOverriders to reallocate, invalidating the
547           // MyVirtualOverriders reference. Set BaseOverriders to the right
548           // value now.
549           BaseOverriders = MyVirtualOverriders;
550 
551           Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders);
552         }
553       } else
554         Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders);
555 
556       // Merge the overriders from this base class into our own set of
557       // overriders.
558       for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(),
559                                OMEnd = BaseOverriders->end();
560            OM != OMEnd;
561            ++OM) {
562         const CXXMethodDecl *CanonOM = OM->first->getCanonicalDecl();
563         Overriders[CanonOM].add(OM->second);
564       }
565     }
566   }
567 
568   for (auto *M : RD->methods()) {
569     // We only care about virtual methods.
570     if (!M->isVirtual())
571       continue;
572 
573     CXXMethodDecl *CanonM = M->getCanonicalDecl();
574     using OverriddenMethodsRange =
575         llvm::iterator_range<CXXMethodDecl::method_iterator>;
576     OverriddenMethodsRange OverriddenMethods = CanonM->overridden_methods();
577 
578     if (OverriddenMethods.begin() == OverriddenMethods.end()) {
579       // This is a new virtual function that does not override any
580       // other virtual function. Add it to the map of virtual
581       // functions for which we are tracking overridders.
582 
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 
591     // This virtual method overrides other virtual methods, so it does
592     // not add any new slots into the set of overriders. Instead, we
593     // replace entries in the set of overriders with the new
594     // overrider. To do so, we dig down to the original virtual
595     // functions using data recursion and update all of the methods it
596     // overrides.
597     SmallVector<OverriddenMethodsRange, 4> Stack(1, OverriddenMethods);
598     while (!Stack.empty()) {
599       for (const CXXMethodDecl *OM : Stack.pop_back_val()) {
600         const CXXMethodDecl *CanonOM = OM->getCanonicalDecl();
601 
602         // C++ [class.virtual]p2:
603         //   A virtual member function C::vf of a class object S is
604         //   a final overrider unless the most derived class (1.8)
605         //   of which S is a base class subobject (if any) declares
606         //   or inherits another member function that overrides vf.
607         //
608         // Treating this object like the most derived class, we
609         // replace any overrides from base classes with this
610         // overriding virtual function.
611         Overriders[CanonOM].replaceAll(
612                                UniqueVirtualMethod(CanonM, SubobjectNumber,
613                                                    InVirtualSubobject));
614 
615         auto OverriddenMethods = CanonOM->overridden_methods();
616         if (OverriddenMethods.begin() == OverriddenMethods.end())
617           continue;
618 
619         // Continue recursion to the methods that this virtual method
620         // overrides.
621         Stack.push_back(OverriddenMethods);
622       }
623     }
624 
625     // C++ [class.virtual]p2:
626     //   For convenience we say that any virtual function overrides itself.
627     Overriders[CanonM].add(SubobjectNumber,
628                            UniqueVirtualMethod(CanonM, SubobjectNumber,
629                                                InVirtualSubobject));
630   }
631 }
632 
633 FinalOverriderCollector::~FinalOverriderCollector() {
634   for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator
635          VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end();
636        VO != VOEnd;
637        ++VO)
638     delete VO->second;
639 }
640 
641 void
642 CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const {
643   FinalOverriderCollector Collector;
644   Collector.Collect(this, false, nullptr, FinalOverriders);
645 
646   // Weed out any final overriders that come from virtual base class
647   // subobjects that were hidden by other subobjects along any path.
648   // This is the final-overrider variant of C++ [class.member.lookup]p10.
649   for (auto &OM : FinalOverriders) {
650     for (auto &SO : OM.second) {
651       SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second;
652       if (Overriding.size() < 2)
653         continue;
654 
655       auto IsHidden = [&Overriding](const UniqueVirtualMethod &M) {
656         if (!M.InVirtualSubobject)
657           return false;
658 
659         // We have an overriding method in a virtual base class
660         // subobject (or non-virtual base class subobject thereof);
661         // determine whether there exists an other overriding method
662         // in a base class subobject that hides the virtual base class
663         // subobject.
664         for (const UniqueVirtualMethod &OP : Overriding)
665           if (&M != &OP &&
666               OP.Method->getParent()->isVirtuallyDerivedFrom(
667                   M.InVirtualSubobject))
668             return true;
669         return false;
670       };
671 
672       // FIXME: IsHidden reads from Overriding from the middle of a remove_if
673       // over the same sequence! Is this guaranteed to work?
674       llvm::erase_if(Overriding, IsHidden);
675     }
676   }
677 }
678 
679 static void
680 AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context,
681                         CXXIndirectPrimaryBaseSet& Bases) {
682   // If the record has a virtual primary base class, add it to our set.
683   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
684   if (Layout.isPrimaryBaseVirtual())
685     Bases.insert(Layout.getPrimaryBase());
686 
687   for (const auto &I : RD->bases()) {
688     assert(!I.getType()->isDependentType() &&
689            "Cannot get indirect primary bases for class with dependent bases.");
690 
691     const CXXRecordDecl *BaseDecl =
692       cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
693 
694     // Only bases with virtual bases participate in computing the
695     // indirect primary virtual base classes.
696     if (BaseDecl->getNumVBases())
697       AddIndirectPrimaryBases(BaseDecl, Context, Bases);
698   }
699 
700 }
701 
702 void
703 CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const {
704   ASTContext &Context = getASTContext();
705 
706   if (!getNumVBases())
707     return;
708 
709   for (const auto &I : bases()) {
710     assert(!I.getType()->isDependentType() &&
711            "Cannot get indirect primary bases for class with dependent bases.");
712 
713     const CXXRecordDecl *BaseDecl =
714       cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
715 
716     // Only bases with virtual bases participate in computing the
717     // indirect primary virtual base classes.
718     if (BaseDecl->getNumVBases())
719       AddIndirectPrimaryBases(BaseDecl, Context, Bases);
720   }
721 }
722