Partial ordering with function template having undeduced context

StackOverflow https://stackoverflow.com/questions/1180325

Question

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*)'
Was it helpful?

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.

OTHER TIPS

Edit: After studying Clang's implementation (by Doug Gregor) of their partial ordering algorithm, I have come to agree with the rest of the posters that the original example is not 'intended' to be ambiguous - even though the standard is not as clear as it could be about what should happen in such situations. I have edited this post to indicate my revised thoughts (for my own benefit & reference). In particular Clang's algorithm clarified that 'typename Const<T>::type' is not translated into 'void' during the partial ordering step - and that each A/P pair is deduced independent of each other.

Initially I wondered why the following was considered ambiguous:

        template<class T> void f(T,T*);  // 1

        template<class T> void f(T, int*); // 2

        f(0, (int*)0); // ambiguous

(The above is ambiguous because one cannot deduce f1(U1,U1*) from f2(T,int*), and going the other way, one cannot deduce f2(U2,int*) from f1(T,T*). Neither is more specialized.)

but the following would not be ambiguous:

        template<class T> struct X { typedef int type; };
        template<class T> void f(T, typename X<T>::type*); // 3
        template<class T> void f(T, int*); // 2

(The reason one could expect it to be ambiguous is if the following were to happen:
- f3(U1,X<U1>::type*) -> f3(U1, int*) ==> f2(T,int*) (deduction ok, T=U1)
- f2(U2,int*) ==> f3(T, X<T>::type*) (deduction ok, T=U2 makes X<U2>::type* -> int*)
If this were true, neither one would be more specialized than the other.)

After studying Clang's partial ordering algorithm it is clear that they treat '3' above as if it was:

template<class T, class S> void f(T, S*); // 4

so deduction of some unique 'U' against 'typename X::type' will succeed -

  • f3(U1,X<U1>::type*) is treated as f3(U1, U2*) ==> f2(T,int*) (deduction not ok)
  • f2(U2,int*) ==> f3(T,S* [[X<T>::type*]]) (deduction ok, T=U2, S=int)

And so '2' is clearly more specialized than '3'.

Transformed parameter-list for T1 (Q inserted): (Q, typename Const::type*). The types of the arguments are AT = (Q, void*)

I wonder if that really is a correct simplification. When you synthesise the type Q, are you allowed to conjure up a specialization for Const for the purposes of determining the ordering of template specliazation?

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

This would imply that T2 is not at least as specialized as T1 because a void* parameter does not match T1's second parameter for any given template parameters.

Edit: Please disregard this post - After studying clangs algorithm for partial ordering as implemented by Doug Gregor (even though it is only partially implemented as of this writing - it seems that the logic that's relevant to the OP's question is implemented adequately enough) - it appears as if it treats the undeduced context as just another template parameter. Which suggests that the overload with the explicit void* argument should be the more specialized version and there should be no ambiguity. As usual Comeau is correct. Now as for the wording in the standard that clearly defines this behavior - that's another matter ...

Since this post was also posted on comp.lang.c++.moderated, and seems to be causing some confusion there too - i thought i'd post my answer to that group here too - since the discussion is obviously relevant to the question asked here.

On Jul 25, 1:11 pm, Bart van Ingen Schenau <b...@ingen.ddns.info> wrote:

You are going one step too fast here. How do you know (and would the compiler know) that there is no specialisation of Const<Q> such that Const<Q>::type != void?

As far as I can see, the compiler would transform the parameter-list of A to: AT=(Q, <unknown>*). To call B with these parameters requires an implicit conversion (<unknown>* to void*) and therefore A is less specialised than B.

I believe this is incorrect. When checking to see which function is more specialized (during partial-ordering), the compiler transforms the parameter-list to (Q, void*) - i.e. it actually instantiates the relevant template (best matching) and looks inside it for the value of 'type' - in this case, based on the primary template, it will be void*.

Regarding your point concerning partial specialization - when checking for which template is more specialized than the other, the only type that can be used is the unique generated type - if there are other specializations at the point of instantiation of the declaration (when overload resolution is being done) they will be considered. If you add them later, and they should get selected you will be violating the ODR (according to 14.7.4.1)

The partial/explicit specializations will also get considertaion during formation of the candidate set - but this time using the types of the actual arguments to the function. If the best matching partial specialization (of X) results in a function type that has a better implicit conversion sequence for some parameter, then we never make it to the partial-ordering phase, and that "better" function will get selected (before making it to the partial ordering phase)

