关于本章

编译器如何编译template？这个问题其实是在探讨编译器是如何实现模板的，本章对这个问题进行展开，描述C++ template的实现。理解template的实现，对于掌握、运用template至关重要。

遗憾的是，在cppreference中，并沒有对此的专门描述，我们只能够搜集一些素材自己進行总结。这个问题也可以通过如下的方式进行Google：

1、Google c++ template mechanism

2、Google c++ compiler template

Template is a kind of static polymorphism

Template is a kind of static polymorphism，对于这个结论，我们需要从下面两个方面进行深入的分析：

1) 从“polymorphism”：既然template是一种polymorphism，那么它的实现思路可以使用在Polymorphism中描述的思想

2) 从“static”：既然是static，那么

它就发生于compile-time
“The definition of a template must be visible at the point of implicit instantiation, which is why template libraries typically provide all template definitions in the headers”（截取自cppreference Templates）
它运用的是static type info

Specialization and instantiation of template

本节描述Specialization and instantiation of template，下面是涉及这个主题的素材。

"specialization"的含义是"特化"，"instantiation"的含义是"实例化"。

cppreference Templates

When template arguments are provided, or, for function and class (since C++17) templates only, deduced, they are substituted for the template parameters to obtain a specialization of the template, that is, a specific type or a specific function lvalue.

NOTE: specification的结果是：a specific type、a specific function lvalue。

Specializations may also be provided explicitly:

full specializations are allowed for class, variable (since C++14) and function templates.

partial specializations are only allowed for class templates and variable templates (since C++14).

NOTE: specialization的分类：

1 explicit specialization：

full specialization

partial specialization

2 implicit specialization：deduced。

NOTE: function template不支持partial specialization，但是通过enable_if + SFINAE + trait技术，也可以实现类似于partial specialization的效果，这通常被称为function template SFINAE，在SFINAE\Function-template-SFINAE.md中对它进行了介绍。

When a class template specialization is referenced in context that requires a complete object type, or when a function template specialization is referenced in context that requires a function definition to exist, the template is instantiated (the code for it is actually compiled), unless the template was already explicitly specialized or explicitly instantiated. Instantiation of a class template doesn't instantiate any of its member functions unless they are also used.

NOTE: lazyness特性，在后面会进行介绍。

At link time, identical instantiations generated by different translation units are merged.

NOTE: 不同的translation unit，可能instantiate了同一个template，显然，它们就包含了相同的instantiation，也就是相同的definition，对于这种情况，一般情况下，compiler是会报multiple definition的，但是对于template，它是会进行特殊处理的。

The definition of a template must be visible at the point of implicit instantiation, which is why template libraries typically provide all template definitions in the headers (e.g. most boost libraries are header-only)

NOTE: 什么叫做implicit instantiation？

这一段，其实解释了一个问题：

Why can templates only be implemented in the header file?

其实，我们完全可以从template的static特性出发来进行理解，关于这一点，在“Template is a kind of static polymorphism”中进行了说明。

Specialization and instantiation of template

顺序: specialization->instantiation，即先specialization，然后instantiation，instantiation发生在实际使用specialization的时候。必须使用specialization of template，才能够instantiation 一个template。

specialization是对一种特殊情况的特殊实现，specialization相当于OOP中的inheritance；

NOTE: 关于specialization VS inheritance，参见C++\Language-reference\Template\Class-template\Class-template-specialization\Specialization-VS-subclass

instantiation 是compiler真正的实现代码。

Lazyness of template instantiation

cppreference Templates中的“Instantiation of a class template doesn't instantiate any of its member functions unless they are also used.”其实已经揭示了lazyness of template instantiation。正如在process中有copy-on-write，template instantiation是instantiation-on-use，后续将"Lazyness of template instantiation"简称为lazy initialization。

下面是member function被使用的场景(也就是它被instance的时候)

1) called(被调用)

借助于Lazyness of template instantiation，我们可以实现conditional compiling，这在C-family-language\C++\Idiom\Template-metaprogramming\SFINAE-trait-enable-if\SFINAE.md#SFINAE and conditional compiling中进行了详细介绍。

