A recent issue I discovered (and no doubt has been encountered before) is that using Voldemort types in D can result in insane symbol bloat. However, at DConf 2016, a presentation by Vladimir Panteleev gave me an idea to help solve the problem. This allows one to create a Voldemort type, but cuts out most of the template bloat that can impede your project.
Voldemort Wrappers
Voldemort wrappers are a way to create chain constructed types — types where you wrap one type in another type, but the construction of the wrapper is done via an Implicit Function Template Instantiation (IFTI) factory function. The type itself is defined inside the function, and so is not able to be named by an external entity (hence the term Voldemort). This is a very nice encapsulation, because the type doesn’t interfere with any other symbols, and all creation of the type itself is funneled through the approved factory function.
An example of a Voldemort Wrapper is the chain function from Phobos. chain takes 2 ranges with the same element type and makes a range that will traverse the first, and then the second, as if they were one range (for more info on ranges, I recommend reading Ali Çehreli’s chapter on the subject). The full chain function gives us lots of niceties, such as implementing all the common features between the two ranges. However, for demonstration purposes, we will write an inputChain function that only works on like-typed input ranges:
Now, we can write a simple test that chains together ranges without any allocation!
And the result:
$ ./testchain hello, world!
This is all pretty straightforward stuff, and isn’t groundbreaking. But what is hidden from you here is the alarming space-cost for Voldemort wrapper types.
Exponential Symbols
Let’s print out the name of the nameless type (yes, it does still have a name, even though you can’t access it). This is a bit tricky, because simply printing typeof(ch).stringof results in the name Chain. However, this isn’t what we want, what we want is the fully qualified and instantiated type name. The easiest way to get this is to create an exception with the type name in it:
The result of running this with our previous main file is a stack trace that starts with:
$ ./testchain object.Exception@simplechain2.d(13) ---------------- 4 testchain 0x00000001063efa24 pure @safe dchar simplechain.inputChain!(immutable(char)[], immutable(char)[]).inputChain(immutable(char)[], immutable(char)[]).Chain.front() + 144 ...
Here is the Chain type in a “nicer” format (I have replaced immutable(char)[] with the more commonly known alias string):
simplechain.inputChain!(string, string).inputChain(string, string).Chain
Here, we can see that the type of ch isn’t just Chain, it contains the full signature of the function Chain comes from ((Note that yes, the mangled symbol name (the one actually stored in the object file) reflects all of these pieces. I’m using exceptions to print out the name because they are easier to read and understand, but the same problem exists with mangled names as well.)) . The reason you see inputChain twice, is because inputChain is a template function. There are two symbols, one for the template (denoted by the instantiation symbol ‘!‘), and one for the function itself, which we will cover later. While this in itself isn’t extremely troubling (and actually makes a lot of sense), the trouble becomes apparent when you try to chain 3 strings together (using UFCS):
Compiling and getting the exception, the type of ch is now:
simplechain.inputChain!(
simplechain.inputChain!(string, string).inputChain(string, string).Chain,
string)
.inputChain(
simplechain.inputChain!(string, string).inputChain(string, string).Chain,
string)
.Chain
I’ve tried to use indents to show you the pieces of this. First, we have the template. The template takes two parameters (two different ranges in fact). The first template parameter is the resulting type of the first inputChain call (you should recognize this from before). Note that this contains not only the template instantation, but the full signature of the function call as well. The second parameter is simply another string. And we get the repeated information for the function parameters.
If you continue this pattern, perhaps with more inputChain calls tacked onto the end of the call (as one would do with range pipelines in Phobos), then you can see how this will get progressively worse. The first argument to each call is going to be a recursive expansion of each previous call. I believe the growth of the symbol name is on the order of <strong>O(2<sup>n</sup>)</strong>, meaning we have exponential growth. However, for name mangling, the expansion is <strong>O(3<sup>n</sup>)</strong>, because unshown here is the return type of each level of function.
Abandoning the Dark Lord
So with such growth, a small range pipeline of Voldemort wrappers can add up to megabyte-long symbol names. But notice that the type itself is dependent only on the template parameters, not the function parameters ((In D, there is such a thing as a nested struct. Such a struct can utilize the stack frame of the function itself, giving access to variables and other definitions inside the function)).
We can solve the problem by moving the struct outside the function itself, to be included in the module namespace. Make this a private struct, and repeat all the template paraphernalia, and we have a “solution”:
And the resulting type:
simplechain.Chain!(simplechain.Chain!(string, string).Chain, string).Chain
Not too bad as a name, and this solves the exponential growth. But we have lost all the niceties that make Voldemort types so attractive — avoiding namespace pollution, avoiding repeating template specification, and encapsulation. This solution leaves a lot to be desired.
Using eponymous templates
So let’s look at a better way, that allows us to keep the benefits of Voldemort types, but without the baggage. In D, all templated functions, enums, types, etc. are actually a short form of a special type of template called an eponymous template. When you compile inputChain, the compiler really treats it as something that looks like this:
An eponymous template function still works with IFTI, so it’s equivalent to the original. However, now we have access to a namespace that we didn’t have before — the space inside the template, but outside the function itself. As shown by Vladimir Panteleev’s DConf 2016 talk, access to this space is forbidden by the compiler to outside functions and types because it always resolves to the eponymously named member.
So let’s put our struct there:
And the resulting type:
simplechain.inputChain!(simplechain.inputChain!(string, string).Chain, string).Chain
Note that the Chain type is safely buried inside the template namespace, without providing access to any outside callers. If you used the above type name, you would get a compiler error.
I call this the Horcrux ((If you don’t get this, then you need to read more Harry Potter)) method. If we compare this to Voldemort, it’s pretty much on par with all the features, except Horcrux wrappers do not support access to the function call stack or any definitions inside the function (unless you move them into Horcrux space as well), and the declaration is a little clunky. However, you may have some advantages. For example, if you had overloaded functions that return the same type, they could both be in the same template, and share the type externally, making them even less repetitive than the equivalent Voldemorts. You could also put unit tests inside that would now have access to the structs directly.
There is some effort to fix the compiler to avoid creating such huge symbols, but until this happens, I will be splitting my functions Horcrux style.
Here is the Github Gist with all the code included in the article.