Update clang to r84119.

1 files changed, 549 insertions, 689 deletions

diff --git a/lib/Sema/SemaTemplateInstantiate.cpp b/lib/Sema/SemaTemplateInstantiate.cpp
index 6c2dc77..65260c8 100644
--- a/lib/Sema/SemaTemplateInstantiate.cpp
+++ b/lib/Sema/SemaTemplateInstantiate.cpp
@@ -11,6 +11,7 @@
 //===----------------------------------------------------------------------===/
 
 #include "Sema.h"
+#include "TreeTransform.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Expr.h"
@@ -25,32 +26,65 @@ using namespace clang;
 // Template Instantiation Support
 //===----------------------------------------------------------------------===/
 
-/// \brief Retrieve the template argument list that should be used to
-/// instantiate the given declaration.
-const TemplateArgumentList &
+/// \brief Retrieve the template argument list(s) that should be used to
+/// instantiate the definition of the given declaration.
+MultiLevelTemplateArgumentList
 Sema::getTemplateInstantiationArgs(NamedDecl *D) {
-  // Template arguments for a class template specialization.
-  if (ClassTemplateSpecializationDecl *Spec 
-        = dyn_cast<ClassTemplateSpecializationDecl>(D))
-    return Spec->getTemplateArgs();
-
-  // Template arguments for a function template specialization.
-  if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D))
-    if (const TemplateArgumentList *TemplateArgs
-          = Function->getTemplateSpecializationArgs())
-      return *TemplateArgs;
+  // Accumulate the set of template argument lists in this structure.
+  MultiLevelTemplateArgumentList Result;
+
+  DeclContext *Ctx = dyn_cast<DeclContext>(D);
+  if (!Ctx)
+    Ctx = D->getDeclContext();
+
+  while (!Ctx->isFileContext()) {
+    // Add template arguments from a class template instantiation.
+    if (ClassTemplateSpecializationDecl *Spec
+          = dyn_cast<ClassTemplateSpecializationDecl>(Ctx)) {
+      // We're done when we hit an explicit specialization.
+      if (Spec->getSpecializationKind() == TSK_ExplicitSpecialization)
+        break;
+
+      Result.addOuterTemplateArguments(&Spec->getTemplateInstantiationArgs());
       
-  // Template arguments for a member of a class template specialization.
-  DeclContext *EnclosingTemplateCtx = D->getDeclContext();
-  while (!isa<ClassTemplateSpecializationDecl>(EnclosingTemplateCtx)) {
-    assert(!EnclosingTemplateCtx->isFileContext() &&
-           "Tried to get the instantiation arguments of a non-template");
-    EnclosingTemplateCtx = EnclosingTemplateCtx->getParent();
+      // If this class template specialization was instantiated from a 
+      // specialized member that is a class template, we're done.
+      assert(Spec->getSpecializedTemplate() && "No class template?");
+      if (Spec->getSpecializedTemplate()->isMemberSpecialization())
+        break;
+    }
+    // Add template arguments from a function template specialization.
+    else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Ctx)) {
+      if (Function->getTemplateSpecializationKind() 
+            == TSK_ExplicitSpecialization)
+        break;
+          
+      if (const TemplateArgumentList *TemplateArgs
+            = Function->getTemplateSpecializationArgs()) {
+        // Add the template arguments for this specialization.
+        Result.addOuterTemplateArguments(TemplateArgs);
+
+        // If this function was instantiated from a specialized member that is
+        // a function template, we're done.
+        assert(Function->getPrimaryTemplate() && "No function template?");
+        if (Function->getPrimaryTemplate()->isMemberSpecialization())
+          break;
+      }
+      
+      // If this is a friend declaration and it declares an entity at
+      // namespace scope, take arguments from its lexical parent
+      // instead of its semantic parent.
+      if (Function->getFriendObjectKind() &&
+          Function->getDeclContext()->isFileContext()) {
+        Ctx = Function->getLexicalDeclContext();
+        continue;
+      }
+    }
+
+    Ctx = Ctx->getParent();
   }
 
-  ClassTemplateSpecializationDecl *EnclosingTemplate 
-    = cast<ClassTemplateSpecializationDecl>(EnclosingTemplateCtx);
-  return EnclosingTemplate->getTemplateArgs();
+  return Result;
 }
 
 Sema::InstantiatingTemplate::
@@ -74,7 +108,7 @@ InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
   }
 }
 
-Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef, 
+Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
                                          SourceLocation PointOfInstantiation,
                                          TemplateDecl *Template,
                                          const TemplateArgument *TemplateArgs,
@@ -86,7 +120,7 @@ Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
                                     InstantiationRange);
   if (!Invalid) {
     ActiveTemplateInstantiation Inst;
-    Inst.Kind 
+    Inst.Kind
       = ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation;
     Inst.PointOfInstantiation = PointOfInstantiation;
     Inst.Entity = reinterpret_cast<uintptr_t>(Template);
@@ -98,7 +132,7 @@ Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
   }
 }
 
-Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef, 
+Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
                                          SourceLocation PointOfInstantiation,
                                       FunctionTemplateDecl *FunctionTemplate,
                                         const TemplateArgument *TemplateArgs,
@@ -106,7 +140,7 @@ Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
                          ActiveTemplateInstantiation::InstantiationKind Kind,
                                               SourceRange InstantiationRange)
 : SemaRef(SemaRef) {
-  
+
   Invalid = CheckInstantiationDepth(PointOfInstantiation,
                                     InstantiationRange);
   if (!Invalid) {
@@ -122,7 +156,7 @@ Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
   }
 }
 
-Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef, 
+Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
                                          SourceLocation PointOfInstantiation,
                           ClassTemplatePartialSpecializationDecl *PartialSpec,
                                          const TemplateArgument *TemplateArgs,
@@ -134,7 +168,7 @@ Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
                                     InstantiationRange);
   if (!Invalid) {
     ActiveTemplateInstantiation Inst;
-    Inst.Kind 
+    Inst.Kind
       = ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution;
     Inst.PointOfInstantiation = PointOfInstantiation;
     Inst.Entity = reinterpret_cast<uintptr_t>(PartialSpec);
@@ -146,6 +180,30 @@ Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
   }
 }
 
+Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
+                                          SourceLocation PointOfInstantation,
+                                          ParmVarDecl *Param,
+                                          const TemplateArgument *TemplateArgs,
+                                          unsigned NumTemplateArgs,
+                                          SourceRange InstantiationRange)
+  : SemaRef(SemaRef) {
+
+  Invalid = CheckInstantiationDepth(PointOfInstantation, InstantiationRange);
+
+  if (!Invalid) {
+    ActiveTemplateInstantiation Inst;
+    Inst.Kind
+      = ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation;
+    Inst.PointOfInstantiation = PointOfInstantation;
+    Inst.Entity = reinterpret_cast<uintptr_t>(Param);
+    Inst.TemplateArgs = TemplateArgs;
+    Inst.NumTemplateArgs = NumTemplateArgs;
+    Inst.InstantiationRange = InstantiationRange;
+    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
+    Invalid = false;
+  }
+}
+
 void Sema::InstantiatingTemplate::Clear() {
   if (!Invalid) {
     SemaRef.ActiveTemplateInstantiations.pop_back();
@@ -156,11 +214,11 @@ void Sema::InstantiatingTemplate::Clear() {
 bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
                                         SourceLocation PointOfInstantiation,
                                            SourceRange InstantiationRange) {
-  if (SemaRef.ActiveTemplateInstantiations.size() 
+  if (SemaRef.ActiveTemplateInstantiations.size()
        <= SemaRef.getLangOptions().InstantiationDepth)
     return false;
 
-  SemaRef.Diag(PointOfInstantiation, 
+  SemaRef.Diag(PointOfInstantiation,
                diag::err_template_recursion_depth_exceeded)
     << SemaRef.getLangOptions().InstantiationDepth
     << InstantiationRange;
@@ -185,21 +243,25 @@ void Sema::PrintInstantiationStack() {
         unsigned DiagID = diag::note_template_member_class_here;
         if (isa<ClassTemplateSpecializationDecl>(Record))
           DiagID = diag::note_template_class_instantiation_here;
-        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr), 
+        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
                      DiagID)
           << Context.getTypeDeclType(Record)
           << Active->InstantiationRange;
-      } else {
-        FunctionDecl *Function = cast<FunctionDecl>(D);
+      } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
         unsigned DiagID;
         if (Function->getPrimaryTemplate())
           DiagID = diag::note_function_template_spec_here;
         else
           DiagID = diag::note_template_member_function_here;
-        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr), 
+        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
                      DiagID)
           << Function
           << Active->InstantiationRange;
+      } else {
+        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
+                     diag::note_template_static_data_member_def_here)
+          << cast<VarDecl>(D)
+          << Active->InstantiationRange;
       }
       break;
     }