NOTE: Lazyness of template instantiation让我联想到了维基百科Type system#Static type checking中关于if <complex test> then <do something> else <signal that there is a type error>的讨论，显然，它是一种run-time lazy；Lazyness of template instantiation是一种compile-time lazy。

CRTP

CRTP是充分运用Lazyness of template instantiation特性的，关于此在wikipedia Curiously recurring template pattern 中给出的了详细的介绍，通过CRTP的学习，我们能够进一步地反过来思考Lazyness of template instantiation特性。在Generic-programming\Curiously-recurring-template-pattern章节中收录了wikipedia Curiously recurring template pattern ，其中对这个话题进行了深入的分析。

完整的编译过程

需要对template的完整的编译过程有一个高屋建瓴的理解，目前还没有遇到专门描述的文章；可以肯定的是：这个完整的过程，包含了前面描述的一些步骤，但是compiler需要考虑的问题，比上面描述的要多得多。下面是我总结的描述这个问题的内容:

1、deduce

2、substitute

3、Primary template and template specializaiton

4、SFINAE

下面的内容主要以void_t的实现为例来进行说明的，参考了如下文章:

1、stackoverflow How does void_t work

在后面的"4 Example: stackoverflow How does void_t work"章节中，收录了这篇文章

2、riptutorial C++ void_t

在后面的"5 Example: riptutorial C++ void_t "章节中，收录了这篇文章

1 先deduce 然后 substitute

“先deduce 然后 substitute”是我在阅读stackoverflow How does void_t work时所总结的，显然它描述了compiler实现template的一个重要过程。

Parameter-list and argument-list

在cppreference中，并没有给出parameter-list、argument-list的专门定义，而是在**template syntax**中提及了它们，为了便于后面的描述，现对它们两者进行说明，下面是引用cppreference Partial template specialization中的描述:

template < parameter-list > class-key class-head-name < argument-list > declaration

从上面的描述可以看到：parameter-list、argument-list。

Template argument: provided or deduced

本节标题描述的是：获得template argument的两种方式：

1、provided：由programmer 显式提供

2、deduced：由compiler 隐式提供；在C++\Language-reference\Template\Implementation\Argument-deduction章节进行专门分析

本节标题中的内容是源自：素材: cppreference Templates。

需要注意的是：先deduce 然后 substitute。

Deduction

在Template-argument-deduction中对这个问题进行了描述。

Substitution: argument->parameter

本节标题的含有是：将template argument 赋给 template parameter的过程，在C++ template的世界中，一般叫做 substitution。

substitution是compiler编译template的过程中的非常重要的一个环节，它其实就是template specialization过程；

关于substitution，在下面的文章中提及了：

thegreenplace SFINAE and enable_if
wikipedia Substitution failure is not an error

cppreference Partial template specialization#The argument list

2 Primary template and template specializaiton

最最简单的情况是，仅仅存在**primary template**，此时compiler仅仅根据primary template进行instantiation of template即可。比较复杂的情况是：当存在多个specialization of template的时候，compiler如何选择set of candidates中的哪个specialization of template进行instantiation？这就是“How dose compiler select from a set of candidates？”。

这个过程还是比较复杂的，目前还没有遇到专门描述的文章。

在stackoverflow How does void_t work中有所涉及，下面是阅读该文章的一些总结：

1、compiler会逐个substitute Primary Class Template、Specialized Class Template

2、首先根据Primary Class Template的替换结果，得到**template parameter list**，然后使用它；

