I tried to strip down as much code as I could from my actual project. This is the minimal code required to reproduce this error. It seems the compiler needs exponentially more space the more types are added to the base type list.
Why is that? and Any ideas how to work around this limitation?
The code constructs a flattened type list from other type lists and types and removes duplicates to provide a unique id for each type registered in the list.
I need this code to work with at least 30-50 types in the type list. The purpose of the code is to provide a runtime type reflection system for explicitly listed types like in this example:
#include <tuple>
// Utils
// Type for concatenated tuples
template<typename... input_t> using tuple_cat_t = decltype(std::tuple_cat(std::declval<input_t>()...));
// Helper to check if a type is contained in a tuple already
template <typename T, typename Tuple> struct contains;
template <typename T, typename... Us> struct contains<T, std::tuple<Us...>> : std::disjunction<std::is_same<T, Us>...> {};
template< class T, class U > inline constexpr bool contains_v = contains<T, U>::value;
// Filter Code:
template <class Out, class In> struct filter_duplicates;
// Partial spezialization for the recursive deduction to end (when input tuple is empty)
template <class Out> struct filter_duplicates<Out /*finished filtered output tuple*/, std::tuple<> /*empty input tuple*/>
{
using filtered_tuple_t = Out;
// The filter function deduction ends here if the input tuple is empty (every element checked). In this case _In is the found filtered output tuple
static constexpr Out& filter(Out&& _In) { return _In; }
};
/* Filter template that is used as long the input tuple is not empty.
It builds the output tuple by recursively checking every element in the
input tuple and deciding whether is can be added to the output tuple and
then continuous deduction with the next input element until the
filter_duplicates definition above matches. */
template <class... OutTypes, class InTest, class... InRest>
struct filter_duplicates<std::tuple<OutTypes...>, std::tuple<InTest, InRest...>>
{
// contained is true if the InTest element from the input tuple is contained in the output tuple already
static constexpr bool contained = contains_v<InTest, std::tuple<OutTypes...>>;
// depending on the condition above either add_t or rem_t is used (which adds InTest to the output tuple or not
using add_t = filter_duplicates<std::tuple<OutTypes..., InTest>, std::tuple<InRest...>>;
using rem_t = filter_duplicates<std::tuple<OutTypes... >, std::tuple<InRest...>>;
// These types resolve to a tuple<...> with either added or remove InTest type
using add_tuple_t = typename add_t::filtered_tuple_t;
using rem_tuple_t = typename rem_t::filtered_tuple_t;
// This type is the result of the check if InTest is contained, so its either add_tuple_t or rem_tuple_t
using filtered_tuple_t = std::conditional_t<contained, rem_tuple_t, add_tuple_t>;
// This type is the result of the check if InTest is contained, so its either the filter_duplicate type containing InTest in the OutTypes or not
using filter_t = std::conditional_t<contained, rem_t, add_t>;
// The function takes the unfiltered tuple instance and returns the filtered tuple instance (duplicate tuple entries are filtered)
static constexpr auto filter(std::tuple<OutTypes..., InTest, InRest...>&& _In)
{
return filter_seq<contained>(std::make_index_sequence<sizeof...(OutTypes)>{}, std::make_index_sequence<sizeof...(InRest) + 1 - contained>{}, std::move(_In));
}
// The input tuple for the next deduction step is built by getting all tuple elements except "InTest" in the case it is in the output list already
template<size_t _Skip, size_t... TIndicesOut, size_t... TIndicesIn, class... In>
static constexpr auto filter_seq(std::index_sequence<TIndicesOut...>, std::index_sequence<TIndicesIn...>, std::tuple<In...>&& _In)
{
return filter_t::filter(std::make_tuple(std::move(std::get<TIndicesOut>(_In))..., std::move(std::get<sizeof...(TIndicesOut) + _Skip + TIndicesIn>(_In))...));
}
};
// Some declarations for easier use
template <class T> using no_duplicates_tuple_t = typename filter_duplicates<std::tuple<>, T>::filtered_tuple_t;
template <class T> using no_duplicates_filter = filter_duplicates<std::tuple<>, T>;
// Function to return a filtered tuple given an unfiltered tuple. It uses the filter type above to construct the new tuple with correct type
template<class... In> constexpr auto make_tuple_no_duplicates(std::tuple<In...>&& _In)
{
return no_duplicates_filter<std::tuple<In...>>::filter(std::move(_In));
}
// Type info wrapper (In my project it contains functions like construct or copy and much more for the runtime type reflection)
struct IType {};
struct STypeUnknown : IType { using TType = void; };
template<typename T> struct SType : IType { using TType = T; };
// STypeList forward declation
template <typename...> struct STypeList;
// This type unwrappes a given STypeList into a flattened plain tuple, so it can be concatenated with other STypeLists or Types
// In case the given type is just a normal type, it is converted into a tuple with a single element: tuple<T> (so tuple_cat() can be used later)
template<typename T> struct SUnwrapTypeList
{
using tuple_type = std::tuple<T>;
tuple_type as_tuple;
SUnwrapTypeList(T& _Value) : as_tuple{ _Value } {}
};
// In case the Type is a STypeList its filtered and flattened tuple is used
template<typename... TypeDefs> struct SUnwrapTypeList<STypeList<TypeDefs...>>
{
using TypeList = STypeList<TypeDefs...>;
using tuple_type = typename TypeList::TTupleDef;
tuple_type as_tuple;
SUnwrapTypeList(TypeList& _Value) : as_tuple(_Value.infos) {}
};
// The actual STypeList that can be constructed from other STypeList instances
template<typename... TypeDefs> struct STypeList
{
// Defines the actual underlying flattened and filtered tuple<...>
using TTupleDef = no_duplicates_tuple_t<tuple_cat_t<typename SUnwrapTypeList<TypeDefs>::tuple_type...>>;
// Type count after flattening and filtering
static constexpr size_t TypeCount() { return std::tuple_size<TTupleDef>::value; }
// helper to get an index_sequence for the filtered flattened tuple
static constexpr auto type_seq = std::make_index_sequence<TypeCount()>{};
// All type infos given via the STypeList constructor, flattened and filtered
TTupleDef infos;
// This constructor is used in the example below. It can take arbitrary STypeLists or SType<XXX> lists and flattens and filteres them using the code above
STypeList(TypeDefs... _Types) noexcept : STypeList(type_seq, std::tuple_cat(SUnwrapTypeList<TypeDefs>(_Types).as_tuple...)) {}
STypeList(TTupleDef& _Types) noexcept : STypeList(type_seq, _Types) {}
STypeList(STypeList&& _Move) noexcept : STypeList(type_seq, _Move.infos) {}
STypeList(const STypeList& _Copy) noexcept : STypeList(type_seq, _Copy.infos) {}
private:
// Final constructor initializing infos. TListIndices is the index_sequence for the filtered and flattened tuple, while TType is the unfiltered flattened tuple from the constructors above
template <size_t... TListIndices, typename... TTypes>
STypeList(std::index_sequence<TListIndices...>, std::tuple<TTypes...>&& _Types) noexcept
: infos{ make_tuple_no_duplicates(std::move(_Types)) }
{ }
// Final constructor initializing infos via copy
template <size_t... TListIndices>
STypeList(std::index_sequence<TListIndices...>, const TTupleDef& _Infos) noexcept
: infos(_Infos)
{ }
};
// Test Code:
struct STestType1 { };
struct STestType2 { };
static inline auto TypeListBase = STypeList
(
STypeUnknown()
,SType<bool>()
,SType<float>()
,SType<double>()
,SType<int>()
,SType<long>()
,SType<char>() //<- comment in to produce error
);
static inline auto TypeListA = STypeList
(
TypeListBase
,SType<STestType1>()
);
static inline auto TypeListB = STypeList
(
TypeListBase
,SType<STestType2>()
);
static inline auto TypeListAB = STypeList
(
TypeListA,
TypeListB
);
int main()
{
}
When trying to compile the output will be (using Visual Studio 2017, problem seems to occur in gcc and VS2019 as well):
1>------ Build started: Project: VsTest, Configuration: Debug x64 ------
1>VsTest.cpp
1>XXX\vstest.cpp(20): fatal error C1060: compiler is out of heap space
1>Done building project "VsTest.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
And now... for something completely different...
What about avoiding the recursive sequence of filter() and filter_seq() calling using a variadic list of bool that say which element extract and which are duplicates?
I mean... given the same helper class with_duplicate in the other answer
template <typename, typename>
struct with_duplicate : public std::false_type
{ };
template <typename OTuple, typename IT0, typename ... ITs>
struct with_duplicate<OTuple, std::tuple<IT0, ITs...>>
: public contains<IT0, OTuple>
{ };
I propose a filter_duplicate declaration a little more complicated
template <typename Out, typename In,
typename = std::integer_sequence<bool>,
typename = std::index_sequence<>,
bool = with_duplicate<Out, In>::value>
struct filter_duplicates;
Now the two recursion cases, cases "is in list" and "isn't in list", that simply inherit from the old filter_t types
template <typename... OutTypes, typename InTest, typename... InRest,
typename Is, bool ... Bs>
struct filter_duplicates<std::tuple<OutTypes...>,
std::tuple<InTest, InRest...>,
std::integer_sequence<bool, Bs...>,
Is, true>
: public filter_duplicates<std::tuple<OutTypes...>,
std::tuple<InRest...>,
std::integer_sequence<bool, Bs..., true>,
std::make_index_sequence<sizeof...(Bs)+1u>>
{ };
template <typename... OutTypes, typename InTest, typename... InRest,
typename Is, bool ... Bs>
struct filter_duplicates<std::tuple<OutTypes...>,
std::tuple<InTest, InRest...>,
std::integer_sequence<bool, Bs...>,
Is, false>
: public filter_duplicates<std::tuple<OutTypes..., InTest>,
std::tuple<InRest...>,
std::integer_sequence<bool, Bs..., false>,
std::make_index_sequence<sizeof...(Bs)+1u>>
{ };
Now the complex part is the ground case that receive a variadic list of bool, one for every type in the original tuple, Bs..., where true is "duplicate type" and false is "no duplicate type"
// ground case
template <typename Out, bool ... Bs, std::size_t ... Is>
struct filter_duplicates<Out, std::tuple<>,
std::integer_sequence<bool, Bs...>,
std::index_sequence<Is...>, false>
{
using filtered_tuple_t = Out;
template <bool B, std::size_t I, typename Tpl>
static constexpr auto getTplCond (Tpl && t)
{
if constexpr ( B ) // duplicate
return std::tuple<>{};
else // not duplicate
return std::tuple{std::get<I>(t)};
}
template <typename ... Ts>
static constexpr std::enable_if_t<sizeof...(Ts) == sizeof...(Bs), Out>
filter (std::tuple<Ts...> && _In)
{ return std::tuple_cat( getTplCond<Bs, Is>(_In)... ); }
};
This way you call a single filter() method that isn't recursive but is recursively inherited.
Also filtered_type_t is recursively inherited.