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

17 files changed, 825 insertions, 661 deletions

diff --git a/include/clang/AST/CXXInheritance.h b/include/clang/AST/CXXInheritance.h
new file mode 100644
index 0000000000..2fc48abe04
--- /dev/null
+++ b/include/clang/AST/CXXInheritance.h
@@ -0,0 +1,212 @@
+//===------ CXXInheritance.h - 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.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_CXXINHERITANCE_H
+#define LLVM_CLANG_AST_CXXINHERITANCE_H
+
+#include "clang/AST/DeclarationName.h"
+#include "clang/AST/DeclBase.h"
+#include "clang/AST/Type.h"
+#include "clang/AST/TypeOrdering.h"
+#include "llvm/ADT/SmallVector.h"
+#include <list>
+#include <map>
+#include <cassert>
+
+namespace clang {
+  
+class CXXBaseSpecifier;
+class CXXMethodDecl;
+class CXXRecordDecl;
+class NamedDecl;
+  
+/// \brief Represents an element in a path from a derived class to a
+/// base class. 
+/// 
+/// Each step in the path references the link from a
+/// derived class to one of its direct base classes, along with a
+/// base "number" that identifies which base subobject of the
+/// original derived class we are referencing.
+struct CXXBasePathElement {
+  /// \brief The base specifier that states the link from a derived
+  /// class to a base class, which will be followed by this base
+  /// path element.
+  const CXXBaseSpecifier *Base;
+  
+  /// \brief The record decl of the class that the base is a base of.
+  const CXXRecordDecl *Class;
+  
+  /// \brief Identifies which base class subobject (of type
+  /// \c Base->getType()) this base path element refers to. 
+  ///
+  /// This value is only valid if \c !Base->isVirtual(), because there
+  /// is no base numbering for the zero or one virtual bases of a
+  /// given type.
+  int SubobjectNumber;
+};
+
+/// \brief Represents a path from a specific derived class
+/// (which is not represented as part of the path) to a particular
+/// (direct or indirect) base class subobject.
+///
+/// Individual elements in the path are described by the \c CXXBasePathElement 
+/// structure, which captures both the link from a derived class to one of its
+/// direct bases and identification describing which base class
+/// subobject is being used.
+struct CXXBasePath : public llvm::SmallVector<CXXBasePathElement, 4> {
+  /// \brief The set of declarations found inside this base class
+  /// subobject.
+  DeclContext::lookup_result Decls;
+};
+
+/// BasePaths - Represents the set of paths from a derived class to
+/// one of its (direct or indirect) bases. For example, given the
+/// following class hierachy:
+///
+/// @code
+/// class A { };
+/// class B : public A { };
+/// class C : public A { };
+/// class D : public B, public C{ };
+/// @endcode
+///
+/// There are two potential BasePaths to represent paths from D to a
+/// base subobject of type A. One path is (D,0) -> (B,0) -> (A,0)
+/// and another is (D,0)->(C,0)->(A,1). These two paths actually
+/// refer to two different base class subobjects of the same type,
+/// so the BasePaths object refers to an ambiguous path. On the
+/// other hand, consider the following class hierarchy:
+///
+/// @code
+/// class A { };
+/// class B : public virtual A { };
+/// class C : public virtual A { };
+/// class D : public B, public C{ };
+/// @endcode
+///
+/// Here, there are two potential BasePaths again, (D, 0) -> (B, 0)
+/// -> (A,v) and (D, 0) -> (C, 0) -> (A, v), but since both of them
+/// refer to the same base class subobject of type A (the virtual
+/// one), there is no ambiguity.
+class CXXBasePaths {
+  /// \brief The type from which this search originated.
+  CXXRecordDecl *Origin;
+  
+  /// Paths - The actual set of paths that can be taken from the
+  /// derived class to the same base class.
+  std::list<CXXBasePath> Paths;
+  
+  /// ClassSubobjects - Records the class subobjects for each class
+  /// type that we've seen. The first element in the pair says
+  /// whether we found a path to a virtual base for that class type,
+  /// while the element contains the number of non-virtual base
+  /// class subobjects for that class type. The key of the map is
+  /// the cv-unqualified canonical type of the base class subobject.
+  std::map<QualType, std::pair<bool, unsigned>, QualTypeOrdering>
+    ClassSubobjects;
+  
+  /// FindAmbiguities - Whether Sema::IsDerivedFrom should try find
+  /// ambiguous paths while it is looking for a path from a derived
+  /// type to a base type.
+  bool FindAmbiguities;
+  
+  /// RecordPaths - Whether Sema::IsDerivedFrom should record paths
+  /// while it is determining whether there are paths from a derived
+  /// type to a base type.
+  bool RecordPaths;
+  
+  /// DetectVirtual - Whether Sema::IsDerivedFrom should abort the search
+  /// if it finds a path that goes across a virtual base. The virtual class
+  /// is also recorded.
+  bool DetectVirtual;
+  
+  /// ScratchPath - A BasePath that is used by Sema::IsDerivedFrom
+  /// to help build the set of paths.
+  CXXBasePath ScratchPath;
+  
+  /// DetectedVirtual - The base class that is virtual.
+  const RecordType *DetectedVirtual;
+  
+  /// \brief Array of the declarations that have been found. This
+  /// array is constructed only if needed, e.g., to iterate over the
+  /// results within LookupResult.
+  NamedDecl **DeclsFound;
+  unsigned NumDeclsFound;
+  
+  friend class CXXRecordDecl;
+  
+  void ComputeDeclsFound();
+  
+public:
+  typedef std::list<CXXBasePath>::const_iterator paths_iterator;
+  typedef NamedDecl **decl_iterator;
+  
+  /// BasePaths - Construct a new BasePaths structure to record the
+  /// paths for a derived-to-base search.
+  explicit CXXBasePaths(bool FindAmbiguities = true,
+                        bool RecordPaths = true,
+                        bool DetectVirtual = true)
+    : FindAmbiguities(FindAmbiguities), RecordPaths(RecordPaths),
+      DetectVirtual(DetectVirtual), DetectedVirtual(0), DeclsFound(0),
+      NumDeclsFound(0) { }
+  
+  ~CXXBasePaths() { delete [] DeclsFound; }
+  
+  paths_iterator begin() const { return Paths.begin(); }
+  paths_iterator end()   const { return Paths.end(); }
+  
+  CXXBasePath&       front()       { return Paths.front(); }
+  const CXXBasePath& front() const { return Paths.front(); }
+  
+  decl_iterator found_decls_begin();
+  decl_iterator found_decls_end();
+  
+  /// \brief Determine whether the path from the most-derived type to the
+  /// given base type is ambiguous (i.e., it refers to multiple subobjects of
+  /// the same base type).
+  bool isAmbiguous(QualType BaseType);
+  
+  /// \brief Whether we are finding multiple paths to detect ambiguities.
+  bool isFindingAmbiguities() const { return FindAmbiguities; }
+  
+  /// \brief Whether we are recording paths.
+  bool isRecordingPaths() const { return RecordPaths; }
+  
+  /// \brief Specify whether we should be recording paths or not.
+  void setRecordingPaths(bool RP) { RecordPaths = RP; }
+  
+  /// \brief Whether we are detecting virtual bases.
+  bool isDetectingVirtual() const { return DetectVirtual; }
+  
+  /// \brief The virtual base discovered on the path (if we are merely
+  /// detecting virtuals).
+  const RecordType* getDetectedVirtual() const {
+    return DetectedVirtual;
+  }
+  
+  /// \brief Retrieve the type from which this base-paths search
+  /// began
+  CXXRecordDecl *getOrigin() const { return Origin; }
+  void setOrigin(CXXRecordDecl *Rec) { Origin = Rec; }
+  
+  /// \brief Clear the base-paths results.
+  void clear();
+  
+  /// \brief Swap this data structure's contents with another CXXBasePaths 
+  /// object.
+  void swap(CXXBasePaths &Other);
+};
+  
+} // end namespace clang
+
+#endif
\ No newline at end of file
diff --git a/include/clang/AST/DeclCXX.h b/include/clang/AST/DeclCXX.h
index 7ba6d2520d..4038fe6081 100644
--- a/include/clang/AST/DeclCXX.h
+++ b/include/clang/AST/DeclCXX.h
@@ -21,13 +21,16 @@
 namespace clang {
 
 class ClassTemplateDecl;
-class CXXRecordDecl;
+class ClassTemplateSpecializationDecl;
+class CXXBasePath;
+class CXXBasePaths;
 class CXXConstructorDecl;
-class CXXDestructorDecl;
 class CXXConversionDecl;
+class CXXDestructorDecl;
 class CXXMethodDecl;
-class ClassTemplateSpecializationDecl;
-
+class CXXRecordDecl;
+class CXXMemberLookupCriteria;
+  
 /// \brief Represents any kind of function declaration, whether it is a
 /// concrete function or a function template.
 class AnyFunctionDecl {
@@ -739,6 +742,114 @@ public:
     return dyn_cast<FunctionDecl>(getDeclContext());
   }
 
+  /// \brief Determine whether this class is derived from the class \p Base.
+  ///
+  /// This routine only determines whether this class is derived from \p Base,
+  /// but does not account for factors that may make a Derived -> Base class
+  /// ill-formed, such as private/protected inheritance or multiple, ambiguous
+  /// base class subobjects.
+  ///
+  /// \param Base the base class we are searching for.
+  ///
+  /// \returns true if this class is derived from Base, false otherwise.
+  bool isDerivedFrom(CXXRecordDecl *Base);
+  
+  /// \brief Determine whether this class is derived from the type \p Base.
+  ///
+  /// This routine only determines whether this class is derived from \p Base,
+  /// but does not account for factors that may make a Derived -> Base class
+  /// ill-formed, such as private/protected inheritance or multiple, ambiguous
+  /// base class subobjects.
+  ///
+  /// \param Base the base class we are searching for.
+  ///
+  /// \param Paths will contain the paths taken from the current class to the
+  /// given \p Base class.
+  ///
+  /// \returns true if this class is derived from Base, false otherwise.
+  ///
+  /// \todo add a separate paramaeter to configure IsDerivedFrom, rather than 
+  /// tangling input and output in \p Paths  
+  bool isDerivedFrom(CXXRecordDecl *Base, CXXBasePaths &Paths);
+  
+  /// \brief Function type used by lookupInBases() to determine whether a 
+  /// specific base class subobject matches the lookup criteria.
+  ///
+  /// \param Specifier the base-class specifier that describes the inheritance 
+  /// from the base class we are trying to match.
+  ///
+  /// \param Path the current path, from the most-derived class down to the 
+  /// base named by the \p Specifier.
+  ///
+  /// \param UserData a single pointer to user-specified data, provided to
+  /// lookupInBases().
+  ///
+  /// \returns true if this base matched the search criteria, false otherwise.
+  typedef bool BaseMatchesCallback(CXXBaseSpecifier *Specifier,
+                                   CXXBasePath &Path,
+                                   void *UserData);
+  
+  /// \brief Look for entities within the base classes of this C++ class,
+  /// transitively searching all base class subobjects.
+  ///
+  /// This routine uses the callback function \p BaseMatches to find base 
+  /// classes meeting some search criteria, walking all base class subobjects
+  /// and populating the given \p Paths structure with the paths through the 
+  /// inheritance hierarchy that resulted in a match. On a successful search,
+  /// the \p Paths structure can be queried to retrieve the matching paths and
+  /// to determine if there were any ambiguities.
+  ///
+  /// \param BaseMatches callback function used to determine whether a given
+  /// base matches the user-defined search criteria.
+  ///
+  /// \param UserData user data pointer that will be provided to \p BaseMatches.
+  ///
+  /// \param Paths used to record the paths from this class to its base class
+  /// subobjects that match the search criteria.
+  ///
+  /// \returns true if there exists any path from this class to a base class
+  /// subobject that matches the search criteria.
+  bool lookupInBases(BaseMatchesCallback *BaseMatches, void *UserData,
+                     CXXBasePaths &Paths);
+  
+  /// \brief Base-class lookup callback that determines whether the given
+  /// base class specifier refers to a specific class declaration.
+  ///
+  /// This callback can be used with \c lookupInBases() to determine whether
+  /// a given derived class has is a base class subobject of a particular type.
+  /// The user data pointer should refer to the canonical CXXRecordDecl of the
+  /// base class that we are searching for.
+  static bool FindBaseClass(CXXBaseSpecifier *Specifier, CXXBasePath &Path,
+                            void *BaseRecord);
+  
+  /// \brief Base-class lookup callback that determines whether there exists
+  /// a tag with the given name.
+  ///
+  /// This callback can be used with \c lookupInBases() to find tag members
+  /// of the given name within a C++ class hierarchy. The user data pointer
+  /// is an opaque \c DeclarationName pointer.
+  static bool FindTagMember(CXXBaseSpecifier *Specifier, CXXBasePath &Path,
+                            void *Name);
+
+  /// \brief Base-class lookup callback that determines whether there exists
+  /// a member with the given name.
+  ///
+  /// This callback can be used with \c lookupInBases() to find members
+  /// of the given name within a C++ class hierarchy. The user data pointer
+  /// is an opaque \c DeclarationName pointer.
+  static bool FindOrdinaryMember(CXXBaseSpecifier *Specifier, CXXBasePath &Path,
+                                 void *Name);
+  
+  /// \brief Base-class lookup callback that determines whether there exists
+  /// a member with the given name that can be used in a nested-name-specifier.
+  ///
+  /// This callback can be used with \c lookupInBases() to find membes of
+  /// the given name within a C++ class hierarchy that can occur within
+  /// nested-name-specifiers.
+  static bool FindNestedNameSpecifierMember(CXXBaseSpecifier *Specifier, 
+                                            CXXBasePath &Path,
+                                            void *UserData);
+  
   /// viewInheritance - Renders and displays an inheritance diagram
   /// for this C++ class and all of its base classes (transitively) using
   /// GraphViz.
diff --git a/include/clang/AST/DeclarationName.h b/include/clang/AST/DeclarationName.h
index 9f9bfa6e3d..ed4ac6b5d4 100644
--- a/include/clang/AST/DeclarationName.h
+++ b/include/clang/AST/DeclarationName.h
@@ -197,6 +197,12 @@ public:
   /// an opaque pointer.
   void *getAsOpaquePtr() const { return reinterpret_cast<void*>(Ptr); }
 
+  static DeclarationName getFromOpaquePtr(void *P) {
+    DeclarationName N;
+    N.Ptr = reinterpret_cast<uintptr_t> (P);
+    return N;
+  }
+  
   static DeclarationName getFromOpaqueInteger(uintptr_t P) {
     DeclarationName N;
     N.Ptr = P;
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