Infinite recursive template instantiation expected?

Question

I am trying to understand why a piece of template metaprogramming is not generating an infinite recursion. I tried to reduce the test case as much as possible, but there's still a bit of setup involved, so bear with me :)

The setup is the following. I have a generic function foo(T) which delegates the implementation to a generic functor called foo_impl via its call operator, like this:

template <typename T, typename = void>
struct foo_impl {};

template <typename T>
inline auto foo(T x) -> decltype(foo_impl<T>{}(x))
{
    return foo_impl<T>{}(x);
}

foo() uses decltype trailing return type for SFINAE purposes. The default implementation of foo_impl does not define any call operator. Next, I have a type-trait that detects whether foo() can be called with an argument of type T:

template <typename T>
struct has_foo
{
    struct yes {};
    struct no {};
    template <typename T1>
    static auto test(T1 x) -> decltype(foo(x),void(),yes{});
    static no test(...);
    static const bool value = std::is_same<yes,decltype(test(std::declval<T>()))>::value;
};

This is just the classic implementation of a type trait via expression SFINAE: has_foo<T>::value will be true if a valid foo_impl specialisation exists for T, false otherwise. Finally, I have two specialisations of the the implementation functor for integral types and for floating-point types:

template <typename T>
struct foo_impl<T,typename std::enable_if<std::is_integral<T>::value>::type>
{
    void operator()(T) {}
};

template <typename T>
struct foo_impl<T,typename std::enable_if<has_foo<unsigned>::value && std::is_floating_point<T>::value>::type>
{
    void operator()(T) {}
};

In the last foo_impl specialisation, the one for floating-point types, I have added the extra condition that foo() must be available for the type unsigned (has_foo<unsigned>::value).

What I don't understand is why the compilers (GCC & clang both) accept the following code:

int main()
{
    foo(1.23);
}

In my understanding, when foo(1.23) is called the following should happen:

1. the specialisation of foo_impl for integral types is discarded because 1.23 is not integral, so only the second specialisation of foo_impl is considered;
2. the enabling condition for the second specialisation of foo_impl contains has_foo<unsigned>::value, that is, the compiler needs to check if foo() can be called on type unsigned;
3. in order to check if foo() can be called on type unsigned, the compiler needs again to select a specialisation of foo_impl among the two available;
4. at this point, in the enabling condition for the second specialisation of foo_impl the compiler encounters again the condition has_foo<unsigned>::value.
5. GOTO 3.

However, it seems like the code is happily accepted both by GCC 5.4 and Clang 3.8. See here: http://ideone.com/XClvYT

I would like to understand what is going on here. Am I misunderstanding something and the recursion is blocked by some other effect? Or maybe am I triggering some sort of undefined/implementation defined behaviour?

Answer 1

has_foo<unsigned>::value is a non-dependent expression, so it immediately triggers instantiation of has_foo<unsigned> (even if the corresponding specialization is never used).

The relevant rules are [temp.point]/1:

For a function template specialization, a member function template specialization, or a specialization for a member function or static data member of a class template, if the specialization is implicitly instantiated because it is referenced from within another template specialization and the context from which it is referenced depends on a template parameter, the point of instantiation of the specialization is the point of instantiation of the enclosing specialization. Otherwise, the point of instantiation for such a specialization immediately follows the namespace scope declaration or definition that refers to the specialization.

(note that we're in the non-dependent case here), and [temp.res]/8:

The program is ill-formed, no diagnostic required, if:
- [...]
- a hypothetical instantiation of a template immediately following its definition would be ill-formed due to a construct that does not depend on a template parameter, or
- the interpretation of such a construct in the hypothetical instantiation is different from the interpretation of the corresponding construct in any actual instantiation of the template.

These rules are intended to give the implementation freedom to instantiate has_foo<unsigned> at the point where it appears in the above example, and to give it the same semantics as if it had been instantiated there. (Note that the rules here are actually subtly wrong: the point of instantiation for an entity referenced by the declaration of another entity actually must immediately precede that entity rather than immediately following it. This has been reported as a core issue, but it's not on the issues list yet as the list hasn't been updated for a while.)

As a consequence, the point of instantiation of has_foo within the floating-point partial specialization occurs before the point of declaration of that specialization, which is after the > of the partial specialization per [basic.scope.pdecl]/3:

The point of declaration for a class or class template first declared by a class-specifier is immediately after the identifier or simple-template-id (if any) in its class-head (Clause 9).

Therefore, when the call to foo from has_foo<unsigned> looks up the partial specializatios of foo_impl, it does not find the floating-point specialization at all.

A couple of other notes about your example:

1) Use of cast-to-void in comma operator:

