Before checking a template template argument against its corresponding

template template parameter, substitute any prior template arguments
into the template template parameter. This, for example, allows us to
properly check the template template argument for a class such as:

  template<typename T, template<T Value> class X> struct Foo;

The actual implementation of this feature was trivial; most of the
change is dedicated to giving decent diagnostics when this
substitution goes horribly wrong. We now get a note like:

  note: while substituting prior template arguments into template
      template parameter 'X' [with T = float]

As part of this change, enabled some very pedantic checking when
comparing template template parameter lists, which shook out a bug in
our overly-eager checking of default arguments of template template
parameters. We now perform only minimal checking of such default
arguments when they are initially parsed.

llvm-svn: 86864

10 files changed, 207 insertions, 42 deletions

diff --git a/clang/include/clang/Basic/DiagnosticSemaKinds.td b/clang/include/clang/Basic/DiagnosticSemaKinds.td
index e4ebb5ecc7c..e0ac0ada8bd 100644
--- a/clang/include/clang/Basic/DiagnosticSemaKinds.td
+++ b/clang/include/clang/Basic/DiagnosticSemaKinds.td
@@ -1099,6 +1099,10 @@ def note_function_template_deduction_instantiation_here : Note<
 def note_partial_spec_deduct_instantiation_here : Note<
   "during template argument deduction for class template partial "
   "specialization %0, here">;
+def note_prior_template_arg_substitution : Note<
+  "while substituting prior template arguments into %select{non-type|template}0"
+  " template parameter%1 %2">;
+  
 def err_field_instantiates_to_function : Error<
   "data member instantiated with function type %0">;
 def err_nested_name_spec_non_tag : Error<
diff --git a/clang/lib/Sema/Sema.h b/clang/lib/Sema/Sema.h
index 6c88995a1bf..b2e0751f443 100644
--- a/clang/lib/Sema/Sema.h
+++ b/clang/lib/Sema/Sema.h
@@ -2650,6 +2650,11 @@ public:
   std::string
   getTemplateArgumentBindingsText(const TemplateParameterList *Params,
                                   const TemplateArgumentList &Args);
+
+  std::string
+  getTemplateArgumentBindingsText(const TemplateParameterList *Params,
+                                  const TemplateArgument *Args,
+                                  unsigned NumArgs);
   
   /// \brief Describes the result of template argument deduction.
   ///
@@ -2872,17 +2877,26 @@ public:
       /// partial specialization or a function template. The
       /// Entity is either a ClassTemplatePartialSpecializationDecl or
       /// a FunctionTemplateDecl.
-      DeducedTemplateArgumentSubstitution
+      DeducedTemplateArgumentSubstitution,
+      
+      /// We are substituting prior template arguments into a new
+      /// template parameter. The template parameter itself is either a
+      /// NonTypeTemplateParmDecl or a TemplateTemplateParmDecl.
+      PriorTemplateArgumentSubstitution
     } Kind;
 
     /// \brief The point of instantiation within the source code.
     SourceLocation PointOfInstantiation;
 
+    /// \brief The template in which we are performing the instantiation,
+    /// for substitutions of prior template arguments.
+    TemplateDecl *Template;
+    
     /// \brief The entity that is being instantiated.
     uintptr_t Entity;
 
-    // \brief If this the instantiation of a default template
-    // argument, the list of template arguments.
+    /// \brief The list of template arguments we are substituting, if they
+    /// are not part of the entity.
     const TemplateArgument *TemplateArgs;
 
     /// \brief The number of template arguments in TemplateArgs.
@@ -2893,8 +2907,9 @@ public:
     /// template instantiation.
     SourceRange InstantiationRange;
 
-    ActiveTemplateInstantiation() : Kind(TemplateInstantiation), Entity(0),
-                                    TemplateArgs(0), NumTemplateArgs(0) {}
+    ActiveTemplateInstantiation()
+      : Kind(TemplateInstantiation), Template(0), Entity(0), TemplateArgs(0), 
+        NumTemplateArgs(0) {}
 
     friend bool operator==(const ActiveTemplateInstantiation &X,
                            const ActiveTemplateInstantiation &Y) {
@@ -2908,6 +2923,12 @@ public:
       case TemplateInstantiation:
         return true;
 
+      case PriorTemplateArgumentSubstitution:
+        if (X.Template != Y.Template)
+          return false;
+          
+        // Fall through
+          
       case DefaultTemplateArgumentInstantiation:
       case ExplicitTemplateArgumentSubstitution:
       case DeducedTemplateArgumentSubstitution:
@@ -2993,6 +3014,22 @@ public:
                           unsigned NumTemplateArgs,
                           SourceRange InstantiationRange = SourceRange());
 
