SFINAE works with deduction but fails with substitution

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.

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)
 { }

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.