How does the compiler find the template function X::max(T const&, T const&) through ADL in the code below?

Question

A quote from the Standard is appreciated.

#include <iostream>

namespace X {
    class A {};
}

template <typename T>
inline T const& max(T const& a, T const& b, T const& c)
{
    return max(max(a, b), c);
}

inline X::A const& max(X::A const& a, X::A const& b)
{
    std::cout << "non-template" << '\n';
    return a;
}

int main()
{
    X::A a, b, c;
    max(a, b, c);
}

namespace X {
    template <typename T>
    inline T const& max(T const& a, T const& b)
    {
        std::cout << "template" << '\n';
        return a;
    }
}

Live example

TemplateRex · Accepted Answer · 2014-07-02T14:29:41.517

Standardese

The call to max() in the example entails a dependent name because its arguments depend on the template parameter T. Two-phase name lookup for such dependent names is defined in the Standard as follows:

14.6.4.2 Candidate functions [temp.dep.candidate]

1 For a function call where the postﬁx-expression is a dependent name, the candidate functions are found using the usual lookup rules (3.4.1, 3.4.2) except that:

— For the part of the lookup using unqualiﬁed name lookup (3.4.1), only function declarations from the template deﬁnition context are found.

— For the part of the lookup using associated namespaces (3.4.2), only function declarations found in either the template deﬁnition context or the template instantiation context are found.

Unqualified lookup is defined by

3.4.1 Unqualiﬁed name lookup [basic.lookup.unqual]

1 In all the cases listed in 3.4.1, the scopes are searched for a declaration in the order listed in each of the respective categories; name lookup ends as soon as a declaration is found for the name. If no declaration is found, the program is ill-formed.

and argument-dependent lookup (ADL) as

3.4.2 Argument-dependent name lookup [basic.lookup.argdep]

1 When the postfix-expression in a function call (5.2.2) is an unqualified-id, other namespaces not considered during the usual unqualified lookup (3.4.1) may be searched, and in those namespaces, namespace-scope friend function or function template declarations (11.3) not otherwise visible may be found. These modifications to the search depend on the types of the arguments (and for template template arguments, the namespace of the template argument).

Why your code fails

In your example, unqualified lookup and ADL both do not find any overload at the point of definition because the compiler has not seen any two-argument max() yet. ADL also applies at the point of instantiation, and at that time, the compiler has seen the two-argument template max(T, T) which is the only one that can be called. (the difference is that template instantion happens after the entire translation unit has been parsed).

Better code

You should fix your code by putting the non-template max(X::A, X::A) overload inside the namespace X and move the template max(T, T) out of it.

#include <iostream>

// generic code

template <typename T>
inline T const& max(T const& a, T const& b)
{
    std::cout << "template" << '\n';
    return a;
}

template <typename T>
inline T const& max(T const& a, T const& b, T const& c)
{
    using ::max; // fallback if no user-defined max
    return max(max(a, b), c);
}

// X specific code

namespace X {

class A {};

inline X::A const& max(X::A const& a, X::A const& b)
{
    std::cout << "non-template" << '\n';
    return a;
}

} // namespace X

int main()
{
    X::A a, b, c;
    max(a, b, c);
}

Live-Example that prints "non-template" twice.

Btw, compilers that do not implement two-phase lookup correctly may end up calling the `non-template` version of `max` instead (for instance, Visual C++). — ComicSansMS, Jul 02 '14 at 14:18
@ComicSansMS on Win platforms, there might even be a `max` macro that interferes with it so that you have to put extra parens `(max)(a,b)` to the call. — TemplateRex, Jul 02 '14 at 14:22
And `(max)` blocks ADL. (one of the handful of places where `()` in an expression changes the meaning of the expression) — Yakk - Adam Nevraumont, Jul 02 '14 at 14:26
@TemplateRex `and at that time, the compiler has seen the two-argument template max(T, T)` - that's exactly what I don't understand. — Wake up Brazil, Jul 02 '14 at 14:26
@WakeupBrazil the compiler parses the entire translation unit before instantiating any template. This is why the 2nd ADL finds the template max and the unqualified and 1st ADL don't. UPdated. — TemplateRex, Jul 02 '14 at 14:28
@TemplateRex That may be the answer I'm looking for. Do you know of any quote in the Standard supporting this? — Wake up Brazil, Jul 02 '14 at 14:30
@Yakk it's ironic that guarding against Windows max macros would in theory block ADL, but since ADL is broken anyway.. ;-) — TemplateRex, Jul 02 '14 at 14:33
@TemplateRex The comment by Vandervood and Josuttis you posted here ( http://stackoverflow.com/q/23030403/2548699 ) seems to indicate that only noninline templates are instantiated at the end of the translation unit. In my example above, all the template functions are inline. Could you comment on this? — Wake up Brazil, Jul 02 '14 at 23:31
@WakeupBrazil if you look at Casey's answer in that Q&A, you see that the end of the translation is added as a point of instantiation (POI), and that templates (regardless of whether they are explicitly inline or not) can have multiple POI. You just need to be careful about ODR-violations. — TemplateRex, Jul 03 '14 at 10:09

How does the compiler find the template function X::max(T const&, T const&) through ADL in the code below?

1 Answers1

Standardese

Why your code fails

Better code