How can I get my templated function to see other global methods defined later?

Question

(Oktalist gave a great answer below, check it out and the comments under it, to help demonstrate everything we've discussed, I've added a full, compiling solution at the bottom of my question that demonstrates everything discussed.)

I have a collection of namespace global methods and templated methods like the following:

namespace PrettyPrint
{
    String to_string(bool val);
    String to_string(char val);
    String to_string(int val);
    String to_string(uint val);
    // ETC...

    template <typename T> String to_string(const T* val)
    {
        if (! val) return U("NULL");
        return String().copy_formatted("(%p)-> %S", (const void*)val, to_string(*val).uchars());
    }

    // ... and more templates to help with containers and such
}

The "String" type is not the C++ string, it's a special class derived off of IBM's ICU library, but not really relevant for this question. Point is, I have a bunch of namespace global methods called to_string and also some templated functions that override them. So far, so good, everything works great. But, now I have another header where I have something like the following defined:

namespace User 
{
    struct Service {
        int code;
        String name;
    }
    //...
}
namespace PrettyPrint
{
    String to_string(const User::Service& val) { return val.name; }
}

So, now I have defined some other type somewhere else, and I've also defined another to_string override in my PrettyPrint namespace to indicate how to convert my new type to a String. Toss both headers into a file, something like this:

#include <the to_string and templates header>
#include <the User::Service header>

main() {
    User::Service s = {1, U("foo")};
    User::Service *p = &s;
    PrettyPrint::to_string(s);
    PrettyPrint::to_string(p);
}

(Yes, the to_string methods should actually be returning a value somewhere, not the point.) The point is that the second call gives a compiler error (gcc, btw) saying that in the templated to_string method there is no matching function for call to 'to_string(const User::Service&)', which of-course exactly matches my method that is defined and included. If I reverse the #include ordering it works just fine.

So, I surmise that the template is only looking at methods defined ahead of it. Is there any fix for this? Given the scope of my project and number of complicated #include's, simply saying "always make sure they come in the right order" is not a tractable solution, and would introduce too much complicated fragility in the code. The base to_string defintions is one of those files that will tend to get included high up in a lot of places, so making sure that any other random type definitions that happen to include a to_string override come first just isn't going to work.

The other solution I have that works in some places is that I've defined a Printable interface in the base file:

namespace PrettyPrint
{
    class Printable {
    public:
        virtual String pretty_print_to_string() const = 0;
    }

    String to_string(const Printable& obj) { return obj.pretty_print_to_string(); }
}

That definition comes before the template methods in the same file. So, that works great for classes where I can simply add in that interface and implement it. Short of any great solutions here, I'm going to simply try to always use that, but there are places where it is not convenient and I'd also just like to understand if there is any way to get the method overloading solution to work without being dependent on #include ordering to work.

Anyhow, what do you all think of these options? Is there an approach that I haven't thought of that might work nicely?

Solution inspired from answer Oktalist gave

This code actually does compile so you can copy it off and play with it, I think I've captured all the relevant use cases along with what works and what doesn't and why.

#include <iostream>

using namespace std;

namespace PrettyPrint
{
    void sample(int val) { cout << "PrettyPrint::sample(int)\n"; }
    void sample(bool val) { cout << "PrettyPrint::sample(bool)\n"; }
    template<typename T> void sample(T* val) { cout << "PrettyPrint::sample(pointer); -> "; sample(*val); }
}

namespace User
{
    struct Foo {
        int i;
        bool b;
    };

    void sample(const Foo& val) {
        //below doesn't work un-qualified, tries to convert the int (val.i) into a Foo to make a recursive call.
        //meaning, it matches the User namespace version first
        //sample(val.i); doesn't work, tries to call User::sample(const Foo&)

        cout << "User::sample(const Foo&); -> {\n";
        cout << '\t'; PrettyPrint::sample(val.i); //now it works
        cout << '\t'; PrettyPrint::sample(val.b);
        cout << "}\n";
    }
}

namespace Other
{
    void test(User::Foo* fubar) {
        cout << "In Other::test(User::Foo*):\n";
        //PrettyPrint::sample(*fubar); //doesn't work, can't find sample(const User::Foo&) in PrettyPrint
        PrettyPrint::sample(fubar); //works, by argument-dependent lookup (ADL) from the template call
        sample(*fubar); //works, finds the method by ADL
        //sample(fubar); //doesn't work, only sees User::sample() and can't instantiate a Foo& from a Foo*
    }

