Why template instantiations go on forever here?

2019-04-02 21:20发布

问题:

In the following code, I want to replace

template <typename T, typename... Args>
auto check (rank<1,T>, Args... args) const
        -> std::enable_if_t<!has_argument_type<T, Args...>(), decltype(check(rank<2, Ts...>{}, args...))> {
    return check(rank<2, Ts...>{}, args...);  // Since rank<1,T> derives immediately from rank<2, Ts...>.
}

template <typename T, typename... Args>
auto check (rank<2,T>, Args... args) const
        -> std::enable_if_t<!has_argument_type<T, Args...>(), decltype(check(rank<3, Ts...>{}, args...))> {
    return check(rank<3, Ts...>{}, args...);  // Since rank<2,T> derives immediately from rank<3, Ts...>.
}
// etc... until rank<9>.

with the simple

template <std::size_t N, typename T, typename... Args>
auto check (rank<N,T>, Args... args) const
        -> std::enable_if_t<!has_argument_type<T, Args...>(), decltype(check(rank<N+1, Ts...>{}, args...))> {
    return check(rank<N+1, Ts...>{}, args...);  // Since rank<N,T> derives immediately from rank<N+1, Ts...>.
}

template <typename T, typename... Args>
auto check (rank<10, T>, Args... args) const { std::cout << "Nothing found.\n"; }

But when I do, the template instantiations go on forever despite the terminating check(rank<10, T>, Args... args) function. Here is the full code using the long version above. Sorry for not minimizing the problem because I don't think I can minimize it and show what the problem is. Jumping to main() will show you the simple task I'm after, but I want to solve it using sequence ranking and overload resolution.

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

template <typename T, typename... Args>
constexpr auto has_argument_type_impl(int)
    -> decltype(std::is_same<typename T::argument_type, std::tuple<Args...>>{});  // Checking both that T::argument_type exists and that it is the same as std::tuple<Args...>.

template <typename T, typename... Args>
constexpr auto has_argument_type_impl(long) -> std::false_type;

template <typename T, typename... Args>
constexpr bool has_argument_type() { return decltype(has_argument_type_impl<T, Args...>(0))::value; }

template <typename T, std::size_t N, typename... Args>
constexpr auto has_argument_type_n_impl(int)
    -> decltype(std::is_same<typename T::template argument_type<N>, std::tuple<Args...>>{});  // Checking both that T::argument_type<N> exists and that it is the same as std::tuple<Args...>.

template <typename T, std::size_t N, typename... Args>
constexpr auto has_argument_type_n_impl(long) -> std::false_type;

template <typename T, std::size_t N, typename... Args>
constexpr bool has_argument_type_n() { return decltype(has_argument_type_n_impl<T, N, Args...>(0))::value; }

template <typename... Ts>
class Factory {
    template <std::size_t, typename...> struct rank;

    template <std::size_t N, typename First, typename... Rest>
    struct rank<N, First, Rest...> : rank<N, Rest...> {};

    template <std::size_t N, typename T> struct rank<N,T> : rank<N+1, Ts...> {};

    template <typename T> struct rank<10, T> {};  // Need to end the instantiations somewhere.
public:
    template <typename... Args>
    decltype(auto) create (Args... args) const {
        return check(rank<0, Ts...>{}, args...);
    }
private:
    template <typename T, typename... Rest, typename... Args>
    auto check (rank<0, T, Rest...>, Args... args) const
            -> std::enable_if_t<has_argument_type<T, Args...>(), decltype(T(args...))> {
        return T(args...);
    }

    template <typename T, typename... Rest, typename... Args>
    auto check (rank<0, T, Rest...>, Args... args) const
            -> std::enable_if_t<!has_argument_type<T, Args...>(), decltype(check(rank<0, Rest...>{}, args...))> {
        return check(rank<0, Rest...>{}, args...);
    }

    template <typename T, typename... Args>
    auto check (rank<0,T>, Args... args) const
            -> std::enable_if_t<!has_argument_type<T, Args...>(), decltype(check(rank<1, Ts...>{}, args...))> {
        return check(rank<1, Ts...>{}, args...);  // Since rank<0,T> derives immediately from rank<1, Ts...>.
    }

    template <std::size_t N, typename T, typename... Rest, typename... Args>
    auto check (rank<N, T, Rest...>, Args... args) const
            -> std::enable_if_t<has_argument_type_n<T, N-1, Args...>(), decltype(T(args...))> {
        return T(args...);
    }

