templates_around.tex

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\part{Around Templates: Other Compile-Time Tools}\label{around}

There is more to compile-time metaprogramming in D than \emph{just} templates. This part will describe the most common tools: string mixins (\ref{stringmixins}), compile-time function evaluation (\ref{ctfe}) and \D{\_\_traits} (\ref{traits}), as seen in relation with templates. For the good news is: they are all interoperable. String mixins are wonderful to inject code in your templates, compile-time-evaluable functions can act as template parameters and can be templated. And, best of best, templated compile-time functions can return strings which can in turn be mixed-in\ldots in your templates. Come and see, it's fun!

\section{String Mixins} \label{stringmixins}

String mixins\index{string mixins} put D code were they are called, just before compilation. Once injected, the code is \emph{bona fide} D code, like any other. Code is manipulated as strings, hence the name.

\subsection{Syntax}\label{stringmixinssyntax}

The syntax is slightly different from mixin templates (\ref{mixintemplates}):

\index{syntax!string mixins}
\begin{dcode}
mixin("some code as a string");
\end{dcode}

You must take care not to forget the parenthesis. String mixins are a purely compile-time tool, so the string must also be determined at compile-time.

\subsection{Mixing Code In, With Templates}\label{stringmixinsandtemplates}

Of course, just injecting predefined code is a bit boring:

\index{string mixins}
\begin{dcode}
mixin("int i = 3;"); // Do not forget the two semicolons
                     // one for the mixed-in code,
                     // one for the mixin() call.
i++;
assert(i == 4);
\end{dcode}

There is no interest in that compared to directly writing standard D code. The fun begins with D powerful constant folding ability: in D, strings can be concatenated at compile-time.\index{compile-time!string concatenation} That's where string mixins meet templates: templates can produce strings at compile-time and can get strings as parameters. You already saw that in section \ref{operatoroverloading} on operator overloading and section \ref{opdispatch} on \DD{opDispatch}, since I couldn't help doing a bit of foreshadowing.

Now, imagine for example wanting a template that generates structs for you. You want to be able to name the structs as you wish. Say we would like the usage to look like that:

\begin{dcode}
module usingmystruct1;
import mystruct1;

mixin(MyStruct!"First");  // creates a new type called First (a struct)
mixin(MyStruct!"Second"); // and another one called Second

void main()
{
    // "First" code was injected right there, in module 'mine'.
    First f1, f2;
    Second s1;

    assert(is( typeof(f1) == First)); 
}
\end{dcode}

Here comes the generating code:

\index{string mixins}
\begin{dcode}
module mystruct1;

template MyStruct(string name)
{
    enum string MyStruct = "struct " ~ name 
                         ~ " { "
                         ~ "/+ some code +/"
                         ~ " }";
}

// For example, with name == "First", it will return
//   "struct First { /+ some code +/ }"
//
\end{dcode}

In this case, the string is assembled inside the template during instantiation,  exposed through the eponymous trick\index{eponymous trick!string mixins} and then mixed in where you want it. Note that the string is generated in the \DD{utils} module containing \DD{MyStruct}, but that \DD{First} and \DD{Second} are defined exactly where the \D{mixin}\DD{()} call is. If you use the mixin in different modules, this will define as many different structs, all named the same way. This might be exactly what you want, or not.

To get the same struct type in different modules, the code must be organized a bit differently: the structs must be generated in the template module.

\index{string mixins}
\begin{dcode}
module mystruct2;

template MyStruct(string name)
{
    alias MyStructImpl!(name).result MyStruct;
}

template MyStructImpl(string name)
{    
    enum string code = "struct " ~ name 
                     ~ " { "
                     ~ "/+ some code +/"
                     ~ " }";
    mixin(code);
    mixin("alias " ~ name ~ " result;");
}
\end{dcode}

\begin{dcode}
module usingmystruct2;
import mystruct2;

MyStruct!"First" f1, f2;
MyStruct!"Second" s1;
\end{dcode}

Usage is a different, as you can see. In this case, \DD{First} is generated inside \DD{MyStructImpl} and exposed through an alias (this particular alias statement is itself generated by a string mixin). In fact, the entire code could be put in the mixin:

\begin{dcode}
module mystruct3;

template MyStruct(string name)
{
    alias MyStructImpl!(name).result MyStruct;
}

template MyStructImpl(string name)
{
mixin("struct " ~ name 
    ~ " {"
    ~ "/* some code */"
    ~ " }\n"
    ~ "alias " ~ name ~ " result;");
}
\end{dcode}

Here is an example using the ternary \DD{?:} operator to do some compile-time selection of code, similar to what can be done with \D{static if} (\ref{staticif}):

\index{string mixins}
\begin{dcode}
module getset2;

enum GetSet { no, yes}

struct S(GetSet getset = GetSet.no, T)
{
    enum priv = "private T value;\n"
              ~ "T get() @property { return value;}\n"
              ~ "void set(T _value) { value = _value;}";

    enum pub = "T value;";

    mixin( (getset == GetSet.yes) ? priv : pub);
}
\end{dcode}

The code:

\begin{dcode}
import getset2;

void main()
{
    S!(GetSet.yes, int) gs;
    gs.set(1);
    assert( gs.get == 1);
}
\end{dcode}

generates:

\begin{dcode}
struct S!(GetSet.yes, int)
{
    private int value;
    int get() @property { return value;}
    void set(int _value) { value = _value;}
}
\end{dcode}

\subsection{Limitations}\label{stringmixinslimitations}

