Beyond the veil: What's after type functions

[Stefan Koch]

Good Evening,

I recently had a programming task in my hobby project where I 
needed to interface with a C library that uses manual closures 
using void**.
This quickly lead to bugs where one would forget to deref twice 
for read or accidental double deference on write (causing the 
written value to be invisible).

After that casting to the correct structure was an issue, since 
(void**) trows away typing information.

So I wanted a discriminated union (a "sumtype") to which I would 
use for all closures where the discriminant would tell me the 
rumtime type.

This is what I ended up with:

---
struct UploadClosure
{
     MHD_PostProcessor* pp;
     const (char)* filename;
     FILE* f;
     size_t totalSize;
}

struct KeyServerClosure
{
     bool processing_request;
}

enum ConnectionClosureKind
{
     Invalid,
     UploadClosure,
     KeyServerClosure,
}

ConnectionClosure* newClosure(ConnectionClosureKind kind)
{
     alias Kind = ConnectionClosureKind;
     const closureSize = closureSize(kind);

     ConnectionClosure* result = /*new ConnectionClosure(); //*/ 
cast(ConnectionClosure*)new ubyte[](closureSize).ptr;

     result.kind = kind;

     final switch (kind)
     {
         case Kind.UploadClosure :
         {
             // result.uploadClosure = new UploadClosure();
             result.uploadClosure = cast(UploadClosure*) 
((cast(void*)result) + (*result).sizeof);
         } break;

         case Kind.KeyServerClosure : {
             result.keyServerClosure = cast(KeyServerClosure*) 
((cast(void*)result) + (*result).sizeof);
         } break;

         case Kind.Invalid : {};
     }

     // import std.stdio; writeln(*result);

     return result;
}

struct ConnectionClosure
{
     ConnectionClosureKind kind;
     union
     {
         UploadClosure* uploadClosure;
         KeyServerClosure* keyServerClosure;
     }
}

size_t closureSize (ConnectionClosureKind kind) pure nothrow @nogc
{
     size_t result = ConnectionClosure.sizeof;

     final switch (kind)
     {
         case ConnectionClosureKind.UploadClosure : result += 
UploadClosure.sizeof;
         case ConnectionClosureKind.KeyServerClosure : result += 
KeyServerClosure.sizeof;
         case ConnectionClosureKind.Invalid : {}
     }

     return result;
}
---

You can easily Imagine the 'struct ConnectionClosure' and the 
`new Closure` function to be generate from the `enum 
ConnectionClosureKind` which would reduce the code snippet I 
posted by 54 lines (which is over 70% of the 75 line snippet).

Traditionally in D one would use templates and static foreach, 
which are known to scale awfully with regards to compile time, 
once you base an entire system on them.
Also they will most likely use string mixins in the 
implementation which means you can run into visibility/protection 
and namespace issues.

So I started to sketch what I would want to the compiler to do. 
(And I know it can do it, because these operations are performed 
internally)

And here was what this would look like:

---
alias type = __type__;

/// Compiler interal API looks up a typename in the given 
scope($D lookupScope)
/// Returns: the type named ($D typeName) if found
///          __emptyType otherwise.
type __lookupTypeFromScope (string typeName, __scope lookupScope);

/// compiler internal API returns the current scope
/// Returns: the current scope
__scope __currentScope();

bool hasInvalidMember(type Enum)
{
     static immutable members = __traits(allMembers, Enum);
     return members.length && members[0] == "Invalid";
}

