digitalmars.D - Technique: Trial functions to allow attribute inference for mutually
- FeepingCreature (105/105) Sep 01 2021 Say you are writing a templated array data structure:
- zjh (3/4) Sep 01 2021 Nice.
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
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