User talk:Schuetzm/scope2
Contents
Example for the inference algorithm
Dereferencing yields return scope
return is a special scope that's higher than any parameters, but lower than static.
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) = [] | [return] (final)
// (dereferencing loses information => return)
// ---------------------------------------------------
// we now have:
// SCOPE(a) = [a]
// SCOPE(b) = []
// SCOPE(c) = [return]
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
int** b = a; // [] := [a] => OK
int d;
int* c = &d; // [return] := [d] => BAD
*b = c; // [return] := [return] => 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) = [] | [return] = [return]
// ---------------------------------------------------
// we now have:
// SCOPE(a) = []
// SCOPE(b) = []
// SCOPE(c) = [return]
// 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; // [return] := [d] => BAD
*b = c; // [return] := [return] => 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) = [] | [return] (final)
// ---------------------------------------------------
// we now have:
// SCOPE(a) = [static]
// SCOPE(b) = []
// SCOPE(c) = [return]
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
int** b = a; // [] := [static] => OK
int d;
int* c = &d; // [return] := [d] => BAD
*b = c; // [return] := [return] => 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
}
