How templates work (1)

[Stefan Koch]

Hi,

I've previously talked about the inherit compile-time impact of 
templates.
After talking  the problem through with a few people among them 
experienced D programmers, I am beginning to see that not 
everyone is aware what a template instantiation has to do.

let's take a simple identity template
template I(alias T)
{
     alias I = T;
}

now let's make an instance
I!(int) i1;

How does the compiler know what a template resolved to?
First it has to look up the _name_ 'I' from it's current scope, 
upwards.
// (depending on the depth (nestedness) of the scope that can 
actually take a lot of time.)
After it has found the template of the name 'I' it will now clone 
the body.
creating something like
{ alias I = _formal_param_1; }
after doing this it will now substitute the formal parameter 
(also known as just parameter) with the actual parameter (also 
known as argument).
resulting in this body :
{ alias I = int }
// (depending on the number of template parameters this too can 
be costly.)
then we substitute the newly created body with the instance which 
looks like this:
{ alias I = int } i1;
Of course this cannot compile since we don't pull a symbol out of 
the body.
I've for clarity omitted the handling of what is got publicized 
as the "eponymous template trick".
Before substituting we will actually try to look for a member in 
the template body which matches the name of the template and 
reference it.
Therefore

I!(int) i1;

actually results in:

{ alias I = int }.I i1;

and that's all there is to a simple templates instance.

let's repeat this for the type long

I!(long) l1;
copy the body
{ alias I = T; }
substitute the parameter
{ alias I = long; }
look for the eponymous member.
{ alias I = long; }.I
put it in place.
{ alias I = long; }.I l1;

Simple right?

And the fundamentals are really that simple.

However:
We have not covered how names are resolved in scopes;
Nor the intricacies of how to pick the right overload for a 
template.
And which implicit conversion happen for that;
Neither have we talked about deferred resolution of templates or
which steps semantic analysis has to take.

I will describe those in future posts as soon as I actually 
understand how the overload are picked ;)

Cheers,

Stefan