Partial ordering of function templates - ambiguous call

Question

Consider this piece of C++11 code:

#include <iostream>
#include <cstddef>

template<typename T> void f(T, const char*) //#1
{ 
    std::cout << "f(T, const char*)\n"; 
}

template<std::size_t N> void f(int, const char(&)[N]) //#2
{ 
    std::cout << "f(int, const char (&)[N])\n"; 
}

int main()
{
    f(7, "ab");
}

Alright, so... which overload is chosen? Before spilling the beans with compiler output, let's try to reason about this.

(All references to sections are for the final standard document for C++11, ISO/IEC 14882:2011.)

T from #1 is deduced to int, N from #2 is deduced to 3, both specializations are candidates, both are viable, so far so good. Which one is best?

First, the implicit conversions needed to match function arguments with function parameters are considered. For the first argument, no conversion is needed in either case (identity conversion), int everywhere, so the two functions are equally good. For the second one, the argument type is const char[3], and the two conversions are:

• for #1, array-to-pointer conversion, category lvalue transformation, according to [13.3.3.1.1]; this conversion category is ignored when comparing conversion sequences according to [13.3.3.2], so this is basically the same as identity conversion for this purpose;
• for #2, the parameter is of reference type and binds directly to the argument, so, according to [13.3.3.1.4], this is again identity conversion.

Again, no luck: the two functions are still equally good. Both being template specializations, we now have to see which function template, if any, is more specialized ([14.5.6.2] and [14.8.2.4]).

EDIT 3: The description below is close, but not quite accurate. See my answer for what I believe to be the correct description of the process.

• Template argument deduction with #1 as parameter and #2 as argument: we invent a value M to substitute for N, T deduced as int, const char* as parameter can be initialized from an argument of type char[M], everything's fine. As far as I can tell, #2 is at least as specialized as #1 for all types involved.
• Template argument deduction with #2 as parameter and #1 as argument: we invent a type U to substitute for T, a parameter of type int cannot be initialized from an argument of type U (unrelated types), a parameter of type char[N] cannot be initialized from an argument of type const char*, and the value of the non-type parameter N cannot be deduced from the arguments, so... everything fails. As far as I can tell, #1 is not at least as specialized as #2 for all types involved.

EDIT 1: The above has been edited based on comments from Columbo and dyp, to reflect the fact that references are removed before attempting template argument deduction in this case.

EDIT 2: Based on info from hvd, top level cv-qualifiers are also removed. In this case, it means const char[N] becomes char[N], because cv-qualifiers on array elements apply to the array itself as well (an array of const is also a const array, so to speak); this wasn't obvious at all in the C++11 standard, but has been clarified for C++14.

Based on the above, I'd say partial ordering of function templates should choose #2 as more specialized, and the call should resolve to it with no ambiguity.

Now, back to the harsh reality. Both GCC 4.9.1 and Clang 3.5.0, with the following options

-Wall -Wextra -std=c++11 -pedantic 

reject the call as ambiguous, with similar error messages. The error from Clang is:

prog.cc:16:2: error: call to 'f' is ambiguous
    f(7, "ab");
    ^
prog.cc:4:27: note: candidate function [with T = int] 
template<typename T> void f(T, const char*) //#1 
                         ^
prog.cc:9:30: note: candidate function [with N = 3] 
template<std::size_t N> void f(int, const char(&)[N]) //#2 
                            ^

Visual C++ 2013's IntelliSense (based on the EDG compiler, as far as I know) also flags the call as ambiguous. Funnily enough, the VC++ compiler goes ahead and compiles the code with no errors, choosing #2. (Yay! It agrees with me, so it must be right.)

The obvious question for the experts is, why is the call ambiguous? What am I missing (in the partial ordering area, I would guess)?

Answer 1

I'm posting the details of my current understanding of the issue as an answer. I'm not sure it will be the final word on this, but it could serve as a basis for further discussion if needed. The comments from dyp, hvd and Columbo have been essential for finding the various bits of information referenced below.

As I suspected, the problem is with the rules for partial ordering of function templates. Section [14.8.2.4] (Deducing template arguments during partial ordering) says that, after the preliminary transformations that remove references and cv-qualifiers, type deduction is done as described in [14.8.2.5] (Deducing template arguments from a type). That section is different from the one that refers to function calls - that would be [14.8.2.1] (Deducing template arguments from a function call).

When template parameters are deduced from function argument types, there are a few special cases that are allowed; for example, a template parameter T used in a function parameter of type T* can be deduced when the function argument is T[i], because the array-to-pointer conversion is allowed in this case. However, this is not the deduction process that's used during partial ordering, even though we're still talking about functions.

I guess the easy way to think about the rules for template argument deduction during partial ordering is to say they're the same rules as for deducing template arguments when matching class template specializations.

Clear as mud? Perhaps a couple of examples will help.

This works, because it uses the rules for deducing template arguments from a function call:

#include <iostream>
#include <type_traits>

template<typename T> void f(T*)
{
    std::cout << std::is_same<T, int>::value << '\n';
}

int main()
{
    int a[3];
    f(a);
}

and prints 1.

This doesn't, because it uses the rules for deducing template arguments from a type:

#include <iostream>

template<typename T> struct A;

template<typename T> struct A<T*>
{
    static void f() { std::cout << "specialization\n"; }
};

int main()
{
    A<int[3]>::f();
}

and the error from Clang is

error: implicit instantiation of undefined template 'A<int [3]>'

The specialization cannot be used, because T* and int[3] don't match in this case, so the compiler tries to instantiate the primary template.

