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