如果存在template specialization，则将根据Primary Class Template得到的**template parameter list**代入到template specialization中，如果template specialization能够匹配**template parameter list**，那么它就是一个有效的，在后面的比较中，会考虑这个template specialization。需要注意的是: compiler会根据**template parameter list**来推导出template specialization的template argument，这个过程非常重要( 典型的案例是 stackoverflow Check if a class has a member function of a given signature # A )。将template parameter list代入到template specialization中，然后进行匹配的过程，是需要结合具体的案例来进行理解的，后面的"案例学习: template specialization and trait"章节中，就收录非常具有代表性的例子。

3、优先级顺序是：Specialized Class Template specialization > Primary Class Template specialization，即compiler会优先选择 "Specialized Class Template specialization"，这就是一次多态

参见: cppreference Partial template specialization#Partial ordering

Partial template specialization是primary template的附庸

本节的观点是我在阅读cppreference Partial template specialization#Name lookup时所总结的，我觉得这个观点对于理解C++ template机制非常重要，下面是论证这个观点的文章:

cppreference Partial template specialization#Name lookup

Partial template specializations are not found by name lookup. Only if the primary template is found by name lookup, its partial specializations are considered. In particular, a using declaration that makes a primary template visible, makes partial specializations visible as well.

NOTE: 上面这段话的意思，翻译为白话就是: compiler只有在看见了primary template的时候，才会考虑partial template specialization，因此可以认为，partial template specialization是primary template的附庸，在素材: stackoverflow How does void_t work中还会涉及到这个问题。

NOTE: 下面这个例子，着重展示的是上面这段话中，using部分的内容。

#include<iostream>

namespace N
{
// primary template
template<class T1, class T2> class Z
{
public:
    Z()
    {
        std::cout << __PRETTY_FUNCTION__ << std::endl;
    }
};

}
using N::Z; // refers to the primary template
namespace N
{
// partial specialization    
template<class T> class Z<T, T*>
{
public:
    Z()
    {
        std::cout << __PRETTY_FUNCTION__ << std::endl;
    }
};

}
Z<int, int*> z; // name lookup finds N::Z (the primary template),
                // the partial specialization with T = int is then used
int main()
{

}
// g++ test.cpp

NOTE: 上述程序的输出如下:
N::Z<T, T*>::Z() [with T = int]

cppreference Function template#Function overloads vs function specializations

参见C++\Language-reference\Template\Function-template\index.md，其中进行了详细分析。

cppreference Partial template specialization#Partial ordering

When a class or variable (since C++14) template is instantiated, and there are partial specializations available, the compiler has to decide if the primary template is going to be used or one of its partial specializations.

1) If only one specialization matches the template arguments, that specialization is used

2) If more than one specialization matches, partial order rules are used to determine which specialization is more specialized. The most specialized specialization is used, if it is unique (if it is not unique, the program cannot be compiled)

3) If no specializations match, the primary template is used

// primary template
template<class T1, class T2, int I>
class A
{
};

// #1: partial specialization where T2 is a pointer to T1
template<class T, int I>
class A<T, T*, I>
{
};

// #2: partial specialization where T1 is a pointer
template<class T, class T2, int I>
class A<T*, T2, I>
{
};

// #3: partial specialization where T1 is int, I is 5,
//     and T2 is a pointer
template<class T>
class A<int, T*, 5>
{
};

// #4: partial specialization where T2 is a pointer
template<class X, class T, int I>
class A<X, T*, I>
{
};
int main()
{
    // given the template A as defined above
    A<int, int, 1> a1;   // no specializations match, uses primary template
    A<int, int*, 1> a2;  // uses partial specialization #1 (T=int, I=1)
    A<int, char*, 5> a3; // uses partial specialization #3, (T=char)
    A<int, char*, 1> a4; // uses partial specialization #4, (X=int, T=char, I=1)
    // A<int*, int*, 2> a5; // error: matches #2 (T=int, T2=int*, I=2)
                         //        matches #4 (X=int*, T=int, I=2)
                         // neither one is more specialized than the other
}
// g++ test.cpp

Informally "A is more specialized than B" means "A accepts a subset of the types that B accepts".

Formally, to establish more-specialized-than relationship between partial specializations, each is first converted to a fictitious function template as follows:

1、the first function template has the same template parameters as the first partial specialization and has just one function parameter, whose type is a class template specialization with all the template arguments from the first partial specialization

2、the second function template has the same template parameters as the second partial specialization and has just one function parameter whose type is a class template specialization with all the template arguments from the second partial specialization.

