Interaction between templates and overloads

Question

The output of the following code is TA, but I don't understand why.

#include <iostream>
#include <type_traits>

struct A {};

template<typename T>
void fun(T) {
    std::cout << "T";
}

template<typename T>
void caller(T t) {
    fun(A{});
    fun(t);
}

void fun(A) {
    std::cout << "A";
}

int main() {
    caller(A{});
}

My understanding of templates tells me the following:

• just before the body of main is parsed, the only function "in place" is the non-template overload of fun, the one printing A, because the templates fun and caller have not been used and, in turn, instantiated;
• only when the call to caller is parsed, is the template caller instantiated with T = A, which implies that caller calls fun with objects of the same type in the two cases;
• furthermore, since that type is A, I'd say that the non-template overload of fun is called in both cases.

However, the above is wrong, otherwise I would get AA (actually, also TT would surprise me less than TA).

I've also noted that moving the non-template overload before the definition of caller, the output becomes AA, so I can only make this conjecture:

• when the parser reads the line fun(A{}); the fun template is instantiated with T = A, even though the template caller is not being instatiated yet;
• then, when caller(A{}); is parsed, caller is instantiated;
• only at this point the second call to fun in the body of caller can be interpreted as a call with an argument of type A, but this time the non-template fun is already known to the compiler, hence it's chosen as a better match.

I don't know if the above makes any sense, though.

More predictably, if if I use the following template specialization

template<>
void fun<A>(A) {
    std::cout << "A";
}

instead of the non-template overload, then output is always AA, regardless of whether I put the specialization before or after caller's definition.

Answer 1

Just to add to Igor Tandetnik answer: if you delay instantiation by providing fake parameters, the overload resolution is delayed:

#include <iostream>
#include <type_traits>

struct A {};

template<typename T>
void fun(T) {
    std::cout << "T";
}

template<typename T, typename AA = A> // <<==== HERE
void caller(T t) {
    fun(AA{});
    fun(t);
}

void fun(A) {
    std::cout << "A";
}

int main() {
    caller(A{}); // Does AA
}

This is a common trick to delay resolution of otherwise template parameter-independent expressions, for example adding fake parameters to templates to prevent specializations from being full, for example:

template<typename T>
struct foo {};

template<>
struct foo<void> {}; // Instantiated immediately

template<typename T, int fake = 0>
struct bar {};

template<int fake>
struct bar<void, fake> {}; // Not instantiated until used

// Users of bar<T> almost never realize they use bar<T, 0>, you can even provide a wrapper without `int` parameter.

Sometimes you need to access template class member with this-> to force them being dependant too, etc.

Answer 2

fun(A{}); doesn't involve any template parameter-dependent expressions, and so the lookup and overload resolution occurs at the point of definition. At that point, only fun(T) is visible; fun(A) does not participate in overload resolution.

fun(t) call depends on T, and so the resolution is delayed to the point of instantiation. At that point, both fun(A) and fun(T) are visible, and fun(A) wins: non-templates are preferred over templates, other things equal.