3

Given

template <typename...> struct Pack;
using T1 = std::tuple<int, char, double>;
using T2 = std::tuple<bool, double, int, char>;

TupleTree<Pack, T1, T2> shall be

Pack<
    Pack<int, bool>, Pack<int, double>, Pack<int, int>, Pack<int, char>,
    Pack<char, bool>, Pack<char, double>, Pack<char, int>, Pack<char, char>,
    Pack<double, bool>, Pack<double, double>, Pack<double, int>, Pack<double, char>
>

And this extends to any number of tuples. Easy enough to understand the definition? Ok, I have the program working correctly:

http://ideone.com/OumeZK

But now I want to extend the definition to

`TupleTreeWithRepeats<P, std::index_sequence<Is...>, Tuples...>`

where Is... will indicate the number of times each tuple is being used repeatedly until moving on to the next tuple. Note that <Is...> = <1,1,...,1> will reduce to the same as TupleTree<P, Tuples...>. The ambiguity that I'm stuck with is with these two specializations:

TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, LoopNumber, P<Ts...>, First, Rest...>
TupleTreeWithRepeatsHelper<P, std::index_sequence<I, Is...>, I, P<Ts...>, First, Rest...>

For some reason, the presence of P<Ts...> causes the ambiguity because when I replace it with a single-named type the ambiguity is removed. Even when I replace std::index_sequence<Is...> with std::index_sequence<I, Is...>, the ambiguity is still there. What's going on? And how to fix this? Here is the code, which is almost the same as that for TupleTree:

#include <iostream>
#include <tuple>
#include <type_traits>

template <typename T> struct Identity { using type = T; };

// Merging packs of types.
template <typename...> struct MergePacks;

template <typename Pack>
struct MergePacks<Pack> : Identity<Pack> {};

template <template <typename...> class P, typename... Types1, typename... Types2, typename... Packs>
struct MergePacks<P<Types1...>, P<Types2...>, Packs...> : MergePacks<P<Types1..., Types2...>, Packs...> {};

// Appending a type to a pack.
template <typename Pack, typename T> struct AppendType;

template <template <typename...> class P, typename... Ts, typename T>
struct AppendType <P<Ts...>, T> {
    using type = P<Ts..., T>;
};

// ExpandPackWithTuple takes a pack, and creates N packs that each end with the tuple's elements, N is the size of the tuple.
template <template <typename...> class P, typename Pack, typename Tuple, typename Indices> struct ExpandPackWithTupleHelper;

template <template <typename...> class P, typename Pack, typename Tuple, std::size_t... Is>
struct ExpandPackWithTupleHelper<P, Pack, Tuple, std::index_sequence<Is...>> {
    using type = P<typename AppendType<Pack, typename std::tuple_element<Is, Tuple>::type>::type...>;
};

template <template <typename...> class P, typename Pack, typename Tuple>
using ExpandPackWithTuple = typename ExpandPackWithTupleHelper<P, Pack, Tuple, std::make_index_sequence<std::tuple_size<Tuple>::value>>::type;

// TupleTreeWithRepeats.
template <template <typename...> class P, typename NumRepeats, std::size_t LoopNumber, typename OutputPack, typename... Tuples> struct TupleTreeWithRepeatsHelper;

template <template <typename...> class P, std::size_t I, std::size_t... Is, std::size_t LoopNumber, typename... Ts, typename First, typename... Rest>
struct TupleTreeWithRepeatsHelper<P, std::index_sequence<I, Is...>, LoopNumber, P<Ts...>, First, Rest...> :
    TupleTreeWithRepeatsHelper<P, std::index_sequence<I, Is...>, LoopNumber + 1, typename MergePacks<ExpandPackWithTuple<P, Ts, First>...>::type, First, Rest...> {};

template <template <typename...> class P, std::size_t I, std::size_t... Is, typename... Ts, typename First, typename... Rest>
struct TupleTreeWithRepeatsHelper<P, std::index_sequence<I, Is...>, I, P<Ts...>, First, Rest...> :
    TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, 0, typename MergePacks<ExpandPackWithTuple<P, Ts, First>...>::type, Rest...> {};

template <template <typename...> class P, std::size_t... Is, std::size_t LoopNumber, typename OutputPack>
struct TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, LoopNumber, OutputPack> {
    using type = OutputPack;
};

template <template <typename...> class P, typename NumRepeats, typename... Tuples> struct TupleTreeWithRepeats;

template <template <typename...> class P, std::size_t I, std::size_t... Is, typename... Tuples>
struct TupleTreeWithRepeats<P, std::index_sequence<I, Is...>, Tuples...> : TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, 0, P<P<>>, Tuples...> {};

