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.