Refactor the code that walks a C++ inheritance hierarchy, searching

for bases, members, overridden virtual methods, etc. The operations
isDerivedFrom and lookupInBases are now provided by CXXRecordDecl,
rather than by Sema, so that CodeGen and other clients can use them
directly.



git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@83396 91177308-0d34-0410-b5e6-96231b3b80d8

14 files changed, 492 insertions, 657 deletions

diff --git a/lib/AST/CMakeLists.txt b/lib/AST/CMakeLists.txt
index 516bed1057..20e1150b22 100644
--- a/lib/AST/CMakeLists.txt
+++ b/lib/AST/CMakeLists.txt
@@ -4,6 +4,7 @@ add_clang_library(clangAST
   APValue.cpp
   ASTConsumer.cpp
   ASTContext.cpp
+  CXXInheritance.cpp
   Decl.cpp
   DeclBase.cpp
   DeclCXX.cpp
diff --git a/lib/AST/CXXInheritance.cpp b/lib/AST/CXXInheritance.cpp
new file mode 100644
index 0000000000..838835b403
--- /dev/null
+++ b/lib/AST/CXXInheritance.cpp
@@ -0,0 +1,244 @@
+//===------ CXXInheritance.cpp - C++ Inheritance ----------------*- C++ -*-===//
+//
+//                     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/DeclCXX.h"
+#include <algorithm>
+#include <set>
+
+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");
+  
+  std::set<NamedDecl *> Decls;
+  for (CXXBasePaths::paths_iterator Path = begin(), PathEnd = end();
+       Path != PathEnd; ++Path)
+    Decls.insert(*Path->Decls.first);
+  
+  NumDeclsFound = Decls.size();
+  DeclsFound = new NamedDecl * [NumDeclsFound];
+  std::copy(Decls.begin(), Decls.end(), DeclsFound);
+}
+
+CXXBasePaths::decl_iterator CXXBasePaths::found_decls_begin() {
+  if (NumDeclsFound == 0)
+    ComputeDeclsFound();
+  return DeclsFound;
+}
+
+CXXBasePaths::decl_iterator CXXBasePaths::found_decls_end() {
+  if (NumDeclsFound == 0)
+    ComputeDeclsFound();
+  return DeclsFound + 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(QualType BaseType) {
+  assert(BaseType->isCanonical() && "Base type must be the canonical type");
+  assert(BaseType.hasQualifiers() == 0 && "Base type must be unqualified");
+  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();
+  ScratchPath.clear();
+  DetectedVirtual = 0;
+}
+
+/// @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);
+  std::swap(FindAmbiguities, Other.FindAmbiguities);
+  std::swap(RecordPaths, Other.RecordPaths);
+  std::swap(DetectVirtual, Other.DetectVirtual);
+  std::swap(DetectedVirtual, Other.DetectedVirtual);
+}
+
+bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base) {
+  CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
+                     /*DetectVirtual=*/false);
+  return isDerivedFrom(Base, Paths);
+}
+
+bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base, CXXBasePaths &Paths) {
+  if (getCanonicalDecl() == Base->getCanonicalDecl())
+    return false;
+  
+  Paths.setOrigin(this);
+  return lookupInBases(&FindBaseClass, Base->getCanonicalDecl(), Paths);
+}
+
+bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches,
+                                  void *UserData,
+                                  CXXBasePaths &Paths) {
+  bool FoundPath = false;
+  
+  ASTContext &Context = getASTContext();
+  for (base_class_iterator BaseSpec = bases_begin(), BaseSpecEnd = bases_end();
+       BaseSpec != BaseSpecEnd; ++BaseSpec) {
+    // Find the record of the base class subobjects for this type.
+    QualType BaseType = Context.getCanonicalType(BaseSpec->getType());
+    BaseType = BaseType.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 (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 = Paths.ClassSubobjects[BaseType];
+    bool VisitBase = true;
+    bool SetVirtual = false;
+    if (BaseSpec->isVirtual()) {
+      VisitBase = !Subobjects.first;
+      Subobjects.first = true;
+      if (Paths.isDetectingVirtual() && Paths.DetectedVirtual == 0) {
+        // 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.
+        Paths.DetectedVirtual = BaseType->getAs<RecordType>();
+        SetVirtual = true;
+      }
+    } else
+      ++Subobjects.second;
+    
+    if (Paths.isRecordingPaths()) {
+      // Add this base specifier to the current path.
+      CXXBasePathElement Element;
+      Element.Base = &*BaseSpec;
+      Element.Class = this;
+      if (BaseSpec->isVirtual())
+        Element.SubobjectNumber = 0;
+      else
+        Element.SubobjectNumber = Subobjects.second;
+      Paths.ScratchPath.push_back(Element);
+    }
+        
+    if (BaseMatches(BaseSpec, Paths.ScratchPath, UserData)) {
+      // We've found a path that terminates that this base.
+      FoundPath = true;
+      if (Paths.isRecordingPaths()) {
+        // We have a path. Make a copy of it before moving on.
+        Paths.Paths.push_back(Paths.ScratchPath);
+      } else if (!Paths.isFindingAmbiguities()) {
+        // We found a path and we don't care about ambiguities;
+        // return immediately.
+        return FoundPath;
+      }
+    } else if (VisitBase) {
+      CXXRecordDecl *BaseRecord
+        = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>()
+                                ->getDecl());
+      if (BaseRecord->lookupInBases(BaseMatches, UserData, Paths)) {
+        // 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 = true;
+        if (!Paths.isFindingAmbiguities())
+          return FoundPath;
+      }
+    }
+    
+    // Pop this base specifier off the current path (if we're
+    // collecting paths).
+    if (Paths.isRecordingPaths())
+      Paths.ScratchPath.pop_back();
+    // If we set a virtual earlier, and this isn't a path, forget it again.
+    if (SetVirtual && !FoundPath) {
+      Paths.DetectedVirtual = 0;
+    }
+  }
+  
+  return FoundPath;
+}
+
+bool CXXRecordDecl::FindBaseClass(CXXBaseSpecifier *Specifier, 
+                                  CXXBasePath &Path,
+                                  void *BaseRecord) {
+  assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord &&
+         "User data for FindBaseClass is not canonical!");
+  return Specifier->getType()->getAs<RecordType>()->getDecl()
+           ->getCanonicalDecl() == BaseRecord;
+}
+
+bool CXXRecordDecl::FindTagMember(CXXBaseSpecifier *Specifier, 
+                                  CXXBasePath &Path,
+                                  void *Name) {
+  RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
+
+  DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
+  for (Path.Decls = BaseRecord->lookup(N);
+       Path.Decls.first != Path.Decls.second;
+       ++Path.Decls.first) {
+    if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
+      return true;
+  }
+
+  return false;
+}
+
+bool CXXRecordDecl::FindOrdinaryMember(CXXBaseSpecifier *Specifier, 
+                                       CXXBasePath &Path,
+                                       void *Name) {
+  RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
+  
+  const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member;
+  DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
+  for (Path.Decls = BaseRecord->lookup(N);
+       Path.Decls.first != Path.Decls.second;
+       ++Path.Decls.first) {
+    if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS))
+      return true;
+  }
+  
+  return false;
+}
+
+bool CXXRecordDecl::FindNestedNameSpecifierMember(CXXBaseSpecifier *Specifier, 
+                                                  CXXBasePath &Path,
+                                                  void *Name) {
+  RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
+  
+  DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
+  for (Path.Decls = BaseRecord->lookup(N);
+       Path.Decls.first != Path.Decls.second;
+       ++Path.Decls.first) {
+    // FIXME: Refactor the "is it a nested-name-specifier?" check
+    if (isa<TypedefDecl>(*Path.Decls.first) ||
+        (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
+      return true;
+  }
+  
+  return false;
+}
\ No newline at end of file
diff --git a/lib/Sema/CMakeLists.txt b/lib/Sema/CMakeLists.txt
index d766fbb01c..1c594fe7a0 100644
--- a/lib/Sema/CMakeLists.txt
+++ b/lib/Sema/CMakeLists.txt
@@ -19,7 +19,6 @@ add_clang_library(clangSema
   SemaExpr.cpp
   SemaExprCXX.cpp
   SemaExprObjC.cpp
-  SemaInherit.cpp
   SemaInit.cpp
   SemaLookup.cpp
   SemaOverload.cpp
diff --git a/lib/Sema/Sema.h b/lib/Sema/Sema.h
index 7354d7cf94..9ddabde869 100644
--- a/lib/Sema/Sema.h
+++ b/lib/Sema/Sema.h
@@ -90,8 +90,7 @@ namespace clang {
   class ObjCPropertyDecl;
   class ObjCContainerDecl;
   class FunctionProtoType;
-  class BasePaths;
-  struct MemberLookupCriteria;
+  class CXXBasePaths;
   class CXXTemporary;
 
 /// BlockSemaInfo - When a block is being parsed, this contains information
@@ -1066,7 +1065,7 @@ public:
       /// pointers used to reconstruct DeclContext::lookup_iterators.
       OverloadedDeclFromDeclContext,
 
-      /// First is a pointer to a BasePaths structure, which is owned
+      /// First is a pointer to a CXXBasePaths structure, which is owned
       /// by the LookupResult. Last is non-zero to indicate that the
       /// ambiguity is caused by two names found in base class
       /// subobjects of different types.
@@ -1085,7 +1084,7 @@ public:
     /// IdentifierResolver::iterator (if StoredKind ==
     /// OverloadedDeclFromIdResolver), a DeclContext::lookup_iterator
     /// (if StoredKind == OverloadedDeclFromDeclContext), or a
-    /// BasePaths pointer (if StoredKind == AmbiguousLookupStoresBasePaths).
+    /// CXXBasePaths pointer (if StoredKind == AmbiguousLookupStoresBasePaths).
     mutable uintptr_t First;
 
     /// The last lookup result, whose contents depend on the kind of
@@ -1168,7 +1167,8 @@ public:
                                            DeclContext::lookup_iterator F,
                                            DeclContext::lookup_iterator L);
 
-    static LookupResult CreateLookupResult(ASTContext &Context, BasePaths *Paths,
+    static LookupResult CreateLookupResult(ASTContext &Context, 
+                                           CXXBasePaths *Paths,
                                            bool DifferentSubobjectTypes) {
       LookupResult Result;
       Result.StoredKind = AmbiguousLookupStoresBasePaths;
@@ -1209,7 +1209,7 @@ public:
 
     NamedDecl* getAsDecl() const;
 
-    BasePaths *getBasePaths() const;
+    CXXBasePaths *getBasePaths() const;
 
     /// \brief Iterate over the results of name lookup.
     ///
@@ -2316,9 +2316,8 @@ public:
                                    unsigned NumBases);
 
   bool IsDerivedFrom(QualType Derived, QualType Base);
-  bool IsDerivedFrom(QualType Derived, QualType Base, BasePaths &Paths);
-  bool LookupInBases(CXXRecordDecl *Class, const MemberLookupCriteria& Criteria,
-                     BasePaths &Paths);
+  bool IsDerivedFrom(QualType Derived, QualType Base, CXXBasePaths &Paths);
+  
   bool CheckDerivedToBaseConversion(QualType Derived, QualType Base,
                                     SourceLocation Loc, SourceRange Range);
   bool CheckDerivedToBaseConversion(QualType Derived, QualType Base,
@@ -2327,7 +2326,7 @@ public:
                                     SourceLocation Loc, SourceRange Range,
                                     DeclarationName Name);
 
-  std::string getAmbiguousPathsDisplayString(BasePaths &Paths);
+  std::string getAmbiguousPathsDisplayString(CXXBasePaths &Paths);
 
   /// CheckOverridingFunctionReturnType - Checks whether the return types are
   /// covariant, according to C++ [class.virtual]p5.
@@ -2348,12 +2347,12 @@ public:
                                 AccessSpecifier LexicalAS);
 
   const CXXBaseSpecifier *FindInaccessibleBase(QualType Derived, QualType Base,
-                                               BasePaths &Paths,
+                                               CXXBasePaths &Paths,
                                                bool NoPrivileges = false);
 
   bool CheckBaseClassAccess(QualType Derived, QualType Base,
                             unsigned InaccessibleBaseID,
-                            BasePaths& Paths, SourceLocation AccessLoc,
+                            CXXBasePaths& Paths, SourceLocation AccessLoc,
                             DeclarationName Name);
 
 
diff --git a/lib/Sema/SemaAccess.cpp b/lib/Sema/SemaAccess.cpp
index e1a7378061..21f83a560d 100644
--- a/lib/Sema/SemaAccess.cpp
+++ b/lib/Sema/SemaAccess.cpp
@@ -11,9 +11,10 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "SemaInherit.h"
 #include "Sema.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/CXXInheritance.h"
+#include "clang/AST/DeclCXX.h"
 using namespace clang;
 
 /// SetMemberAccessSpecifier - Set the access specifier of a member.
@@ -47,7 +48,7 @@ bool Sema::SetMemberAccessSpecifier(NamedDecl *MemberDecl,
 /// inaccessible. If @p NoPrivileges is true, special access rights (members
 /// and friends) are not considered.
 const CXXBaseSpecifier *Sema::FindInaccessibleBase(
-    QualType Derived, QualType Base, BasePaths &Paths, bool NoPrivileges) {
+    QualType Derived, QualType Base, CXXBasePaths &Paths, bool NoPrivileges) {
   Base = Context.getCanonicalType(Base).getUnqualifiedType();
   assert(!Paths.isAmbiguous(Base) &&
          "Can't check base class access if set of paths is ambiguous");
@@ -61,12 +62,12 @@ const CXXBaseSpecifier *Sema::FindInaccessibleBase(
   if (CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(getCurFunctionDecl()))
     CurrentClassDecl = MD->getParent();
 
-  for (BasePaths::paths_iterator Path = Paths.begin(), PathsEnd = Paths.end();
+  for (CXXBasePaths::paths_iterator Path = Paths.begin(), PathsEnd = Paths.end();
       Path != PathsEnd; ++Path) {
 
     bool FoundInaccessibleBase = false;
 
-    for (BasePath::const_iterator Element = Path->begin(),
+    for (CXXBasePath::const_iterator Element = Path->begin(),
          ElementEnd = Path->end(); Element != ElementEnd; ++Element) {
       const CXXBaseSpecifier *Base = Element->Base;
 
@@ -106,7 +107,7 @@ const CXXBaseSpecifier *Sema::FindInaccessibleBase(
 /// and report an error if it can't. [class.access.base]
 bool Sema::CheckBaseClassAccess(QualType Derived, QualType Base,
                                 unsigned InaccessibleBaseID,
-                                BasePaths &Paths, SourceLocation AccessLoc,
+                                CXXBasePaths &Paths, SourceLocation AccessLoc,
                                 DeclarationName Name) {
 
   if (!getLangOptions().AccessControl)
diff --git a/lib/Sema/SemaCXXCast.cpp b/lib/Sema/SemaCXXCast.cpp
index 9822a44b0f..69d1f92a08 100644
--- a/lib/Sema/SemaCXXCast.cpp
+++ b/lib/Sema/SemaCXXCast.cpp
@@ -12,9 +12,9 @@
 //===----------------------------------------------------------------------===//
 
 #include "Sema.h"
-#include "SemaInherit.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/CXXInheritance.h"
 #include "clang/Basic/PartialDiagnostic.h"
 #include "llvm/ADT/SmallVector.h"
 #include <set>
@@ -610,8 +610,8 @@ TryStaticDowncast(Sema &Self, QualType SrcType, QualType DestType,
     return TC_NotApplicable;
   }
 
-  BasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/!CStyle,
-                  /*DetectVirtual=*/true);
+  CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/!CStyle,
+                     /*DetectVirtual=*/true);
   if (!Self.IsDerivedFrom(DestType, SrcType, Paths)) {
     return TC_NotApplicable;
   }
@@ -652,13 +652,14 @@ TryStaticDowncast(Sema &Self, QualType SrcType, QualType DestType,
     }
     std::string PathDisplayStr;
     std::set<unsigned> DisplayedPaths;
-    for (BasePaths::paths_iterator PI = Paths.begin(), PE = Paths.end();
+    for (CXXBasePaths::paths_iterator PI = Paths.begin(), PE = Paths.end();
          PI != PE; ++PI) {
       if (DisplayedPaths.insert(PI->back().SubobjectNumber).second) {
         // We haven't displayed a path to this particular base
         // class subobject yet.
         PathDisplayStr += "\n    ";
-        for (BasePath::const_reverse_iterator EI = PI->rbegin(),EE = PI->rend();
+        for (CXXBasePath::const_reverse_iterator EI = PI->rbegin(),
+                                                 EE = PI->rend();
              EI != EE; ++EI)
           PathDisplayStr += EI->Base->getType().getAsString() + " -> ";
         PathDisplayStr += DestType.getAsString();
@@ -720,7 +721,7 @@ TryStaticMemberPointerUpcast(Sema &Self, QualType SrcType, QualType DestType,
   // B base of D
   QualType SrcClass(SrcMemPtr->getClass(), 0);
   QualType DestClass(DestMemPtr->getClass(), 0);
-  BasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/!CStyle,
+  CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/!CStyle,
                   /*DetectVirtual=*/true);
   if (!Self.IsDerivedFrom(SrcClass, DestClass, Paths)) {
     return TC_NotApplicable;
diff --git a/lib/Sema/SemaDecl.cpp b/lib/Sema/SemaDecl.cpp
index 8e69caae5c..a1fcf89c54 100644
--- a/lib/Sema/SemaDecl.cpp
+++ b/lib/Sema/SemaDecl.cpp
@@ -12,11 +12,11 @@
 //===----------------------------------------------------------------------===//
 
 #include "Sema.h"
-#include "SemaInherit.h"
 #include "clang/AST/APValue.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/Analysis/CFG.h"
+#include "clang/AST/CXXInheritance.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/ExprCXX.h"
@@ -2455,6 +2455,35 @@ static bool isUsingDecl(Decl *D) {
   return isa<UsingDecl>(D) || isa<UnresolvedUsingDecl>(D);
 }
 
+/// \brief Data used with FindOverriddenMethod
+struct FindOverriddenMethodData {
+  Sema *S;
+  CXXMethodDecl *Method;
+};
+
+/// \brief Member lookup function that determines whether a given C++
+/// method overrides a method in a base class, to be used with
+/// CXXRecordDecl::lookupInBases().
+static bool FindOverriddenMethod(CXXBaseSpecifier *Specifier,
+                                 CXXBasePath &Path,
+                                 void *UserData) {
+  RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
+  
+  FindOverriddenMethodData *Data 
+    = reinterpret_cast<FindOverriddenMethodData*>(UserData);
+  for (Path.Decls = BaseRecord->lookup(Data->Method->getDeclName());
+       Path.Decls.first != Path.Decls.second;
+       ++Path.Decls.first) {
+    if (CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(*Path.Decls.first)) {
+      OverloadedFunctionDecl::function_iterator MatchedDecl;
+      if (MD->isVirtual() && !Data->S->IsOverload(Data->Method, MD, MatchedDecl))
+        return true;
+    }
+  }
+  
+  return false;
+}
+
 NamedDecl*
 Sema::ActOnFunctionDeclarator(Scope* S, Declarator& D, DeclContext* DC,
                               QualType R, DeclaratorInfo *DInfo,
@@ -2690,11 +2719,13 @@ Sema::ActOnFunctionDeclarator(Scope* S, Declarator& D, DeclContext* DC,
 
   if (CXXMethodDecl *NewMD = dyn_cast<CXXMethodDecl>(NewFD)) {
     // Look for virtual methods in base classes that this method might override.
-
-    BasePaths Paths;
-    if (LookupInBases(cast<CXXRecordDecl>(DC),
-                      MemberLookupCriteria(NewMD), Paths)) {
-      for (BasePaths::decl_iterator I = Paths.found_decls_begin(),
+    CXXBasePaths Paths;
+    FindOverriddenMethodData Data;
+    Data.Method = NewMD;
+    Data.S = this;
+    if (cast<CXXRecordDecl>(DC)->lookupInBases(&FindOverriddenMethod, &Data,
+                                                Paths)) {
+      for (CXXBasePaths::decl_iterator I = Paths.found_decls_begin(),
            E = Paths.found_decls_end(); I != E; ++I) {
         if (CXXMethodDecl *OldMD = dyn_cast<CXXMethodDecl>(*I)) {
           if (!CheckOverridingFunctionReturnType(NewMD, OldMD) &&
diff --git a/lib/Sema/SemaDeclCXX.cpp b/lib/Sema/SemaDeclCXX.cpp
index 23a6b58a9c..b33f8cc835 100644
--- a/lib/Sema/SemaDeclCXX.cpp
+++ b/lib/Sema/SemaDeclCXX.cpp
@@ -12,9 +12,9 @@
 //===----------------------------------------------------------------------===//
 
 #include "Sema.h"
-#include "SemaInherit.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/CXXInheritance.h"
 #include "clang/AST/DeclVisitor.h"
 #include "clang/AST/TypeOrdering.h"
 #include "clang/AST/StmtVisitor.h"
@@ -25,6 +25,7 @@
 #include "llvm/Support/Compiler.h"
 #include <algorithm> // for std::equal
 #include <map>
+#include <set>
 
 using namespace clang;
 
@@ -607,6 +608,139 @@ void Sema::ActOnBaseSpecifiers(DeclPtrTy ClassDecl, BaseTy **Bases,
                        (CXXBaseSpecifier**)(Bases), NumBases);
 }
 
+/// \brief Determine whether the type \p Derived is a C++ class that is
+/// derived from the type \p Base.
+bool Sema::IsDerivedFrom(QualType Derived, QualType Base) {
+  if (!getLangOptions().CPlusPlus)
+    return false;
+    
+  const RecordType *DerivedRT = Derived->getAs<RecordType>();
+  if (!DerivedRT)
+    return false;
+  
+  const RecordType *BaseRT = Base->getAs<RecordType>();
+  if (!BaseRT)
+    return false;
+  
+  CXXRecordDecl *DerivedRD = cast<CXXRecordDecl>(DerivedRT->getDecl());
+  CXXRecordDecl *BaseRD = cast<CXXRecordDecl>(BaseRT->getDecl());
+  return DerivedRD->isDerivedFrom(BaseRD);
+}
+
+/// \brief Determine whether the type \p Derived is a C++ class that is
+/// derived from the type \p Base.
+bool Sema::IsDerivedFrom(QualType Derived, QualType Base, CXXBasePaths &Paths) {
+  if (!getLangOptions().CPlusPlus)
+    return false;
+  
+  const RecordType *DerivedRT = Derived->getAs<RecordType>();
+  if (!DerivedRT)
+    return false;
+  
+  const RecordType *BaseRT = Base->getAs<RecordType>();
+  if (!BaseRT)
+    return false;
+  
+  CXXRecordDecl *DerivedRD = cast<CXXRecordDecl>(DerivedRT->getDecl());
+  CXXRecordDecl *BaseRD = cast<CXXRecordDecl>(BaseRT->getDecl());
+  return DerivedRD->isDerivedFrom(BaseRD, Paths);
+}
+
+/// CheckDerivedToBaseConversion - Check whether the Derived-to-Base
+/// conversion (where Derived and Base are class types) is
+/// well-formed, meaning that the conversion is unambiguous (and
+/// that all of the base classes are accessible). Returns true
+/// and emits a diagnostic if the code is ill-formed, returns false
+/// otherwise. Loc is the location where this routine should point to
+/// if there is an error, and Range is the source range to highlight
+/// if there is an error.
+bool
+Sema::CheckDerivedToBaseConversion(QualType Derived, QualType Base,
+                                   unsigned InaccessibleBaseID,
+                                   unsigned AmbigiousBaseConvID,
+                                   SourceLocation Loc, SourceRange Range,
+                                   DeclarationName Name) {
+  // First, determine whether the path from Derived to Base is
+  // ambiguous. This is slightly more expensive than checking whether
+  // the Derived to Base conversion exists, because here we need to
+  // explore multiple paths to determine if there is an ambiguity.
+  CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true,
+                     /*DetectVirtual=*/false);
+  bool DerivationOkay = IsDerivedFrom(Derived, Base, Paths);
+  assert(DerivationOkay &&
+         "Can only be used with a derived-to-base conversion");
+  (void)DerivationOkay;
+  
+  if (!Paths.isAmbiguous(Context.getCanonicalType(Base).getUnqualifiedType())) {
+    // Check that the base class can be accessed.
+    return CheckBaseClassAccess(Derived, Base, InaccessibleBaseID, Paths, Loc,
+                                Name);
+  }
+  
+  // We know that the derived-to-base conversion is ambiguous, and
+  // we're going to produce a diagnostic. Perform the derived-to-base
+  // search just one more time to compute all of the possible paths so
+  // that we can print them out. This is more expensive than any of
+  // the previous derived-to-base checks we've done, but at this point
+  // performance isn't as much of an issue.
+  Paths.clear();
+  Paths.setRecordingPaths(true);
+  bool StillOkay = IsDerivedFrom(Derived, Base, Paths);
+  assert(StillOkay && "Can only be used with a derived-to-base conversion");
+  (void)StillOkay;
+  
+  // Build up a textual representation of the ambiguous paths, e.g.,
+  // D -> B -> A, that will be used to illustrate the ambiguous
+  // conversions in the diagnostic. We only print one of the paths
+  // to each base class subobject.
+  std::string PathDisplayStr = getAmbiguousPathsDisplayString(Paths);
+  
+  Diag(Loc, AmbigiousBaseConvID)
+  << Derived << Base << PathDisplayStr << Range << Name;
+  return true;
+}
+
+bool
+Sema::CheckDerivedToBaseConversion(QualType Derived, QualType Base,
+                                   SourceLocation Loc, SourceRange Range) {
+  return CheckDerivedToBaseConversion(Derived, Base,
+                                      diag::err_conv_to_inaccessible_base,
+                                      diag::err_ambiguous_derived_to_base_conv,
+                                      Loc, Range, DeclarationName());
+}
+
+
+/// @brief Builds a string representing ambiguous paths from a
+/// specific derived class to different subobjects of the same base
+/// class.
+///
+/// This function builds a string that can be used in error messages
+/// to show the different paths that one can take through the
+/// inheritance hierarchy to go from the derived class to different
+/// subobjects of a base class. The result looks something like this:
+/// @code
+/// struct D -> struct B -> struct A
+/// struct D -> struct C -> struct A
+/// @endcode
+std::string Sema::getAmbiguousPathsDisplayString(CXXBasePaths &Paths) {
+  std::string PathDisplayStr;
+  std::set<unsigned> DisplayedPaths;
+  for (CXXBasePaths::paths_iterator Path = Paths.begin();
+       Path != Paths.end(); ++Path) {
+    if (DisplayedPaths.insert(Path->back().SubobjectNumber).second) {
+      // We haven't displayed a path to this particular base
+      // class subobject yet.
+      PathDisplayStr += "\n    ";
+      PathDisplayStr += Context.getTypeDeclType(Paths.getOrigin()).getAsString();
+      for (CXXBasePath::const_iterator Element = Path->begin();
+           Element != Path->end(); ++Element)
+        PathDisplayStr += " -> " + Element->Base->getType().getAsString();
+    }
+  }
+  
+  return PathDisplayStr;
+}
+
 //===----------------------------------------------------------------------===//
 // C++ class member Handling
 //===----------------------------------------------------------------------===//
@@ -919,10 +1053,10 @@ Sema::BuildBaseInitializer(QualType BaseType, Expr **Args,
     if (!DirectBaseSpec || !DirectBaseSpec->isVirtual()) {
       // We haven't found a base yet; search the class hierarchy for a
       // virtual base class.
-      BasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true,
-                      /*DetectVirtual=*/false);
+      CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true,
+                         /*DetectVirtual=*/false);
       if (IsDerivedFrom(Context.getTypeDeclType(ClassDecl), BaseType, Paths)) {
-        for (BasePaths::paths_iterator Path = Paths.begin();
+        for (CXXBasePaths::paths_iterator Path = Paths.begin();
              Path != Paths.end(); ++Path) {
           if (Path->back().Base->isVirtual()) {
             VirtualBaseSpec = Path->back().Base;
diff --git a/lib/Sema/SemaExprCXX.cpp b/lib/Sema/SemaExprCXX.cpp
index 4e9d7dedaf..86a5ad88cc 100644
--- a/lib/Sema/SemaExprCXX.cpp
+++ b/lib/Sema/SemaExprCXX.cpp
@@ -11,9 +11,9 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "SemaInherit.h"
 #include "Sema.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/CXXInheritance.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/Basic/PartialDiagnostic.h"
 #include "clang/Basic/TargetInfo.h"
@@ -1322,8 +1322,8 @@ QualType Sema::CheckPointerToMemberOperands(
 
   if (Context.getCanonicalType(Class).getUnqualifiedType() !=
       Context.getCanonicalType(LType).getUnqualifiedType()) {
-    BasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/false,
-                    /*DetectVirtual=*/false);
+    CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/false,
+                       /*DetectVirtual=*/false);
     // FIXME: Would it be useful to print full ambiguity paths, or is that
     // overkill?
     if (!IsDerivedFrom(LType, Class, Paths) ||
diff --git a/lib/Sema/SemaInherit.cpp b/lib/Sema/SemaInherit.cpp
deleted file mode 100644
index 8f932ac7d1..0000000000
--- a/lib/Sema/SemaInherit.cpp
+++ /dev/null
@@ -1,353 +0,0 @@
-//===---- SemaInherit.cpp - C++ Inheritance ---------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file provides Sema routines for C++ inheritance semantics,
-// including searching the inheritance hierarchy.
-//
-//===----------------------------------------------------------------------===//
-
-#include "SemaInherit.h"
-#include "Sema.h"
-#include "clang/AST/ASTContext.h"
-#include "clang/AST/DeclCXX.h"
-#include "clang/AST/Type.h"
-#include "clang/AST/TypeOrdering.h"
-#include <algorithm>
-#include <memory>
-#include <set>
-#include <string>
-
-using namespace clang;
-
-/// \brief Computes the set of declarations referenced by these base
-/// paths.
-void BasePaths::ComputeDeclsFound() {
-  assert(NumDeclsFound == 0 && !DeclsFound &&
-         "Already computed the set of declarations");
-
-  std::set<NamedDecl *> Decls;
-  for (BasePaths::paths_iterator Path = begin(), PathEnd = end();
-       Path != PathEnd; ++Path)
-    Decls.insert(*Path->Decls.first);
-
-  NumDeclsFound = Decls.size();
-  DeclsFound = new NamedDecl * [NumDeclsFound];
-  std::copy(Decls.begin(), Decls.end(), DeclsFound);
-}
-
-BasePaths::decl_iterator BasePaths::found_decls_begin() {
-  if (NumDeclsFound == 0)
-    ComputeDeclsFound();
-  return DeclsFound;
-}
-
-BasePaths::decl_iterator BasePaths::found_decls_end() {
-  if (NumDeclsFound == 0)
-    ComputeDeclsFound();
-  return DeclsFound + 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 BasePaths::isAmbiguous(QualType BaseType) {
-  assert(BaseType->isCanonical() && "Base type must be the canonical type");
-  assert(BaseType.hasQualifiers() == 0 && "Base type must be unqualified");
-  std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
-  return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
-}
-
-/// clear - Clear out all prior path information.
-void BasePaths::clear() {
-  Paths.clear();
-  ClassSubobjects.clear();
-  ScratchPath.clear();
-  DetectedVirtual = 0;
-}
-
-/// @brief Swaps the contents of this BasePaths structure with the
-/// contents of Other.
-void BasePaths::swap(BasePaths &Other) {
-  std::swap(Origin, Other.Origin);