// Testing
template <typename...> struct Pack;
using T1 = std::tuple<int, char, double>;
using T2 = std::tuple<bool, double, int, char>;
using T3 = std::tuple<double, int>;

int main() {
    std::cout << std::is_same<
        TupleTreeWithRepeats<Pack, std::index_sequence<1,1,1>, T1, T2, T3>::type,
        Pack<
            Pack<int, bool, double>, Pack<int, bool, int>, Pack<int, double, double>, Pack<int, double, int>, Pack<int, int, double>, Pack<int, int, int>, Pack<int, char, double>, Pack<int, char, int>,
            Pack<char, bool, double>, Pack<char, bool, int>, Pack<char, double, double>, Pack<char, double, int>, Pack<char, int, double>, Pack<char, int, int>, Pack<char, char, double>, Pack<char, char, int>,
            Pack<double, bool, double>, Pack<double, bool, int>, Pack<double, double, double>, Pack<double, double, int>, Pack<double, int, double>, Pack<double, int, int>, Pack<double, char, double>, Pack<double, char, int>
        >
    >::value << '\n';  // ambiguous
}
4
  • Interestingly it is not ambiguous for clang: coliru.stacked-crooked.com/a/4272e7d68f252d6e
    – Marco A.
    Oct 2, 2015 at 22:02
  • I'm compiling with GCC 5.1. I edited my code slightly just now by the way, because I spotted a logic error in the second specialization. But the ambiguity is still the main problem. But the ambiguity needs to be removed first before I fine-tune the specializations and test the output.
    – prestokeys
    Oct 2, 2015 at 22:03
  • @MarcoA. I think the compilation simply timed out on that one. Looking at the output with less depth, it looks like clang was going down some infinite recursion.
    – T.C.
    Oct 2, 2015 at 22:03
  • @T.C. I'm inclined to think that you're right, although I would have expected a feedback for that
    – Marco A.
    Oct 2, 2015 at 22:06

2 Answers 2

1

As far as I can tell, these two should not be ambiguous.

Regardless, an easy workaround is to just implement "with repeats" in terms of "without repeats":

// TupleTreeWithRepeats.
template <template <typename...> class P, typename Tuples>
struct TupleTreeWithRepeatsHelper;

template <template <typename...> class P, typename... Tuples>
struct TupleTreeWithRepeatsHelper<P, Pack<Tuples...>> :
    Identity<TupleTree<P, Tuples...>> {};

template <template <typename...> class P, typename NumRepeats, typename... Tuples> 
struct TupleTreeWithRepeats;

template <template <typename...> class P, std::size_t... Is, typename... Tuples>
struct TupleTreeWithRepeats<P, std::index_sequence<Is...>, Tuples...> :
    TupleTreeWithRepeatsHelper<P, typename MergePacks<repeat<Tuples, Is>...>::type> {};

Where repeat is

template<class T, std::size_t> using id = T;

template<class T, std::size_t... Is>
Pack<id<T, Is>...> do_repeat(std::index_sequence<Is...>);

template<class T, std::size_t I>
using repeat = decltype(do_repeat<T>(std::make_index_sequence<I>()));

Demo. One might argue that this is also a better design.


Minimized to:

template<class> class Purr { };

template <template <class> class, class>
struct Meow;

template <template <class> class P>
struct Meow<P, P<int>> { };

template <template <class> class P, class T>
struct Meow<P, P<T>> { };

Meow<Purr, Purr<int>> c;

GCC reports an ambiguity, which definitely looks like a bug to me. Clang handles this correctly.

1
  • Thanks for the workaround, T.C. But since understanding the C++ language is more important than my program, is the first implementation truly ambiguous or not? I know you stated your opinion. But if it truly is ambiguous, will a workaround like your solution above always exist?
    – prestokeys
    Oct 2, 2015 at 22:15
0

Though T.C.'s workaround is certainly more elegant, this workaround I've found might be the general workaround that should always work whenever this GCC bug is encountered. Instead of avoiding the GCC bug, I confronted it. Simply replace P<Ts...> with a single typename and define a separate meta-function that uses it:

template <template <typename...> class P, typename OutputPack, typename Tuple> struct AddToOutput;

template <template <typename...> class P, typename... Ts, typename Tuple>
struct AddToOutput<P, P<Ts...>, Tuple> : MergePacks<ExpandPackWithTuple<P, Ts, Tuple>...> {};

// My workaround, using struct AddToOutput.
template <template <typename...> class P, std::size_t... Is, std::size_t LoopNumber, typename OutputPack, typename First, typename... Rest>
struct TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, LoopNumber, OutputPack, First, Rest...> :
    TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, LoopNumber + 1, typename AddToOutput<P, OutputPack, First>::type, First, Rest...> {};