It's this second kind of deduction that's used during partial ordering.

---

Let's get back to our function template declarations:

template<typename T> void f(T, const char*); //#1
template<std::size_t N> void f(int, const char(&)[N]); //#2

My description of the process for partial ordering becomes:

• Template argument deduction with #1 as parameter and #2 as argument: we invent a value M to substitute for N, T is deduced as int, but a parameter of type const char* does not match an argument of type char[M], so #2 is not at least as specialized as #1 for the second pair of types.
• Template argument deduction with #2 as parameter and #1 as argument: we invent a type U to substitute for T, int and U do not match (different types), a parameter of type char[N] does not match an argument of type const char*, and the value of the non-type template parameter N cannot be deduced from the arguments, so #1 is not at least as specialized as #2 for either pair of types.

Since, in order to be chosen, a template needs to be at least as specialized as the other for all types, it follows that neither template is more specialized than the other and the call is ambiguous.

---

The explanation above goes somewhat against the description of a similar problem in Core Language Active Issue 1610 (link provided by hvd).

The example in there is:

template<class C> void foo(const C* val) {}
template<int N> void foo(const char (&t)[N]) {}

The author argues that, intuitively, the second template should be chosen as more specialized, and that this doesn't currently happen (neither template is more specialized than the other).

He then explains that the reason is the removal of the const qualifier from const char[N], yielding char[N], which causes deduction to fail with const C* as parameter.

However, based on my current understanding, deduction would fail in this case, const or no const. This is confirmed by the current implementations in Clang and GCC: if we remove the const qualifier from the parameters of both function templates and call foo() with a char[3] argument, the call is still ambiguous. Arrays and pointers simply don't match according to the current rules during partial ordering.

Having said that, I'm not a member of the committee, so there may be more to this than I currently understand.

---

Update: I've recently stumbled upon another Core active issue that goes back to 2003: issue 402.

The example in there is equivalent to the one in 1610. The comments on the issue make it clear that the two overloads are unordered according to the partial ordering algorithm as it stands, precisely because of the lack of array-to-pointer decay rules during partial ordering.

The last comment is:

There was some sentiment that it would be desirable to have this case ordered, but we don't think it's worth spending the time to work on it now. If we look at some larger partial ordering changes at some point, we will consider this again.

Thus, I'm pretty confident that the interpretation I gave above is correct.

Answer 2

Initially, I thought the problem with you code is that you were not accounting for function type adjustment. Function type adjustment causes an array with bounds to be interpreted as a pointer to the type. I tried to find the solution to your problem by asking the compiler what it is seeing statically via templates, but instead I get more interesting results:

#include <iostream>
#include <type_traits>

template<typename T, std::size_t N>
void is_same( const T* _left, const char(&_right)[N] )
{
 typedef decltype(_left) LeftT;
 typedef decltype(_right) RightT;

 std::cout << std::is_same<LeftT,const char*>::value << std::endl;
 std::cout << std::is_same<LeftT,const char(&)[3]>::value << std::endl;
 std::cout << std::is_same<LeftT,const char(&)[4]>::value << std::endl;
 std::cout << std::is_same<RightT,const char*>::value << std::endl;
 std::cout << std::is_same<RightT,const char(&)[3]>::value << std::endl;
 std::cout << std::is_same<RightT,const char(&)[4]>::value << std::endl;
}

int main()
{
 std::cout << std::boolalpha;

 is_same( "ab", "cd" );

 return 0;
}

The output yields: true false false false true false

The compiler is capable of distinguishing the arguments in this case.

Edit 1: Here's some more code. Introducing rvalue references makes functions more distinguishable.

#include <iostream>

// f
template<typename _T>
 void f( _T, const char* )
 {
  std::cout << "f( _T, const char* )" << std::endl;
 }

template<std::size_t _kN>
 void f( int, const char(&)[_kN] )
 {
  std::cout << "f( int, const char (&)[_kN] )" << std::endl;
 }

// g
template<typename _T>
 void g( _T, const char* )
 {
  std::cout << "g( _T, const char* )" << std::endl;
 }

template<std::size_t _kN>
 void g( int, const char(&&)[_kN] )
 {
  std::cout << "g( int, const char (&&)[_kN] )" << std::endl;
 }

// h
template<std::size_t _kN>
 void h( int, const char(&)[_kN] )
 {
  std::cout << "h( int, const char(&)[_kN] )" << std::endl;
 }

template<std::size_t _kN>
 void h( int, const char(&&)[_kN] )
 {
  std::cout << "h( int, const char (&&)[_kN] )" << std::endl;
 }

int main()
{
 //f( 7, "ab" ); // Error!
 //f( 7, std::move("ab") ); // Error!
 f( 7, static_cast<const char*>("ab") ); // OK
 //f( 7, static_cast<const char(&)[3]>("ab") ); // Error!
 //f( 7, static_cast<const char(&&)[3]>("ab") ); // Error!

 g( 7, "ab" ); // OK
 //g( 7, std::move("ab") ); // Error!
 g( 7, static_cast<const char*>("ab") ); // OK
 g( 7, static_cast<const char(&)[3]>("ab") ); // OK
 //g( 7, static_cast<const char (&&)[3]>("ab") ); // Error!

 h( 7, "ab" ); // OK (What? Why is this an lvalue?)
 h( 7, std::move("ab") ); // OK
 //h( 7, static_cast<const char*>("ab") ); // Error
 h( 7, static_cast<const char(&)[3]>("ab") ); // OK
 h( 7, static_cast<const char(&&)[3]>("ab") ); // OK

 return 0;
}