Here is an example with comments about what should be going on at various steps:

    template<class T, bool=true> struct X;  // Primary

    template<class T> struct X<T,true> { typedef T type; };  // A
    template<> struct X<int*,true> { typedef void* type; };  // B


    template<class T> void f(T,typename X<T>::type); //1
    template<class T> void f(T*,void*); //2


    int main()
    {
      void* pv;
      int* pi;


      f(pi,pi);   
      // two candidate functions: f1<int*>(int*,void*),  f2<int>(int*,void*)
      // Note: specialization 'B' used to arrive at void* in f1
      // neither has a better ICS than the other, so lets partially order
      // transformed f1 is f1<U1>(U1,X<U1,true>::type) --> f1<U1>(U1,U1) 
      //       (template 'A' used to get the second U1)
      // obviously deduction will fail (U1,U1) -> (T*,void*)
      // and also fails the other way (U2*, void*) -> (T,X<T>::type)
      // can not partially order them - so ambiguity 




      f(pv,pv);  
      // two candidate functions: f1<void*>(void*,void*), f2<void>(void*,void*)
      // Note: specialization 'A' used to arrive at second void* in f1
      // neither has a better ICS than the other, so lets partially order
      // transformed f1 is f1<U1>(U1,X<U1>::type) --> f1<U1>(U1,U1) 
      //       (template 'A' used to get the second U1)
      // obviously deduction will fail (U1,U1) -> (T*,void*)
      // and also fails the other way (U2*, void*) -> (T,X<T>::type)
      // can not partially order them - so ambiguity again             

    }

It's also worth mentioning that if the primary template does not have a definition - then SFINAE operates during the partial ordering phase, neither can be deduced from the other, and ambiguity should result.

Also if you add another template that would lead to another match if the point of instantation of either of those functions is moved elsewhere in the translation unit you will clearly violate the ODR.

On Jul 25, 1:11 pm, Bart van Ingen Schenau <b...@ingen.ddns.info> wrote:

First, being more specialised means that these are fewer types where that template can be selected by overload resolution. Using this, the rules for partial ordering can be summarised as: Try to find a type for A such that A can be called but B not, or overload resolution prefers to call A. If that type can be found, then B is more specialised than A.

No argument here. But based on the rules as they are currently, the OP's example has to be ambiguous.

Finally, here are explicit, unambiguous answers to the two specific questions raised by litb:

1) Will this now use the value of T deduced for the first parameter?
Yes - of course, it has to, it is doing template argument deduction - the 'links' have to be maintained.

2) Now, why do the implementations say that the second is more specialized instead?
Because they are wrong ;)

I hope this puts the issue to rest - Please let me know if there is anything that is still unclear :)

Edit: litb raised a good point in his comment - perhaps stating that the primary template will always get used for the instantiation with the unique generated type is too strong a statement.
There are instances where the primary template will not be called.
What I am getting at is that when partial ordering is occuring, some unique generated type is used to match the best specialization. You're right, it doesn't have to be the primary template. I have edited the above language to do so. He also raised an issue regarding defining a better matching template after the point of instantation. That will be a violation of the ODR according to the section on point of instantiation.

The standard says that once the A/P pairs are created (using the rules of transformation as described in temp.func.order) they are deduced against each other using template argument deduction (temp.deduct)- and that section handles the case of non-deduced contexts, instantiating the template and its nested type, triggering points of instantiations. The temp.point section handles the ODR violations (the meaning of partial ordering should not change regardless of the points of instantation within a translation unit). I'm still not sure where the confusion is coming from? – Faisal Vali 1 hour ago [delete this comment]

litb: "Note that the step that puts Q into Const::type to build the arguments is not covered explicitly by the SFINAE rule. The SFINAE rules work with argument deduction, put the paragraphs that put Q into the function template function parameter list are at 14.5.5.2.'

The SFINAE rules have to be used here - how could they not be? I feel it is sufficiently implied - i won't deny that it could be clearer, and while i encourage the committee to clarify this - i don't think it needs to be clarified to interpret your example sufficiently.

Let me provide one way to link them. From (14.8.2): "When an explicit template argument list is specified, the template arguments must be compatible with the template parameter list and must result in a valid function type as described below; otherwise type deduction fails"

