Document number J16/01-0009 = WG21 N1295

Partial specialization of function templates
============================================

Peter Dimov, pdimov@mmltd.net
     with advice from
David Abrahams, abrahams@mediaone.net


Overview
--------

C++ currently has

* class template explicit specializations;
* class template partial specializations;
* function template explicit specializations.

This leads many users to believe that function templates can be partially
specialized; some of them even come up with the logical extension to the syntax
on their own and are quite surprised that their compiler complains.

Indeed, the standard in 14/2 explicitly forbids the "natural" function template
partial specialization syntax.


Why introduce them
------------------

[This section is written with the assumption that the reader will understand the
proposed function template partial specialization syntax by analogy to class
template partial specialization. For a detailed description, please refer to the
following two sections]

In many situations, a partial specialization of a function template can be
emulated with an overload:

  template<class T> void f(T);
  template<class T> void f<T*>(T*);  // specialize 'f' for pointers
  template<class T> void f(T*);      // overload 'f' for pointers

This has lead many to think that partial specializations are not
necessary. However, there are cases where overloads do not suffice:

* It is not possible to add an overload to a closed scope, like a class (or
  namespace std - but see LWG issue 226 and the paper "User supplied
  specializations of standard library algorithms".)

  A partial specialization may be used to specialize a function template that is
  a member of a closed scope.

* When a template parameter does not appear in the function argument list, it is
  not possible to overload on it:

  template<class T> void f();      // 'f' cannot be overloaded
  template<class T> void f<T*>();  // but it can be specialized

* Existing code may depend on the fact that a function template is not
  overloaded:

  template<class T> void f(T);

  template<class It> void user1(It first, It last)
  {
    typedef typename std::iterator_traits<It>::value_type Vt;
    std::for_each(first, last, &f<Vt>); // must cast &f<Vt> to void (*) (Vt) if overloaded

    // std::for_each is used as an example only; in this trivial case
    // an explicit loop gets around the problem easily
  }

  struct base {};
  struct derived: base {};

  void user2()
  {
    derived d;
    f<base>(d); // must use f(static_cast<base&>(d)) if overloaded
  }

* Existing code grants friendship to a template function

  The overload will not inherit the access, but a specialization will.

In summary, partial specializations are virtually indistinguishable from the
primary template from the compiler's point of view. This makes them ideal for
modifying the behavior of an existing template function without breaking or
otherwise negatively affecting code that already depends on it.

An often-used approach is to emulate function template partial specialization
with helper classes:

  template<class T> struct f_helper
  {
    static void f();
  };

  template<class T> inline void f()
  {
    f_helper<T>::f();
  }

  template<class T> struct f_helper<T*> // specialize f() for pointers
  {
    static void f(); // specialized behavior
  }

This approach works (although the code has a distinct "workaround" look).

Unfortunately, libraries rarely provide helper classes for the users (or other
library authors) to specialize. Even the standard C++ library, which has been
designed with extensibility in mind, does not have helper classes.


How could they work
-------------------

This section is provided as a proof-of-concept. It is understood that the core
working group may want to produce a new proposal from the ground up.

Informally (see Appendix A for proposed changes to the standard), partial
specialization of function templates would work as follows:

  template<class T> void f();     // primary template

  template<> void f<int>();       // explicit specialization

  template<class T> void f<T*>(); // partial specialization

  void g()
  {
    f<double>();  // calls the primary template
    f<int>();     // calls the explicit specialization
    f<int*>();    // calls the partial specialization
  }

Selecting the specialization to instantiate can be determined using the class
template partial specialization rules.

The situation becomes a bit more involved when multiple overloaded templates are
present:

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

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

  template<> void f<int>(int);       // #1.1

  template<> void f<int>(int*);      // #2.1

  template<> void f(int);            // equivalent to #1.1

  template<> void f(int*);           // equivalent to #2.1 because of 14.5.5.2/1

  template<class U> void f<U*>(U*);  // #1.2

  template<class U> void f<U*>(U**); // #2.2

In this case the primary template that is being specialized can be determined by
the following procedure:

For each primary template candidate, substitute the template arguments from the
specialization into the primary template signature; if the two signatures match
exactly, this primary template is being specialized.

Example:

#1.2 -> #1: the substitution is T = U*. #1 becomes void f<U*>(U*) and matches
   #1.2 exactly.

#1.2 -> #2: T = U*, #2 becomes void f<U*>(U**), no match.

This process always selects one primary template, except in the corner cases
where:

* multiple cv-qualifiers fold into one:

  template<class T> void f(T const *);

  template<class T> void f(T *);

  template<class U> void f<U const>(U const *); // ambiguous, U const const == U const

* multiple references collapse into one:

  template<class T> void f(T &);

  template<class T> void f(T);

  template<class U> void f<U &>(U &); // ambiguous, U & & == U &


Appendix A: Proposed changes
----------------------------

7.3.3/9:

- change the note to refer to partial specializations in general:

"Note: template partial specializations are found by looking up the primary
template and then considering all partial specializations of that template. If a
using-declaration names a template, partial specializations introduced after the
using-declaration are effectively visible because the primary template is
visible (14.5.4)."

14/2:

- remove the second sentence
- change the note to read:

"Note: if the declarator-id is a template-id, the declaration declares a
template partial specialization (14.5.4)."

14/4:

- change "class template partial specialization" to "template partial
  specialization"

14.5.4:

- change section name to "Template partial specializations"

14.5.4/1:

- remove all occurrences of the word "class".

14.5.4/4:

- optionally provide an example for a function template partial specialization:

template<class T1, class T2, int I>	T1  f(T2 (&t2) [I]);
template<class T, int I>		T   f<T,   T*,  I>(T*  (&t) [I]);
template<class T1, class T2, int I>	T1* f<T1*, T2,  I>(T2  (&)  [I]);
template<class T>			int f<int, T*,  5>(T*  (&t) [5]);
template<class T1, class T2, int I>	T1  f<T1,  T2*, I>(T2* (&a) [I]);

14.5.4/5:

- remove the word "class" in the second sentence

14.5.4/6:

- not sure about that one

14.5.4/7:

- remove the word "class" in the third sentence

14.5.4/9:

- remove the word "class" in the first sentence

14.5.4/11 (new paragraph):

A function template partial specialization specializes a primary template if and
only if, after substituting the template arguments provided in the
specialization template argument list into the primary template declaration, the
resulting function signature matches that of the specialization.

[Note: each function template partial specialization specializes at most one
primary template.]

14.5.4/12 (new paragraph):

[Example:

template<class T> void f(T  x);      // primary template #1
template<class U> void f(U* y);      // primary template #2

template<class V> void f<V*>(V* z);  // specialization of #1, T = V*
template<class W> void f<W*>(W** w); // specialization of #2, U = W*

-- end example.]

14.5.4.1/1:

- remove the first occurrence of "class" in the first sentence
- change the second "class" to "template" in the first sentence
- remove the word "class" in the second sentence
- remove the word "class" in "the use of the class template is ambiguous"

14.5.4.2:

- change section name to "Partial ordering of template specializations"

14.5.4.2/1: (change to):

For two template partial specializations (that specialize the same primary
template,) 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.5.2):

- synthesize a unique class template with the same parameter list as the primary
  template;

- 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 of the synthesized class template with the
  template arguments of the first partial specialization;

- 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 of the synthesized class template with the
  template arguments of the second partial specialization.

14.5.4.2/2 (change example to):

template<int I, int J, class T> class X { };
template<int I, int J>		class X<I, J, int> { };		// #1
template<int I>			class X<I, I, int> { };		// #2

template<int I, int J, class T> class __unique;

template<int I, int J>		void __f(__unique<I, J, int>);	// #A
template<int I>			void __f(__unique<I, I, int>);	// #B

14.5.4.2/3 (new paragraph):

[Example:

template<class T, class U, class V>	U  f		(V);
template<class U, class V>		U  f<int, U, V>	(V);	// #1
template<class T>			T  f<int, T, T>	(T);	// #2

template<class T, class U, class V>	class __unique;

template<class U, class V>		void __f(__unique<int, U, V>);	// #A
template<class T>			void __f(__unique<int, T, T>);	// #B

-- end example.]