Title
Partial ordering of function templates is underspecified
Status
cd1
Section
13.7.7.3 [temp.func.order]
Submitter
Martin von Loewis/Martin Sebor

Created on 2000-03-13.00:00:00 last changed 167 months ago

Messages

Date: 2003-10-15.00:00:00

[Voted into WP at October 2003 meeting.]

Date: 2003-10-15.00:00:00

[Voted into WP at October 2003 meeting.]

Date: 2002-10-15.00:00:00

Proposed resolution (October 2002):

Change 13.7.7.3 [temp.func.order] paragraph 2 to read:

Partial ordering selects which of two function templates is more specialized than the other by transforming each template in turn (see next paragraph) and performing template argument deduction using the function parameter types, or in the case of a conversion function the return type. The deduction process determines whether one of the templates is more specialized than the other. If so, the more specialized template is the one chosen by the partial ordering process.

Change 13.7.7.3 [temp.func.order] paragraph 3 to read:

To produce the transformed template, for each type, non-type, or template template parameter 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.

Change 13.7.7.3 [temp.func.order] paragraph 4 to read (note: the section reference should refer to the section added to 13.10.3 [temp.deduct] below):

Using the transformed function template's function parameter list, or in the case of a conversion function its transformed return type, perform type deduction against the function parameter list (or return type) of the other function. The mechanism for performing these deductions is given in 14.8.2.x.

Remove the text of 13.7.7.3 [temp.func.order] paragraph 5 but retain the example. The removed text is:

A template is more specialized than another if, and only if, it is at least as specialized as the other template and that template is not at least as specialized as the first.

Insert the following section before 14.8.2.5 (Note that this would either be a new 14.8.2.4, or would be given a number like 14.8.2.3a. If neither of these is possible from a troff point of view, this could be made 14.8.2.5. )

Deducing template arguments when determining the partial ordering of function templates (temp.deduct.partial)

Template argument deduction is done by comparing certain types associated with the two function templates being compared.

Two sets of types are used to determine the partial ordering. For each of the templates involved there is the original function type and the transformed function type. [Note: The creation of the transformed type is described in 13.7.7.3 [temp.func.order].] The deduction process uses the transformed type as the argument template and the original type of the other template as the parameter template. 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.

The types used to determine the ordering depend on the context in which the partial ordering is

  • In the context of a function call, the function parameter types are used.
  • In the context of a call to a conversion operator, the return types of the conversion function templates are used.
  • In other contexts (13.7.7.3 [temp.func.order]), the function template's function type is used.

Each type from the parameter template and the corresponding type from the argument template are used as the types of P and A.

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.

If both P and A were reference types (before being replaced with the type referred to above), determine which of the two types (if any) is more cv-qualified than the other; otherwise the types are considered to be equally cv-qualified for partial ordering purposes. The result of this determination will be used below.

Remove any top-level cv-qualifiers:

  • If P is a cv-qualified type, P is replaced by the cv-unqualified version of P.
  • If A is a cv-qualified type, A is replaced by the cv-unqualified version of A.

Using the resulting types P and A the deduction is then done as described in (13.10.3.6 [temp.deduct.type]). If deduction succeeds for a given type, the type from the argument template is considered to be at least as specialized as the type from the parameter template.

If, for a given type, deduction succeeds in both directions (i.e., the types are identical after the transformations above) if the type from the argument template is more cv-qualified than the type from the parameter template (as described above) that type is considered to be more specialized than the other. If neither type is more cv-qualified than the other then neither type is more specialized than the other.

If for each type being considered a given template is at least as specialized for all types and more specialized for some set of types and the other template is not more specialized for any types or is not at least as specialized for any types, then the given template is more specialized than the other template. Otherwise, neither template is more specialized than the other.

In most cases, all template parameters must have values in order for deduction to succeed, but for partial ordering purposes a template parameter may remain without a value provided it is not used in the types being used for partial ordering. [Note: A template parameter used in a non-deduced context is considered used.]

[Example:

template <class T> T f(int);        // #1
template <class T, class U> T f(U); // #2
void g() {
    f<int>(1);  // Calls #1
}
--end example]

Date: 2020-12-15.00:00:00

