Template function lookup

Question

Consider this piece of code:

#include <iostream>
#include <vector>

template<typename A>
void foo(A& a) {
    std::cout << "the wrong foo" << std::endl;
}

template<typename A>
void do_stuff(A& a) {
    foo(a);
}

template<typename X>
void foo(std::vector<X>& a) {
    std::cout << "the right foo" << std::endl;
}

int main()
{
    std::vector<int> q;
    do_stuff(q);
}

Why is it calling the "wrong" foo? If the first declaration of foo is removed the right foo is called.

I am using gcc 4.6.3.

Update: If functions are declared in the following order, the right foo is called.

template<typename A> void do_stuff(A& a) { ... }
template<typename A> void foo(A& a) { ... }
template<typename X> void foo(std::vector<X>& a) { ... }

Answer 1

The observed behavior is correct, as foo(a) is a type dependent expression according to:

14.6.2.2 Type-dependent expressions                         [temp.dep.expr]

1) Except as described below, an expression is type-dependent if any
   subexpression is type-dependent.

2) this is type-dependent if the class type of the enclosing member
   function is dependent (14.6.2.1).

3) An id-expression is type-dependent if it contains

    — an identifier associated by name lookup with one or more declarations 
      declared with a dependent type,
    ...

and under 14.6.4 (Dependent name resoultion):

14.6.4.2 Candidate functions                              [temp.dep.candidate]

For a function call that depends on a template parameter, the candidate
functions are found using the usual lookup rules (3.4.1, 3.4.2, 3.4.3) except
that:

— For the part of the lookup using unqualified name lookup (3.4.1) or qualified
  name lookup (3.4.3), only function declarations from the template definition 
  context are found.
— For the part of the lookup using associated namespaces (3.4.2), only function
  declarations found in either the template definition context or the template
  instantiation context are found.

If the function name is an unqualified-id and the call would be ill-formed or
would find a better match had the lookup within the associated namespaces
considered all the function declarations with external linkage introduced in
those namespaces in all translation units, not just considering those
declarations found in the template definition and template instantiation
contexts, then the program has undefined behavior.

The "wrong" foo() is picked because that's the only one visible at the point of template definition, and the "right" foo() is not considered because it's not in a namespace associated with the types of the function arguments.

If you modify your code so that the "right" foo() would be in an associated namespace, it would be picked instead of the "wrong" foo(). (In this particular case, it's not allowed by the standard, so don't do the below, but with your own namespace / types this is how it should work)

#include <iostream>
#include <vector>

template<typename A> void foo(A& a)
{
    std::cout << "the wrong foo" << std::endl;
}

template<typename A>
void do_stuff(A& a) {
    foo(a);
}

namespace std { // evil, don't do this with namespace std!

template<typename X>
void foo(std::vector<X>& a) {
    std::cout << "the right foo" << std::endl;
}

}

int main()
{
    std::vector<int> q;
    do_stuff(q); // calls the "right" foo()
}

Answer 2

Within a template definition, name lookup for a non-dependent name (that is, one like foo that doesn't depend on the template parameters) is performed where the template is defined, not where it's instantiated. This is specified by the standard:

C++11 14.6.3 Non-dependent names used in a template definition are found using the usual name lookup and bound at the point they are used.

and illustrated by an example similar to yours:

void g(double);
void h();

template<class T> class Z {
public:
  void f() {
    g(1);           // calls g(double)
    h++;            // ill-formed: cannot increment function;
                    // this could be diagnosed either here or
                    // at the point of instantiation
  }
};

void g(int);        // not in scope at the point of the template
                    // definition, not considered for the call g(1)

Regarding your update: I believe that, with both foo declarations placed after do_stuff, the program should be ill-formed, and GCC is incorrect to (apparently) defer lookup until the point of instantiation when it fails at the point of use.

UPDATE: As noted in the comments, this behaviour is indeed incorrect, and was fixed in gcc-4.7.