Implement template argument deduction for pack expansions whose

pattern is a template argument, which involves repeatedly deducing
template arguments using the pattern of the pack expansion, then
bundling the resulting deductions into an argument pack.

We can now handle a variety of simple list-handling metaprograms using
variadic templates. See, e.g., the new "count" metaprogram.


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

10 files changed, 247 insertions, 61 deletions

diff --git a/include/clang/AST/DeclTemplate.h b/include/clang/AST/DeclTemplate.h
index 6628b3ffb0..7a311c8741 100644
--- a/include/clang/AST/DeclTemplate.h
+++ b/include/clang/AST/DeclTemplate.h
@@ -417,11 +417,6 @@ class DependentFunctionTemplateSpecializationInfo {
     return reinterpret_cast<FunctionTemplateDecl*const*>(this+1);
   }
 
-  const TemplateArgumentLoc *getTemplateArgs() const {
-    return reinterpret_cast<const TemplateArgumentLoc*>(
-             &getTemplates()[getNumTemplates()]);
-  }
-
 public:
   DependentFunctionTemplateSpecializationInfo(
                                  const UnresolvedSetImpl &Templates,
@@ -439,6 +434,12 @@ public:
     return getTemplates()[I];
   }
 
+  /// \brief Returns the explicit template arguments that were given.
+  const TemplateArgumentLoc *getTemplateArgs() const {
+    return reinterpret_cast<const TemplateArgumentLoc*>(
+                                                        &getTemplates()[getNumTemplates()]);
+  }
+
   /// \brief Returns the number of explicit template arguments that were given.
   unsigned getNumTemplateArgs() const {
     return d.NumArgs;
diff --git a/include/clang/AST/TemplateBase.h b/include/clang/AST/TemplateBase.h
index 4096dc1731..c7cb2fbe8e 100644
--- a/include/clang/AST/TemplateBase.h
+++ b/include/clang/AST/TemplateBase.h
@@ -285,6 +285,12 @@ public:
   /// same.
   bool structurallyEquals(const TemplateArgument &Other) const;
 
+  /// \brief When the template argument is a pack expansion, returns 
+  /// the pattern of the pack expansion.
+  ///
+  /// \param Ellipsis Will be set to the location of the ellipsis.
+  TemplateArgument getPackExpansionPattern() const;
+
   /// \brief Print this template argument to the given output stream.
   void print(const PrintingPolicy &Policy, llvm::raw_ostream &Out) const;
              
diff --git a/include/clang/Basic/DiagnosticSemaKinds.td b/include/clang/Basic/DiagnosticSemaKinds.td
index 9742501088..50439d0fa0 100644
--- a/include/clang/Basic/DiagnosticSemaKinds.td
+++ b/include/clang/Basic/DiagnosticSemaKinds.td
@@ -1868,8 +1868,8 @@ def err_pack_expansion_instantiation_unsupported : Error<
   "clang cannot yet instantiate pack expansions">;
 def err_pack_expansion_mismatch_unsupported : Error<
   "clang cannot yet instantiate pack expansions with mismatched pack levels">;
-def err_pack_expansion_deduction : Error<
-  "clang cannot yet perform template argument deduction for a pack expansion">;
+def err_pack_expansion_deduction_compare : Error<
+  "clang cannot yet compare deduced template argument packs">;
 
 def err_unexpected_typedef : Error<
   "unexpected type name %0: expected expression">;
diff --git a/include/clang/Sema/Sema.h b/include/clang/Sema/Sema.h
index 4eba0e5c3c..fe7c477061 100644
--- a/include/clang/Sema/Sema.h
+++ b/include/clang/Sema/Sema.h
@@ -3247,6 +3247,14 @@ public:
   ///
   /// \param Arg The template argument that will be traversed to find
   /// unexpanded parameter packs.
+  void collectUnexpandedParameterPacks(TemplateArgument Arg,
+                   llvm::SmallVectorImpl<UnexpandedParameterPack> &Unexpanded);
+
+  /// \brief Collect the set of unexpanded parameter packs within the given
+  /// template argument.  
+  ///
+  /// \param Arg The template argument that will be traversed to find
+  /// unexpanded parameter packs.
   void collectUnexpandedParameterPacks(TemplateArgumentLoc Arg,
                     llvm::SmallVectorImpl<UnexpandedParameterPack> &Unexpanded);
 
@@ -3862,7 +3870,8 @@ public:
   TemplateName
   SubstTemplateName(TemplateName Name, SourceLocation Loc,
                     const MultiLevelTemplateArgumentList &TemplateArgs);
-  bool Subst(const TemplateArgumentLoc &Arg, TemplateArgumentLoc &Result,
+  bool Subst(const TemplateArgumentLoc *Args, unsigned NumArgs,
+             TemplateArgumentListInfo &Result,
              const MultiLevelTemplateArgumentList &TemplateArgs);
 
   void InstantiateFunctionDefinition(SourceLocation PointOfInstantiation,
diff --git a/lib/AST/TemplateBase.cpp b/lib/AST/TemplateBase.cpp
index bfc834f090..04e8a389cf 100644
--- a/lib/AST/TemplateBase.cpp
+++ b/lib/AST/TemplateBase.cpp
@@ -191,6 +191,28 @@ bool TemplateArgument::structurallyEquals(const TemplateArgument &Other) const {
   return false;
 }
 
+TemplateArgument TemplateArgument::getPackExpansionPattern() const {
+  assert(isPackExpansion());
+  
+  switch (getKind()) {
+    case Type:
+      return getAsType()->getAs<PackExpansionType>()->getPattern();
+      
+    case Expression:
+    case Template:
+      // FIXME: Variadic templates.
+      llvm_unreachable("Expression and template pack expansions unsupported");
+      
+    case Declaration:
+    case Integral:
+    case Pack:
+    case Null:
+      return TemplateArgument();
+  }
+  
+  return TemplateArgument();
+}
+
 void TemplateArgument::print(const PrintingPolicy &Policy, 
                              llvm::raw_ostream &Out) const {
   switch (getKind()) {
diff --git a/lib/Sema/SemaTemplateDeduction.cpp b/lib/Sema/SemaTemplateDeduction.cpp
index 80ba1a3dd6..d5a036d4fb 100644
--- a/lib/Sema/SemaTemplateDeduction.cpp
+++ b/lib/Sema/SemaTemplateDeduction.cpp
@@ -21,6 +21,7 @@
 #include "clang/AST/StmtVisitor.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
+#include "llvm/ADT/BitVector.h"
 #include <algorithm>
 
 namespace clang {
@@ -947,6 +948,24 @@ static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args,
   return ArgIdx < NumArgs;
 }
 
+/// \brief Retrieve the depth and index of an unexpanded parameter pack.
+static std::pair<unsigned, unsigned> 
+getDepthAndIndex(UnexpandedParameterPack UPP) {
+  if (const TemplateTypeParmType *TTP
+                          = UPP.first.dyn_cast<const TemplateTypeParmType *>())
+    return std::make_pair(TTP->getDepth(), TTP->getIndex());
+  
+  if (TemplateTypeParmDecl *TTP = UPP.first.dyn_cast<TemplateTypeParmDecl *>())
+    return std::make_pair(TTP->getDepth(), TTP->getIndex());
+  
+  if (NonTypeTemplateParmDecl *NTTP 
+                              = UPP.first.dyn_cast<NonTypeTemplateParmDecl *>())
+    return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
+  
+  TemplateTemplateParmDecl *TTP = UPP.first.get<TemplateTemplateParmDecl *>();
+  return std::make_pair(TTP->getDepth(), TTP->getIndex());
+}
+
 static Sema::TemplateDeductionResult
 DeduceTemplateArguments(Sema &S,
                         TemplateParameterList *TemplateParams,
@@ -955,18 +974,32 @@ DeduceTemplateArguments(Sema &S,
                         TemplateDeductionInfo &Info,
                     llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
                         bool NumberOfArgumentsMustMatch) {
+  // C++0x [temp.deduct.type]p9:
+  //   If the template argument list of P contains a pack expansion that is not 
+  //   the last template argument, the entire template argument list is a 
+  //   non-deduced context.
+  // FIXME: Implement this.
+
+
+  // C++0x [temp.deduct.type]p9:
+  //   If P has a form that contains <T> or <i>, then each argument Pi of the 
+  //   respective template argument list P is compared with the corresponding 
+  //   argument Ai of the corresponding template argument list of A.
   unsigned ArgIdx = 0, ParamIdx = 0;
   for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams); 
        ++ParamIdx) {
+    // FIXME: Variadic templates.
+    // What do we do if the argument is a pack expansion?
+    
     if (!Params[ParamIdx].isPackExpansion()) {
-      // The simple case: deduce template arguments by matching P and A.
+      // The simple case: deduce template arguments by matching Pi and Ai.
       
       // Check whether we have enough arguments.
       if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
         return NumberOfArgumentsMustMatch? Sema::TDK_TooFewArguments 
                                          : Sema::TDK_Success;
       
-      // Perform deduction for this P/A pair.
+      // Perform deduction for this Pi/Ai pair.
       if (Sema::TemplateDeductionResult Result
           = DeduceTemplateArguments(S, TemplateParams,
                                     Params[ParamIdx], Args[ArgIdx],
@@ -978,12 +1011,107 @@ DeduceTemplateArguments(Sema &S,
       continue;
     }
     
-    // FIXME: Variadic templates. 
-    // The parameter is a pack expansion, so we'll
-    // need to repeatedly unify arguments against the parameter, capturing
-    // the bindings for each expanded parameter pack.
-    S.Diag(Info.getLocation(), diag::err_pack_expansion_deduction);
-    return Sema::TDK_TooManyArguments;
+    // The parameter is a pack expansion.
+    
+    // C++0x [temp.deduct.type]p9:
+    //   If Pi is a pack expansion, then the pattern of Pi is compared with 
+    //   each remaining argument in the template argument list of A. Each 
+    //   comparison deduces template arguments for subsequent positions in the 
+    //   template parameter packs expanded by Pi.
+    TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
+    
+    // Compute the set of template parameter indices that correspond to
+    // parameter packs expanded by the pack expansion.
+    llvm::SmallVector<unsigned, 2> PackIndices;
+    {
+      llvm::BitVector SawIndices(TemplateParams->size());
+      llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
+      S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
+      for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
+        unsigned Depth, Index;
+        llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
+        if (Depth == 0 && !SawIndices[Index]) {
+          SawIndices[Index] = true;
+          PackIndices.push_back(Index);
+        }
+      }
+    }
+    assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
+        
+    // FIXME: If there are no remaining arguments, we can bail out early
+    // and set any deduced parameter packs to an empty argument pack.
+    // The latter part of this is a (minor) correctness issue.
+    
+    // Save the deduced template arguments for each parameter pack expanded
+    // by this pack expansion, then clear out the deduction.
+    llvm::SmallVector<DeducedTemplateArgument, 2> 
+      SavedPacks(PackIndices.size());
+    for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
+      SavedPacks[I] = Deduced[PackIndices[I]];
+      Deduced[PackIndices[I]] = DeducedTemplateArgument();
+    }
+
+    // Keep track of the deduced template arguments for each parameter pack
+    // expanded by this pack expansion (the outer index) and for each 
+    // template argument (the inner SmallVectors).
+    llvm::SmallVector<llvm::SmallVector<DeducedTemplateArgument, 4>, 2>
+      NewlyDeducedPacks(PackIndices.size());
+    bool HasAnyArguments = false;
+    while (hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) {
+      HasAnyArguments = true;
+      
+      // Deduce template arguments from the pattern.
+      if (Sema::TemplateDeductionResult Result 
+            = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
+                                      Info, Deduced))
+        return Result;
+      
+      // Capture the deduced template arguments for each parameter pack expanded
+      // by this pack expansion, add them to the list of arguments we've deduced
+      // for that pack, then clear out the deduced argument.
+      for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
+        DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
+        if (!DeducedArg.isNull()) {
+          NewlyDeducedPacks[I].push_back(DeducedArg);
+          DeducedArg = DeducedTemplateArgument();
+        }
+      }
+      
+      ++ArgIdx;
+    }
+    
+    // Build argument packs for each of the parameter packs expanded by this
+    // pack expansion.
+    for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
+      if (HasAnyArguments && NewlyDeducedPacks[I].empty()) {
+        // We were not able to deduce anything for this parameter pack,
+        // so just restore the saved argument pack.
+        Deduced[PackIndices[I]] = SavedPacks[I];
+        continue;
+      }
+      
+      if (!SavedPacks[I].isNull()) {
+        // FIXME: Check against the existing argument pack.
+        S.Diag(Info.getLocation(), diag::err_pack_expansion_deduction_compare);
+        return Sema::TDK_TooFewArguments;
+      }
+      
+      if (NewlyDeducedPacks[I].empty()) {
+        // If we deduced an empty argument pack, create it now.
+        Deduced[PackIndices[I]]
+          = DeducedTemplateArgument(TemplateArgument(0, 0));
+        continue;
+      }
+                
+      TemplateArgument *ArgumentPack
+        = new (S.Context) TemplateArgument [NewlyDeducedPacks[I].size()];
+      std::copy(NewlyDeducedPacks[I].begin(), NewlyDeducedPacks[I].end(),
+                ArgumentPack);
+      Deduced[PackIndices[I]]
+        = DeducedTemplateArgument(TemplateArgument(ArgumentPack,
+                                                   NewlyDeducedPacks[I].size()),
+                            NewlyDeducedPacks[I][0].wasDeducedFromArrayBound());
+    }
   }
   
   // If there is an argument remaining, then we had too many arguments.
@@ -1087,12 +1215,16 @@ FinishTemplateArgumentDeduction(Sema &S,
   // C++ [temp.deduct.type]p2:
   //   [...] or if any template argument remains neither deduced nor
   //   explicitly specified, template argument deduction fails.
+  // FIXME: Variadic templates Empty parameter packs?
   llvm::SmallVector<TemplateArgument, 4> Builder;
   for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
     if (Deduced[I].isNull()) {
+      unsigned ParamIdx = I;
+      if (ParamIdx >= Partial->getTemplateParameters()->size())
+        ParamIdx = Partial->getTemplateParameters()->size() - 1;
       Decl *Param
         = const_cast<NamedDecl *>(
-                                Partial->getTemplateParameters()->getParam(I));
+                          Partial->getTemplateParameters()->getParam(ParamIdx));
       Info.Param = makeTemplateParameter(Param);
       return Sema::TDK_Incomplete;
     }
@@ -1118,22 +1250,23 @@ FinishTemplateArgumentDeduction(Sema &S,
   ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
   const TemplateArgumentLoc *PartialTemplateArgs
     = Partial->getTemplateArgsAsWritten();
-  unsigned N = Partial->getNumTemplateArgsAsWritten();
 
   // Note that we don't provide the langle and rangle locations.
   TemplateArgumentListInfo InstArgs;
 
-  for (unsigned I = 0; I != N; ++I) {
-    Decl *Param = const_cast<NamedDecl *>(
-                    ClassTemplate->getTemplateParameters()->getParam(I));
-    TemplateArgumentLoc InstArg;
-    if (S.Subst(PartialTemplateArgs[I], InstArg,
-                MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
-      Info.Param = makeTemplateParameter(Param);
-      Info.FirstArg = PartialTemplateArgs[I].getArgument();
-      return Sema::TDK_SubstitutionFailure;
-    }
-    InstArgs.addArgument(InstArg);
+  if (S.Subst(PartialTemplateArgs,
+              Partial->getNumTemplateArgsAsWritten(),
+              InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
+    unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
+    if (ParamIdx >= Partial->getTemplateParameters()->size())
+      ParamIdx = Partial->getTemplateParameters()->size() - 1;
+
+    Decl *Param
+      = const_cast<NamedDecl *>(
+                          Partial->getTemplateParameters()->getParam(ParamIdx));
+    Info.Param = makeTemplateParameter(Param);
+    Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
+    return Sema::TDK_SubstitutionFailure;
   }
 
   llvm::SmallVector<TemplateArgument, 4> ConvertedInstArgs;
diff --git a/lib/Sema/SemaTemplateInstantiate.cpp b/lib/Sema/SemaTemplateInstantiate.cpp
index 2fa4ac5b0b..16e1faa7f9 100644
--- a/lib/Sema/SemaTemplateInstantiate.cpp
+++ b/lib/Sema/SemaTemplateInstantiate.cpp
@@ -1723,12 +1723,13 @@ Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
   return Instantiator.TransformTemplateName(Name);
 }
 
-bool Sema::Subst(const TemplateArgumentLoc &Input, TemplateArgumentLoc &Output,
+bool Sema::Subst(const TemplateArgumentLoc *Args, unsigned NumArgs,
+                 TemplateArgumentListInfo &Result,
                  const MultiLevelTemplateArgumentList &TemplateArgs) {
   TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
                                     DeclarationName());
-
-  return Instantiator.TransformTemplateArgument(Input, Output);
+  
+  return Instantiator.TransformTemplateArguments(Args, NumArgs, Result);
 }
 
 Decl *LocalInstantiationScope::getInstantiationOf(const Decl *D) {
diff --git a/lib/Sema/SemaTemplateInstantiateDecl.cpp b/lib/Sema/SemaTemplateInstantiateDecl.cpp
index 115cdc4545..54c509544f 100644
--- a/lib/Sema/SemaTemplateInstantiateDecl.cpp
+++ b/lib/Sema/SemaTemplateInstantiateDecl.cpp
@@ -1095,13 +1095,9 @@ Decl *TemplateDeclInstantiator::VisitFunctionDecl(FunctionDecl *D,
     // Instantiate the explicit template arguments.
     TemplateArgumentListInfo ExplicitArgs(Info->getLAngleLoc(),
                                           Info->getRAngleLoc());
-    for (unsigned I = 0, E = Info->getNumTemplateArgs(); I != E; ++I) {
-      TemplateArgumentLoc Loc;
-      if (SemaRef.Subst(Info->getTemplateArg(I), Loc, TemplateArgs))
-        return 0;
-
-      ExplicitArgs.addArgument(Loc);
-    }
+    if (SemaRef.Subst(Info->getTemplateArgs(), Info->getNumTemplateArgs(),
+                      ExplicitArgs, TemplateArgs))
+      return 0;
 
     // Map the candidate templates to their instantiations.
     for (unsigned I = 0, E = Info->getNumTemplates(); I != E; ++I) {
@@ -1791,19 +1787,12 @@ TemplateDeclInstantiator::InstantiateClassTemplatePartialSpecialization(
   
   // Substitute into the template arguments of the class template partial
   // specialization.
-  const TemplateArgumentLoc *PartialSpecTemplateArgs
-    = PartialSpec->getTemplateArgsAsWritten();
-  unsigned N = PartialSpec->getNumTemplateArgsAsWritten();
-
   TemplateArgumentListInfo InstTemplateArgs; // no angle locations
-  for (unsigned I = 0; I != N; ++I) {
-    TemplateArgumentLoc Loc;
-    if (SemaRef.Subst(PartialSpecTemplateArgs[I], Loc, TemplateArgs))
-      return 0;
-    InstTemplateArgs.addArgument(Loc);
-  }
+  if (SemaRef.Subst(PartialSpec->getTemplateArgsAsWritten(), 
+                    PartialSpec->getNumTemplateArgsAsWritten(), 
+                    InstTemplateArgs, TemplateArgs))
+    return 0;
   
-
   // Check that the template argument list is well-formed for this
   // class template.
   llvm::SmallVector<TemplateArgument, 4> Converted;
diff --git a/lib/Sema/SemaTemplateVariadic.cpp b/lib/Sema/SemaTemplateVariadic.cpp
index f2651ef65c..bb9c01afad 100644
--- a/lib/Sema/SemaTemplateVariadic.cpp
+++ b/lib/Sema/SemaTemplateVariadic.cpp
@@ -253,6 +253,12 @@ bool Sema::DiagnoseUnexpandedParameterPack(SourceLocation Loc,
   return true;
 }
 
+void Sema::collectUnexpandedParameterPacks(TemplateArgument Arg,
+                   llvm::SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
+  CollectUnexpandedParameterPacksVisitor(Unexpanded)
+    .TraverseTemplateArgument(Arg);
+}
+
 void Sema::collectUnexpandedParameterPacks(TemplateArgumentLoc Arg,
                    llvm::SmallVectorImpl<UnexpandedParameterPack> &Unexpanded) {
   CollectUnexpandedParameterPacksVisitor(Unexpanded)
diff --git a/test/CXX/temp/temp.decls/temp.variadic/count.cpp b/test/CXX/temp/temp.decls/temp.variadic/count.cpp
index aa880a5370..1f6778adc3 100644
--- a/test/CXX/temp/temp.decls/temp.variadic/count.cpp
+++ b/test/CXX/temp/temp.decls/temp.variadic/count.cpp
@@ -1,17 +1,36 @@
 // RUN: %clang_cc1 -std=c++0x -fsyntax-only -verify %s
 
-template<typename Head, typename ...Tail>
-struct count {
-  static const unsigned value = 1 + count<Tail...>::value;
-};
+namespace Basic {
+  template<typename Head, typename ...Tail>
+  struct count {
+    static const unsigned value = 1 + count<Tail...>::value;
+  };
 
-template<typename T>
-struct count<T> {
-  static const unsigned value = 1;
-};
+  template<typename T>
+  struct count<T> {
+    static const unsigned value = 1;
+  };
 
-int check1[count<int>::value == 1? 1 : -1];
-int check2[count<float, double>::value == 2? 1 : -1];
-int check3[count<char, signed char, unsigned char>::value == 3? 1 : -1];
+  int check1[count<int>::value == 1? 1 : -1];
+  int check2[count<float, double>::value == 2? 1 : -1];
+  int check3[count<char, signed char, unsigned char>::value == 3? 1 : -1];
+}
 
+namespace WithPackExpansion {
+  template<typename ...> struct count;
 
+  template<typename Head, typename ...Tail>
+  struct count<Head, Tail...> {
+    static const unsigned value = 1 + count<Tail...>::value;
+  };
+
+  template<>
+  struct count<> {
+    static const unsigned value = 0;
+  };
+
+  int check0[count<>::value == 0? 1 : -1];
+  int check1[count<int>::value == 1? 1 : -1];
+  int check2[count<float, double>::value == 2? 1 : -1];
+  int check3[count<char, signed char, unsigned char>::value == 3? 1 : -1];
+}