clang/test/SemaTemplate/temp-param-subst-linear.cpp

   1 // RUN: %clang_cc1 -std=c++17 %s -verify
   2 // expected-no-diagnostics
   3
   4 // This test attempts to ensure that the below template parameter pack
   5 // splitting technique executes in linear time in the number of template
   6 // parameters. The size of the list below is selected so as to execute
   7 // relatively quickly on a "good" compiler and to time out otherwise.
   8
   9 template<typename...> struct TypeList;
  10
  11 namespace detail {
  12 template<unsigned> using Unsigned = unsigned;
  13 template<typename T, T ...N> using ListOfNUnsignedsImpl = TypeList<Unsigned<N>...>;
  14 template<unsigned N> using ListOfNUnsigneds =
  15   __make_integer_seq<ListOfNUnsignedsImpl, unsigned, N>;
  16
  17 template<typename T> struct TypeWrapper {
  18   template<unsigned> using AsTemplate = T;
  19 };
  20
  21 template<typename ...N> struct Splitter {
  22   template<template<N> class ...L,
  23            template<unsigned> class ...R> struct Split {
  24     using Left = TypeList<L<0>...>;
  25     using Right = TypeList<R<0>...>;
  26   };
  27 };
  28 }
  29
  30 template<typename TypeList, unsigned N, typename = detail::ListOfNUnsigneds<N>>
  31 struct SplitAtIndex;
  32
  33 template<typename ...T, unsigned N, typename ...NUnsigneds>
  34 struct SplitAtIndex<TypeList<T...>, N, TypeList<NUnsigneds...>> :
  35   detail::Splitter<NUnsigneds...>::
  36     template Split<detail::TypeWrapper<T>::template AsTemplate...> {};
  37
  38 template<typename T, int N> struct Rep : Rep<typename Rep<T, N-1>::type, 1> {};
  39 template<typename ...T> struct Rep<TypeList<T...>, 1> { typedef TypeList<T..., T...> type; };
  40
  41 using Ints = Rep<TypeList<int>, 14>::type;
  42
  43 template<typename T> extern int Size;
  44 template<typename ...T> constexpr int Size<TypeList<T...>> = sizeof...(T);
  45
  46 using Left = SplitAtIndex<Ints, Size<Ints> / 2>::Left;
  47 using Right = SplitAtIndex<Ints, Size<Ints> / 2>::Right;
  48 static_assert(Size<Left> == 8192);
  49 static_assert(Size<Right> == 8192);
  50
  51 template<typename L, typename R> struct Concat;
  52 template<typename ...L, typename ...R> struct Concat<TypeList<L...>, TypeList<R...>> {
  53   using type = TypeList<L..., R...>;
  54 };
  55
  56 using Ints = Concat<Left, Right>::type;