The function templates are then ranked as if for function template overloading.

#include <iostream>
// primary template
template<int I, int J, class T> struct X
{
};
// partial specialization #1
template<int I, int J> struct X<I, J, int>
{
    static const int s = 1;
};
// fictitious function template for #1 is
// template<int I, int J> void f(X<I, J, int>); #A

// partial specialization #2
template<int I> struct X<I, I, int>
{
    static const int s = 2;
};
// fictitious function template for #2 is
// template<int I>        void f(X<I, I, int>); #B

int main()
{
    X<2, 2, int> x; // both #1 and #2 match
// partial ordering for function templates:
// #A from #B: void(X<I,J,int>) from void(X<U1, U1, int>): deduction ok
// #B from #A: void(X<I,I,int>) from void(X<U1, U2, int>): deduction fails
// #B is more specialized
// #2 is the specialization that is instantiated
    std::cout << x.s << '\n'; // prints 2
}
// g++ test.cpp

NOTE: 上述过程没有理解

案例学习: template specialization and trait

要想完整地理解compiler编译"Primary template and template specializaiton"的过程，还需要结合具体的案例，最最典型的案例就是基于template specialization来实现trait，下面是一些具体案例:

accu An introduction to C++ Traits # `is_pointer`

#include <iostream>

template<typename T>
struct is_pointer
{
    static const bool value = false;
};

template<typename T>
struct is_pointer<T*>
{
    static const bool value = true;
};

int main()
{
    // for any type T other than void, the
    // class is derived from false_type
    std::cout << is_pointer<char>::value << '\n';
    // but when T is void, the class is derived
    // from true_type
    std::cout << is_pointer<void*>::value << '\n';
}

1、is_pointer<void*> 根据 primary template 得到的 template parameter list是: void*

2、将template parameter list void* 代入到template specialization中，能够正常匹配因此，这个specialization是一个有效的specialization。

template<typename T>
struct is_pointer<T*>

3、比较，显然会选择 specialization is_pointer<T*>

cppreference std::is_member_function_pointer

#include<type_traits>
template<class T>
struct is_member_function_pointer_helper: std::false_type
{
};

template<class T, class U>
struct is_member_function_pointer_helper<T U::*> : std::is_function<T>
{
};

template<class T>
struct is_member_function_pointer: is_member_function_pointer_helper<typename std::remove_cv<T>::type>
{
};
class A {
public:
    void member() { }
};

int main()
{
    // fails at compile time if A::member is a data member and not a function
    static_assert(std::is_member_function_pointer<decltype(&A::member)>::value,
                  "A::member is not a member function."); 
}

stackoverflow Check if a class has a member function of a given signature # A

#include <type_traits>
#include <iostream>
// Primary template with a static assertion
// for a meaningful error message
// if it ever gets instantiated.
// We could leave it undefined if we didn't care.

template<typename, typename T>
struct has_serialize
{
    static_assert(std::integral_constant<T, false>::value, "Second template parameter needs to be of function type.");
};

// specialization that does the checking
template<typename C, typename Ret, typename ... Args>
struct has_serialize<C, Ret(Args...)>
{
private:
    template<typename T>
    static constexpr auto check(T*) -> typename
    std::is_same<
    decltype( std::declval<T>().serialize( std::declval<Args>()... ) ),
    Ret    // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    >::type;// attempt to call it and see if the return type is correct

    template<typename >
    static constexpr std::false_type check(...);

    typedef decltype(check<C>(0)) type;

public:
    static constexpr bool value = type::value;
};

struct X
{
    int serialize(const std::string&)
    {
        return 42;
    }
};

struct Y: X
{
};

struct Z
{
};
int main()
{
    std::cout << has_serialize<Y, int(const std::string&)>::value << std::endl; // will print 1
    std::cout << has_serialize<Z, int(const std::string&)>::value << std::endl; // will print 1
}
// g++ --std=c++11 test.cpp

1、has_serialize<Y, int(const std::string&)>根据 primary template 得到的 template parameter list是 int(const std::string&)>

