Type Qualifiers and Wild Cards

written by Walter Bright

November 7, 2011

Type qualifiers are modifiers applied to data types. The most useful one in D is the immutable qualifier,

immutable(T)

which creates a new type from type T that cannot be written to, and is guaranteed to never change. The immutable type qualifier is transitive, meaning any data reachable through an instance of type immutable(T) is itself immutable. In the vernacular this is called transitivity, or more simply, it's “turtles all the way down”.

Immutable types are particularly useful when doing multithreaded programming, as no synchronization is necessary for immutable types.

When using immutable qualifiers in the real world, however, one runs into some unexpected issues. For example, given a simple function to add a constant to an indirect value:

int func(int* p) {
  return *p + 7;
}

What happens if we try to pass it an immutable(int)* argument (which is a pointer to an immutable int)? It'll fail to compile as a pointer to immutable cannot be implicitly cast to a pointer to a mutable (if this was possible, there'd be no useful static typechecking of immutability). Our hapless programmer is reduced to writing the function twice:

int func(immutable(int)* p) {
  return *p + 7;
}

Meanwhile, he curses the designer of the language as he is forced to commit the cardinal sin of copypasta'ing his code. To add further insult, the compiler generates exactly the same native code for each of those two functions.

This miserable state of affairs is addressed by adding a new type qualifier: const. A const type cannot be written to, but also it is not guaranteed the data is immutable. The data could be changed via another mutable reference to it. Like immutable, const is transitive.

The beauty is that both T and immutable(T) can be implicitly cast to const(T), so only one version of the function needs to be written:

int func(const(int)* p) {
  return *p + 7;
}

and everyone is happy, the angels sing, but hmm, there still seems to be an evil stench here somewhere. What about this, the identity function:

int* func(int* p) {
  return p;
}

Throwing in a const:

const(int)* func(const(int)* p) {
  return p;
}

Hmm, that doesn't really work. An identity function should return the same type that it was given, not that type converted to const. What about using templates? We can write:

T func(T)(T p) {
  return p;
}

which will solve the problem, won't it? T can take on int*, const(int)*, and immutable(int)*. Sure, for that function and similar ones. But template functions:

can't be used for virtual functions
can't be used for a binary interface
will generate multiple copies of a function that are the same except for the type signature (arguably, this should be fixed by better compiler technology)

But worse, consider:

struct S {
  T p;
}

T* func(S)(S s) {
  return &s.p;
}

or even some fiendishly complex compound type built out of T. We want the type qualifier of S transferred to T. If a const or immutable S is passed, then the code won't compile, as the return type is T*, not const(T)* or immutable(T)*. Attempting to enhance the template system to create a ‘type qualifier parameter’ consumed many gallons of coffee and many hours at the coffee shop. All the ideas were rejected as just too painfully ugly. It just was a bad fit for templates, or we just weren't smart enough. A new approach was needed.

We found it by simply coming up with a new type qualifier. I know, I know, too many type qualifiers will sink the boat. Adding them is a dangerous game.

It looks like:

inout(T)* func(inout(S) s) {
  return &s.p;
}

It isn't a template, and inout can only be used on function parameters and the return value. inout is set to the type qualifier of its corresponding argument when it is called, and the return type is constructed out of that qualifier. Inside the function, inout behaves similarly to const. Voila, one function in source code and in generated code. The argument s can be immutable, const or neither. Let's try it out with a program that prints the type of the return value of foo():

import std.stdio;

inout(int)* foo(inout(int)* p) {
  return p;
}

void main() {
  int x = 1;
  const int y = 2;
  immutable int z = 3;

  writeln(typeid(typeof(foo(&x))));
  writeln(typeid(typeof(foo(&y))));
  writeln(typeid(typeof(foo(&z))));
}

Compiling it and running it prints:

int*
const(int)*
immutable(int)*

And looking at the object file reveals that there's only one foo(). Victory!

With a template inout function, we also get a benefit of the instantiations being reduced:

import std.stdio;

inout(T)* func(T)(inout(T)* p)
{
  writefln("instantiated with %s", typeid(T));
  return p;
}

void main()
{
  int m;
  const(int) c;
  immutable(int) i;

  writeln(typeid(func(&m)));
  writeln(typeid(func(&c)));
  writeln(typeid(func(&i)));
}

Output:

instantiated with int
int*
instantiated with int
const(int)*
instantiated with int
immutable(int)*

And func is instantiated only once with T==int, instead of the three times one would get if it were declared as:

T* func(T)(T* p)

There is a little more to it than that. Suppose there's more than one inout parameter, and their qualifications differ?

import std.stdio;

inout(int)* foo(inout(int)* p,
                inout(int)* q) {
  return p;
}

void main() {
  int x = 1;
  immutable int z = 3;

  writeln(typeid(typeof(foo(&x, &z))));
}

prints:

const(int)*

which is what it must be. Furthermore, inside the function, immutable, const and unqualified types cannot be implicitly cast to inout, and inout can only be implicitly cast to const. This plugs any ‘leaks’ where immutable data could get infiltrated by mutable references.

Conclusion

Having an immutable type qualifier allows for static type checking of many desirable qualities in data. But to have both mutable and immutable typed data in a program, there needs to be mechanisms where single functions can be used for both. const provides this for function parameters, and inout provides it for return values. Both have an aura of inevitability about them, once that string gets pulled, the behavior they must have can be derived.

Acknowledgements

Thanks to Kenji Hara and Steve Schveighoffer for their helpful comments on this article.

Articles

Type Qualifiers and Wild Cards

Conclusion

Acknowledgements