@@ -208,7 +270,7 @@ void Sema::PrintInstantiationStack() {
       TemplateDecl *Template = cast<TemplateDecl>((Decl *)Active->Entity);
       std::string TemplateArgsStr
         = TemplateSpecializationType::PrintTemplateArgumentList(
-                                                         Active->TemplateArgs, 
+                                                         Active->TemplateArgs,
                                                       Active->NumTemplateArgs,
                                                       Context.PrintingPolicy);
       Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
@@ -219,14 +281,14 @@ void Sema::PrintInstantiationStack() {
     }
 
     case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution: {
-      FunctionTemplateDecl *FnTmpl 
+      FunctionTemplateDecl *FnTmpl
         = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
       Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
                    diag::note_explicit_template_arg_substitution_here)
         << FnTmpl << Active->InstantiationRange;
       break;
     }
-        
+
     case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
       if (ClassTemplatePartialSpecializationDecl *PartialSpec
             = dyn_cast<ClassTemplatePartialSpecializationDecl>(
@@ -244,6 +306,22 @@ void Sema::PrintInstantiationStack() {
       }
       break;
 
+    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation: {
+      ParmVarDecl *Param = cast<ParmVarDecl>((Decl *)Active->Entity);
+      FunctionDecl *FD = cast<FunctionDecl>(Param->getDeclContext());
+
+      std::string TemplateArgsStr
+        = TemplateSpecializationType::PrintTemplateArgumentList(
+                                                         Active->TemplateArgs,
+                                                      Active->NumTemplateArgs,
+                                                      Context.PrintingPolicy);
+      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
+                   diag::note_default_function_arg_instantiation_here)
+        << (FD->getNameAsString() + TemplateArgsStr)
+        << Active->InstantiationRange;
+      break;
+    }
+
     }
   }
 }
