Overload resolution resolves to a function not visible yet

Question

This is kind of a follow on to this question.

#include <iostream>

struct type1 {};
struct type2 {};

void foo(type1 x)
{
  std::cout << "foo(type1)" << std::endl;
}

template<typename T>
void bar() {
  foo(T());
}

int main()
{
  bar<type1>();
  bar<type2>();
  return 0;
}

void foo(type2 x)
{
  std::cout << "foo(type2)" << std::endl;
}

In the above code foo(type2) is not visible at the time of instantiation of bar<type2> in main. And yet the code compiles and produces the following output :

foo(type1)
foo(type2)

How does the compiler know that foo(type2) is available when instantiating bar<type2> in main?

EDIT : I am trying to understand more about how overload resolution during template instantiation works. Consider the code below :

#include <iostream>

struct type1 {};
struct type2 {};
struct type3 {
  operator type2() { return type2(); }
};

void foo(type1 x)
{
  std::cout << "foo(type1)" << std::endl;
}

void foo(type2 x)
{
  std::cout << "foo(type2)" << std::endl;
}

int main()
{
  foo(type3());
  return 0;
}

void foo(type3 x)
{
  std::cout << "foo(type3)" << std::endl;
}

The output is

foo(type2)

Even though a closer match foo(type3) is available, the call foo(type3()) resolves to foo(type2) because that was the only candidate that has been parsed by the compiler until that point. Now consider the following code :

#include <iostream>

struct type1 {};
struct type2 {};
struct type3 {
  operator type2() { return type2(); }
};

void foo(type2 x)
{
  std::cout << "foo(type2)" << std::endl;
}

template<typename T>
void bar() {
  foo(T());
}

int main()
{
  bar<type3>();
  return 0;
}

void foo(type3 x)
{
  std::cout << "foo(type3)" << std::endl;
}

The output is

foo(type3)

That is, at the point of the call bar<type3>(), even though only foo(type2) is visible, the compiler still picks foo(type3) that comes later because that is a closer match.

Answer 1

Any symbol left without a definition is to be replaced during the linking process, since the function foo(type2) could've been provided in another file.

The compiler is to say whether the function needed has been defined by the end of the entire process, when no further substitution can be applied.

In order to clarify the understanding, you must be aware of the steps required to compile, say, a common C program:

• first, you expand all the macros on your code;

• then your code is validated according to the language syntax, so that it can be converted into assembly language -- the compilation process itself; during this step, every symbol found without a definition is annotated in a table with the entries (symbol, definition), that shall be completed later, allowing your program to be constructed properly;

• next, your code compiled into assembly will be converted to machine language, i.e., the objects will be created;

• finally, you need to link your already executable objects, in order to solve any dependencies on symbol definitions; this last step checks your objects for undefined symbols, adding definitions from other modules or from libraries, thus, completing the program.

If any symbol was not correctly "linked" to its definition, the compiler will point out an error in your program -- the classic undefined reference to....

Considering the code you've posted, the process would be executed until it reaches the compiler. The compiler would traverse the code, notice the definition of type1, type2, foo(type1 x), and bar<T>().

struct type1 {};
struct type2 {};

When it'd reached the main, it would find the call for bar<type1>();, and would call foo(type1()), which is already known, and can be used properly.

void foo(type1 x) {
    std::cout << "foo(type1)" << std::endl;
}

template<typename T>
void bar() {
    foo(T());
}

int main() {

    bar<type1>();
    bar<type2>();
    return 0;

}

Once it'd reached the next call, bar<type2>();, it would try to call foo(type2()), but no such definition would be available for usage, so it would relate this call as an unknown symbol, that must be replaced by a definition in the later processes.

After the compiler runs through the main, it reaches a new definition, that is exactly the one lacking definition on the "translation table" being created.

void foo(type2 x) {
    std::cout << "foo(type2)" << std::endl;
}

So, in the next step, the compilation is able to replace the symbol with its respective definition, and the program compiles correctly.

Regards!

Answer 2

The answer is found via argument-dependent name lookup (ADL) (which is also mentioned in the linked question). foo(T()); has two lookups. First at template definition time, any functions defined at the point of definition are included in the overload set. This means when the compiler sees foo(T()); inside of bar, it adds only void foo(type1 x) to the overload set. However there is a second lookup that is performed, called ADL. At template instantiation time, i.e. bar<type2>(); it looks for a foo in the same namespace as the argument which is provided, which in this case is type2. Since type2 is in the global namespace, it looks for a foo that takes a type2 in the global namespace and finds it, and resolves the call. If you are looking for info from the standard, see 14.6.4.2 Candidate functions.

Try the following and watch the code fail. This is because it cannot find foo in the same namespace as a::type1.

#include <iostream>

namespace a
{
  struct type1 {};
}

template<typename T>
void bar() {
  foo(T());
}

int main()
{
  bar<a::type1>();
  return 0;
}

void foo(a::type1 x)
{
  std::cout << "foo(a::type1)" << std::endl;
}