www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Technique: Trial functions to allow attribute inference for mutually

reply FeepingCreature <feepingcreature gmail.com> writes:
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.
Sep 01 2021
parent zjh <fqbqrr 163.com> writes:
On Wednesday, 1 September 2021 at 09:06:01 UTC, FeepingCreature 
wrote:
 Say you are writing a templated array data structure:
Nice.
Sep 01 2021