@@ -258,14 +336,16 @@ bool Sema::isSFINAEContext() const {
 
     switch(Active->Kind) {
     case ActiveTemplateInstantiation::TemplateInstantiation:
+    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation:
+
       // This is a template instantiation, so there is no SFINAE.
       return false;
-        
+
     case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation:
       // A default template argument instantiation may or may not be a
       // SFINAE context; look further up the stack.
       break;
-        
+
     case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution:
     case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
       // We're either substitution explicitly-specified template arguments
@@ -281,482 +361,274 @@ bool Sema::isSFINAEContext() const {
 // Template Instantiation for Types
 //===----------------------------------------------------------------------===/
 namespace {
-  class VISIBILITY_HIDDEN TemplateTypeInstantiator {
-    Sema &SemaRef;
-    const TemplateArgumentList &TemplateArgs;
+  class VISIBILITY_HIDDEN TemplateInstantiator
+    : public TreeTransform<TemplateInstantiator> {
+    const MultiLevelTemplateArgumentList &TemplateArgs;
     SourceLocation Loc;
     DeclarationName Entity;
 
   public:
-    TemplateTypeInstantiator(Sema &SemaRef, 
-                             const TemplateArgumentList &TemplateArgs,
-                             SourceLocation Loc,
-                             DeclarationName Entity) 
-      : SemaRef(SemaRef), TemplateArgs(TemplateArgs), 
-        Loc(Loc), Entity(Entity) { }
-
-    QualType operator()(QualType T) const { return Instantiate(T); }
-    
-    QualType Instantiate(QualType T) const;
-
-    // Declare instantiate functions for each type.
-#define TYPE(Class, Base)                                       \
-    QualType Instantiate##Class##Type(const Class##Type *T) const;
-#define ABSTRACT_TYPE(Class, Base)
-#include "clang/AST/TypeNodes.def"
-  };
-}
-
-QualType 
-TemplateTypeInstantiator::InstantiateExtQualType(const ExtQualType *T) const {
-  // FIXME: Implement this
-  assert(false && "Cannot instantiate ExtQualType yet");
-  return QualType();
-}
-
-QualType 
-TemplateTypeInstantiator::InstantiateBuiltinType(const BuiltinType *T) const {
-  assert(false && "Builtin types are not dependent and cannot be instantiated");
-  return QualType(T, 0);
-}
-
-QualType 
-TemplateTypeInstantiator::
-InstantiateFixedWidthIntType(const FixedWidthIntType *T) const {
-  // FIXME: Implement this
-  assert(false && "Cannot instantiate FixedWidthIntType yet");
-  return QualType();
-}
-
-QualType 
-TemplateTypeInstantiator::InstantiateComplexType(const ComplexType *T) const {
-  // FIXME: Implement this
-  assert(false && "Cannot instantiate ComplexType yet");
-  return QualType();
-}
-
-QualType 
-TemplateTypeInstantiator::InstantiatePointerType(const PointerType *T) const {
-  QualType PointeeType = Instantiate(T->getPointeeType());
-  if (PointeeType.isNull())
-    return QualType();
-
-  return SemaRef.BuildPointerType(PointeeType, 0, Loc, Entity);
-}
+    typedef TreeTransform<TemplateInstantiator> inherited;
+
+    TemplateInstantiator(Sema &SemaRef,
+                         const MultiLevelTemplateArgumentList &TemplateArgs,
+                         SourceLocation Loc,
+                         DeclarationName Entity)
+      : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
+        Entity(Entity) { }
+
+    /// \brief Determine whether the given type \p T has already been
+    /// transformed.
+    ///
+    /// For the purposes of template instantiation, a type has already been
+    /// transformed if it is NULL or if it is not dependent.
+    bool AlreadyTransformed(QualType T) {
+      return T.isNull() || !T->isDependentType();
+    }
 
-QualType 
-TemplateTypeInstantiator::InstantiateBlockPointerType(
-                                            const BlockPointerType *T) const {
-  QualType PointeeType = Instantiate(T->getPointeeType());
-  if (PointeeType.isNull())
-    return QualType();
-  
-  return SemaRef.BuildBlockPointerType(PointeeType, 0, Loc, Entity);
-}
+    /// \brief Returns the location of the entity being instantiated, if known.
+    SourceLocation getBaseLocation() { return Loc; }
 
-QualType
-TemplateTypeInstantiator::InstantiateLValueReferenceType(
-                                        const LValueReferenceType *T) const {
-  QualType ReferentType = Instantiate(T->getPointeeType());
-  if (ReferentType.isNull())
-    return QualType();
+    /// \brief Returns the name of the entity being instantiated, if any.
+    DeclarationName getBaseEntity() { return Entity; }
 
-  return SemaRef.BuildReferenceType(ReferentType, true, 0, Loc, Entity);
-}
+    /// \brief Transform the given declaration by instantiating a reference to
+    /// this declaration.
+    Decl *TransformDecl(Decl *D);
 
-QualType
-TemplateTypeInstantiator::InstantiateRValueReferenceType(
-                                        const RValueReferenceType *T) const {
-  QualType ReferentType = Instantiate(T->getPointeeType());
-  if (ReferentType.isNull())
-    return QualType();
+    /// \brief Transform the definition of the given declaration by
+    /// instantiating it.
+    Decl *TransformDefinition(Decl *D);
 
-  return SemaRef.BuildReferenceType(ReferentType, false, 0, Loc, Entity);
-}
+    /// \brief Rebuild the exception declaration and register the declaration
+    /// as an instantiated local.
+    VarDecl *RebuildExceptionDecl(VarDecl *ExceptionDecl, QualType T,
+                                  DeclaratorInfo *Declarator,
+                                  IdentifierInfo *Name,
+                                  SourceLocation Loc, SourceRange TypeRange);
 
-QualType 
-TemplateTypeInstantiator::
-InstantiateMemberPointerType(const MemberPointerType *T) const {
-  QualType PointeeType = Instantiate(T->getPointeeType());
-  if (PointeeType.isNull())
-    return QualType();
+    /// \brief Check for tag mismatches when instantiating an
+    /// elaborated type.
+    QualType RebuildElaboratedType(QualType T, ElaboratedType::TagKind Tag);
 
-  QualType ClassType = Instantiate(QualType(T->getClass(), 0));
-  if (ClassType.isNull())
-    return QualType();
+    Sema::OwningExprResult TransformPredefinedExpr(PredefinedExpr *E);
+    Sema::OwningExprResult TransformDeclRefExpr(DeclRefExpr *E);
 
-  return SemaRef.BuildMemberPointerType(PointeeType, ClassType, 0, Loc, 
-                                        Entity);
-}
-
-QualType 
-TemplateTypeInstantiator::
-InstantiateConstantArrayType(const ConstantArrayType *T) const {
-  QualType ElementType = Instantiate(T->getElementType());
-  if (ElementType.isNull())
-    return ElementType;
-  
-  // Build a temporary integer literal to specify the size for
-  // BuildArrayType. Since we have already checked the size as part of
-  // creating the dependent array type in the first place, we know
-  // there aren't any errors. However, we do need to determine what
-  // C++ type to give the size expression.
-  llvm::APInt Size = T->getSize();
-  QualType Types[] = { 
-    SemaRef.Context.UnsignedCharTy, SemaRef.Context.UnsignedShortTy, 
-    SemaRef.Context.UnsignedIntTy, SemaRef.Context.UnsignedLongTy, 
-    SemaRef.Context.UnsignedLongLongTy, SemaRef.Context.UnsignedInt128Ty 
+    /// \brief Transforms a template type parameter type by performing
+    /// substitution of the corresponding template type argument.
+    QualType TransformTemplateTypeParmType(const TemplateTypeParmType *T);
   };
-  const unsigned NumTypes = sizeof(Types) / sizeof(QualType);
-  QualType SizeType;
-  for (unsigned I = 0; I != NumTypes; ++I)
-    if (Size.getBitWidth() == SemaRef.Context.getIntWidth(Types[I])) {
-      SizeType = Types[I];
-      break;
-    }
-
-  if (SizeType.isNull())
-    SizeType = SemaRef.Context.getFixedWidthIntType(Size.getBitWidth(), false);
-
-  IntegerLiteral ArraySize(Size, SizeType, Loc);
-  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(), 
-                                &ArraySize, T->getIndexTypeQualifier(), 
-                                Loc, Entity);
 }
 
-QualType 
-TemplateTypeInstantiator::
-InstantiateIncompleteArrayType(const IncompleteArrayType *T) const {
-  QualType ElementType = Instantiate(T->getElementType());
-  if (ElementType.isNull())
-    return ElementType;
-  
-  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(), 
-                                0, T->getIndexTypeQualifier(), 
-                                Loc, Entity);
-}
+Decl *TemplateInstantiator::TransformDecl(Decl *D) {
+  if (!D)
+    return 0;
 
-QualType
-TemplateTypeInstantiator::
-InstantiateVariableArrayType(const VariableArrayType *T) const {
-  // FIXME: Implement this
-  assert(false && "Cannot instantiate VariableArrayType yet");
-  return QualType();
-}
+  if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
+    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
+      assert(TemplateArgs(TTP->getDepth(), TTP->getPosition()).getAsDecl() &&
+             "Wrong kind of template template argument");
+      return cast<TemplateDecl>(TemplateArgs(TTP->getDepth(),
+                                             TTP->getPosition()).getAsDecl());
+    }
 
-QualType 
-TemplateTypeInstantiator::
-InstantiateDependentSizedArrayType(const DependentSizedArrayType *T) const {
-  Expr *ArraySize = T->getSizeExpr();
-  assert(ArraySize->isValueDependent() && 
-         "dependent sized array types must have value dependent size expr");
-  
-  // Instantiate the element type if needed
-  QualType ElementType = T->getElementType();
-  if (ElementType->isDependentType()) {
-    ElementType = Instantiate(ElementType);
-    if (ElementType.isNull())
-      return QualType();
-  }
-  
-  // Instantiate the size expression
-  EnterExpressionEvaluationContext Unevaluated(SemaRef, Action::Unevaluated);
-  Sema::OwningExprResult InstantiatedArraySize = 
-    SemaRef.InstantiateExpr(ArraySize, TemplateArgs);
-  if (InstantiatedArraySize.isInvalid())
-    return QualType();
-  
-  return SemaRef.BuildArrayType(ElementType, T->getSizeModifier(),
-                                InstantiatedArraySize.takeAs<Expr>(),
-                                T->getIndexTypeQualifier(), Loc, Entity);
-}
+    // If the corresponding template argument is NULL or non-existent, it's
+    // because we are performing instantiation from explicitly-specified
+    // template arguments in a function template, but there were some
+    // arguments left unspecified.
+    if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
+                                          TTP->getPosition()))
+      return D;
 
-QualType 
-TemplateTypeInstantiator::
-InstantiateDependentSizedExtVectorType(
-                                const DependentSizedExtVectorType *T) const {
-
-  // Instantiate the element type if needed.
-  QualType ElementType = T->getElementType();
-  if (ElementType->isDependentType()) {
-    ElementType = Instantiate(ElementType);
-    if (ElementType.isNull())
-      return QualType();
+    // FIXME: Implement depth reduction of template template parameters
+    assert(false &&
+      "Reducing depth of template template parameters is not yet implemented");
   }
 
-  // The expression in a dependent-sized extended vector type is not
-  // potentially evaluated.
-  EnterExpressionEvaluationContext Unevaluated(SemaRef, Action::Unevaluated);
-
-  // Instantiate the size expression.
-  const Expr *SizeExpr = T->getSizeExpr();
-  Sema::OwningExprResult InstantiatedArraySize = 
-    SemaRef.InstantiateExpr(const_cast<Expr *>(SizeExpr), TemplateArgs);
-  if (InstantiatedArraySize.isInvalid())
-    return QualType();
-  
-  return SemaRef.BuildExtVectorType(ElementType,
-                                    SemaRef.Owned(
-                                      InstantiatedArraySize.takeAs<Expr>()),
-                                    T->getAttributeLoc());
+  return SemaRef.FindInstantiatedDecl(cast<NamedDecl>(D), TemplateArgs);
 }
 