    template <std::size_t N, typename T, typename... Rest, typename... Args>
    auto check (rank<N, T, Rest...>, Args... args) const
            -> std::enable_if_t<!has_argument_type_n<T, N-1, Args...>(), decltype(check(rank<N, Rest...>{}, args...))> {
        return check(rank<N, Rest...>{}, args...);
    }

//  I want to use the following instead of what's below it.
//  template <std::size_t N, typename T, typename... Args>
//  auto check (rank<N,T>, Args... args) const
//          -> std::enable_if_t<!has_argument_type_n<T, N-1, Args...>(), decltype(check(rank<N+1, Ts...>{}, args...))> {
//      return check(rank<N+1, Ts...>{}, args...);  // Since rank<N,T> derives immediately from rank<N+1, Ts...>.
//  }
//
//  template <typename T, typename... Args>
//  auto check (rank<10, T>, Args... args) const { std::cout << "Nothing found.\n"; }

    template <typename T, typename... Args>
    auto check (rank<1,T>, Args... args) const
            -> std::enable_if_t<!has_argument_type_n<T, 0, Args...>(), decltype(check(rank<2, Ts...>{}, args...))> {
        return check(rank<2, Ts...>{}, args...);  // Since rank<1,T> derives immediately from rank<2, Ts...>.
    }

    template <typename T, typename... Args>
    auto check (rank<2,T>, Args... args) const
            -> std::enable_if_t<!has_argument_type_n<T, 1, Args...>(), decltype(check(rank<3, Ts...>{}, args...))> {
        return check(rank<3, Ts...>{}, args...);  // Since rank<2,T> derives immediately from rank<3, Ts...>.
    }
    // etc... until rank<9>.
};

// Testing
struct Object {
    template <std::size_t, typename = void> struct ArgumentType;
    template <typename T> struct ArgumentType<0,T> { using type = std::tuple<int, bool, char, double>; };
    template <typename T> struct ArgumentType<1,T> { using type = std::tuple<bool, char, double>; };
    template <std::size_t N> using argument_type = typename ArgumentType<N>::type;

    Object (int, bool, char, double) { print(); }
    Object (bool, char, double) { print(); }
    void print() const { std::cout << "Object\n"; }
};

struct Thing {
    template <std::size_t, typename = void> struct ArgumentType;
    template <typename T> struct ArgumentType<0,T> { using type = std::tuple<int, int, char>; };
    template <typename T> struct ArgumentType<1,T> { using type = std::tuple<int, char>; };
    template <typename T> struct ArgumentType<2,T> { using type = std::tuple<char>; };
    template <std::size_t N> using argument_type = typename ArgumentType<N>::type;

    Thing (int, int, char) { print(); }
    Thing (int, char) { print(); }
    Thing (char) { print(); }
    void print() const { std::cout << "Thing\n"; }
};

struct Blob {
    using argument_type = std::tuple<int, double>;

    Blob (int, double) { print(); }
    void print() const { std::cout << "Blob\n"; }
};

struct Widget {
    using argument_type = std::tuple<int>;
    Widget (double, double, int, double) { print(); }
    Widget (int) { print(); }
    void print() const { std::cout << "Widget\n"; }
};

int main() {
    Factory<Blob, Object, Thing, Widget>().create(4,3.5);  // Blob
    Factory<Object, Blob, Widget, Thing>().create(2);  // Widget
    Factory<Object, Thing, Blob, Widget>().create(5);  // Widget
    Factory<Blob, Object, Thing, Widget>().create(4,true,'a',7.5);  // Object
    Factory<Blob, Thing, Object, Widget>().create(true,'a',7.5);  // Object
    Factory<Blob, Object, Thing, Widget>().create('a');  // Thing
}

I know that there are other ways of accomplishing this, but I'm trying to understand sequence ranking better, and would like to know why I cannot use the commented-out section. How to avoid the repetitive code that I need to put (to rank<9>, or even higher rank) that is currently making this code work? Thanks for your patience.

Note: I actually must NOT enter the repetitive part of the code manually as I currently have. Because the highest N value for rank<N, Ts...> used in the check overloads will be determined during compile-time as the highest N value such that a argument_type<N> member type exists among all the Ts.... Thus I HAVE to use the generic part that I commented out, and the rank<10,T> I'm using will have to have the 10 replaced by that specific N value. Thus, this is not just a matter of convenience. I have to solve this problem to continue developing the program.

