c++templates template-argument-deduction function-templates partial-ordering

Partial ordering with function template having undeduced context

While reading another question, i came to a problem with partial ordering, which i cut down to the following test-case

template<typename T>
struct Const { typedef void type; };

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

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

int main() {
  // GCC chokes on f(0, 0) (not being able to match against T1)
  void *p = 0;
  f(0, p);
}

For both function templates, the function type of the specialization that enters overload resolution is void(int, void*). But partial ordering (according to comeau and GCC) now says that the second template is more specialized. But why?

Let me go through partial ordering and show where i have questions. May Q be an unique made-up type used for determining partial ordering according to 14.5.5.2.

Transformed parameter-list for T1 (Q inserted): (Q, typename Const<Q>::type*). The types of the arguments are AT = (Q, void*)
Transformed parameter-list for T2 (Q inserted): BT = (Q, void*), which are also the types of the arguments.
Non-transformed parameter-list for T1: (T, typename Const<T>::type*)
Non-transformed parameter-list for T2: (T, void*)

Since C++03 under-specifies this, i did use the intention that i read about in several defect reports. The above transformed parameter list for T1 (called AT by me) is used as argument list for 14.8.2.1 "Deducing template arguments from a function call".

14.8.2.1 does not need to transform AT or BT itself anymore (like, removing reference declarators, etc), and goes straight to 14.8.2.4, which independently for each A / P pair does type deduction:

AT against T2: { (Q, T), (void*, void*) }. T is the only template parameter here, and it will find that T must be Q. Type deduction succeeds trivially for AT against T2.
BT against T1: { (Q, T), (void*, typename Const<T>::type*) }. It will find that T is Q, too here. typename Const<T>::type* is an un-deduced context, and so it won't be used to deduce anything.

Here is my first question: Will this now use the value of T deduced for the first parameter? If the answer is no, then the first template is more specialized. This can't be the case, because both GCC and Comeau say that the second template is more specialized, and i don't believe they are wrong. So we assume "yes", and insert void* into T. The paragraph (14.8.2.4) says "Deduction is done independently for each pair and the results are then combined" and also "In certain contexts, however, the value does not participate in type deduction, but instead uses the values of template arguments that were either deduced elsewhere or explicitly specified." This sounds like "yes" too.

Deduction therefore succeeds too, for every A / P pair. Now, each template is at least as specialized as the other, because deduction didn't also rely on any implicit conversions and succeeded in both directions. As a result, the call should be ambiguous.

So my second question: Now, why do the implementations say that the second template is more specialized? What point did i overlook?

Edit: I tested explicit specialization and instantiation, and both, in recent GCC versions (4.4) tell me that the reference to the specialization is ambiguous, while an older version of GCC (4.1) doesn't rise that ambiguity error. This suggests that recent GCC versions have inconsistent partial ordering for function templates.

template<typename T>
struct Const { typedef void type; };

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

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

template<> void f(int, void*) { }
  // main.cpp:11: error: ambiguous template specialization 
  // 'f<>' for 'void f(int, void*)'

Solution

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.