Partial Specialization Ordering with Non-Deduced Context

Why are dependent template types not deducible in partial specialization?

During template argument deduction everything on the left-hand side of the scope resolution operator :: in a template argument of the partial specialization is a non-deduced context, meaning that a template parameter appearing there will not be deduced from the corresponding argument of the specialization.

Further, if part of a qualified type name is non-deduced context, then all parameters used to specify the type are non-deduced.

So in your example neither D nor E are deduced from typename Outer<D>::template Inner<E> and since there is no other way of deducing them, deduction fails, meaning that the partial specialization is never viable.

Class template specialization partial ordering and function synthesis

Clang is being GCC-compatible (and compatible with existing code that depends on both of these behaviors).

Consider [temp.deduct.type]p1:

[...] an attempt is made to find template argument values (a type for a type parameter, a value for a non-type parameter, or a template for a template parameter) that will make P, after substitution of the deduced values (call it the deduced A), compatible with A.

The crux of the issue is what "compatible" means here.

When partially ordering function templates, Clang merely deduces in both directions; if deduction succeeds in one direction but not the other, it assumes that means the result will be "compatible", and uses that as the ordering result.

When partially ordering class template partial specializations, however, Clang interprets "compatible" as meaning "the same". Therefore it only considers one partial specialization to be more specialized than another if substituting the deduced arguments from one of them into the other would reproduce the original partial specialization.

Changing either of these two to match the other breaks substantial amounts of real code. :(

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.

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.

---

Related Topics