SFINAE works with deduction but fails with substitution

Question

Consider the following MCVE

struct A {};

template<class T>
void test(T, T) {
}

template<class T>
class Wrapper {
    using type = typename T::type;
};

template<class T>
void test(Wrapper<T>, Wrapper<T>) {
}

int main() {
    A a, b;
    test(a, b);     // works
    test<A>(a, b);  // doesn't work
    return 0;
}

Here test(a, b); works and test<A>(a, b); fails with:

<source>:11:30: error: no type named 'type' in 'A'
    using type = typename T::type;
                 ~~~~~~~~~~~~^~~~
<source>:23:13: note: in instantiation of template class 'Wrap<A>' requested here
    test<A>(a, b);  // doesn't work
            ^
<source>:23:5: note: while substituting deduced template arguments into function template 'test' [with T = A]
    test<A>(a, b);  // doesn't work

LIVE DEMO

Question: Why is that? Shouldn't SFINAE work during substitution? Yet here it seems to work during deduction only.

Footcloth

In test(a, b);, T cannot be deduced for the second overload of test, so this overload is discarded before the instantiation of Wrapper<A>, and so the list of candidates only contains the first test, which is why this works. In the second case, the second overload is valid candidate since T is explicitly provided, thus implying the instantiation of Wrapper<A> which fails. – Inaptitude

Just curious: what is your intent here? To select different overloads based on the existence of the ::type member type? – Hertha

@LF The intent was to restrict the template to Wrapper<T> types, it seemed like it worked like SFINAE sometimes but apparently it didn't. – Footcloth

Answer 1

Deduction of the function called in a function call expression is performed in two steps:

1. Determination of the set of viable functions;
2. Determination of the best viable function.

The set of viable function can only contain function declaration and template function specialization declaration.

So when a call expression (test(a,b) or test<A>(a,b)) names a template function, it is necessary to determine all template arguments: this is called template argument deduction. This is performed in three steps [temp.deduct]:

1. Subsitution of explicitly provided template arguments (in names<A>(x,y) A is explicitly provided);(substitution means that in the function template delcaration, the template parameter are replaced by their argument)
2. Deduction of template arguments that are not provided;
3. Substitution of deduced template argument.

Call expression test(a,b)

1. There are no explictly provided template argument.
2. T is deduced to A for the first template function, deduction fails for the second template function [temp.deduct.type]/8. So the second template function will not participate to overload resolution
3. A is subsituted in the declaration of the first template function. The subsitution succeeds.

So there is only one overload in the set and it is selected by overload resolution.

Call expression test<A>(a,b)

(Edit after the pertinent remarks of @T.C. and @geza)

1. The template argument is provided: A and it is substituted in the declaration of the two template functions. This substitution only involves the instantiation of the declaration of the function template specialization. So it is fine for the two template
2. No deduction of template argument
3. No substitution of deduced template argument.

So the two template specializations, test<A>(A,A) and test<A>(Wrapper<A>,Wrapper<A>), participate in overload resolution. First the compiler must determine which function are viable. To do that the compiler needs to find an implicit conversion sequence that converts the function argument to the function parameter type [over.match.viable]/4:

Third, for F to be a viable function, there shall exist for each argument an implicit conversion sequence that converts that argument to the corresponding parameter of F.

For the second overload, in order to find a conversion to Wrapper<A> the compiler needs the definition of this class. So it (implicitly) instantiates it. This is this instantiation that causes the observed error generated by compilers.

Chinch

Thanks, makes sense. Can you provide the relevant quotes from the standard for why deduction fails in the first case test(a, b)? – Footcloth

@Footcloth I added the link in the answer to timsong-cpp.github.io/cppwp/n4659/temp.deduct.type#8. P and A must have the same form template-name<T> – Chinch

The substitution works just fine. A function is not "called" until it is selected by overload resolution. However, evaluating whether the function is a viable candidate requires checking if an A can be converted to a Wrapper<A>, and that requires instantiating Wrapper<A>. – Indigestible

