User talk:Schuetzm/scope2

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) := [b] (final)
    b = a;
    // scope of `a` is fixed => do nothing
    int d;
    int* c;
    // => SCOPE(c) := [c] (incomplete)
    c = &d;
    *b = c;
    // assignment from `c`:
    // => SCOPE(c) |= SCOPE(*b) = [c] | [static] (final)
    // (dereferencing loses information => static)
    // ---------------------------------------------------
    // we now have:
    // SCOPE(a) = [a]
    // SCOPE(b) = [b]
    // SCOPE(c) = [static]
    // => all resolved
    // ---------------------------------------------------
    // => satisfiable, now let's check the assignments:

    int** b = a;        // [b]      := [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) := [a] (incomplete)
    T** b;
    // start with empty scope for locals
    // => SCOPE(b) := [b] (final)
    b = a;
    // only access to `a`:
    // => SCOPE(a) |= SCOPE(b) = [a] | [b] = [a]
    T d;
    T* c;
    // => SCOPE(c) = [c] (incomplete)
    c = &d;
    *b = c;
    // assignment from `c`:
    // => SCOPE(c) |= SCOPE(*b) = [c] | [static] = [static]
    // ---------------------------------------------------
    // we now have:
    // SCOPE(a) = [a]
    // SCOPE(b) = [b]
    // SCOPE(c) = [static]
    // => all resolved
    // ---------------------------------------------------
    // => satisfiable, now let's check the assignments:

    int** b = a;        // [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) := [b] (final)
    b = a;
    // scope of `a` is fixed => do nothing
    int d;
    int* c;
    // => SCOPE(c) := [c] (incomplete)
    c = &d;
    *b = c;
    // assignment from `c`:
    // => SCOPE(c) |= SCOPE(*b) = [c] | [static] (final)
    // ---------------------------------------------------
    // we now have:
    // SCOPE(a) = [static]
    // SCOPE(b) = [b]
    // SCOPE(c) = [static]
    // => all resolved
    // ---------------------------------------------------
    // => satisfiable, now let's check the assignments:

    int** b = a;        // [b]      := [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) := [haystack] (incomplete)
    // => SCOPE(needle)   := [needle] (final)

    for(int i = 0; i < haystack.length - needle.length; i++) {
        T[] sub;
        // => SCOPE(sub) := [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) {
            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) = [a] (incomplete)
    // => SCOPE(b) = [a] (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) := [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) := [b] (final)
    b = chooseStringAtRandom(s1, a);
    // SCOPE(s1[]) = [s1] (final)
    // `a` is returned and stored in `b`
    // => SCOPE(a) |= SCOPE(b) = [a] | [b] = [a] (final)
    // ---------------------------------------------------
    // we now have:
    // SCOPE(a) = [a]
    // SCOPE(b) = [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) = [haystack] (incomplete)
    // => SCOPE(needle)   = [needle] (final)
    import std.conv : to;
    // ignoring the writeln(), works as usual
    writeln("Calling findSubstring(...)");
    return findSubstring(haystack, needle);
    // `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) = [input]
    odd_FilterImpl tmp;
    // => SCOPE(tmp) = [tmp]
    ref tmp2 = tmp.prop_input;
    // => SCOPE(tmp2) = [tmp2]
    // 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;
    // `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) = [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) := [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);