Friday, January 04, 2008

Function Template Overload Resolution and Specialization Anomaly

I recently realized that function template overloading and function template specialization can interact with each other in complex ways giving rise to quite surprising C++ programs. Consider,

template<class T> // (a) a base template
void f( T ) {
std::cout << "f(T)\n";
}

template<>
void f<>(int*) { // (b) an explicit specialization
std::cout << "f(int *) specilization\n";
}

template<class T> // (c) another, overloads (a)
void f( T* ) {
std::cout << "f(T *)\n";
}

int main (void) {
int *p = 0;
f(p);
}

Output of the above program is "f(T *)" (i.e. (c) is invoked in main). Now simply swap the order in which (b) and (c) are written. The output of the program changes! This time it invokes (b) giving output as "f(int *) specilization".

The reason behind it is that when the integer full specilization (b) of f is defined in the order shown above, it is a full specialization of (a). But (c) is a better match as it is an overloaded primary template defined afterwards and we get "f(T *)" as an output.

When (b) is defined after (c), (b) is an integer full specilization of (c) and hence the specilization is chosen as expected.

An excerpt from the book "C++ Templates - The Complete Guide" helps explain what is really happening here.

"Partial specialization doesn't introduce a completely new template: It is an extension of an existing template (the primary template). When a CLASS template is looked up, only primary templates are considered at first. If, after the selection of a primary template, it turns out that there is a partial specialization of that template with a template argument pattern that matches that of the instantiation, its definition (in other words, its body) is instantiated instead of the definition of the primary template. (Full template specializations work exactly the same way.)"

(Added this para on May-05-2008)
Note that the above paragraph applies to class templates only. But when full specializations are in consideration, the above paragraph applies to function templates as well. Full function template specialization is supported by C++98 standard but not partial function template specialization. A better alternative to partial function template specialization is to use plain old function overloading. Having said that, as far as I know, there are efforts begin made towards standardizing partial function template specialization for C++09 standard. (please see comments for more discussion on this.)

The program clearly shows that the order of definition of specilizations and overloads affects primary template lookup. As a result, interestingly enough, you can define the f<>(int *) full specialization twice in the program. One after (a) and another one after (c) and program compiles just fine!

template<class T> // (a) a base template
void f( T ) {
std::cout << "f(T)\n";
}

template<>
void f<>(int*) { // (b) an explicit specialization
std::cout << "f(int *) specilization\n";
}

template<class T> // (c) another, overloads (a)
void f( T* ) {
std::cout << "f(T *)\n";
}

template<>
void f<>(int*) { // (d) another identical explicit specialization
std::cout << "f(int *) another specilization\n";
}

int main (void) {
int *p = 0;
f(p);
}

What is the output here? Any guesses?

This program is an example of complexity that results due to orthogonality of C++ language. In simple terms, number of C++ features can co-exist and their interplay can baffle any uninitiated C++ programmer! I wonder how complex it would be once we have partial function template specialization support in standard C++ in 2009.

5 comments:

girman said...

Yes. It's interesting behavior.
As for me, I prefer to use not explicit specializations, but pure overloaded functions instead.

If you'll replace

template<>
void f<>(int*) { /*bla-bla-bla*/ }

with

void f(int*) { /*bla-bla-bla*/ }

problem will gone.

Not-template functions have always better match for compiler.

But.... I don't know... May be there are some situations, when we'll have to use only template specializations, and pure functions overloads wouldn't work?

Maxim Yegorushkin said...

Not sure, though, if you quoted the right excerpt. There is no partial specialisation for functions in the current standard. That excerpt applies to class templates only.

There is no reason for void f<>(int*) to be a full function template specialisation. If you make it just a function overload, as girman suggested, reordering the declarations will not produce surprising results.

Sumant said...

Good point! Using good old function overloading makes perfect sense and solves the problem of reordering. But after all the fun is in the least explored corners of C++. I added a para in the original post describing the better alternative of overloading. Having said that, is it a violation of Onde Definition Rule (ODR) to allow two identical full explicit function template specializations (f<>(int *))?

Maxim Yegorushkin said...

A quote from the blessed standard §3.2 One definition rule, clause 5:

There can be more than one definition of a class type (clause 9), enumeration type (7.2), inline function with external linkage (7.1.2), class template (clause 14), non-static function template (14.5.5), static data member of a class template (14.5.1.3), member function of a class template (14.5.1.1), or template specialization for which some template parameters are not specified (14.7, 14.5.4) in a program provided that each definition appears in a different translation unit, and provided the definitions satisfy the following requirements...

The implication of this clause is that full function specialisations obey the same rules as regular (non-template) functions, not function templates.

Here is an example:

// foo.h
template<class T> void foo(T) {}
template<> void foo(int) {}

If this header is included in more than one translation unit (.cc/.cpp), the linker complains about foo(int) being defined in several translation units, even if that specialisation is never used (called, or the address is taken).

To fix this, foo(int) specialisation needs to be declared inline, or static, or its definition must be removed from the header. On the other hand, function template need not be inline, as the standard provides relaxed one definition rules for templates.

The latter is often exploited to put static members in the headers. Exampe:

// some.h
struct some
{
static int member;
};
int some::member = 0;

This header is going to cause multiple some::member definition linker error when included in more than one translation unit. A workaround:

template<class T>
struct static_member
{
static T member;
};

// static data member of a class template (14.5.1.3),
// can be defined in many translation units.
template<class T>
T static_member<T>::member = T();

struct some : static_member<int>
{
// not a template, but still has its static member declared in the header.
};

Returning back to function templates, function overloading is often easier to deal with and can be used to simulate (non-existent) partial function specialisation:

template<class T> struct type {}; // boost::type<>
// generic implementation
template<class T, class U> void foo_impl(type<T>, type<U>);
// "partial" overload for second argument int
template<class T> void foo_impl(type<T>, type<int>);

template<class T, class U>
void foo() // interface for foo_impl
{
// convert template arguments to typed values,
// so that regular function overloading can be used.
foo_impl(type<T>(), type<U>());
}

int main()
{
foo<void, void>();
foo<void, int>();
}

xander345 said...

if you like c++ you can compile it online here: http://codecompiler.info/

32, 64 - windows & Linux - and more programming languages