template <template <typename...> class P, std::size_t I, std::size_t... Is, typename OutputPack, typename First, typename... Rest>
struct TupleTreeWithRepeatsHelper<P, std::index_sequence<I, Is...>, I, OutputPack, First, Rest...> :
    TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, 1, typename AddToOutput<P, OutputPack, First>::type, Rest...> {};

The entire code:

#include <iostream>
#include <tuple>

template <typename T> struct Identity { using type = T; };

// Merging packs of types.
template <typename...> struct MergePacks;

template <typename Pack>
struct MergePacks<Pack> : Identity<Pack> {};

template <template <typename...> class P, typename... Types1, typename... Types2, typename... Packs>
struct MergePacks<P<Types1...>, P<Types2...>, Packs...> : MergePacks<P<Types1..., Types2...>, Packs...> {};

// Appending a type to a pack.
template <typename Pack, typename T> struct AppendType;

template <template <typename...> class P, typename... Ts, typename T>
struct AppendType <P<Ts...>, T> {
    using type = P<Ts..., T>;
};

// ExpandPackWithTuple takes a pack, and creates N packs that each end with the tuple's elements, where N is the size of the tuple.
template <template <typename...> class P, typename Pack, typename Tuple, typename Indices> struct ExpandPackWithTupleHelper;

template <template <typename...> class P, typename Pack, typename Tuple, std::size_t... Is>
struct ExpandPackWithTupleHelper<P, Pack, Tuple, std::index_sequence<Is...>> {
    using type = P<typename AppendType<Pack, typename std::tuple_element<Is, Tuple>::type>::type...>;
};

template <template <typename...> class P, typename Pack, typename Tuple>
using ExpandPackWithTuple = typename ExpandPackWithTupleHelper<P, Pack, Tuple, std::make_index_sequence<std::tuple_size<Tuple>::value>>::type;

// Now, for TupleTree itself.
template <template <typename...> class P, typename OutputPack, typename... Tuples> struct TupleTreeHelper;

template <template <typename...> class P, typename... Ts, typename First, typename... Rest>
struct TupleTreeHelper<P, P<Ts...>, First, Rest...> : TupleTreeHelper<P, typename MergePacks<ExpandPackWithTuple<P, Ts, First>...>::type, Rest...> {};

template <template <typename...> class P, typename OutputPack>
struct TupleTreeHelper<P, OutputPack> {
    using type = OutputPack;
};

template <template <typename...> class P, typename... Tuples>
using TupleTree = typename TupleTreeHelper<P, P<P<>>, Tuples...>::type;

// TupleTreeWithRepeats.
template <template <typename...> class P, typename NumRepeats, std::size_t LoopNumber, typename OutputPack, typename... Tuples> struct TupleTreeWithRepeatsHelper;

template <template <typename...> class P, typename OutputPack, typename Tuple> struct AddToOutput;  // This is only needed for a workaround against the GCC 5.1 bug explained below.

template <template <typename...> class P, typename... Ts, typename Tuple>
struct AddToOutput<P, P<Ts...>, Tuple> : MergePacks<ExpandPackWithTuple<P, Ts, Tuple>...> {};

// The following two specializations run into ambiguity with GCC 5.1, though Clang runs it fine.  It is GCC that is bugged.
//template <template <typename...> class P, std::size_t... Is, std::size_t LoopNumber, typename... Ts, typename First, typename... Rest>
//struct TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, LoopNumber, P<Ts...>, First, Rest...> :
//  TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, LoopNumber + 1, typename MergePacks<ExpandPackWithTuple<P, Ts, First>...>::type, First, Rest...> {};
//
//template <template <typename...> class P, std::size_t I, std::size_t... Is, typename... Ts, typename First, typename... Rest>
//struct TupleTreeWithRepeatsHelper<P, std::index_sequence<I, Is...>, I, P<Ts...>, First, Rest...> :
//  TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, 1, typename MergePacks<ExpandPackWithTuple<P, Ts, First>...>::type, Rest...> {};

// My workaround, using struct AddToOutput.
template <template <typename...> class P, std::size_t... Is, std::size_t LoopNumber, typename OutputPack, typename First, typename... Rest>
struct TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, LoopNumber, OutputPack, First, Rest...> :
    TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, LoopNumber + 1, typename AddToOutput<P, OutputPack, First>::type, First, Rest...> {};

template <template <typename...> class P, std::size_t I, std::size_t... Is, typename OutputPack, typename First, typename... Rest>
struct TupleTreeWithRepeatsHelper<P, std::index_sequence<I, Is...>, I, OutputPack, First, Rest...> :
    TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, 1, typename AddToOutput<P, OutputPack, First>::type, Rest...> {};

