Is this template syntax illegal?

Question

I'm getting an "internal compiler error" with this using GCC 4.9.2:

#include <type_traits>

template <typename T, typename, int, template <typename U, U, U> class>
struct Sort;

template <typename T, template <T...> class Z, T N, T... Is,
          template <typename U, U, U> class Comparator>
struct Sort<T, Z<N, Is...>, 0, Comparator> {
  template <T I>
  struct less_than : std::integral_constant<bool, Comparator<T, I, N>::value> {
  };
};

int main() {}

The error message states:

c:\ADandD>g++ -std=c++14 ComparatorAndSorterTGeneralized.cpp ComparatorAndSorterTGeneralized.cpp:254:80: internal compiler error: in tsubst, at cp/pt.c:11738

template<T I>
struct less_than : std::integral_constant<bool, Comparator<T,I,N>::value> {};
                                                                              ^

Please submit a full bug report, with preprocessed source if appropriate. See http://gcc.gnu.org/bugs.html for instructions.

The issue is the template <typename U, U, U> class Comparator being used. I've never tried this before. At first I tried the template <typename T, T, T> class Comparator, but that would not compile because of the template shadowing, so I knew that was illegal. And then changing it to U still did not compile, so I thought the whole idea is not allowed.

Update: Upon instantiating, this compiles in Visual Studio 2015 Preview:

#include <type_traits>

template <typename T, typename, int, template <typename U, U, U> class>
struct Sort;

template <typename T, template <T...> class Z, T N, T... Is,
          template <typename U, U, U> class Comparator>
struct Sort<T, Z<N, Is...>, 0, Comparator> {
  template <T I>
  struct less_than : std::integral_constant<bool, Comparator<T, I, N>::value> {
  };
};

template <int...>
struct index_sequence {};

template <typename T, T A, T B>
    struct LessThan : std::integral_constant < bool,
    A<B> {};

enum { QuickSort, MergeSort, InsertionSort };

int main() {
  Sort<int, index_sequence<4, 5, 6, 1, 2, 7>, QuickSort, LessThan> quickSort;
}

Answer 1

template <typename T, typename, int, template <typename U, U, U> class>
  struct Sort;  

This is perfectly legal.

It could be redeclared like this, giving names to all the parameters:

template <typename T, typename T2, int I, template <typename U, U X, U Y> class TT>
  struct Sort;  

It declares a class template Sort which has four template parameters, the type parameter T, a second type parameter T2 (unnamed in the original), a non-type template parameter I, and a template template parameter TT.

The template template parameter TT must a class template taking three template parameters, U is a type parameter and the second and third (X and Y) are non-type template parameters of type U.

A suitable argument for the fourth template parameter of Sort might be something like:

template <typename T, T t1, T t2>
  class Foo
  { static const bool value = t1 < t2; };

which would be instantiated like:

Foo<int, 1, 2> fi;

or

Foo<char, 'a', 'b'> fc;