implicit instantiation of undefined template '

When trying to offer functions for const and non-const template arguments in my library I came across a strange problem. The following source code is a minimal example phenomenon:

#include <iostream>


template<typename some_type>
struct some_meta_class;

template<>
struct some_meta_class<int>
{
    typedef void type;
};



template<typename some_type>
struct return_type
{
    typedef typename some_meta_class< some_type >::type test;

    typedef void type;
};



template<typename type>
typename return_type<type>::type foo( type & in )
{
    std::cout << "non-const" << std::endl;
}

template<typename type>
void foo( type const & in )
{
    std::cout << "const" << std::endl;
}


int main()
{
    int i;

    int const & ciref = i;
    foo(ciref);
}

I tried to implement a non-const version and a const version for foo but unfortunately this code won't compile on CLANG 3.0 and gcc 4.6.3.

main.cpp:18:22: error: implicit instantiation of undefined template 'some_meta_class'

So for some reason the compiler wants to use the non-const version of foo for a const int-reference. This obviously leads to the error above because there is no implementation for some_meta_class. The strange thing is, that if you do one of the following changes, the code compile well and works:

uncomment/remove the non-const version
uncomemnt/remove the typedef of return_type::test

This example is of course minimalistic and pure academic. In my library I came across this problem because the const and non-const version return different types. I managed this problem by using a helper class which is partially specialized.

But why does the example above result in such strange behaviour? Why doesn't the compiler want to use the non-const version where the const version is valid and and matches better?

The reason is the way function call resolution is performed, together with template argument deduction and substitution.

Firstly, name lookup is performed. This gives you two functions with a matching name foo().
Secondly, type deduction is performed: for each of the template functions with a matching name, the compiler tries to deduce the function template arguments which would yield a viable match. The error you get happens in this phase.
Thirdly, overload resolution enters the game. This is only after type deduction has been performed and the signatures of the viable functions for resolving the call have been determined, which makes sense: the compiler can meaningfully resolve your function call only after it has found out the exact signature of all the candidates.

The fact that you get an error related to the non-const overload is not because the compiler chooses it as a most viable candidate for resolving the call (that would be step 3), but because the compiler produces an error while instantiating its return type to determine its signature, during step 2.

It is not entirely obvious why this results in an error though, because one might expect that SFINAE applies (Substitution Failure Is Not An Error). To clarify this, we might consider a simpler example:

template<typename T> struct X { };

template<typename T> typename X<T>::type f(T&) { }  // 1
template<typename T> void f(T const&) { }           // 2

int main()
{
    int const i = 0;
    f(i); // Selects overload 2
}

In this example, SFINAE applies: during step 2, the compiler will deduce T for each of the two overloads above, and try to determine their signatures. In case of overload 1, this results in a substitution failure: X<const int> does not define any type (no typedef in X). However, due to SFINAE, the compiler simply discards it and finds that overload 2 is a viable match. Thus, it picks it.

Let's now change the example slightly in a way that mirrors your example:

template<typename T> struct X { };

template<typename Y>
struct R { typedef typename X<Y>::type type; };

// Notice the small change from X<T> into R<T>!
template<typename T> typename R<T>::type f(T&) { }  // 1
template<typename T> void f(T const&) { }           // 2

int main()
{
    int const i = 0;
    f(i); // ERROR! Cannot instantiate R<int const>
}

What has changed is that overload 1 no longer returns X<T>::type, but rather R<T>::type. This is in turn the same as X<T>::type because of the typedef declaration in R, so one might expect it to yield the same result. However, in this case you get a compilation error. Why?

The Standard has the answer (Paragraph 14.8.3/8):

If a substitution results in an invalid type or expression, type deduction fails. An invalid type or expression is one that would be ill-formed if written using the substituted arguments. [...] Only invalid types and expressions in the immediate context of the function type and its template parameter types can result in a deduction failure.

Clearly, the second example (as well as yours) generates an error in a nested context, so SFINAE does not apply. I believe this answers your question.

By the way, it is interesting to notice, that this has changed since C++03, which more generally stated (Paragraph 14.8.2/2):

[...] If a substitution in a template parameter or in the function type of the function template results in an invalid type, type deduction fails. [...]

If you are curious about the reasons why things have changed, this paper might give you an idea.