How are template definitions matched to template declarations?

Question

How exactly is a template declaration matched to a template definition? I found some text in the standard about template-ids referring to the same function if "their template-names [...] refer to the same template and [...]" (14.4 [temp.type] p1) but I can't find a definition for template-names or when template-names refer to the same template. I'm not sure if I'm on the right track anyway because I haven't deciphered the grammar well enough to tell if a template-id is part of the definition/declaration of a template, or just a use of a template.

For example, the following program works fine.

#include <iostream>

template<typename T>
T foo(T t);

int main() {
    foo(1);
}

template<typename T>
T foo(T t)
{ std::cout << "A\n"; return 0; }

If I change the way I use the template parameters in the template definition the names apparently no longer refer to the same template, and linking fails.

#include <iostream>

template<typename T>
T foo(T t);

int main() {
    foo(1);
}

template<typename T>
int foo(T t) { std::cout << "A\n"; return 0; }

// or

template<typename T>
struct identity {
    typedef T type;
};

template<typename T>
typename identity<T>::type
foo(T t) { std::cout << "A\n"; return 0; }

Next, if I move the template definition to another translation unit, for my implementation of C++ (MSVC 11 beta) the program works no matter how I say the types.

//main.cpp

template<typename T>
T foo(T t);

int main() {
    foo(1);
}

//definition.cpp
#include <iostream>

template<typename T>
struct identity {
    typedef T type;
};

template<typename T>
typename identity<T>::type
foo(T t) { std::cout << "A\n"; return 0; }

template int foo<int>(int);

or

//definition.cpp
#include <iostream>

template<typename T>
int foo(T t) { std::cout << "A\n"; return 0; }

template int foo<int>(int);

or even if the definition isn't a template at all:

//definition.cpp
#include <iostream>

int foo(T t) { std::cout << "A\n"; return 0; }

Obviously linking is succeeding because the signature/mangled name is the same regardless of the template that was instantiated to create the symbol. I think this undefined behavior because I'm violating:

§ 14.1 [temp] p6

A function template, member function of a class template, or static data member of a class template shall be defined in every translation unit in which it is implicitly instantiated (14.7.1) unless the corresponding specialization is explicitly instantiated (14.7.2) in some translation unit; no diagnostic is required.

But then say I try to fulfill those requirements by putting a definition of the template in the second translation unit, and including an explicit instantiation at one of two locations:

#include <iostream>

template<typename T>
T foo(T t) { std::cout << "A\n"; return 0; }

// Location 1    

template<typename T>
int foo(int t) { std::cout << "B\n"; return 0; }

// Location 2

What are the rules about disambiguating what template an explicit instantiation refers to? Putting it at Location 1 causes the correct template to be instantiated and that definition to be used in the final program, while putting it at Location 2 instantiates the other template, and causes what I believe is undefined behavior under 14.1 p6 above.

On the other hand an implicit instantiation of two templates definitions picks the first template no matter what, so it seems like the rule for disambiguating the templates is different in these circumstances:

#include <iostream>

template<typename T>
T foo(T t) { std::cout << "A\n"; return 0; }

template<typename T>
int foo(int t) { std::cout << "B\n"; return 0; }

int main() {
    foo(1); // prints "A"
}

The reason this came up is related to this question where the questioner discovered that a single forward declaration

template<typename T>
T CastScriptVarConst(const ScriptVar_t& s);

could not act as a declaration of multiple template definitions:

template<typename T>
typename std::enable_if<GetType<T>::value < SVT_BASEOBJ,T>::type
CastScriptVarConst(const ScriptVar_t& s) {
    return (T) s;
}

template<typename T>
typename std::enable_if<!(GetType<T>::value < SVT_BASEOBJ)
                        && std::is_base_of<CustomVar,T>::value,T>::type
CastScriptVarConst(const ScriptVar_t& s) {
    return *s.as<T>();
}

And I wanted to better understand the relationship between template definitions and declarations.

Answer 1

OK, let's start from the beginning. The "template-name" of a template is the actual name of the function or class being templated; that is, in

template<class T> T foo(T t);