static auto test(T1 x) -> decltype(foo(x),void(),yes{});

This is a bad pattern. operator, lookup is still performed for a comma operator where one of its operands is of class or enumeration type (even though it can never succeed). This can result in ADL being performed [implementations are permitted but not required to skip this], which triggers the instantiation of all associated classes of the return type of foo (in particular, if foo returns unique_ptr<X<T>>, this can trigger the instantiation of X<T> and may render the program ill-formed if that instantiation doesn't work from this translation unit). You should prefer to cast all operands of a comma operator of user-defined type to void:

static auto test(T1 x) -> decltype(void(foo(x)),yes{});

2) SFINAE idiom:

template <typename T1>
static auto test(T1 x) -> decltype(void(foo(x)),yes{});
static no test(...);
static const bool value = std::is_same<yes,decltype(test(std::declval<T>()))>::value;

This is not a correct SFINAE pattern in the general case. There are a few problems here:

• if T is a type that cannot be passed as an argument, such as void, you trigger a hard error instead of value evaluating to false as intended
• if T is a type to which a reference cannot be formed, you again trigger a hard error
• you check whether foo can be applied to an lvalue of type remove_reference<T> even if T is an rvalue reference

A better solution is to put the entire check into the yes version of test instead of splitting the declval portion into value:

template <typename T1>
static auto test(int) -> decltype(void(foo(std::declval<T1>())),yes{});
template <typename>
static no test(...);
static const bool value = std::is_same<yes,decltype(test<T>(0))>::value;

This approach also more naturally extends to a ranked set of options:

// elsewhere
template<int N> struct rank : rank<N-1> {};
template<> struct rank<0> {};


template <typename T1>
static no test(rank<2>, std::enable_if_t<std::is_same<T1, double>::value>* = nullptr);
template <typename T1>
static yes test(rank<1>, decltype(foo(std::declval<T1>()))* = nullptr);
template <typename T1>
static no test(rank<0>);
static const bool value = std::is_same<yes,decltype(test<T>(rank<2>()))>::value;

Finally, your type trait will evaluate faster and use less memory at compile time if you move the above declarations of test outside the definition of has_foo (perhaps into some helper class or namespace); that way, they do not need to be redundantly instantiated once for each use of has_foo.

Answer 2

It's not actually UB. But it really shows you how TMP is complex...

The reason this doesn't infinitely recurse is because of completeness.

template <typename T>
struct foo_impl<T,typename std::enable_if<std::is_integral<T>::value>::type>
{
    void operator()(T) {}
};

// has_foo here

template <typename T>
struct foo_impl<T,typename std::enable_if<has_foo<unsigned>::value && std::is_floating_point<T>::value>::type>
{
    void operator()(T) {}
};

When you call foo(3.14);, you instantiate has_foo<float>. That in turn SFINAEs on foo_impl.

The first one is enabled if is_integral. Obviously, this fails.

The second foo_impl<float> is now considered. Trying to instantiate it, the compiles sees has_foo<unsigned>::value.

Back to instantiating foo_impl: foo_impl<unsigned>!

The first foo_impl<unsigned> is a match.

The second one is considered. The enable_if contains has_foo<unsigned> - the one the compiler is already trying to instantiate.

Since it's currently being instantiated, it's incomplete, and this specialization is not considered.

Recursion stops, has_foo<unsigned>::value is true, and your code snippet works!

---

So, you want to know how it comes down to it in the standard? Okay.

[14.7.1/1] If a class template has been declared, but not defined, at the point of instantiation ([temp.point]), the instantiation yields an incomplete class type.

(incomplete)