-QualType 
-TemplateTypeInstantiator::InstantiateVectorType(const VectorType *T) const {
-  // FIXME: Implement this
-  assert(false && "Cannot instantiate VectorType yet");
-  return QualType();
-}
-
-QualType 
-TemplateTypeInstantiator::InstantiateExtVectorType(
-                                              const ExtVectorType *T) const {
-  // FIXME: Implement this
-  assert(false && "Cannot instantiate ExtVectorType yet");
-  return QualType();
-}
-
-QualType 
-TemplateTypeInstantiator::
-InstantiateFunctionProtoType(const FunctionProtoType *T) const {
-  QualType ResultType = Instantiate(T->getResultType());
-  if (ResultType.isNull())
-    return ResultType;
-
-  llvm::SmallVector<QualType, 4> ParamTypes;
-  for (FunctionProtoType::arg_type_iterator Param = T->arg_type_begin(),
-                                         ParamEnd = T->arg_type_end(); 
-       Param != ParamEnd; ++Param) {
-    QualType P = Instantiate(*Param);
-    if (P.isNull())
-      return P;
-
-    ParamTypes.push_back(P);
-  }
-
-  return SemaRef.BuildFunctionType(ResultType, ParamTypes.data(), 
-                                   ParamTypes.size(),
-                                   T->isVariadic(), T->getTypeQuals(),
-                                   Loc, Entity);
-}
+Decl *TemplateInstantiator::TransformDefinition(Decl *D) {
+  Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
+  if (!Inst)
+    return 0;
 
-QualType 
-TemplateTypeInstantiator::
-InstantiateFunctionNoProtoType(const FunctionNoProtoType *T) const {
-  assert(false && "Functions without prototypes cannot be dependent.");
-  return QualType();
+  getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
+  return Inst;
 }
 
-QualType 
-TemplateTypeInstantiator::InstantiateTypedefType(const TypedefType *T) const {
-  TypedefDecl *Typedef 
-    = cast_or_null<TypedefDecl>(
-                           SemaRef.InstantiateCurrentDeclRef(T->getDecl()));
-  if (!Typedef)
-    return QualType();
-  
-  return SemaRef.Context.getTypeDeclType(Typedef);
+VarDecl *
+TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
+                                           QualType T,
+                                           DeclaratorInfo *Declarator,
+                                           IdentifierInfo *Name,
+                                           SourceLocation Loc,
+                                           SourceRange TypeRange) {
+  VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, T, Declarator,
+                                                 Name, Loc, TypeRange);
+  if (Var && !Var->isInvalidDecl())
+    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
+  return Var;
 }
 
-QualType 
-TemplateTypeInstantiator::InstantiateTypeOfExprType(
-                                              const TypeOfExprType *T) const {
-  // The expression in a typeof is not potentially evaluated.
-  EnterExpressionEvaluationContext Unevaluated(SemaRef, Action::Unevaluated);
-  
-  Sema::OwningExprResult E 
-    = SemaRef.InstantiateExpr(T->getUnderlyingExpr(), TemplateArgs);
-  if (E.isInvalid())
-    return QualType();
+QualType
+TemplateInstantiator::RebuildElaboratedType(QualType T,
+                                            ElaboratedType::TagKind Tag) {
+  if (const TagType *TT = T->getAs<TagType>()) {
+    TagDecl* TD = TT->getDecl();
+
+    // FIXME: this location is very wrong;  we really need typelocs.
+    SourceLocation TagLocation = TD->getTagKeywordLoc();
+
+    // FIXME: type might be anonymous.
+    IdentifierInfo *Id = TD->getIdentifier();
+
+    // TODO: should we even warn on struct/class mismatches for this?  Seems
+    // like it's likely to produce a lot of spurious errors.
+    if (!SemaRef.isAcceptableTagRedeclaration(TD, Tag, TagLocation, *Id)) {
+      SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
+        << Id
+        << CodeModificationHint::CreateReplacement(SourceRange(TagLocation),
+                                                   TD->getKindName());
+      SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
+    }
+  }
 
-  return SemaRef.BuildTypeofExprType(E.takeAs<Expr>());
+  return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(T, Tag);
 }
 
-QualType 
-TemplateTypeInstantiator::InstantiateTypeOfType(const TypeOfType *T) const {
-  QualType Underlying = Instantiate(T->getUnderlyingType());
-  if (Underlying.isNull())
-    return QualType();
+Sema::OwningExprResult 
+TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
+  if (!E->isTypeDependent())
+    return SemaRef.Owned(E->Retain());
 
-  return SemaRef.Context.getTypeOfType(Underlying);
-}
+  FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
+  assert(currentDecl && "Must have current function declaration when "
+                        "instantiating.");
 
-QualType
-TemplateTypeInstantiator::InstantiateDecltypeType(const DecltypeType *T) const {
-  // C++0x [dcl.type.simple]p4:
-  //   The operand of the decltype specifier is an unevaluated operand.
-  EnterExpressionEvaluationContext Unevaluated(SemaRef,
-                                               Action::Unevaluated);
-  
-  Sema::OwningExprResult E 
-    = SemaRef.InstantiateExpr(T->getUnderlyingExpr(), TemplateArgs);
+  PredefinedExpr::IdentType IT = E->getIdentType();
 
-  if (E.isInvalid())
-    return QualType();
-  
-  return SemaRef.BuildDecltypeType(E.takeAs<Expr>());
-}
+  unsigned Length =
+    PredefinedExpr::ComputeName(getSema().Context, IT, currentDecl).length();
 
-QualType 
-TemplateTypeInstantiator::InstantiateRecordType(const RecordType *T) const {
-  RecordDecl *Record 
-    = cast_or_null<RecordDecl>(SemaRef.InstantiateCurrentDeclRef(T->getDecl()));
-  if (!Record)
-    return QualType();
-  
-  return SemaRef.Context.getTypeDeclType(Record);
+  llvm::APInt LengthI(32, Length + 1);
+  QualType ResTy = getSema().Context.CharTy.withConst();
+  ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI, 
+                                                 ArrayType::Normal, 0);
+  PredefinedExpr *PE =
+    new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
+  return getSema().Owned(PE);
 }
 
-QualType 
-TemplateTypeInstantiator::InstantiateEnumType(const EnumType *T) const {
-  EnumDecl *Enum 
-    = cast_or_null<EnumDecl>(SemaRef.InstantiateCurrentDeclRef(T->getDecl()));
-  if (!Enum)
-    return QualType();
-  
-  return SemaRef.Context.getTypeDeclType(Enum);
-}
+Sema::OwningExprResult
+TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
+  // FIXME: Clean this up a bit
+  NamedDecl *D = E->getDecl();
+  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
+    if (NTTP->getDepth() >= TemplateArgs.getNumLevels()) {
+      assert(false && "Cannot reduce non-type template parameter depth yet");
+      return getSema().ExprError();
+    }
 
-QualType 
-TemplateTypeInstantiator::
-InstantiateTemplateTypeParmType(const TemplateTypeParmType *T) const {
-  if (T->getDepth() == 0) {
-    // Replace the template type parameter with its corresponding
-    // template argument.
-    
-    // If the corresponding template argument is NULL or doesn't exist, it's 
-    // because we are performing instantiation from explicitly-specified 
-    // template arguments in a function template class, but there were some 
+    // If the corresponding template argument is NULL or non-existent, it's
+    // because we are performing instantiation from explicitly-specified
+    // template arguments in a function template, but there were some
     // arguments left unspecified.
-    if (T->getIndex() >= TemplateArgs.size() ||
-        TemplateArgs[T->getIndex()].isNull())
-      return QualType(T, 0); // Would be nice to keep the original type here
-        
-    assert(TemplateArgs[T->getIndex()].getKind() == TemplateArgument::Type &&
-           "Template argument kind mismatch");
-    return TemplateArgs[T->getIndex()].getAsType();
-  } 
+    if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
+                                          NTTP->getPosition()))
+      return SemaRef.Owned(E->Retain());
 
-  // The template type parameter comes from an inner template (e.g.,
-  // the template parameter list of a member template inside the
-  // template we are instantiating). Create a new template type
-  // parameter with the template "level" reduced by one.
-  return SemaRef.Context.getTemplateTypeParmType(T->getDepth() - 1,
-                                                 T->getIndex(),
-                                                 T->isParameterPack(),
-                                                 T->getName());
-}
+    const TemplateArgument &Arg = TemplateArgs(NTTP->getDepth(),
+                                               NTTP->getPosition());
 