2、将template parameter list int(const std::string&)>代入到template specialization中，能够正常匹配因此，这个specialization是一个有效的specialization。

template<typename C, typename Ret, typename ... Args>
struct has_serialize<C, Ret(Args...)>
{
};

compiler能够根据 template parameter list 推到出template specialization的parameter C、Ret、Args 的argument。

SFINAE

SFINAE是C++ template的重要机制，在SFINAE章节中对SFINAE进行了深入分析。

4 Example: stackoverflow How does `void_t` work # A

這是我在学习void_t的实现的時候，遇到的一篇讲解的比较详细的、涉及template的实现的文章，我覺得非常好，遂收录在此。它结合了一个具体的案例对这个过程进行描述，非常好。

Given a simple variable template that evaluates to void if all template arguments are well formed:

#include <type_traits> // std::true_type

template<class ... >
using void_t = void;
// primary template
template<class, class = void>
struct has_member: std::false_type
{
};

// specialized as has_member< T , void > or discarded (sfinae)
template<class T>
struct has_member<T, void_t<decltype( T::member )> > : std::true_type
{
};
class A
{
public:
    int member;
};

class B
{
};
int main()
{
    static_assert( has_member< A >::value , "A" );
    static_assert( has_member< B >::value , "B" );
}

// g++ --std=c++11 test.cpp

1、Primary Class Template

When you write has_member<A>::value, the compiler looks up the name has_member and finds the primary class template, that is, this declaration:

template< class , class = void >
struct has_member;

