On Friday, 27 February 2015 at 23:18:24 UTC, Marc Schütz wrote:
> * When a scoped value is stored somewhere, it is then reachable through the destination. Therefore, assuming the source's scope is fixed, the destination's scope must be widened to accommodate the source's scope.

So, when you are referring to scope here; you are referring to the scope of the indirection, right ?

You don't cover the lifetime of the address of operation, and I'm not how this is supposed to work in your proposal.

> I will also add examples how return and static annotations are handled.

static annotation ? Seems like a bad idea and I'm sure we can do without.

On Friday, 27 February 2015 at 23:18:24 UTC, Marc Schütz wrote:
> I think I have an inference algorithm that works. It can infer the required scope levels for local variables given the constraints of function parameters, and it can even infer the annotations for the parameters (in template functions). It can also cope with local variables that are explicitly declared as `scope`, though these are mostly unnecessary.
>
> Interestingly, the rvalue/lvalue problem deadalnix found is only relevant during assignment checking, but not during inference. That's because we are free to widen the scope of variables that are to be inferred as needed.
>
> It's based on two principles:
>
> * We start with the minimum possible scope a variable may have, which is empty for local variables, and its own lifetime for parameters.
> * When a scoped value is stored somewhere, it is then reachable through the destination. Therefore, assuming the source's scope is fixed, the destination's scope must be widened to accommodate the source's scope.
> * From the opposite viewpoint, a value that is to be stored somewhere must have at least the destination's scope. Therefore, assuming the destination's scope is fixed, the source's scope needs to be widened accordingly.
>
> I haven't formalized it yet, but I posted a very detailed step-by-step demonstration on my wiki talk page (nicer to read because it has syntax highlighting):
> http://wiki.dlang.org/User_talk:Schuetzm/scope2

I need to sleep as well right now. But I still don't understand where the cycles come from. Taken from your example:

*b = c;
// assignment from `c`:
// => SCOPE(c) |= SCOPE(*b)
// => DEFER because SCOPE(*b) = SCOPE(b) is incomplete

`c` is merely being copied, but you indicate here that it will now inherit b's (or some part of b's) scope. Why would c's scope inherit b's when it is merely being copied and not written to?

On Friday, 27 February 2015 at 23:37:42 UTC, deadalnix wrote:
> On Friday, 27 February 2015 at 23:18:24 UTC, Marc Schütz wrote:
>> * When a scoped value is stored somewhere, it is then reachable through the destination. Therefore, assuming the source's scope is fixed, the destination's scope must be widened to accommodate the source's scope.
>
> So, when you are referring to scope here; you are referring to the scope of the indirection, right ?
>

Yes. Terminology is a problem here, I guess. When I talk about "the scope" of a variable, it means that only references to values can be stored there whose lifetimes are at least as large as the scope.

> You don't cover the lifetime of the address of operation, and I'm not how this is supposed to work in your proposal.
>

It was in the examples, but it was wrong. I've corrected it: A dereference results in static lifetime.

>> I will also add examples how return and static annotations are handled.
>
> static annotation ? Seems like a bad idea and I'm sure we can do without.

It's only necessary if parameters of `@safe` functions are automatically scoped; then we need a way to opt-out. This is actually optional and does not affect the consistency, but I thought it is a good idea, because it reduces the overall amount of annotations. And I assume that most @safe functions are already written in a way that conforms to this. We'd need to analyze some code bases to find out whether this is actually true.

On Saturday, 28 February 2015 at 06:37:40 UTC, Zach the Mystic
wrote:
> On Friday, 27 February 2015 at 23:18:24 UTC, Marc Schütz wrote:
>> I think I have an inference algorithm that works. It can infer the required scope levels for local variables given the constraints of function parameters, and it can even infer the annotations for the parameters (in template functions). It can also cope with local variables that are explicitly declared as `scope`, though these are mostly unnecessary.
>>
>> Interestingly, the rvalue/lvalue problem deadalnix found is only relevant during assignment checking, but not during inference. That's because we are free to widen the scope of variables that are to be inferred as needed.
>>
>> It's based on two principles:
>>
>> * We start with the minimum possible scope a variable may have, which is empty for local variables, and its own lifetime for parameters.
>> * When a scoped value is stored somewhere, it is then reachable through the destination. Therefore, assuming the source's scope is fixed, the destination's scope must be widened to accommodate the source's scope.
>> * From the opposite viewpoint, a value that is to be stored somewhere must have at least the destination's scope. Therefore, assuming the destination's scope is fixed, the source's scope needs to be widened accordingly.
>>
>> I haven't formalized it yet, but I posted a very detailed step-by-step demonstration on my wiki talk page (nicer to read because it has syntax highlighting):
>> http://wiki.dlang.org/User_talk:Schuetzm/scope2
>
> I need to sleep as well right now. But I still don't understand where the cycles come from. Taken from your example:
>
> *b = c;
> // assignment from `c`:
> // => SCOPE(c) |= SCOPE(*b)
> // => DEFER because SCOPE(*b) = SCOPE(b) is incomplete
>
> `c` is merely being copied, but you indicate here that it will now inherit b's (or some part of b's) scope. Why would c's scope inherit b's when it is merely being copied and not written to?

