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);