When are two function templates considered as partially ordered and when are ambiguous?

Question

I'm completely confused after reading the question How to make these std::function parameters unambiguous?, so far I'd thought I understood what partial ordering of function templates is, but after reading that question I wrote down three examples to check the compiler's behavior, and the results received are hard for me to understand.

Example #1

template <class T>
void foo(T) {}

template <class T>
void foo(T&) {}

int main()
{
  int i;
  foo<int>(i); // error: call is ambiguous! 
}

Question: Both functions are viable, that's obvious, but isn't the one taking T& more specialized than T? Instead, the compiler raises ambiguous call error.

Example #2

#include <iostream>

template <class T>
struct X {};

template <>
struct X<int> 
{
  X() {}
  X(X<int&> const&) {} // X<int> is constructible from X<int&>
  // note: this is not a copy constructor!
};

template <>
struct X<int&> 
{
  X() {}
  X(X<int> const&) {} // X<int&> is constructible from X<int>
  // note: this is not a copy constructor!
};

template <class T>
void bar(X<T>) { std::cout << __PRETTY_FUNCTION__ << std::endl; }

template <class T>
void bar(X<T&>) { std::cout << __PRETTY_FUNCTION__ << std::endl; }

int main()
{
  bar<int>(X<int>());   // calls void bar(X<T>) [with T = int]

  bar<int>(X<int&>());  // calls void bar(X<T&>) [with T = int]
}

Question: If the T& and T are ambiguous in Example #1, then why here none call is ambiguous? X<int> is constructible from X<int&>, as well as X<int&> is constructible from X<int> thanks to provided constructors. Is it because compiler generated X<int>::X(X<int> const&) copy-constructor is a better conversion sequence than X<int>::X(X<int&> const&), (if so, what makes it better, note that arguments are passed by value), and so the ordering of specializations does not matter at all?

Example #3

#include <iostream>

// note: a new type used in constructors!
template <class U>
struct F {};

template <class T>
struct X
{
  X() {}

  template <class U>
  X(F<U> const&) {}  // X<T> is constructible from any F<U>
  // note: it takes F type, not X!
};

template <class T>
void qux(X<T>) { std::cout << __PRETTY_FUNCTION__ << std::endl; }

template <class T>
void qux(X<T&>) { std::cout << __PRETTY_FUNCTION__ << std::endl; }

int main()
{
  qux<int>(F<int>());  // calls void qux(X<T&>) [with T = int]

  qux<int>(F<int&>()); // calls void qux(X<T&>) [with T = int]
}

Question: Now this is similar scenario to "matching lambda [](int){} against std::function<void(int&)> and std::function<void(int)>" from question linked. Why in both calls the more specialized function template is picked? Is it because the conversion sequence is the same, so partial ordering starts to matter?

All tests done on GCC 4.9.0 with -std=c++11 and no extra flags.

Answer 1

Overload resolution tries to find the best function like this:

(1) [over.match.best]/1:

Given these definitions, a viable function F1 is defined to be a better function than another viable function F2 if for all arguments i, ICSi(F1) is not a worse conversion sequence than ICSi(F2), and then
— for some argument j, ICSj(F1) is a better conversion sequence than ICSj(F2), or, if not that,
— the context is an initialization by user-defined conversion (see 8.5, 13.3.1.5, and 13.3.1.6) and the standard conversion sequence from the return type of F1 to the destination type (i.e., the type of the entity being initialized) is a better conversion sequence than the standard conversion sequence from the return type of F2 to the destination type.
[ Example:

struct A {
  A();
  operator int();
  operator double();
} a;

int i = a;    // a.operator int() followed by no conversion is better 
              // than `a.operator double()`     
              // followed by a conversion to `int`
float x = a;  // ambiguous: both possibilities require conversions,
              // and neither is better than the other

— end example ] or, if not that,
— F1 is a non-template function and F2 is a function template specialization, or, if not that,
— F1 and F2 are function template specializations, and the function template for F1 is more specialized than the template for F2 according to the partial ordering rules described in 14.5.6.2.

---

Case 1:

but isn't the one taking T& more specialized than T?

According to overload resolution, no conversion is better (both are identity conversions, which are exact matches), and since no other bullet in (1) applies, partial ordering is done. [temp.deduct.partial]/5 says that references are replaced by the type they refer to for purposes of partial ordering:

Before the partial ordering is done, certain transformations are performed on the types used for partial ordering:
— If P is a reference type, P is replaced by the type referred to.
— If A is a reference type, A is replaced by the type referred to.

Since the parameters of the parameter templates are completely identical it is not hard to see that the deductions against each other are successful both ways -- so neither template is more specialized than the other.

Case 2:

Partial ordering isn't needed here. The user-defined-conversion from X<int> to X<int&> has a worse rank than converting X<int> to X<int> -- The latter is given Exact Match rank by [over.ics.user]/4:

A conversion of an expression of class type to the same class type is given Exact Match rank, […]

Thus it's obviously a better conversion than X<int> to X<int&>, which has Conversion rank. Same goes vice versa, for X<int&> to X<int>.

Case 3:

The third case is similar to the first. X<int> and X<int&> both have a constructor template that can take an arbitrary specialization of F. (1) tells us that since none of the conversion sequences is better than the other in any way (in fact, they are completely identical), the more specialized template is chosen.

template <class T> void bar(X<T>);  // #1

template <class T> void bar(X<T&>); // #2

// Call:
bar<int>( F<int>() );

Going back to [temp.deduct.partial], type deduction is performed. A unique type, call it Unique, is synthesized for the template parameter of each argument template. The following procedures with corresponding results are carried out - note that the steps are exactly the same when calling with F<int> as with F<int&> (and any other specialization of F):

1. template #1 as the parameter template and template #2 as the argument template, X<Unique&> is deduced against X<T>, yielding T=Unique&. On the other hand,
2. template #2 as the parameter template against template #1 as the argument template, X<Unique> is deduced against X<T&>, which results in a deduction failure.

As we can see template #2 is more specialized. When used as an argument template in step 1, deduction succeeded, whereas for template #1 as the argument template in step 2, the deduction failed. Therefore the second, more specialized function templates' specialization is called.

Answer 2

Example 1 :

The compiler cannot know if you want to pass a by reference or by value. If you specialize your template with a T * he will know easily because the function call syntax will be different foo(&a).

Example 2 :

Here you tell the compiler that the second overload of qux takes a X<T &> so he knows that you want to construct this object with an T &. There is no ambiguity. But if you do this :

template <class T>
void qux(X<T>) { std::cout << __PRETTY_FUNCTION__ << std::endl; }

template <class T>
void qux(X<T> &) { std::cout << __PRETTY_FUNCTION__ << std::endl; }

You will end up with the same problem

Example 3:

Same problem.

I don't know if it's very clear so if someone could improve my answer, that could be useful to the author