Should have written that after I slept :-P The second point
(widening the destinations scope) is wrong, it would need to be
narrowed. But it's also unnecessary.

However, the part you quoted is still relevant (though also
wrong): This is only about inference, not about checking. We
start with the smallest possible scope (empty: []), and
successively widen the scope, until all assignments are valid. In
the extreme case, the scope will be widened to [static], because,
no matter how restricted a destination is, it can always contain
a reference to a value with infinite lifetime.

I corrected the examples, and I'm now going to add another one
that shows how `return` inference works.

I encountered an ugly problem. Actually, I had already run into it in my first proposal, but Steven Schveighoffer just posted about it here, which made me aware again:

http://forum.dlang.org/thread/mcqcor$aa$1@digitalmars.com#post-mcqk4s:246qb:241:40digitalmars.com

    class T {
        void doSomething() scope;
    }
    struct S {
        RC!T t;
    }
    void main() {
        auto s = S(RC!T()); // `s.t`'s refcount is 1
        foo(s, s.t);        // borrowing, no refcount changes
    }
    void foo(ref S s, scope T t) {
        s.t = RC!T();       // drops the old `s.t`
        t.doSomething();    // oops, `t` is gone
    }

This (and similar things) are the reason I introduced "const borrowing", a way for an object to make itself temporarily const, as long as borrowed references to it exist. Unfortunately, this was broken in the presence of aliasing: When another alias (in the above example, imagine another pointer to `s`) of the owning struct existed before the borrowing took place, it was not affected by the change to const.

Now that I know a bit more about linear type systems (but am not an expert by any means), I understand why it happens. I suspect that the only way to really prevent problems of this kind is a full blown linear type system, i.e. one that guarantees that to each object there is at most one mutable reference.

The question is: What do we do about it? Maybe there is actually a way to fix this problem without a borrow checker? Any type system gurus here?

Or we could simply live with it and make it a convention not to pass RC objects (or related types) into situations where it can be a problem. I don't like that option, though.

Or we implement a borrow checker... It doesn't have to be as fancy as Rust's, i.e. we don't need to have data flow analysis. Just a lexical scope based solution would work.

Any other ideas and opinions?

On a positive note, I did some experiments with the inference algorithm, and I'm reasonably sure it works (absent un-@safe operations like `delete` and `free()`, of course). Here are the examples:

http://wiki.dlang.org/User_talk:Schuetzm/scope2

I'm going to try and formalize it during the next days.

On Saturday, 28 February 2015 at 11:12:23 UTC, Marc Schütz wrote:
> On Friday, 27 February 2015 at 23:37:42 UTC, deadalnix wrote:
>> You don't cover the lifetime of the address of operation, and I'm not how this is supposed to work in your proposal.
>>
>
> It was in the examples, but it was wrong. I've corrected it: A dereference results in static lifetime.