I think you're somewhat wrong about the last part of your answer. With const Wrapper<T> &, compiler would not have to check whether Wrapper<A> is a completely defined object (similarly to Wrapper<T> &), yet it fails to compile. – Polythene

@Indigestible Indeed... I have thought that when I started editing the answer, that is why I sited overload resolution, and then I was wrong to change my mind! – Chinch

@Footcloth I had to make a serious edit after the remarks of T.C. and geza, I suppose this answer is somewhat in reviewed state now. – Chinch

Answer 2

Self introduction

Hello everyone, I am an innocent compiler.

The first call

test(a, b);     // works

In this call, the argument type is A. Let me first consider the first overload:

template <class T>
void test(T, T);

Easy. T = A. Now consider the second:

template <class T>
void test(Wrapper<T>, Wrapper<T>);

Hmm ... what? Wrapper<T> for A? I have to instantiate Wrapper<T> for every possible type T in the world just to make sure that a parameter of type Wrapper<T>, which might be specialized, can't be initialized with an argument of type A? Well ... I don't think I'm going to do that ...

Hence I will not instantiate any Wrapper<T>. I will choose the first overload.

The second call

test<A>(a, b);  // doesn't work

test<A>? Aha, I don't have to do deduction. Let me just check the two overloads.

template <class T>
void test(T, T);

T = A. Now substitute — the signature is (A, A). Perfect.

template <class T>
void test(Wrapper<T>, Wrapper<T>);

T = A. Now subst ... Wait, I never instantiated Wrapper<A>? I can't substitute then. How can I know whether this would be a viable overload for the call? Well, I have to instantiate it first. (instantiating) Wait ...

using type = typename T::type;

A::type? Error!

Back to L. F.

Hello everyone, I am L. F. Let's review what the compiler has done.

Was the compiler innocent enough? Did he (she?) conform to the standard? @YSC has pointed out that [temp.over]/1 says:

When a call to the name of a function or function template is written (explicitly, or implicitly using the operator notation), template argument deduction ([temp.deduct]) and checking of any explicit template arguments ([temp.arg]) are performed for each function template to find the template argument values (if any) that can be used with that function template to instantiate a function template specialization that can be invoked with the call arguments. For each function template, if the argument deduction and checking succeeds, the template-arguments (deduced and/or explicit) are used to synthesize the declaration of a single function template specialization which is added to the candidate functions set to be used in overload resolution. If, for a given function template, argument deduction fails or the synthesized function template specialization would be ill-formed, no such function is added to the set of candidate functions for that template. The complete set of candidate functions includes all the synthesized declarations and all of the non-template overloaded functions of the same name. The synthesized declarations are treated like any other functions in the remainder of overload resolution, except as explicitly noted in [over.match.best].

The missing type leads to a hard error. Read https://stackoverflow.com/a/15261234. Basically, we have two stages when determining whether template<class T> void test(Wrapper<T>, Wrapper<T>) is the desired overload:

1. Instantiation. In this case, we (fully) instantiate Wrapper<A>. In this stage, using type = typename T::type; is problematic because A::type is nonexistent. Problems that occur in this stage are hard errors.

2. Substitution. Since the first stage already fails, this stage is not even reached in this case. Problems that occur in this stage are subject to SFINAE.

So yeah, the innocent compiler has done the right thing.

Hertha

@YSC An overload has to be instantiated for its validity to be checked. I will update my answer to clarify on this point. – Hertha

Of course it has to be instantiated. But it's instantiated in the call test(a, b) too. Well, the declaration of the function anyway (but that includes Wrapper<whatever>). – Mancini

@StoryTeller Well ... given an argument of type A, Wrapper<T> can't be deduced. There is no type Wrapper<T> even remotely related to an argument of type A. Since it is not even deduced, what can be instantiated? – Hertha

Sorry, what? I don't recall a non-deduced context being dependent on the argument. It's a property of the parameter. – Mancini