foo is the template name. For function templates, the rule for deciding whether they are the same is quite long, described in 14.5.5.1 "Function template overloading". Paragraph 6 of that section (I'm quoting from C++03 here, so the wording and paragraph numbers might have changed in C++11) defines the terms equivalent and functionally equivalent, when applied to expressions involving template parameters.

In short, equivalent expressions are the same apart from possibly having different names for template parameters, and functionally equivalent expressions are the same if they happen to evaluate to the same thing. For example, the first two f declarations are equivalent, but the third is only functionally equivalent to the other two:-

template<int A, int B>
void f(array<A + B>);
template<int T1, int T2>
void f(array<T1 + T2>);
template<int A, int B>
void f(array< mpl::plus< mpl::int<A>, mpl::int<B> >::value >);

It goes on in paragraph 7 to extend those two definitions to whole function templates. Two function templates that match (in name, scope, and template parameter lists) are equivalent if they also have equivalent return types and argument types, or functionally equivalent if they only have functionally equivalent return types and argument types. Looking at your second example, these two functions are only functionally equivalent:-

template<typename T>
T foo(T t);

template<typename T>
typename identity<T>::type foo(T t);

Paragraph 7 closes with the dire warning that, "If a program contains declarations of function templates that are functionally equivalent but not equivalent, the program is ill-formed; no diagnostic is required." Your second example is, thus, not valid C++. Detecting errors like that would require each declaration and definition of a function template to be annotated in the binary with an AST describing the template expression each parameter and the return type came from, which is why the standard doesn't require implementations to detect it. MSVC is justified in compiling your third example how you intended, but it would be just as justified to break.

Moving on to explicit instantiation, the important section is 14.7, "Template instantiation and specialization". Paragraph 5 disallows all of the following:

• Explicitly instantiating a template more than once;
• Explicitly instantiating and explicitly specializing the same template;
• Explicitly specializing a template for the same set of arguments more than once.

Again, "no diagnostic is required" as it's quite hard to detect.

So to expand your explicit instantiation example, the following code breaks the second rule and is illegal :-

/* Template definition. */
template<typename T>
T foo(T t)
{ ... }

/* Specialization, OK in itself. */
template< >
int foo(int t)
{ ... }

/* Explicit instantiation, OK in itself. */
template< >
int foo(int t);

This is illegal regardless of the locations of the explicit specialization and the explicit instantiation, but of course because no diagnostic is required, you may get useful results on some compilers. Note also the difference between explicit instantiation and explicit specialization. The following example is ill-formed because it declares an explicit specialization without defining it:-

template<typename T>
T f(T f)
{ ... }

template< >
int f(int);

void g(void)
{ f(3); }

but this example is well-formed, because it has an explicit instantiation:-

template<typename T>
T f(T f)
{ ... }

template f(int);

void g(void)
{ f(3); }

The < > makes all the difference. Be warned also that even when you do define an explicit specialization, it has to be before you use it, otherwise the compiler might already have generated an implicit instantiation for that template. This is in 14.7.3 "Explicit specialization" paragraph 6, just below where you were reading, and again, no diagnostic is required. To adapt the same example, this is ill-formed:-

template<typename T>
T f(T f)
{ ... }

void g(void)
{ f(3); } // Implicitly specializes int f(int)

template< >
int f(int) // Too late for an explicit specialization
{ ... }

If you weren't confused enough yet, take a look at your last example:-

template<typename T>
T foo(T t) { ... }

template<typename T>
int foo(int t) { ... }

The second definition of foo is not a specialization of the first definition. It would have to be template< > int foo(int) to be a specialization of template<typename T> T foo(T). But that's OK: function overloading is allowed, and it's allowed between function templates and normal functions. Calls of the form foo(3) will always use the first definition, because its template parameter T can be deduced from the argument type. The second definition does not allow its template parameter to be deduced from the argument type. Only by explicitly specifying T can you reach the second definition, and only then when the call is not ambiguous with the first definition:-

f<int>(3); // ambiguous
f<string>(3); // can only be the second one

The whole process of doing overload resolution for function templates is too long to describe here. Read section 14.8.3 if you're interested and ask more questions :-)