text: //===- CXXInheritance.cpp - C++ Inheritance -------------------------------===//
  //
  //                     The LLVM Compiler Infrastructure
  //
  // This file is distributed under the University of Illinois Open Source
  // License. See LICENSE.TXT for details.
  //
  //===----------------------------------------------------------------------===//
  //
  // This file provides routines that help analyzing C++ inheritance hierarchies.
  //
  //===----------------------------------------------------------------------===//
  
  #include "clang/AST/CXXInheritance.h"
  #include "clang/AST/ASTContext.h"
  #include "clang/AST/Decl.h"
  #include "clang/AST/DeclBase.h"
  #include "clang/AST/DeclCXX.h"
  #include "clang/AST/DeclTemplate.h"
  #include "clang/AST/RecordLayout.h"
  #include "clang/AST/TemplateName.h"
  #include "clang/AST/Type.h"
  #include "clang/Basic/LLVM.h"
  #include "llvm/ADT/DenseMap.h"
  #include "llvm/ADT/STLExtras.h"
  #include "llvm/ADT/SetVector.h"
  #include "llvm/ADT/SmallVector.h"
  #include "llvm/ADT/iterator_range.h"
  #include "llvm/Support/Casting.h"
  #include <algorithm>
  #include <utility>
  #include <cassert>
  #include <vector>
  
  using namespace clang;
  
  /// \brief Computes the set of declarations referenced by these base
  /// paths.
  void CXXBasePaths::ComputeDeclsFound() {
    assert(NumDeclsFound == 0 && !DeclsFound &&
           "Already computed the set of declarations");
  
    llvm::SetVector<NamedDecl *, SmallVector<NamedDecl *, 8>> Decls;
    for (paths_iterator Path = begin(), PathEnd = end(); Path != PathEnd; ++Path)
      Decls.insert(Path->Decls.front());
  
    NumDeclsFound = Decls.size();
    DeclsFound = llvm::make_unique<NamedDecl *[]>(NumDeclsFound);
    std::copy(Decls.begin(), Decls.end(), DeclsFound.get());
  }
  
  CXXBasePaths::decl_range CXXBasePaths::found_decls() {
    if (NumDeclsFound == 0)
      ComputeDeclsFound();
  
    return decl_range(decl_iterator(DeclsFound.get()),
                      decl_iterator(DeclsFound.get() + NumDeclsFound));
  }
  
  /// isAmbiguous - Determines whether the set of paths provided is
  /// ambiguous, i.e., there are two or more paths that refer to
  /// different base class subobjects of the same type. BaseType must be
  /// an unqualified, canonical class type.
  bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
    BaseType = BaseType.getUnqualifiedType();
    std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
    return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
  }
  
  /// clear - Clear out all prior path information.
  void CXXBasePaths::clear() {
    Paths.clear();
    ClassSubobjects.clear();
    VisitedDependentRecords.clear();
    ScratchPath.clear();
    DetectedVirtual = nullptr;
  }
  
  /// @brief Swaps the contents of this CXXBasePaths structure with the
  /// contents of Other.
  void CXXBasePaths::swap(CXXBasePaths &Other) {
    std::swap(Origin, Other.Origin);
    Paths.swap(Other.Paths);
    ClassSubobjects.swap(Other.ClassSubobjects);
    VisitedDependentRecords.swap(Other.VisitedDependentRecords);
    std::swap(FindAmbiguities, Other.FindAmbiguities);
    std::swap(RecordPaths, Other.RecordPaths);
    std::swap(DetectVirtual, Other.DetectVirtual);
    std::swap(DetectedVirtual, Other.DetectedVirtual);
  }
  
  bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const {
    CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
                       /*DetectVirtual=*/false);
    return isDerivedFrom(Base, Paths);
  }
  
  bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base,
                                    CXXBasePaths &Paths) const {
    if (getCanonicalDecl() == Base->getCanonicalDecl())
      return false;
    
    Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
  
    const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
    // FIXME: Capturing 'this' is a workaround for name lookup bugs in GCC 4.7.
    return lookupInBases(
        [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
          return FindBaseClass(Specifier, Path, BaseDecl);
        },
        Paths);
  }
  
  bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const {
    if (!getNumVBases())
      return false;
  
    CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
                       /*DetectVirtual=*/false);
  
    if (getCanonicalDecl() == Base->getCanonicalDecl())
      return false;
    
    Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
  
    const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
    // FIXME: Capturing 'this' is a workaround for name lookup bugs in GCC 4.7.
    return lookupInBases(
        [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
          return FindVirtualBaseClass(Specifier, Path, BaseDecl);
        },
        Paths);
  }
  
  bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
    const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl();
    return forallBases([TargetDecl](const CXXRecordDecl *Base) {
      return Base->getCanonicalDecl() != TargetDecl;
    });
  }
  
  bool
  CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const {
    assert(isDependentContext());
  
    for (; !CurContext->isFileContext(); CurContext = CurContext->getParent())
      if (CurContext->Equals(this))
        return true;
  
    return false;
  }
  
  bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches,
                                  bool AllowShortCircuit) const {
    SmallVector<const CXXRecordDecl*, 8> Queue;
  
    const CXXRecordDecl *Record = this;
    bool AllMatches = true;
    while (true) {
      for (const auto &I : Record->bases()) {
        const RecordType *Ty = I.getType()->getAs<RecordType>();
        if (!Ty) {
          if (AllowShortCircuit) return false;
          AllMatches = false;
          continue;
        }
  
        CXXRecordDecl *Base = 
              cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition());
        if (!Base ||
            (Base->isDependentContext() &&
             !Base->isCurrentInstantiation(Record))) {
          if (AllowShortCircuit) return false;
          AllMatches = false;
          continue;
        }
        
        Queue.push_back(Base);
        if (!BaseMatches(Base)) {
          if (AllowShortCircuit) return false;
          AllMatches = false;
          continue;
        }
      }
  
      if (Queue.empty())
        break;
      Record = Queue.pop_back_val(); // not actually a queue.
    }
  
    return AllMatches;
  }
  
  bool CXXBasePaths::lookupInBases(ASTContext &Context,
                                   const CXXRecordDecl *Record,
                                   CXXRecordDecl::BaseMatchesCallback BaseMatches,
                                   bool LookupInDependent) {
    bool FoundPath = false;
  
    // The access of the path down to this record.
    AccessSpecifier AccessToHere = ScratchPath.Access;
    bool IsFirstStep = ScratchPath.empty();
  
    for (const auto &BaseSpec : Record->bases()) {
      // Find the record of the base class subobjects for this type.
      QualType BaseType =
          Context.getCanonicalType(BaseSpec.getType()).getUnqualifiedType();
  
      // C++ [temp.dep]p3:
      //   In the definition of a class template or a member of a class template,
      //   if a base class of the class template depends on a template-parameter,
      //   the base class scope is not examined during unqualified name lookup 
      //   either at the point of definition of the class template or member or 
      //   during an instantiation of the class tem- plate or member.
      if (!LookupInDependent && BaseType->isDependentType())
        continue;
      
      // Determine whether we need to visit this base class at all,
      // updating the count of subobjects appropriately.
      std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
      bool VisitBase = true;
      bool SetVirtual = false;
      if (BaseSpec.isVirtual()) {
        VisitBase = !Subobjects.first;
        Subobjects.first = true;
        if (isDetectingVirtual() && DetectedVirtual == nullptr) {
          // If this is the first virtual we find, remember it. If it turns out
          // there is no base path here, we'll reset it later.
          DetectedVirtual = BaseType->getAs<RecordType>();
          SetVirtual = true;
        }
      } else
        ++Subobjects.second;
      
      if (isRecordingPaths()) {
        // Add this base specifier to the current path.
        CXXBasePathElement Element;
        Element.Base = &BaseSpec;
        Element.Class = Record;
        if (BaseSpec.isVirtual())
          Element.SubobjectNumber = 0;
        else
          Element.SubobjectNumber = Subobjects.second;
        ScratchPath.push_back(Element);
  
        // Calculate the "top-down" access to this base class.
        // The spec actually describes this bottom-up, but top-down is
        // equivalent because the definition works out as follows:
        // 1. Write down the access along each step in the inheritance
        //    chain, followed by the access of the decl itself.
        //    For example, in
        //      class A { public: int foo; };
        //      class B : protected A {};
        //      class C : public B {};
        //      class D : private C {};
        //    we would write:
        //      private public protected public
        // 2. If 'private' appears anywhere except far-left, access is denied.
        // 3. Otherwise, overall access is determined by the most restrictive
        //    access in the sequence.
        if (IsFirstStep)
          ScratchPath.Access = BaseSpec.getAccessSpecifier();
        else
          ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere, 
                                                   BaseSpec.getAccessSpecifier());
      }
      
      // Track whether there's a path involving this specific base.
      bool FoundPathThroughBase = false;
      
      if (BaseMatches(&BaseSpec, ScratchPath)) {
        // We've found a path that terminates at this base.
        FoundPath = FoundPathThroughBase = true;
        if (isRecordingPaths()) {
          // We have a path. Make a copy of it before moving on.
          Paths.push_back(ScratchPath);
        } else if (!isFindingAmbiguities()) {
          // We found a path and we don't care about ambiguities;
          // return immediately.
          return FoundPath;
        }
      } else if (VisitBase) {
        CXXRecordDecl *BaseRecord;
        if (LookupInDependent) {
          BaseRecord = nullptr;
          const TemplateSpecializationType *TST =
              BaseSpec.getType()->getAs<TemplateSpecializationType>();
          if (!TST) {
            if (auto *RT = BaseSpec.getType()->getAs<RecordType>())
              BaseRecord = cast<CXXRecordDecl>(RT->getDecl());
          } else {
            TemplateName TN = TST->getTemplateName();
            if (auto *TD =
                    dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl()))
              BaseRecord = TD->getTemplatedDecl();
          }
          if (BaseRecord) {
            if (!BaseRecord->hasDefinition() ||
                VisitedDependentRecords.count(BaseRecord)) {
              BaseRecord = nullptr;
            } else {
              VisitedDependentRecords.insert(BaseRecord);
            }
          }
        } else {
          BaseRecord = cast<CXXRecordDecl>(
              BaseSpec.getType()->castAs<RecordType>()->getDecl());
        }
        if (BaseRecord &&
            lookupInBases(Context, BaseRecord, BaseMatches, LookupInDependent)) {
          // C++ [class.member.lookup]p2:
          //   A member name f in one sub-object B hides a member name f in
          //   a sub-object A if A is a base class sub-object of B. Any
          //   declarations that are so hidden are eliminated from
          //   consideration.
          
          // There is a path to a base class that meets the criteria. If we're 
          // not collecting paths or finding ambiguities, we're done.
          FoundPath = FoundPathThroughBase = true;
          if (!isFindingAmbiguities())
            return FoundPath;
        }
      }
      
      // Pop this base specifier off the current path (if we're
      // collecting paths).
      if (isRecordingPaths()) {
        ScratchPath.pop_back();
      }
  
      // If we set a virtual earlier, and this isn't a path, forget it again.
      if (SetVirtual && !FoundPathThroughBase) {
        DetectedVirtual = nullptr;
      }
    }
  
    // Reset the scratch path access.
    ScratchPath.Access = AccessToHere;
    
    return FoundPath;
  }
  
  bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches,
                                    CXXBasePaths &Paths,
                                    bool LookupInDependent) const {
    // If we didn't find anything, report that.
    if (!Paths.lookupInBases(getASTContext(), this, BaseMatches,
                             LookupInDependent))
      return false;
  
    // If we're not recording paths or we won't ever find ambiguities,
    // we're done.
    if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities())
      return true;
    
    // C++ [class.member.lookup]p6:
    //   When virtual base classes are used, a hidden declaration can be
    //   reached along a path through the sub-object lattice that does
    //   not pass through the hiding declaration. This is not an
    //   ambiguity. The identical use with nonvirtual base classes is an
    //   ambiguity; in that case there is no unique instance of the name
    //   that hides all the others.
    //
    // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy
    // way to make it any faster.
    Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) {
      for (const CXXBasePathElement &PE : Path) {
        if (!PE.Base->isVirtual())
          continue;
  
        CXXRecordDecl *VBase = nullptr;
        if (const RecordType *Record = PE.Base->getType()->getAs<RecordType>())
          VBase = cast<CXXRecordDecl>(Record->getDecl());
        if (!VBase)
          break;
  
        // The declaration(s) we found along this path were found in a
        // subobject of a virtual base. Check whether this virtual
        // base is a subobject of any other path; if so, then the
        // declaration in this path are hidden by that patch.
        for (const CXXBasePath &HidingP : Paths) {
          CXXRecordDecl *HidingClass = nullptr;
          if (const RecordType *Record =
                  HidingP.back().Base->getType()->getAs<RecordType>())
            HidingClass = cast<CXXRecordDecl>(Record->getDecl());
          if (!HidingClass)
            break;
  
          if (HidingClass->isVirtuallyDerivedFrom(VBase))
            return true;
        }
      }
      return false;
    });
  
    return true;
  }
  
  bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier, 
                                    CXXBasePath &Path,
                                    const CXXRecordDecl *BaseRecord) {
    assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
           "User data for FindBaseClass is not canonical!");
    return Specifier->getType()->castAs<RecordType>()->getDecl()
              ->getCanonicalDecl() == BaseRecord;
  }
  
  bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier, 
                                           CXXBasePath &Path,
                                           const CXXRecordDecl *BaseRecord) {
    assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
           "User data for FindBaseClass is not canonical!");
    return Specifier->isVirtual() &&
           Specifier->getType()->castAs<RecordType>()->getDecl()
              ->getCanonicalDecl() == BaseRecord;
  }
  
  bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier, 
                                    CXXBasePath &Path,
                                    DeclarationName Name) {
    RecordDecl *BaseRecord =
      Specifier->getType()->castAs<RecordType>()->getDecl();
  
    for (Path.Decls = BaseRecord->lookup(Name);
         !Path.Decls.empty();
         Path.Decls = Path.Decls.slice(1)) {
      if (Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag))
        return true;
    }
  
    return false;
  }
  
  static bool findOrdinaryMember(RecordDecl *BaseRecord, CXXBasePath &Path,
                                 DeclarationName Name) {
    const unsigned IDNS = Decl::IDNS_Ordinary | Decl::IDNS_Tag |
                          Decl::IDNS_Member;
    for (Path.Decls = BaseRecord->lookup(Name);
         !Path.Decls.empty();
         Path.Decls = Path.Decls.slice(1)) {
      if (Path.Decls.front()->isInIdentifierNamespace(IDNS))
        return true;
    }
  
    return false;
  }
  
  bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier,
                                         CXXBasePath &Path,
                                         DeclarationName Name) {
    RecordDecl *BaseRecord =
        Specifier->getType()->castAs<RecordType>()->getDecl();
    return findOrdinaryMember(BaseRecord, Path, Name);
  }
  
  bool CXXRecordDecl::FindOrdinaryMemberInDependentClasses(
      const CXXBaseSpecifier *Specifier, CXXBasePath &Path,
      DeclarationName Name) {
    const TemplateSpecializationType *TST =
        Specifier->getType()->getAs<TemplateSpecializationType>();
    if (!TST) {
      auto *RT = Specifier->getType()->getAs<RecordType>();
      if (!RT)
        return false;
      return findOrdinaryMember(RT->getDecl(), Path, Name);
    }
    TemplateName TN = TST->getTemplateName();
    const auto *TD = dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl());
    if (!TD)
      return false;
    CXXRecordDecl *RD = TD->getTemplatedDecl();
    if (!RD)
      return false;
    return findOrdinaryMember(RD, Path, Name);
  }
  
  bool CXXRecordDecl::FindOMPReductionMember(const CXXBaseSpecifier *Specifier,
                                             CXXBasePath &Path,
                                             DeclarationName Name) {
    RecordDecl *BaseRecord =
        Specifier->getType()->castAs<RecordType>()->getDecl();
  
    for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty();
         Path.Decls = Path.Decls.slice(1)) {
      if (Path.Decls.front()->isInIdentifierNamespace(IDNS_OMPReduction))
        return true;
    }
  
    return false;
  }
  
  bool CXXRecordDecl::
  FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier, 
                                CXXBasePath &Path,
                                DeclarationName Name) {
    RecordDecl *BaseRecord =
      Specifier->getType()->castAs<RecordType>()->getDecl();
    
    for (Path.Decls = BaseRecord->lookup(Name);
         !Path.Decls.empty();
         Path.Decls = Path.Decls.slice(1)) {
      // FIXME: Refactor the "is it a nested-name-specifier?" check
      if (isa<TypedefNameDecl>(Path.Decls.front()) ||
          Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag))
        return true;
    }
    
    return false;
  }
  
  std::vector<const NamedDecl *> CXXRecordDecl::lookupDependentName(
      const DeclarationName &Name,
      llvm::function_ref<bool(const NamedDecl *ND)> Filter) {
    std::vector<const NamedDecl *> Results;
    // Lookup in the class.
    DeclContext::lookup_result DirectResult = lookup(Name);
    if (!DirectResult.empty()) {
      for (const NamedDecl *ND : DirectResult) {
        if (Filter(ND))
          Results.push_back(ND);
      }
      return Results;
    }
    // Perform lookup into our base classes.
    CXXBasePaths Paths;
    Paths.setOrigin(this);
    if (!lookupInBases(
            [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
              return CXXRecordDecl::FindOrdinaryMemberInDependentClasses(
                  Specifier, Path, Name);
            },
            Paths, /*LookupInDependent=*/true))
      return Results;
    for (const NamedDecl *ND : Paths.front().Decls) {
      if (Filter(ND))
        Results.push_back(ND);
    }
    return Results;
  }
  
  void OverridingMethods::add(unsigned OverriddenSubobject, 
                              UniqueVirtualMethod Overriding) {
    SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides
      = Overrides[OverriddenSubobject];
    if (std::find(SubobjectOverrides.begin(), SubobjectOverrides.end(), 
                  Overriding) == SubobjectOverrides.end())
      SubobjectOverrides.push_back(Overriding);
  }
  
  void OverridingMethods::add(const OverridingMethods &Other) {
    for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I) {
      for (overriding_const_iterator M = I->second.begin(), 
                                  MEnd = I->second.end();
           M != MEnd; 
           ++M)
        add(I->first, *M);
    }
  }
  
  void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) {
    for (iterator I = begin(), IEnd = end(); I != IEnd; ++I) {
      I->second.clear();
      I->second.push_back(Overriding);
    }
  }
  
  namespace {
  
  class FinalOverriderCollector {
    /// \brief The number of subobjects of a given class type that
    /// occur within the class hierarchy.
    llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount;
  
    /// \brief Overriders for each virtual base subobject.
    llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders;
  
    CXXFinalOverriderMap FinalOverriders;
  
  public:
    ~FinalOverriderCollector();
  
    void Collect(const CXXRecordDecl *RD, bool VirtualBase,
                 const CXXRecordDecl *InVirtualSubobject,
                 CXXFinalOverriderMap &Overriders);
  };
  
  } // namespace
  
  void FinalOverriderCollector::Collect(const CXXRecordDecl *RD, 
                                        bool VirtualBase,
                                        const CXXRecordDecl *InVirtualSubobject,
                                        CXXFinalOverriderMap &Overriders) {
    unsigned SubobjectNumber = 0;
    if (!VirtualBase)
      SubobjectNumber
        = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())];
  
    for (const auto &Base : RD->bases()) {
      if (const RecordType *RT = Base.getType()->getAs<RecordType>()) {
        const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl());
        if (!BaseDecl->isPolymorphic())
          continue;
  
        if (Overriders.empty() && !Base.isVirtual()) {
          // There are no other overriders of virtual member functions,
          // so let the base class fill in our overriders for us.
          Collect(BaseDecl, false, InVirtualSubobject, Overriders);
          continue;
        }
  
        // Collect all of the overridders from the base class subobject
        // and merge them into the set of overridders for this class.
        // For virtual base classes, populate or use the cached virtual
        // overrides so that we do not walk the virtual base class (and
        // its base classes) more than once.
        CXXFinalOverriderMap ComputedBaseOverriders;
        CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders;
        if (Base.isVirtual()) {
          CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl];
          BaseOverriders = MyVirtualOverriders;
          if (!MyVirtualOverriders) {
            MyVirtualOverriders = new CXXFinalOverriderMap;
  
            // Collect may cause VirtualOverriders to reallocate, invalidating the
            // MyVirtualOverriders reference. Set BaseOverriders to the right
            // value now.
            BaseOverriders = MyVirtualOverriders;
  
            Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders);
          }
        } else
          Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders);
  
        // Merge the overriders from this base class into our own set of
        // overriders.
        for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(), 
                                 OMEnd = BaseOverriders->end();
             OM != OMEnd;
             ++OM) {
          const CXXMethodDecl *CanonOM = OM->first->getCanonicalDecl();
          Overriders[CanonOM].add(OM->second);
        }
      }
    }
  
    for (auto *M : RD->methods()) {
      // We only care about virtual methods.
      if (!M->isVirtual())
        continue;
  
      CXXMethodDecl *CanonM = M->getCanonicalDecl();
      using OverriddenMethodsRange =
          llvm::iterator_range<CXXMethodDecl::method_iterator>;
      OverriddenMethodsRange OverriddenMethods = CanonM->overridden_methods();
  
      if (OverriddenMethods.begin() == OverriddenMethods.end()) {
        // This is a new virtual function that does not override any
        // other virtual function. Add it to the map of virtual
        // functions for which we are tracking overridders. 
  
        // C++ [class.virtual]p2:
        //   For convenience we say that any virtual function overrides itself.
        Overriders[CanonM].add(SubobjectNumber,
                               UniqueVirtualMethod(CanonM, SubobjectNumber,
                                                   InVirtualSubobject));
        continue;
      }
  
      // This virtual method overrides other virtual methods, so it does
      // not add any new slots into the set of overriders. Instead, we
      // replace entries in the set of overriders with the new
      // overrider. To do so, we dig down to the original virtual
      // functions using data recursion and update all of the methods it
      // overrides.
      SmallVector<OverriddenMethodsRange, 4> Stack(1, OverriddenMethods);
      while (!Stack.empty()) {
        for (const CXXMethodDecl *OM : Stack.pop_back_val()) {
          const CXXMethodDecl *CanonOM = OM->getCanonicalDecl();
  
          // C++ [class.virtual]p2:
          //   A virtual member function C::vf of a class object S is
          //   a final overrider unless the most derived class (1.8)
          //   of which S is a base class subobject (if any) declares
          //   or inherits another member function that overrides vf.
          //
          // Treating this object like the most derived class, we
          // replace any overrides from base classes with this
          // overriding virtual function.
          Overriders[CanonOM].replaceAll(
                                 UniqueVirtualMethod(CanonM, SubobjectNumber,
                                                     InVirtualSubobject));
  
          auto OverriddenMethods = CanonOM->overridden_methods();
          if (OverriddenMethods.begin() == OverriddenMethods.end())
            continue;
  
          // Continue recursion to the methods that this virtual method
          // overrides.
          Stack.push_back(OverriddenMethods);
        }
      }
  
      // C++ [class.virtual]p2:
      //   For convenience we say that any virtual function overrides itself.
      Overriders[CanonM].add(SubobjectNumber,
                             UniqueVirtualMethod(CanonM, SubobjectNumber,
                                                 InVirtualSubobject));
    }
  }
  
  FinalOverriderCollector::~FinalOverriderCollector() {
    for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator
           VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end();
         VO != VOEnd; 
         ++VO)
      delete VO->second;
  }
  
  void 
  CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const {
    FinalOverriderCollector Collector;
    Collector.Collect(this, false, nullptr, FinalOverriders);
  
    // Weed out any final overriders that come from virtual base class
    // subobjects that were hidden by other subobjects along any path.
    // This is the final-overrider variant of C++ [class.member.lookup]p10.
    for (auto &OM : FinalOverriders) {
      for (auto &SO : OM.second) {
        SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second;
        if (Overriding.size() < 2)
          continue;
  
        auto IsHidden = [&Overriding](const UniqueVirtualMethod &M) {
          if (!M.InVirtualSubobject)
            return false;
  
          // We have an overriding method in a virtual base class
          // subobject (or non-virtual base class subobject thereof);
          // determine whether there exists an other overriding method
          // in a base class subobject that hides the virtual base class
          // subobject.
          for (const UniqueVirtualMethod &OP : Overriding)
            if (&M != &OP &&
                OP.Method->getParent()->isVirtuallyDerivedFrom(
                    M.InVirtualSubobject))
              return true;
          return false;
        };
  
        Overriding.erase(
            std::remove_if(Overriding.begin(), Overriding.end(), IsHidden),
            Overriding.end());
      }
    }
  }
  
  static void 
  AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context,
                          CXXIndirectPrimaryBaseSet& Bases) {
    // If the record has a virtual primary base class, add it to our set.
    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
    if (Layout.isPrimaryBaseVirtual())
      Bases.insert(Layout.getPrimaryBase());
  
    for (const auto &I : RD->bases()) {
      assert(!I.getType()->isDependentType() &&
             "Cannot get indirect primary bases for class with dependent bases.");
  
      const CXXRecordDecl *BaseDecl =
        cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
  
      // Only bases with virtual bases participate in computing the
      // indirect primary virtual base classes.
      if (BaseDecl->getNumVBases())
        AddIndirectPrimaryBases(BaseDecl, Context, Bases);
    }
  
  }
  
  void 
  CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const {
    ASTContext &Context = getASTContext();
  
    if (!getNumVBases())
      return;
  
    for (const auto &I : bases()) {
      assert(!I.getType()->isDependentType() &&
             "Cannot get indirect primary bases for class with dependent bases.");
  
      const CXXRecordDecl *BaseDecl =
        cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
  
      // Only bases with virtual bases participate in computing the
      // indirect primary virtual base classes.
      if (BaseDecl->getNumVBases())
        AddIndirectPrimaryBases(BaseDecl, Context, Bases);
    }
  }
  