Difference between revisions of "User:Schuetzm/scope2"
(→scope inference) |
|||
(14 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | == | + | == Introduction == |
The current D language specification reserves the '''scope''' keyword in function signatures to specify that a parameter will not be escaped by the function, making it @safe to pass references to local variables or manually managed memory to it, among other things. This feature is currently unimplemented, apart from its use with lambdas where it guarantees the closure will be allocated on the stack instead of the GC. This proposal intends to change that. It will allow the safe and efficient implementation of various memory management strategies (including reference counting), as well as unified handling of references to GC, reference counted data, local variables, containers, and others. | The current D language specification reserves the '''scope''' keyword in function signatures to specify that a parameter will not be escaped by the function, making it @safe to pass references to local variables or manually managed memory to it, among other things. This feature is currently unimplemented, apart from its use with lambdas where it guarantees the closure will be allocated on the stack instead of the GC. This proposal intends to change that. It will allow the safe and efficient implementation of various memory management strategies (including reference counting), as well as unified handling of references to GC, reference counted data, local variables, containers, and others. | ||
− | The proposal is mostly a superset of [[DIP25]], but is generalized to all types of references and adds inference to alleviate the need for explicit annotations. | + | The proposal is mostly a superset of [[DIP25]], but is generalized to all types of references and adds inference to alleviate the need for explicit annotations. Credits are due to the authors of that DIP, ''Andrei'' and ''Walter'', then to ''Zach the Mystic'' who had the idea to generalize DIP25 as well as provided inspiration for the inference algorithm, ''deadalnix'' for his many valuable arguments, for example pointing out the intricacies of handling multiple indirections safely, and various other members of the community who provided useful contributions in past discussions in the news groups. |
+ | |||
+ | == Overview == | ||
=== Basics === | === Basics === | ||
Line 16: | Line 18: | ||
ubyte[1024] chunkOfData = ...; | ubyte[1024] chunkOfData = ...; | ||
sendData(chunkOfData); | sendData(chunkOfData); | ||
− | // this is @safe: no reference to the local | + | // this is @safe: no reference to the local has escaped |
someOtherFunction(chunkOfData); | someOtherFunction(chunkOfData); | ||
− | // this is @system: the callee gives no guarantees about | + | // this is @system: the callee gives no guarantees about the param |
} | } | ||
</source> | </source> | ||
Line 26: | Line 28: | ||
=== Implicit '''scope''' and opt-out === | === Implicit '''scope''' and opt-out === | ||
− | To reduce the need for manual annotations, @safe functions take all their reference parameters as '''scope'''. '''ref''' | + | To reduce the need for manual annotations, @safe functions take all their reference parameters as '''scope'''. '''ref''' implies '''scope''' even in @system functions. Because sometimes a @safe function may actually want to accept non-scope params, there is an opt-out in the form of '''static'''. Coupled with scope inference for templates, and an optional change like "@safe by default" (currently being discussed), this will get rid of most explicit scope annotations: |
<source lang="D"> | <source lang="D"> | ||
Line 43: | Line 45: | ||
=== '''scope''' for value types & overloading === | === '''scope''' for value types & overloading === | ||
− | '''scope''' applies to all types with indirections: pointers, slices, class references, '''ref''' parameters, delegates, and aggregates containing such. Functions | + | '''scope''' applies to all types with indirections: pointers, slices, class references, '''ref''' parameters, delegates, and aggregates containing such. Functions can be overloaded on '''scope'''. This allows efficient passing of RC wrappers for instance: |
<source lang="D"> | <source lang="D"> | ||
struct RC(T) if(is(T == class)) { | struct RC(T) if(is(T == class)) { | ||
// ... | // ... | ||
− | this( | + | this(this) static { |
// increment refcount | // increment refcount | ||
count++; | count++; | ||
} | } | ||
− | ~this() { | + | ~this() static { |
// decrement refcount | // decrement refcount | ||
if(--count == 0) | if(--count == 0) | ||
destroy(payload); | destroy(payload); | ||
} | } | ||
− | this( | + | this(this) scope { |
// DON'T increment refcount | // DON'T increment refcount | ||
} | } | ||
Line 86: | Line 88: | ||
All of this can be implemented in user code or in the standard library. The compiler doesn't need to be aware of reference counting. | All of this can be implemented in user code or in the standard library. The compiler doesn't need to be aware of reference counting. | ||
+ | |||
+ | The rules for overloading are: | ||
+ | * If only an overload accepting '''scope''' is defined, it is selected. | ||
+ | * If only an overload accepting '''static''' (the default) is defined, it can only be called if the argument also has static scope. | ||
+ | * If both overloads are defined, the static one is called for arguments with static scope, and the scope one for all others. | ||
+ | |||
+ | Because scope is inferred for templates, we must explicitly specify '''static''' and '''scope''' if we want to overload on them. | ||
=== Implicit conversions === | === Implicit conversions === | ||
Line 109: | Line 118: | ||
=== Returning scoped parameters === | === Returning scoped parameters === | ||
− | Some functions want to return a parameter that is passed in, or something reachable through one, e.g. a member of '''this'''. They can express this by annotating the parameter with the keyword '''return''', just as in [[DIP25]] | + | Some functions want to return a parameter that is passed in, or something reachable through one, e.g. a member of '''this'''. They can express this by annotating the parameter with the keyword '''return''', just as in [[DIP25]]: |
<source lang="D"> | <source lang="D"> | ||
Line 120: | Line 129: | ||
</source> | </source> | ||
− | To prevent accidental access to a member (e.g. ''payload'' in the above example), the member can be annotated with '''scope'''. The compiler will then treat it as if it | + | To specify that the value is returned through another parameter, the '''return!ident''' syntax can be used. If necessary, these annotations can be used multiple times per parameter, when the reference can be returned through several other parameters: |
+ | |||
+ | <source lang="D"> | ||
+ | int* foo( | ||
+ | scope int* input return return!output return!output2, | ||
+ | int** output, | ||
+ | out int* output2 | ||
+ | ); | ||
+ | </source> | ||
+ | |||
+ | To prevent accidental non-scoped access to a member (e.g. ''payload'' in the above example), the member can be annotated with '''scope'''. The compiler will then treat it as if it were always accessed through an appropriately annotated property that returns a (scoped) reference to it. | ||
The compiler will make sure the returned value is not used in any way that is un-@safe. In particular, it will verify that the returned references' lifetimes won't exceed the lifetimes of the arguments they're coming from. | The compiler will make sure the returned value is not used in any way that is un-@safe. In particular, it will verify that the returned references' lifetimes won't exceed the lifetimes of the arguments they're coming from. | ||
Line 126: | Line 145: | ||
=== '''scope''' inference === | === '''scope''' inference === | ||
− | For templates and nested functions, the compiler | + | For templates and nested functions, the compiler will infer the scope annotations, just as it infers purity and @safe-ty. Generic code therefore rarely needs any explicit annotations: |
<source lang="D"> | <source lang="D"> | ||
Line 142: | Line 161: | ||
=== Multiple indirections === | === Multiple indirections === | ||
− | Multiple indirections are also handled in a way that preserves the guarantees about lifetimes. Because '''scope''' is not a type modifier, it cannot encode information about the lifetimes of objects | + | Multiple indirections are also handled in a way that preserves the guarantees about lifetimes. Because '''scope''' is not a type modifier, it cannot encode information about the lifetimes of objects behind more than one indirection. Therefore, the compiler must be conservative. For the left-hand side of assignments, it must assume that the destination has infinite lifetime, while for the right-hand side, it must assume that the destination will vanish as soon as the reference through which it is accessed goes out of scope. |
=== @safe-ty violations with borrowing === | === @safe-ty violations with borrowing === | ||
− | When borrowing is combined with explicit, non lexical-scope based memory management (of which reference counting is one form), there will inevitably be problems as the one discussed in [http://forum.dlang.org/post/huspgmeupgobjubtsmfe@forum.dlang.org this forum thread]. To deal with them in a safe way requires some kind of data flow and aliasing analysis. Rust is an example of a language that uses very sophisticated analysis algorithms for that. This proposal will include a simplified algorithm to detect potentially unsafe uses at compile time, at the cost of detecting some false positives, for which there will however be workarounds. Instead of disallowing these operations, they will be treated as @system. It is therefore up to the end user to decide how to deal with them | + | When borrowing is combined with explicit, non lexical-scope based memory management (of which reference counting is one form), there will inevitably be problems as the one discussed in [http://forum.dlang.org/post/huspgmeupgobjubtsmfe@forum.dlang.org this forum thread]. To deal with them in a safe way requires some kind of data flow and aliasing analysis. Rust is an example of a language that uses very sophisticated analysis algorithms for that. This proposal will include a simplified algorithm to detect potentially unsafe uses at compile time, at the cost of detecting some false positives, for which there will however be workarounds. Instead of disallowing these operations, they will be treated as @system. It is therefore up to the end user to decide how to deal with them: they can make their code @trusted if they verify that it is indeed safe, but the compiler just can't know it, or they can rewrite it in a way that allows the compiler to proof the safety. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | ' | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | The operations that are potentially unsafe are: | |
+ | * borrowing from a mutable global variable | ||
+ | : Global variables can be accessed and therefore be mutated from anywhere. | ||
+ | * re-borrowing from a mutable variable to which another borrowed reference is currently accessible | ||
+ | : A @safe function can then assume that its parameters don't alias in a dangerous way. |
Latest revision as of 13:19, 25 March 2015
Contents
Introduction
The current D language specification reserves the scope keyword in function signatures to specify that a parameter will not be escaped by the function, making it @safe to pass references to local variables or manually managed memory to it, among other things. This feature is currently unimplemented, apart from its use with lambdas where it guarantees the closure will be allocated on the stack instead of the GC. This proposal intends to change that. It will allow the safe and efficient implementation of various memory management strategies (including reference counting), as well as unified handling of references to GC, reference counted data, local variables, containers, and others.
The proposal is mostly a superset of DIP25, but is generalized to all types of references and adds inference to alleviate the need for explicit annotations. Credits are due to the authors of that DIP, Andrei and Walter, then to Zach the Mystic who had the idea to generalize DIP25 as well as provided inspiration for the inference algorithm, deadalnix for his many valuable arguments, for example pointing out the intricacies of handling multiple indirections safely, and various other members of the community who provided useful contributions in past discussions in the news groups.
Overview
Basics
scope is a storage class; it will only be applicable to parameters in function signatures (which include the implicit this parameter for methods, as well as the context pointer for delegates). It will have the semantics one expects: when a function with a scope parameter returns, the corresponding argument will not have been stored in a global variable or on the heap, etc:
void sendData(scope ubyte[] data);
void someOtherFunction(ubyte[] data);
void main() {
ubyte[1024] chunkOfData = ...;
sendData(chunkOfData);
// this is @safe: no reference to the local has escaped
someOtherFunction(chunkOfData);
// this is @system: the callee gives no guarantees about the param
}
As we can see, certain operations, like taking the address of a local (or slicing of a fixed-size array, which is equivalent), no longer need to be @system per se. Instead, it's what is done with the resulting reference that decides whether it's @system or @safe.
Implicit scope and opt-out
To reduce the need for manual annotations, @safe functions take all their reference parameters as scope. ref implies scope even in @system functions. Because sometimes a @safe function may actually want to accept non-scope params, there is an opt-out in the form of static. Coupled with scope inference for templates, and an optional change like "@safe by default" (currently being discussed), this will get rid of most explicit scope annotations:
void doSomething(int[] data) @safe;
// equivalent to:
void doSomething(scope int[] data) @safe;
void foo(int[] input, static int* output) @safe;
// `input` is scope, `output` isn't
void bar(ref MyStruct s) @safe;
// equivalent to:
void bar(scope ref MyStruct s) @safe;
scope for value types & overloading
scope applies to all types with indirections: pointers, slices, class references, ref parameters, delegates, and aggregates containing such. Functions can be overloaded on scope. This allows efficient passing of RC wrappers for instance:
struct RC(T) if(is(T == class)) {
// ...
this(this) static {
// increment refcount
count++;
}
~this() static {
// decrement refcount
if(--count == 0)
destroy(payload);
}
this(this) scope {
// DON'T increment refcount
}
~this() scope {
// DON'T decrement refcount
}
// magic, to be explained later
alias borrow this;
}
void foo(scope MyClass object);
RC!MyClass global;
void bar(scope RC!MyClass object) {
if(some_condition)
global = object; // make a copy, adjust refcount
}
void main() {
RC!MyClass x = ...;
// auto conversion to MyClass, no refcount update:
foo(x);
// no refcount update at call site,
// no needless double indirection with `ref`:
bar(x);
}
All of this can be implemented in user code or in the standard library. The compiler doesn't need to be aware of reference counting.
The rules for overloading are:
- If only an overload accepting scope is defined, it is selected.
- If only an overload accepting static (the default) is defined, it can only be called if the argument also has static scope.
- If both overloads are defined, the static one is called for arguments with static scope, and the scope one for all others.
Because scope is inferred for templates, we must explicitly specify static and scope if we want to overload on them.
Implicit conversions
A scope parameter doesn't care how the data it refers to has been allocated. All it requires is that the reference stays valid for the duration of the function call. Therefore, it's a perfect fit for library functions. They don't need to be templated to support different resource management strategies of the library's user. It acts as a bridge between different types of strategies, just like const acts as a bridge between mutable and immutable data.
// no template bloat, no knowledge about RC etc.:
double computeAverage(scope int[] data);
void main() {
int[20] local = [1,2,3,...];
writeln(computeAverage(local)); // OK
int[] heap = ...;
writeln(computeAverage(heap)); // OK
RC!(int[]) rc = ...;
writeln(computeAverage(rc)); // OK
}
This is achieved by allowing non-scoped types to convert to scope implicitly. For builtin references, the language does this automatically. User-defined types must opt in by defining an appropriate alias this.
Returning scoped parameters
Some functions want to return a parameter that is passed in, or something reachable through one, e.g. a member of this. They can express this by annotating the parameter with the keyword return, just as in DIP25:
struct RC(T) if(is(T == class)) {
scope T payload;
T borrow() return { // `return` applies to `this`
return payload;
}
}
To specify that the value is returned through another parameter, the return!ident syntax can be used. If necessary, these annotations can be used multiple times per parameter, when the reference can be returned through several other parameters:
int* foo(
scope int* input return return!output return!output2,
int** output,
out int* output2
);
To prevent accidental non-scoped access to a member (e.g. payload in the above example), the member can be annotated with scope. The compiler will then treat it as if it were always accessed through an appropriately annotated property that returns a (scoped) reference to it.
The compiler will make sure the returned value is not used in any way that is un-@safe. In particular, it will verify that the returned references' lifetimes won't exceed the lifetimes of the arguments they're coming from.
scope inference
For templates and nested functions, the compiler will infer the scope annotations, just as it infers purity and @safe-ty. Generic code therefore rarely needs any explicit annotations:
T* foo(T)(T* a, T* b) {
static T* cache;
cache = b;
return a;
}
// `foo!int` will be inferred as:
int* foo_int(scope int* a return, static int* b);
// (`static` is the default anyway, only here for clarity)
Multiple indirections
Multiple indirections are also handled in a way that preserves the guarantees about lifetimes. Because scope is not a type modifier, it cannot encode information about the lifetimes of objects behind more than one indirection. Therefore, the compiler must be conservative. For the left-hand side of assignments, it must assume that the destination has infinite lifetime, while for the right-hand side, it must assume that the destination will vanish as soon as the reference through which it is accessed goes out of scope.
@safe-ty violations with borrowing
When borrowing is combined with explicit, non lexical-scope based memory management (of which reference counting is one form), there will inevitably be problems as the one discussed in this forum thread. To deal with them in a safe way requires some kind of data flow and aliasing analysis. Rust is an example of a language that uses very sophisticated analysis algorithms for that. This proposal will include a simplified algorithm to detect potentially unsafe uses at compile time, at the cost of detecting some false positives, for which there will however be workarounds. Instead of disallowing these operations, they will be treated as @system. It is therefore up to the end user to decide how to deal with them: they can make their code @trusted if they verify that it is indeed safe, but the compiler just can't know it, or they can rewrite it in a way that allows the compiler to proof the safety.
The operations that are potentially unsafe are:
- borrowing from a mutable global variable
- Global variables can be accessed and therefore be mutated from anywhere.
- re-borrowing from a mutable variable to which another borrowed reference is currently accessible
- A @safe function can then assume that its parameters don't alias in a dangerous way.