Have you ever encountered strange cryptic errors messages involving deduction or substitution failures in your C++ templates and had a really tough time debugging them? This is a very common problem and probably the biggest that templates suffer from, the template instantiation process is very complex and contains various stages at which errors can occur. In my previous post I gave a brief example of template instantiation, in this post I break down the stages of the template instantiation process and explain what is happening under the hood.
If you’re still new to C++ templates you may want to check out my previous post on an introduction to templates.
A template declaration and it’s associated definition do not generate any code on their own, they defines a generic parameterized group of functions, member functions, classes, aliases or variables, from which an instance can be constructed.
When a template declaration is referenced in a context which requires an instance of that group, a non-generic declaration is constructed with a particular set of arguments. This process is often broadly referred to as ‘template instantiation’, however there are multiple stages involved and understanding these stages can be invaluable when writing and particularly debugging template code:
During this process the template declaration being instantiated can either be a regular template declaration, referred to as the primary template, or an explicit template specialization. During this process the resulting non-generic instance is represented by it’s template id, that in broadest terms is treated by the compiler as a regular non-template declaration.
When the compiler parses a name the first thing it must do is associate it with the declaration that introduced it; this process is known as name lookup.
This is where one of the first differences between types of template occurs. Name lookup for non-function templates such as a class, alias or variable template, must produce a single declaration, where as name lookup for function and member function templates can produce multiple declarations which are all instantiated and later passed to overload or specialization resolution where a single template id must be chosen.
There are two kinds of name lookup; qualified and unqualified. A qualified name lookup is performed when the name has an explicit namespace or class qualifier preceding it and will be limited to that specified scope and an unqualified name lookup is performed when the name does not and will look in multiple contexts. For example:
Name lookup is not explicitly part of the instantiation process, however there are some aspects of it that can directly effect the way in which instantiation is triggered, therefore it is important to mention.
One of these is two-phase lookup; the principle that a C++ compiler will compile your source code in two phases. In the first phase, all code is parsed and checked for general syntax, however only non-dependent names are compiled fully. In the second phase, dependent names are re-compiled once the template parameters those names depend on have been substituted.
A dependent name is one one that contains a non-substituted template parameter from a surrounding scope, such as a function or class template parameter.
As a simple example, consider the following function template:
The first function call takes as its argument, the integer literal
10, as this argument is non-dependent, the lookup can be performed immediately in the first phase. The second function call takes as it’s argument the function parameter
var, as this argument is dependent on the template parameter
T, the lookup must be deferred to the second phase, once the function template function ‘bar’ has been instantiated and
T has been substituted.
It is worth noting however, that not all C++ compilers implement two-phase lookup fully, some still adopt an early implementation method in which entire template definitions are deferred to the second phase, which can sometimes lead to invalid C++ code being accepted by the compiler, and therefore causing trouble for cross platform applications.
Argument Deduction and Substitution
For each template declaration returned by the name lookup, the compiler will construct a template id, with a specific set of template arguments. To do this, a template argument is determined and substituted into the template id for each template parameter of the template declaration.
There are three different ways in which template arguments can be determined, which influence how the arguments are substituted into the template id; they can be specified explicitly, they can be deduced from default template arguments and in the case of function and member function templates they can be deduced from the types of the function call arguments. The argument deduction and substitution is done in this order:
- Substitution of explicit template arguments
- Deduction of non-explicit template arguments
- Substitution of non-explicit template arguments
Substitution of Explicit Template Arguments
Template arguments that are specified explicitly are substituted into the template id first before non-explicit template arguments are deduced. Additionally explicitly specified template arguments are always substituted from left to right. For example:
Here the template parameter
T is determined from the explicit template explicit argument
Deduction of Non-Explicit Template Arguments
After explicit template arguments are substituted, the compiler will attempt to determine template arguments for the rest of the templates parameters. First, if the template is a function or member function template, it will then attempt to deduce each template argument from the types of the function parameters. For example:
Here the template argument
T is determined from the function parameter
Next the compiler will attempt to deduce each template argument from from a default argument if one is available. For example:
Here the template argument
T is determined from a default argument as
Note that unlike default function arguments, default template arguments do not have to be at the end of the parameter list.
Substitution of Non-Explicit Template Arguments
Once the compiler has successfully determined the non-explicit template arguments, it attempts to substitute those arguments into each corresponding template parameter of the template id.
This is where the substitution failure is not an error (SFINAE) principle is applied. SFINAE states that if a template id is ill formed as a result of a template argument substitution, then rather than triggering a error, the template id candidate is simply dropped and not considered for overload or specialisation resolution.
Once a valid template id declaration has been constructed with substituted template arguments, it is then added to the list of specializations for that template declaration, provided that template id declaration has not been added already.
The specialization process is generally triggered in this way, as an implicit pre-requisite to instantiation, however it can be triggered explicitly when an explicit template specialization directive is encountered.
Finally if the template declaration was referenced in a context which requires a definition and the template id has not previously been instantiation then the compiler will instantiate it, constructing a definition for the template id.
If the definition of the template being instantiated is not available at this point, for function or member function templates the instantiating of the definition is then deferred until the template definition appears in the translation unit, for class, alias or variable templates the compiler will trigger a error.
To do this he compiler will substitute all uses of the template declaration’s parameters within the associated definition, with the arguments of the template id, to construct a definition for the template id.
For example, consider a function template with three template parameters typename
T and int
D that defines a group of functions that take a parameter of type
T, construct a pointer of type
S, passing the parameter and the value of
D to the constructor and then returning the pointer:
When the function template is specialized a template id is constructed where, typename
S is specified explicitly as the type
T is deduced as the type ‘float’ form the argument
10.0f and int
D is deduced from the default argument as
Now when the function template definition is instantiated all uses of the templates parameters within the definition are substituted with the associated arguments from the template id.
Once the instantiation process is done the template id has a valid declaration and definition and is then inserted into the generated code. It is important to note here that at this point the template id must conform to the one definition rule (ODR).
Overload or Specialization Resolution
After argument deduction and substitution, specialization and instantiation has been performed for each template declaration returned by name lookup the compiler then performs overload or specialization resolution. This is the process by which the compiler chooses the best candidate from the function or member function overloads or from the class, alias or variable specializations and if no candidate can be chosen the compiler triggers an ambiguity error.