template hell

[regehr]

below is the fully reduced version of test case 00 in this repo:

https://github.com/regehr/compiler-crashes

it seems clear that we have some work to do on simplifying template code (I think we all knew this but I wanted to provide an actionable test in case anyone has time to look into it)

template < bool > struct a;
typedef a< true > b;
template < bool bt > struct a {
  static const bool c = bt;
  typedef a d;
};
template < int e > struct f {
  static const int c = e;
  typedef int g;
};
template < typename, typename = int > struct h;
template < int, typename i, typename > struct j { typedef i d; };
template < typename i, typename k > struct j< false, i, k > { typedef k d; };
template < typename i, typename k, typename l > struct m {
  typedef typename j< i::c, k, l >::d d;
};
template < typename > struct n;
template < typename o, typename p > struct q {
  typedef o aa;
  typedef p n;
};
template < typename o > struct r : o::d {};
template < int bt > struct s : a< !bt > {};
template < typename o > struct t : s< r< o >::c > {};
template < typename > struct ab;
template < typename > struct ac;
template < typename ad > struct ab< ac< ad > > { typedef typename ad::aa d; };
template < typename ad > struct n< ac< ad > > {
  typedef ac< typename ad::n > d;
};
template < typename ae, typename i > struct u : ae::template af< i > {};
template < typename ae, typename i, typename k >
struct v : ae::template af< i, k > {};
template < typename ae, typename i > struct w : ae::template af< i > {};
template < int > struct ag {
  template < typename x > struct af {
    typedef x d;
    enum { y = ((void (*)(d))0, 1) };
  };
};
template < typename o > struct ah : o {};
template < typename, typename, typename > struct z;
template < int e, typename x, typename ai > struct z< ag< e >, x, ai > {
  typedef typename w< ag< e >, x >::d d;
};
template < typename ae, typename i, typename k > struct aj {
  template < typename x > struct af {
    typedef typename v< ae, i, typename z< k, x, int >::d >::d d;
  };
};
template < typename o > struct ak { typedef o d; };
template < template < typename, typename > class ae > struct al {
  template < typename x, typename am > struct af : ak< ae< x, am > > {};
};
template < typename o, typename > struct h { typedef o d; };
template < template < typename, typename > class ae > struct an {
  typedef aj< al< ae >, f< 7 >, ag< 1 > > d;
};
template < template < typename, typename > class ae, typename i, typename k,
           typename ao >
struct h< ae< i, k >, ao > {
  typedef typename an< ae >::d d;
};
template < typename ae, typename i > struct ap : u< typename h< ae >::d, i > {};
template < typename ae, typename k > struct aq : v< ae, int, k > {};
template < typename ae, typename ar >
struct as : ap< ae, typename ab< ar >::d > {};
template < typename, typename > struct at;
struct au {
  template < typename ar > struct af {
    typedef t< as< at< int, ag< 1 > >, ar > > d;
  };
};
template < int, typename, typename, typename, typename >
struct av : a< false > {};
template < typename i, typename k, typename l, typename aw >
struct av< true, i, k, l, aw > : av< r< i >::c, k, l, aw, b > {};
template <> struct av< true, b, b, b, b > : b {};
template < typename i, typename k, typename l = b, typename aw = b,
           typename ax = b >
struct ay : av< i::c, k, l, aw, ax > {};
template < typename > struct az { typedef ac< q< int, int > > ba; };
struct bb {
  typedef int bc;
};
template < typename ar, typename bd > struct be {
  typedef typename aq< bd, ar >::d bf;
  typedef typename n< ar >::d bc;
};
template < typename ar, typename bg > struct bh {
  typedef be< ar, bg > bi;
  typedef
      typename m< typename bi::bf, bh< typename bi::bc, bg >, bb >::d::bc bc;
};
template < typename > struct bj {
  template < typename, typename ar >
  struct af : ay< t< a< false > >, ap< au, ar > > {};
};
template < typename bg > struct bk {
  typedef az<
      typename bh< ac< q< f< 4 >, q< f< 7 >, int > > >, ah< bj< bg > > >::bc >
      d;
};
template < typename bd > struct bl { typedef typename bk< bd >::d::ba d; };
template < typename > struct bm;
template < typename bn, typename bo >
struct at : bm< typename bo::g >::template af< bn, bo > {};
template <> struct bm< int > {
  template < typename bn, typename bo > struct af : a< bn::c <= bo::c > {};
};
template < class > struct bv { typedef int d; };
template < class bp > struct bq {
  typedef ab< typename bl< at< typename bv< bp >::d, f< 0 > > >::d > d;
};
template < class br, class bs, class bp > void beta(br, bs, bp) {
  typename bq< bp >::d a;
}
template < class, class bp > void bu(unsigned, unsigned bw, bp by) {
  beta(bw, 1, by);
}
void bx() { bu< double >(0, 0, bx); }

