User talk:Schuetzm/scope2
Example for the inference algorithm
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 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
}
Examples for 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) {
T[] sub;
// => SCOPE(sub) := [] (incomplete)
sub = haystack[i .. i + needle.length];
// => SCOPE(haystack) |= SCOPE(sub)
// => DEFER because SCOPE(sub) is incomplete
if(sub == needle) {
return haystack[i .. $];
// => SCOPE(haystack) |= SCOPE(return) = [] | [return] = [return]
}
}
return null;
// nothing to do here, `null` has fixed static scope
// ---------------------------------------------------
// we now have:
// SCOPE(haystack) = [return]
// SCOPE(needle) = []
// SCOPE(sub) = []
// unresolved:
// SCOPE(haystack) |= SCOPE(sub)
// resolve:
// SCOPE(haystack) := [return] | [] = [return]
// => all resolved
// ---------------------------------------------------
// => satisfiable, now let's check the assignments:
for(int i = 0; i < haystack.length - needle.length) {
T[] sub;
sub = haystack[i .. i + needle.length];
// [] := [return] => OK
if(sub == needle) {
// equivalent to: if(opEquals(sub, needle))
// let's assume `opEquals` takes both params by scope
// sub: [] := [] => OK
// 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);
T chooseStringAtRandom(T)(T a, T b) {
// => SCOPE(a) = [] (incomplete)
// => SCOPE(b) = [] (incomplete)
return random() % 2 == 0 ? a : b;
// ?: operator affects both `a` and `b`
// => SCOPE(a) |= SCOPE(return) = [] | [return] = [return]
// => SCOPE(b) |= SCOPE(return) = [] | [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);