(In the OP, that's written as a definition.)

The template argument list <A> is compared to the template parameter list of this primary template. Since the primary template has two parameters, but you only supplied one, the remaining parameter is defaulted to the default template argument: void. It's as if you had written has_member<A, void>::value.

NOTE:

1、上面这段话中的“template argument list <A> ”对应的是“has_member<A>::value”中的A。

2、compiler会编译source file，source file中，会include定义了primary class template、specialized class template 的header file，所以compiler会同时看到primary class template、specialized class template，并且primary class template在specialized class template之前。

3、上面这段话中的**template parameter list**非常重要，后面会使用给它。

2、Specialized Class Template

Now, the template parameter list is compared against any specializations of the template has_member. Only if no specialization matches, the definition of the primary template is used as a fall-back. So the partial specialization is taken into account:

template< class T >
struct has_member< T , void_t< decltype( T::member ) > > : true_type
{ };

The compiler tries to match the template arguments A, void with the patterns defined in the partial specialization: T and void_t<..> one by one. First, template argument deduction is performed. The partial specialization above is still a template with template-parameters that need to be "filled" by arguments.

NOTE:

先deduce，然后进行substitute。

上面这段话中的“filled”，其实就是substitute的意思。

The first pattern T, allows the compiler to deduce the template-parameter T. This is a trivial deduction, but consider a pattern like T const&, where we could still deduce T. For the pattern T and the template argument A, we deduce T to be A.

In the second pattern void_t< decltype( T::member ) >, the template-parameter T appears in a context where it cannot be deduced from any template argument.

There are two reasons for this:

1、The expression inside decltype is explicitly excluded from template argument deduction. I guess this is because it can be arbitrarily complex.

2、Even if we used a pattern without decltype like void_t< T >, then the deduction of T happens on the resolved alias template. That is, we resolve the alias template and later try to deduce the type T from the resulting pattern. The resulting pattern, however, is void, which is not dependent on T and therefore does not allow us to find a specific type for T. This is similar to the mathematical problem of trying to invert a constant function (in the mathematical sense of those terms).

NOTE: 关于decltype是Non-deduced contexts，参加cppreference Template argument deduction，其中有专门说明。

Template argument deduction is finished(*), now the deduced template arguments are substituted. This creates a specialization that looks like this:

NOTE: 先deduce，然后进行substitute

template<>
struct has_member< A, void_t< decltype( A::member ) > > : true_type
{ };

The type void_t< decltype( A::member ) > can now be evaluated. It is well-formed after substitution, hence, no Substitution Failure occurs. We get:

template<>
struct has_member<A, void> : true_type
{ };

3、Choice

Now, we can compare the template parameter list of this specialization with the template arguments supplied to the original has_member<A>::value. Both types match exactly, so this partial specialization is chosen.

On the other hand, when we define the template as:

// primary template
template< class , class = int > // <-- int here instead of void
struct has_member : false_type
{ };
// specializaiton template
template< class T >
struct has_member< T , void_t< decltype( T::member ) > > : true_type
{ };

We end up with the same specialization:

template<>
struct has_member<A, void> : true_type
{ };

but our template argument list for has_member<A>::value now is <A, int>. The arguments do not match the parameters of the specialization, and the primary template is chosen as a fall-back.

NOTE: 这段话的意思是：只有primary template的argument-list和specialization的argument-list的一致的时候，才会选择specializaiton，这再次验证了在前面总结的:

partial template specialization是primary template的附庸

(*) The Standard, IMHO confusingly, includes the substitution process and the matching of explicitly specified template arguments in the template argument deduction process. For example (post-N4296) [temp.class.spec.match]/2:

A partial specialization matches a given actual template argument list if the template arguments of the partial specialization can be deduced from the actual template argument list.

But this does not just mean that all template-parameters of the partial specialization have to be deduced; it also means that substitution must succeed and (as it seems?) the template arguments have to match the (substituted) template parameters of the partial specialization. Note that I'm not completely aware of where the Standard specifies the comparison between the substituted argument list and the supplied argument list.

5 Example: riptutorial C++ `void_t`

How does this work? When I try to instantiate has_foo<T>::value, that will cause the compiler to try to look for the best specialization for has_foo<T, void>. We have two options: the primary, and this secondary one which involves having to instantiate that underlying expression:

1、If T does have a member function foo(), then whatever type that returns gets converted to void, and the specialization is preferred to the primary based on the template partial ordering rules. So has_foo<T>::value will be true

2、If T doesn't have such a member function (or it requires more than one argument), then substitution fails for the specialization and we only have the primary template to fallback on. Hence, has_foo<T>::value is false.

20200427: 对这个问题的分析，需要从compiler的compile model入手，在Why can’t I separate the definition of my templates class from its declaration and put it inside a .cpp file? ¶ Δ中对此的分析是非常好的。

TO READ

bytefreaks C++: “undefined reference to” templated class function

stackoverflow “Undefined symbols” linker error with simple template class

stackoverflow Template instantiation details of GCC and MS compilers

gnu Compiling c++ template is very slow.

oracle Chapter 7 Compiling Templates

stackoverflow Template Compilation

https://accu.org/index.php/journals/427

为了便于区分，primary template、Specialized template

compiler肯定会substitute所有的template，替换后的的template叫什么名字？叫做specialization of template

substitute的过程可能会发生失败，它们会被从candidate中drop掉

compiler

对于template specialization

关于本章

Template is a kind of static polymorphism

Specialization and instantiation of template

cppreference Templates

Specialization and instantiation of template

Lazyness of template instantiation

CRTP

完整的编译过程

1 先deduce 然后 substitute

Parameter-list and argument-list

Template argument: provided or deduced

Deduction

Substitution: argument->parameter

cppreference Partial template specialization#The argument list

2 Primary template and template specializaiton

Partial template specialization是primary template的附庸

cppreference Partial template specialization#Name lookup

cppreference Function template#Function overloads vs function specializations

cppreference Partial template specialization#Partial ordering

案例学习: template specialization and trait

accu An introduction to C++ Traits # is_pointer

cppreference std::is_member_function_pointer

stackoverflow Check if a class has a member function of a given signature # A

SFINAE

4 Example: stackoverflow How does void_t work # A

1、Primary Class Template

2、Specialized Class Template

3、Choice

5 Example: riptutorial C++ void_t

stackoverflow Why can templates only be implemented in the header file?

TO READ

accu An introduction to C++ Traits # `is_pointer`

4 Example: stackoverflow How does `void_t` work # A

5 Example: riptutorial C++ `void_t`