[octoploid]

Another example (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=72457):

namespace std {
typedef int size_t;
template <typename _Tp, _Tp __v> struct integral_constant {
  static constexpr _Tp value = __v;
  typedef integral_constant type;
  constexpr operator int() { return 1; }
};
typedef integral_constant<int, 0> false_type;
template <typename...> struct __or_;
template <typename _B1, typename _B2> struct __or_<_B1, _B2> : _B2 {};
template <typename...> struct __and_;
template <typename _B1, typename _B2> struct __and_<_B1, _B2> : _B1 {};
template <typename _Pp> struct __not_ : integral_constant<int, !_Pp::value> {};
struct __is_void_helper : false_type {};
template <typename> struct is_void : __is_void_helper {};
template <typename _Tp> _Tp declval();
struct __is_default_constructible_atom : __and_<__not_<is_void<int>>, int> {};
template <typename>
struct __is_default_constructible_safe : __is_default_constructible_atom {};
template <typename>
struct is_default_constructible : __is_default_constructible_safe<int> {};
template <typename, typename> struct is_same : integral_constant<int, 0> {};
template <typename _Tp> struct decay { typedef _Tp type; };
template <int, typename> struct enable_if;
template <typename _Tp> struct enable_if<1, _Tp> { typedef _Tp type; };
template <typename _Tp> _Tp forward;
template <typename...> struct tuple;
template <typename> struct tuple_size;
template <typename> struct tuple_element;
template <typename _Tp, _Tp...> struct integer_sequence;
template <typename _Head, typename... _Tail>
struct tuple_element<tuple<_Head, _Tail...>> {
  typedef _Head type;
};
template <typename... _Elements>
struct tuple_size<tuple<_Elements...>>
    : integral_constant<int, sizeof...(_Elements)> {};
namespace placeholders {
int _1;
}
template <int, typename _Tuple>
using _Safe_tuple_element_t =
    typename enable_if<tuple_size<_Tuple>::value,
                       tuple_element<_Tuple>>::type::type;
template <typename> struct _Mu {
  template <typename _Tuple>
  _Safe_tuple_element_t<0, _Tuple> operator()(int, _Tuple &);
};
template <typename> struct _Bind;
template <typename _Functor, typename... _Bound_args>
struct _Bind<_Functor(_Bound_args...)> {
  template <typename... _Args,
            typename _Result = decltype(_Functor()(
                _Mu<_Bound_args>()(0, declval<tuple<_Args...> &>())...))>
  _Result operator()(_Args...);
};
template <typename _Tp, typename _Tp2 = _Tp>
using __is_socketlike = __or_<_Tp2, integral_constant<int, 0>>;
template <int, typename _Func, typename... _BoundArgs> struct _Bind_helper {
  typedef _Bind<_Func(_BoundArgs...)> type;
};
template <typename _Func, typename... _BoundArgs>
typename _Bind_helper<__is_socketlike<_Func>::value, _Func, _BoundArgs...>::type
bind(_Func, _BoundArgs...);
namespace {
template <typename...> struct list;
template <template <typename...> class, typename...> struct defer;
template <typename T> T *_nullptr_v();
template <typename T> using _t = typename T::type;
template <int> using size_t = integral_constant<int, 0>;
template <int> using bool_ = integral_constant<int, 0>;
namespace detail {
enum indices_strategy_ { recurse };
constexpr indices_strategy_ strategy_(std::size_t, std::size_t) {
  return recurse;
}
template <std::size_t, typename State, indices_strategy_> struct make_indices_ {
  using type = State;
};
}
template <long... Is> using index_sequence = integer_sequence<int, Is...>;
template <std::size_t>
using make_index_sequence =
    _t<detail::make_indices_<0, index_sequence<>, detail::strategy_(0, 0)>>;
template <typename F, typename... Args>
using invoke = typename F::template invoke<Args...>;
namespace lazy {
template <typename F, typename... Args>
using invoke = defer<invoke, F, Args...>;
}
template <typename T> struct id { using type = T; };
namespace detail {
template <template <typename...> typename, typename> struct defer_;
template <template <typename...> class C, typename... Ts>
struct defer_<C, list<Ts...>> {
  using type = C<Ts...>;
};
}
template <template <typename...> class C, typename... Ts>
struct defer : detail::defer_<C, list<Ts...>> {};
template <template <typename...> class C> struct quote {
  template <typename... Ts> using invoke = _t<detail::defer_<C, list<Ts...>>>;
};
template <template <typename> class> using quote_trait = int;
template <typename F, typename... Ts> struct bind_front {
  template <typename... Us> using invoke = invoke<F, Ts..., Us...>;
};
template <typename F, typename... Us> struct bind_back {
  template <typename... Ts> using invoke = invoke<F, Ts..., Us...>;
};
namespace extension {
template <typename, typename> struct apply;
template <typename F, typename Ret, typename... Args>
struct apply<F, Ret(Args...)> : lazy::invoke<F, Args...> {};
}
template <typename C, typename List>
using apply = _t<extension::apply<C, List>>;
template <typename, typename Q = quote<list>> using curry = Q;
template <typename F> using uncurry = bind_front<quote<apply>, F>;
namespace detail {
template <typename> struct _if_;
template <typename If, typename Then> struct _if_<list<If, Then>> {
  using type = Then;
};
}
template <typename... Args> using if_ = _t<detail::_if_<list<Args...>>>;
template <int If, typename... Args>
using if_c = _t<detail::_if_<list<bool_<If>, Args...>>>;
namespace lazy {
template <typename... Args> using if_ = defer<if_, Args...>;
}
template <bool... Bools>
using and_c = is_same<int, integer_sequence<int, Bools...>>;
template <typename... Bools> using strict_and = and_c<Bools::value...>;
namespace detail {
struct repeat_n_c_ {
  using type = list<>;
};
}
template <int, typename> using repeat_n_c = _t<detail::repeat_n_c_>;
template <typename N, typename T> using repeat_n = repeat_n_c<N::value, T>;
namespace detail {
template <typename> struct at_impl_ {
  template <typename T> static T eval(T *);
};
template <typename, typename> struct at_;
template <typename... Ts, typename N>
struct at_<list<Ts...>, N>
    : decltype(at_impl_<repeat_n<N, void>>::eval(static_cast<id<Ts> *>(0)...)) {
};
}
template <typename List, typename N> using at = _t<detail::at_<List, N>>;
template <typename List, int> using at_c = at<List, size_t<0>>;
namespace detail {
template <typename> struct drop_impl_ {
  template <typename... Ts> static id<list<Ts...>> eval(Ts...);
};
template <typename, typename> struct drop_;
template <typename... Ts, typename N>
struct drop_<list<Ts...>, N>
    : decltype(drop_impl_<repeat_n<N, void>>::eval(_nullptr_v<Ts>...)) {};
}
template <typename List, int> using drop_c = _t<detail::drop_<List, size_t<0>>>;
namespace detail {
template <typename> struct back_;
template <typename Head, typename... List> struct back_<list<Head, List...>> {
  using type = at_c<list<Head>, sizeof...(List)>;
};
}
template <typename List> using back = _t<detail::back_<List>>;
namespace detail {
template <typename, typename> struct find_if_;
template <typename... List, typename Fun> struct find_if_<list<List...>, Fun> {
  static constexpr int s_v{invoke<Fun, List>::value...};
  using type = drop_c<list<List...>, s_v>;
};
}
template <typename List, typename Fun>
using find_if = _t<detail::find_if_<List, Fun>>;
namespace detail {
template <typename Sequence>
struct as_list_ : lazy::invoke<uncurry<curry<quote_trait<id>>>, Sequence> {};
}
template <typename Sequence> using as_list = _t<detail::as_list_<Sequence>>;
}
namespace v3 {
namespace adl_begin_end_detail {
struct begin_fn;
}
using adl_begin_end_detail::begin_fn;
namespace view {
template <typename> struct view;
}
namespace detail {
struct any_ {
  template <typename T> any_(T);
};
using any = any_;
template <typename T> using decay_t = _t<decay<T>>;
}
enum cardinality { infinite };
template <typename> struct range_cardinality;
template <cardinality> struct basic_view {};
template <typename, typename BaseRng,
          cardinality = range_cardinality<BaseRng>::value>
struct view_adaptor;
template <typename T> struct static_const { static constexpr T value{}; };
template <typename T>
struct value_type : lazy::if_<int, typename T::value_type> {};
namespace detail {
template <typename...> auto models_(any) -> false_type;
template <typename... Ts, typename Concept,
          typename = decltype(Concept().template requires_<Ts...>(Ts()...))>
auto models_(Concept *);
template <typename> struct most_refined_;
template <typename Head, typename... Tail>
struct most_refined_<list<Head, Tail...>> {
  using type = Head;
};
template <typename> using avoid_empty_braces = false_type;
}
namespace concepts {
template <typename Concept, typename... Ts>
struct models
    : bool_<
          _t<decltype(detail::models_<Ts...>(_nullptr_v<Concept>()))>::value> {
};
template <typename Concept, typename... Ts>
auto model_of() -> if_c<models<Concept, Ts...>::value>;
template <typename Concepts, typename... Ts>
struct most_refined : detail::most_refined_<
                          find_if<Concepts, bind_back<quote<models>, Ts...>>> {
};
struct ConstructibleObject {
  template <typename T, if_c<detail::avoid_empty_braces<T>::value, int> = 0>
  auto requires_(T);
};
struct SemiRegular {
  template <typename T>
  auto requires_() -> decltype(model_of<ConstructibleObject, T>);
};
}
template <typename, typename> using ConvertibleTo = concepts::models<int>;
namespace detail {
template <typename T> using tag_elem = back<as_list<T>>;
}
template <typename Base> struct chain { using type = Base; };
template <typename Base>
struct Trans_NS_tagged_detail_tagged : _t<chain<Base>> {};
template <typename Element> struct box {
  Element value;
  template <typename enable_if<is_default_constructible<Element>::value,
                               int>::type = 0>
  constexpr box() : value{} {}
};
template <typename T, int> using storage = box<T>;
template <typename, typename> struct compressed_tuple_;
template <typename... Ts, long... Is>
struct compressed_tuple_<list<Ts...>, index_sequence<Is...>>
    : storage<Ts, 0>... {};
template <typename... Ts>
using compressed_tuple =
    compressed_tuple_<list<Ts...>, make_index_sequence<sizeof...(Ts)>>;
template <typename... Ts>
using tagged_compressed_tuple =
    Trans_NS_tagged_detail_tagged<compressed_tuple<detail::tag_elem<Ts>>...>;
struct first;
struct compressed_pair : tagged_compressed_tuple<first(int)> {};
struct pipeable_access {
  template <typename Pipeable> struct impl : Pipeable {};
};
template <typename Arg, typename Pipe>
auto operator|(Arg arg, Pipe)
    -> decltype(pipeable_access::impl<Pipe>::pipe(arg, 0));
struct Readable {
  template <typename I> using value_t = _t<value_type<I>>;
};
struct range_access {
  template <typename T> static id<box<T>> mixin_base_2_(int);
  template <typename Cur>
  struct mixin_base_ : decltype(mixin_base_2_<Cur>(0)) {};
  template <typename Cur> using mixin_base_t = _t<mixin_base_<Cur>>;
  struct Cursor {
    template <typename T>
    auto requires_()
        -> decltype(concepts::model_of<concepts::SemiRegular, mixin_base_t<T>>);
  };
  template <typename Rng>
  static auto begin_cursor(Rng rng, int) -> decltype(rng.begin_cursor());
};
namespace detail {
template <typename T>
using cursor_concept = concepts::most_refined<list<range_access::Cursor>, T>;
template <typename T> using cursor_concept_t = _t<cursor_concept<T>>;
template <typename Cur> struct iterator_associated_types_base {
  using cursor_concept_t = detail::cursor_concept_t<Cur>;
  using value_type = range_access;
};
}
template <typename Cur>
struct basic_iterator : detail::iterator_associated_types_base<Cur> {};
namespace adl_begin_end_detail {
struct begin_fn {
  template <typename Rng> auto impl(Rng rng, int) -> decltype(rng.begin());
  template <typename Rng>
  auto operator()(Rng rng) -> detail::decay_t<decltype(impl(rng, 0))>;
};
}
auto begin = static_const<begin_fn>::value;
namespace concepts {
struct Range {
  template <typename T> using iterator_t = decltype(begin(T()));
};
struct InputRange : Range {
  template <typename T> using value_t = Readable::value_t<iterator_t<T>>;
};
}
template <typename Rng>
using range_value_t = concepts::InputRange::value_t<Rng>;
namespace detail {
template <cardinality Card>
integral_constant<cardinality, Card> test_cardinality(basic_view<Card> *);
}
template <typename Rng>
struct range_cardinality
    : if_<is_same<Rng, Rng>,
          decltype(detail::test_cardinality(static_cast<Rng *>(0)))> {};
namespace detail {
template <typename Rng, typename Cont>
using ConvertibleToContainer =
    strict_and<ConvertibleTo<range_value_t<Rng>, Cont>>;
}
}
inline namespace v3 {
template <typename Derived, cardinality Cardinality>
struct view_interface : basic_view<Cardinality> {
  template <typename Container, typename D = Derived,
            typename enable_if<(detail::ConvertibleToContainer<D, Container>()),
                               int>::type = 0>
  operator Container();
};
namespace detail {
template <typename Derived>
using begin_cursor_t = decltype(range_access::begin_cursor(Derived(), 0));
template <typename Derived>
using facade_iterator_t = basic_iterator<begin_cursor_t<Derived>>;
}
template <typename Derived, cardinality Cardinality>
struct view_facade : view_interface<Derived, Cardinality> {
  template <typename D = Derived> detail::facade_iterator_t<D> begin();
};
namespace detail {
template <typename Derived> using begin_adaptor_t = decltype(declval<Derived>);
template <typename Derived>
using adapted_iterator_t = decltype(declval<Derived>);
struct adaptor_value_type_ : compressed_pair {};
}
template <typename, typename>
struct adaptor_cursor : detail::adaptor_value_type_ {};
template <typename D>
using adaptor_cursor_t =
    adaptor_cursor<detail::adapted_iterator_t<D>, detail::begin_adaptor_t<D>>;
template <typename Derived, typename, cardinality Cardinality>
struct view_adaptor : view_facade<Derived, Cardinality> {
  template <typename D = Derived> adaptor_cursor_t<D> begin_cursor();
};
namespace view {
struct view_access {
  template <typename View> struct impl {
    template <typename... Ts, typename V = View>
    static auto bind(Ts... ts) -> decltype(V::bind(ts...));
  };
  template <typename Fun> view<Fun> operator()(Fun);
} make_view;
template <typename View> struct view {
  View view_;
  template <typename Rng, typename Vw>
  static auto pipe(Rng rng, Vw) -> decltype(view_(rng));
  template <typename... Ts, typename V = View>
  auto operator()(Ts...)
      -> decltype(make_view(view_access::impl<V>::bind(view_, forward<Ts>...)));
};
}
template <typename Rng>
struct iter_transform_view : view_adaptor<iter_transform_view<Rng>, Rng> {};
namespace view {
struct transform_fn {
  template <typename Fun>
  static auto bind(transform_fn transform, Fun)
      -> decltype(bind(transform, placeholders::_1, 0));
  template <typename Rng, typename Fun>
  iter_transform_view<Rng> operator()(Rng, Fun);
};
auto transform = static_const<view<transform_fn>>::value;
struct ints_fn : view_facade<int, infinite> {
} ints;
}
}
int m = view::ints | view::transform(0);
}

can be hand reduced to:

template <typename Element> struct box {
  Element value;
  constexpr box() : value{} {}
};
struct B: box<int> { };
template box<B>::box();

[regehr]

Thanks Markus, that's a great example. I wonder how many new transformations are needed to get to your hand-reduced version.

[chenyang78]

On 2016-08-09 00:35, octoploid wrote:

Another example (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=72457):

Thanks, Markus.

One big missing part in the current C-Reduce is the ability to process some commonly-used C++11 features such as lambda, variadic templates and decltype. I will see what I can do for it when I have spare time.

• Yang