What Is the Partial Ordering Procedure in Template Deduction

What is the partial ordering procedure in template deduction

While Xeo gave a pretty good description in the comments, I will try to give a step-by-step explanation with a working example.

First of all, the first sentence from the paragraph you quoted says:

For each of the templates involved there is the original function type and the transformed function type. [...]

Hold on, what is this "transformed function type"? Paragraph 14.5.6.2/3 explains that:

To produce the transformed template, for each type, non-type, or template template parameter (including
template parameter packs (14.5.3) thereof) synthesize a unique type, value, or class template respectively
and substitute it for each occurrence of that parameter in the function type of the template [...]

This formal description may sound obscure, but it is actually very simple in practice. Let's take this function template as an example:

template<typename T, typename U>
void foo(T, U) // #1

Now since T and U are type parameters, the above paragraph is asking us to pick a corresponding type argument for T (whatever) and substitute it everywhere in the function signature where T appears, then to do the same for U.

Now "synthesizing a unique type" means that you have to pick a fictitious type you haven't used anywhere else, and we could call that P1 (and then pick a P2 for U), but that would make our discussion uselessly formal.

Let's just simplify things and pick int for T and bool for U - we're not using those types anywhere else, so for our purposes, they are just as good as P1 and P2.

So after the transformation, we have:

void foo(int, bool) // #1b

This is the transformed function type for our original foo() function template.

So let's continue interpreting the paragraph you quoted. The second sentence says:

The deduction process uses the transformed type as the argument template and the original type of the other template as the parameter template. [...]

Wait, what "other template"? We only have one overload of foo() so far. Right, but for the purpose of establishing an ordering between function templates, we need at least two of them, so we'd better create a second one. Let's use:

template<typename T>
void foo(T const*, X<T>) // #2

Where X is some class template of ours.

Now what with this second function template? Ah, yes, we need to do the same we previously did for the first overload of foo() and transform it: so again, let's pick some type argument for T and replace T everywhere. I'll pick char this time (we aren't using it anywhere else in this example, so that's as good as some fictitious P3):

void foo(char const*, X<char>) #2b

Great, now he have two function templates and the corresponding transformed function types. So how to determine whether #1 is more specialized than #2 or vice versa?

What we know from the above sentence is that the original templates and their transformed function types must be matched somehow. But how? That's what the third sentence explains:

This process is done twice for each type involved in the partial ordering comparison: once using the transformed template-1 as the argument template and template-2 as the parameter template and again using the transformed template-2 as the argument template and template-1 as the parameter template

