Author: rsmith Date: Wed Mar 7 17:07:33 2018 New Revision: 326973 URL: http://llvm.org/viewvc/llvm-project?rev=326973&view=rev Log: When substituting previously-checked template arguments into a template template parameter that is an expanded parameter pack, only substitute into the current slice, not the entire pack.
This reduces the checking of N template template arguments for an expanded parameter pack containing N parameters from quadratic time to linear time in the length of the pack. This is important because one (and possibly the only?) general technique for splitting a template parameter pack in linear time depends on doing this. Added: cfe/trunk/test/SemaTemplate/temp-param-subst-linear.cpp Modified: cfe/trunk/include/clang/Sema/Sema.h cfe/trunk/lib/Sema/SemaTemplate.cpp cfe/trunk/lib/Sema/SemaTemplateInstantiateDecl.cpp cfe/trunk/test/CXX/drs/dr10xx.cpp Modified: cfe/trunk/include/clang/Sema/Sema.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/Sema/Sema.h?rev=326973&r1=326972&r2=326973&view=diff ============================================================================== --- cfe/trunk/include/clang/Sema/Sema.h (original) +++ cfe/trunk/include/clang/Sema/Sema.h Wed Mar 7 17:07:33 2018 @@ -6362,9 +6362,8 @@ public: QualType InstantiatedParamType, Expr *Arg, TemplateArgument &Converted, CheckTemplateArgumentKind CTAK = CTAK_Specified); - bool CheckTemplateArgument(TemplateTemplateParmDecl *Param, - TemplateArgumentLoc &Arg, - unsigned ArgumentPackIndex); + bool CheckTemplateTemplateArgument(TemplateParameterList *Params, + TemplateArgumentLoc &Arg); ExprResult BuildExpressionFromDeclTemplateArgument(const TemplateArgument &Arg, @@ -7700,6 +7699,10 @@ public: StmtResult SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs); + TemplateParameterList * + SubstTemplateParams(TemplateParameterList *Params, DeclContext *Owner, + const MultiLevelTemplateArgumentList &TemplateArgs); + Decl *SubstDecl(Decl *D, DeclContext *Owner, const MultiLevelTemplateArgumentList &TemplateArgs); Modified: cfe/trunk/lib/Sema/SemaTemplate.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Sema/SemaTemplate.cpp?rev=326973&r1=326972&r2=326973&view=diff ============================================================================== --- cfe/trunk/lib/Sema/SemaTemplate.cpp (original) +++ cfe/trunk/lib/Sema/SemaTemplate.cpp Wed Mar 7 17:07:33 2018 @@ -4617,6 +4617,8 @@ bool Sema::CheckTemplateArgument(NamedDe if (NTTP->isParameterPack() && NTTP->isExpandedParameterPack()) NTTPType = NTTP->getExpansionType(ArgumentPackIndex); + // FIXME: Do we need to substitute into parameters here if they're + // instantiation-dependent but not dependent? if (NTTPType->isDependentType() && !isa<TemplateTemplateParmDecl>(Template) && !Template->getDeclContext()->isDependentContext()) { @@ -4756,9 +4758,15 @@ bool Sema::CheckTemplateArgument(NamedDe // Check template template parameters. TemplateTemplateParmDecl *TempParm = cast<TemplateTemplateParmDecl>(Param); + TemplateParameterList *Params = TempParm->getTemplateParameters(); + if (TempParm->isExpandedParameterPack()) + Params = TempParm->getExpansionTemplateParameters(ArgumentPackIndex); + // Substitute into the template parameter list of the template // template parameter, since previously-supplied template arguments // may appear within the template template parameter. + // + // FIXME: Skip this if the parameters aren't instantiation-dependent. { // Set up a template instantiation context. LocalInstantiationScope Scope(*this); @@ -4769,10 +4777,9 @@ bool Sema::CheckTemplateArgument(NamedDe return true; TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, Converted); - TempParm = cast_or_null<TemplateTemplateParmDecl>( - SubstDecl(TempParm, CurContext, - MultiLevelTemplateArgumentList(TemplateArgs))); - if (!TempParm) + Params = SubstTemplateParams(Params, CurContext, + MultiLevelTemplateArgumentList(TemplateArgs)); + if (!Params) return true; } @@ -4793,7 +4800,7 @@ bool Sema::CheckTemplateArgument(NamedDe case TemplateArgument::Template: case TemplateArgument::TemplateExpansion: - if (CheckTemplateArgument(TempParm, Arg, ArgumentPackIndex)) + if (CheckTemplateTemplateArgument(Params, Arg)) return true; Converted.push_back(Arg.getArgument()); @@ -6536,9 +6543,8 @@ static void DiagnoseTemplateParameterLis /// /// This routine implements the semantics of C++ [temp.arg.template]. /// It returns true if an error occurred, and false otherwise. -bool Sema::CheckTemplateArgument(TemplateTemplateParmDecl *Param, - TemplateArgumentLoc &Arg, - unsigned ArgumentPackIndex) { +bool Sema::CheckTemplateTemplateArgument(TemplateParameterList *Params, + TemplateArgumentLoc &Arg) { TemplateName Name = Arg.getArgument().getAsTemplateOrTemplatePattern(); TemplateDecl *Template = Name.getAsTemplateDecl(); if (!Template) { @@ -6573,10 +6579,6 @@ bool Sema::CheckTemplateArgument(Templat << Template; } - TemplateParameterList *Params = Param->getTemplateParameters(); - if (Param->isExpandedParameterPack()) - Params = Param->getExpansionTemplateParameters(ArgumentPackIndex); - // C++1z [temp.arg.template]p3: (DR 150) // A template-argument matches a template template-parameter P when P // is at least as specialized as the template-argument A. Modified: cfe/trunk/lib/Sema/SemaTemplateInstantiateDecl.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Sema/SemaTemplateInstantiateDecl.cpp?rev=326973&r1=326972&r2=326973&view=diff ============================================================================== --- cfe/trunk/lib/Sema/SemaTemplateInstantiateDecl.cpp (original) +++ cfe/trunk/lib/Sema/SemaTemplateInstantiateDecl.cpp Wed Mar 7 17:07:33 2018 @@ -3118,6 +3118,13 @@ TemplateDeclInstantiator::SubstTemplateP return InstL; } +TemplateParameterList * +Sema::SubstTemplateParams(TemplateParameterList *Params, DeclContext *Owner, + const MultiLevelTemplateArgumentList &TemplateArgs) { + TemplateDeclInstantiator Instantiator(*this, Owner, TemplateArgs); + return Instantiator.SubstTemplateParams(Params); +} + /// \brief Instantiate the declaration of a class template partial /// specialization. /// Modified: cfe/trunk/test/CXX/drs/dr10xx.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/CXX/drs/dr10xx.cpp?rev=326973&r1=326972&r2=326973&view=diff ============================================================================== --- cfe/trunk/test/CXX/drs/dr10xx.cpp (original) +++ cfe/trunk/test/CXX/drs/dr10xx.cpp Wed Mar 7 17:07:33 2018 @@ -31,9 +31,8 @@ namespace dr1004 { // dr1004: 5 // This example (from the standard) is actually ill-formed, because // name lookup of "T::template A" names the constructor. - // FIXME: Only issue one diagnostic for this case. - template<class T, template<class> class U = T::template A> struct Third { }; // expected-error 2{{is a constructor name}} - Third<A<int> > t; // expected-note {{in instantiation of}} expected-note {{while substituting}} expected-note {{while checking}} + template<class T, template<class> class U = T::template A> struct Third { }; // expected-error {{is a constructor name}} + Third<A<int> > t; // expected-note {{in instantiation of default argument}} } namespace dr1048 { // dr1048: 3.6 Added: cfe/trunk/test/SemaTemplate/temp-param-subst-linear.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/SemaTemplate/temp-param-subst-linear.cpp?rev=326973&view=auto ============================================================================== --- cfe/trunk/test/SemaTemplate/temp-param-subst-linear.cpp (added) +++ cfe/trunk/test/SemaTemplate/temp-param-subst-linear.cpp Wed Mar 7 17:07:33 2018 @@ -0,0 +1,56 @@ +// RUN: %clang_cc1 -std=c++17 %s -verify +// expected-no-diagnostics + +// This test attempts to ensure that the below template parameter pack +// splitting technique executes in linear time in the number of template +// parameters. The size of the list below is selected so as to execute +// relatively quickly on a "good" compiler and to time out otherwise. + +template<typename...> struct TypeList; + +namespace detail { +template<unsigned> using Unsigned = unsigned; +template<typename T, T ...N> using ListOfNUnsignedsImpl = TypeList<Unsigned<N>...>; +template<unsigned N> using ListOfNUnsigneds = + __make_integer_seq<ListOfNUnsignedsImpl, unsigned, N>; + +template<typename T> struct TypeWrapper { + template<unsigned> using AsTemplate = T; +}; + +template<typename ...N> struct Splitter { + template<template<N> class ...L, + template<unsigned> class ...R> struct Split { + using Left = TypeList<L<0>...>; + using Right = TypeList<R<0>...>; + }; +}; +} + +template<typename TypeList, unsigned N, typename = detail::ListOfNUnsigneds<N>> +struct SplitAtIndex; + +template<typename ...T, unsigned N, typename ...NUnsigneds> +struct SplitAtIndex<TypeList<T...>, N, TypeList<NUnsigneds...>> : + detail::Splitter<NUnsigneds...>:: + template Split<detail::TypeWrapper<T>::template AsTemplate...> {}; + +template<typename T, int N> struct Rep : Rep<typename Rep<T, N-1>::type, 1> {}; +template<typename ...T> struct Rep<TypeList<T...>, 1> { typedef TypeList<T..., T...> type; }; + +using Ints = Rep<TypeList<int>, 14>::type; + +template<typename T> extern int Size; +template<typename ...T> constexpr int Size<TypeList<T...>> = sizeof...(T); + +using Left = SplitAtIndex<Ints, Size<Ints> / 2>::Left; +using Right = SplitAtIndex<Ints, Size<Ints> / 2>::Right; +static_assert(Size<Left> == 8192); +static_assert(Size<Right> == 8192); + +template<typename L, typename R> struct Concat; +template<typename ...L, typename ...R> struct Concat<TypeList<L...>, TypeList<R...>> { + using type = TypeList<L..., R...>; +}; + +using Ints = Concat<Left, Right>::type; _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits