The C++ Instantiation Model





The C++ Instantiation Model

Template instantiation is the process of obtaining a regular class or function from a corresponding template entity by appropriately substituting the template parameters. This may sound fairly straightforward, but in practice many details need to be formally established.

1 Two-Phase Lookup

In Chapter 9 we saw that dependent names cannot be resolved when parsing templates. Instead, they are looked up again at the point of instantiation. Nondependent names, however, are looked up early so that many errors can be diagnosed when the template is first seen. This leads to the concept of two-phase lookup [5]: The first phase is the parsing of a template, and the second phase is its instantiation.

[5] Beside two-phase lookup, terms such as two-stage lookup or two-phase name lookup are also used.

During the first phase, nondependent names are looked up while the template is being parsed using both the ordinary lookup rules and, if applicable, the rules for argument-dependent lookup (ADL). Unqualified dependent names (which are dependent because they look like the name of a function in a function call with dependent arguments) are also looked up that way, but the result of the lookup is not considered complete until an additional lookup is performed when the template is instantiated.

During the second phase, which occurs when templates are instantiated at a point called the point of instantiation (POI), dependent qualified names are looked up (with the template parameters replaced with the template arguments for that specific instantiation), and an additional ADL is performed for the unqualified dependent names.

2 Points of Instantiation

We have already illustrated that there are points in the source of template clients where a C++ compiler must have access to the declaration or the definition of a template entity. A point of instantiation (POI) is created when a code construct refers to a template specialization in such a way that the definition of the corresponding template needs to be instantiated to create that specialization. The POI is a point in the source where the substituted template could be inserted. For example:

class MyInt { 
  public: 
   MyInt(int i); 
}; 

MyInt operator - (MyInt const&); 

bool operator > (MyInt const&, MyInt const&); 
typedef MyInt Int; 

template<typename T> 
void f(T i) 
{ 
    if (i>0) { 
        g(-i); 
    } 
} 
// (1) 
void g(Int) 
{ 
    // (2) 
    f<Int>(42);  // point of call 
    // (3) 
} 
// (4) 

When a C++ compiler sees the call f<Int>(42), it knows the template f will need to be instantiated for T substituted with MyInt: A POI is created. Points (2) and (3) are very close to the point of call, but they cannot be POIs because C++ does not allow us to insert the definition of ::f<Int>(Int) there. The essential difference between point (1) and point (4) is that at point (4) the function g(Int) is visible, and hence the template-dependent call g(-i) can be resolved. However, if point (1) were the POI, then that call could not be resolved because g(Int) is not yet visible. Fortunately, C++ defines the POI for a reference to a nonclass specialization to be immediately after the nearest namespace scope declaration or definition that contains that reference. In our example, this is point (4).

You may wonder why this example involved the type MyInt rather than simple int. The answer lies in the fact that the second lookup performed at the POI is only an ADL. Because int has no associated namespace, the POI lookup would therefore not take place and would not find function g. Hence, if you were to replace the typedef for Int with

typedef int Int; 

the previous example should no longer compile. [6]

[6] In 2002 the C++ standardization committee was still investigating alternatives that would make the example valid with the latter typedef.

For class specializations, the situation is different, as the following example illustrates:

template<typename T> 
class S { 
  public: 
    T m; 
}; 
// (5) 
unsigned long h() 
{ 
    // (6) 
    return (unsigned long)sizeof(S<int>); 
    // (7) 
} 
// (8) 

Again, the function scope points (6) and (7) cannot be POIs because a definition of a namespace scope class S<int> cannot appear there (and templates cannot appear in function scope). If we were to follow the rule for nonclass instances, the POI would be at point (8), but then the expression sizeof(S<int>) is invalid because the size of S<int> cannot be determined until point (8) is reached. Therefore, the POI for a reference to a generated class instance is defined to be the point immediately before the nearest namespace scope declaration of definition that contains the reference to that instance. In our example, this is point (5).

When a template is actually instantiated, the need for additional instantiations may appear. Consider a short example:

template<typename T> 
class S { 
  public: 
    typedef int I; 
}; 

// (1) 
template<typename T> 
void f() 
{ 
    S<char>::I var1 = 41; 
    typename S<T>::I var2 = 42; 
} 

int main() 
{ 
    f<double>(); 
} 
// (2): (2a), (2b) 

Our preceding discussion already established that the POI for f<double> is at point (2). The function template f() also refers to the class specialization S<char> with a POI that is therefore at point (1). It references S<T> too, but because this is still dependent, we cannot really instantiate it at this point. However, if we instantiate f<double> at point (2), we notice that we also need to instantiate the definition of S<double>. Such secondary or transitive POIs are defined slightly differently. For nonclass entities, the secondary POI is exactly the same as the primary POI. For class entities, the secondary POI immediately precedes (in the nearest enclosing namespace scope) the primary POI. In our example, this means that the POI of f<double> can be placed at point (2b), and just before it—at point (2a)—is the secondary POI for S<double>. Note how this differs from the POI for S<char>.

A translation unit usually contains multiple POIs for the same instance. For class template instances, only the first POI in each translation unit is retained, and the subsequent ones are ignored (they are not really considered POIs). For nonclass instances, all POIs are retained. In either case, the ODR requires that the instantiations occurring at any of the retained POIs be equivalent, but a C++ compiler does not need to verify and diagnose violations of this rule. This allows a C++ compiler to pick just one nonclass POI to perform the actual instantiation without worrying that another POI might result in a different instantiation.

In practice, most compilers delay the actual instantiation of noninline function templates to the end of the translation unit. This effectively moves the POIs of the corresponding template specializations to the end of the translation unit. The intention of the C++ language designers was for this to be a valid implementation technique, but the standard does not make this clear.