+    /// \brief Note that we are substituting prior template arguments into a
+    /// non-type or template template parameter.
+    InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
+                          TemplateDecl *Template,
+                          NonTypeTemplateParmDecl *Param,
+                          const TemplateArgument *TemplateArgs,
+                          unsigned NumTemplateArgs,
+                          SourceRange InstantiationRange);
+
+    InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
+                          TemplateDecl *Template,
+                          TemplateTemplateParmDecl *Param,
+                          const TemplateArgument *TemplateArgs,
+                          unsigned NumTemplateArgs,
+                          SourceRange InstantiationRange);
+    
     /// \brief Note that we have finished instantiating this template.
     void Clear();
 
diff --git a/clang/lib/Sema/SemaTemplate.cpp b/clang/lib/Sema/SemaTemplate.cpp
index ce2ffc1ac18..6770385cfad 100644
--- a/clang/lib/Sema/SemaTemplate.cpp
+++ b/clang/lib/Sema/SemaTemplate.cpp
@@ -566,13 +566,21 @@ void Sema::ActOnTemplateTemplateParameterDefault(DeclPtrTy TemplateParamD,
   //   A template-parameter shall not be used in its own default argument.
   // FIXME: Implement this check! Needs a recursive walk over the types.
 
-  // Check the well-formedness of the template argument.
+  // Check only that we have a template template argument. We don't want to
+  // try to check well-formedness now, because our template template parameter
+  // might have dependent types in its template parameters, which we wouldn't
+  // be able to match now.
+  //
+  // If none of the template template parameter's template arguments mention
+  // other template parameters, we could actually perform more checking here.
+  // However, it isn't worth doing.
   TemplateArgumentLoc DefaultArg = translateTemplateArgument(*this, Default);
-  if (CheckTemplateArgument(TemplateParm, DefaultArg)) {
-    TemplateParm->setInvalidDecl();
+  if (DefaultArg.getArgument().getAsTemplate().isNull()) {
+    Diag(DefaultArg.getLocation(), diag::err_template_arg_not_class_template)
+      << DefaultArg.getSourceRange();
     return;
   }
-
+  
   TemplateParm->setDefaultArgument(DefaultArg);
 }
 
@@ -1739,8 +1747,8 @@ bool Sema::CheckTemplateArgumentList(TemplateDecl *Template,
       QualType NTTPType = NTTP->getType();
       if (NTTPType->isDependentType()) {
         // Do substitution on the type of the non-type template parameter.
-        InstantiatingTemplate Inst(*this, TemplateLoc,
-                                   Template, Converted.getFlatArguments(),
+        InstantiatingTemplate Inst(*this, TemplateLoc, Template,
+                                   NTTP, Converted.getFlatArguments(),
                                    Converted.flatSize(),
                                    SourceRange(TemplateLoc, RAngleLoc));
 
@@ -1850,6 +1858,30 @@ bool Sema::CheckTemplateArgumentList(TemplateDecl *Template,
       TemplateTemplateParmDecl *TempParm
         = cast<TemplateTemplateParmDecl>(*Param);
 
+      // Substitute into the template parameter list of the template
+      // template parameter, since previously-supplied template arguments
+      // may appear within the template template parameter.
+      {
+        // Set up a template instantiation context.
+        LocalInstantiationScope Scope(*this);
+        InstantiatingTemplate Inst(*this, TemplateLoc, Template,
+                                   TempParm, Converted.getFlatArguments(),
+                                   Converted.flatSize(),
+                                   SourceRange(TemplateLoc, RAngleLoc));
+      
+        TemplateArgumentList TemplateArgs(Context, Converted,
+                                          /*TakeArgs=*/false);
+        TempParm = cast_or_null<TemplateTemplateParmDecl>(
+                        SubstDecl(TempParm, CurContext, 
+                                 MultiLevelTemplateArgumentList(TemplateArgs)));
+        if (!TempParm) {
+          Invalid = true;
+          break;
+        }
+        
+        // FIXME: TempParam is leaked.
+      }
+      
       switch (Arg.getArgument().getKind()) {
       case TemplateArgument::Null:
         assert(false && "Should never see a NULL template argument here");
@@ -2518,9 +2550,9 @@ Sema::TemplateParameterListsAreEqual(TemplateParameterList *New,
           NextDiag = diag::note_template_param_different_kind;
         }
         Diag((*NewParm)->getLocation(), NextDiag)
-        << IsTemplateTemplateParm;
+          << IsTemplateTemplateParm;
         Diag((*OldParm)->getLocation(), diag::note_template_prev_declaration)
-        << IsTemplateTemplateParm;
+          << IsTemplateTemplateParm;
       }
       return false;
     }
@@ -2528,21 +2560,6 @@ Sema::TemplateParameterListsAreEqual(TemplateParameterList *New,
     if (isa<TemplateTypeParmDecl>(*OldParm)) {
       // Okay; all template type parameters are equivalent (since we
       // know we're at the same index).
-#if 0
-      // FIXME: Enable this code in debug mode *after* we properly go through
-      // and "instantiate" the template parameter lists of template template
-      // parameters. It's only after this instantiation that (1) any dependent
-      // types within the template parameter list of the template template
-      // parameter can be checked, and (2) the template type parameter depths
-      // will match up.
-      QualType OldParmType
-        = Context.getTypeDeclType(cast<TemplateTypeParmDecl>(*OldParm));
-      QualType NewParmType
-        = Context.getTypeDeclType(cast<TemplateTypeParmDecl>(*NewParm));
-      assert(Context.getCanonicalType(OldParmType) ==
-             Context.getCanonicalType(NewParmType) &&
-             "type parameter mismatch?");
-#endif
     } else if (NonTypeTemplateParmDecl *OldNTTP
                  = dyn_cast<NonTypeTemplateParmDecl>(*OldParm)) {
       // The types of non-type template parameters must agree.
@@ -2566,10 +2583,13 @@ Sema::TemplateParameterListsAreEqual(TemplateParameterList *New,
         }
         return false;
       }
+      assert(OldNTTP->getDepth() == NewNTTP->getDepth() && 
+             "Non-type template parameter depth mismatch");
+      assert(OldNTTP->getPosition() == NewNTTP->getPosition() && 
+             "Non-type template parameter position mismatch");
     } else {
       // The template parameter lists of template template
       // parameters must agree.
-      // FIXME: Could we perform a faster "type" comparison here?
       assert(isa<TemplateTemplateParmDecl>(*OldParm) &&
              "Only template template parameters handled here");
       TemplateTemplateParmDecl *OldTTP
@@ -2582,6 +2602,11 @@ Sema::TemplateParameterListsAreEqual(TemplateParameterList *New,
                                           /*IsTemplateTemplateParm=*/true,
                                           TemplateArgLoc))
         return false;
+      
+      assert(OldTTP->getDepth() == NewTTP->getDepth() && 
+             "Template template parameter depth mismatch");
+      assert(OldTTP->getPosition() == NewTTP->getPosition() && 
+             "Template template parameter position mismatch");      
     }
   }
 
@@ -4594,12 +4619,24 @@ QualType Sema::RebuildTypeInCurrentInstantiation(QualType T, SourceLocation Loc,
 std::string
 Sema::getTemplateArgumentBindingsText(const TemplateParameterList *Params,
                                       const TemplateArgumentList &Args) {
+  // FIXME: For variadic templates, we'll need to get the structured list.
+  return getTemplateArgumentBindingsText(Params, Args.getFlatArgumentList(),
+                                         Args.flat_size());
+}
+
+std::string
+Sema::getTemplateArgumentBindingsText(const TemplateParameterList *Params,
+                                      const TemplateArgument *Args,
+                                      unsigned NumArgs) {
   std::string Result;
 
-  if (!Params || Params->size() == 0)
+  if (!Params || Params->size() == 0 || NumArgs == 0)
     return Result;
   
   for (unsigned I = 0, N = Params->size(); I != N; ++I) {
+    if (I >= NumArgs)
+      break;
+    
     if (I == 0)
       Result += "[with ";
     else
diff --git a/clang/lib/Sema/SemaTemplateInstantiate.cpp b/clang/lib/Sema/SemaTemplateInstantiate.cpp
index 74f521e3cf2..b1e0481932f 100644
--- a/clang/lib/Sema/SemaTemplateInstantiate.cpp
+++ b/clang/lib/Sema/SemaTemplateInstantiate.cpp
@@ -190,26 +190,69 @@ Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
 }
 
 Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
-                                          SourceLocation PointOfInstantation,
+                                          SourceLocation PointOfInstantiation,
                                           ParmVarDecl *Param,
                                           const TemplateArgument *TemplateArgs,
                                           unsigned NumTemplateArgs,
                                           SourceRange InstantiationRange)
   : SemaRef(SemaRef) {
 
-  Invalid = CheckInstantiationDepth(PointOfInstantation, InstantiationRange);
+  Invalid = CheckInstantiationDepth(PointOfInstantiation, InstantiationRange);
 
   if (!Invalid) {
     ActiveTemplateInstantiation Inst;
     Inst.Kind
       = ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation;
-    Inst.PointOfInstantiation = PointOfInstantation;
+    Inst.PointOfInstantiation = PointOfInstantiation;
+    Inst.Entity = reinterpret_cast<uintptr_t>(Param);
+    Inst.TemplateArgs = TemplateArgs;
+    Inst.NumTemplateArgs = NumTemplateArgs;
+    Inst.InstantiationRange = InstantiationRange;
+    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
+  }
+}
+
+Sema::InstantiatingTemplate::
+InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
+                      TemplateDecl *Template,
+                      NonTypeTemplateParmDecl *Param,
+                      const TemplateArgument *TemplateArgs,
+                      unsigned NumTemplateArgs,
+                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
+  Invalid = CheckInstantiationDepth(PointOfInstantiation, InstantiationRange);
+  
+  if (!Invalid) {
+    ActiveTemplateInstantiation Inst;
+    Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
+    Inst.PointOfInstantiation = PointOfInstantiation;
+    Inst.Template = Template;
+    Inst.Entity = reinterpret_cast<uintptr_t>(Param);
+    Inst.TemplateArgs = TemplateArgs;
+    Inst.NumTemplateArgs = NumTemplateArgs;
+    Inst.InstantiationRange = InstantiationRange;
+    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
+  }
+}
+
+Sema::InstantiatingTemplate::
+InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
+                      TemplateDecl *Template,
+                      TemplateTemplateParmDecl *Param,
+                      const TemplateArgument *TemplateArgs,
+                      unsigned NumTemplateArgs,
+                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
+  Invalid = CheckInstantiationDepth(PointOfInstantiation, InstantiationRange);
+  
+  if (!Invalid) {
+    ActiveTemplateInstantiation Inst;
+    Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
+    Inst.PointOfInstantiation = PointOfInstantiation;
+    Inst.Template = Template;
     Inst.Entity = reinterpret_cast<uintptr_t>(Param);
     Inst.TemplateArgs = TemplateArgs;
     Inst.NumTemplateArgs = NumTemplateArgs;
     Inst.InstantiationRange = InstantiationRange;
     SemaRef.ActiveTemplateInstantiations.push_back(Inst);
-    Invalid = false;
   }
 }
 
@@ -331,6 +374,23 @@ void Sema::PrintInstantiationStack() {
       break;
     }
 
+    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution: {
+      NamedDecl *Parm = cast<NamedDecl>((Decl *)Active->Entity);
+      std::string Name;
+      if (!Parm->getName().empty())
+        Name = std::string(" '") + Parm->getName().str() + "'";
+                                        
+      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
+                   diag::note_prior_template_arg_substitution)
+        << isa<TemplateTemplateParmDecl>(Parm)
+        << Name
+        << getTemplateArgumentBindingsText(
+                                    Active->Template->getTemplateParameters(), 
+                                           Active->TemplateArgs, 
+                                           Active->NumTemplateArgs)
+        << Active->InstantiationRange;
+      break;
+    }
     }
   }
 }
