Confusing function lookup with templates in C++

Question

Starting with the following (using gcc version 4.0.1):

namespace name {
   template <typename T>
   void foo(const T& t) {
      bar(t);
   }

   template <typename T>
   void bar(const T& t) {
      baz(t);
   }

   void baz(int) {
      std::cout << "baz(int)\n";
   }
}

If I add (in the global namespace)

struct test {};
void bar(const test&) {
   std::cout << "bar(const test&)\n";
}

then, as I expected,

name::foo(test()); // produces "bar(const test&)"

But if I just add

void bar(const double&) {
   std::cout << "bar(const double&)\n";
}

it can't seem to find this overload:

name::foo(5.0) // produces "baz(int)"

What's more,

typedef std::vector<int> Vec;
void bar(const Vec&) {
   std::cout << "bar(const Vec&)\n";
}

doesn't appear either, so

name::foo(Vec());

gives a compiler error

error: cannot convert ‘const std::vector<int, std::allocator<int> >’ to ‘int’ for argument ‘1’ to ‘void name::baz(int)’

Is this how the lookup is supposed to work? (Note: if I remove the namespace name, then everything works as I expected.)

How can I modify this example so that any overload for bar is considered? (I thought that overloads were supposed to be considered before templates?)

Answer 1

I assume you added the double version to the global namespace too, and you call foo from main after everything is defined. So this is basically two phase name lookup. Looking up an unqualified function name that is dependent because an argument in the call is dependent (on its type) is done in two phases.

The first phase does a unqualified and argument dependent lookup in the definition context. It then freezes the result, and using the instantiation context (the sum of the declarations at the point of instantiation) does a second argument dependent lookup only. No unqualified lookup is done anymore. So for your example it means:

• The call bar(t) within foo<test> looks up bar using argument dependent lookup at the instantiation context (it doesn't find it using unqualified lookup, because foo is declared above the bar template). Depending on whether you define the global bar before or after the foo template, it will find the global bar declaration using argument dependent lookup already in the first phase (it's defined in test's namespace). Then the call in main will instantiate foo<test> and it will possible find bar in this phase (if you declared it after you declared the template).

• The call bar(t) within foo<int> doesn't do argument dependent lookup (or rather, the result for the lookup is an empty declaration set), because int is a fundamental type. So, unqualified lookup at the definition context will find nothing either, because the matching bar template is declared after the foo template. The call would be ill-formed, and the standard says about this situation at 14.6.4.2/1

  If the call would be ill-formed [...] then the program has undefined behavior.

  You should therefor consider this as a "i did a dirty thing and the compiler chose not to slap me" case, i think :)

• The call bar(t) within foo<Vec> will do the lookups again, and will look for bar in std:: (because that's where std::vector is defined). It doesn't find a bar there, neither in the definition context. So it decides to go by undefined behavior again, and uses the bar template, and which in itself again does undefined behavior by using the baz declared after it and which cannot be found by neither ADL nor unqualified lookup from the definition context.

  If the vector were a vector<test>, then lookup for bar would be done at global scope too, because argument dependent lookup will not only use the argument type directly, but also the type of the template arguments in them, if there are any.

---

If you use GCC, then don't rely entirely on its behavior. In the following code, it claims the call is ambiguous, although the code is perfectly fine - the f in afake should not be a candidate.

namespace aname {
  struct A { };
  void f(A) { }
}

namespace afake {
  template<typename T>
  void g(T t) { f(t); }
  void f(aname::A) { }
}

int main() { aname::A a; afake::g(a); }

If you want to test your snippets against conformance, best use the comeau online compiler with the strict settings.

Answer 2

The rule for looking up name is that if the name is unqualified, the parameter's namespace will be used to search for the function.

name::foo(test()); works because in foo you have call bar(test()); basically and test's namespace is used for searching bar. In this case, global namespace.

name::foo(Vec()); this wont work as Vec is a typedef not a class or struct.

See C++ standard for function name lookup rules.

Answer 3

Do a google on "c++ koenig lookup"

That should give you enough information on the template lookup rules.

Herb Sutter has a good article on the subject:
http://www.gotw.ca/gotw/030.htm

Answer 4

I can confirm the behaviour you are seeing on my system and I believe it's correct.

Looks like the overload resolution is just looking in the namespaces of it's arguments so the version of bar that takes a test works because test is in the global namespace and so the compiler checks there for a version of bar which , as you rightly pointed out, is prioritised over the templated version.

For the Vec version the important namespace is std. If you put a version of bar in std you'll find it picks it up.

The double version doesn't work because the global namespace is not used for the lookup since double is a built-in type and not specially associated with the global namespace in any way.

Answer 5

The following code compiles fine for me using VS 2005 Professional Edition:

#include <iostream>
#include <vector>

using std::cout;


typedef std::vector<int> Vec;

namespace name {
    template <typename T>
    void foo(const T& t) {
        bar(t);
    }

    template <typename T>
    void bar(const T& t) {
        baz(t);
    }

    void baz(int) {
        std::cout << "baz(int)\n";
    }   

    void bar(const Vec&) {
        std::cout << "bar(const Vec&)\n";
    }
}


int main()
{
    name::foo(Vec());
    return 0;
}

Please post your original code so that we can find out what's wrong.

Answer 6

The following program works fine for me on gcc 4.3 and gcc 4.1 (the only two compilers I have on hand:

#include <iostream>
#include <vector>

namespace name {
   template <typename T>
   void foo(const T& t) {
      bar(t);
   }

   template <typename T>
   void bar(const T& t) {
      baz(t);
   }

   void baz(int) {
      std::cout << "baz(int)\n";
   }

   struct test {};
    void bar(const test&) {
       std::cout << "bar(const test&)\n";
    }

    void bar(const double&) {
       std::cout << "bar(const double&)\n";
    }

    typedef std::vector<int> Vec;
    void bar(const Vec&) {
       std::cout << "bar(const Vec&)\n";
    }
}

int main()
{
    name::foo(name::test());
    name::foo(5.0);
    name::foo(name::Vec());
}

Producing:

bar(const test&)
bar(const double&)
bar(const Vec&)

What compiler are you using?