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