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