Code crafting is still a bit awkward\index{string mixins!limitations}, because I haven't introduced CTFE yet (see \ref{ctfe}). So we are limited to simple concatenation for now: looping for example is possible with templates, but far easier with CTFE. Even then, it's already wonderfully powerful: you can craft D code with some `holes' (types, names, whatever) that will be completed by a template instantiation and then mixed in elsewhere. You can create other any kind of D code with that.

You can put \D{mixin}\DD{()} expressions almost were you want to, but\ldots

\TODO{Test the limits:inside static if expressions, for example}


\aparte{Escaping strings}{One usual problem with manipulating D code as string is how to deal with strings in code? You must escape them. Either use \DD{\textbackslash"} to create string quotes, a bit like was done in section \ref{functiontemplatessyntax} to generate the error message for \DD{select}. Or you can put strings between \DD{q\{} and \DD{\}}. }

\section{Compile-Time Function Evaluation} \label{ctfe}

\subsection{Evaluation at Compile-Time} \label{compiletimeevaluation}

Compile-Time Function Evaluation\index{CTFE}
%\index{Compile-Time Function Evaluation|see{CTFE}}
(from now on, CTFE) is an extension of the constant-folding that's done during compilation\index{compile-time!constant folding} in D code: if you can calculate \DD{1 + 2 + 3*4} at compile-time, why not extend it to whole functions evaluation? I'll call evaluable at compile-time functions CTE functions from now on.

It's a very hot topic in D right now and the reference compiler has advanced by leaps and bounds in 2011. The limits to what can be done with CTE functions are pushed farther away at each new release.  All the \D{foreach}, \D{while}, \D{if}/\D{then}/\D{else} statements, arrays manipulation, struct manipulation, function manipulation\ldots are there. You can even do pointer arithmetics! When I began this document (DMD 2.055), the limitations\index{CTFE!limitations} were mostly: no classes and no exceptions (and so, no \DD{enforce}). This was changed with DMD 2.057, allowing the manipulation of classes at compile-time.

In fact danger lies the other way round: it's easy to forget that CTE functions must also be standard, runtime, functions. Remember that some actions only make sense at compile-time or with compile-time initialized constants: indexing on tuples for example:

\subsection{\texorpdfstring{\D{\_\_ctfe}}
                           {\_\_ctfe}}

\unfinished{Write something on this new functionality, which enables testing inside a function whether we are at compile-time or runtime.}

\subsection{Templates and CTFE} \label{templatesandctfe}
\index{CTFE!and templates}
\index{template!and CTFE}

\unfinished{Some juicy examples should be added.}

That means: you can feed compile-time constants to your classical D function and its code will be evaluated at compile-time. As far as templates are concerned, this means that function return values can be used as template parameters and as \D{enum} initializers:

\index{CTFE}
\begin{dcode}

\end{dcode}

Template functions can very well give rise to functions evaluated at compile-time:

\begin{dcode}
\end{dcode}

\subsection{Templates and CTFE and String Mixins, oh my!}
\label{templatesandctfeandstringmixins}

And the fireworks is when you mix (!) that with string mixins: code can be generated by functions, giving access to almost the entire D language to craft it. This code can be mixed in templates to produce what you want. And, to close the loop: the function returning the code-as-string can itself be a template, using another template parameters as its own parameters.

Concretly, here is the getting-setting code from section \ref{stringmixinsandtemplates}, reloaded:

\begin{dcode}
module getset3;
import std.conv;

enum GetSet { no, yes}

string priv(string type, string index)
{
    return 
    "private "~type~" value"~index~";\n"
  ~ type~" get"~index~"() @property { return value"~index~";}\n"
  ~ "void set"~index~"("~type~" _value) { value"~index~" = _value;}";
}   

string pub(string type, string index)
{
    return type ~ "value" ~ index ~ ";";
}

string GenerateS(GetSet getset = GetSet.no, T...)()
{
    string result;    
    foreach(index, Type; T)
        static if (getset == GetSet.yes)
		     result ~= priv(Type.stringof, to!string(index));
        else
            result ~= pub(Type.stringof, to!string(index));
    return result;
}

struct S(GetSet getset = GetSet.no, T...)
{
    mixin(GenerateS!(getset,T));
}

void main()
{
    S!(GetSet.yes, int, string, int) gs;

/* Generates:
struct S!(GetSet.yes, int, string, int)
{
    private int value0;
    int get0() @property { return value0;}
    void set0(int _value) { value0 = _value;}

    private string value1;
    string get1() @property { return value1;}
    void set1(string _value) { value1 = _value;}

    private int value2;
    int get2() @property { return value2;}
    void set2(int _value) { value2 = _value;}
}
*/

    gs.set1("abc");
    assert(gs.get1 == "abc");
}
\end{dcode}

This code is much more powerful than the one we saw in section \ref{stringmixinsandtemplates}: the number of types is flexible, and an entire set of getters/setters is generated when asked to. All this is done by simply plugging \D{string}-returning functions together, and a bit of looping by way of a compile-time \D{foreach}.

\subsection{Simple String Interpolation}\label{stringinterpolation}

All this play with the concatenating operator (\DD{\~}) is becoming a drag. We should write a string interpolation function, evaluable at compile-time of course, to help us in our task. Here is how I want to use it:

\begin{dcode}
module usinginterpolate;
import stringinterpolation;

alias interpolate!"struct #0 { #1 value; #0[#2] children;}" makeTree;

enum string intTree = makeTree("IntTree", "int", 2);
enum string doubleTree = makeTree("DoubleTree", "double", "");

static assert(intTree 
          == "struct IntTree { int value; IntTree[2] children;}");
static assert(doubleTree 
          == "struct DoubleTree { double value; DoubleTree[] children;}");
\end{dcode}

As you can see, the string to be interpolated is passed as a template parameter. Placeholders use a character normally not found in D code: \DD{\#}. The $n^{th}$ parameter is \DD{\#n}, starting from 0. As a concession to practicality, a lone \DD{\#} is considered equivalent to \DD{\#0}. Args to be put into the string are passed as standard (non-template) parameters and can be of any type.

\begin{dcode}
module stringinterpolation;
import std.conv;

template interpolate(string code)
{
    string interpolate(Args...)(Args args) {
        string[] stringified;
        foreach(index, arg; args) stringified ~= to!string(arg);

        string result;
        int i;
        int zero = to!int('0');

        while (i < code.length) {
            if (code[i] == '#') {
                int j = 1;
                int index;
                while (i+j < code.length
                    && to!int(code[i+j])-zero >= 0
                    && to!int(code[i+j])-zero <= 9)
                {
                    index = index*10 + to!int(code[i+j])-zero;
                    ++j;
                }

                result ~= stringified[index];
                i += j;
            }
            else {
                result ~= code[i];
                ++i;
            }
        }

        return result;
    }
}
\end{dcode}

\TODO{The syntax could be extended somewhat: inserting multiple strings, inserting a range of strings, all arguments to the end.}

\subsection{Example: extending \DD{std.functional.binaryFun}}\label{naryfun}

\unfinished{This one is dear to my heart. Mapping $n$ ranges in parallel is one of the first things that I wanted to do with ranges, for examples to create ranges of structs with constructor taking more than one parameter.}

Phobos has two really interesting templates: \stdanchor{functional}{unaryFun} and \stdanchor{functional}{binaryFun}.

\TODO{Explain that this aims to extend that to n-args functions.}

\TODO{Augh, the introduction, as of DMD 2.058 of a nice closure syntax more or less alleviate the need for such a construction.}


\begin{dcode}
bool isaz(char c) {
    return c >= 'a' && c <= 'z';
}

bool isAZ(char c) {
    return c >= 'A' && c <= 'Z';
}

bool isNotLetter(char c) {
    return !isaz(c) && !isAZ(c);
}

int letternum(char c) {
    return to!int(c) - to!int('a') + 1;
}

int arity(string s) {
    if (s.length == 0) return 0;

    int arity;
    string padded = " " ~ s ~ " ";
    foreach(i, c; padded[0..$-2])
        if (isaz(padded[i+1]) 
         && isNotLetter(padded[i]) 
         && isNotLetter(padded[i+2]))
            arity = letternum(padded[i+1]) > arity ? 
                    letternum(padded[i+1]) 
                  : arity;
    return arity;
}

string templateTypes(int arit) {
    if (arit == 0) return "";
    if (arit == 1) return "A";

    string result;
    foreach(i; 0..arit)
        result ~= "ABCDEFGHIJKLMNOPQRSTUVWXYZ"[i] ~ ", ";

    return result[0..$-2];
}

string params(int arit) {
    if (arit == 0) return "";
    if (arit == 1) return "A a";

    string result;
    foreach(i; 0..arit)
        result ~= "ABCDEFGHIJKLMNOPQRSTUVWXYZ"[i]
               ~ " " ~ "abcdefghijklmnopqrstuvwxyz"[i]
               ~ ", ";

    return result[0..$-2];
}

string naryFunBody(string code, int arit) {
    return interpolate!"auto ref naryFun(#0)(#1) { return #2;}"
                      (templateTypes(arit), params(arit), code);
}

template naryFun(string code, int arit = arity(code))
{
    mixin(naryFunBody(code, arit));
}
\end{dcode}

\subsection{Sorting Networks}\label{sortingnetworks}

Sorting networks are a nice example of what compile-time code generation can buy you. Sorting is a very vast subject and obtaining near-optimal sort in many circumstances is quite difficult. But in some cases, if you know your input length, you can build a pre-defined list of comparisons between elements and swap them if they are not in the correct order. Here, I will represent sorting networks as pairs of indices in the input range: given indices $i$ and $j$, compare \DD{input[i]} and \DD{input[j]}, and so on.

For example, given an array\footnote{ Or a random-access range.} of length $n$, \autoref{table:sortingnetworks} presents possible (optimal, in this case) sorting networks.

\begin{table}[htb]
\centering
\begin{tabular}[c]{|l|l|}
\hline
$n$ & Sorting network \\ \hline \hline
2   & [[0, 1]] \\ \hline
3   & [[0, 2], [0, 1], [1, 2]] \\ \hline
4   & [[0, 2], [1, 3], [0, 1], [2, 3], [1, 2]] \\ \hline
5   & [[0, 4], [0, 2], [1, 3], [2, 4], [0, 1], [2, 3], [1, 4], [1, 2], [3, 4]] \\ \hline
\end{tabular}
\caption{The first few sorting networks}
\label{table:sortingnetworks}
\end{table}

The code to generate the list of indices can be found in Knuth's \emph{The Art of Computer Programming} or on the net. The code given below I translated from Common Lisp\index{lisp} (!) to D, and is taken from Doug Hoyte's \href{http://letoverlambda.com}{Let Over Lambda}, a very opinionated book about Common Lisp's macros.

\begin{dcode}
module sortingnetwork;

int ceilLog2(int n)
{
    int i;
    if ((n & (n-1)) == 0) i = -1;
    while (n > 0) { ++i; n/= 2;}
    return i;
}

/**
 * Given a length n, returns an array of indices pairs
 * corresponding to a sorting network for length n.
 * Looks a bit like C code, isn't it?
 */
int[2][] sortingNetwork(int n)
{
    int[2][] network;
    auto t = ceilLog2(n);
    auto p = 1 << (t-1);
    while (p > 0)
    {
        auto q = 1 << (t-1);
        auto r = 0;
        auto d = p;
        while (d > 0)
        {
            for(int i = 0; i<=(n-d-1); ++i)
            {
                if (r == (i & p)) network ~= [i, i+d];
            }
            d = q-p;
            q /= 2;
            r = p;
        }
        p /= 2;
    }
    return network;
}
\end{dcode}

\DD{sortingNetwork} returns an array of indices pairs. From this, it's easy to generate code. The basic building block done by \DD{interpolate} (\ref{stringinterpolation}):

\begin{dcode}
module buildsortingcode;
import stringinterpolation;
import sortingnetwork;

string buildSortingCode(size_t l)()
{
    enum network = sortingNetwork!(l);
    string result;
    foreach(elem; network) result ~= 
        interpolate!(
        "t1 = input[#0];
         t2 = input[#1];
         if (!binaryFun!pred(t1, t2))
         { 
             auto temp = t2;
             input[#1] = t1;
             input[#0] = temp;
         }\n")(elem[0], elem[1]);
    return result;
}
\end{dcode}

And from there, I want a template that pre-generates a templated sorting network function. As for \stdanchor{algorithm}{sort}, a predicate \DD{pred} determines the way individual range elements are compared.

\begin{dcode}
module networksort;
import std.range;
import std.functional;
import std.exception;
import buildsortingcode;
import stringinterpolation;

template networkSort(size_t l)
{
    mixin(
interpolate!(
    "void networkSort(alias pred = \"a < b\", R)(ref R input)
     if (isRandomAccessRange!R)
     { 
         enforce(input.length >= #, 
                 \"Calling networkSort!# with a range of less than # elements\");
	      ElementType!R t1, t2;")(l)
      ~ buildSortingCode!(l) 
 ~ "}");
}
\end{dcode}

The strange mixin-in-a-template construction is there to cut the template in two, to allow user code like this:

\begin{dcode}
// somewhere in your code
alias networkSort!32 sort32;

// somewhere else
sort32(myArr);
sort32!"a > b"(myArr);
\end{dcode}

\DD{sort32} is designed to work on 32-elements-long random-access ranges, without knowing in advance the nature of the range nor the predicate used to sort. If you call it on ranges with a length greater than 32, it will sort only the first 32 elements. For less than 32 elements, the enforcement will fail.

So, what does that little sorting routine buy us? It appears to be quite efficient for small-size arrays, compared to \stdanchor{algorithm}{sort}, but sees its performance degrade after a point. Table \ref{table:sortingnetworkperformance} compares one million sorting of $n$-elements randomly-shuffled arrays done with \DD{networkSort} and \DD{std.algorithm.sort} and gives the ratio of speed-up brought by pre-computing the sorting code. 

\begin{table}[htb]
\centering
\begin{tabular}[c]{|c|c|c|c|}
\hline
$n$ & Sorting network & Standard sort & ratio \\
    & (ms)            & (ms)          &       \\ \hline \hline
5  & 324  & 532  & 1.642 \\ \hline
10 & 555  & 1096 & 1.975 \\ \hline
10 & 803  & 1679 & 2.091 \\ \hline
20 & 1154 & 2314 & 2.005 \\ \hline
25 & 1538 & 3244 & 2.109 \\ \hline
30 & 2173 & 3508 & 1.614 \\ \hline
35 & 4075 & 4120 & 1.011 \\ \hline
40 & 5918 & 5269 & 0.890 \\ \hline
45 & 7479 & 5959 & 0.797 \\ \hline
50 & 9179 & 6435 & 0.701 \\ \hline
\end{tabular}
\caption{Comparing \DD{networkSort} and \D{std.algorithm.sort}}
\label{table:sortingnetworkperformance}
\end{table}

So, at least on this benchmark, \DD{networkSort} outperforms Phobos with a speed-up of up to 100\% for ranges between 5 and 40 elements.\footnote{ FWIW, on my computer, the cut-off seems to be for about 38-39 elements.} Of course, Phobos' \DD{sort} is much more versatile, since it works on ranges with a length known only at runtime, but if you know your input's length in advance \DD{networkSort} can be nice to use.

In any cases, the idea to take home away is that, if you've a good idea of what your runtime data will look like, you probably can pre-generate optimal code for it at compile time and then do some triaging at runtime.

\section{\texorpdfstring{\D{\_\_traits}}
                        {\_\_traits}}
\label{traits}

The general \D{\_\_traits} syntax can be found online \href{www.dlang.org/traits.html}{here}. Traits are basically another compile-time introspection\index{compile-time!introspection!with \_\_traits@with \D{\_\_traits}}\index{introspection!with \_\_traits@with \D{\_\_traits}} tool, complementary to the \D{is} expression (see  \autoref{isexpression}). Most of time, \D{\_\_traits} will return \D{true} or \D{false} for simple type-introspection questions (is this type or symbol an abstract class, or a final function?). As D is wont to do, these questions are sometimes ones you could ask using \D{is} or template constraints, but sometimes not. What's interesting is that you can do some introspection on types, but also on symbols or expressions.

\subsection{\texorpdfstring{Yes/No Questions with \D{\_\_traits}}
                           {Yes/No Questions with \_\_traits}}
\label{yesnoquestionsontypes}

Seeing how this is a document on templates and that we have already seen many introspection tools, here is a quick list of what yes/no questions you can ask which can or \emph{cannot} be tested with \D{is}:\footnote{As with any other affirmation in this document, readers should feel free to prove me wrong. That shouldn't be too difficult.}

\begin{table}[htb]
\centering
\begin{tabular}[c]{|c|c|}
\hline
Question & Doable with other tools? \\
\hline
\hline
isArithmetic & Yes \\
isAssociativeArray & Yes \\
isFloating & Yes \\
isIntegral & Yes \\
isScalar & Yes \\
isStaticArray & Yes \\
isUnsigned & Yes \\
\hline
\hline
isAbstractClass & No \\
isFinalClass & No \\
isVirtualFunction & No \\
isAbstractFunction & No \\
isFinalFunction & No \\
isStaticFunction & No \\
\hline
\hline
isRef & No \\
isOut & No \\
isLazy & No \\
\hline
\hline
hasMember & No (Yes?) \\
isSame & No \\
compiles & Yes (in a way) \\
\hline
\end{tabular}
\caption{Comparison between \D{\_\_traits} and other introspection tools}
\label{table:traits}
\end{table}

These can all be quite useful in your code, but I'll shy away from them since they are not heavily template-related. More interesting in my opinion is using \D{\_\_traits} to get new information about a type. These are really different from other introspection tools and I will deal with them in more detail right now.

\subsection{\DD{identifier}}

\DD{identifier} gives you a symbol's name as a string. This is quite interesting, since some symbols are what I'd call \emph{active}: for example, if \DD{foo} is a function, \DD{foo.stringof} will try to first call \DD{foo} and the \DD{.stringof} will fail. Also, \DD{.stringof}, though eminently useful, sometimes returns strangely formatted strings. \DD{identifier} is much more well-behaved.

Let's get back to one of the very first template in this doc, \DD{nameOf} on page \pageref{templatedeclarationexamples}. Initially, it was coded like this:

\begin{dcode}
template nameOf(alias a)
{
    enum string name = a.stringof; // enum: manifest constant
                                   // determined at compile-time
}
\end{dcode}

But, this fail for functions:

\begin{dcode}
int foo(int i, int j) { return i+j;}

auto name = nameOf!foo; // Error, 'foo' must be called with 2 arguments
\end{dcode}

It's much better to use \D{\_\_traits} (also, the eponymous trick (\ref{eponymous}):

\begin{dcode}
module nameof;

template nameOf(alias a)
{
    enum string nameOf = __traits(identifier, a);
}

unittest
{
    int foo(int i, int j) { return i+j;}
    enum name = nameOf!foo; // name is available at compile-time

    assert(name == "foo");
}
\end{dcode}

Note that this works for many (all?) kinds of symbols: template names, class names, even modules:
auto
\begin{dcode}
import std.typecons;
import nameof;

enum name2 = nameOf!(nameOf); // "nameOf(alias a)"
enum name3 = nameOf!(std.typecons); //"typecons"
\end{dcode}

\subsection{\DD{getMember}}

In a nutshell, \D{\_\_traits}\DD{(getMember, name, "member")} will give you direct access to \DD{name.member}. This is the real member: you can get its value (if any), set it anew, etc. Any D construct with members is OK as a \DD{name}. If you wonder why the aggregate is called directly by its own name whereas the member needs a string, it's because the aggregate is a valid symbol (it exists by itself), when the member's name has no existence outside the aggregate (or even worse, may refer to another, unrelated, construct).

\aparte{Aggregates}{I'll use \emph{aggregate} as a catch-all term for any D construct that has members. Structs and classes are obvious aggregates, as are interfaces, but it's interesting to keep in mind that templates too have members (remember section \ref{instantiating}? A template is a named, parameterized scope). So all \D{\_\_traits} calls shown in this section can be used on templates. That's interesting to keep in mind. Even more interesting, to my eyes, is that \emph{modules} are also aggregates even though they are not first-class citizens in D-land. You'll see examples of this in the following sections.}

\subsection{\DD{allMembers}}
\index{\_\_traits@\D{\_\_traits}!allMembers@\DD{allMembers}}

This one is cool. Given an aggregate name, \D{\_\_traits}\DD{(allMembers, aggregate)} will return a tuple of string literals, each of which is the name of a member. For a class, the parent classes' members are also included. Built-in properties (like \DD{.sizeof}) are not included in that list. Note that I did say 'tuple': it's a bit more powerful than an array, because it can be iterated over at compile-time.

The names are not repeated for overloads, but see the next section for a way to get the overloads.

\begin{dcode}
module usingallmembers1;

class MyClass 
{
    int i;
    
    this() { i = 0;}
    this(int j) { i = j;}
    ~this() { }
    
    void foo() { ++i;}
    int foo(int j) { return i+j;}
}

void main()
{
    // Put in an array for a more human-readable printing
    enum myMembers = [__traits(allMembers, MyClass)];

    // See "i" and "foo" in the middle of standard class members
    // "foo" appears only once, despite it being overloaded.
    assert(myMembers == ["i", "__ctor", "__dtor", "foo", "toString", 
                         "toHash", "opCmp", "opEquals", "Monitor", "factory"]);
}
\end{dcode}

So the above code is a nice way to get members, both fields (like \DD{i}) and methods (like \DD{foo}). In case you wonder what \DD{"\_\_ctor"} and \DD{"\_\_dtor"} are, it's the internal D name for constructors and destructors. But it's perfectly usable in your code! For structs, the list far less cluttered since they only get the constructor and destructor's names and \DD{opAssign}, the assignment operator (\DD{=}).

Since this trait returns strings, it can be plugged directly into \DD{getMember}. See a bit farther down a way to get a nice list of all members and their types.

Now, let's ramp things up a bit: what about class and struct templates? Let's try this out:

\begin{dcode}
module allmemberstemplate;

class MyClass(T)
{
    T field;
}

static assert([__traits(allMembers, MyClass)] == ["MyClass"]);
\end{dcode}

Oh, what happened? Remember from \autoref{basics} that struct, classes and functions templates are just syntactic sugar for the 'real' syntax:

\begin{dcode}
template MyClass(T)
{
    class MyClass
    {
        T field;
    }
}
\end{dcode}

So, \DD{MyClass} is just the name of the external template, whose one and only member is\ldots the \DD{MyClass} class. So all is well. If you instantiate the template, it functions as you might expect:

\begin{dcode}
module allmemberstemplate2;
import allmemberstemplate;

static assert([__traits(allMembers, MyClass!int)] 
           == ["field", "toString", "toHash", "opCmp", 
               "opEquals", "Monitor", "factory"]);
\end{dcode}

If you remember one of the very first use we saw for templates in \ref{instantiating}, that is as a named, parameterized scope,\index{scope} this can give rise to interesting introspection:\index{introspection}

\begin{dcode}
module templateintrospection;

template Temp(A, B)
{
    A a;
    B foo(A a, B b) { return b;}
    int i;
    alias A    AType;
    alias A[B] AAType;
}

static assert([__traits(allMembers, Temp)] 
           == ["a", "foo", "i", "AType", "AAType"]);
static assert([__traits(allMembers, Temp!(double,string))] 
           == ["a","foo", "i", "AType", "AAType"]);
\end{dcode} 

As you can see, you also get aliases' names. By the way, this is true for structs and templates also\ldots

Another fun fact is that D modules\index{module!modules as aggregates} are amenable to \D{\_\_traits}'s calls, though that's true only for packaged module (that is, \D{import }\DD{pack.mod;} imports the \DD{pack} and \DD{mod} symbols, but \D{import }\D{mod;} imports nothing).

\begin{dcode}
module allmembersmodule;
import std.algorithm;
import std.ctype;

enum algos = [__traits(allMembers, std.algorithm)]; // huuuge list of names
enum ctypes = [__traits(allMembers, std.ctype)];

void main()
{
    assert(ctypes == ["object","std","isalnum","isalpha",
                      "iscntrl","isdigit","islower",
                      "ispunct","isspace","isupper","isxdigit",
                      "isgraph","isprint","isascii","tolower",
                      "toupper","_ctype"]);
}
\end{dcode}

In the previous code, you see that among \DD{a} members, there is \DD{"object"} (the implicit \DD{object.d} module\index{module!implicit object.d module@implicit \DD{object.d} module} imported by the runtime), and \DD{"std"}, the global package that shows here whenever you import a \DD{std.*} module. It would be easy to imagine a template that recursively explore the members, find the modules and try to recurse into them to get a complete import-tree with a template. Halas \DD{"std"} blocks that, since the package itself do not have a member.\footnote{ If someone finds a way to determine with a template that \DD{b} imports \DD{std.algorithm}, I'd be delighted to see how it's done!}

\aparte{introspection}{I'm pretty sure auto-introspection (a module calling \DD{allMembers} on its own name) used to work in Fall 2011. Now it's 2012 and this doesn't work anymore. Hmmm\ldots}

Like for the other aggregates, you get the aliased names also, and the unit tests defined in the module.\footnote{ For those of you curious about it, they are named \DD{\_\_unittestXXX} where \DD{XXX} is a number. Their type is more or less \D{void delegate}\DD{()}}\footnote{ I didn't try static constructors in modules. Don't hesitate to play with them and tell me what happens.}

\aparte{What's the point of inspecting a module?}{ Well, first that was just for fun and to see if I could duplicate a module or create a struct with an equivalent members list (all forwarding to the module's own members). But the real deal for me was when using string mixins to generate some type. If the user uses the mixin in its own module, it could create conflicts with already-existing names. So I searched for a way for a mixin template to inspect the module it's currently being instantiated in.

Then, I wanted to write a template the, given a class name, would give me the entire hierarchy it's in (as the local module scope would see it, that was enough for me). This \DD{Hierarchy} template should be shown in this document.

Then, while testing \stdanchor{traits}{ParameterTypeTuple}, I saw that it gives the parameter typetuple of \emph{one} function, even when it's overloaded. So inspecting a module is also a way to get the full list of functions with a particular name and getting the parameter typetuple for each of them.}

\TODO{Inject Hierarchy here.}
\TODO{Code a more powerful version of ParameterTypeTuple.}

\subsection{\DD{derivedMembers}}

Really it's the same as above, except that you do not get a class' parents members, only the class' own members.

\subsection{\DD{getOverloads}}
\index{\_\_traits@\D{\_\_traits}!getOverloads@\DD{getOverloads}}

Given:

\begin{itemize}
\item an aggregate name or an instance of that agregrate
\item a member name as a string
\end{itemize}

Then, \D{\_\_traits}\DD{(getOverloads, name, "member")} will gives you a tuple of all local overloads of \DD{name.member}. By 'local', I mean that for classes, you do not get the parents classes overloads. There is a difference between using \DD{getOverloads} on a type and on an instance: in the former case, you get \ldots, well I don't know exactly what it is you get but it's a bit akin to static members. On an instance, you get an expression that is the exact member overload. The \href{http://dlang.org/traits.html#getOverloads}{documentation} is misleading: it says \DD{getOverloads} returns an array, but than cannot be the case, as all overloads must have a different type. What's cool is that, by using \DD{"\_\_ctor"}, you also get a direct access to a type's constructor overloads. That can be quite handy in some cases.

\subsection{Getting All Members, Even Overloaded Ones}
\index{\_\_traits@\D{\_\_traits}!getting all members}

Now, if you're like me, the urge to mix \DD{allMembers} (which returns the members' names without overloads) and \DD{getOverloads}  (which returns the overload of \emph{one} member) is quite great. So let's do that.

First, a bit of machinery: I want the members to be described by a name and a type. Let's create a struct holder, templated of course:

\TODO{Getting qualified names would be better.}

\begin{dcode}
module member;

struct Member(string n, T)
{
    enum name = n; // for external access
    alias T Type;
}
\end{dcode}

Given a member name, we'll need a template that delivers the associated \DD{Member}. I also want a way to impose the name, this will come handy later on:

\begin{dcode}
module makemember;
public import member;
import nameof;

template MakeMember(alias member)
{
    mixin("alias Member!(\"" ~ nameOf!member ~ "\", typeof(member)) MakeMember;");
}

template MakeNamedMember(string name)
{
    template MakeNamedMember(alias member)
    {
        mixin("alias Member!(\""~name~"\", typeof(member)) MakeNamedMember;");
    }
}
\end{dcode}

Now, given an aggregate name and a member name (as a string, since these do not exist by themselves), we want a list of \DD{Member} structs holding all the information:

\begin{dcode}
module overloads1;
import std.typetuple;
import makemember;

template Overloads(alias a, string member)
{
    alias staticMap!(MakeMember, __traits(getOverloads,a, member))
          Overloads;
}
\end{dcode}

\DD{staticMap} is explained in section \ref{staticmap}.

Now, that already works:

\begin{dcode}
module myclass;

class MyClass 
{
    int i; // field
    alias i j; // symbol alias
    
    alias int Int; // type alias

    struct Inner {} // Inner type
                
    template Temp(T) { alias T Temp;} // template
    
    this() { i = 0;} // constructor #1
    this(int j) { i = j;} // constructor #2
    ~this() { }
    
    void foo(int j) { ++i;} // foo overload #1
    int foo(int j, int k = 0) { return i+j;} // foo overload #2
    
    alias foo bar; // symbol alias
    
    unittest
    {
        int i;
    }
}
\end{dcode}

\begin{dcode}
module usingoverloads1;
import std.stdio;
import overloads1;
import myclass;

void main()
{
    alias Overloads!(MyClass, "foo") o;
    
    /* 
    prints:
    foo, of type: void(int j)
    foo, of type: int(int j, int k = 0)
    */
    foreach(elem; o) 
        writeln(elem.name, ", of type: ", elem.Type.stringof);
}
\end{dcode}

We indeed got two \DD{Member} instances, one for each overload. Each \DD{Member} holds the name \DD{"foo"} and the overload type. Except, there is a catch: for a field, there are no overloads. Aliases are also problematic and not correctly dealt with. We need to pay attention to that in \DD{Overloads}:

\begin{dcode}
module overloads2;
import std.typetuple;
import makemember;

/**
 * Gets the overloads of a given member, as a Member type tuple.
 */
template Overloads(alias a, string member)
{
    // a.member is a method
    static if (__traits(compiles, __traits(getOverloads, a, member)) 
        && __traits(getOverloads, a, member).length > 0)
        alias staticMap!(MakeNamedMember!(member), __traits(getOverloads, a, member))
              Overloads;
    else // field or alias
    // a.member is a field, or a symbol alias
        static if (is(typeof(__traits(getMember, a, member))))
            mixin("alias Member!(\""~member~"\", typeof(__traits(getMember, a, member))) Overloads;");
    // a.member is a type alias
    else static if (mixin("is(Member!(\""~member~"\", __traits(getMember, a, member)))"))
        mixin("alias Member!(\""~member~"\", __traits(getMember, a, member)) Overloads;");
    // a.member is template
    else
        mixin("alias Member!(\""~member~"\", void) Overloads;");
}
\end{dcode}

The entire template may be a bit daunting, but it's to give it a (mostly) correct way to deal with the many kinds of member an aggregate may have: fields, methods, type aliases, symbols aliases, template names\ldots As of this writing, it does not deal correctly with inner types: I think it should give them a \DD{Outer.Inner} type, whereas here it produces only \DD{Inner}.\footnote{ Maybe by using the \DD{qualifiedName} template shown in section \ref{parent}} Also, unittest blocks appear, but they are given a \D{void} type, the default case in this template. I think they should have a \D{void}\DD{()} type.

The last step is to get this for all members of a given aggregate. It's quite easy:

\begin{ndcode}
module allmembers;
import overloads2;
import std.typetuple;

template GetOverloads(alias a)
{
    template GetOverloads(string member)
    {
        alias Overloads!(a, member) GetOverloads;
    }
}

template AllMembers(alias a)
{
    alias staticMap!(GetOverloads!(a), __traits(allMembers, a)) AllMembers; 
}
\end{ndcode}

The strange \DD{GetOverloads} two-stage construction is just a way to map it more easily on line 11. So, this was quite long to explain, but it works nicely:

\begin{dcode}
module usingallmembers2;
import std.typetuple;
import std.stdio;
import myclass;
import allmembers;

void main()
{
    alias AllMembers!(MyClass) O;
    writeln(O.stringof);

    foreach(o; O)
        writeln(o.name, ", of type: " ~ o.Type.stringof);

    /*
    prints:
    i, of type: int
    j, of type: int
    Int, of type: int
    (...)
    __ctor, of type: MyClass()
    __ctor, of type: MyClass(int j)
    (...)
    foo, of type: void(int j)
    foo, of type: int(int j, int k = 0)
    (...)
    */
}
\end{dcode}

That's cool, every member and overload is acounted for: the two contructors are there, the destructor also, and of course \DD{i}, of type \D{int}.

\TODO{Example: store all members in a hashtable or a polymorphic association list. As a mixin, to be put inside types to enable runtime reflection? (a.send("someMethod", args), a.setInstanceVariable("i",5))}

\subsection{Testing for Interface Implementation}\label{implements}

The previous section gave us a way to get an aggregate member list. From there, it's an easy step to get an interface's member list and to see if a given symbol's members contains the entire interface member list:

\begin{dcode}
module implements;
import std.typetuple;
import allmembers;

/**
 * Statically check if symbol 'a' implements interface I
 * (that is, if all members of I are found in members of a.
 */
template implements(alias a, I) if (is(I == interface))
{
    alias implementsImpl!(a, AllMembers!I) implements;
}

template implementsImpl(alias a, Items...)
{
    static if (Items.length == 0)
        enum implementsImpl = true;
    else static if (staticIndexOf!(Items[0], AllMembers!a) == -1)
        enum implementsImpl = false;
    else
        enum implementsImpl = implementsImpl!(a, Items[1..$]);
}

interface I
{
    int foo(int i);
    void foo();
    
    string toString();
}

class Bad
{
    void foo(int i) {}
}

struct Good
{
    int field;
    
    int foo(int i) { return i;}
    void foo() { field = 1;}
            
    string toString() { return "I'm a good struct!";}
}

unittest
{
    assert( implements!(Good, I));
    assert(!implements!(Bad, I));
}
\end{dcode}

\subsection{\DD{getVirtualFunctions}}

It's in the same family than \DD{getOverloads} and such. It'll give you the list of virtual overloads for a class method. Given a class name, finding all overloads of all fields, even overriden ones, is let as a exercise to the reader.

\subsection{\DD{parent}}
\index{\_\_traits@\D{\_\_traits}!parent@\DD{parent}}
\label{parent}

\D{\_\_traits}\DD{(parents, symbol)} will return the symbol that's the parent of it. It's \emph{not} the parent in a 'class hierarchy' sense,\footnote{ If you came here to see a way to get all parents of a class, see section \ref{classhierarchy}.} it deals with qualified names and strip one level. Once you reach the toplevel scope, it returns the module name (this can be dangerous, because modules themselves do not have parents). See:

\begin{dcode}
module cclass;
import nameof;

class C
{
    int i;
    int foo(int j)
    {
        int k; // k is "cclass.C.foo.k"
        assert(nameOf!(__traits(parent, k)) == "foo");
        return i+k;
    }
}
\end{dcode}

\begin{dcode}
module parent;
import nameof;
import cclass;

// C is more precisely a cclass.C)
static assert(nameOf!(__traits(parent, C)) == "cclass");

void main() 
{
    auto c = new C(); // c is "parent.main.c"
    assert(nameOf!(__traits(parent, c)) == "main");
    assert(nameOf!(__traits(parent, c.i)) == "C");
    c.foo(1);
}
\end{dcode}

Even if there is no \DD{qualifiedIdentifier} in \D{\_\_traits}, we can construct a template to get it:

\begin{dcode}
module qualifiedname;
import nameof;

template qualifiedName(alias a)
{
    // does it have a parent?
    static if (__traits(compiles, __traits(parent, a)))
    // If yes, get the name and recurse
        enum qualifiedName = qualifiedName!(__traits(parent, a)) 
                           ~  "." ~ nameOf!(a);
    // if not, it's a module name. Stop there.
    else
        enum qualifiedName = nameOf!a;
}
\end{dcode}

\begin{dcode}
module usingqualifiedname;
import qualifiedname;
import cclass;

void main()
{
    auto c = new C();
    assert(qualifiedName!c == "usingqualifiedname.main.c");
    
    assert(qualifiedName!(c.foo) == "cclass.C.foo"); // same in both cases
    assert(qualifiedName!(C.foo) == "cclass.C.foo");
}
\end{dcode}

Note that \DD{c.foo} is \emph{not} qualified as \DD{usingqualifiedname.main.c.foo}.

\subsection{Local Scope Name}
\index{scope!local scope name}

Sometimes, when dealing with mixin templates (\ref{mixintemplates}) or string mixins (\ref{stringmixins}), you'll inject code in an unknown scope. To get your way round, it can be useful to get the local scope's name. Intuitively, the previous example could help with that: just create a local variable, get the qualified name of its parent to determine in which scope the mixin is. Then, expose the scope name. Let's call this one \DD{scopeName} and the associated inquisitive template \DD{getScopeName}.

\begin{dcode}
module scopename;
public import qualifiedname;

mixin template getScopeName()
{
    enum scopeName = qualifiedName!(__traits(parent, scopeName));
}
\end{dcode}

The idea is to declare local enum called \DD{scopeName} and take the qualified name of its own parent in the same expression (yes, that works!).

To use \DD{getScopeName}, just mix it in where you need a local scope name:

\begin{dcode}
module usingscopename;
import std.stdio;
import scopename;

class C
{
    mixin getScopeName; // 1
    
    int i;
    int foo(int j)
    {
        int k;
        mixin getScopeName; // 2
        writeln(scopeName);
        return i+k;
    }    
}

void main()
{
    auto c = new C();
    writeln(c.scopeName); // "test.C" (1)
    c.foo(1);             // "test.C.foo" (2)
    
    mixin getScopeName; // 3
    writeln(scopeName);   // "test.main" (3)
}
\end{dcode}

\section{Wrapping it all Together}\label{wrappingitup}

\unfinished{I have to dig some cute examples in my code base. Using string mixins and CTFE and templates all together.}