Difference between revisions of "DIP38"
Timotheecour (talk | contribs) |
Timotheecour (talk | contribs) |
||
Line 28: | Line 28: | ||
== Abstract == | == Abstract == | ||
− | In short, the compiler internally annotates ref-return | + | In short, the compiler internally annotates each ref input argument ai of a ref-return function with inref or outref indicating whether or not the function may return ai by reference (possibly via field accesses). If the function is a method or internal function, the function itself is marked as inref or outref as reference to the implicit 'this' parameter. |
− | + | ||
− | These annotations are used to validate/invalidate ref return functions | + | These annotations are used to validate/invalidate safety of ref return functions. |
− | + | ||
+ | They're written in the automatically generated di interface files. | ||
== Internal Compiler Annotation == | == Internal Compiler Annotation == | ||
Dconf13 introduced safe references enabled by a runtime check (see email thread from Walter: 'Rvalue references - The resolution'). I propose a formulation that is safe, yet doesn't require any runtime check. | Dconf13 introduced safe references enabled by a runtime check (see email thread from Walter: 'Rvalue references - The resolution'). I propose a formulation that is safe, yet doesn't require any runtime check. | ||
− | The compiler automatically annotates any return | + | The compiler automatically annotates any ref return function with inref/outref on ref input arguments: |
eg: | eg: | ||
Line 54: | Line 55: | ||
will be rewritten internally by the compiler as having the signature: | will be rewritten internally by the compiler as having the signature: | ||
<syntaxhighlight lang="d"> | <syntaxhighlight lang="d"> | ||
− | ref | + | ref T foo(outref T a, inref T b, outref U c); |
</syntaxhighlight> | </syntaxhighlight> | ||
− | indicating that ref depends on ref arguments | + | indicating that ref depends on ref arguments a and c (dependency on c is via field access). The other input ref arguments are marked 'inref' because they can't be returned by ref. |
− | Second example: when the function is a member (say of a struct), the 'this' parameter is | + | Second example: when the function is a member (say of a struct), the 'this' parameter is implicit, and the same rules apply: |
<syntaxhighlight lang="d"> | <syntaxhighlight lang="d"> | ||
Line 67: | Line 68: | ||
<syntaxhighlight lang="d"> | <syntaxhighlight lang="d"> | ||
− | struct S { T t; ref | + | struct S { T t; ref T fooc(outref T a) outref; } |
</syntaxhighlight> | </syntaxhighlight> | ||
− | because there's a ref dependency on | + | because there's a ref dependency on a and the implicit 'this' argument (the annotation for 'this' is at the method level, as const would be). |
− | |||
− | |||
The di files will have to write those annotations written down, which shall be done automatically. | The di files will have to write those annotations written down, which shall be done automatically. | ||
Line 77: | Line 76: | ||
== Safe ref validation at compile time == | == Safe ref validation at compile time == | ||
− | Given those | + | Given those inref/outref annotations, it is easy to validate/invalidate ref safety; we simply check whether the program typechecks under the following conversion rules: |
− | + | ||
− | + | Allowed type conversions: | |
− | + | ||
− | + | global => outref //global: gc-allocated, static, etc. | |
+ | output of ref-return function call => outref | ||
+ | outref . field => outref // field access | ||
+ | local => inref | ||
+ | global => inref | ||
+ | outref => inref | ||
+ | temporary => inref | ||
Examples: taken from Walter's above mentioned email: | Examples: taken from Walter's above mentioned email: | ||
Line 89: | Line 94: | ||
//Case A: | //Case A: | ||
ref T fooa(ref T t) { return t; } | ref T fooa(ref T t) { return t; } | ||
− | //=> ref | + | //=> ref T fooa(outref T t); |
− | ref T bar() { T t; return fooa(t); } // error | + | ref T bar() { T t; return fooa(t); } // error: wrong conversion local => outref |
//Case B: | //Case B: | ||
ref T foob(ref U u) { return u.t; } | ref T foob(ref U u) { return u.t; } | ||
− | //=>ref | + | //=>ref T foob(outref U u) { return u.t; } |
− | ref U bar() { T t; return foob(t); } // error | + | ref U bar() { T t; return foob(t); } // error: wrong conversion local => outref |
//Case C: | //Case C: | ||
struct S { T t; ref T fooc() { return t; } } | struct S { T t; ref T fooc() { return t; } } | ||
− | //=>struct S { T t; ref | + | //=>struct S { T t; ref T fooc() outref; } //outref refers to hidden this parameter |
− | ref T bar() { S s; return s.fooc(); } // error | + | ref T bar() { S s; return s.fooc(); } // error: wrong conversion local => outref |
//Case D: | //Case D: | ||
− | |||
− | |||
ref T food() { | ref T food() { | ||
T t; | T t; | ||
ref T bar() { return t; } | ref T bar() { return t; } | ||
− | //=>ref | + | //=>ref T bar() outref; //outref refers to hidden this parameter, this could be rewritten as: ref T bar(outref void*this) ; |
− | return bar(); //error since | + | return bar(); // error: wrong conversion local => outref (since 'this' refers to local stack) |
} | } | ||
//case E: | //case E: | ||
Transitively calling other functions: | Transitively calling other functions: | ||
− | + | ref T fooe(T t) { return ref fooa(t); } //error because of conversion local=>outref when attempting to call fooa(t). | |
− | ref T fooe(T t) { return ref fooa(t); } //error | ||
− | |||
</syntaxhighlight> | </syntaxhighlight> | ||
== Algorithmic details for ref dependency analysis== | == Algorithmic details for ref dependency analysis== | ||
− | |||
− | |||
Let's take the following example for illustration: | Let's take the following example for illustration: | ||
<syntaxhighlight lang="d"> | <syntaxhighlight lang="d"> | ||
Line 130: | Line 129: | ||
The propagation algorithm goes as follows | The propagation algorithm goes as follows | ||
− | + | * initialize each ref argument of ref-return functions with 'ref' (ie we don't know yet whether it's inref or outref) | |
− | * initialize each ref-return | ||
* construct an oriented graph: | * construct an oriented graph: | ||
* nodes are ref-return functions | * nodes are ref-return functions | ||
* edges are ref-return dependencies (one edge per return statement in a ref return function): with example above, there is a graph with 2 nodes (foo1 and foo2) and a single edge (foo1 -> foo2). | * edges are ref-return dependencies (one edge per return statement in a ref return function): with example above, there is a graph with 2 nodes (foo1 and foo2) and a single edge (foo1 -> foo2). | ||
* while some ref annotations have changed do: | * while some ref annotations have changed do: | ||
− | * for each node with a ' | + | * for each node with a 'ref' annotation |
* recompute annotations and remove '?' if all outgoing edges have no '?' annotations | * recompute annotations and remove '?' if all outgoing edges have no '?' annotations | ||
* case A1) if there are no nodes with '?' annotations, then we have succeeded in compile time inference of ref dependency | * case A1) if there are no nodes with '?' annotations, then we have succeeded in compile time inference of ref dependency |
Revision as of 05:15, 7 May 2013
Contents
DIP38: Safe references and rvalue references without runtime checks.
Title: | Safe references and rvalue references without runtime checks |
---|---|
DIP: | 38 |
Version: | 1 |
Status: | Draft |
Created: | 2013-05-06 |
Last Modified: | 2013-05-06 |
Author: | Timothee Cour |
Links: |
Abstract
In short, the compiler internally annotates each ref input argument ai of a ref-return function with inref or outref indicating whether or not the function may return ai by reference (possibly via field accesses). If the function is a method or internal function, the function itself is marked as inref or outref as reference to the implicit 'this' parameter.
These annotations are used to validate/invalidate safety of ref return functions.
They're written in the automatically generated di interface files.
Internal Compiler Annotation
Dconf13 introduced safe references enabled by a runtime check (see email thread from Walter: 'Rvalue references - The resolution'). I propose a formulation that is safe, yet doesn't require any runtime check. The compiler automatically annotates any ref return function with inref/outref on ref input arguments:
eg:
struct U{T x;}
ref T foo(ref T a, ref T b, ref U c){
static T d;
if(condition)
return a;
else if(condition(b))
return c.x;
else
return d;
}
will be rewritten internally by the compiler as having the signature:
ref T foo(outref T a, inref T b, outref U c);
indicating that ref depends on ref arguments a and c (dependency on c is via field access). The other input ref arguments are marked 'inref' because they can't be returned by ref.
Second example: when the function is a member (say of a struct), the 'this' parameter is implicit, and the same rules apply:
struct S { T t; ref T fooc(ref T a) { if(condition) return t; else return a;} }
will be rewritten internally by the compiler as having the signature:
struct S { T t; ref T fooc(outref T a) outref; }
because there's a ref dependency on a and the implicit 'this' argument (the annotation for 'this' is at the method level, as const would be).
The di files will have to write those annotations written down, which shall be done automatically.
Safe ref validation at compile time
Given those inref/outref annotations, it is easy to validate/invalidate ref safety; we simply check whether the program typechecks under the following conversion rules:
Allowed type conversions:
global => outref //global: gc-allocated, static, etc. output of ref-return function call => outref outref . field => outref // field access local => inref global => inref outref => inref temporary => inref
Examples: taken from Walter's above mentioned email:
//Case A:
ref T fooa(ref T t) { return t; }
//=> ref T fooa(outref T t);
ref T bar() { T t; return fooa(t); } // error: wrong conversion local => outref
//Case B:
ref T foob(ref U u) { return u.t; }
//=>ref T foob(outref U u) { return u.t; }
ref U bar() { T t; return foob(t); } // error: wrong conversion local => outref
//Case C:
struct S { T t; ref T fooc() { return t; } }
//=>struct S { T t; ref T fooc() outref; } //outref refers to hidden this parameter
ref T bar() { S s; return s.fooc(); } // error: wrong conversion local => outref
//Case D:
ref T food() {
T t;
ref T bar() { return t; }
//=>ref T bar() outref; //outref refers to hidden this parameter, this could be rewritten as: ref T bar(outref void*this) ;
return bar(); // error: wrong conversion local => outref (since 'this' refers to local stack)
}
//case E:
Transitively calling other functions:
ref T fooe(T t) { return ref fooa(t); } //error because of conversion local=>outref when attempting to call fooa(t).
Algorithmic details for ref dependency analysis
Let's take the following example for illustration:
ref T foo1(ref T a, T b, ref T c) { if(...) return foo2(a); else return foo2(c); }
ref T foo2(ref T a) { return a; }
The propagation algorithm goes as follows
- initialize each ref argument of ref-return functions with 'ref' (ie we don't know yet whether it's inref or outref)
- construct an oriented graph:
* nodes are ref-return functions * edges are ref-return dependencies (one edge per return statement in a ref return function): with example above, there is a graph with 2 nodes (foo1 and foo2) and a single edge (foo1 -> foo2).
- while some ref annotations have changed do:
* for each node with a 'ref' annotation * recompute annotations and remove '?' if all outgoing edges have no '?' annotations
- case A1) if there are no nodes with '?' annotations, then we have succeeded in compile time inference of ref dependency
- case A2) otherwise, for each node with '?' annotations, then there are loops in the graph, and for these nodes we fall back in runtime check on return addresses as proposed in Dconf13. This case should be rare in practice. However there might be a slightly more complex algorithm in that case too that doesn't require runtime check (I will think about it).
For the above example we have: iteration 0(initialization): foo1:ref()? foo2:ref()?
iteration 1: foo1:ref()? foo2:ref(0)
iteration 2: foo1:ref(0,2) foo2:ref(0)
Loops in the graph (case A2) correspond to the case of mutually recursive ref return functions. For example:
ref T foo1(ref T a, T b, ref T c) { if(...) return foo2(a,0,c); else return a; }
ref T foo2(ref T a, T b, ref T c) { if(...) return foo1(a,1,c); else return c; }
Rvalue references
As for rvalue references, the compiler shall introduce a temporary variable before calling the ref function as has been discussed elsewhere. The same rules apply.
Copyright
This document has been placed in the Public Domain.