    void test2(User::Foo* happy) {
        using PrettyPrint::sample; //now both work! this is the way to do it.
        cout << "In Other::test2(User::Foo*):\n";
        sample(*happy);
        sample(happy);
    }
}

int main() {
    int i=0, *p = &i;
    bool b=false;
    User::Foo f = {1, true}, *pf = &f;

    //sample(i);  <-- doesn't work, PrettyPrint namespace is not visible here, nor is User for that matter.
    PrettyPrint::sample(i); //now it works
    //PrettyPrint::sample(f); //doesn't work, forces search in PrettyPrint only, doesn't see User override.

    using namespace PrettyPrint;  // now they all work.
    sample(p);
    sample(b);

    sample(f);
    sample(pf);

    Other::test(pf);
    Other::test2(pf);

    return 0;
}

This results in the following output:

PrettyPrint::sample(int)
PrettyPrint::sample(pointer); -> PrettyPrint::sample(int)
PrettyPrint::sample(bool)
User::sample(const Foo&); -> {
    PrettyPrint::sample(int)
    PrettyPrint::sample(bool)
}
PrettyPrint::sample(pointer); -> User::sample(const Foo&); -> {
    PrettyPrint::sample(int)
    PrettyPrint::sample(bool)
}
In Other::test(User::Foo*):
PrettyPrint::sample(pointer); -> User::sample(const Foo&); -> {
    PrettyPrint::sample(int)
    PrettyPrint::sample(bool)
}
User::sample(const Foo&); -> {
    PrettyPrint::sample(int)
    PrettyPrint::sample(bool)
}
In Other::test2(User::Foo*):
User::sample(const Foo&); -> {
    PrettyPrint::sample(int)
    PrettyPrint::sample(bool)
}
PrettyPrint::sample(pointer); -> User::sample(const Foo&); -> {
    PrettyPrint::sample(int)
    PrettyPrint::sample(bool)
}

Answer 1

During the first phase of two phase lookup, when the template is defined, unqualified lookup looks for dependent and non-dependent names in the immediate enclosing namespace of the template and finds only those to_string overloads which appear before the template definition.

During the second phase of two phase lookup, when the template is instantiated, argument-dependent lookup looks for dependent names in the namespaces associated with any class types passed as arguments to the named functions. But because your to_string(const User::Service&) overload is in the PrettyPrint namespace, it will not be found by argument-dependent lookup.

Move your to_string(const User::Service&) overload into the User namespace to make use of argument-dependent lookup, which will find any overloads declared at the point of template instantiation, including any declared after the point of template definition.

See also http://clang.llvm.org/compatibility.html#dep_lookup

Answer 2

What the compiler does when instantiating a template is essentially expanding it (more or less like a macro), and compiling the result on the fly. To do that, any functions (or other stuff) mentioned must be visible at that point. So make sure any declarations used are mentioned beforehand (in the same header file, most probably).

Answer 3

I don't entirely understand what's going on here, but it appears that if you want the later defined methods to be used, then they need to be template specializations. The compiler won't see function overrides later in the program.

First off, we reproduce the problem. I do so with this program in gcc-4.8.2:

// INCLUDE FILE 1
template <class T> void to_string (T const * a) {
  to_string (*a);
}
// INCLUDE FILE 1 END

// INCLUDE FILE 2
// How do we make this program work when this is necessarily declared after to_string(T const * A)?
void to_string(int const & a) {
  return;
}
// INCLUDE FILE 2 END

int main (void) {
  int i = 5;
  int * p = &i;

  to_string(i);
  to_string(p);
  to_string(&i);

  return 0;
}

In order to get it working, we need to do this...

// INCLUDE FILE 1
// The pointer version needs something to call...
template <class T> void to_string (T const & a);


// This can't be T const * a.  Try it.  So weird...
template <class T> void to_string (T * a) {
  foo (*a);
}
// INCLUDE FILE 1 END

// INCLUDE FILE 2
// This has to specialize template<> void to_string.  If we just override, we get a linking error.
template<> void to_string <int> (int const & a) {
  return;
}
// INCLUDE FILE 2 END

int main (void) {
  int i = 5;
  int * p = &i;

  to_string(i);
  to_string(p);
  to_string(&i);

  return 0;
}