/// given an enum ($ closureEnumType) where all members are 
type-name (execpt for the first member iff that member is called 
'Invalid' return an array of type values which corrospond the 
type names in the enum. By default the names are looked up in the 
current scope, but this can be customized setting optional the 
lookupScope parameter)
type[] getClosureTypes(type closureEnumType, __scope lookupScope 
= __currentScope())
{
     assert(is(closureEnumType == enum), __FUNCTION__ ~ " expects 
an enum to be passed in" ~
         " which has member named equivalent to the types stored 
in the closure union");

     // type function traits don't produce compiler tuples since 
that would mean a shape change.
     immutable string[] enumMembers =
         __traits(allMembers, 
closureEnumType)[hasInvalidMember(closureEnumType)
                  /*strip the first invalid member if there is 
one*/ .. $];

     __type__[] result;
     result.length = enumMembers.length;

     foreach(i,m;enumMembers)
     {
         __type__ t = __lookupTypeFromScope(m, lookupScope);
         // assert that t is not the __emptyType
         debug { assert(is(t), "Could not find a type named: " ~ 
m); }
         else { if (!is(t))  return null; }
         result[i] = t;
     }

     return result;
}

string genSizeEnumerationCases(type closureEnumType, string 
targetVaribleName)
{
     string result;
     auto closureTypes = getClosureTypes(closureEnumType, 
__currentScope());
     assert(closureTypes != null,
         "An error occurred when getting closure types, perhaps 
the types are not visible from current scope");

     immutable string case_prefix = "case " ~ __traits(identifier, 
closureEnumType) ~ ".";
     foreach(t;closureTypes)
     {
         result ~= case_prefix ~ __traits(identifier, t) ~ ": " ~ 
targetVaribleName ~ " = " ~ t.sizeof ~ "; break;\n";
     }

     if (hasInvalidMember(closureEnumType))
         result ~= case_prefix ~ "Invalid : " ~ targetVaribleName 
~ " = 0;\n";
}

size_t closureSize (ConnectionClosureKind kind) pure nothrow @nogc
{
     size_t result = ConnectionClosure.sizeof;

     size_t size;

     final switch (kind)
     {
         mixin(genSizeEnumerationCases(typeof(kind), "size"));
     }

     result += size;

     return result;
}
---

Look at the concise imperative code above.
It does not rely on any library functionality (except if you want 
to call the compiler internal api a 'library').

Now let's write a template which would do the same thing trying 
to reduce compile times as much as we can:

---
template hasInvalidMember(EnumT)
{
     enum hasInvalidMember = __traits(allMembers, EnumT).length > 
1 && __traits(allMembers, EnumT)[0] == "Invaild";
}

/// Note: Be careful about the instantiation context.
/// This can go very poorly of the type names in EnumT are 
locally shadowed, we can't pass a scope in here so we can't fix 
this!
template getClosureTypes(EnumT)
{
     alias getClosureTypes = mixin(() {
     char[] result = cast(char[])"AliasSeq!("; // let's hope this 
template is defined in the destination of the mixin otherwise we 
will error
     // note: we could fix this my nesting a couple more mixins 
but then the code get's even more bloated
     static assert(is(EnumT == enum), __FUNCTION__ ~ " expects an 
enum to be passed in" ~
         " which has member named equivalent to the types stored 
in the closure union");
     // this will be a statically unrolled tuple foreach bloating 
the size of this
     // since we need to do another mixin within here
     // this might be removed before codegen but you do pay the 
price of building the function before codegen even though it's 
only use once by ctfe.
     // and it will be one function per instance of 
getClosureTypes bloating the internal symbol table.
     foreach(i,m;__traits(allMembers, 
enumT)[hasInvalidMember!(enumT) .. $])
     {
         static assert(is(mixin(m)), m ~ " is either not a type, 
or it's not visible here");
         result ~= m ~ ",";
     }
     // replace the last useless ',' with a ')' to close the 
AliasSeq.
     result[$-1] = ')';
} ());
}

template genSizeEnumerationCases(closureEnumType, string 
targetVaribleName)
{
     enum genSizeEnumerationCases = (() {
     string result;
     alias closureTypes = getClosureTypes!(closureEnumType);
     // also note how we can't assert here that getClosureTypes 
not error ...
     // thereby lengthening the instantiation trace if something 
does go wrong
     immutable string case_prefix = "case " ~ __traits(identifier, 
closureEnumType) ~ ".";
     foreach(t;closureTypes)
     // again unrolled tuple foreach bloating this function ...
     // and again we actually have to build an internal function 
and then we have to interpret it. So we pay for the template 
instance and for CTFE...
     {
         result ~= case_prefix ~ __traits(identifier, t) ~ ": " ~ 
targetVaribleName ~ " = " ~ t.sizeof ~ "; break;\n";
     }

     if (hasInvalidMember!(closureEnumType))
         result ~= case_prefix ~ "Invalid : " ~ targetVaribleName 
~ " = 0;\n";

      return result;
}());
}

size_t closureSize (ConnectionClosureKind kind) pure nothrow @nogc
{
     size_t result = ConnectionClosure.sizeof;

     size_t size;

     final switch (kind)
     {
         mixin(genSizeEnumerationCases!(typeof(kind), "size"));
     }

     result += size;

     return result;
}
---

Without the comments the template would probably be somewhat 
shorter.
But again they are dependent on the external template AliasSeq to 
be visible in the template instantiation context.
CTFE can't cache them because they are new symbols every time.
They use unrolled tuple foreaches increasing the size of the body 
that ctfe and semantic has to deal with.
And they have to generate new symbols persistently ... even 
though those might get stripped the compiler has to allocate 
memory for them and spent time to generate them.
Thereby memory consumption and further reducing scalability.

whereas the type function with extended internal compiler API has 
none of these problems.
And does not rely on library functionality.

With this in mind, please tell me what you think :)

Cheers,
Stefan