@YSC No. What if Wrapper<A> has a constructor to take an argument of type A? – Hertha

@StoryTeller Sorry ... I accidentally used a term that has a special meaning ... I will change my wording. – Hertha

@StoryTeller "but that includes Wrapper<whatever>" - Well, that includes Wrapper<whatever> is whatever can be deduced. Since whatever cannot be deduced, this overload is discarded from the list of candidates, and Wrapper<whatever> is not instantiated. – Inaptitude

@Inaptitude - Aha, yes, of course. Pattern matching first. – Mancini

@StoryTeller I will update my answer. It is simplifying things too much now. – Hertha

@YSC The answer has been rewritten significantly. Do you have any suggestions now? – Hertha

@StoryTeller The answer has been rewritten significantly. Do you have any suggestions now? – Hertha

Thanks. What's the standard article reference for "I have to instantiate Wrapper<T> for every possible type T. I'm not going to do that..." – Footcloth

@YSC Give me some time :P – Hertha

@Footcloth It's the standard quote from YSC eel.is/c++draft/temp.over – Inaptitude

@YSC Thanks. I have incorporated it into the answer. To be honest, I should study the template function related part of the standard quite a little bit more ... – Hertha

I believe Wrapper<T> is non-deduced context because of temp.deduct.type/8 and temp.deduct.type/12 – Footcloth

@Footcloth It's not a non-deduced context though, since deduction succeeds if you pass in a Wrapper<U>. – Ygerne

Answer 3

I'm not a language lawyer but I don't think that defining a using type = typename T::type; inside a class is, itself, usable as SFINAE to enable/disable a function receiving an object of that class.

If you want a solution, you can apply SFINAE to the Wrapper version as follows

template<class T>
auto test(Wrapper<T>, Wrapper<T>)
   -> decltype( T::type, void() )
 { }

This way, this test() function is enabled only for T types with a type type defined inside it.

In your version, is enabled for every T type but gives error when T is incompatible with Wrapper.

-- EDIT --

The OP precises and asks

My Wrapper has many more dependencies on T, it would be impractical to duplicate them all in a SFINAE expression. Isn't there a way to check if Wrapper itself can be instantiated?

As suggested by Holt, you can create a custom type traits to see if a type is a Wrapper<something> type; by example

template <typename>
struct is_wrapper : public std::false_type
 { };

template <typename T>
struct is_wrapper<Wrapper<T>> : public std::true_type
 { using type = T; };

Then you can modify the Wrapper version to receive a U type and check if U is a Wrapper<something> type

template <typename U>
std::enable_if_t<is_wrapper<U>{}> test (U, U)
 { using T = typename is_wrapper<U>::type; }

Observe that you can recover the original T type (if you need it) using the type definition inside the is_wrapper struct.

If you need a non-Wrapper version of test(), with this solution you have to explicity disable it when T is a Wrapper<something> type to avoid collision

template <typename T>
std::enable_if_t<!is_wrapper<T>{}> test(T, T)
 { }

Slenderize

My Wrapper has many more dependencies on T, it would be impractical to duplicate them all in a SFINAE expression. Isn't there a way to check if Wrapper<T> itself can be instantiated? Besides, would really like to know why it doesn't work. – Footcloth

@Footcloth - thinking on it but my first idea (using std::declval<Wrapper<T>>() instead T::type inside declval()) gives the same hard error of your case... About the "why?" question, sorry, I'm not an expert. – Slenderize

@Footcloth You need to hide Wrapper<T> in a template parameter and performs tests on this template parameter using a trait, e.g., is_wrapper... And you need to disable the other overloads when T is not a wrapper. – Inaptitude

@Inaptitude - do you mind if I add an example of your solution? Or do you prefer add an answer yourself? – Slenderize

@Slenderize Feel free to add the example, here is a non-full tested snippet: godbolt.org/z/Los-fJ – Inaptitude

@Footcloth - answer modified following the suggestion from Holt. – Slenderize