Edit: Here is a more minimal example, showing the same problem:

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

template <typename T>
constexpr auto has_argument_type_impl(int)
    -> decltype(typename T::argument_type{}, std::true_type{});

template <typename T>
constexpr auto has_argument_type_impl(long) -> std::false_type;

template <typename T>
constexpr bool has_argument_type() { return decltype(has_argument_type_impl<T>(0))::value; }

template <typename... Ts>
class Factory {
    template <std::size_t, typename...> struct rank;

    template <std::size_t N, typename First, typename... Rest>
    struct rank<N, First, Rest...> : rank<N, Rest...> {};

    template <std::size_t N, typename T> struct rank<N,T> : rank<N+1, Ts...> {};

    template <typename T> struct rank<10, T> {};  // Need to end the instantiations somewhere.
public:
    template <typename... Args>
    decltype(auto) create (Args... args) const {
        return check(rank<0, Ts...>{}, args...);
    }
private:
    template <std::size_t N, typename T, typename... Rest, typename... Args>
    auto check (rank<N, T, Rest...>, Args... args) const
            -> std::enable_if_t<has_argument_type<T>(), decltype(T(args...))> {
        return T(args...);
    }

    template <std::size_t N, typename T, typename... Rest, typename... Args>
    auto check (rank<N, T, Rest...>, Args... args) const
            -> std::enable_if_t<!has_argument_type<T>(), decltype(check(rank<N, Rest...>{}, args...))> {
        return check(rank<N, Rest...>{}, args...);
    }

    template <typename T, typename... Args>
    auto check (rank<0,T>, Args... args) const
            -> std::enable_if_t<!has_argument_type<T>(), decltype(check(rank<1, Ts...>{}, args...))> {
        return check(rank<1, Ts...>{}, args...);  // Since rank<0,T> derives immediately from rank<1, Ts...>.
    }

//  I want to use the following instead of what's below it.
//  template <std::size_t N, typename T, typename... Args>
//  auto check (rank<N,T>, Args... args) const
//          -> std::enable_if_t<!has_argument_type<T>(), decltype(check(rank<N+1, Ts...>{}, args...))> {
//      return check(rank<N+1, Ts...>{}, args...);  // Since rank<N,T> derives immediately from rank<N+1, Ts...>.
//  }
//
//  template <typename T, typename... Args>
//  auto check (rank<10, T>, Args... args) const { std::cout << "Nothing found.\n"; }

    template <typename T, typename... Args>
    auto check (rank<1,T>, Args... args) const
            -> std::enable_if_t<!has_argument_type<T>(), decltype(check(rank<2, Ts...>{}, args...))> {
        return check(rank<2, Ts...>{}, args...);  // Since rank<1,T> derives immediately from rank<2, Ts...>.
    }

    template <typename T, typename... Args>
    auto check (rank<2,T>, Args... args) const
            -> std::enable_if_t<!has_argument_type<T>(), decltype(check(rank<3, Ts...>{}, args...))> {
        return check(rank<3, Ts...>{}, args...);  // Since rank<2,T> derives immediately from rank<3, Ts...>.
    }
    // etc... until rank<9>.
};

// Testing
struct Object {};
struct Thing {};

struct Blob {
    using argument_type = std::tuple<int, double>;
    Blob (int, double) { std::cout << "Blob\n"; }
};

int main() {
    Factory<Object, Thing, Blob>().create(4,3.5);  // Blob
}

回答1:

Partial ordering does not kick in until very late in the overload resolution process.

Ignoring all the ping-ponging amongst your various check overloads, eventually you end up with

template <std::size_t N, typename T, typename... Args>
auto check (rank<N,T>, Args... args) const
      -> std::enable_if_t<!has_argument_type_n<T, N, Args...>(), 
                          decltype(check(rank<N+1, Ts...>{}, args...))>;

template <typename T, typename... Args>
auto check (rank<10, T>, Args... args) const;

with a rank<10, something I frankly don't care about>. Deduction and substitution will be performed for both overloads; and as part of substitution into the return type of the first signature, you'll instantiate rank<11, Ts...>, which in turn bypasses the terminating specialization of rank, resulting in an infinite chain of template instantiations. You don't even get to the point where the partial ordering tiebreaker chooses the second overload.

Just constrain the first overload to N < 10. It will need to lexically precede the return type (so that when N >= 10 the compiler doesn't attempt to substitute into it), so put it in a default template argument.