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