Category Archives: Programming

Programming languages and software development

Have your Voldemort types, and keep your disk space too!

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 from1 . 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 O(2n), meaning we have exponential growth. However, for name mangling, the expansion is O(3n), 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 parameters2.

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 Horcrux3 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.

  1. 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. []
  2. 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 []
  3. If you don’t get this, then you need to read more Harry Potter []

Import Changes in D 2.071 [Updated]

Note: This post has been updated on 8/29/2016 with new information on mixin template imports.

In the upcoming version of D, several changes have been made to the import system, including fixes for 2 of the oldest bugs in D history.

There’s bound to be a lot of confusion on this, so I wrote this to try and explain the rules, and the reasoning behind some of the changes. I’ll also explain how you can mitigate any issues you have in your code base.

Bugs 313 and 314

Links: 313 and 314

Description

Private imports are not supposed to infiltrate the modules they are imported in. If you import a, and a imports b privately, then you should not have any access to b‘s symbols. However, before this was fixed, you could access b symbols via the Fully Qualified Name. A FQN is where you list all packages, including subpackages, separated by dots, to access a symbol. For example std.stdio.writeln.

In addition, when importing a module using static, renamed, or selective imports, the imported symbols were incorrectly made public to importing modules.

An example:

With 2.070 and prior versions, compiling this works just fine. With 2.071 and above, you will get either a deprecation warning, or an error.

Note that the private qualifier is only for illustration. This is the default import protection for any imports.

For an example of how selective imports add public symbols:

With 2.070, this compiled just fine. However, printf is supposed to be a private symbol of module ex2_a. With 2.071 and above, this will trigger a deprecation warning. In the future, the code will trigger an error.

Selective imports and FQN

A combination of both 313 and 314 is when you use a selective import, and expect the Fully Qualified Name to also be imported. This is not what the selective import was supposed to do, it was only supposed to add the symbols requested.

An example:

In this example, std.stdio.writeln is not actually supposed to be imported, only write is supposed to be imported (and even the FQN std.stdio.write isn’t imported!). We have to import std.range, because otherwise this would not compile (ironically, the package std is not imported by the selective import unless there is another import of the FQN).

In 2.070, this produces no warning or error. In 2.071 and beyond, this will produce a deprecation warning, and eventually an error.

Fixing problematic code

In order to fix such code, you have to decide what was intended. If your code really was supposed to publicly import the symbols, prepend public to the import statement. This brings all the symbols imported into the namespace of the module, so any importing module also sees those symbols. In our example 2 above, this would mean adding public to the import statement in ex2_a.d

If the imported module was not supposed to publicly expose the symbols, then you need to fix all importing modules with this problem. In our example, this would mean adding import core.stdc.stdio; to the top of ex2_main.d.

In the case of accidentally exposing the FQN of symbols that were privately imported, this is typically an issue with the importing module, not the imported one. In this case, you need to add an import. In our example 1 case, this would mean adding an import for ex1_a module to ex1_main.d.

For example 3, you can achieve the original behavior by both selectively importing the symbol, and statically importing the module. Just add static import std.stdio; to your scoped imports. Alternatively, you can add writeln to the selectively imported symbols, and use the unqualified name instead of the FQN.

For an example of how Phobos was fixed for this problem (there were thousands of messages in every build with deprecation warnings), see the PR I created.

Bug 10378

Links: 10378 Pull Request

Description

Another import-related bug fix is to prevent unintentional hijacking of symbols inside a scoped import. Such imports are not at module level, and import inside a function or other scope. These imports are only valid within the scope. Prior to 2.071, such imports were equivalent to importing every symbol in the imported module into the namespace of that scope. This overrode any other symbol in that namespace, including local variables in outer scopes. An example:

In 2.070 and prior, the assert above used ex4_a‘s definition of foo, not the local variable. In 2.071 and beyond, the local foo has precedence. The precedence rules work like this:

  1. Any local symbols are examined first. This includes selective imports which are aliased into the local scope.
  2. Any module-level symbols are examined.
  3. Any symbols imported are examined, starting with the most derived scope imports, all the way to module-level imports.

Note that this may be a breaking change, as demonstrated by the example.

Why did we change this?

This was changed because any symbol added to an import can drastically affect any code that uses non-selective scoped imports, hijacking the symbol in ways that the author cannot predict. While there is still potential for hijacking, since scoped imports override any module-level or higher level scoped imports, at least symbols that are locally defined are not affected. These are the symbols under direct control of the author of the module, and they should always have precedence.

A common change to a module is to move imports inside the scope of functions or types that are the only users of that import. This helps avoid namespace pollution. However, given that local module functions had precedence over imported ones, but scoped imports would take precedence away, this move was not always what the user intended. For this reason, module functions now always have precedence over non-selective scoped imports.

Fixing problematic code

This one is a little more nuanced. It may be that you wished to override the local symbols! In this case, use a selective import. Selective imports alias the symbols selected into the local scope, overriding any other symbols defined at that point. In our example, if we expected foo to refer to ex4_a.foo, then we would use an import like this: import ex4_a: foo;

In addition, you can use the FQN instead of using the simple name. I would recommend using a static or renamed import in that case.

Imports from mixin templates1

Links: Forum discussion, issue 15925

Description

A somewhat controversial change with 2.071 is the effect mixins can have with imports. If you have a mixin template which imports a module, then use that template within a class or struct, the import is only considered while inside the mixin template. It is not considered when inside the class or struct. For example:

The previous version would allow the import to be considered where the mixin occurs. In order to have a mixin template add an imported symbol, you can selectively import the symbol. In this case, static import will not work:

Why did we change this?

The explanation seems to be that allowing such imports can create a form of hijacking. Since a class-level import would override a module-level import, a user may not realize that the mixed-in import is present, and therefore overriding a module-level import that is in the local module. The hijacking can come after the fact, in the imported module, without the user’s knowledge or any changes in his code.

Fixing problematic code

There isn’t a very easy way to rectify this problem. The only solution is to selectively import all the symbols you may need from that other module within the mixin.

Transitional Switches

The new version of the compiler comes with two new transitional switches that you can use to find or ignore these errors (note that these affect the mixin template imports as well):

-transition=checkimports: This switch will warn you if you have code that behaved differently prior to issue 10378 being fixed. Note that this may slow down compilation notably, hence it’s not the default2

-transition=import: This switch reverts behavior back to the import rules prior to 10378 being fixed. Only use this switch as a stop-gap measure until you can fix the code!

General Recommendations

Because importing external modules that are outside your control can lead to hijacking, I recommend never importing a module at a scoped level that isn’t selective, static, or renamed. This gives you full control over what invades your namespace. The compiler will protect you now a little bit better, but it’s always better to defend against namespace pollution from an uncontrolled module.

References

D programming language

D Import Spec

Issue 313

Issue 314

Issue 10378

issue 15925

D Compiler Download

  1. Thanks to captaindet for bringing this issue to my attention []
  2. Thanks to Dicebot for pointing this out []