Unexpected overload resolution with default function template parameter

Question

I am experiencing an overload resolution behaviour that seems very unexpected. The following code is rejected with an ambiguity error by both gcc and clang:

template <typename T>
struct A
{
    typedef T key_type;
};

template <typename T>
void foo(A<T> rng, T val);

template <typename T, typename U = T>
void foo(T, typename U::key_type);

int main()
{
    A<int> i;
    foo(i, 0);
}

The error is:

test.cpp:16:5: error: call to 'foo' is ambiguous
    foo(i, 0);
    ^~~
test.cpp:8:6: note: candidate function [with T = int]
void foo(A<T> rng, T val);
     ^
test.cpp:11:6: note: candidate function [with T = A<int>, U = A<int>]
void foo(T, typename U::key_type);
     ^

I would expect both to be exact matches but the first overload to win in partial ordering, since in the first parameter A<T> is more specialized than T.

What blows my mind is that if I change the second signature to:

template <typename T, typename U = T>
void foo(T, typename T::key_type);

both gcc and clang now accept the code, and choose the first overload as I would originally expect.

I don't see how this change can make a difference in behaviour: all I did was substitute the use of a template parameter which was neither explicitly specified nor deduced (U) with its default value (T).

Then again, the behaviour before the change is unexpected to begin with, so maybe I am missing something.

Could someone explain:

1. why the first case is ambiguous; and
2. why the change I made resolves the ambiguity?

In case it's relevant, the compiler versions I tested with are gcc 4.8.0 and a recent trunk build of clang.

Answer 1

The question is whether there is a substitution phase of the deduced template arguments into the parameter list after argument deduction. This phase is where default arguments will be used for template parameters that haven't yet been deduced.

The question for what deduction contexts this extra step is done and for what not is subject of an active core issue, http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#697 .

If you do that extra substitution step, you need to also instantiate templates (otherwise the substitution step would make not much sense on its own). You could also just only pick the default arguments, without doing the substitution, but in the Standard these two things go together, so as an implementor I would not choose that path.

Partial ordering is largely independent of the context for which partial ordering is being done (some context dependent things are considered - for example, function parameters that do not have explicit call arguments are ignored). It is also independent on whether or not a template parameter had an explicit template argument passed or not (so if you had given a value to U, partial ordering would not have "remembered" it.

Clang and GCC do not do the substitution step and don't make use of template default arguments. So when the T is compared against U::key_type to figure out U, they say "huh, a non-deduced context. we will say 'success, nothing to mismatch!' for this parameter". The same happens when it compares T against T::key_type. When it compares the other direction along, WhatEver::key_type against T, T can too deduce that dependent type. So for the second parameter, in both your tries both templates are at least as specialized as each other.

However the important difference is that after the deduction, there must be values for all the parameters used in the parameter type list.

In most cases, all template parameters must have values in order for deduction to succeed, but for partial ordering purposes a template parameter may remain without a value provided it is not used in the types being used for partial ordering. [ Note: A template parameter used in a non-deduced context is considered used. — end note ]

In your second try, T was deduced by the first parameter, so nothing bad happened after the comparisons of the parameter/argument types were done. In the first try, U was left undeduced, and so the first template was not considered "more specialized" than the second in the aftermath.