C++ template instantiation, what exactly does it mean?

Question

Now, I'm familiar with templates and I'm somewhat familiar with things like SFINAE, and I've been wondering what goes on when a template is instantiated by the compiler.

When you do things in TMP, like SFINAE, or even the simple Fibonacci sequence in TMP, it seems like the compiler is doing more than what I understand under template instantiation. It seems the compiler is executing the template code.

My question is, what exactly is template instantiation and where is the line drawn with the compiler actually executing code?

The compiler creates a type of your template, is my understanding of template instantiation. But in TMP it seems like it's doing a whole lot more than that, and that confuses me.

Answer 1

It's best to think of it as a bunch of functions, which is what it really is. Consider a class Type, which here represents the compiler's internal representation of a type.

template<typename T> class X {
    T t;
};

In run-time C++, you could express this as

Type* X(Type *t) {
    static std::unordered_map<Type*, Type*> cache;
    if (cache.find(t) != cache.end())
        return cache[t];
    Type* ret = new Type;
    ret->DataMembers.insert("t", t);
    return cache[t] = ret;
}

Of course, a little extra would be needed for specializations and such. Using this model, though, it's easy to two things.

A) Instantiating a template is equivalent to a function call, which happens to occur at compile-time, just like constexpr. Of course, a clever compiler may do something else as an optimization, but in the general case.

B) How it extends to any other functionality provided by templates.

Because instantiating a template is Turing-complete, you can't really handle it any other way. The reason it seems like the compiler is executing them is because it is. They are nothing more than functions in a limited EDSL with bad syntax.