Template argument deduction for template template parameters. This

permits, among other things, ripping apart and reconstructing
templates via partial specialization:

  template<typename T> 
  struct DeepRemoveConst { typedef T type; };

  template<typename T>
  struct DeepRemoveConst<const T> {
    typedef typename DeepRemoveConst<T>::type type;
  };

  template<template<typename> class TT, typename T>
  struct DeepRemoveConst<TT<T> > {
    typedef TT<typename DeepRemoveConst<T>::type> type;
  };

Also, fix a longstanding thinko in the code handling partial ordering
of class template partial specializations. We were performing the
second deduction without clearing out the results of the first
deduction. It's amazing we got through so much code with such a
horrendous error :(



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

5 files changed, 136 insertions, 52 deletions

diff --git a/include/clang/AST/ASTContext.h b/include/clang/AST/ASTContext.h
index 7392170be9..20ed4ef539 100644
--- a/include/clang/AST/ASTContext.h
+++ b/include/clang/AST/ASTContext.h
@@ -925,6 +925,10 @@ public:
   /// types, values, and templates.
   TemplateName getCanonicalTemplateName(TemplateName Name);
 
+  /// \brief Determine whether the given template names refer to the same
+  /// template.
+  bool hasSameTemplateName(TemplateName X, TemplateName Y);
+  
   /// \brief Retrieve the "canonical" template argument.
   ///
   /// The canonical template argument is the simplest template argument
diff --git a/lib/AST/ASTContext.cpp b/lib/AST/ASTContext.cpp
index b5d9cac9fa..0add7e65cc 100644
--- a/lib/AST/ASTContext.cpp
+++ b/lib/AST/ASTContext.cpp
@@ -2350,6 +2350,12 @@ TemplateName ASTContext::getCanonicalTemplateName(TemplateName Name) {
   return DTN->CanonicalTemplateName;
 }
 
+bool ASTContext::hasSameTemplateName(TemplateName X, TemplateName Y) {
+  X = getCanonicalTemplateName(X);
+  Y = getCanonicalTemplateName(Y);
+  return X.getAsVoidPointer() == Y.getAsVoidPointer();
+}
+
 TemplateArgument
 ASTContext::getCanonicalTemplateArgument(const TemplateArgument &Arg) {
   switch (Arg.getKind()) {
diff --git a/lib/Sema/SemaTemplate.cpp b/lib/Sema/SemaTemplate.cpp
index ee928bccaf..9305d6ebb1 100644
--- a/lib/Sema/SemaTemplate.cpp
+++ b/lib/Sema/SemaTemplate.cpp
@@ -2607,10 +2607,6 @@ 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.
@@ -2626,11 +2622,6 @@ 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");      
     }
   }
 
diff --git a/lib/Sema/SemaTemplateDeduction.cpp b/lib/Sema/SemaTemplateDeduction.cpp
index 2eb3af2b60..fa45806a72 100644
--- a/lib/Sema/SemaTemplateDeduction.cpp
+++ b/lib/Sema/SemaTemplateDeduction.cpp
@@ -168,32 +168,48 @@ DeduceNonTypeTemplateArgument(ASTContext &Context,
 
 static Sema::TemplateDeductionResult
 DeduceTemplateArguments(ASTContext &Context,
+                        TemplateParameterList *TemplateParams,
                         TemplateName Param,
                         TemplateName Arg,
                         Sema::TemplateDeductionInfo &Info,
                         llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
-  // FIXME: Implement template argument deduction for template
-  // template parameters.
-
-  // FIXME: this routine does not have enough information to produce
-  // good diagnostics.
-
   TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
-  TemplateDecl *ArgDecl = Arg.getAsTemplateDecl();
-
-  if (!ParamDecl || !ArgDecl) {
-    // FIXME: fill in Info.Param/Info.FirstArg
-    return Sema::TDK_Inconsistent;
+  if (!ParamDecl) {
+    // The parameter type is dependent and is not a template template parameter,
+    // so there is nothing that we can deduce.
+    return Sema::TDK_Success;
   }
-
-  ParamDecl = cast<TemplateDecl>(ParamDecl->getCanonicalDecl());
-  ArgDecl = cast<TemplateDecl>(ArgDecl->getCanonicalDecl());
-  if (ParamDecl != ArgDecl) {
-    // FIXME: fill in Info.Param/Info.FirstArg
+  
+  if (TemplateTemplateParmDecl *TempParam
+        = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
+    // Bind the template template parameter to the given template name.
+    TemplateArgument &ExistingArg = Deduced[TempParam->getIndex()];
+    if (ExistingArg.isNull()) {
+      // This is the first deduction for this template template parameter.
+      ExistingArg = TemplateArgument(Context.getCanonicalTemplateName(Arg));
+      return Sema::TDK_Success;
+    }
+    
+    // Verify that the previous binding matches this deduction.
+    assert(ExistingArg.getKind() == TemplateArgument::Template);
+    if (Context.hasSameTemplateName(ExistingArg.getAsTemplate(), Arg))
+      return Sema::TDK_Success;
+    
+    // Inconsistent deduction.
+    Info.Param = TempParam;
+    Info.FirstArg = ExistingArg;
+    Info.SecondArg = TemplateArgument(Arg);
     return Sema::TDK_Inconsistent;
   }
-
-  return Sema::TDK_Success;
+  
+  // Verify that the two template names are equivalent.
+  if (Context.hasSameTemplateName(Param, Arg))
+    return Sema::TDK_Success;
+  
+  // Mismatch of non-dependent template parameter to argument.
+  Info.FirstArg = TemplateArgument(Param);
+  Info.SecondArg = TemplateArgument(Arg);
+  return Sema::TDK_NonDeducedMismatch;
 }
 
 /// \brief Deduce the template arguments by comparing the template parameter
@@ -224,32 +240,20 @@ DeduceTemplateArguments(ASTContext &Context,
   assert(Arg.isCanonical() && "Argument type must be canonical");
 
   // Check whether the template argument is a dependent template-id.
-  // FIXME: This is untested code; it can be tested when we implement
-  // partial ordering of class template partial specializations.
   if (const TemplateSpecializationType *SpecArg
         = dyn_cast<TemplateSpecializationType>(Arg)) {
     // Perform template argument deduction for the template name.
     if (Sema::TemplateDeductionResult Result
-          = DeduceTemplateArguments(Context,
+          = DeduceTemplateArguments(Context, TemplateParams,
                                     Param->getTemplateName(),
                                     SpecArg->getTemplateName(),
                                     Info, Deduced))
       return Result;
 
-    unsigned NumArgs = Param->getNumArgs();
-
-    // FIXME: When one of the template-names refers to a
-    // declaration with default template arguments, do we need to
-    // fill in those default template arguments here? Most likely,
-    // the answer is "yes", but I don't see any references. This
-    // issue may be resolved elsewhere, because we may want to
-    // instantiate default template arguments when we actually write
-    // the template-id.
-    if (SpecArg->getNumArgs() != NumArgs)
-      return Sema::TDK_NonDeducedMismatch;
 
     // Perform template argument deduction on each template
     // argument.
+    unsigned NumArgs = std::min(SpecArg->getNumArgs(), Param->getNumArgs());
     for (unsigned I = 0; I != NumArgs; ++I)
       if (Sema::TemplateDeductionResult Result
             = DeduceTemplateArguments(Context, TemplateParams,
@@ -276,13 +280,12 @@ DeduceTemplateArguments(ASTContext &Context,
   // Perform template argument deduction for the template name.
   if (Sema::TemplateDeductionResult Result
         = DeduceTemplateArguments(Context,
+                                  TemplateParams,
                                   Param->getTemplateName(),
                                TemplateName(SpecArg->getSpecializedTemplate()),
                                   Info, Deduced))
     return Result;
 
-  // FIXME: Can the # of arguments in the parameter and the argument
-  // differ due to default arguments?
   unsigned NumArgs = Param->getNumArgs();
   const TemplateArgumentList &ArgArgs = SpecArg->getTemplateArgs();
   if (NumArgs != ArgArgs.size())
@@ -639,9 +642,9 @@ DeduceTemplateArguments(ASTContext &Context,
 
     //     template-name<T> (where template-name refers to a class template)
     //     template-name<i>
-    //     TT<T> (TODO)
-    //     TT<i> (TODO)
-    //     TT<> (TODO)
+    //     TT<T>
+    //     TT<i>
+    //     TT<>
     case Type::TemplateSpecialization: {
       const TemplateSpecializationType *SpecParam
         = cast<TemplateSpecializationType>(Param);
@@ -793,14 +796,10 @@ DeduceTemplateArguments(ASTContext &Context,
     return Sema::TDK_NonDeducedMismatch;
       
   case TemplateArgument::Template:
-#if 0
-      // FIXME: We need template argument deduction for template template
-      // parameters.
-      if (Arg.getKind() == TemplateArgument::Template)
+    if (Arg.getKind() == TemplateArgument::Template)
       return DeduceTemplateArguments(Context, TemplateParams, 
                                      Param.getAsTemplate(),
-                                     Arg.getAsTemplate(), Info, Deduced, 0);
-#endif
+                                     Arg.getAsTemplate(), Info, Deduced);
     Info.FirstArg = Param;
     Info.SecondArg = Arg;
     return Sema::TDK_NonDeducedMismatch;
@@ -2092,6 +2091,7 @@ Sema::getMoreSpecializedPartialSpecialization(
                                                                0);
 
   // Determine whether PS2 is at least as specialized as PS1
+  Deduced.clear();
   Deduced.resize(PS1->getTemplateParameters()->size());
   bool Better2 = !DeduceTemplateArgumentsDuringPartialOrdering(Context,
                                                   PS1->getTemplateParameters(),
diff --git a/test/SemaTemplate/deduction.cpp b/test/SemaTemplate/deduction.cpp
new file mode 100644
index 0000000000..7b7e18f74a
--- /dev/null
+++ b/test/SemaTemplate/deduction.cpp
@@ -0,0 +1,83 @@
+// RUN: clang-cc -fsyntax-only %s
+
+// Template argument deduction with template template parameters.
+template<typename T, template<T> class A> 
+struct X0 {
+  static const unsigned value = 0;
+};
+
+template<template<int> class A>
+struct X0<int, A> {
+  static const unsigned value = 1;
+};
+
+template<int> struct X0i;
+template<long> struct X0l;
+int array_x0a[X0<long, X0l>::value == 0? 1 : -1];
+int array_x0b[X0<int, X0i>::value == 1? 1 : -1];
+
+template<typename T, typename U>
+struct is_same {
+  static const bool value = false;
+};
+
+template<typename T>
+struct is_same<T, T> {
+  static const bool value = true;
+};
+
+template<typename T> struct allocator { };
+template<typename T, typename Alloc = allocator<T> > struct vector {};
+
+// Fun with meta-lambdas!
+struct _1 {};
+struct _2 {};
+
+// Replaces all occurrences of _1 with Arg1 and _2 with Arg2 in T.
+template<typename T, typename Arg1, typename Arg2>
+struct Replace {
+  typedef T type;
+};
+
+// Replacement of the whole type.
+template<typename Arg1, typename Arg2>
+struct Replace<_1, Arg1, Arg2> {
+  typedef Arg1 type;
+};
+
+template<typename Arg1, typename Arg2>
+struct Replace<_2, Arg1, Arg2> {
+  typedef Arg2 type;
+};
+
+// Replacement through cv-qualifiers
+template<typename T, typename Arg1, typename Arg2>
+struct Replace<const T, Arg1, Arg2> {
+  typedef typename Replace<T, Arg1, Arg2>::type const type;
+};
+
+// Replacement of templates
+template<template<typename> class TT, typename T1, typename Arg1, typename Arg2>
+struct Replace<TT<T1>, Arg1, Arg2> {
+  typedef TT<typename Replace<T1, Arg1, Arg2>::type> type;
+};
+
+template<template<typename, typename> class TT, typename T1, typename T2,
+         typename Arg1, typename Arg2>
+struct Replace<TT<T1, T2>, Arg1, Arg2> {
+  typedef TT<typename Replace<T1, Arg1, Arg2>::type,
+             typename Replace<T2, Arg1, Arg2>::type> type;
+};
+
+// Just for kicks...
+template<template<typename, typename> class TT, typename T1,
+         typename Arg1, typename Arg2>
+struct Replace<TT<T1, _2>, Arg1, Arg2> {
+  typedef TT<typename Replace<T1, Arg1, Arg2>::type, Arg2> type;
+};
+
+int array0[is_same<Replace<_1, int, float>::type, int>::value? 1 : -1];
+int array1[is_same<Replace<const _1, int, float>::type, const int>::value? 1 : -1];
+int array2[is_same<Replace<vector<_1>, int, float>::type, vector<int> >::value? 1 : -1];
+int array3[is_same<Replace<vector<const _1>, int, float>::type, vector<const int> >::value? 1 : -1];
+int array4[is_same<Replace<vector<int, _2>, double, float>::type, vector<int, float> >::value? 1 : -1];