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