User talk:Schuetzm/scope2
Contents
Example for the inference algorithm
Dereferencing yields static scope
Note that this is depending on whether we're on the LHS or RHS of an assignment. The inference algorithm only assigns scopes from LHS to RHS; therefore we always use static. On the RHS, a dereference gets the scope of the reference it's been reached through, because we at least known that it can't have a shorter lifetime than that.
Dereferencing includes the dereference operator, implicit dereferencing of struct/union pointers, of class references, as well as indexing and slicing.
Applied to the function deadalnix used to demonstrate the rvalue/lvalue problem:
(1) foo() is @safe, making its param scoped:
void foo(scope int** a) {
// no inference for `a` => self-owned
// ("mystery scope" in your terms)
// => SCOPE(a) := [a] (final)
int** b;
// => SCOPE(b) := [] (incomplete)
b = a;
// scope of `a` is fixed => do nothing
int d;
int* c;
// => SCOPE(c) := [] (incomplete)
c = &d;
*b = c;
// assignment from `c`:
// => SCOPE(c) |= SCOPE(*b) = [] | [static] (final)
// (dereferencing loses information => static)
// ---------------------------------------------------
// we now have:
// SCOPE(a) = [a]
// SCOPE(b) = []
// SCOPE(c) = [static]
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
int** b = a; // [] := [a] => OK
int d;
int* c = &d; // [static] := [d] => BAD
*b = c; // [static] := [static] => OK
// => invalid assignment
// note how it even traces where the bad value comes from
}
(2) foo() is in a template, param scope gets inferred
void foo(T)(T** a) {
// start with empty scope for params
// => SCOPE(a) := [] (incomplete)
T** b;
// start with empty scope for locals
// => SCOPE(b) := [] (incomplete)
b = a;
// only access to `a`:
// => SCOPE(a) |= SCOPE(b)
// => DEFER because SCOPE(b) is incomplete
T d;
T* c;
// => SCOPE(c) = [] (incomplete)
c = &d;
*b = c;
// assignment from `c`:
// => SCOPE(c) |= SCOPE(*b) = [] | [static] = [static]
// ---------------------------------------------------
// we now have:
// SCOPE(a) = []
// SCOPE(b) = []
// SCOPE(c) = [static]
// unresolved:
// SCOPE(a) |= SCOPE(b)
// resolve:
// SCOPE(a) := [] | [] = []
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
int** b = a; // [] := [] => OK
int d;
int* c = &d; // [static] := [d] => BAD
*b = c; // [static] := [static] => OK
// => invalid assignment
// again, the culprit can be detected
}
(3) foo() takes unscoped pointer
void foo(int** a) {
// no inference for `a` => static
// => SCOPE(a) := [static] (final)
int** b;
// => SCOPE(b) := [] (incomplete)
b = a;
// scope of `a` is fixed => do nothing
int d;
int* c;
// => SCOPE(c) := [] (incomplete)
c = &d;
*b = c;
// assignment from `c`:
// => SCOPE(c) |= SCOPE(*b) = [] | [static] (final)
// ---------------------------------------------------
// we now have:
// SCOPE(a) = [static]
// SCOPE(b) = []
// SCOPE(c) = [static]
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
int** b = a; // [] := [static] => OK
int d;
int* c = &d; // [static] := [d] => BAD
*b = c; // [static] := [static] => OK
// => invalid assignment
// escape detection for locals works even without scope params
// and in @system code
}
return inference
T[] findSubstring(T)(T[] haystack, T[] needle) {
// find first occurrence of substring
// naive implementation
// => SCOPE(return) := [return] (fixed)
// [return] is a scope higher than all params
// => SCOPE(haystack) := [] (incomplete)
// => SCOPE(needle) := [] (incomplete)
for(int i = 0; i < haystack.length - needle.length; i++) {
// haystack and needle are read here, but not assigned
// => need large enough scope to be accessible at this point
// use the variables' lifetimes
// => SCOPE(haystack) |= [haystack] = [haystack] (incomplete)
// => SCOPE(needle) |= [needle] = [needle] (incomplete)
// (this is optional; instead, we could just assign them their own lifetimes)
T[] sub;
// => SCOPE(sub) := [] (incomplete)
sub = haystack[i .. i + needle.length];
// haystack and needle are read again; ignoring from now on
// => SCOPE(haystack) |= SCOPE(sub)
// => DEFER because SCOPE(sub) is incomplete
if(sub == needle) {
// sub is read here
// => SCOPE(sub) |= [sub] = [sub] (final)
return haystack[i .. $];
// => SCOPE(haystack) |= SCOPE(return) = [haystack] | [return] = [return]
}
}
return null;
// nothing to do here, `null` has fixed static scope
// ---------------------------------------------------
// we now have:
// SCOPE(haystack) = [return]
// SCOPE(needle) = [needle]
// SCOPE(sub) = [sub]
// unresolved:
// SCOPE(haystack) |= SCOPE(sub)
// resolve:
// SCOPE(haystack) := [return] | [sub] = [return]
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
for(int i = 0; i < haystack.length - needle.length; i++) {
T[] sub;
sub = haystack[i .. i + needle.length];
// [sub] := [return] => OK
if(sub == needle) {
// equivalent to: if(opEquals(sub, needle))
// let's assume `opEquals` takes both params by scope
// sub: [] := [sub] => OK
// needle: [] := [needle] => OK
return haystack[i .. $];
// [return] := [return] => OK
}
}
return null;
// [return] := [static] => OK
}
// the inferred signature for T == immutable(char) is then
string findSubstring(scope string haystack return, scope string needle);
Multiple return params:
T chooseStringAtRandom(T)(T a, T b) {
// => SCOPE(a) = [] (incomplete)
// => SCOPE(b) = [] (incomplete)
return random() % 2 == 0 ? a : b;
// => SCOPE(a) |= [a] = [a]
// => SCOPE(b) |= [b] = [b]
// ?: operator affects both `a` and `b`
// => SCOPE(a) |= SCOPE(return) = [a] | [return] = [return]
// => SCOPE(b) |= SCOPE(return) = [b] | [return] = [return]
// ---------------------------------------------------
// we now have:
// SCOPE(a) = [return]
// SCOPE(b) = [return]
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
return random() % 2 == 0 ? a : b;
// RHS SCOPE(cond ? a : b) = MIN(SCOPE(a), SCOPE(b)) =
// = MIN([return], [return]) = [return]
// [return] := [return] => OK
}
// the inferred signature for T == string is then
string chooseStringAtRandom(scope string a return, scope string b return);
Calling functions
string global_string;
void foo() {
string[13] text = "Hello, world!";
// => nothing, string[13] has no indirections
string a;
// => SCOPE(a) := [] (incomplete)
a = findSubstring(text, "world");
// equivalent to: ... findSubstring(text[], ...)
// text[] is returned, but SCOPE(text[]) is fixed
// => no inference
global_string = findSubstring(text, "world");
// ditto
string[5] s1 = "Hello";
string b;
// => SCOPE(b) := [] (final)
b = chooseStringAtRandom(s1, a);
// SCOPE(s1[]) = [s1] (final)
// `a` is read
// => SCOPE(a) |= [a] = [] | [a] = [a] (incomplete)
// `a` is returned and stored in `b`
// => SCOPE(a) |= SCOPE(b) = [a] | [] = [a] (final)
// ---------------------------------------------------
// we now have:
// SCOPE(a) = [a]
// SCOPE(b) = []
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
string[13] text = "Hello, world!";
string a;
a = findSubstring(text, "world");
// equivalent to: ... findSubstring(text[], ...)
// findSubstring takes both params as scope
// text[]: [] := [text] => OK
// "world": [] := [static] => OK
// findSubstring returns haystack
// => equivalent to `a = text[]`
// return: [a] := [text] => OK
global_string = findSubstring(text, "world");
// [static] := [text] => BAD
string[5] s1 = "Hello";
string b;
b = chooseStringAtRandom(s1, a);
// [b] := MIN([s1], [a]) = [s1] => // OK
// ---------------------------------------------------
// => invalid assignment to global_string
}
Wrappers
string findSubstring(scope string haystack return, scope string needle);
auto trace(alias func, Args...)(Args args) {
import std.conv : to;
writeln("Calling " ~ func.stringof ~ "(" ~ args.to!string ~ ")");
return func(args);
}
auto s = trace!findSubstring(haystack, needle);
// expands to (scope/return not yet in the signature):
string trace_findSubstring(string haystack, string needle) {
// => SCOPE(haystack) = [] (incomplete)
// => SCOPE(needle) = [] (incomplete)
import std.conv : to;
// ignoring the writeln(), works as usual
writeln("Calling findSubstring(...)");
return findSubstring(haystack, needle);
// reading haystack & needle
// => SCOPE(haystack) |= [haystack] = [haystack] (incomplete)
// => SCOPE(needle) |= [needle] = [needle] (final)
// `haystack` is assigned to the return value
// => SCOPE(haystack) |= [return] = [haystack] | [return] = [return] (final)
// ---------------------------------------------------
// we now have:
// SCOPE(haystack) = [return]
// SCOPE(needle) = [needle]
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
return findSubstring(haystack, needle);
// haystack: [] := [return] => OK
// needle: [] := [needle] => OK
// return: [return] := SCOPE(haystack) = [return] => OK
}
// inferred annotations:
string trace_findSubstring(scope string haystack return, scope string needle);
auto filter(alias pred, T)(T input) {
static struct FilterImpl {
private scope T _input;
private void skip() {
while(!_input.empty && !pred(_input.front))
_input.popFront();
}
@property ElementType!T front() {
skip();
return _input.front;
}
@property bool empty() {
skip();
return _input.empty;
}
void popFront() {
_input.popFront();
}
}
return FilterImpl(input);
}
alias odd = filter!(n => n % 2, int[]);
// becomes (without annotations):
auto odd_filter(int[] input) {
static struct odd_FilterImpl {
private scope int[] _input;
// scope member is equivalent to:
private @property ref prop_input() return { return _input; }
private void skip() {
// `empty`, `front` and `popFront` are template functions
// => their scope/return annotations are inferred as needed
// => they take _input as scope
while(!_input.empty && !(_input.front % 2))
_input.popFront();
}
@property int front() {
// can be inferred to take `this` as scope
skip();
return _input.front;
}
@property bool empty() {
// ditto
skip();
return _input.empty;
}
void popFront() {
// ditto
_input.popFront();
}
}
return odd_FilterImpl(input);
// equivalent to:
odd_FilterImpl tmp;
tmp._input = input;
return tmp;
// equivalent to:
// => SCOPE(input) = []
odd_FilterImpl tmp;
// => SCOPE(tmp) = []
ref tmp2 = tmp.prop_input;
// => SCOPE(tmp2) = []
// read `tmp`:
// => SCOPE(tmp) |= [tmp] = [tmp] (incomplete)
// call `tmp.prop_input`:
// (`this` is returned and assigned to `tmp2`)
// => SCOPE(tmp) |= SCOPE(tmp2)
// => DEFER because tmp2 is incomplete
// `tmp2` is a ref => assume it will be written to
// => SCOPE(tmp2) |= SCOPE(tmp)
// => DEFER because tmp is incomplete
tmp2 = input;
// `tmp2` is read
// => SCOPE(tmp2) |= [tmp2] = [tmp2] (incomplete)
// `input` is assigned to `tmp2`
// => SCOPE(input) |= SCOPE(tmp2)
// => DEFER because tmp2 is incomplete
return tmp;
// => SCOPE(tmp) |= [return] = [return] (incomplete)
// doesn't need to be deferred, because `|` is commutative
// ---------------------------------------------------
// we now have:
// SCOPE(input) = []
// SCOPE(tmp) = [return]
// SCOPE(tmp2) = [tmp2]
// unresolved:
// SCOPE(tmp) |= SCOPE(tmp2)
// SCOPE(tmp2) |= SCOPE(tmp)
// SCOPE(input) |= SCOPE(tmp2)
// resolve loop using union:
// SCOPE(tmp) := [return] | [tmp2] = [return]
// SCOPE(tmp2) := [return] | [tmp2] = [return]
// unresolved:
// SCOPE(input) |= SCOPE(tmp2)
// resolve:
// SCOPE(input) := [] | [return] = [return]
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
odd_FilterImpl tmp;
ref tmp2 = tmp.prop_input;
// call (`tmp` is the implicit `this` argument):
// [] := [return] => OK
// `tmp` is returned and assigned to `tmp2`
// [return] := [return] => OK
tmp2 = input;
// [return] := [return] => OK
return tmp;
// [return] := [return] => OK
}
// inferred signature:
// - SCOPE(input) is not [static]
// => `input` can be `scope`
// - SCOPE(input) refers to [return]
// => `input` is annotated with `return`
auto odd_filter(scope int[] input return);
Unused stores are ignored
void foo() {
int* a, b;
// => SCOPE(a) = [] (incomplete)
// => SCOPE(b) = [] (final)
{
int x;
a = &x;
b = &x;
}
writeln(*a);
// as is read => make sure its scope is large enough
// => SCOPE(a) |= [a] = [] | [a] = [a] (final)
// ---------------------------------------------------
// we now have:
// SCOPE(a) = [a]
// SCOPE(b) = []
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
int* a, b;
// default initialization: a = b = null
// a: [a] := [static] => OK
// b: [] := [static] => OK
{
int x;
a = &x; // [a] := [x] => BAD
b = &x; // [] := [x] => OK
}
writeln(*a);
// deref: [] := [a] => OK
// => note how the dead value in `b` is ignored
// this allows slightly more flexibility and avoids
// a few false positives
}