... but only on the LHS of an assignment; on the RHS its the scope of the reference it comes from (it's lifetime is at least as long as that of the reference).

On Saturday, 28 February 2015 at 20:49:22 UTC, Marc Schütz wrote:
> Any other ideas and opinions?

I'm a little busy. It'll take me some time. There's a lot going on in recent days with all these ideas.

On Saturday, 28 February 2015 at 20:49:22 UTC, Marc Schütz wrote:
> I encountered an ugly problem. Actually, I had already run into it in my first proposal, but Steven Schveighoffer just posted about it here, which made me aware again:
>
> http://forum.dlang.org/thread/mcqcor$aa$1@digitalmars.com#post-mcqk4s:246qb:241:40digitalmars.com
>
>     class T {
>         void doSomething() scope;
>     }
>     struct S {
>         RC!T t;
>     }
>     void main() {
>         auto s = S(RC!T()); // `s.t`'s refcount is 1
>         foo(s, s.t);        // borrowing, no refcount changes
>     }
>     void foo(ref S s, scope T t) {
>         s.t = RC!T();       // drops the old `s.t`
>         t.doSomething();    // oops, `t` is gone
>     }

One quick thing. I suggest a solution here:

http://forum.dlang.org/post/jycylhdhdewtgumbavep@forum.dlang.org

You do the checking and adding in the called function, not the caller. The algorithm:

1. Keep a compile-time refcount per function. Does the parameter get released, i.e. does the refcount ever go below 1? If not, stop.

2. Can the parameter contain (as a member) a reference to a refcounted struct of the types of any of the other parameters? If not, stop.

3. Okay, you need to preserve the reference. Add a call to opAdd at the beginning and one to opRelease at the end of the function. Done.

On Sunday, 1 March 2015 at 05:29:19 UTC, Zach the Mystic wrote:
> On Saturday, 28 February 2015 at 20:49:22 UTC, Marc Schütz wrote:
>> I encountered an ugly problem. Actually, I had already run into it in my first proposal, but Steven Schveighoffer just posted about it here, which made me aware again:
>>
>> http://forum.dlang.org/thread/mcqcor$aa$1@digitalmars.com#post-mcqk4s:246qb:241:40digitalmars.com
>>
>>    class T {
>>        void doSomething() scope;
>>    }
>>    struct S {
>>        RC!T t;
>>    }
>>    void main() {
>>        auto s = S(RC!T()); // `s.t`'s refcount is 1
>>        foo(s, s.t);        // borrowing, no refcount changes
>>    }
>>    void foo(ref S s, scope T t) {
>>        s.t = RC!T();       // drops the old `s.t`
>>        t.doSomething();    // oops, `t` is gone
>>    }
>
> One quick thing. I suggest a solution here:
>
> http://forum.dlang.org/post/jycylhdhdewtgumbavep@forum.dlang.org
>
> You do the checking and adding in the called function, not the caller. The algorithm:
>
> 1. Keep a compile-time refcount per function. Does the parameter get released, i.e. does the refcount ever go below 1? If not, stop.
>
> 2. Can the parameter contain (as a member) a reference to a refcounted struct of the types of any of the other parameters? If not, stop.
>
> 3. Okay, you need to preserve the reference. Add a call to opAdd at the beginning and one to opRelease at the end of the function. Done.

I don't think a callee-based solution can work:

    class T {
        void doSomething() scope;
    }
    struct S {
        RC!T t;
    }
    void main() {
        auto s = S(RC!T()); // `s.t`'s refcount is 1
        T t = s.t;          // borrowing from the RC wrapper
        foo(s);
        t.doSomething();    // oops, `t` is gone
    }
    void foo(ref S s) {
        s.t = RC!T();       // drops the old `s.t`
    }

`foo()` has no idea whether there are still `scope` borrowings to `s.t`.

Therefore, if there _is_ a solution, it needs to work inside the caller. You second idea [1] goes in the right direction. Unfortunately, it is DIP74 specific; in this form, it cannot be applied to user-defined struct-based RC wrappers. (DIP25 is also affected by this problem, by the way.)

To keep the compiler agnostic about the purpose of the structs in question, I'm afraid the only solution is uniqueness tracking. If `@unique` we're a property of references, we could either automatically make those references `const` when more than one reference exists, or disallow passing these values to functions if the corresponding parameter is annotated @unique.

Unfortunately, this is likely to be a very invasive change, in contrast to `scope` :-(

[1] http://forum.dlang.org/post/bghjqvvrdcfqmoiyyuqz@forum.dlang.org

On Saturday, 28 February 2015 at 11:12:23 UTC, Marc Schütz wrote:
> Yes. Terminology is a problem here, I guess. When I talk about "the scope" of a variable, it means that only references to values can be stored there whose lifetimes are at least as large as the scope.
>

Make sure you explicit that. The variable itself has a scope, and this scope is different from the scope of indirections stored in the variable.

Additionally, this naturally bring the question of multiple indirection in a variable (for a struct for instance).

>> You don't cover the lifetime of the address of operation, and I'm not how this is supposed to work in your proposal.
>>
>
> It was in the examples, but it was wrong. I've corrected it: A dereference results in static lifetime.
>

Will do a second pass on the damn thing :)

>>> I will also add examples how return and static annotations are handled.
>>
>> static annotation ? Seems like a bad idea and I'm sure we can do without.
>
> It's only necessary if parameters of `@safe` functions are automatically scoped; then we need a way to opt-out. This is actually optional and does not affect the consistency, but I thought it is a good idea, because it reduces the overall amount of annotations. And I assume that most @safe functions are already written in a way that conforms to this. We'd need to analyze some code bases to find out whether this is actually true.

Ok I misunderstood what you meant by static anotation. Sounds good. Scope by default, and an optout.

Problem is transition. We have a scope keyword what does it become ?