From (14.5.5.2/3) "The transformation used is: — 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 mind, the above quote implies that once you "create" unique generated types for each template parameter, the function declaration has to be implicity instantiated by explicitly supplying the unique types as template arguments to our function template. If this results in an invalid function type, then not only the transformation, but more importantly the subsequent template argument deduction necessary to partially order the function fails.

From (14.5.5.2/4) "Using the transformed function parameter list, perform argument deduction against the other function template. The transformed template is at least as specialized as the other if, and only if, the deduction succeeds and the deduced parameter types are an exact match (so the deduction does not rely on implicit conversions)."

If the transformed function parameter list leads to substitution failure, then we know deduction could not have succeeded. And since deduction did not succeed, it is not as specialized as the other - that is all we need to know to proceed in partial ordering the two.

litb: I'm also not sure what happens in this case: template<typename T> struct A; template<typename T> void f(T, typename A<T>::type); template<typename T> void f(T*, typename A<T>::type); surely, that's indended to be valid code, but doing A::type, it will fail because at the template definition context, A isn't defined yet" Also note that there is no POI defined for template instantiations resulting from this kind of substitution while trying to determine an ordering (partial ordering does not depend on any context. It's a static property of two function templates involved). I think this looks like a problem in the Standard which needs to be fixed.

Ok - i think i see where we are seeing things differently. If i understand you correctly, you are saying that as these function templates get declared, the compiler is keeping a track of the partial ordering amongst them, regardless of overload resolution ever getting triggered to select between them. If that is how you interpret it, then i can see why you would expect the above behavior you describe. But I do not think that the standard ever requires or mandates that.

Now, the standard is clear that the partial ordering is agnostic to the type that is used in calling the function (I believe this is what you are referring to when you describe it as a static property and it being context independent).

The standard is also clear that it only cares about partial ordering (invokes partial ordering) between function templates during the process of overload resolution (13.3.3/1) if and only if it could not pick the better function based on ICS's or if one is a template and the other is not. [Partial ordering of class template partial specializations is a separate issue and in my mind uses the relevant context (other template definitions) that requires the instantiation of that particular class.]

Thus, in my opinion, since the machinery of partial ordering of function templates is invoked when overload resolution is performed, it has to use a relevant portion of the context (template definitions and specializations) available at the point when the overload resolution is being done.

So based on my interepretation, according to your example using 'template struct A' above, the code is valid. The partial ordering is not done at the definition context. But if/when you happen to invoke overload resolution between the two functions by writing a call to f((int*)0,0) - and at that time when the compiler either tries to assemble a candidate declaration or partially order them (if it gets to the partial-ordering step) if an invalid expression or type results as part of the function type, SFINAE helps us out and tells us that template deduction fails (as far as partial ordering is concerned, that implies that one cannot be more specialized than the other if we could not even transform the template).

Now as regards POIs - if you are convinced, as I am, that the transformed function types are supposed to represent implicit instantiations using explicitly supplied template argument lists (using the uniquely generated types) then the following standard quotes are relevant:

14.6.4.1/1 For a function template specialization, a member function template specialization, or a specialization for a member function or static data member of a class template, if the specialization is implicitly instantiated because it is referenced from within another template specialization and the context from which it is referenced depends on a template parameter, the point of instantiation of the specialization is the point of instantiation of the enclosing specialization.

The way I interpret this is that the POI of the transformed function type and the origianl function type is the same as the POI for those functions created by the actual function call.

litb: Since partial ordering is rather only a property of the syntactic form of parameters (i.e "T*" against "T(*)[N]"), i would vote for amending the specification (like "if Q appears in a nested name specifier of a qualified-id naming a type, then the type named is "Q") Or saying that the type named is another unique type. This means that in template<typename T> void f(T, typename Const<T>::type*); the argument list is (Q, R*), for example. Same for template<typename T> void f(T*, typename ConstI<sizeof(T)>::type); the arg lisst would be (Q*, R). A similar rule would be needed for non-type parameters, of course. I would have to think about it and make some test cases to see if this would yield natural orderings, though.

Aah - now you are suggesting a possible solution that resolves the ambiguity in favor of what we all intuitively expect - this is a separate problem, and while I like the direction you are heading in, like you, I too would have to put some thought into it before proclaiming its workability.

Thanks for continuing the discussion. I wish SO didn't just limit you to placing comments.

Since you can edit my posts, please feel free to respond within the post if that is easier.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top