Say you are writing a templated array data structure:

struct Array(T)
{
    T[] store;
    int length;
    void add(T value) {
        if (length == store.length)
            resize(store.empty ? 16 : store.length * 2);
        store[length++] = value;
    }
    void resize(size_t newsize) {
        Array result;
        result.store = new T[newsize];
        this.store[0 .. length].each!(a => result.add(a));
        this = result;
    }
}

Fairly straightforward, we have our backing array, we track length, we use an exponential resize strategy that doubles the backing size whenever we run full. Let's write a test:

@safe unittest {
    struct S {
        int i;
    }
    Array!S array;
    array.add(S(5));
}

This fails with an error. Our problem is that we want @safe, but add and resize are, by default, @system. Fine, no problem, we void add(T value) @safe and move on.

A bit later, we write another test:

unittest {
    struct S {
        int i;
        void opAssign(S s) @system { this.i = s.i; }
    }
    Array!S array;
    array.add(S(5));
}

Now our @safe is a hindrance! Rather, we want the compiler to infer when it can use @safe and when it needs @system in Array.

We remember that template functions infer attributes:

    void add()(T value) { ... }
    void resize()(size_t newsize) { ... }

But it still doesn't work! What gives?

The problem is that add and resize are in a mutual recursion. D's attribute inference conks out at this point because it cannot establish that add is allowed to be @safe without checking whether resize can be @safe, which it cannot prove without checking that add is allowed to be @safe... so it gives up and falls back to @system.

How do we square this circle? We define a "trial function":

    alias trial = {
        auto store = new T[1];
        store[0] = T.init;
    };

This function stands in for "the sort of operations" that will be done on T in the mutual recursion. It tries out the operations that we require and tells us which attributes are safe. Since it is a lambda, it is also attribute inferred, but it doesn't participate in any recursion, so it avoids the issue.

Then we just transfer the attributes to our recursive pair:

struct Array(T)
{
    T[] store;
    int length;
    alias trial = {
        auto store = new T[1];
        store[0] = T.init;
    };
    enum attributes = [__traits(getFunctionAttributes, trial)].join(" ");
    mixin(q{
        void add(T value)} ~ attributes ~ q{
        {
            if (length == store.length)
                resize(store.empty ? 16 : store.length * 2);
            store[length++] = value;
    	}
        void resize(size_t newsize)} ~ attributes ~ q{
        {
            Array result;
            result.store = new T[newsize];
            this.store[0 .. length].each!(a => result.add(a));
            this = result;
        }
    });
}

Now, since we manually specify the attributes on each function in the mutual recursion, D does not have to do any work to infer them, resulting in a data structure that works for either @safe or @system code.

On Wednesday, 1 September 2021 at 09:06:01 UTC, FeepingCreature wrote:

Nice.