@@ -351,8 +411,10 @@ bool Sema::isSFINAEContext() const {
       return false;
 
     case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation:
-      // A default template argument instantiation may or may not be a
-      // SFINAE context; look further up the stack.
+    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution:
+      // A default template argument instantiation and substitution into
+      // template parameters with arguments for prior parameters may or may 
+      // not be a SFINAE context; look further up the stack.
       break;
 
     case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution:
@@ -910,9 +972,9 @@ Sema::InstantiateClass(SourceLocation PointOfInstantiation,
        Member != MemberEnd; ++Member) {
     Decl *NewMember = SubstDecl(*Member, Instantiation, TemplateArgs);
     if (NewMember) {
-      if (NewMember->isInvalidDecl())
+      if (NewMember->isInvalidDecl()) {
         Invalid = true;
-      else if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
+      } 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);
diff --git a/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp b/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp
index db797d6f986..ab712946dc5 100644
--- a/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp
+++ b/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp
@@ -1051,7 +1051,7 @@ TemplateDeclInstantiator::SubstTemplateParams(TemplateParameterList *L) {
        PI != PE; ++PI) {
     NamedDecl *D = cast_or_null<NamedDecl>(Visit(*PI));
     Params.push_back(D);
-    Invalid = Invalid || !D;
+    Invalid = Invalid || !D || D->isInvalidDecl();
   }
 
   // Clean up if we had an error.
diff --git a/clang/test/CXX/temp/temp.param/p12.cpp b/clang/test/CXX/temp/temp.param/p12.cpp
index 5511224ebe9..10bdb656649 100644
--- a/clang/test/CXX/temp/temp.param/p12.cpp
+++ b/clang/test/CXX/temp/temp.param/p12.cpp
@@ -34,4 +34,6 @@ template<int N,
 // Check validity of default arguments
 template<template<class, int> class // expected-note{{previous template template parameter is here}}
            = Y1> // expected-error{{template template argument has different template parameters than its corresponding template template parameter}}
-  class C1; 
+  class C1 {};
+
+C1<> c1;
diff --git a/clang/test/SemaTemplate/default-arguments.cpp b/clang/test/SemaTemplate/default-arguments.cpp
index 8352afdb0dc..e1999218dd0 100644
--- a/clang/test/SemaTemplate/default-arguments.cpp
+++ b/clang/test/SemaTemplate/default-arguments.cpp
@@ -107,3 +107,14 @@ template<typename T, template<typename> class X = T::template apply>
   struct X4;
 int array4[is_same<X4<add_pointer>, 
                    X4<add_pointer, add_pointer::apply> >::value? 1 : -1];
+
+template<int> struct X5 {}; // expected-note{{has a different type 'int'}}
+template<long> struct X5b {};
+template<typename T, 
+         template<T> class B = X5> // expected-error{{template template argument has different}} \
+                                   // expected-note{{previous non-type template parameter}}
+  struct X6 {};
+
+X6<int> x6a;
+X6<long> x6b;
+X6<long, X5b> x6c;
diff --git a/clang/test/SemaTemplate/instantiate-template-template-parm.cpp b/clang/test/SemaTemplate/instantiate-template-template-parm.cpp
index b158251915a..00b2c0ecc2f 100644
--- a/clang/test/SemaTemplate/instantiate-template-template-parm.cpp
+++ b/clang/test/SemaTemplate/instantiate-template-template-parm.cpp
@@ -19,3 +19,15 @@ int i;
 apply<add_pointer, int>::type ip = &i;
 apply<add_reference, int>::type ir = i;
 apply<add_reference, float>::type fr = i; // expected-error{{non-const lvalue reference to type 'float' cannot be initialized with a value of type 'int'}}
+
+// Template template parameters
+template<int> struct B; // expected-note{{has a different type 'int'}}
+
+template<typename T, 
+         template<T Value> class X> // expected-error{{cannot have type 'float'}} \
+                                    // expected-note{{with type 'long'}}
+struct X0 { };
+
+X0<int, B> x0b1;
+X0<float, B> x0b2; // expected-note{{while substituting}}
+X0<long, B> x0b3; // expected-error{{template template argument has different template parameters}}
diff --git a/clang/test/SemaTemplate/instantiation-default-2.cpp b/clang/test/SemaTemplate/instantiation-default-2.cpp
index 740832c5ba3..4d9a0e2717b 100644
--- a/clang/test/SemaTemplate/instantiation-default-2.cpp
+++ b/clang/test/SemaTemplate/instantiation-default-2.cpp
@@ -15,4 +15,4 @@ Constant<float (*)(int, double), &f> *c5;
 
 Constant<float (*)(int, int), f> *c6; // expected-error{{non-type template argument of type 'float (*)(int, double)' cannot be converted to a value of type 'float (*)(int, int)'}}
 
-Constant<float, 0> *c7; // expected-note{{in instantiation of default argument for 'Constant<float>' required here}}
+Constant<float, 0> *c7; // expected-note{{while substituting}}
diff --git a/clang/test/SemaTemplate/nested-template.cpp b/clang/test/SemaTemplate/nested-template.cpp
index 849d835541f..e18329c145d 100644
--- a/clang/test/SemaTemplate/nested-template.cpp
+++ b/clang/test/SemaTemplate/nested-template.cpp
@@ -122,7 +122,7 @@ template<typename T,
   struct X2_arg;
 
 X2<int>::Inner<X2_arg> x2i1;
-X2<float>::Inner<X2_arg> x2i2; // expected-note{{instantiation}}
+X2<float> x2a; // expected-note{{instantiation}}
 X2<long>::Inner<X2_arg> x2i3; // expected-error{{template template argument has different}}