So basically the transformed function type of the first template (#1b) is to be matched against the function type of the original second template (#2). And of course the other way round, the transformed function type of the second second template (#2b) is to be matched against the function type of the original first template (#1).

If matching will succeed in one direction but not in the other, then we will know that one of the templates is more specialized than the other. Otherwise, neither is more specialized.

Let's start. First of all, we will have to match:

void foo(int, bool) // #1b

Against:

template<typename T>
void foo(T const*, X<T>) // #2

Is there a way we can perform type deduction on T so that T const* becomes exactly int and X<T> becomes exactly bool? (actually, an exact match is not necessary, but there are really few exceptions to this rule and they are not relevant for the purpose of illustrating the partial ordering mechanism, so we'll ignore them).

Hardly. So let's try matching the other way round. We should match:

void foo(char const*, X<char>) // #2b

Against:

template<typename T, typename U>
void foo(T, U) // #1

Can we deduce T and U here to produce an exact match for char const* and X<char>, respectively? Sure! It's trivial. We just pick T = char const* and U = X<char>.

So we found out that the transformed function type of our first overload of foo() (#1b) cannot be matched against the original function template of our second overload of foo() (#2); on the other hand, the transformed function type of the second overload (#2b) can be matched against the original function template of the first overload (#1).

Conclusion? The second overload of foo() is more specialized than the first one.

To pick a counter-example, consider these two function templates:

template<typename T, typename U>
void bar(X<T>, U)

template<typename T, typename U>
void bar(U, T const*)

Which overload is more specialized than the other? I won't go through the whole procedure again, but you can do it, and that should convince you that a match cannot be produced in either direction, since the first overload is more specialized than the second one for what concerns the first parameter, but the second one is more specialized than the first one for what concerns the second parameter.

Conclusion? Neither function template is more specialized than the other.

Now in this explanation I have ignored a lot of details, exceptions to the rules, and cryptic passages in the Standard, but the mechanism outlined in the paragraph you quoted is indeed this one.

Also notice, that the same mechanism outlined above is used to establish a "more-specialized-than" ordering between partial specializations of a class template by first creating an associated, fictitious function template for each specialization, and then ordering those function templates through the algorithm described in this answer.

This is specified by paragraph 14.5.5.2/1 of the C++11 Standard:

For two class template partial specializations, the first is at least as specialized as the second if, given the
following rewrite to two function templates, the first function template is at least as specialized as the second
according to the ordering rules for function templates (14.5.6.2):

— the first function template has the same template parameters as the first partial specialization and has
a single function parameter whose type is a class template specialization with the template arguments
of the first partial specialization, and

— the second function template has the same template parameters as the second partial specialization
and has a single function parameter whose type is a class template specialization with the template
arguments of the second partial specialization.

Hope this helped.

Template partial ordering - why does partial deduction succeed here

As discussed in the comments, I believe there are several aspects of the function template partial ordering algorithm that are unclear or not specified at all in the standard, and this shows in your example.

To make things even more interesting, MSVC (I tested 12 and 14) rejects the call as ambiguous. I don't think there's anything in the standard to conclusively prove which compiler is right, but I think I might have a clue about where the difference comes from; there's a note about that below.

Your question (and this one) challenged me to do some more investigation into how things work. I decided to write this answer not because I consider it authoritative, but rather to organize the information I have found in one place (it wouldn't fit in comments). I hope it will be useful.

First, the proposed resolution for issue 1391. We discussed it extensively in comments and chat. I think that, while it does provide some clarification, it also introduces some issues. It changes [14.8.2.4p4] to (new text in bold):

Each type nominated above from the parameter template and the
corresponding type from the argument template are used as the types of
P and A. If a particular P contains no template-parameters that
participate in template argument deduction, that P is not used to
determine the ordering.

Not a good idea in my opinion, for several reasons:

If P is non-dependent, it doesn't contain any template parameters at all, so it doesn't contain any that participate in argument deduction either, which would make the bold statement apply to it. However, that would make template<class T> f(T, int) and template<class T, class U> f(T, U) unordered, which doesn't make sense. This is arguably a matter of interpretation of the wording, but it could cause confusion.
It messes with the notion of used to determine the ordering, which affects [14.8.2.4p11]. This makes template<class T> void f(T) and template<class T> void f(typename A<T>::a) unordered (deduction succeeds from first to second, because T is not used in a type used for partial ordering according to the new rule, so it can remain without a value). Currently, all compilers I've tested report the second as more specialized.

It would make #2 more specialized than #1 in the following example:

#include <iostream>

template<class T> struct A { using a = T; };

struct D { };
template<class T> struct B { B() = default; B(D) { } };
template<class T> struct C { C() = default; C(D) { } };

template<class T> void f(T, B<T>) { std::cout << "#1\n"; } // #1
template<class T> void f(T, C<typename A<T>::a>) { std::cout << "#2\n"; } // #2

int main()
{
   f<int>(1, D());
}

(#2's second parameter is not used for partial ordering, so deduction succeeds from #1 to #2 but not the other way around). Currently, the call is ambiguous, and should arguably remain so.

After looking at Clang's implementation of the partial ordering algorithm, here's how I think the standard text could be changed to reflect what actually happens.

Leave [p4] as it is and add the following between [p8] and [p9]:

For a P / A pair:

If P is non-dependent, deduction is considered successful if and only if P and A are the same type.

Substitution of deduced template parameters into the non-deduced contexts appearing in P is not performed and does not affect the outcome of the deduction process.

If template argument values are successfully deduced for all template parameters of P except the ones that appear only in non-deduced contexts, then deduction is considered successful (even if some parameters used in P remain without a value at the end of the deduction process for that particular P / A pair).

Notes:

About the second bullet point: [14.8.2.5p1] talks about finding template argument values that will make P, after substitution of the deduced values (call it the deduced A), compatible with A. This could cause confusion about what actually happens during partial ordering; there's no substitution going on.
MSVC doesn't seem to implement the third bullet point in some cases. See the next section for details.
The second and third bullet points are intented to also cover cases where P has forms like A<T, typename U::b>, which aren't covered by the wording in issue 1391.

Change the current [p10] to:

Function template F is at least as specialized as function template
G if and only if:

for each pair of types used to determine the ordering, the type from F is at least as specialized as the type from G, and,

when performing deduction using the transformed F as the argument template and G as the parameter template, after deduction is done
for all pairs of types, all template parameters used in the types from
G that are used to determine the ordering have values, and those
values are consistent across all pairs of types.

F is more specialized than G if F is at least as specialized
as G and G is not at least as specialized as F.

Make the entire current [p11] a note.

(The note added by the resolution of 1391 to [14.8.2.5p4] needs to be adjusted as well - it's fine for [14.8.2.1], but not for [14.8.2.4].)

For MSVC, in some cases, it looks like all template parameters in P need to receive values during deduction for that specific P / A pair in order for deduction to succeed from A to P. I think this could be what causes implementation divergence in your example and others, but I've seen at least one case where the above doesn't seem to apply, so I'm not sure what to believe.

Another example where the statement above does seem to apply: changing template<typename T> void bar(T, T) to template<typename T, typename U> void bar(T, U) in your example swaps results around: the call is ambiguous in Clang and GCC, but resolves to b in MSVC.

One example where it doesn't:

#include <iostream>

template<class T> struct A { using a = T; };
template<class, class> struct B { };

template<class T, class U> void f(B<U, T>) { std::cout << "#1\n"; }
template<class T, class U> void f(B<U, typename A<T>::a>) { std::cout << "#2\n"; }

int main()
{
   f<int>(B<int, int>());
}

This selects #2 in Clang and GCC, as expected, but MSVC rejects the call as ambiguous; no idea why.

The partial ordering algorithm as described in the standard speaks of synthesizing a unique type, value, or class template in order to generate the arguments. Clang manages that by... not synthesizing anything. It just uses the original forms of the dependent types (as declared) and matches them both ways. This makes sense, as substituting the synthesized types doesn't add any new information. It can't change the forms of the A types, since there's generally no way to tell what concrete types the substituted forms could resolve to. The synthesized types are unknown, which makes them pretty similar to template parameters.

When encountering a P that is a non-deduced context, Clang's template argument deduction algorithm simply skips it, by returning "success" for that particular step. This happens not only during partial ordering, but for all types of deductions, and not just at the top level in a function parameter list, but recursively whenever a non-deduced context is encountered in the form of a compound type. For some reason, I found that surprising the first time I saw it. Thinking about it, it does, of course, make sense, and is according to the standard ([...] does not participate in type deduction [...] in [14.8.2.5p4]).

This is consistent with Richard Corden's comments to his answer, but I had to actually see the compiler code to understand all the implications (not a fault of his answer, but rather of my own - programmer thinking in code and all that).

I've included some more information about Clang's implementation in this answer.

Partial ordering of function templates containing template parameter packs

First step in overload resolution is finding all the candidates. For the call g(Tuple<int>()), there are three viable candidates:

g(Tuple<int>); // #1: [Types = {int}]
g(Tuple<int>); // #2: [T1 = int, Types = {}]
g(Tuple<int>); // #3: [T1 = int, Types = {}]

All three are equally viable candidates from the perspective of conversion sequences (since, of course, they all take the same argument which is an Exact Match for the input). They are all function template specializations, so we can't differentiate on that basis either.

So we're left with function template partial ordering. We synthesize types for each of the overloads and attempt to perform template deduction with our synthesized types against each of the other overloads. The simpler comparison is (1) vs (2) and (1) vs (3). There, we have [temp.deduct.partial]:

If A was transformed from a function parameter pack and P is not a parameter pack, type deduction fails.

Since we transform Types... into UniqA..., and the first parameter is T1, type deduction fails. That makes (2) and (3) both more specialized than (1). So now we compare (2) and (3).

First, can we deduce (2) from (3)?

template <class T1, class... Types> void g(Tuple<T1, Types...> );

g(Tuple<Uniq3, Uniq3Pack&...>());

Sure, no problem T1 == Uniq3 and Types... == Uniq3Pack&.... Next, we try the other direction:

template <class T1, class... Types> void g(Tuple<T1, Types&...> );

g(Tuple<Uniq2, Uniq2Pack...>());

This fails, since Uniq2Pack isn't a pack of reference types and Types&... is. Since deduction only succeeds in one direction, that makes (3) the more specialized overload.

As it's the last one standing, (3) is the best viable candidate. It may seem counterintuitive, since we're not actually calling it with a reference type - but it's still the best choice.

Partial ordering with function template having undeduced context

Here's my go at this. I agree with Charles Bailey that the incorrect step is to go from Const<Q>::Type* to void*

template<typename T>
void f(T, typename Const<T>::type*) { cout << "Const"; } // T1

template<typename T>
void f(T, void*) { cout << "void*"; } // T2

The steps we want to take are:

14.5.5.2/2

Given two overloaded function templates, whether one is more specialized than another can be determined by transforming each template in turn and using argument deduction (14.8.2) to compare it to the other.

14.5.5.2/3-b1

For each type template parameter, synthesize a unique type and substitute that for each occurrence of that parameter in the function parameter list, or for a template conversion function, in the return type.

In my opinion, the types are synthesized as follows:

(Q, Const<Q>::Type*)    // Q1
(Q, void*)              // Q2

I don't see any wording that requires that the second synthesized parameter of T1 be void*. I don't know of any precedent for that in other contexts either. The type Const<Q>::Type* is perfectly valid type within the C++ type system.

So now we perform the deduction steps:

Q2 to T1

We try to deduce the template parameters for T1 so we have:

Parameter 1: T is deduced to be Q
Parameter 2: Nondeduced context

Even though parameter 2 is a non deduced context, deduction has still succeeded because we have a value for T.

Q1 to T2

Deducing the template parameters for T2 we have:

Parameter 1: T is deduced to be Q
Parameter 2: void* does not match Const<Q>::Type* so deduction failure.

IMHO, here's where the standard lets us down. The parameter is not dependent so it's not really clear what should happen, however, my experience (based on a squinted read of 14.8.2.1/3) is that even where the parameter type P is not dependent, then the argument type A should match it.

The synthesized arguments of T1 can be used to specialize T2, but not vice versa. T2 is therefore more specialized than T1 and so is the best function.

UPDATE 1:

Just to cover the poing about Const<Q>::type being void. Consider the following example:

template<typename T>
struct Const;

template<typename T>
void f(T, typename Const<T>::type*) // T1
{ typedef typename T::TYPE1 TYPE; }

template<typename T>
void f(T, void*)                    // T2
{ typedef typename T::TYPE2 TYPE ; }

template<>
struct Const <int>
{
  typedef void type;
};

template<>
struct Const <long>
{
  typedef long type;
};

void bar ()
{
  void * p = 0;
  f (0, p);
}

In the above, Const<int>::type is used when we're performing the usual overload resolution rules, but not when we get to the partial overloading rules. It would not be correct to choose an arbitrary specialization for Const<Q>::type. It may not be intuitive, but the compiler is quite happy to have a synthasized type of the form Const<Q>::type* and to use it during type deduction.

UPDATE 2

template <typename T, int I>
class Const
{
public:
  typedef typename Const<T, I-1>::type type;
};

template <typename T>
class Const <T, 0>
{
public:
  typedef void type;
};

template<typename T, int I>
void f(T (&)[I], typename Const<T, I>::type*)     // T1
{ typedef typename T::TYPE1 TYPE; }

template<typename T, int I>
void f(T (&)[I], void*)                           // T2
{ typedef typename T::TYPE2 TYPE ; }


void bar ()
{
  int array[10];
  void * p = 0;
  f (array, p);
}

When the Const template is instantiated with some value I, it recursively instantiates itself until I reaches 0. This is when the partial specialization Const<T,0> is selected. If we have a compiler which synthesizes some real type for the parameters of the function, then what value will the compiler choose for the array index? Say 10? Well, this would be fine for the above example but it wouldn't match the partial specialization Const<T, 10 + 1> which, conceptually at least, would result in an infinite number of recursive instantiations of the primary. Whatever value that it selected we could modify the end condition to be that value + 1, and then we'd have an infinite loop in the partial ordering algorithm.

I do not see how the partial ordering algorithm could correctly instantiate Const to find what type really is.

what's the original type for a member function template during partial ordering

Yes, it's a bit of a mess. As you've observed, it doesn't make sense for the "original type" of a class non-static member function to lack the inserted this parameter.

The only way to make it work is for the subsequent paragraphs in subclause 3 to apply to the "original" function type on the other side of [temp.deduct.partial] as well as the "transformed" function type. You could just about read it that way for what is presently the first sentence of the second paragraph, reading "each" as applying to both the transformed and original function type:

Each function template M that is a member function is considered to have a new first parameter of type X(M) [...]

However, since the resolution to CWG 2445 in P2108 we have another sentence:

If exactly one of the function templates was considered [...] via a rewritten candidate with a reversed order of parameters, then the order of the function parameters in its transformed template is reversed.

So we quite clearly have this reversal applying asymmetrically, giving an absurd result. On the upside, it's fairly clear how it should read; the adjustments to function type (this insertion and parameter reversal) should apply prior to unique type synthesis/substitution, and apply to the "original" and transformed function type equally.

As far as I can tell, this defect does not appear to have been reported to the Core Language Working Group; it does not appear in the C++ Standard Core Language Active Issues list.

Deducing template arguments during partial ordering when parameters are function parameter pack

Why f(1, 2, 3); calls #2?

There's a lot of questions in your question (one question per question please!), so I will stick to that one. First, we perform template deduction. #3 fails, but #1 and #2 succeed:

template<class... Args>
void f(Args... args);        // #1, with Args = {int, int, int}
template<class T1, class... Args> 
void f(T1 a1, Args... args); // #2, with T1 = int, Args = {int, int}

Both functions take three ints by value, so all the normal tiebreakers in overload resolution fail to resolve the ambiguity. So we get to the very last one:

Given these definitions, a viable function F1 is defined to be a better function than another viable function F2 if for all arguments i, ICS_i(F1) is not a worse conversion sequence than ICS_i(F2), and then

— [...]

— 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.

The rules are:

Step 1: synthesize types [temp.func.order]:

To produce the transformed template, for each type, non-type, or template template parameter (including
template parameter packs (14.5.3) thereof) synthesize a unique type, value, or class template respectively
and substitute it for each occurrence of that parameter in the function type of the template.

So we have:

void f(Pack1... args);         // #1
void f(U2 a1, Pack2... args);  // #2

Step 2: perform deduction as described in [temp.deduct.partial]. The context we're in is a function call, so we use the types for which the function call has arguments.

First, we try to deduce #2 from #1. That is, we try to match (T1, Args...) against (Pack1...). The first part is then P = T1, A = Pack1.... We have:

If A was transformed from a function parameter pack and P is not a parameter pack, type deduction fails.

So deducing #2 from #1 fails, so the argument Args... is not at least as specialized as T1, Args....

Next, we try to deduce #1 from #2. That is, we try to match (Args...) against (U2, Pack2...). That succeeds, so T1, Args... is at least as specialized as Args....

Since #2 is at least as specialized as #1 and #1 is not at least as specialized as #2, we can say that #2 is more specialized:

Function template F is at least as specialized as function template G if, for each pair of types used to
determine the ordering, the type from F is at least as specialized as the type from G. F is more specialized
than G if F is at least as specialized as G and G is not at least as specialized as F.

The more specialized template is preferred, so we call #2.

The P/A deducation when determining the partial order of C++ overloaded function templates

For each type, non-type, and template parameter, including parameter packs, a unique fictitious type, value, or template is generated and substituted into function type of the template

U1 here is not a template type; it's a unique ficitious type and it's different from int, so the deduction fails.

What Is the Partial Ordering Procedure in Template Deduction