-QualType 
-TemplateTypeInstantiator::
-InstantiateTemplateSpecializationType(
-                                  const TemplateSpecializationType *T) const {
-  llvm::SmallVector<TemplateArgument, 4> InstantiatedTemplateArgs;
-  InstantiatedTemplateArgs.reserve(T->getNumArgs());
-  for (TemplateSpecializationType::iterator Arg = T->begin(), ArgEnd = T->end();
-       Arg != ArgEnd; ++Arg) {
-    TemplateArgument InstArg = SemaRef.Instantiate(*Arg, TemplateArgs);
-    if (InstArg.isNull())
-      return QualType();
-
-    InstantiatedTemplateArgs.push_back(InstArg);
-  }
+    // The template argument itself might be an expression, in which
+    // case we just return that expression.
+    if (Arg.getKind() == TemplateArgument::Expression)
+      return SemaRef.Owned(Arg.getAsExpr()->Retain());
 
-  // FIXME: We're missing the locations of the template name, '<', and '>'.
+    if (Arg.getKind() == TemplateArgument::Declaration) {
+      ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
 
-  TemplateName Name = SemaRef.InstantiateTemplateName(T->getTemplateName(),
-                                                      Loc, 
-                                                      TemplateArgs);
+      VD = cast_or_null<ValueDecl>(
+                              getSema().FindInstantiatedDecl(VD, TemplateArgs));
+      if (!VD)
+        return SemaRef.ExprError();
 
-  return SemaRef.CheckTemplateIdType(Name, Loc, SourceLocation(),
-                                     InstantiatedTemplateArgs.data(),
-                                     InstantiatedTemplateArgs.size(),
-                                     SourceLocation());
-}
-
-QualType 
-TemplateTypeInstantiator::
-InstantiateQualifiedNameType(const QualifiedNameType *T) const {
-  // When we instantiated a qualified name type, there's no point in
-  // keeping the qualification around in the instantiated result. So,
-  // just instantiate the named type.
-  return (*this)(T->getNamedType());
-}
+      return SemaRef.BuildDeclRefExpr(VD, VD->getType(), E->getLocation(),
+                                      /*FIXME:*/false, /*FIXME:*/false);
+    }
 
-QualType 
-TemplateTypeInstantiator::
-InstantiateTypenameType(const TypenameType *T) const {
-  if (const TemplateSpecializationType *TemplateId = T->getTemplateId()) {
-    // When the typename type refers to a template-id, the template-id
-    // is dependent and has enough information to instantiate the
-    // result of the typename type. Since we don't care about keeping
-    // the spelling of the typename type in template instantiations,
-    // we just instantiate the template-id.
-    return InstantiateTemplateSpecializationType(TemplateId);
+    assert(Arg.getKind() == TemplateArgument::Integral);
+    QualType T = Arg.getIntegralType();
+    if (T->isCharType() || T->isWideCharType())
+      return SemaRef.Owned(new (SemaRef.Context) CharacterLiteral(
+                                            Arg.getAsIntegral()->getZExtValue(),
+                                            T->isWideCharType(),
+                                            T,
+                                            E->getSourceRange().getBegin()));
+    if (T->isBooleanType())
+      return SemaRef.Owned(new (SemaRef.Context) CXXBoolLiteralExpr(
+                                          Arg.getAsIntegral()->getBoolValue(),
+                                          T,
+                                          E->getSourceRange().getBegin()));
+
+    assert(Arg.getAsIntegral()->getBitWidth() == SemaRef.Context.getIntWidth(T));
+    return SemaRef.Owned(new (SemaRef.Context) IntegerLiteral(
+                                              *Arg.getAsIntegral(),
+                                              T,
+                                              E->getSourceRange().getBegin()));
   }
 
-  NestedNameSpecifier *NNS 
-    = SemaRef.InstantiateNestedNameSpecifier(T->getQualifier(), 
-                                             SourceRange(Loc),
-                                             TemplateArgs);
-  if (!NNS)
-    return QualType();
+  NamedDecl *InstD = SemaRef.FindInstantiatedDecl(D, TemplateArgs);
+  if (!InstD)
+    return SemaRef.ExprError();
 
-  return SemaRef.CheckTypenameType(NNS, *T->getIdentifier(), SourceRange(Loc));
-}
+  // If we instantiated an UnresolvedUsingDecl and got back an UsingDecl,
+  // we need to get the underlying decl.
+  // FIXME: Is this correct? Maybe FindInstantiatedDecl should do this?
+  InstD = InstD->getUnderlyingDecl();
 
-QualType 
-TemplateTypeInstantiator::
-InstantiateObjCObjectPointerType(const ObjCObjectPointerType *T) const {
-  assert(false && "Objective-C types cannot be dependent");
-  return QualType();
+  // FIXME: nested-name-specifier for QualifiedDeclRefExpr
+  return SemaRef.BuildDeclarationNameExpr(E->getLocation(), InstD,
+                                          /*FIXME:*/false,
+                                          /*FIXME:*/0,
+                                          /*FIXME:*/false);
 }
 
 QualType
-TemplateTypeInstantiator::
-InstantiateObjCInterfaceType(const ObjCInterfaceType *T) const {
-  assert(false && "Objective-C types cannot be dependent");
-  return QualType();
-}
+TemplateInstantiator::TransformTemplateTypeParmType(
+                                              const TemplateTypeParmType *T) {
+  if (T->getDepth() < TemplateArgs.getNumLevels()) {
+    // Replace the template type parameter with its corresponding
+    // template argument.
 
-QualType 
-TemplateTypeInstantiator::
-InstantiateObjCQualifiedInterfaceType(
-                                 const ObjCQualifiedInterfaceType *T) const {
-  assert(false && "Objective-C types cannot be dependent");
-  return QualType();
-}
+    // If the corresponding template argument is NULL or doesn't exist, it's
+    // because we are performing instantiation from explicitly-specified
+    // template arguments in a function template class, but there were some
+    // arguments left unspecified.
+    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex()))
+      return QualType(T, 0);
 
-/// \brief The actual implementation of Sema::InstantiateType().
-QualType TemplateTypeInstantiator::Instantiate(QualType T) const {
-  // If T is not a dependent type, there is nothing to do.
-  if (!T->isDependentType())
-    return T;
+    assert(TemplateArgs(T->getDepth(), T->getIndex()).getKind()
+             == TemplateArgument::Type &&
+           "Template argument kind mismatch");
 
-  QualType Result;
-  switch (T->getTypeClass()) {
-#define TYPE(Class, Base)                                               \
-  case Type::Class:                                                     \
-    Result = Instantiate##Class##Type(cast<Class##Type>(T.getTypePtr()));  \
-    break;
-#define ABSTRACT_TYPE(Class, Base)
-#include "clang/AST/TypeNodes.def"
+    return TemplateArgs(T->getDepth(), T->getIndex()).getAsType();
   }
 
-  // C++ [dcl.ref]p1:
-  //   [...] Cv-qualified references are ill-formed except when
-  //   the cv-qualifiers are introduced through the use of a
-  //   typedef (7.1.3) or of a template type argument (14.3), in
-  //   which case the cv-qualifiers are ignored.
-  // 
-  // The same rule applies to function types.
-  if (!Result.isNull() && T.getCVRQualifiers() &&
-      !Result->isFunctionType() && !Result->isReferenceType())
-    Result = Result.getWithAdditionalQualifiers(T.getCVRQualifiers());
-  return Result;
+  // The template type parameter comes from an inner template (e.g.,
+  // the template parameter list of a member template inside the
+  // template we are instantiating). Create a new template type
+  // parameter with the template "level" reduced by one.
+  return getSema().Context.getTemplateTypeParmType(
+                                  T->getDepth() - TemplateArgs.getNumLevels(),
+                                                   T->getIndex(),
+                                                   T->isParameterPack(),
+                                                   T->getName());
 }
 
-/// \brief Instantiate the type T with a given set of template arguments.
+/// \brief Perform substitution on the type T with a given set of template
+/// arguments.
 ///
 /// This routine substitutes the given template arguments into the
 /// type T and produces the instantiated type.