In 13.7.7.3 [temp.func.order], partial ordering is explained in terms of template argument deduction. However, the exact procedure for doing so is not specified. A number of details are missing, they are explained as sub-issues below.

  1. 13.7.7.3 [temp.func.order] paragraph 2 refers to 13.10.3 [temp.deduct] for argument deduction. This is the wrong reference; it explains how explicit arguments are processed (paragraph 2) and how function parameter types are adjusted (paragraph 3). Neither of these steps is meaningful in the context of partial ordering. Next in deduction follows one of the steps in 13.10.3.2 [temp.deduct.call], 13.10.3.3 [temp.deduct.funcaddr], 13.10.3.4 [temp.deduct.conv], or 13.10.3.6 [temp.deduct.type]. The standard does not specify which of these contexts apply to partial ordering.
  2. Because 13.10.3.2 [temp.deduct.call] and 13.10.3.4 [temp.deduct.conv] both start with actual function parameters, it is meaningful to assume that partial ordering uses 13.10.3.6 [temp.deduct.type], which only requires types. With that assumption, the example in 13.7.7.3 [temp.func.order] paragraph 5 becomes incorrect, considering the two templates
        template<class T> void g(T);  // #1
        template<class T> void g(T&); // #2
    
    Here, #2 is at least as specialized as #1: With a synthetic type U, #2 becomes g(U&); argument deduction against #1 succeeds with T=U&. However, #1 is not at least as specialized as #2: Deducing g(U) against g(T&) fails. Therefore, the second template is more specialized than the first, and the call g(x) is not ambiguous.
  3. According to John Spicer, the intent of the partial ordering was that it uses deduction as in a function call (13.10.3.2 [temp.deduct.call]), which is indicated by the mentioning of "exact match" in 13.7.7.3 [temp.func.order] paragraph 4. If that is indeed the intent, it should be specified how values are obtained for the step in 13.10.3.2 [temp.deduct.call] paragraph 1, where the types of the arguments are determined. Also, since 13.10.3.2 [temp.deduct.call] paragraph 2 drops references from the parameter type, symmetrically, references should be dropped from the argument type (which is done in Clause 7 [expr] paragraph 2, for a true function call).
  4. 13.7.7.3 [temp.func.order] paragraph 4 requires an "exact match" for the "deduced parameter types". It is not clear whether this refers to the template parameters, or the parameters of the template function. Considering the example
        template<class S> void g(S);  // #1
        template<class T> void g(T const &); // #3
    
    Here, #3 is clearly at least as specialized as #1. To determine whether #1 is at least as specialized as #3, a unique type U is synthesized, and deduction of g<U>(U) is performed against #3. Following the rules in 13.10.3.2 [temp.deduct.call], deduction succeeds with T=U. Since the template argument is U, and the deduced template parameter is also U, we have an exact match between the template parameters. Even though the conversion from U to U const & is an exact match, it is not clear whether the added qualification should be taken into account, as it is in other places.

Issue 200 covers a related issue, illustrated by the following example:

    template <class T> T f(int);
    template <class T, class U> T f(U);
    void g() {
        f<int>(1);
    }

Even though one template is "obviously" more specialized than the other, deduction fails in both directions because neither function parameter list allows template parameter T to be deduced.

(See also issue 250.)

Nathan Sidwell:

13.7.7.3 [temp.func.order] describes the partial ordering of function templates. Paragraph 5 states,

A template is more specialized than another if, and only if, it is at least as specialized as the other template and that template is not at least as specialized as the first.
To paraphrase, given two templates A & B, if A's template parameters can be deduced by B, but B's cannot be deduced by A, then A is more specialized than B. Deduction is done as if for a function call. In particular, except for conversion operators, the return type is not involved in deduction. This leads to the following templates and use being unordered. (This example is culled from G++ bug report 4672 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view&pr=4672)
  template <typename T, class U> T checked_cast(U from); //#1
  template <typename T, class U> T checked_cast(U * from); //#2
  class C {};

  void foo (int *arg)
  {
    checked_cast <C const *> (arg);
  }
In the call,

#1 can be deduced with T = 'C const *' and U = 'int *'

#2 can be deduced with T = 'C const *' and U = 'int'

It looks like #2 is more specialized that #1, but 13.7.7.3 [temp.func.order] does not make it so, as neither template can deduce 'T' from the other template's function parameters.

Possible Resolutions:

There are several possible solutions, however through experimentation I have discounted two of them.

Option 1:

When deducing function ordering, if the return type of one of the templates uses a template parameter, then return types should be used for deduction. This, unfortunately, makes existing well formed programs ill formed. For example

  template <class T> class X {};

  template <class T> X<T> Foo (T *);	// #1
  template <class T> int Foo (T const *); // #2

  void Baz (int *p1, int const *p2)
  {
    int j = Foo (p2); //#3
  }
Here, neither #1 nor #2 can deduce the other, as the return types fail to match. Considering only the function parameters gives #2 more specialized than #1, and hence makes the call #3 well formed.

Option 2:

As option 1, but only consider the return type when deducing the template whose return type involves template parameters. This has the same flaw as option 1, and that example is similarly ill formed, as #1's return type 'X<T,0>' fails to match 'int' so #1 cannot deduce #2. In the converse direction, return types are not considered, but the function parameters fail to deduce.

Option 3:

It is observed that the original example is only callable with a template-id-expr to supply a value for the first, undeducible, parameter. If that parameter were deducible it would also appear within at least one of the function parameters. We can alter paragraph 4 of [temp.func.order] to indicate that it is not necessary to deduce the parameters which are provided explicitly, when the call has the form of a template-id-expr. This is a safe extension as it only serves to make ill formed programs well formed. It is also in line with the concept that deduction for function specialization order should proceed in a similar manner to function calling, in that explicitly provided parameter values are taken into consideration.

Suggested resolution:

Insert after the first sentence of paragraph 4 in 13.7.7.3 [temp.func.order]

Should any template parameters remain undeduced, and the function call be of the form of a template-id-expr, those template parameters provided in the template-id-expr may be arbitrarily synthesized prior to determining whether the deduced arguments generate a valid function type.

See also issue 200.

(April 2002) John Spicer and John Wiegley have written a paper on this. See 02-0051/N1393.

History
Date User Action Args
2008-10-05 00:00:00adminsetstatus: wp -> cd1
2004-04-09 00:00:00adminsetmessages: + msg1024
2003-11-15 00:00:00adminsetstatus: ready -> wp
2003-04-25 00:00:00adminsetstatus: review -> ready
2002-11-08 00:00:00adminsetmessages: + msg743
2002-11-08 00:00:00adminsetstatus: open -> review
2000-05-21 00:00:00adminsetmessages: + msg364
2000-03-13 00:00:00admincreate