3 The Inclusion and Separation Models

Whenever a POI is encountered, the definition of the corresponding template must somehow be accessible. For class specializations this means that the class template definition must have been seen earlier in the translation unit. For nonclass POIs this is also possible, and typically nonclass template definitions are simply added to header files that are #included into the translation unit. This source model for template definitions is called the inclusion model, and at the time of this writing it is by far the most popular approach.

For nonclass POIs an alternative exists: The nonclass template can be declared using export and defined in another translation unit. This is known as the separation model. The following code excerpt illustrates this with our perennial max() template:

// Translation unit 1: 
#include <iostream> 
export template<typename T> 
T const& max (T const&, T const&); 

int main() 
{ 
    std::cout << max(7, 42) << std::endl;   // (1) 
} 

// Translation unit 2: 
export template<typename T> 
T const& max (T const& a, T const& b) 
{ 
    return a<b?b:a; // (2) 
} 

When compiling the first file, a compiler will notice the POI for T substituted with int created by the statement at point (1). The compilation system must then make sure that the definition in the second file is instantiated to satisfy that POI.

Looking Across Translation Units

Suppose the first file just shown (translation unit 1) is rewritten as follows:

// Translation unit 1: 
#include <iostream> 
export template<typename T> T const& max(T const&, T const&); 

namespace N { 
   class I { 
     public: 
       I(int i): v(i) {} 
       int v; 
   }; 

   bool operator < (I const& a, I const& b) { 
       return a.v<b.v; 
   } 
} 

int main() 
{ 
   std::cout << max(N::I(7), N::I(42)).v << std::endl;  // (3) 
} 

The POI created at point (3) again requires the definition in the second file (translation unit 2). However, this definition uses the < operator which now refers to the overloaded operator declared in translation unit 1 and which is not visible in translation unit 2. For this to work, it is clear that the instantiation process needs to refer to two different declaration contexts. [7] The first context is the one in which the template is defined, and the second context is the one in which type I is declared. To involve these two contexts, names in templates are therefore looked up in two phases as explained in Section 10.3.1 on page 146.

[7] A declaration context is the collection of all declarations accessible at a given point.

The first phase occurs when templates are parsed (in other words, when a C++ compiler first sees the template definition). At this stage, nondependent names are looked up using both the ordinary lookup rules and the ADL rules. In addition, unqualified names of functions that are dependent (because their arguments are dependent) are looked up using the ordinary lookup rules, but the result is memorized without attempting overload resolution—this is done after the second phase.

The second phase occurs at the point of instantiation. At this point, dependent qualified names are looked up using both ordinary and argument-dependent lookup rules. Dependent unqualified names (which were looked up using ordinary lookup rules during the first phase) are now looked up using ADL rules only, and the result of the ADL is then combined with the result of the ordinary lookup that occurred during the first phase. It is this combined set that is used to select the called function through overload resolution.

Although this two-phase lookup mechanism seems essential to enable the separation model, it is also the mechanism used with the inclusion model. However, many early implementations of the inclusion model delayed all lookups until the point of instantiation. [8]

[8] This results in a behavior that is close to what you'd expect from a macro expansion mechanism.

5 Examples

A few examples illustrate more effectively the effect of what we just described. Our first example is a simple case of the inclusion model:

template<typename T> 
void f1(T x) 
{ 
    g1(x); // (1) 
} 

void g1(int) 
{ 
} 

int main() 
{ 
    f1(7);  // ERROR: g1 not found! 
}           // (2) POI for f1<int>(int) 

The call f1(7) creates a point of instantiation for f1<int>(int) just outside of main() function (at point (2)). In this instantiation, the key issue is the lookup of function g1. When the definition of the template f1 is first encountered, it is noted that the unqualified name g1 is dependent because it is the name of a function in a function call with dependent arguments (the type of the argument x depends on the template parameter T). Therefore, g1 is looked up at point (1) using ordinary lookup rules; however, no g1 is visible at this point. At point (2), the POI, the function is looked up again in associated namespaces and classes, but the only argument type is int, and it has no associated namespaces and classes. Therefore, g1 is never found even though ordinary lookup at the POI would have found g1.

The second example demonstrates how the separation model can lead to overload ambiguities across translation units. The example consists of three files (one of which is a header file):

// File common.hpp: 
export template<typename T> 
void f(T); 

class A { 
}; 
class B { 
}; 

class X { 
  public: 
    operator A() { return A(); } 
    operator B() { return B(); } 
}; 

// File a.cpp: 
#include "common.hpp" 

void g(A) 
{ 
} 

int main() 
{ 
    f<X>(X()); 
} 

// File b.cpp: 
#include "common.hpp" 

void g(B) 
{ 
} 

export template<typename T> 
void f(T x) 
{ 
    g(x); 
} 

The main() function calls f<X>(X()) in file a.cpp which resolves to the exported template defined in file b.cpp. The call g(x) is therefore instantiated with an argument of type X. Function g() is looked up twice: once using ordinary lookup in file b.cpp (when the template is parsed) and once using ADL in file a.cpp (where the template is instantiated). The first lookup finds g(B), and the second lookup finds g(A). Both are viable functions through a user-defined conversion, and hence the call is really ambiguous.

Note that in file b.cpp the call g(x) does not seem ambiguous at all. It is the two-phase lookup mechanism that brings in possibly unexpected candidate functions. Extreme care should therefore be taken when writing and documenting exported templates.


     Python   SQL   Java   php   Perl 
     game development   web development   internet   *nix   graphics   hardware 
     telecommunications   C++ 
     Flash   Active Directory   Windows