template <template <typename...> class P, typename OutputPack>
struct TupleTreeWithRepeatsHelper<P, std::index_sequence<>, 1, OutputPack> {
    using type = OutputPack;
};

template <template <typename...> class P, typename NumRepeats, typename... Tuples> struct TupleTreeWithRepeats;

template <template <typename...> class P, std::size_t... Is, typename... Tuples>
struct TupleTreeWithRepeats<P, std::index_sequence<Is...>, Tuples...> : TupleTreeWithRepeatsHelper<P, std::index_sequence<Is...>, 1, P<P<>>, Tuples...> {};

// Testing
#include <type_traits>

template <typename...> struct Pack;
using T1 = std::tuple<int, char, double>;
using T2 = std::tuple<bool, double, int, char>;
using T3 = std::tuple<double, int>;

int main() {
    std::cout << std::boolalpha;
    std::cout << std::is_same<
        ExpandPackWithTuple<Pack, Pack<int, bool>, std::tuple<int, char, double>>,
        Pack<Pack<int, bool, int>, Pack<int, bool, char>, Pack<int, bool, double>>
    >::value << '\n';  // true

    std::cout << std::is_same<
        MergePacks<ExpandPackWithTuple<Pack, Pack<>, T1>>::type,
        Pack<Pack<int>, Pack<char>, Pack<double>>
    >::value << '\n';  // true

    std::cout << std::is_same<
        MergePacks<ExpandPackWithTuple<Pack, Pack<int>, T2>, ExpandPackWithTuple<Pack, Pack<char>, T2>, ExpandPackWithTuple<Pack, Pack<double>, T2>>::type,
        Pack<
            Pack<int, bool>, Pack<int, double>, Pack<int, int>, Pack<int, char>,
            Pack<char, bool>, Pack<char, double>, Pack<char, int>, Pack<char, char>,
            Pack<double, bool>, Pack<double, double>, Pack<double, int>, Pack<double, char>
        >
    >::value << '\n';  // true

    std::cout << std::is_same<
        TupleTree<Pack, T1, T2>,
        Pack<
            Pack<int, bool>, Pack<int, double>, Pack<int, int>, Pack<int, char>,
            Pack<char, bool>, Pack<char, double>, Pack<char, int>, Pack<char, char>,
            Pack<double, bool>, Pack<double, double>, Pack<double, int>, Pack<double, char>
        >
    >::value << '\n';  // true

    std::cout << std::is_same<
        TupleTree<Pack, T1, T2, T3>,
        Pack<
            Pack<int, bool, double>, Pack<int, bool, int>, Pack<int, double, double>, Pack<int, double, int>, Pack<int, int, double>, Pack<int, int, int>, Pack<int, char, double>, Pack<int, char, int>,
            Pack<char, bool, double>, Pack<char, bool, int>, Pack<char, double, double>, Pack<char, double, int>, Pack<char, int, double>, Pack<char, int, int>, Pack<char, char, double>, Pack<char, char, int>,
            Pack<double, bool, double>, Pack<double, bool, int>, Pack<double, double, double>, Pack<double, double, int>, Pack<double, int, double>, Pack<double, int, int>, Pack<double, char, double>, Pack<double, char, int>
        >
    >::value << '\n';  // true

    std::cout << std::is_same<
        TupleTreeWithRepeats<Pack, std::index_sequence<1,1>, T1, T2>::type,
        Pack<
            Pack<int, bool>, Pack<int, double>, Pack<int, int>, Pack<int, char>,
            Pack<char, bool>, Pack<char, double>, Pack<char, int>, Pack<char, char>,
            Pack<double, bool>, Pack<double, double>, Pack<double, int>, Pack<double, char>
        >
    >::value << '\n';  // true

    std::cout << std::is_same<
        TupleTreeWithRepeats<Pack, std::index_sequence<1,1,1>, T1, T2, T3>::type,
        Pack<
            Pack<int, bool, double>, Pack<int, bool, int>, Pack<int, double, double>, Pack<int, double, int>, Pack<int, int, double>, Pack<int, int, int>, Pack<int, char, double>, Pack<int, char, int>,
            Pack<char, bool, double>, Pack<char, bool, int>, Pack<char, double, double>, Pack<char, double, int>, Pack<char, int, double>, Pack<char, int, int>, Pack<char, char, double>, Pack<char, char, int>,
            Pack<double, bool, double>, Pack<double, bool, int>, Pack<double, double, double>, Pack<double, double, int>, Pack<double, int, double>, Pack<double, int, int>, Pack<double, char, double>, Pack<double, char, int>
        >
    >::value << '\n';  // true
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.