@@ -782,9 +654,9 @@ QualType TemplateTypeInstantiator::Instantiate(QualType T) const {
 ///
 /// \returns If the instantiation succeeds, the instantiated
 /// type. Otherwise, produces diagnostics and returns a NULL type.
-QualType Sema::InstantiateType(QualType T, 
-                               const TemplateArgumentList &TemplateArgs,
-                               SourceLocation Loc, DeclarationName Entity) {
+QualType Sema::SubstType(QualType T,
+                         const MultiLevelTemplateArgumentList &TemplateArgs,
+                         SourceLocation Loc, DeclarationName Entity) {
   assert(!ActiveTemplateInstantiations.empty() &&
          "Cannot perform an instantiation without some context on the "
          "instantiation stack");
@@ -793,35 +665,34 @@ QualType Sema::InstantiateType(QualType T,
   if (!T->isDependentType())
     return T;
 
-  TemplateTypeInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
-  return Instantiator(T);
+  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
+  return Instantiator.TransformType(T);
 }
 
-/// \brief Instantiate the base class specifiers of the given class
-/// template specialization.
+/// \brief Perform substitution on the base class specifiers of the
+/// given class template specialization.
 ///
 /// Produces a diagnostic and returns true on error, returns false and
 /// attaches the instantiated base classes to the class template
 /// specialization if successful.
-bool 
-Sema::InstantiateBaseSpecifiers(CXXRecordDecl *Instantiation,
-                                CXXRecordDecl *Pattern,
-                                const TemplateArgumentList &TemplateArgs) {
+bool
+Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
+                          CXXRecordDecl *Pattern,
+                          const MultiLevelTemplateArgumentList &TemplateArgs) {
   bool Invalid = false;
   llvm::SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
-  for (ClassTemplateSpecializationDecl::base_class_iterator 
+  for (ClassTemplateSpecializationDecl::base_class_iterator
          Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
        Base != BaseEnd; ++Base) {
     if (!Base->getType()->isDependentType()) {
-      // FIXME: Allocate via ASTContext
-      InstantiatedBases.push_back(new CXXBaseSpecifier(*Base));
+      InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
       continue;
     }
 
-    QualType BaseType = InstantiateType(Base->getType(), 
-                                        TemplateArgs, 
-                                        Base->getSourceRange().getBegin(),
-                                        DeclarationName());
+    QualType BaseType = SubstType(Base->getType(),
+                                  TemplateArgs,
+                                  Base->getSourceRange().getBegin(),
+                                  DeclarationName());
     if (BaseType.isNull()) {
       Invalid = true;
       continue;
@@ -864,25 +735,33 @@ Sema::InstantiateBaseSpecifiers(CXXRecordDecl *Instantiation,
 /// \param TemplateArgs The template arguments to be substituted into
 /// the pattern.
 ///
+/// \param TSK the kind of implicit or explicit instantiation to perform.
+///
+/// \param Complain whether to complain if the class cannot be instantiated due
+/// to the lack of a definition.
+///
 /// \returns true if an error occurred, false otherwise.
 bool
 Sema::InstantiateClass(SourceLocation PointOfInstantiation,
                        CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
-                       const TemplateArgumentList &TemplateArgs,
-                       bool ExplicitInstantiation) {
+                       const MultiLevelTemplateArgumentList &TemplateArgs,
+                       TemplateSpecializationKind TSK,
+                       bool Complain) {
   bool Invalid = false;
-  
-  CXXRecordDecl *PatternDef 
+
+  CXXRecordDecl *PatternDef
     = cast_or_null<CXXRecordDecl>(Pattern->getDefinition(Context));
   if (!PatternDef) {
-    if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
+    if (!Complain) {
+      // Say nothing
+    } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
       Diag(PointOfInstantiation,
            diag::err_implicit_instantiate_member_undefined)
         << Context.getTypeDeclType(Instantiation);
       Diag(Pattern->getLocation(), diag::note_member_of_template_here);
     } else {
       Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
-        << ExplicitInstantiation
+        << (TSK != TSK_ImplicitInstantiation)
         << Context.getTypeDeclType(Instantiation);
       Diag(Pattern->getLocation(), diag::note_template_decl_here);
     }
@@ -902,20 +781,22 @@ Sema::InstantiateClass(SourceLocation PointOfInstantiation,
   // Start the definition of this instantiation.
   Instantiation->startDefinition();
 
-  // Instantiate the base class specifiers.
-  if (InstantiateBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
+  // Do substitution on the base class specifiers.
+  if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
     Invalid = true;
 
   llvm::SmallVector<DeclPtrTy, 4> Fields;
   for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
-         MemberEnd = Pattern->decls_end(); 
+         MemberEnd = Pattern->decls_end();
        Member != MemberEnd; ++Member) {
-    Decl *NewMember = InstantiateDecl(*Member, Instantiation, TemplateArgs);
+    Decl *NewMember = SubstDecl(*Member, Instantiation, TemplateArgs);
     if (NewMember) {
       if (NewMember->isInvalidDecl())
         Invalid = true;
       else if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
         Fields.push_back(DeclPtrTy::make(Field));
+      else if (UsingDecl *UD = dyn_cast<UsingDecl>(NewMember))
+        Instantiation->addDecl(UD);
     } else {
       // FIXME: Eventually, a NULL return will mean that one of the
       // instantiations was a semantic disaster, and we'll want to set Invalid =
@@ -938,32 +819,52 @@ Sema::InstantiateClass(SourceLocation PointOfInstantiation,
     Consumer.HandleTagDeclDefinition(Instantiation);
 
   // If this is an explicit instantiation, instantiate our members, too.
-  if (!Invalid && ExplicitInstantiation) {
+  if (!Invalid && TSK != TSK_ImplicitInstantiation) {
     Inst.Clear();
-    InstantiateClassMembers(PointOfInstantiation, Instantiation, TemplateArgs);
+    InstantiateClassMembers(PointOfInstantiation, Instantiation, TemplateArgs,
+                            TSK);
   }
 
   return Invalid;
 }
 
-bool 
+bool
 Sema::InstantiateClassTemplateSpecialization(
                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
-                           bool ExplicitInstantiation) {
+                           TemplateSpecializationKind TSK,
+                           bool Complain) {
   // Perform the actual instantiation on the canonical declaration.
   ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
-                               Context.getCanonicalDecl(ClassTemplateSpec));
-
-  // We can only instantiate something that hasn't already been
-  // instantiated or specialized. Fail without any diagnostics: our
-  // caller will provide an error message.
-  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared)
+                                         ClassTemplateSpec->getCanonicalDecl());
+
+  // Check whether we have already instantiated or specialized this class
+  // template specialization.
+  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
+    if (ClassTemplateSpec->getSpecializationKind() == 
+          TSK_ExplicitInstantiationDeclaration &&
+        TSK == TSK_ExplicitInstantiationDefinition) {
+      // An explicit instantiation definition follows an explicit instantiation
+      // declaration (C++0x [temp.explicit]p10); go ahead and perform the
+      // explicit instantiation.
+      ClassTemplateSpec->setSpecializationKind(TSK);
+      InstantiateClassTemplateSpecializationMembers(
+                        /*FIXME?*/ClassTemplateSpec->getPointOfInstantiation(), 
+                                  ClassTemplateSpec,
+                                  TSK);
+      return false;
+    }
+    
+    // We can only instantiate something that hasn't already been
+    // instantiated or specialized. Fail without any diagnostics: our
+    // caller will provide an error message.    
     return true;
+  }
 
+  if (ClassTemplateSpec->isInvalidDecl())
+    return true;
+  
   ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
-  CXXRecordDecl *Pattern = Template->getTemplatedDecl();
-  const TemplateArgumentList *TemplateArgs 
-    = &ClassTemplateSpec->getTemplateArgs();
+  CXXRecordDecl *Pattern = 0;
 
   // C++ [temp.class.spec.match]p1:
   //   When a class template is used in a context that requires an
@@ -976,14 +877,14 @@ Sema::InstantiateClassTemplateSpecialization(
   typedef std::pair<ClassTemplatePartialSpecializationDecl *,
                     TemplateArgumentList *> MatchResult;
   llvm::SmallVector<MatchResult, 4> Matched;
-  for (llvm::FoldingSet<ClassTemplatePartialSpecializationDecl>::iterator 
+  for (llvm::FoldingSet<ClassTemplatePartialSpecializationDecl>::iterator
          Partial = Template->getPartialSpecializations().begin(),
          PartialEnd = Template->getPartialSpecializations().end();
        Partial != PartialEnd;
        ++Partial) {
     TemplateDeductionInfo Info(Context);
     if (TemplateDeductionResult Result
-          = DeduceTemplateArguments(&*Partial, 
+          = DeduceTemplateArguments(&*Partial,
                                     ClassTemplateSpec->getTemplateArgs(),
                                     Info)) {
       // FIXME: Store the failed-deduction information for use in
@@ -998,7 +899,7 @@ Sema::InstantiateClassTemplateSpecialization(
     //   -- If exactly one matching specialization is found, the
     //      instantiation is generated from that specialization.
     Pattern = Matched[0].first;
-    TemplateArgs = Matched[0].second;
+    ClassTemplateSpec->setInstantiationOf(Matched[0].first, Matched[0].second);
   } else if (Matched.size() > 1) {
     //   -- If more than one matching specialization is found, the
     //      partial order rules (14.5.4.2) are used to determine
@@ -1007,61 +908,137 @@ Sema::InstantiateClassTemplateSpecialization(
     //      specialized than all of the other matching
     //      specializations, then the use of the class template is
     //      ambiguous and the program is ill-formed.
-    // FIXME: Implement partial ordering of class template partial
-    // specializations.
-    Diag(ClassTemplateSpec->getLocation(), 
-         diag::unsup_template_partial_spec_ordering);
+    llvm::SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
+    for (llvm::SmallVector<MatchResult, 4>::iterator P = Best + 1,
+                                                  PEnd = Matched.end();
+         P != PEnd; ++P) {
+      if (getMoreSpecializedPartialSpecialization(P->first, Best->first) 
+            == P->first)
+        Best = P;
+    }
+    
+    // Determine if the best partial specialization is more specialized than
+    // the others.
+    bool Ambiguous = false;
+    for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
+                                                  PEnd = Matched.end();
+         P != PEnd; ++P) {
+      if (P != Best &&
+          getMoreSpecializedPartialSpecialization(P->first, Best->first)
+            != Best->first) {
+        Ambiguous = true;
+        break;
+      }
+    }
+     
+    if (Ambiguous) {
+      // Partial ordering did not produce a clear winner. Complain.
+      ClassTemplateSpec->setInvalidDecl();
+      Diag(ClassTemplateSpec->getPointOfInstantiation(),
+           diag::err_partial_spec_ordering_ambiguous)
+        << ClassTemplateSpec;
+      
+      // Print the matching partial specializations.
+      for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
+                                                    PEnd = Matched.end();
+           P != PEnd; ++P)
+        Diag(P->first->getLocation(), diag::note_partial_spec_match)
+          << getTemplateArgumentBindingsText(P->first->getTemplateParameters(),
+                                             *P->second);
+
+      return true;
+    }
+    
+    // Instantiate using the best class template partial specialization.
+    Pattern = Best->first;
+    ClassTemplateSpec->setInstantiationOf(Best->first, Best->second);
   } else {
     //   -- If no matches are found, the instantiation is generated
     //      from the primary template.
-
-    // Since we initialized the pattern and template arguments from
-    // the primary template, there is nothing more we need to do here.
+    ClassTemplateDecl *OrigTemplate = Template;
+    while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
+      // If we've found an explicit specialization of this class template,
+      // stop here and use that as the pattern.
+      if (OrigTemplate->isMemberSpecialization())
+        break;
+      
+      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
+    }
+    
+    Pattern = OrigTemplate->getTemplatedDecl();
   }
 
-  // Note that this is an instantiation.  
-  ClassTemplateSpec->setSpecializationKind(
-                        ExplicitInstantiation? TSK_ExplicitInstantiation 
-                                             : TSK_ImplicitInstantiation);
+  // Note that this is an instantiation.
+  ClassTemplateSpec->setSpecializationKind(TSK);
+
+  bool Result = InstantiateClass(ClassTemplateSpec->getPointOfInstantiation(),
+                                 ClassTemplateSpec, Pattern,
+                              getTemplateInstantiationArgs(ClassTemplateSpec),
+                                 TSK,
+                                 Complain);
 
-  bool Result = InstantiateClass(ClassTemplateSpec->getLocation(),
-                                 ClassTemplateSpec, Pattern, *TemplateArgs,
-                                 ExplicitInstantiation);
-  
   for (unsigned I = 0, N = Matched.size(); I != N; ++I) {
     // FIXME: Implement TemplateArgumentList::Destroy!
     //    if (Matched[I].first != Pattern)
     //      Matched[I].second->Destroy(Context);
   }
-  
+
   return Result;
 }
 
-/// \brief Instantiate the definitions of all of the member of the
-/// given class, which is an instantiation of a class template or a
-/// member class of a template.
+/// \brief Instantiates the definitions of all of the member
+/// of the given class, which is an instantiation of a class template
+/// or a member class of a template.
 void
 Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
                               CXXRecordDecl *Instantiation,
-                              const TemplateArgumentList &TemplateArgs) {
+                        const MultiLevelTemplateArgumentList &TemplateArgs,
+                              TemplateSpecializationKind TSK) {
   for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
                                DEnd = Instantiation->decls_end();
        D != DEnd; ++D) {
     if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
-      if (!Function->getBody())
+      if (Function->getInstantiatedFromMemberFunction()) {
+        // If this member was explicitly specialized, do nothing.
+        if (Function->getTemplateSpecializationKind() ==
+              TSK_ExplicitSpecialization)
+          continue;
+        
+        Function->setTemplateSpecializationKind(TSK);
+      }
+      
+      if (!Function->getBody() && TSK == TSK_ExplicitInstantiationDefinition)
         InstantiateFunctionDefinition(PointOfInstantiation, Function);
     } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
-      const VarDecl *Def = 0;
-      if (!Var->getDefinition(Def))
-        InstantiateVariableDefinition(Var);
+      if (Var->isStaticDataMember()) {
+        // If this member was explicitly specialized, do nothing.
+        if (Var->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
+          continue;
+        
+        Var->setTemplateSpecializationKind(TSK);
+        
+        if (TSK == TSK_ExplicitInstantiationDefinition)
+          InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
+      }        
     } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
-      if (!Record->isInjectedClassName() && !Record->getDefinition(Context)) {
-        assert(Record->getInstantiatedFromMemberClass() && 
-               "Missing instantiated-from-template information");
+      if (Record->isInjectedClassName())
+        continue;
+      
+      assert(Record->getInstantiatedFromMemberClass() &&
+             "Missing instantiated-from-template information");
+      
+      // If this member was explicitly specialized, do nothing.
+      if (Record->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
+        continue;
+      
+      if (!Record->getDefinition(Context))
         InstantiateClass(PointOfInstantiation, Record,
                          Record->getInstantiatedFromMemberClass(),
-                         TemplateArgs, true);
-      }
+                         TemplateArgs,
+                         TSK);
+      
+      InstantiateClassMembers(PointOfInstantiation, Record, TemplateArgs, 
+                              TSK);
     }
   }
 }
@@ -1069,9 +1046,11 @@ Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
 /// \brief Instantiate the definitions of all of the members of the
 /// given class template specialization, which was named as part of an
 /// explicit instantiation.
-void Sema::InstantiateClassTemplateSpecializationMembers(
+void
+Sema::InstantiateClassTemplateSpecializationMembers(
                                            SourceLocation PointOfInstantiation,
-                          ClassTemplateSpecializationDecl *ClassTemplateSpec) {
+                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
+                                               TemplateSpecializationKind TSK) {
   // C++0x [temp.explicit]p7:
   //   An explicit instantiation that names a class template
   //   specialization is an explicit instantion of the same kind
@@ -1081,172 +1060,53 @@ void Sema::InstantiateClassTemplateSpecializationMembers(
   //   containing the explicit instantiation, except as described
   //   below.
   InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
-                          ClassTemplateSpec->getTemplateArgs());
+                          getTemplateInstantiationArgs(ClassTemplateSpec),
+                          TSK);
 }
 
-/// \brief Instantiate a nested-name-specifier.
-NestedNameSpecifier *
-Sema::InstantiateNestedNameSpecifier(NestedNameSpecifier *NNS,
-                                     SourceRange Range,
-                                     const TemplateArgumentList &TemplateArgs) {
-  // Instantiate the prefix of this nested name specifier.
-  NestedNameSpecifier *Prefix = NNS->getPrefix();
-  if (Prefix) {
-    Prefix = InstantiateNestedNameSpecifier(Prefix, Range, TemplateArgs);
-    if (!Prefix)
-      return 0;
-  }
+Sema::OwningStmtResult
+Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
+  if (!S)
+    return Owned(S);
 
-  switch (NNS->getKind()) {
-  case NestedNameSpecifier::Identifier: {
-    assert(Prefix && 
-           "Can't have an identifier nested-name-specifier with no prefix");
-    CXXScopeSpec SS;
-    // FIXME: The source location information is all wrong.
-    SS.setRange(Range);
-    SS.setScopeRep(Prefix);
-    return static_cast<NestedNameSpecifier *>(
-                                 ActOnCXXNestedNameSpecifier(0, SS,
-                                                             Range.getEnd(),
-                                                             Range.getEnd(),
-                                                    *NNS->getAsIdentifier()));
-    break;
-  }
+  TemplateInstantiator Instantiator(*this, TemplateArgs,
+                                    SourceLocation(),
+                                    DeclarationName());
+  return Instantiator.TransformStmt(S);
+}
 
-  case NestedNameSpecifier::Namespace:
-  case NestedNameSpecifier::Global:
-    return NNS;
-    
-  case NestedNameSpecifier::TypeSpecWithTemplate:
-  case NestedNameSpecifier::TypeSpec: {
-    QualType T = QualType(NNS->getAsType(), 0);
-    if (!T->isDependentType())
-      return NNS;
-
-    T = InstantiateType(T, TemplateArgs, Range.getBegin(), DeclarationName());
-    if (T.isNull())
-      return 0;
-
-    if (T->isDependentType() || T->isRecordType() ||
-        (getLangOptions().CPlusPlus0x && T->isEnumeralType())) {
-      assert(T.getCVRQualifiers() == 0 && "Can't get cv-qualifiers here");
-      return NestedNameSpecifier::Create(Context, Prefix, 
-                 NNS->getKind() == NestedNameSpecifier::TypeSpecWithTemplate,
-                                         T.getTypePtr());
-    }
+Sema::OwningExprResult
+Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
+  if (!E)
+    return Owned(E);
 
-    Diag(Range.getBegin(), diag::err_nested_name_spec_non_tag) << T;
-    return 0;
-  }
-  }
+  TemplateInstantiator Instantiator(*this, TemplateArgs,
+                                    SourceLocation(),
+                                    DeclarationName());
+  return Instantiator.TransformExpr(E);
+}
 
-  // Required to silence a GCC warning
-  return 0;
+/// \brief Do template substitution on a nested-name-specifier.
+NestedNameSpecifier *
+Sema::SubstNestedNameSpecifier(NestedNameSpecifier *NNS,
+                               SourceRange Range,
+                         const MultiLevelTemplateArgumentList &TemplateArgs) {
+  TemplateInstantiator Instantiator(*this, TemplateArgs, Range.getBegin(),
+                                    DeclarationName());
+  return Instantiator.TransformNestedNameSpecifier(NNS, Range);
 }
 
 TemplateName
-Sema::InstantiateTemplateName(TemplateName Name, SourceLocation Loc,
-                              const TemplateArgumentList &TemplateArgs) {
-  if (TemplateTemplateParmDecl *TTP 
-        = dyn_cast_or_null<TemplateTemplateParmDecl>(
-                                                 Name.getAsTemplateDecl())) {
-    assert(TTP->getDepth() == 0 && 
-           "Cannot reduce depth of a template template parameter");
-    assert(TemplateArgs[TTP->getPosition()].getAsDecl() &&
-           "Wrong kind of template template argument");
-    ClassTemplateDecl *ClassTemplate 
-      = dyn_cast<ClassTemplateDecl>(
-                               TemplateArgs[TTP->getPosition()].getAsDecl());
-    assert(ClassTemplate && "Expected a class template");
-    if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName()) {
-      NestedNameSpecifier *NNS 
-        = InstantiateNestedNameSpecifier(QTN->getQualifier(),
-                                         /*FIXME=*/SourceRange(Loc),
-                                         TemplateArgs);
-      if (NNS)
-        return Context.getQualifiedTemplateName(NNS, 
-                                                QTN->hasTemplateKeyword(),
-                                                ClassTemplate);
-    }
-
-    return TemplateName(ClassTemplate);
-  } else if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) {
-    NestedNameSpecifier *NNS 
-      = InstantiateNestedNameSpecifier(DTN->getQualifier(),
-                                       /*FIXME=*/SourceRange(Loc),
-                                       TemplateArgs);
-    
-    if (!NNS) // FIXME: Not the best recovery strategy.
-      return Name;
-    
-    if (NNS->isDependent())
-      return Context.getDependentTemplateName(NNS, DTN->getName());
-
-    // Somewhat redundant with ActOnDependentTemplateName.
-    CXXScopeSpec SS;
-    SS.setRange(SourceRange(Loc));
-    SS.setScopeRep(NNS);
-    TemplateTy Template;
-    TemplateNameKind TNK = isTemplateName(*DTN->getName(), 0, Template, &SS);
-    if (TNK == TNK_Non_template) {
-      Diag(Loc, diag::err_template_kw_refers_to_non_template)
-        << DTN->getName();
-      return Name;
-    } else if (TNK == TNK_Function_template) {
-      Diag(Loc, diag::err_template_kw_refers_to_non_template)
-        << DTN->getName();
-      return Name;
-    }
-    
-    return Template.getAsVal<TemplateName>();
-  }
-
-  
-
-  // FIXME: Even if we're referring to a Decl that isn't a template template
-  // parameter, we may need to instantiate the outer contexts of that
-  // Decl. However, this won't be needed until we implement member templates.
-  return Name;
+Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
+                        const MultiLevelTemplateArgumentList &TemplateArgs) {
+  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
+                                    DeclarationName());
+  return Instantiator.TransformTemplateName(Name);
 }
 
-TemplateArgument Sema::Instantiate(TemplateArgument Arg, 
-                                   const TemplateArgumentList &TemplateArgs) {
-  switch (Arg.getKind()) {
-  case TemplateArgument::Null:
-    assert(false && "Should never have a NULL template argument");
-    break;
-    
-  case TemplateArgument::Type: {
-    QualType T = InstantiateType(Arg.getAsType(), TemplateArgs, 
-                                 Arg.getLocation(), DeclarationName());
-    if (T.isNull())
-      return TemplateArgument();
-    
-    return TemplateArgument(Arg.getLocation(), T);
-  }
-
-  case TemplateArgument::Declaration:
-    // FIXME: Template instantiation for template template parameters.
-    return Arg;
-
-  case TemplateArgument::Integral:
-    return Arg;
-
-  case TemplateArgument::Expression: {
-    // Template argument expressions are not potentially evaluated.
-    EnterExpressionEvaluationContext Unevaluated(*this, Action::Unevaluated);
-
-    Sema::OwningExprResult E = InstantiateExpr(Arg.getAsExpr(), TemplateArgs);
-    if (E.isInvalid())
-      return TemplateArgument();
-    return TemplateArgument(E.takeAs<Expr>());
-  }
-  
-  case TemplateArgument::Pack:
-    assert(0 && "FIXME: Implement!");
-    break;
-  }
-
-  assert(false && "Unhandled template argument kind");
-  return TemplateArgument();
+TemplateArgument Sema::Subst(TemplateArgument Arg,
+                         const MultiLevelTemplateArgumentList &TemplateArgs) {
+  TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
+                                    DeclarationName());
+  return Instantiator.TransformTemplateArgument(Arg);
 }